Aggregated Ed25519 Signatures

Simple Ed25519 Signature

We first start by presenting Ed25519 signature algorithm from RFC8032 :

The public parameters are (𝔾, q, B) where 𝔾 is a group defined by elliptic curve, q is the order of the group and B is the generator of the group.

To generate a key pair Alice chooses a random secret sk from the field and hashes it using SHA-512 to get an extended-private-key:

(1) h=SHA-512(sk) = h[0],h[1],...,h[63] = x'||prefix

where:

(2) prefix = h[32],h[33],...h[63]

(3) x' = h[0],h[1],...h[31] = b₂₅₅b₂₅₄...b₂b₁b₀

the private key x will be x' with b₂₅₅ = 0, b₂₅₄ = 1 and b₂=b₁=b₀=0. The corresponding Public key A will be A = xB where B is the generator point.

To sign on a message M Alice uses the prefix to compute an element r:

(4) r = SHA-512(h[32],h[33],...,h[63] || M)

with a corresponding point R = r modq B.

using k = SHA-512(R || A || M) Alice computes:

(5) s = r + kx

and outputs sig = (s, R)

Finally to validate a signature sig over a message M using a public key A we check equality:

(6) 8sB ?=? 8R + 8kA

Aggregated Ed25519 Signature

We Based this construction on the work in Compact Multi-Signatures for Smaller Blockchains section 5.1. The original construction was for Schnorr signatures and ordinary curves. Since Ed25519 is a type of Schnorr signature based on curve25519 we make the appropriate adjustments to the protocol:

Aggregated Ed25519 signature scheme, is a set of protocols between n parties such that they can jointly sign a message. The specific protocol we describe uses hash functions H₀, H₁, H₂ : {0, 1}^* → ℤ_q. These hash functions can be constructed from a single SHA-512 using proper domain separation. The parameters are the same as in the case of single signer signature: (𝔾, q, G).

Key Generation: Each party chooses sk and computes private key x and public key A in the same manner as the single signer case (eq. 1,2,3).

Key Aggregation: This will be the combined public key eventually:
apk ← H₁(A_j, {A₁, ..., A_n}) ⋅ A_j

Signing: Signing is an interactive three round protocol:

Round 1: This is a commitment round. Party i computes r_i using:

(7) r = SHA-512(h[32],h[33],...,h[63] || M || z)

For z a random number with 256 bits ¹. and point R_i = r_i modq B.

Let t_i ← H₂(R_i). Send t_i to all other signers corresponding to A₁, ..., A_n and wait to receive t_j = H₂(R_i) from all other signers j ≠ i.

Round 2: Send R_i to all other signers corresponding to A_i, ..., A_n and wait to receive R_j from all other signers j ≠ i. Check that t_j = H₂(R_j) for all j = 1, ..., n.

Round 3: each party:

1. Compute apk - Key Aggregation with public keys A_i, ..A_n.

2. Compute a_i = H₁(A_i, {A₁, ..., A_n}).

3. Compute R̂ ← R_j and k ← H₀(R̂, apk, M).

4. Compute s_i ← r_i + k ⋅ x_i ⋅ a_imod q.

5. Send s_i to all other signers and wait to receive s_j from other signers j ≠ i.

6. Compute s ← s_j and output (R̂, s) as the final signature

Validation is the same as in simple Ed25519 (eq. 6).

¹ Taking equation 4 per the RFC will not work in this case. We would like to thank @evq for pointing this issue and suggested a fix.