SigKeyPair.mk.{u_1, u_2}
  {PK_sigType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
  {SK_sigType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. } (pkPK_sig : PK_sigType u_1)
  (skSK_sig : SK_sigType u_2) :
  SigKeyPairSigKeyPair.{u_1, u_2} (PK_sig : Type u_1) (SK_sig : Type u_2) : Type (max u_1 u_2)§2.5, p. 472 assumption 2: A key pair for a signature scheme, coupling
a public verification key with the corresponding signing key.  PK_sigType u_1 SK_sigType u_2

Sig.mk.{u_1, u_2, u_3, u_4}
  {PK_sigType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
  {SK_sigType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. } {MType u_3 : Type u_3A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
  {SType u_4 : Type u_4A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
  (keygenSigKeyPair PK_sig SK_sig : SigKeyPairSigKeyPair.{u_1, u_2} (PK_sig : Type u_1) (SK_sig : Type u_2) : Type (max u_1 u_2)§2.5, p. 472 assumption 2: A key pair for a signature scheme, coupling
a public verification key with the corresponding signing key.  PK_sigType u_1 SK_sigType u_2)
  (signSK_sig → M → S : SK_sigType u_2 → MType u_3 → SType u_4)
  (verifyPK_sig → M → S → Bool : PK_sigType u_1 → MType u_3 → SType u_4 → BoolBool : TypeThe Boolean values, `true` and `false`.

Logically speaking, this is equivalent to `Prop` (the type of propositions). The distinction is
public important for programming: both propositions and their proofs are erased in the code generator,
while `Bool` corresponds to the Boolean type in most programming languages and carries precisely one
bit of run-time information.
)
  (correctness∀ (m : M), verify keygen.pk m (sign keygen.sk m) = true :
    ∀ (mM : MType u_3),
      verifyPK_sig → M → S → Bool keygenSigKeyPair PK_sig SK_sig.pkSigKeyPair.pk.{u_1, u_2} {PK_sig : Type u_1} {SK_sig : Type u_2} (self : SigKeyPair PK_sig SK_sig) : PK_sig mM
          (signSK_sig → M → S keygenSigKeyPair PK_sig SK_sig.skSigKeyPair.sk.{u_1, u_2} {PK_sig : Type u_1} {SK_sig : Type u_2} (self : SigKeyPair PK_sig SK_sig) : SK_sig mM) =Eq.{u_1} {α : Sort u_1} : α → α → PropThe equality relation. It has one introduction rule, `Eq.refl`.
We use `a = b` as notation for `Eq a b`.
A fundamental property of equality is that it is an equivalence relation.
```
variable (α : Type) (a b c d : α)
variable (hab : a = b) (hcb : c = b) (hcd : c = d)

example : a = d :=
  Eq.trans (Eq.trans hab (Eq.symm hcb)) hcd
```
Equality is much more than an equivalence relation, however. It has the important property that every assertion
respects the equivalence, in the sense that we can substitute equal expressions without changing the truth value.
That is, given `h1 : a = b` and `h2 : p a`, we can construct a proof for `p b` using substitution: `Eq.subst h1 h2`.
Example:
```
example (α : Type) (a b : α) (p : α → Prop)
        (h1 : a = b) (h2 : p a) : p b :=
  Eq.subst h1 h2

example (α : Type) (a b : α) (p : α → Prop)
    (h1 : a = b) (h2 : p a) : p b :=
  h1 ▸ h2
```
The triangle in the second presentation is a macro built on top of `Eq.subst` and `Eq.symm`, and you can enter it by typing `\t`.
For more information: [Equality](https://lean-lang.org/theorem_proving_in_lean4/quantifiers_and_equality.html#equality)


Conventions for notations in identifiers:

 * The recommended spelling of `=` in identifiers is `eq`.
        trueBool.true : BoolThe Boolean value `true`, not to be confused with the proposition `True`. ) :
  SigSig.{u_1, u_2, u_3, u_4} (PK_sig : Type u_1) (SK_sig : Type u_2) (M : Type u_3) (S : Type u_4) :
  Type (max (max (max u_1 u_2) u_3) u_4)§2.5, p. 472 assumption 2 and Figure 1, p. 471: Abstract digital signature
scheme. The paper uses "the signature Sig (XEdDSA), is EUF-CMA" (§2.5, p. 472).
In Figure 1, Alice verifies "sign(SPKᵦᵖᵏ, IKᵦˢᵏ), sign(PQSPKᵦᵖᵏ, IKᵦˢᵏ)".
Correctness requires that honestly generated signatures verify under the matching
public key. Concrete instantiation: XEdDSA over Curve25519.  PK_sigType u_1 SK_sigType u_2 MType u_3 SType u_4