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