Nova/examples/ecdsa/main.rs
examples/ecdsa/main.rsRaw
1//! Demonstrates how to use Nova to produce a recursive proof of an ECDSA signature.
2//! This example proves the knowledge of a sequence of ECDSA signatures with different public keys on different messages,
3//! but the example can be adapted to other settings (e.g., proving the validity of the certificate chain with a well-known root public key)
4//! Scheme borrowed from https://github.com/filecoin-project/bellperson-gadgets/blob/main/src/eddsa.rs
5//! Sign using G1 curve, and prove using G2 curve.
6
7use core::ops::{Add, AddAssign, Mul, MulAssign, Neg};
8use ff::{
9 derive::byteorder::{ByteOrder, LittleEndian},
10 Field, PrimeField, PrimeFieldBits,
11};
12use generic_array::typenum::U8;
13use neptune::{poseidon::PoseidonConstants, Strength};
14use nova_snark::{
15 traits::{circuit::TrivialTestCircuit, Group as Nova_Group},
16 CompressedSNARK, PublicParams, RecursiveSNARK,
17};
18use num_bigint::BigUint;
19use pasta_curves::{
20 arithmetic::CurveAffine,
21 group::{Curve, Group},
22};
23use rand::{rngs::OsRng, RngCore};
24use sha3::{Digest, Sha3_512};
25use subtle::Choice;
26
27mod circuit;
28mod utils;
29
30use crate::circuit::{Coordinate, EcdsaCircuit, EcdsaSignature};
31use crate::utils::BitIterator;
32
33type G1 = pasta_curves::pallas::Point;
34type G2 = pasta_curves::vesta::Point;
35type S1 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
36type S2 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
37
38#[derive(Debug, Clone, Copy)]
39pub struct SecretKey(pub <G1 as Group>::Scalar);
40
41impl SecretKey {
42 pub fn random(mut rng: impl RngCore) -> Self {
43 let secret = <G1 as Group>::Scalar::random(&mut rng);
44 Self(secret)
45 }
46}
47
48#[derive(Debug, Clone, Copy)]
49pub struct PublicKey(pub G1);
50
51impl PublicKey {
52 pub fn from_secret_key(s: &SecretKey) -> Self {
53 let point = G1::generator() * s.0;
54 Self(point)
55 }
56}
57
58#[derive(Clone)]
59pub struct Signature {
60 pub r: G1,
61 pub s: <G1 as Group>::Scalar,
62}
63
64impl SecretKey {
65 pub fn sign(self, c: <G1 as Group>::Scalar, mut rng: impl RngCore) -> Signature {
66 // T
67 let mut t = [0u8; 80];
68 rng.fill_bytes(&mut t[..]);
69
70 // h = H*(T || M)
71 let h = Self::hash_to_scalar(b"Nova_Ecdsa_Hash", &t[..], &c.to_repr());
72
73 // R = [h]G
74 let r = G1::generator().mul(h);
75
76 // s = h + c * sk
77 let mut s = c;
78
79 s.mul_assign(&self.0);
80 s.add_assign(&h);
81
82 Signature { r, s }
83 }
84
85 fn mul_bits<B: AsRef<[u64]>>(
86 s: &<G1 as Group>::Scalar,
87 bits: BitIterator<B>,
88 ) -> <G1 as Group>::Scalar {
89 let mut x = <G1 as Group>::Scalar::zero();
90 for bit in bits {
91 x.double();
92
93 if bit {
94 x.add_assign(s)
95 }
96 }
97 x
98 }
99
100 fn to_uniform(digest: &[u8]) -> <G1 as Group>::Scalar {
101 assert_eq!(digest.len(), 64);
102 let mut bits: [u64; 8] = [0; 8];
103 LittleEndian::read_u64_into(digest, &mut bits);
104 Self::mul_bits(&<G1 as Group>::Scalar::one(), BitIterator::new(bits))
105 }
106
107 pub fn to_uniform_32(digest: &[u8]) -> <G1 as Group>::Scalar {
108 assert_eq!(digest.len(), 32);
109 let mut bits: [u64; 4] = [0; 4];
110 LittleEndian::read_u64_into(digest, &mut bits);
111 Self::mul_bits(&<G1 as Group>::Scalar::one(), BitIterator::new(bits))
112 }
113
114 pub fn hash_to_scalar(persona: &[u8], a: &[u8], b: &[u8]) -> <G1 as Group>::Scalar {
115 let mut hasher = Sha3_512::new();
116 hasher.input(persona);
117 hasher.input(a);
118 hasher.input(b);
119 let digest = hasher.result();
120 Self::to_uniform(digest.as_ref())
121 }
122}
123
124impl PublicKey {
125 pub fn verify(&self, c: <G1 as Group>::Scalar, signature: &Signature) -> bool {
126 let modulus = Self::modulus_as_scalar();
127 let order_check_pk = self.0.mul(modulus);
128 if !order_check_pk.eq(&G1::identity()) {
129 return false;
130 }
131
132 let order_check_r = signature.r.mul(modulus);
133 if !order_check_r.eq(&G1::identity()) {
134 return false;
135 }
136
137 // 0 = [-s]G + R + [c]PK
138 self
139 .0
140 .mul(c)
141 .add(&signature.r)
142 .add(G1::generator().mul(signature.s).neg())
143 .eq(&G1::identity())
144 }
145
146 fn modulus_as_scalar() -> <G1 as Group>::Scalar {
147 let mut bits = <G1 as Group>::Scalar::char_le_bits().to_bitvec();
148 let mut acc = BigUint::new(Vec::<u32>::new());
149 while let Some(b) = bits.pop() {
150 acc <<= 1_i32;
151 acc += b as u8;
152 }
153 let modulus = acc.to_str_radix(10);
154 <G1 as Group>::Scalar::from_str_vartime(&modulus).unwrap()
155 }
156}
157
158fn main() {
159 // In a VERY LIMITED case of messages known to be unique due to application level
160 // and being less than the group order when interpreted as integer, one can sign
161 // the message directly without hashing
162 pub const MAX_MESSAGE_LEN: usize = 16;
163 assert!(MAX_MESSAGE_LEN * 8 <= <G1 as Group>::Scalar::CAPACITY as usize);
164
165 // produce public parameters
166 println!("Generating public parameters...");
167
168 let pc = PoseidonConstants::<<G2 as Group>::Scalar, U8>::new_with_strength(Strength::Standard);
169 let circuit_primary = EcdsaCircuit::<<G2 as Nova_Group>::Scalar> {
170 z_r: Coordinate::new(
171 <G2 as Nova_Group>::Scalar::zero(),
172 <G2 as Nova_Group>::Scalar::zero(),
173 ),
174 z_g: Coordinate::new(
175 <G2 as Nova_Group>::Scalar::zero(),
176 <G2 as Nova_Group>::Scalar::zero(),
177 ),
178 z_pk: Coordinate::new(
179 <G2 as Nova_Group>::Scalar::zero(),
180 <G2 as Nova_Group>::Scalar::zero(),
181 ),
182 z_c: <G2 as Nova_Group>::Scalar::zero(),
183 z_s: <G2 as Nova_Group>::Scalar::zero(),
184 r: Coordinate::new(
185 <G2 as Nova_Group>::Scalar::zero(),
186 <G2 as Nova_Group>::Scalar::zero(),
187 ),
188 g: Coordinate::new(
189 <G2 as Nova_Group>::Scalar::zero(),
190 <G2 as Nova_Group>::Scalar::zero(),
191 ),
192 pk: Coordinate::new(
193 <G2 as Nova_Group>::Scalar::zero(),
194 <G2 as Nova_Group>::Scalar::zero(),
195 ),
196 c: <G2 as Nova_Group>::Scalar::zero(),
197 s: <G2 as Nova_Group>::Scalar::zero(),
198 c_bits: vec![Choice::from(0u8); 256],
199 s_bits: vec![Choice::from(0u8); 256],
200 pc: pc.clone(),
201 };
202
203 let circuit_secondary = TrivialTestCircuit::default();
204
205 let pp = PublicParams::<
206 G2,
207 G1,
208 EcdsaCircuit<<G2 as Group>::Scalar>,
209 TrivialTestCircuit<<G1 as Group>::Scalar>,
210 >::setup(circuit_primary, circuit_secondary.clone());
211
212 // produce non-deterministic advice
213 println!("Generating non-deterministic advice...");
214
215 let num_steps = 3;
216
217 let signatures = || {
218 let mut signatures = Vec::new();
219 for i in 0..num_steps {
220 let sk = SecretKey::random(&mut OsRng);
221 let pk = PublicKey::from_secret_key(&sk);
222
223 let message = format!("MESSAGE{}", i).as_bytes().to_owned();
224 assert!(message.len() <= MAX_MESSAGE_LEN);
225
226 let mut digest: Vec<u8> = message.to_vec();
227 for _ in 0..(32 - message.len() as u32) {
228 digest.extend(&[0u8; 1]);
229 }
230
231 let c = SecretKey::to_uniform_32(digest.as_ref());
232
233 let signature_primary = sk.sign(c, &mut OsRng);
234 let result = pk.verify(c, &signature_primary);
235 assert!(result);
236
237 // Affine coordinates guaranteed to be on the curve
238 let rxy = signature_primary.r.to_affine().coordinates().unwrap();
239 let gxy = G1::generator().to_affine().coordinates().unwrap();
240 let pkxy = pk.0.to_affine().coordinates().unwrap();
241
242 let s = signature_primary.s;
243
244 signatures.push(EcdsaSignature::<
245 <G1 as Nova_Group>::Base,
246 <G1 as Nova_Group>::Scalar,
247 >::new(
248 Coordinate::<<G1 as Nova_Group>::Base>::new(*pkxy.x(), *pkxy.y()),
249 Coordinate::<<G1 as Nova_Group>::Base>::new(*rxy.x(), *rxy.y()),
250 s,
251 c,
252 Coordinate::<<G1 as Nova_Group>::Base>::new(*gxy.x(), *gxy.y()),
253 ));
254 }
255 signatures
256 };
257
258 let (z0_primary, circuits_primary) = EcdsaCircuit::<<G2 as Nova_Group>::Scalar>::new::<
259 <G1 as Nova_Group>::Base,
260 <G1 as Nova_Group>::Scalar,
261 >(num_steps, &signatures(), &pc);
262
263 // Secondary circuit
264 let z0_secondary = <G1 as Group>::Scalar::zero();
265
266 // produce a recursive SNARK
267 println!("Generating a RecursiveSNARK...");
268
269 type C1 = EcdsaCircuit<<G2 as Nova_Group>::Scalar>;
270 type C2 = TrivialTestCircuit<<G1 as Nova_Group>::Scalar>;
271
272 let mut recursive_snark: Option<RecursiveSNARK<G2, G1, C1, C2>> = None;
273
274 for (i, circuit_primary) in circuits_primary.iter().take(num_steps).enumerate() {
275 let result = RecursiveSNARK::prove_step(
276 &pp,
277 recursive_snark,
278 circuit_primary.clone(),
279 circuit_secondary.clone(),
280 z0_primary,
281 z0_secondary,
282 );
283 assert!(result.is_ok());
284 println!("RecursiveSNARK::prove_step {}: {:?}", i, result.is_ok());
285 recursive_snark = Some(result.unwrap());
286 }
287
288 assert!(recursive_snark.is_some());
289 let recursive_snark = recursive_snark.unwrap();
290
291 // verify the recursive SNARK
292 println!("Verifying the RecursiveSNARK...");
293 let res = recursive_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
294 println!("RecursiveSNARK::verify: {:?}", res.is_ok());
295 assert!(res.is_ok());
296
297 // produce a compressed SNARK
298 println!("Generating a CompressedSNARK...");
299 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
300 println!("CompressedSNARK::prove: {:?}", res.is_ok());
301 assert!(res.is_ok());
302 let compressed_snark = res.unwrap();
303
304 // verify the compressed SNARK
305 println!("Verifying a CompressedSNARK...");
306 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
307 println!("CompressedSNARK::verify: {:?}", res.is_ok());
308 assert!(res.is_ok());
309}