---
type: slide

---

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

---