- Hardware Acceleration
- Light Client
- Arithmetic Fields
- Efficient Signatures
- Proof Aggregation
- Vulnerabilities
- Licensing
- Verifiable Delay Functions (VDF)
- Formal Verification
- 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
- Signature verification is a problem that arises in many ZK related projects, from Zcash to zk-rollups
- Different types of signatures depend on different field or curve arithmetic and need different speed-up methods
- Here we will discuss some different options for signature schemes, and strategies for efficient implementations
- Given a ZKP system, a simple signature scheme can be constructed as follows. The signer generates a random secret key sk, and hashes it to get the associated public key pk. They then prove, in zero knowledge, that they know some sk such that hash(sk) = pk. Picnic is a variant of this idea, using a block cipher rather than a hash function
- Since the statement being proved involves just a single evaluation of a hash or block cipher, these schemes can be highly efficient, particularly if using arithmetic-friendly primitives such as LowMC or Poseidon
- The caveat here is that the proof must be generated by the user who owns the secret key. If the signature is part of a larger circuit, such as Zcash’s spend circuit, this may be undesirable, as a user cannot outsource proving to another entity without revealing their secret key to that entity
- If we wish to support delegated proving, it may be best to use a conventional signature scheme such as ECDSA, and include its verification steps in our circuit. This way the user can generate just a signature, and a separate prover can prove that they witnessed a valid signature
- To make this efficient, we can choose an elliptic curve such that the base field of the curve matches the “native” field of our argument system. An example of this is the Baby Jubjub curve, whose base field matches the scalar field of alt_bn128. If we use an argument system such as Groth16 with alt_bn128 as our curve, Baby Jubjub arithmetic can be done “natively”
- However, using a curve like Baby Jubjub isn’t always an option. Sometimes we need compatibility with existing tools which support conventional curves. Polygon Zero, for example, must support Ethereum’s existing signature scheme, which is ECDSA over secp256k1. In these cases, we must simulate arithmetic in another field using bignum techniques
- For example, if we use standard multiplication algorithms for ED25519 field multiplication and range check each of the 5x5 limb products, we can reduce the cost by:
- Since 2^255 = 19 mod p_ed25519, you could combine limb products with the same weight mod 255 (in bits). The combined products will have a few more bits but it should be cheaper overall
- If we split each intermediate product into bits and use binary adders, we can minimize the number of splits by adding intermediate products with the same weight "natively" first. For example, if two intermediate products have a weight of 2^51 (the base), we can split the sum into 52 bits, which is just over half the cost of doing two 51-bit splits. When we have an intermediate product with a weight of 2^255 or more, we can change its weight to 1 and multiply it by 19, since 2^255 = 19 mod p_ed25519. That could help to further reduce the number of splits
- Alternatively, there's the Aztec approach of having the prover give a purported product, then checking the identity mod p_native (almost free) and then mod, say, 2^306 (can ignore limb products with weights of 306+)
- We're going to publish a couple other methods soon, which should be cheaper than the ones above
- These methods can be generalized to arbitrary low-degree formulas rather than simple multiplications. Checking a whole elliptic curve formula directly can be much more efficient
- Finally, we would expect the cost to come down significantly if you used a PLONK or STARK implementation that supported lookup-based range checks, instead of range checking via binary decomposition
- We can use incomplete formulae if we’re careful
- In the scalar multiplication code, we would suggest looking into windowing
- If we’re checking an ECDSA or EdDSA signature, we can leverage the fact that one of the multiplications has a fixed base, enabling various preprocessing tricks
- Curve-specific: secp256k1 supports the GLV endomorphism, for example, which allows us to split a curve multiplication into two smaller ones, opening the door to multi-scalar multiplication methods such as Yao’s
- 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
-
Zero-knowledge proof systems require the following properties to be defined as a zero-knowledge proof:
- Completeness: If a statement is true, an honest verifier will be convinced of this by an honest prover
- Soundness: If a statement is false, then there is a negligible probably that a cheating prover can prove the validity of the statement to an honest verifier
- Zero-knowledge property: If a statement is true, then the verifier learns nothing about the statement other than the fact that the statement is true
-
As such, if one of the above properties are broken, we no longer have a valid zero-knowledge proof system
-
This section organizes known vulnerabilities in implementations of zero-knowledge proof systems by the above properties and an additional section mainly pertaining to more general cryptographic vulnerabilities
- Correctness of G_k, generated in the ownership proof, is not enforced in the balance proof in Lelantus
- 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
- Addendum: Challenges should also be generated in such a way they are independently random.
- 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
- In certain ZK-SNARK protocols, a trusted setup ceremony is devised in order to produce parameters for use in the proof generation of a particular statement
- However, there are extra parameters, deemed as toxic waste, that meant to be destroyed after the ceremony has been performed. If the toxic waste is not properly disposed of, a cheating prover can generate fake proofs and mislead and honest verifier
- 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)
| 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
- https://vdfresearch.org/
- https://blog.trailofbits.com/2018/10/12/introduction-to-verifiable-delay-functions-vdfs/