[Signature Merging for Large-Scale Consensus - Cryptography - Ethereum Research](https://ethresear.ch/t/signature-merging-for-large-scale-consensus/17386) - ETH has 800k validators and growing - BLS signatures - supports aggregation - Give it a bunch of signatures and it spits out one signature representing all - Simple, efficient - Uses an *aggregator* to aggregate - Need to keep track of who participates - Uses bitfield where each index is a validator - 1 = signs, 0 = didn't - Takes all the 800k validators, puts them into chunks, then they vote - 1/32 vote at once, per slot - SSF - get everyone to vote all at once - One idea: - Chaotic gossip system - Sigs sent out, aggregated, thrown out, etc. - Start from signatures and keep chaotically aggregating - Since we have a lot of validators but not a ton of networking nodes, it could work - Problem: aggregating the aggregate signatures is easy, but aggregating bitfields is weird - ex. if both bitfields are active on first bit what do you do? - Using boolean system can get confusing - Fundamental problem: **Bitfield marriage** ### Signature Merge - Scheme, abstract API allowing for merging signatures and extracting bitfield out of them *How we can instantiate this system* - Forget about BLS, aggregate using recursive SNARKs - 3 techniques based on proof-carrying data - Paradigm for sending rpoofs and data, proofs attest to validity of data - 3 Done with recursive snarks - Full STARK recursion - Recursive Halo2 (atomic accumulation) - Folding (split accumulation) 1. STARK recursion - Takes bitfield and STARK, another bitfield and STARK, verifies inside circuit, does some useful stuff, then spits out a bitfield and STARK - Output is the same as the input - With this system, the collector could get bitfields and proof to send to the verifier - The useful computation takes 2 bitfields, a signature, and index, and verifies signatures, unions bitfields - Lean system where we're basically just sending bitfields - Proof system logic: Verifier is big, has to computes hashes to FFTs. Slow. No good. - We want to shrink this box with more modern technique Rest of talk goes through techniques to make circuit verifier smaller - First stop: Halo paper by Zcash team - Introduces new technique for not having to do full verification inside circuit, but just the easy part. - Accumulate the rest to the next recursion step, and so on - Results in verification be much smaller but we still have something to verify at the end - Instead of verifying expensive thing, cheaply verify it and accumulate rest of verification to next step - You still need to verify at some point - Much smaller verifier, but you still have accumulator object as an output - Folding - new hyped form of shrinking verifier even more - Instead of dealing with expensive to produce/verify proofs, Nova works with instance and witness of R1CS system and folds that instead - No need to go into proof system works or verifying - Take 2 instances to a problem, fold them together, and check the folding was done correctly - *In theory*, much simpler - Verifier is minimal complexity befcause it doesn't do proof verification - Many issues with adoption in Ethereum setting Folding Open problems in PCP setting: 1. Original NOVA paper designed with IVC chain-like thing in mind - Good for fibonacci/verifying chains, but we have a more graph-style structure with no order - Adapting Nova to PCP results in complicated diagrams 2. Nova has an issue in the input size - If you have a big witness, big communication cost - You pay for distributed prover - Nova isn't great with polynomial stuff, deals with vectors of field elements 3. In folding, you need to verify folding was correct, which involves group operations and cycles - Buggy, PCP makes more complications - Help: - Figuring out open problems in various appraoches - Specifying how circuit would look like - Benchmarking