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