# New signature aggregation protocol ---- Dmitry Khovratovich (EF-Cryptography) and Lev Soukhanov (PSE) --- Context: ---- <!-- .slide: data-background=#1A237E --> * 1M validators * Currently each validator sign only 1 block per epoch;  * 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 ----  --- 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 ----  * 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$. ---