Nova/examples/signature.rs
examples/signature.rsRaw
1use bellperson::{
2 gadgets::{boolean::AllocatedBit, test::TestConstraintSystem},
3 ConstraintSystem, SynthesisError,
4};
5use core::ops::{AddAssign, MulAssign};
6use ff::{
7 derive::byteorder::{ByteOrder, LittleEndian},
8 Field, PrimeField, PrimeFieldBits,
9};
10use nova_snark::{gadgets::ecc::AllocatedPoint, traits::Group as NovaGroup};
11use num_bigint::BigUint;
12use pasta_curves::{
13 arithmetic::CurveAffine,
14 group::{Curve, Group},
15};
16use rand::{rngs::OsRng, RngCore};
17use sha3::{Digest, Sha3_512};
18
19#[derive(Debug, Clone, Copy)]
20pub struct SecretKey<G: Group>(G::Scalar);
21
22impl<G> SecretKey<G>
23where
24 G: Group,
25{
26 pub fn random(mut rng: impl RngCore) -> Self {
27 let secret = G::Scalar::random(&mut rng);
28 Self(secret)
29 }
30}
31
32#[derive(Debug, Clone, Copy)]
33pub struct PublicKey<G: Group>(G);
34
35impl<G> PublicKey<G>
36where
37 G: Group,
38{
39 pub fn from_secret_key(s: &SecretKey<G>) -> Self {
40 let point = G::generator() * s.0;
41 Self(point)
42 }
43}
44
45#[derive(Clone)]
46pub struct Signature<G: Group> {
47 pub r: G,
48 pub s: G::Scalar,
49}
50
51impl<G> SecretKey<G>
52where
53 G: Group,
54{
55 pub fn sign(self, c: G::Scalar, mut rng: impl RngCore) -> Signature<G> {
56 // T
57 let mut t = [0u8; 80];
58 rng.fill_bytes(&mut t[..]);
59
60 // h = H*(T || M)
61 let h = Self::hash_to_scalar(b"Nova_Ecdsa_Hash", &t[..], c.to_repr().as_mut());
62
63 // R = [h]G
64 let r = G::generator().mul(h);
65
66 // s = h + c * sk
67 let mut s = c;
68
69 s.mul_assign(&self.0);
70 s.add_assign(&h);
71
72 Signature { r, s }
73 }
74
75 fn mul_bits<B: AsRef<[u64]>>(s: &G::Scalar, bits: BitIterator<B>) -> G::Scalar {
76 let mut x = G::Scalar::zero();
77 for bit in bits {
78 x = x.double();
79
80 if bit {
81 x.add_assign(s)
82 }
83 }
84 x
85 }
86
87 fn to_uniform(digest: &[u8]) -> G::Scalar {
88 assert_eq!(digest.len(), 64);
89 let mut bits: [u64; 8] = [0; 8];
90 LittleEndian::read_u64_into(digest, &mut bits);
91 Self::mul_bits(&G::Scalar::one(), BitIterator::new(bits))
92 }
93
94 pub fn to_uniform_32(digest: &[u8]) -> G::Scalar {
95 assert_eq!(digest.len(), 32);
96 let mut bits: [u64; 4] = [0; 4];
97 LittleEndian::read_u64_into(digest, &mut bits);
98 Self::mul_bits(&G::Scalar::one(), BitIterator::new(bits))
99 }
100
101 pub fn hash_to_scalar(persona: &[u8], a: &[u8], b: &[u8]) -> G::Scalar {
102 let mut hasher = Sha3_512::new();
103 hasher.input(persona);
104 hasher.input(a);
105 hasher.input(b);
106 let digest = hasher.result();
107 Self::to_uniform(digest.as_ref())
108 }
109}
110
111impl<G> PublicKey<G>
112where
113 G: Group,
114 G::Scalar: PrimeFieldBits,
115{
116 pub fn verify(&self, c: G::Scalar, signature: &Signature<G>) -> bool {
117 let modulus = Self::modulus_as_scalar();
118 let order_check_pk = self.0.mul(modulus);
119 if !order_check_pk.eq(&G::identity()) {
120 return false;
121 }
122
123 let order_check_r = signature.r.mul(modulus);
124 if !order_check_r.eq(&G::identity()) {
125 return false;
126 }
127
128 // 0 = [-s]G + R + [c]PK
129 self
130 .0
131 .mul(c)
132 .add(&signature.r)
133 .add(G::generator().mul(signature.s).neg())
134 .eq(&G::identity())
135 }
136
137 fn modulus_as_scalar() -> G::Scalar {
138 let mut bits = G::Scalar::char_le_bits().to_bitvec();
139 let mut acc = BigUint::new(Vec::<u32>::new());
140 while let Some(b) = bits.pop() {
141 acc <<= 1_i32;
142 acc += b as u8;
143 }
144 let modulus = acc.to_str_radix(10);
145 G::Scalar::from_str_vartime(&modulus).unwrap()
146 }
147}
148
149#[derive(Debug)]
150pub struct BitIterator<E> {
151 t: E,
152 n: usize,
153}
154
155impl<E: AsRef<[u64]>> BitIterator<E> {
156 pub fn new(t: E) -> Self {
157 let n = t.as_ref().len() * 64;
158
159 BitIterator { t, n }
160 }
161}
162
163impl<E: AsRef<[u64]>> Iterator for BitIterator<E> {
164 type Item = bool;
165
166 fn next(&mut self) -> Option<bool> {
167 if self.n == 0 {
168 None
169 } else {
170 self.n -= 1;
171 let part = self.n / 64;
172 let bit = self.n - (64 * part);
173
174 Some(self.t.as_ref()[part] & (1 << bit) > 0)
175 }
176 }
177}
178
179// Synthesize a bit representation into circuit gadgets.
180pub fn synthesize_bits<F: PrimeField, CS: ConstraintSystem<F>>(
181 cs: &mut CS,
182 bits: Option<Vec<bool>>,
183) -> Result<Vec<AllocatedBit>, SynthesisError> {
184 (0..F::NUM_BITS)
185 .map(|i| {
186 AllocatedBit::alloc(
187 cs.namespace(|| format!("bit {i}")),
188 Some(bits.as_ref().unwrap()[i as usize]),
189 )
190 })
191 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
192}
193
194pub fn verify_signature<G: NovaGroup, CS: ConstraintSystem<G::Base>>(
195 cs: &mut CS,
196 pk: AllocatedPoint<G>,
197 r: AllocatedPoint<G>,
198 s_bits: Vec<AllocatedBit>,
199 c_bits: Vec<AllocatedBit>,
200) -> Result<(), SynthesisError> {
201 let g = AllocatedPoint::<G>::alloc(
202 cs.namespace(|| "g"),
203 Some((
204 G::Base::from_str_vartime(
205 "28948022309329048855892746252171976963363056481941647379679742748393362948096",
206 )
207 .unwrap(),
208 G::Base::from_str_vartime("2").unwrap(),
209 false,
210 )),
211 )
212 .unwrap();
213
214 cs.enforce(
215 || "gx is vesta curve",
216 |lc| lc + g.get_coordinates().0.get_variable(),
217 |lc| lc + CS::one(),
218 |lc| {
219 lc + (
220 G::Base::from_str_vartime(
221 "28948022309329048855892746252171976963363056481941647379679742748393362948096",
222 )
223 .unwrap(),
224 CS::one(),
225 )
226 },
227 );
228
229 cs.enforce(
230 || "gy is vesta curve",
231 |lc| lc + g.get_coordinates().1.get_variable(),
232 |lc| lc + CS::one(),
233 |lc| lc + (G::Base::from_str_vartime("2").unwrap(), CS::one()),
234 );
235
236 let sg = g.scalar_mul(cs.namespace(|| "[s]G"), s_bits)?;
237 let cpk = pk.scalar_mul(&mut cs.namespace(|| "[c]PK"), c_bits)?;
238 let rcpk = cpk.add(&mut cs.namespace(|| "R + [c]PK"), &r)?;
239
240 let (rcpk_x, rcpk_y, _) = rcpk.get_coordinates();
241 let (sg_x, sg_y, _) = sg.get_coordinates();
242
243 cs.enforce(
244 || "sg_x == rcpk_x",
245 |lc| lc + sg_x.get_variable(),
246 |lc| lc + CS::one(),
247 |lc| lc + rcpk_x.get_variable(),
248 );
249
250 cs.enforce(
251 || "sg_y == rcpk_y",
252 |lc| lc + sg_y.get_variable(),
253 |lc| lc + CS::one(),
254 |lc| lc + rcpk_y.get_variable(),
255 );
256
257 Ok(())
258}
259
260type G1 = pasta_curves::pallas::Point;
261type G2 = pasta_curves::vesta::Point;
262
263fn main() {
264 let mut cs = TestConstraintSystem::<<G1 as Group>::Scalar>::new();
265 assert!(cs.is_satisfied());
266 assert_eq!(cs.num_constraints(), 0);
267
268 let sk = SecretKey::<G2>::random(&mut OsRng);
269 let pk = PublicKey::from_secret_key(&sk);
270
271 // generate a random message to sign
272 let c = <G2 as Group>::Scalar::random(&mut OsRng);
273
274 // sign and verify
275 let signature = sk.sign(c, &mut OsRng);
276 let result = pk.verify(c, &signature);
277 assert!(result);
278
279 // prepare inputs to the circuit gadget
280 let pk = {
281 let pkxy = pk.0.to_affine().coordinates().unwrap();
282
283 AllocatedPoint::<G2>::alloc(
284 cs.namespace(|| "pub key"),
285 Some((*pkxy.x(), *pkxy.y(), false)),
286 )
287 .unwrap()
288 };
289 let r = {
290 let rxy = signature.r.to_affine().coordinates().unwrap();
291 AllocatedPoint::alloc(cs.namespace(|| "r"), Some((*rxy.x(), *rxy.y(), false))).unwrap()
292 };
293 let s = {
294 let s_bits = signature
295 .s
296 .to_le_bits()
297 .iter()
298 .map(|b| *b)
299 .collect::<Vec<bool>>();
300
301 synthesize_bits(&mut cs.namespace(|| "s bits"), Some(s_bits)).unwrap()
302 };
303 let c = {
304 let c_bits = c.to_le_bits().iter().map(|b| *b).collect::<Vec<bool>>();
305
306 synthesize_bits(&mut cs.namespace(|| "c bits"), Some(c_bits)).unwrap()
307 };
308
309 // Check the signature was signed by the correct sk using the pk
310 verify_signature(&mut cs, pk, r, s, c).unwrap();
311
312 assert!(cs.is_satisfied());
313}