Introducing Expander: The Fastest GKR Proof System to Date

TL;DR: We are excited to announce the benchmarking and open source of our zero-knowledge proof (ZKP) system, Expander, developed by Polyhedra Network. Expander can prove 4500 Keccak-f permutations per second on an Apple M3 Max Machine! This makes Expander the most efficient open-source-proof system in the industry to date. Having demonstrated its efficiency on our zkBridge, Expander will also revolutionize zkVM and zkML.

Keccak-256 is a cryptographic hash function standardized by NIST in the secure hash algorithm 3 (SHA-3) and is the hash function used by the Ethereum blockchain. It appears everywhere in the ZK technology on the Ethereum chain, including proving the data inclusion on Ethereum in zkBridge, proving the Keccak hash function in the ECDSA signature in zkRollup, and proving the KECCAK256 instructions in zkEVM. However, it is perhaps the least ZK-friendly hash function. It takes tens of millions of gates to implement Keccak as a circuit, and the time to generate the ZK proof grows proportionally with the size of the circuit. To put things in context, the standardized SHA-256 hash function on the same input length takes around 20k gates to implement, and the ZK-friendly hash functions, such as MiMC, Poseidon, and Rescue, take only hundreds of gates, but these functions aren’t easily accessible on Ethereum. Therefore, it is a challenge to efficiently prove Keccak-256 hash functions in order to build ZK applications with native support of Ethereum.

Our proof system: To tackle this problem, we developed our ZKP system with a focus on optimizing prover efficiency. Our proof system combines the doubly efficient interactive proofs, known as the GKR protocol [1], with the recent polynomial commitment scheme based on error-correcting codes in Orion [2] and Brakedown [3]. With the algorithms proposed in Libra [4], the GKR protocol yields a strictly linear prover time in the size of the arithmetic circuit. To obtain an argument scheme, the GKR protocol is combined with a polynomial commitment scheme on multilinear polynomials. We deploy the constructions in Orion and Brakedown based on the generalized Spielman code with expander graphs. The prover computation only consists of a linear number of hashes and field operations in the size of the polynomial. No FFT is involved in our proof system, thus the scheme can work on any finite field, unlike SNARKs based on Reed-Solomon code and univariate polynomials, such as STARK and Plonk.

Choice of the field: We implement our proof system over the Mersenne prime p = 231–1. The protocol is executed over the 3-th extension field F_p3. Arithmetic operations over this field can be computed extremely efficiently.

Compiler: As the circuit representation of the GKR protocol is different from R1CS, Plonkish arithmetization, and Stark, we had to develop our own compiler. Expander compiles the computation to a layered arithmetic circuit with customized gates, such as inner product gates, that are supported by our GKR protocol. Using our compiler, one Keccak-f permutation is compiled into a circuit with 400 thousand gates, which is actually larger than the size of Keccak in R1CS and AIR. Additional optimizations, such as lookup tables, are in progress to further reduce the circuit size.

Benchmark: With these optimizations, we are psyched to report the benchmarking of our proof system on Keccak. Expander can generate the proof of 4500 Keccak-f permutations per second on an Apple M3 Max machine. We also benchmarked the same algorithm on an x86 machine on the AMD 7950X3D CPU and Expander can prove 4500 Keccak functions per second in this setting. We also want to highlight the low memory cost of our proof system. It only takes 16MB per Keccak, and the peak memory usage for 4000 Keccak hashes is only 63GB.

Implication: The performance of Expander opens the possibility for the creation of many ZK applications that are compatible with Ethereum. For example, in our zkBridge solution, we enable trustless interoperability between Ethereum and other blockchains, which needs to prove the Casper FFG consensus involving a lot of Keccak hashes. With the Ethereum block headers, in theory, one can use any Ethereum data on other Layer-1 and Layer-2 networks by providing a ZKP proving that there is a valid path of the Merkle Patricia Trie (MPT) to the smart contract. This is known as the data inclusion proof in our zkBridge. However, this is not currently possible in practice for large data precisely because of the overhead of proving Keccak. As Keccak is the hash function used in Ethereum MPT, to prove the inclusion of 1MB data we would need to prove more than 32768 Keccak-f permutations. Our benchmarking hopes to solve this problem in the near future. With Expander, we can generate the proof of inclusion of 1MB of data in a minute with only one machine (prover), which can be further improved using multiple machines.

[1] Goldwasser S, Kalai YT, Rothblum GN. Delegating computation: interactive proofs for muggles. Journal of the ACM (JACM). 2015 Sep 11;62(4):1–64.

[2] Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time. InAnnual International Cryptology Conference 2022 Aug 15 (pp. 299–328).

[3] Golovnev A, Lee J, Setty S, Thaler J, Wahby RS. Brakedown: Linear-time and field-agnostic SNARKs for R1CS. InAnnual International Cryptology Conference 2023 Aug 9 (pp. 193–226).

[4] Xie, T., Zhang, J., Zhang, Y., Papamanthou, C. and Song, D., 2019. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39 (pp. 733–764).