hash-chain-sonobe
Repo showcasing usage of Sonobe with Arkworks and Circom circuits.
The main idea is to prove $z_n = H(H(…~H(H(H(z_0)))))$, where $n$ is the number of Keccak256 hashes ($H$) that we compute. Proving this in a ‘normal’ R1CS circuit for a large $n$ would be too costly, but with folding we can manage to prove it in a reasonable time span.
For more info about Sonobe, check out Sonobe’s docs.
Usage
poseidon_chain.rs (arkworks circuit)
Proves a chain of Poseidon hashes, using the arkworks/poseidon circuit, with Nova+CycleFold.
cargo test --release poseidon_chain -- --nocapture
sha_chain_offchain.rs (arkworks circuit)
Proves a chain of SHA256 hashes, using the arkworks/sha256 circuit, with Nova+CycleFold.
cargo test --release sha_chain_offchain -- --nocapture
keccak_chain.rs (circom circuit)
Proves a chain of keccak256 hashes, using the vocdoni/keccak256-circom circuit, with Nova+CycleFold.
Assuming rust and circom have been installed:
- ./compile-circuit.sh
- cargo test --release keccak_chain -- --nocapture
Note: the Circom variant currently has a bit of extra overhead since at each folding step it uses Circom witness generation to obtain the witness and then it imports it into the arkworks constraint system.
Repo structure
- the Circom circuit (that defines the keccak-chain) to be folded is defined at ./circuit/keccak-chain.circom
- the logic to fold the circuit using Sonobe is defined at src/{poseidon_chain, shachain{offchain, onchain}, keccak_chain}.rs
Other
Additionally there is the src/naive_approach_{poseidon,sha}_chain.rs file, which mimics the amount of hashes computed by the src/{poseidon,sha}_chain.rs file, but instead of folding it does it by building a big circuit that does all the hashes at once, as we would do before folding existed.
To run it:
- cargo test --release naive_approach_sha_chain -- --nocapture
- cargo test --release naive_approach_poseidon_chain -- --nocapture