Thread by @ethotim

Been exploring some of the lesser-known ZK constructions and decided to share some brief facts, so here we go, a thread about Bulletproofs, Halo2, MPC-in-the-head, and more 🧵👇

🛡🔫 Bulletproofs:
- short NIZK that requires no trusted setup
- build with Pedersen commitments
- support proof aggregation
- prover time: O(N∗log(N)) ~30s
- verifier time: O(N) ~1.1s
- proof size: O(log(N)) ~1.3KB
- assumptions: discrete log

✅Bulletproofs - best fit for:
- range proofs (take only 600 bytes)
- inner product proofs
- intermediary checks in MPC protocols
- aggregated and distributed (with many private inputs) proofs

🚫Poor choice for:
- complex arbitrary statements that are verified on-chain

Bulletproofs - Used in:
- Confidential TX for Bitcoin: elementsproject.org/features/confi…
- Monero: medium.com/digitalassetre…
- Stellar Shielded Tx (Cloak): github.com/stellar/slings…

🛠 Bulletproofs - libraries:
- github.com/dalek-cryptogr… (Rust)
- github.com/adjoint-io/bul… (Haskell)
- github.com/bbuenz/BulletP… (Java)

📚 Resources to learn more:
- crypto.stanford.edu/bulletproofs/
-
- cathieyun.medium.com/building-on-bu…

⚜️ Sigma Protocols (+Fiat-Shamir):
- short proof that needs no trusted setup
- require a constant number (3) of public-key operations
- multiple Sigma proofs can be composed together in configurations like A and\or B, eq(A,B), all(n,A)
- assumption: discrete log, honest verifier

✅Sigma protocols - Best fit for:
- discrete log (dlog) proofs
- one-of-many dlogs
- discrete log equality (dleq)

🚫Poor choice for:
- complex arbitrary statements

Sigma Protocols - Used in:
- Signal (Algebraic MACs for group chats): signal.org/blog/signal-pr…
- dleq proofs in the adaptor signatures
- verifiable random functions
- ElGamal encryption in the Cryptography for #metoo: petsymposium.org/2019/files/pap…

🛠 Sigma Protocols - Libs:
- github.com/LLFourn/secp25… (Rust)
- pkg.go.dev/go.dedis.ch/ky… (Go)
- github.com/cryptobiu/libs… (C++)
- github.com/spring-epfl/zk… (Python)

📚 Learn more:
- medium.com/@loveshharchan…
- slideplayer.com/slide/4039383/
- community.zkproof.org/t/standardizin…

💫 Halo 2
- combines efficient accumulation scheme with PLONKish arithmetization and needs no trusted setup
- based on IPA commitment scheme
- flourishing developer ecosystem
- prover time: O(N*log N)
- verifier time: O(1)>Groth16
- proof size: O(log N)
- assumption: discrete log

👅Libraries (flavors of Halo2):
- github.com/zcash/halo2 - original (IPA)
- github.com/privacy-scalin… - replaces IPA with KZG
github.com/Orbis-Tertius/… - replaces IPA with FRI (WIP)

✅ Halo2 - Best fit for:
- arbitrary verifiable computation
- recursive proof composition*
- circuit-optimized hashing based on lookup-based Sinsemilla function

🚫 Poor choice for:
- costly to verify on Ethereum unless KZG-version is used
- recursive proof composition*

🤔 Halo2 - What’s with recursion?
- recursion isn’t yet supported by the original Halo2 (github.com/zcash/halo2/is…)
- currently, it’s only possible with the KZG-based version using github.com/scroll-tech/ha…
- Orbis Labs are working on their accumulation scheme using Tiny-RAM arch

Halo2 - Used in:
- Zcash shielded protocol (Orchard): electriccoin.co/blog/announcin…
- Scroll zkEVM: scroll.io/blog/zkEVM#zkE…)
- Orbis ZK-Rollup on Cardano: github.com/Orbis-Tertius
- Dark Fi L1: dark.fi

📚 Halo2 - Resources to learn more:
- General overview: electriccoin.co/blog/explainin…
- Docs: zcash.github.io/halo2/
- Talk:
- Math: vitalik.ca/general/2021/1…
- Ecosystem showcase:
- More: github.com/adria0/awesome…

🐭 Plonky2 - Overview:
- combines FRI with PLONK and needs no trusted setup
- optimized for modern processors with SIMD and 64 byte Goldilocks fields
- prover time: O(log N)
- verifier time: O(log N)
- proof size: O(N*log N)
- assumptions: collision-resistant hash function

👀 Plonky2 - More insights:
- allows to choose: fewer rows => fast prover OR fewer columns and constraints => fast verifier
~38x faster than Halo2, ~64x faster than Groth’16 (

https://twitter.com/sebastienladuca/status/1555789080289579008

)
- uses Poseidon sponge and GMIMC as hash functions for FRI

✅ Plonky2 - Best fit for:
- arbitrary verifiable computation
- recursive proof composition
- circuit optimization using custom gates

🚫Poor choice for:
- statements about elliptic curve operations (due to non-native arithmetic)

Plonky2 - Used in:
- Mir protocol (before acquisition by Polygon): mirprotocol.org
- Polygon Zero (ZK L2): polygon.technology/solutions/poly…

Plonky2 - Libraries
- github.com/mir-protocol/p… (Rust)

📚 Resources:
- Overview: blog.polygon.technology/introducing-pl…
- Paper: github.com/mir-protocol/p…

Continuation of this thread with facts about MPC-in-the-head proofs:

https://twitter.com/ethotim/status/1567602193775181824