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());
}
}