Skip to content

Aggregated Ed25519 Signatures

Omer Shlomovits edited this page Oct 3, 2019 Β· 12 revisions

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] = b255b254...b2b1b0

the private key x will be x' with b255 = 0, b254 = 1 and b2=b1=b0=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 H0, H1, H2 : {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 ← H1(Aj, {A1, ..., An})β€…β‹…β€…Aj

Signing: Signing is an interactive three round protocol:

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

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

For z a random number with 256 bits 1. and point Ri = ri modq B.

Let ti ← H2(Ri). Send ti to all other signers corresponding to A1, ..., An and wait to receive tj = H2(Ri) from all other signers j ≠ i.

Round 2: Send Ri to all other signers corresponding to Ai, ..., An and wait to receive Rj from all other signers j ≠ i. Check that tj = H2(Rj) for all j = 1, ..., n.

Round 3: each party:

  1. Compute apk - Key Aggregation with public keys Ai, ..An.

  2. Compute ai = H1(Ai, {A1, ..., An}).

  3. Compute RΜ‚ ← Rj and k ← H0(RΜ‚, apk, M).

  4. Compute si ← riβ€…+β€…kβ€…β‹…β€…xiβ€…β‹…β€…aimod q.

  5. Send si to all other signers and wait to receive sj from other signers j ≠ i.

  6. Compute s ← sj and output (RΜ‚, s) as the final signature

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

1 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.

Clone this wiki locally