New signature aggregation protocol

Dmitry Khovratovich (EF-Cryptography) and Lev Soukhanov (PSE)

Context:

  • 1M validators
  • Currently each validator sign only 1 block per epoch;

image

  • We want them to sign everything

Requirements:

[PICTURE]

  • A block contains attestations.
  • Attestation \(A\) is an aggregated signature with bitmask \(B\)
  • Signers are rewarded/penalized based on \(B\) (can't be fully hidden).
  • Signatures are broadcast and aggregated within a few seconds

Protocol

image

Protocol

  1. Split all validators into groups of size \(M\) and each group into subgroups of size \(V\)
  2. Validators send individual signatures to aggregators of the subgroup.
  3. Aggregators sum signatures, sign the aggregation, and send it to attesters of the group.
  4. Attesters sum aggregations to signature \(\sigma\) and create a SNARK proof \(\pi\) that asserts that \(P\) is a sum of pubkeys.
  5. Block proposer selects two best attestations.
  6. To verify an attestation it suffices:
  • to check \(\pi\).
  • to check that \(\sigma\) is a valid signature on \(P\).

Assumptions

  • Group public keys (\(2^{15}\) members) are pre-assembled as a set of subgroup commitments

SNARK: formal statement

For public input \((P,B, \sigma, C)\) there exist aggregations \(\{\widetilde{\Sigma}_i\} = (\widetilde{P}_i,\widetilde{\sigma}_i,\widetilde{B}_i)\) with signatures \(\widehat{\sigma}_i\) of aggregators such that

  • \(\widehat{\sigma}_i\) is a signature of \(\{\widetilde{\Sigma}_i\}\).
  • \(C\) is a commitment to all public keys \(\{P\}_G\) of the group.
  • \(\widetilde{P}_i\) is a pubkey aggregated by the bitmask \(\widetilde{B}_i\) for \(\{P\}_G\).
  • All \(\widetilde{P}\) sum to \(P\)
  • All bitmasks \(\widetilde{B}\) union to \(B\)
  • All signatures \(\widetilde{\sigma}\) sum to \(\sigma\) (to guarantee that aggregators see the signatures).

SNARK: technique

GKR protocol:

  • Sumcheck-based SNARK
  • No trusted setup
  • No pairings

Costs:

  • Proof size \(O(depth\cdot \log(width))\)
  • Proof cost \(O(size)\)
  • Verifier cost \(O(depth\cdot \log(width))\) hash calls

SNARK details:

  1. Prover costs:
    • GKR prover for public key summation (\(2^{18}\) keys, i.e. 18 layers of key addition tree)
    • GKR prover for aggregator signature verification (\(2^9\) signatures)
    • Opening input commitments
  2. More
    • Public inputs: validator subgroup sets are available as commitments
    • Some tricks to minimize the opening costs

Concrete numbers

  1. Proof construction needs \(\approx 8M\) field operations. Currently within a second for \(8M<2^{18}\).
  2. Proof size is \(\approx 4\log^2(8M)=1200\) field elements, i.e. around 2 bytes per validator.
  3. Verifier cost \(\approx \log^2(8M)=300\) hashes, i.e. 10K hashes per 1M validators.

Reducing costs

  1. Put the GKR verifier into a succinct SNARK:

    • Need to prove 400 hashes within a second
    • Doable with arithmetic hashes and tailored SNARKs, like HyperPlonk (\(\approx 100\)-MSM per hash).
    • Doable without arithmetic hashes but much more complex (the original key-addition circuit must be cut).
    • Need another pairing curve for that (BW6).

  2. Make the aggregator signatures SNARK-friendly (at least not BLS)

Security requirements (informal):

  • All public keys from the bitmask signed the message
  • Aggregators have seen aggregated keys and signatures for the subgroup

Comparing to Horn

image

  • Horn has the same architecture but does not do SNARKs.
  • It is not asserted that aggregators and collectors have done the job.
  • Redundancy in aggregators and collectors increase the total attestation size.

PQ-SNARK: formal statement

Input:

  • \(G_1,G_2,\ldots,G_k\): public keys of slot validators;
  • \(s\) – slot index
  • \(i_1,i_2,\ldots,i_t\): indices of validators who signed.
  • \(M\) – block hash

Witness:

  • XMSS signatures \((\sigma_1,\ldots,\sigma_t)\);

Constraints:

  • For all \(j\leq t\;\) XMSS-Verifier\((G_i,\sigma_i,s,M)=\)true.

Data structures

Data structures:

Public key \(G = (\underbrace{P}_{\text{user-unique parameter}},\underbrace{U}_{\text{Merkle root}})\)

Signature \(\sigma = (\underbrace{R}_{\text{counter value}},\underbrace{(c_1,c_2,\ldots,c_v)}_{\text{Chain entries}},\underbrace{(h_1,h_2,\ldots,h_{l})}_{\text{Merkle path}})\)

Verifier code

XMSS-Verify\((\underbrace{G}_{(P,U)},\underbrace{\sigma}_{(R,(c_1,c_2,\ldots,c_v),(h_1,h_2,\ldots,h_{l}))},s,M)\):

  1. Hashing into chains: \((i_1,i_2,\ldots,i_v) \leftarrow H(P,\mathrm{tweakm}(s),R,M)\)
  2. Target sum check \(\sum_j i_j \overset{?}{=} T\)
  3. Leaf value \(h_0\leftarrow H(H^{W-1-i_1}_{P,\mathrm{tweak}}(c_1),\ldots,H^{W-1-i_v}_{P,\mathrm{tweak}}(c_v))\).
  4. \((h_1,h_2,\ldots,h_{l})\) is a Merkle proof towards root \(U\) from leaf \(h_0\) at position \(s\).
Select a repo