# 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;
![image](https://hackmd.io/_uploads/Bkw9Y0muA.png)
* 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](https://hackmd.io/_uploads/HyJxEUZ_R.png)
---
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](https://hackmd.io/_uploads/r11taAmOA.png)
* 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.

{"title":"New signature aggregation protocol","description":"Context:","contributors":"[{\"id\":\"edda4d62-a8ca-4067-980b-bc0c94fc47b5\",\"add\":4735,\"del\":882}]","slideOptions":"{\"center\":false,\"keyboard\":true,\"theme\":\"white\",\"maxScale\":2,\"height\":1000}"}