<style>
.ui-content #doc.markdown-body, .ui-content .ui-infobar {
max-width: 1280px;
}
</style>

# Benchmarks For Digital ID Wallet Project

## High Level Requirements

The zero-knowledge proof (ZKP) scheme that will be used in Digital ID Wallet (DIW) should meet the following requirements:

| Requirement | Rationale |
| --------------------------------------------------- | ---------------------------------------------------------- |
| No trusted setup / long structured reference string | Fewer security assumptions and less mobile bandwidth usage |
| Overall low bandwidth usage | Mobile device limitations |
| Recursive proving | Offline verifiable presentation generation capability |
| Fast proving | Mobile device limitations |
| Post-quantum soundness | Future-proofing |

## Target Circuit

The credential issuer should sign a SHA256 hash of a JSON web token (JWT) containing the credential attributes. Therefore, SHA256 is a good target circuit and an assumed performance bottleneck of the per-issuance proof.

## Survey of Potential ZKP Solutions

The ZKP schemes in the table below are plausibly post-quantum sound and do not require trusted setup.

| Solutions | ZKP Scheme | Prover Complexity | Frontend | Existing SHA256 Implementations | Existing Benchmarks |
| ------------------------------------------------------------- | ---------------------------------------------------------------------------------------------- | ----------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| [Plonky2](https://github.com/0xPolygonZero/plonky2/tree/main) | [TurboPLONK + FRI](https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/plonky2.pdf) | $O(n \log n)$ | Rust API/[Noirky2](https://blog.eryx.co/2024/10/29/Noirky2-how-we-made-a-Plonky2-proving-backend-for-Noir.html) | [No-lookup](https://github.com/polymerdao/plonky2-sha256/blob/main/src/circuit.rs); [No-lookup](https://github.com/proxima-one/plonky2/tree/merkle-stark/merkle-stark/src/sha256_stark); [No-lookup](https://github.com/JumpCrypto/plonky2-crypto/blob/main/src/hash/sha256.rs); [Noir cross-compile (no-lookup)](https://github.com/eryxcoop/acvm-backend-plonky2/blob/main/plonky2-backend/src/circuit_translation/sha256_translator.rs) | [PSE CSP (mobile-ready)](https://hackmd.io/@clientsideproving/B1xLCuJL5yg), [Celer (2023)](https://blog.celer.network/2023/08/04/the-pantheon-of-zero-knowledge-proof-development-frameworks/) |
| [Plonky3](https://github.com/Plonky3/Plonky3/tree/main) | TurboPLONK + FRI | $O(n \log n)$ | Rust API/[Lurk](https://github.com/lurk-lab/lurk)/[powdr(Rust)](https://docs.powdr.org/backends/plonky3.html)/[SP1(Rust)](https://github.com/succinctlabs/sp1) | [In powdr (no-lookup)](https://github.com/babybear-labs/benchmark/tree/main/powdr); [SP1 (uses precompiles?)](https://github.com/babybear-labs/benchmark/tree/main/sp1/algos/sha256) | [In powdr](https://github.com/babybear-labs/benchmark/tree/main/reports/powdr) |
| [STWO](https://github.com/starkware-libs/stwo) | [CSTARK](https://eprint.iacr.org/2024/278) | $O(n \log n)$ | Rust API/[Cairo](https://github.com/starkware-libs/stwo-cairo?tab=readme-ov-file) | [Cairo port of zkEmail, no-lookup](https://github.com/iosis-tech/zkemail-cairo/blob/main/sha256.cairo) | Not found, but claimed to be ["1.1M CairoCPU cycles, provable with STWO in 6.5s"](https://x.com/bartolomeo_diaz/status/1888240222724354106) |
| [Polyhedra Expander](https://github.com/PolyhedraZK/Expander) | [Libra](https://eprint.iacr.org/2019/317) ([Orion](https://eprint.iacr.org/2022/1010.pdf) PCS) | $O(n)$ | Rust API/gnark | [Rust API](https://github.com/PolyhedraZK/proof-arena/blob/d29e6b369e4226f206b6c4a6e65808204fd8fc91/problems/sha256_hash/expander-sha256/src/main.rs); [gnark](https://github.com/MAYA-ZK/Gnark_on_Icicle_benchmarking/blob/main/sha256/sha256.go#L128) | [In Rust](https://proofarena.org/problems/3) |
| [Spartan + WHIR](https://github.com/worldfnd/ProveKit) | [Spartan](https://eprint.iacr.org/2019/550)+[WHIR](https://eprint.iacr.org/2024/1586) | $O(n)$ | [Noir](https://github.com/worldfnd/ProveKit) | [ProveKit Example](https://github.com/worldfnd/ProveKit/tree/main/noir-examples/sha256) | - |
| [Binius](https://github.com/IrreducibleOSS/binius/tree/main) | [Binius](https://eprint.iacr.org/2023/1784.pdf) | ~$O(n)$ | Rust API | [With lookups](https://github.com/IrreducibleOSS/binius/blob/main/examples/sha256_circuit_with_lookup.rs); [without lookups](https://github.com/IrreducibleOSS/binius/blob/main/examples/sha256_circuit.rs) | [Official benchmark](https://www.binius.xyz/benchmarks/) |
| Ligero | [Ligero](https://eprint.iacr.org/2022/1608) | $O(n \log n)$ | [C++ API???](https://github.com/scipr-lab/libiop?tab=readme-ov-file) | Not found, but [potentially usable one here](https://github.com/search?q=repo%3Ascipr-lab%2Flibsnark%20sha256&type=code) | ⚠️ The linked codebase is older than the recent version of the paper; There is a not-yet-opensourced impl from [Ligetron](https://platform.ligetron.com/marketplace); |

## Comparison Across Proof Systems

The benchmarks were measuring the performance of SHA256 circuits with 2048 B input (~33 SHA256 compressions[^2]), with the exception of Polyhedra Expander circuit (1024 B input). Measured on Apple M2 Air laptop.

| Circuit (GitHub link) | Proving Time | Verification Time | Proof Size | Preprocessing Size | Preprocessing RAM | Prover RAM |
| ------------------------------------------------------------------------------------------------------------------------- | ------------ | -------------------- | ---------- | -------------------------------------------------- | ----------------- | --------------------------- |
| [Binius (no-lookup)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/binius)[^2] | 1.8545 s | 244.48 ms | 475.6 KB | 321.8 KB | ~10.44 MB | ~26.94 MB |
| [Binius (lookup)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/binius)[^2] | 11.025 s | 572.73 ms | 1.8 MB | 716.86 KB | ~5.02 MB | ~66.14 MB |
| [Plonky2 (no-lookup)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/plonky2) | 20.138 s | 5.3135 ms | 175.6 KB | 2.28 GB (prover-only data) + 1.06 KB (common data) | ~2.74 GB | ~2.40 GB |
| [Plonky3 (SP1 w/precompile)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/plonky3-sp1) | 12.596 s | 184.11 ms | 1.72 MB | 156.34 MB (PK) + 90.76 KB (ELF) | ~1 GB | ~5 GB |
| [Plonky3 (powdr, no precompile)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/plonky3-powdr) | 20.741 s | 256.11 ms | 1.93 MB | 3.1 GB (proving key) + 321 MB (constants) | ~3.87 GB | ~0.32 GB |
| [STWO (Cairo)](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/stwo) | 21.1 s | N/A (verifier error) | 39.5 MB | 12.6 MB (trace) + 3.4 Mb (memory) | ~600 MB | ~10GB |
| [Ligero (Ligetron, *uses WebGPU*)](https://platform.ligetron.com/marketplace/project?id=78180426-2a09-4c36-ac68-52f1ab4ffbe6&version=1.0) | 12.06 s | 9.16 s | 10.29 MB | 33KB (prover data) | N/A | ~500 MB VRAM + ~30 MB RAM |
| [Polyhedra Expander (Orion + GF2), 1kB input](https://github.com/privacy-scaling-explorations/zkid-benchmarks/tree/main/polyhedra-expander) | 70 s | 26 s | 30.75 MB | 6 GB (circuit) | N/A | 15.55 GB |

[^1]: [Plonkish circuit example with lookups in STWO](https://github.com/starkware-libs/stwo/blob/dev/crates/prover/src/examples/plonk/mod.rs)

[^2]: Binius circuits only perform compressions but not full SHA256, so an actual full implementation would incur extra overhead