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 .into_iter()
186 .map(|i| {
187 AllocatedBit::alloc(
188 cs.namespace(|| format!("bit {i}")),
189 Some(bits.as_ref().unwrap()[i as usize]),
190 )
191 })
192 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
193}
194
195pub fn verify_signature<G: NovaGroup, CS: ConstraintSystem<G::Base>>(
196 cs: &mut CS,
197 pk: AllocatedPoint<G>,
198 r: AllocatedPoint<G>,
199 s_bits: Vec<AllocatedBit>,
200 c_bits: Vec<AllocatedBit>,
201) -> Result<(), SynthesisError> {
202 let g = AllocatedPoint::<G>::alloc(
203 cs.namespace(|| "g"),
204 Some((
205 G::Base::from_str_vartime(
206 "28948022309329048855892746252171976963363056481941647379679742748393362948096",
207 )
208 .unwrap(),
209 G::Base::from_str_vartime("2").unwrap(),
210 false,
211 )),
212 )
213 .unwrap();
214
215 cs.enforce(
216 || "gx is vesta curve",
217 |lc| lc + g.get_coordinates().0.get_variable(),
218 |lc| lc + CS::one(),
219 |lc| {
220 lc + (
221 G::Base::from_str_vartime(
222 "28948022309329048855892746252171976963363056481941647379679742748393362948096",
223 )
224 .unwrap(),
225 CS::one(),
226 )
227 },
228 );
229
230 cs.enforce(
231 || "gy is vesta curve",
232 |lc| lc + g.get_coordinates().1.get_variable(),
233 |lc| lc + CS::one(),
234 |lc| lc + (G::Base::from_str_vartime("2").unwrap(), CS::one()),
235 );
236
237 let sg = g.scalar_mul(cs.namespace(|| "[s]G"), s_bits)?;
238 let cpk = pk.scalar_mul(&mut cs.namespace(|| "[c]PK"), c_bits)?;
239 let rcpk = cpk.add(&mut cs.namespace(|| "R + [c]PK"), &r)?;
240
241 let (rcpk_x, rcpk_y, _) = rcpk.get_coordinates();
242 let (sg_x, sg_y, _) = sg.get_coordinates();
243
244 cs.enforce(
245 || "sg_x == rcpk_x",
246 |lc| lc + sg_x.get_variable(),
247 |lc| lc + CS::one(),
248 |lc| lc + rcpk_x.get_variable(),
249 );
250
251 cs.enforce(
252 || "sg_y == rcpk_y",
253 |lc| lc + sg_y.get_variable(),
254 |lc| lc + CS::one(),
255 |lc| lc + rcpk_y.get_variable(),
256 );
257
258 Ok(())
259}
260
261type G1 = pasta_curves::pallas::Point;
262type G2 = pasta_curves::vesta::Point;
263
264fn main() {
265 let mut cs = TestConstraintSystem::<<G1 as Group>::Scalar>::new();
266 assert!(cs.is_satisfied());
267 assert_eq!(cs.num_constraints(), 0);
268
269 let sk = SecretKey::<G2>::random(&mut OsRng);
270 let pk = PublicKey::from_secret_key(&sk);
271
272 // generate a random message to sign
273 let c = <G2 as Group>::Scalar::random(&mut OsRng);
274
275 // sign and verify
276 let signature = sk.sign(c, &mut OsRng);
277 let result = pk.verify(c, &signature);
278 assert!(result);
279
280 // prepare inputs to the circuit gadget
281 let pk = {
282 let pkxy = pk.0.to_affine().coordinates().unwrap();
283
284 AllocatedPoint::<G2>::alloc(
285 cs.namespace(|| "pub key"),
286 Some((*pkxy.x(), *pkxy.y(), false)),
287 )
288 .unwrap()
289 };
290 let r = {
291 let rxy = signature.r.to_affine().coordinates().unwrap();
292 AllocatedPoint::alloc(cs.namespace(|| "r"), Some((*rxy.x(), *rxy.y(), false))).unwrap()
293 };
294 let s = {
295 let s_bits = signature
296 .s
297 .to_le_bits()
298 .iter()
299 .map(|b| *b)
300 .collect::<Vec<bool>>();
301
302 synthesize_bits(&mut cs.namespace(|| "s bits"), Some(s_bits)).unwrap()
303 };
304 let c = {
305 let c_bits = c.to_le_bits().iter().map(|b| *b).collect::<Vec<bool>>();
306
307 synthesize_bits(&mut cs.namespace(|| "c bits"), Some(c_bits)).unwrap()
308 };
309
310 // Check the signature was signed by the correct sk using the pk
311 verify_signature(&mut cs, pk, r, s, c).unwrap();
312
313 assert!(cs.is_satisfied());
314}