This is a simple prototype of distributed zero-knowledge cycle detection via recursive proof aggregation on SP1.
Distributed: no central entity knows the entire graph. Zero-knowledge: each node learns the nodes that exist on paths to it only (and whether there's a cycle).
Inspired by @nibnalin's post Recursive zkSNARKs: Exploring New Territory.
To build the program, run the following command:
cargo build --releaseTo run the program as the first node in the loop without generating a proof:
cargo run --release -- --executeTo run the program for each node in the loop, generating the execution proof for the next to verify:
cargo run --releaseIf you're running on the CPU and it is recent:
RUSTFLAGS='-C target-cpu=native -C target-feature=+avx512f' && RUST_LOG=info && time cargo run --releaseor
RUSTFLAGS='-C target-cpu=native -C target-feature=+avx512f' RUST_LOG=info time cargo run --releaseThis will execute the program and display the output, warming up your motherboard in the process. :-)