- Hardware Acceleration
- Light Client
- Arithmetic Fields
- Efficient Signatures
- Proof Aggregation
- Vulnerability
- Licensing
- Verifiable Delay Functions (VDF)
- Proof generation is time-consuming, high-latency, and not efficient enough on traditional CPUs
- As L2 rollups and other applications of ZKP grow, we need to consider hardware as a potential breakthrough of performance improvement
- zk-mining: Plug-n-play FPGA accelerator cards (revenue through hardware sale)
- zk-Rollup: public, private and on-premise cloud (revenue through hourly premiere)
- Software auxiliary: SDK for dApps and API (license to program FPGA in developer-friendly way
- Permissioned networks, e.g. StarkNet
- Permissionless networks where provers compete on cost, e.g. Mina's Snarketplace
- Permissionless networks where provers compete on latency, e.g. Polygon Hermes & Zero
- Performance: latency, throughput, and power consumption
- Total cost of ownership (capital expenditures and maintenance costs)
- NRE cost (non recurring engineering: onboarding difficulties)
- Long-term comparative advantage: competitor performance may double in a year with the same MSPR (e.g. Intel, Nvidia GPU)
- Current popular structure is to combine CPU and FPGA/GPU to perform proof generation. CPU tackles single-threaded pieces at higher frequency and deal with non-determinism
- MSM and FFT can be parallelized, but arithmetization and commitments may be single threaded (different from the “embarrassingly parallel” PoW mining structure)
- Most FPGA design tools are proprietary: FPGAs have higher barrier to enter than GPU accelerations
- Full node is resource-draining: downloading and verifying the whole chain of blocks takes time and resources
- Not retail friendly to be on mobile and perform quick actions like sending transactions and verifying balances
- Trust-minimized interaction with full nodes and do not interact directly with the blockchain
- Much lighter on resources and storage but require higher network bandwidth
- Linear time based on chain length: verify from the root to the target height (may be from a trusted height, therefore constant length)
- Process overview:
- retrieve a chain of headers instead of full block
- verify the signatures of the intermediary signed headers and resolve disputes through checking with full nodes iteratively
- Superlight client: requires downloading only a logarithmic number of block headers while storing only a single block header between executions
| Name | Mechanism | Prover Complexity | Verifier Complexity | Trusted Setup | Reference |
|---|---|---|---|---|---|
| Recursive SNARKs | Cycle of elliptic curves | High | Low | Yes | https://minaprotocol.com/wp-content/uploads/technicalWhitepaper.pdf |
| KVC (Key-Value Commitment) | Constant size key-value map | Med-high | Medium | No | https://eprint.iacr.org/2020/1161.pdf |
| AMT (authenticated multipoint evaluation tree) | authenticate a polynomial multipoint evaluation at the first n roots of unity | Medium | Medium | No | https://people.csail.mit.edu/devadas/pubs/scalable_thresh.pdf |
| KZG Polynomial Commitment | Elliptic curve pairings with BLS12-381 | High | Low | Yes | https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf |
| Verkle Tree | (with anonymous revocation) | High | Low | No | https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf |
| Vector Commitment | RSA and computational Diffie-Hellman over bilinear groups | High | Low | Yes | https://eprint.iacr.org/2011/495.pdf |
| One-to-many prover VSS | Prover batching with sumcheck and Fiat-Shamir | Medium | Low | No | https://www.usenix.org/system/files/sec22summer_zhang-jiaheng.pdf |
- Proof systems encode computation as a set of polynomial equations defined over a field. Operating on a different field will lead to gigantic circuits.
- For pairing based SNARKs, there is a limited selection of pairing-friendly curves such as BN254 and BLS12-381.
- FFTs require factors of two for the curves in order to make the polynomial computations practical.
- Proof recursions require encoding arithmetic statements of a field into equations over a different field.
- Bridge operators and roll-ups need interoperability with non-pairing friendly and not highly 2-adic curves, such as Bitcoin and Ethereum’s ECDSA over secp256k1. (BN254 precompiled contract)
- Choosing the field is a tradeoff of speed and security.
- Brute force: decompose elements into limbs and operate on the limbs; Reduce and recompose the elements only when necessary
- Very expensive: may represent up to 1000X the original constraints in the circuit
- xJsnark framework
- gnark implementation
- 2-chains and cycles: use matching base fields to implement one curve inside of the other (assume pairing based schemes)
- Non-pairing based scheme can use non-pairing friendly or hybrid cycles at a cost, such as using PCS (polynomial commitment scheme) or pasta curves with linear time.
- Pasta Curves
- 2-chains of elliptic curves
- Lower the requirements on the field: Polynomial Commitment Scheme (PCS) may not involve elliptic curves at all to be instantiated on arbitrary fields
- A survey of elliptic curves for proof systems
- ECFFT: Fast Polynomial Algorithms over all Finite Fields
- Signatures are widely used in projects and can contribute to slow computation speed and poor user experience
- Different types of signatures depend on different field or curve arithmetic and need different speed-up methods
- Use “ZK native” signatures if possible (i.e. Picnic)
- Use “native” curves if possible (i.e. JubJub)
- In non-native curve arithmetic, for example ED25519, combine the limb products with the same weight mod 255 (in bits)
- minimize the number of splits by adding intermediate products with the same weight first. For example, when we have 2 intermediate projects of weight 2^51, we can split the sum into 52 bits
- If we have an intermediate product with weight of 2^255 or more, we can change its weight to 1 and multiply by 19, since 2^255 = 19 mod p_ed25519
- Use CRT related method like Aztec’s approach to have the prover give a purported product and check the identity mod p_native to ignore large limb products
- Use a PLONK or STARK can cut down the cost significantly
- Check windowing in the scalar multiplication code
- Leverage the constant generator in one of the multiplications in EdDSA
- GLV Endomorphism can split a curve multiplication into two smaller ones in curves like secp256k1
- Proving n statements individually leads to n proofs. Therefore, in the absence of recursion/aggregation, the verification cost grows linearly with the number of statements proven. This is not ideal for a high-throughput blockchain
- Custom PLONK gates, the bilinearity elliptic curve pairings as used in KZG
- Halo uses recursion to include proof number i-1 in proof i for all i and:
- amortizes the verification cost of the final proof for all n proofs
- necessitates sequentialism: proof i cannot be generated until proof i-1 already exists
- Plonky2 uses custom PLONK gates for the Poseidon hash function to succinctly verify FRI proofs
- recursive proofs on FRI proofs to prove the validity of multiple proofs in one
- the final recursive proof proves the validity of all tx proofs
- SnarkPack utilizes the KZG10 polynomial commitment schemes together with the Bulletproof trick to aggregate Groth16 proofs into a single proof
- can be verified in base-2 logarithmic time (in the number of proofs)
- Proofs for Inner Pairing Products and Applications
- SnarkPack: Practical SNARK Aggregation
- Recursive Proof Composition without a Trusted Setup
- Fractal: Post-Quantum and Transparent Recursive Proofs from Holography
- Fast Recursive Arguments with PLONK and FRI
- Trail of Bits is publicly disclosing critical vulnerabilities that break the soundness of multiple implementations of zero-knowledge proof systems, including PlonK and Bulletproofs
- These vulnerabilities are caused by insecure implementations of the Fiat-Shamir transformation that allow malicious users to forge proofs for random statements
- The vulnerabilities in one of these proof systems, Bulletproofs, stem from a mistake in the original academic paper, in which the authors recommend an insecure Fiat-Shamir generation
- The following repositories were affected:
- The Fiat-Shamir hash computation must include all public values from the zero-knowledge proof statement and all public values computed in the proof (i.e., all random “commitment” values)
- Serving up zero-knowledge proofs
- The Frozen Heart vulnerability in PlonK
- The Frozen Heart vulnerability in Bulletproofs
- The Frozen Heart vulnerability in Girault’s proof of knowledge
- Coordinated disclosure of vulnerabilities affecting Girault, Bulletproofs, and PlonK
- Honest verifier zero-knowledge proofs (HVZKP) assume an honest verifier. This means that in the presence of malicious verifiers, non-interactive protocols should always be used
- These also exchange fewer messages between prover and verifier. A malicious verifier can employ different attacks depending on the proof system
- Using HVZKP in the wrong context
- UC non-interactive, proactive, threshold ECDSA with identifiable aborts (2020)
- Lack of range constraints for the tree_index variable
- Insufficient range checks while emulating non-native field operations
| License | Permissions | Conditions | Projects |
|---|---|---|---|
| MIT | Commercial use, distribution, modification, private use | License and copyright notice | Scroll, Libsnark |
| GNU GPLv3 | Commercial use, distribution, modification, patent use, private use | Disclose source, license and copyright notice, state changes | Aleo, Tornado Cash. Aztec |
| Mozilla Public License | Commercial use, distribution, modification, patent use, private use | Disclose source, license and copyright notice | / |
| Apache License | Commercial use, distribution, modification, patent use, private use | License and copyright notice, state changes | O(1) Labs, StarkEx, Halo2, zkSync |
| BSD License | Commercial use, distribution, modification, patent use, private use | Disclose source, license and copyright notice | / |
| BSL | Non-production use, distribution, modification, private use | Disclose source, license and copyright notice | Uniswap v3, Aave |
| BOSL (Bootstrap Open Source License) | Commercial use, distribution, modification, private use | Open-source the improvements, improvements available under BOSL after 12 months, disclose source, license and copyright notice | Zcash (halo2’s initial launch) |
| Polaris Prover License | Non-commercial use | No transfer of rights, state changes | StarkWare Prover |
- randomness is hard to generate on chain due to non-determinism, but we still want to be able to verify the randomness
- fairness of leader election is hard to ensure as the attacker may manipulate the randomness in election
- Anyone has to compute sequential steps to distinguish the output. No one can have a speed advantage.
- The result has to be efficiently verifiable in a short time (typically in log(t))
- injective rational maps (First attempt in original VDF paper): “weak VDF” requires large parallel processing
- Finite group of unknown order (Pietrazak and Wesolowski): use a trapdoor or Rivest-Shamir-Wagner time-lock puzzle
- Chia blockchain: use VDF for consensus algorithms
- Protocol Labs + Ethereum Foundation: co-funding grants for research of viability of building optimized ASICs for running a VDF
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent