Nova/benches/sha256.rs
benches/sha256.rsRaw
1//! Benchmarks Nova's prover for proving SHA-256 with varying sized messages.
2//! We run a single step with the step performing the entire computation.
3//! This code invokes a hand-written SHA-256 gadget from bellman/bellperson.
4//! It also uses code from bellman/bellperson to compare circuit-generated digest with sha2 crate's output
5#![allow(non_snake_case)]
6type G1 = pasta_curves::pallas::Point;
7type G2 = pasta_curves::vesta::Point;
8use ::bellperson::{
9 gadgets::{
10 boolean::{AllocatedBit, Boolean},
11 num::{AllocatedNum, Num},
12 sha256::sha256,
13 Assignment,
14 },
15 ConstraintSystem, SynthesisError,
16};
17use core::time::Duration;
18use criterion::*;
19use ff::{PrimeField, PrimeFieldBits};
20use nova_snark::{
21 traits::{
22 circuit::{StepCircuit, TrivialTestCircuit},
23 Group,
24 },
25 PublicParams, RecursiveSNARK,
26};
27use sha2::{Digest, Sha256};
28
29#[derive(Clone, Debug)]
30struct Sha256Circuit<Scalar: PrimeField> {
31 preimage: Vec<u8>,
32 digest: Scalar,
33}
34
35impl<Scalar: PrimeField + PrimeFieldBits> StepCircuit<Scalar> for Sha256Circuit<Scalar> {
36 fn arity(&self) -> usize {
37 1
38 }
39
40 fn synthesize<CS: ConstraintSystem<Scalar>>(
41 &self,
42 cs: &mut CS,
43 _z: &[AllocatedNum<Scalar>],
44 ) -> Result<Vec<AllocatedNum<Scalar>>, SynthesisError> {
45 let mut z_out: Vec<AllocatedNum<Scalar>> = Vec::new();
46
47 let bit_values: Vec<_> = self
48 .preimage
49 .clone()
50 .into_iter()
51 .flat_map(|byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8))
52 .map(Some)
53 .collect();
54 assert_eq!(bit_values.len(), self.preimage.len() * 8);
55
56 let preimage_bits = bit_values
57 .into_iter()
58 .enumerate()
59 .map(|(i, b)| AllocatedBit::alloc(cs.namespace(|| format!("preimage bit {i}")), b))
60 .map(|b| b.map(Boolean::from))
61 .collect::<Result<Vec<_>, _>>()?;
62
63 let hash_bits = sha256(cs.namespace(|| "sha256"), &preimage_bits)?;
64
65 for (i, hash_bits) in hash_bits.chunks(256_usize).enumerate() {
66 let mut num = Num::<Scalar>::zero();
67 let mut coeff = Scalar::ONE;
68 for bit in hash_bits {
69 num = num.add_bool_with_coeff(CS::one(), bit, coeff);
70
71 coeff = coeff.double();
72 }
73
74 let hash = AllocatedNum::alloc(cs.namespace(|| format!("input {i}")), || {
75 Ok(*num.get_value().get()?)
76 })?;
77
78 // num * 1 = hash
79 cs.enforce(
80 || format!("packing constraint {i}"),
81 |_| num.lc(Scalar::ONE),
82 |lc| lc + CS::one(),
83 |lc| lc + hash.get_variable(),
84 );
85 z_out.push(hash);
86 }
87
88 // sanity check with the hasher
89 let mut hasher = Sha256::new();
90 hasher.update(&self.preimage);
91 let hash_result = hasher.finalize();
92
93 let mut s = hash_result
94 .iter()
95 .flat_map(|&byte| (0..8).rev().map(move |i| (byte >> i) & 1u8 == 1u8));
96
97 for b in hash_bits {
98 match b {
99 Boolean::Is(b) => {
100 assert!(s.next().unwrap() == b.get_value().unwrap());
101 }
102 Boolean::Not(b) => {
103 assert!(s.next().unwrap() != b.get_value().unwrap());
104 }
105 Boolean::Constant(_b) => {
106 panic!("Can't reach here")
107 }
108 }
109 }
110
111 Ok(z_out)
112 }
113
114 fn output(&self, _z: &[Scalar]) -> Vec<Scalar> {
115 vec![self.digest]
116 }
117}
118
119type C1 = Sha256Circuit<<G1 as Group>::Scalar>;
120type C2 = TrivialTestCircuit<<G2 as Group>::Scalar>;
121
122criterion_group! {
123name = recursive_snark;
124config = Criterion::default().warm_up_time(Duration::from_millis(3000));
125targets = bench_recursive_snark
126}
127
128criterion_main!(recursive_snark);
129
130fn bench_recursive_snark(c: &mut Criterion) {
131 let bytes_to_scalar = |bytes: [u8; 32]| -> <G1 as Group>::Scalar {
132 let mut bytes_le = bytes;
133 bytes_le.reverse();
134 <G1 as Group>::Scalar::from_repr(bytes_le).unwrap()
135 };
136
137 let decode_hex = |s: &str| -> <G1 as Group>::Scalar {
138 let bytes = (0..s.len())
139 .step_by(2)
140 .map(|i| u8::from_str_radix(&s[i..i + 2], 16))
141 .collect::<Result<Vec<u8>, _>>()
142 .unwrap();
143 let bytes_arr: [u8; 32] = bytes.try_into().unwrap();
144 bytes_to_scalar(bytes_arr)
145 };
146
147 // Test vectors
148 let circuits = vec![
149 Sha256Circuit {
150 preimage: vec![0u8; 64],
151 digest: decode_hex("12df9ae4958c1957170f9b04c4bc00c27315c5d75a391f4b672f952842bfa5ac"),
152 },
153 Sha256Circuit {
154 preimage: vec![0u8; 128],
155 digest: decode_hex("13abfac9782cb9c13c4508bde596f1914fe2f744f6a661c0c9a16659745c4e1b"),
156 },
157 Sha256Circuit {
158 preimage: vec![0u8; 256],
159 digest: decode_hex("0f5a007b5aef126a58f9bbd937842967c44253e7f97d98b5cd10bfe44d6782c8"),
160 },
161 Sha256Circuit {
162 preimage: vec![0u8; 512],
163 digest: decode_hex("06a6cfaad91d49366f18443cd4e11576ff27c174bb9fe2bc54735a79e3e456e0"),
164 },
165 Sha256Circuit {
166 preimage: vec![0u8; 1024],
167 digest: decode_hex("3763c73508f5fbb36daae8257d6c5c07db08ec5df0549ccf692b9fa218fd0ef7"),
168 },
169 Sha256Circuit {
170 preimage: vec![0u8; 2048],
171 digest: decode_hex("35c18d6c3cf49e42b3ffcb54ea04bdc16617efba0e673abc8c858257955005a5"),
172 },
173 Sha256Circuit {
174 preimage: vec![0u8; 4096],
175 digest: decode_hex("25349112d1bd5ba15e3e2d3effa01af1da02c097ce6208cdf28f34b74d35feb2"),
176 },
177 Sha256Circuit {
178 preimage: vec![0u8; 8192],
179 digest: decode_hex("22bc891155c7d423039a2206ed4a5342755948baeb13a54b61dbead7c3d3b8f6"),
180 },
181 Sha256Circuit {
182 preimage: vec![0u8; 16384],
183 digest: decode_hex("3fda713dc72ddcd42ce625c75f7e41d526d30647278a3dfcda95904e59ade7f1"),
184 },
185 Sha256Circuit {
186 preimage: vec![0u8; 32768],
187 digest: decode_hex("1e2091bd3e3cedffebb7316b52414fff82511cbd232561874a4ae11ae2040ac1"),
188 },
189 Sha256Circuit {
190 preimage: vec![0u8; 65536],
191 digest: decode_hex("0c33953975c438ce357912f27b0fbcf98bae6eb68a1a913386672ee406a4f479"),
192 },
193 ];
194
195 for circuit_primary in circuits {
196 let mut group = c.benchmark_group(format!(
197 "NovaProve-Sha256-message-len-{}",
198 circuit_primary.preimage.len()
199 ));
200 group.sample_size(10);
201
202 // Produce public parameters
203 let pp =
204 PublicParams::<G1, G2, C1, C2>::setup(circuit_primary.clone(), TrivialTestCircuit::default());
205
206 let circuit_secondary = TrivialTestCircuit::default();
207 let z0_primary = vec![<G1 as Group>::Scalar::from(2u64)];
208 let z0_secondary = vec![<G2 as Group>::Scalar::from(2u64)];
209
210 group.bench_function("Prove", |b| {
211 b.iter(|| {
212 let mut recursive_snark = RecursiveSNARK::new(
213 black_box(&pp),
214 black_box(&circuit_primary),
215 black_box(&circuit_secondary),
216 black_box(z0_primary.clone()),
217 black_box(z0_secondary.clone()),
218 );
219 // produce a recursive SNARK for a step of the recursion
220 assert!(recursive_snark
221 .prove_step(
222 black_box(&pp),
223 black_box(&circuit_primary),
224 black_box(&circuit_secondary),
225 black_box(z0_primary.clone()),
226 black_box(z0_secondary.clone()),
227 )
228 .is_ok());
229 })
230 });
231 group.finish();
232 }
233}