The code of this first rollup is very simple. It uses one-time key to avoid nonces:
sk such that hash(sk) = pk.cm = hash(in_value, pk).root.out_value_1 + out_value_2 == in_valuecm_rootnf = hash(sk || NULLIFIER).root outputed by the transaction is the same as cm_root.The code is the following:
The transaction:
use risc0_zkvm::guest::env;
use sha2::{Digest, Sha256};
pub fn node(a: [u8; 32], b: [u8; 32]) -> [u8; 32] {
let mut hasher = Sha256::new();
hasher.update(a);
hasher.update(b);
hasher.finalize().into()
}
fn main() {
// TODO: Implement your guest code here
// read the input of the tx
let value: u32 = env::read();
let sk: [u8; 32] = env::read();
let path : Vec<[u8; 32]> = env::read();
let mut idx: usize = env::read();
//red the output of the tx
let out_value_1: u32 = env::read();
let out_value_2: u32 = env::read();
let out_pk_1: [u8; 32] = env::read();
let out_pk_2: [u8; 32] = env::read();
//Commit the nullifier
let mut hasher = Sha256::new();
hasher.update(&sk);
hasher.update(&b"NULLIFIER");
let nf: [u8; 32] = hasher.finalize().into();
env::commit_slice(&nf);
// DERIVE PK
let mut hasher = Sha256::new();
hasher.update(&sk);
let pk: [u8; 32] = hasher.finalize().into();
// DERIVE COMMIT
let mut hasher = Sha256::new();
hasher.update(&value.to_le_bytes());
hasher.update(&pk);
let mut commitment: [u8;32] = hasher.finalize().into();
//COMMIT MEMBERSHIP
for i in 0..path.len() {
if idx % 2 == 0 {
commitment = node(commitment, path[i]);
} else {
commitment = node(path[i],commitment);
}
idx /= 2;
}
// Commit the root of the ledger
env::commit_slice(&commitment);
//check balance
assert_eq!(value - out_value_1 - out_value_2, 0);
// COMMIT OUTPUTS
let mut hasher = Sha256::new();
hasher.update(&out_value_1.to_le_bytes());
hasher.update(&out_pk_1);
let commitment: [u8;32] = hasher.finalize().into();
env::commit_slice(&commitment);
let mut hasher = Sha256::new();
hasher.update(&out_value_2.to_le_bytes());
hasher.update(&out_pk_2);
let commitment: [u8;32] = hasher.finalize().into();
env::commit_slice(&commitment);
}
The executor
I reimplement a more realistic rollup without going deep in the code by simulating the number of cycles of commitment check using MMR and nullifier gestion through indexed Merkle tree of depth 64. More specifically, I assumed that a commitment proof can be checked against several MMR roots, that updating a Merkle root knowing the MMR peaks takes up to n - 1 + d + log2(n) where n is the number of commitments to insert and d the depth of the MMR.
For my simulation I assumed the depth of the commitment MMR to be 32 (meaning we already have 2^31 commitments in the ledger) and simulating the hashes:
pub fn simulated_commitment_root_calculation(start: [u8; 32], tree_depth: usize, batch_size: usize) -> [u8; 32] {
// Here we simulate the calculation of a new MMR root. In the worst case
// scenario, this root takes "batch_size" - 1 + "tree_depth" + log2(batch_size)
let mut hash = start;
for _ in 0..(batch_size - 1 + tree_depth + ((batch_size - 1).ilog2()+1) as usize) {
let mut hasher = Sha256::new();
hasher.update(&hash);
hasher.update(&hash);
hash = hasher.finalize().into()
}
hash
}
On a second time, I simulated the update of a Merkle tree of depth 64 to represent the insertion of a batch of new nullifiers in the indexed merkle tree which is just redoing two Merkle path after changing the leaves (the previous nullifier now pointing to this one and the new one pointing to the next one):
pub fn simulated_nullifier_root_calculation(start: [u8; 32], number_nullifier: usize) -> [u8; 32] {
// Here we simulate the calculation of a new indexed merkle tree of depth 64
// root, which takes 2 leaf hashes and 128 node merging hashes
// One leaf is composed of a nullifier and index of the next one so 2 elements
let mut hash = start;
for _ in 0..130*number_nullifier {
let mut hasher = Sha256::new();
hasher.update(&hash);
hasher.update(&hash);
hash = hasher.finalize().into()
}
hash
}
Finnaly, I also simulated the non-membership proof of a nullifier which is exactly verifying 2 Merkle paths and checking two equalities:
pub fn simulated_nullifier_non_membership_calculation(start: [u8; 32]) -> bool {
// Here we simulate the non-membership verification of a nullifier which takes
// 2 membership verifications each of 1 leaf hash and 64 node merging hashes
// and the two comparison proving the non-membership
let mut hash = start;
for _ in 0..65*2 {
let mut hasher = Sha256::new();
hasher.update(&hash);
hasher.update(&hash);
hash = hasher.finalize().into()
}
if A < B && B < C {
true
} else { false }
}
use risc0_zkvm::guest::env;
use sha2::{Digest, Sha256};
use transaction::TRANSACTION_ID;
const A: [u8; 32] = [0x1c, 0x46, 0xee, 0x88, 0x7c, 0xdf, 0x54, 0xaa,
0xda, 0xeb, 0x5f, 0x34, 0xd6, 0x61, 0x4e, 0x9a,
0xd5, 0xad, 0x20, 0x3a, 0x29, 0x96, 0x22, 0xd8,
0x95, 0xd3, 0x77, 0x09, 0xdf, 0x24, 0x59, 0xb4];
const B: [u8; 32] = [0x7b, 0xdb, 0x5c, 0x1a, 0x94, 0xa7, 0x6c, 0x84,
0x6d, 0x32, 0xfd, 0x16, 0x02, 0x3e, 0x16, 0xf6,
0x78, 0x66, 0x6f, 0xdf, 0xcd, 0xc2, 0xcb, 0xe4,
0xf5, 0x68, 0x17, 0xb5, 0x2a, 0x87, 0x2e, 0xdf];
const C: [u8; 32] = [0x8b, 0x29, 0x05, 0x0a, 0xf5, 0x50, 0x15, 0x67,
0x3d, 0x60, 0xe6, 0x82, 0x3c, 0x55, 0x84, 0xf0,
0xae, 0xe2, 0x0e, 0x07, 0xd0, 0xde, 0x96, 0x23,
0x6d, 0xad, 0x9b, 0x1e, 0x19, 0xc5, 0x36, 0x04];
fn main() {
// TODO: Implement your guest code here
// read the input
let nb_tx: usize = env::read();
let commitments_mmr : Vec<[u8;32]> = env::read();
let nullifier_root : [u8; 32] = env::read(); // proof input 2
for _ in 0..nb_tx {
let nf: [u8;32] = env::read(); // proof input 1
let _nf_proof: Vec<[u8;32]> = env::read(); // 126 hash + 2 nullifer + 2 idx
let _index: Vec<u32> = env::read();
let root: [u8;32] = env::read();
let cm1: [u8;32] = env::read(); // proof input 3
let cm2: [u8;32] = env::read(); // proof input 4
// simulate non-membership verification
assert!(simulated_nullifier_non_membership_calculation(nf));
// verify root is in the MMR peaks
assert!(commitments_mmr.contains(&root) || true);
// verify the proof
env::verify(TRANSACTION_ID,&[nf,nullifier_root,cm1,cm2].concat()).unwrap();
}
// simulate new commitment root calculation
let new_commitment_root = simulated_commitment_root_calculation(commitments_mmr[0], 32, nb_tx);
// simulate new nullifier root
let new_nullifier_root = simulated_nullifier_root_calculation(nullifier_root, nb_tx);
env::commit(&new_commitment_root);
env::commit(&new_nullifier_root);
}
The host
use std::time::Instant;
use sha2::{Digest, Sha256};
use rand::{rng, Rng};
// These constants represent the RISC-V ELF and the image ID generated by risc0-build.
// The ELF is used for proving and the ID is used for verification.
use rollup::{ROLLUP_ELF, ROLLUP_ID};
use transaction::{TRANSACTION_ELF};
use risc0_zkvm::{default_prover, ExecutorEnv, Prover, ProverOpts, ReceiptKind};
pub fn padded_leaves(elements: Vec<[u8; 32]>) -> Vec<[u8; 32]> {
let mut vector = Vec::clone(&elements);
while !vector.len().is_power_of_two() {
vector.push([0u8; 32]);
}
vector
}
pub fn node(a: [u8; 32], b: [u8; 32]) -> [u8; 32] {
let mut hasher = Sha256::new();
hasher.update(a);
hasher.update(b);
hasher.finalize().into()
}
pub fn root(elements: Vec<[u8; 32]>) -> [u8; 32] {
let mut elements = elements;
if !elements.len().is_power_of_two() {
elements = padded_leaves(elements);
}
let n = elements.len();
let mut nodes = elements;
for h in (1..=n.ilog2()).rev() {
for i in 0..2usize.pow(h - 1) {
nodes[i] = node(nodes[i * 2], nodes[i * 2 + 1]);
}
}
nodes[0]
}
pub fn path(leaves: Vec<[u8;32]>, idx: usize) -> Vec<[u8;32]> {
let mut leaves = leaves;
if !leaves.len().is_power_of_two() {
leaves = padded_leaves(leaves);
}
assert!(idx < leaves.len());
let n = leaves.len();
let mut nodes = leaves.clone();
let mut path = Vec::new();
let mut idx = idx;
for h in (1..=n.ilog2()).rev() {
if idx % 2 == 0 {
path.push(nodes[idx + 1]);
} else {
path.push(nodes[idx - 1]);
}
idx /= 2;
for i in 0..2usize.pow(h - 1) {
nodes[i] = node(nodes[i * 2], nodes[i * 2 + 1]);
}
}
path
}
fn main() {
// Initialize tracing. In order to view logs, run `RUST_LOG=info cargo run`
tracing_subscriber::fmt()
.with_env_filter(tracing_subscriber::filter::EnvFilter::from_default_env())
.init();
// An executor environment describes the configurations for the zkVM
// including program inputs.
// A default ExecutorEnv can be created like so:
// `let env = ExecutorEnv::builder().build().unwrap();`
// However, this `env` does not have any inputs.
//
// To add guest input to the executor environment, use
// ExecutorEnvBuilder::write().
// To access this method, you'll need to use ExecutorEnv::builder(), which
// creates an ExecutorEnvBuilder. When you're done adding input, call
// ExecutorEnvBuilder::build().
for nb_tx in vec![2usize] {
let mut rng = rng();
let mut commitments : Vec<[u8;32]> = Vec::new();
let mut sks : Vec<[u8;32]> = (0..nb_tx+32).map(|_| {
let mut arr = [0u8; 32];
rng.fill(&mut arr);
arr
}).collect();
let mut pks : Vec<[u8;32]> = sks.iter().map(|arr| {
let mut hasher = Sha256::new();
hasher.update(arr);
hasher.finalize().into()
}).collect();
for i in 0..nb_tx+32 {
let mut hasher = Sha256::new();
hasher.update(&1_000_000u32.to_le_bytes());
hasher.update(&pks[i]);
commitments.push(hasher.finalize().into());
}
let value = 1_000_000u32;
// Env builder rollup
let mut rollup_builder = ExecutorEnv::builder();
rollup_builder.write(&nb_tx).unwrap();
rollup_builder.write(&commitments).unwrap();
rollup_builder.write(&root(commitments.clone())).unwrap();
for i in 0..nb_tx {
println!("
=== transaction {i} over {nb_tx} txns ===");
let mut tx_builder = ExecutorEnv::builder();
// write inputs in exact order expected by guest
tx_builder.write(&value).unwrap();
tx_builder.write(&sks[i]).unwrap();
let path = path(commitments.clone(), i);
tx_builder.write(&path).unwrap();
tx_builder.write(&i).unwrap();
tx_builder.write(&(value/2)).unwrap();
tx_builder.write(&(value/2)).unwrap();
let mut arr = [0u8; 32];
rng.fill(&mut arr);
sks.push(arr);
let mut hasher = Sha256::new();
hasher.update(arr);
pks.push(hasher.finalize().into());
tx_builder.write(&pks.last()).unwrap();
let mut arr = [0u8; 32];
rng.fill(&mut arr);
sks.push(arr);
let mut hasher = Sha256::new();
hasher.update(arr);
pks.push(hasher.finalize().into());
tx_builder.write(&pks.last()).unwrap();
let env = tx_builder.build().unwrap();
let opts = ProverOpts::default().with_receipt_kind(ReceiptKind::Succinct);
let prover = default_prover();
let t0 = Instant::now();
let prove_info = prover.prove_with_opts(env, TRANSACTION_ELF, &opts).expect("prove failed");
let stark_time = t0.elapsed();
println!("transaction proof took {}s to prove", stark_time.as_secs());
let receipt = prove_info.receipt;
let bytes = &receipt.journal.bytes;
let nf: [u8;32] = bytes[0..32].try_into().unwrap();
let root: [u8;32] = bytes[32..64].try_into().unwrap();
let cm1: [u8;32] = bytes[64..96].try_into().unwrap();
let cm2: [u8;32] = bytes[96..128].try_into().unwrap();
rollup_builder.write(&nf).unwrap();
let nullifier_proof: [[u8; 32]; 128] = rand::random();
let nullifier_proof : Vec<[u8; 32]> = nullifier_proof.iter().map(|&e| e).collect();
rollup_builder.write(&nullifier_proof).unwrap();
rollup_builder.write(&[1u32, 2u32]).unwrap();
rollup_builder.write(&root).unwrap();
rollup_builder.write(&cm1).unwrap();
rollup_builder.write(&cm2).unwrap();
rollup_builder.add_assumption(receipt);
}
println!("
=== transition over {nb_tx} txns ===");
let env = rollup_builder.build().expect("build failed");
let opts = ProverOpts::default().with_receipt_kind(ReceiptKind::Succinct);
let prover = default_prover();
let t0 = Instant::now();
let prove_info = prover.prove_with_opts(env, ROLLUP_ELF, &opts).expect("prove failed");
let stark_time = t0.elapsed();
println!("rollup proof took {}s to prove", stark_time.as_secs());
let v0 = Instant::now();
prove_info.receipt.verify(ROLLUP_ID).expect("verify failed");
let verify_time = v0.elapsed();
println!("rollup proof took {}s to verify", verify_time.as_secs());
}
}
A transaction:
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 3.773123ms
number of segments: 1
131072 total cycles
66807 user cycles (50.97%)
25800 paging cycles (19.68%)
38465 reserved cycles (29.35%)
ecalls
597 Read calls, 1785 cycles, (1.36%)
23 Sha2 calls, 1702 cycles, (1.30%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
294 Read calls
4 Write calls
0 VerifyIntegrity2 calls
0 VerifyIntegrity calls
0 ProveKeccak calls
0 Keccak calls
WARNING: Proving in dev mode does not generate a valid receipt. Receipts generated from this process are invalid and should never be used in production.
transaction proof took 0s to prove
The rollup over several size of batches:
=== transition over 2 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 32.701782ms
number of segments: 3
2621440 total cycles
2252735 user cycles (85.94%)
64475 paging cycles (2.46%)
304230 reserved cycles (11.61%)
ecalls
1150 Sha2 calls, 85372 cycles, (3.26%)
19227 Read calls, 57613 cycles, (2.20%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
9577 Read calls
64 Write calls
2 VerifyIntegrity calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
=== transition over 5 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 79.885608ms
number of segments: 6
5767168 total cycles
5287945 user cycles (91.69%)
132869 paging cycles (2.30%)
346354 reserved cycles (6.01%)
ecalls
2771 Sha2 calls, 205734 cycles, (3.57%)
44787 Read calls, 134290 cycles, (2.33%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
22354 Read calls
64 Write calls
5 VerifyIntegrity calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
=== transition over 10 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 157.124539ms
number of segments: 11
11010048 total cycles
10344303 user cycles (93.95%)
245776 paging cycles (2.23%)
419969 reserved cycles (3.81%)
ecalls
5468 Sha2 calls, 405992 cycles, (3.69%)
87387 Read calls, 262085 cycles, (2.38%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
43649 Read calls
64 Write calls
10 VerifyIntegrity calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
=== transition over 50 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 726.180079ms
number of segments: 51
53477376 total cycles
50789091 user cycles (94.97%)
1098029 paging cycles (2.05%)
1590256 reserved cycles (2.97%)
ecalls
27032 Sha2 calls, 2007168 cycles, (3.75%)
428187 Read calls, 1284445 cycles, (2.40%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
214009 Read calls
64 Write calls
50 VerifyIntegrity calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
=== transition over 100 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 1.741632446s
number of segments: 102
106954752 total cycles
101343570 user cycles (94.75%)
2174348 paging cycles (2.03%)
3436834 reserved cycles (3.21%)
ecalls
53984 Sha2 calls, 4008416 cycles, (3.75%)
854187 Read calls, 2562395 cycles, (2.40%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
426959 Read calls
100 VerifyIntegrity calls
64 Write calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
=== transition over 1000 txns ===
WARNING: proving in dev mode. This will not generate valid, secure proofs.
execution time: 14.701376674s
number of segments: 1014
1062469632 total cycles
1011309132 user cycles (95.18%)
21547742 paging cycles (2.03%)
29612758 reserved cycles (2.79%)
ecalls
539090 Sha2 calls, 40028660 cycles, (3.77%)
8522187 Read calls, 25565495 cycles, (2.41%)
1 Terminate calls, 2 cycles, (0.00%)
0 Write calls, 0 cycles, (0.00%)
0 User calls, 0 cycles, (0.00%)
0 Poseidon2 calls, 0 cycles, (0.00%)
0 BigInt calls, 0 cycles, (0.00%)
syscalls
4260059 Read calls
1000 VerifyIntegrity calls
64 Write calls
0 VerifyIntegrity2 calls
0 ProveKeccak calls
0 Keccak calls
To evaluate how long it would take to prove the 1000 transactions, we use the same formula as risc0 provide for RTX 4090:
1 062 469 632 cycles of execute: 11.8 seconds (at 90 MHz)1114 calls to rv32im (each of 1 048 576 cycles): 872 seconds (at 1.34 MHz)1114 calls to lift (each of 256 000 cycles): 210 seconds (at 1.36 MHz)1113 calls to join (each of 256 000 cycles): 238 seconds (at 1.2 MHz)