Nova/examples/ecdsa/circuit.rs
examples/ecdsa/circuit.rsRaw
1use bellperson::{
2 gadgets::{boolean::AllocatedBit, num::AllocatedNum},
3 ConstraintSystem, SynthesisError,
4};
5use ff::{PrimeField, PrimeFieldBits};
6use generic_array::typenum::U8;
7use neptune::{
8 circuit::poseidon_hash,
9 poseidon::{Poseidon, PoseidonConstants},
10};
11use nova_snark::{gadgets::ecc::AllocatedPoint, traits::circuit::StepCircuit};
12use subtle::Choice;
13
14// An affine point coordinate that is on the curve.
15#[derive(Clone, Copy, Debug)]
16pub struct Coordinate<F>
17where
18 F: PrimeField<Repr = [u8; 32]>,
19{
20 pub x: F,
21 pub y: F,
22 pub is_infinity: bool,
23}
24
25impl<F> Coordinate<F>
26where
27 F: PrimeField<Repr = [u8; 32]>,
28{
29 // New affine point coordiante on the curve so is_infinity = false.
30 pub fn new(x: F, y: F) -> Self {
31 Self {
32 x,
33 y,
34 is_infinity: false,
35 }
36 }
37}
38
39// An ECDSA signature
40#[derive(Clone, Debug)]
41pub struct EcdsaSignature<Fb, Fs>
42where
43 Fb: PrimeField<Repr = [u8; 32]>,
44 Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
45{
46 pk: Coordinate<Fb>, // public key
47 r: Coordinate<Fb>, // (r, s) is the ECDSA signature
48 s: Fs,
49 c: Fs, // hash of the message
50 g: Coordinate<Fb>, // generator of the group; could be omitted if Nova's traits allow accessing the generator
51}
52
53impl<Fb, Fs> EcdsaSignature<Fb, Fs>
54where
55 Fb: PrimeField<Repr = [u8; 32]>,
56 Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
57{
58 pub fn new(pk: Coordinate<Fb>, r: Coordinate<Fb>, s: Fs, c: Fs, g: Coordinate<Fb>) -> Self {
59 Self { pk, r, s, c, g }
60 }
61}
62
63// An ECDSA signature proof that we will use on the primary curve
64#[derive(Clone, Debug)]
65pub struct EcdsaCircuit<F>
66where
67 F: PrimeField<Repr = [u8; 32]>,
68{
69 pub z_r: Coordinate<F>,
70 pub z_g: Coordinate<F>,
71 pub z_pk: Coordinate<F>,
72 pub z_c: F,
73 pub z_s: F,
74 pub r: Coordinate<F>,
75 pub g: Coordinate<F>,
76 pub pk: Coordinate<F>,
77 pub c: F,
78 pub s: F,
79 pub c_bits: Vec<Choice>,
80 pub s_bits: Vec<Choice>,
81 pub pc: PoseidonConstants<F, U8>,
82}
83
84impl<F> EcdsaCircuit<F>
85where
86 F: PrimeField<Repr = [u8; 32]>,
87{
88 // Creates a new [`EcdsaCircuit<Fb, Fs>`]. The base and scalar field elements from the curve
89 // field used by the signature are converted to scalar field elements from the cyclic curve
90 // field used by the circuit.
91 pub fn new<Fb, Fs>(
92 num_steps: usize,
93 signatures: &[EcdsaSignature<Fb, Fs>],
94 pc: &PoseidonConstants<F, U8>,
95 ) -> (F, Vec<Self>)
96 where
97 Fb: PrimeField<Repr = [u8; 32]>,
98 Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
99 {
100 let mut z0 = F::zero();
101 let mut circuits = Vec::new();
102 for i in 0..num_steps {
103 let mut j = i;
104 if i > 0 {
105 j = i - 1
106 };
107 let z_signature = &signatures[j];
108 let z_r = Coordinate::new(
109 F::from_repr(z_signature.r.x.to_repr()).unwrap(),
110 F::from_repr(z_signature.r.y.to_repr()).unwrap(),
111 );
112
113 let z_g = Coordinate::new(
114 F::from_repr(z_signature.g.x.to_repr()).unwrap(),
115 F::from_repr(z_signature.g.y.to_repr()).unwrap(),
116 );
117
118 let z_pk = Coordinate::new(
119 F::from_repr(z_signature.pk.x.to_repr()).unwrap(),
120 F::from_repr(z_signature.pk.y.to_repr()).unwrap(),
121 );
122
123 let z_c = F::from_repr(z_signature.c.to_repr()).unwrap();
124 let z_s = F::from_repr(z_signature.s.to_repr()).unwrap();
125
126 let signature = &signatures[i];
127 let r = Coordinate::new(
128 F::from_repr(signature.r.x.to_repr()).unwrap(),
129 F::from_repr(signature.r.y.to_repr()).unwrap(),
130 );
131
132 let g = Coordinate::new(
133 F::from_repr(signature.g.x.to_repr()).unwrap(),
134 F::from_repr(signature.g.y.to_repr()).unwrap(),
135 );
136
137 let pk = Coordinate::new(
138 F::from_repr(signature.pk.x.to_repr()).unwrap(),
139 F::from_repr(signature.pk.y.to_repr()).unwrap(),
140 );
141
142 let c_bits = Self::to_le_bits(&signature.c);
143 let s_bits = Self::to_le_bits(&signature.s);
144 let c = F::from_repr(signature.c.to_repr()).unwrap();
145 let s = F::from_repr(signature.s.to_repr()).unwrap();
146
147 let circuit = EcdsaCircuit {
148 z_r,
149 z_g,
150 z_pk,
151 z_c,
152 z_s,
153 r,
154 g,
155 pk,
156 c,
157 s,
158 c_bits,
159 s_bits,
160 pc: pc.clone(),
161 };
162 circuits.push(circuit);
163
164 if i == 0 {
165 z0 =
166 Poseidon::<F, U8>::new_with_preimage(&[r.x, r.y, g.x, g.y, pk.x, pk.y, c, s], pc).hash();
167 }
168 }
169
170 (z0, circuits)
171 }
172
173 // Converts the scalar field element from the curve used by the signature to a bit represenation
174 // for later use in scalar multiplication using the cyclic curve used by the circuit.
175 fn to_le_bits<Fs>(fs: &Fs) -> Vec<Choice>
176 where
177 Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
178 {
179 let bits = fs
180 .to_repr()
181 .iter()
182 .flat_map(|byte| (0..8).map(move |i| Choice::from((byte >> i) & 1u8)))
183 .collect::<Vec<Choice>>();
184 bits
185 }
186
187 // Synthesize a bit representation into circuit gadgets.
188 fn synthesize_bits<CS: ConstraintSystem<F>>(
189 cs: &mut CS,
190 bits: &[Choice],
191 ) -> Result<Vec<AllocatedBit>, SynthesisError> {
192 let alloc_bits: Vec<AllocatedBit> = bits
193 .iter()
194 .enumerate()
195 .map(|(i, bit)| {
196 AllocatedBit::alloc(
197 cs.namespace(|| format!("bit {}", i)),
198 Some(bit.unwrap_u8() == 1u8),
199 )
200 })
201 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
202 .unwrap();
203 Ok(alloc_bits)
204 }
205}
206
207impl<F> StepCircuit<F> for EcdsaCircuit<F>
208where
209 F: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
210{
211 // Prove knowledge of the sk used to generate the Ecdsa signature (R,s)
212 // with public key PK and message commitment c.
213 // [s]G == R + [c]PK
214 fn synthesize<CS: ConstraintSystem<F>>(
215 &self,
216 cs: &mut CS,
217 z: AllocatedNum<F>,
218 ) -> Result<AllocatedNum<F>, SynthesisError> {
219 let z_rx = AllocatedNum::alloc(cs.namespace(|| "z_rx"), || Ok(self.z_r.x))?;
220 let z_ry = AllocatedNum::alloc(cs.namespace(|| "z_ry"), || Ok(self.z_r.y))?;
221 let z_gx = AllocatedNum::alloc(cs.namespace(|| "z_gx"), || Ok(self.z_g.x))?;
222 let z_gy = AllocatedNum::alloc(cs.namespace(|| "z_gy"), || Ok(self.z_g.y))?;
223 let z_pkx = AllocatedNum::alloc(cs.namespace(|| "z_pkx"), || Ok(self.z_pk.x))?;
224 let z_pky = AllocatedNum::alloc(cs.namespace(|| "z_pky"), || Ok(self.z_pk.y))?;
225 let z_c = AllocatedNum::alloc(cs.namespace(|| "z_c"), || Ok(self.z_c))?;
226 let z_s = AllocatedNum::alloc(cs.namespace(|| "z_s"), || Ok(self.z_s))?;
227
228 let z_hash = poseidon_hash(
229 cs.namespace(|| "input hash"),
230 vec![z_rx, z_ry, z_gx, z_gy, z_pkx, z_pky, z_c, z_s],
231 &self.pc,
232 )?;
233
234 cs.enforce(
235 || "z == z1",
236 |lc| lc + z.get_variable(),
237 |lc| lc + CS::one(),
238 |lc| lc + z_hash.get_variable(),
239 );
240
241 let g = AllocatedPoint::alloc(
242 cs.namespace(|| "G"),
243 Some((self.g.x, self.g.y, self.g.is_infinity)),
244 )?;
245 let s_bits = Self::synthesize_bits(&mut cs.namespace(|| "s_bits"), &self.s_bits)?;
246 let sg = g.scalar_mul(cs.namespace(|| "[s]G"), s_bits)?;
247 let r = AllocatedPoint::alloc(
248 cs.namespace(|| "R"),
249 Some((self.r.x, self.r.y, self.r.is_infinity)),
250 )?;
251 let c_bits = Self::synthesize_bits(&mut cs.namespace(|| "c_bits"), &self.c_bits)?;
252 let pk = AllocatedPoint::alloc(
253 cs.namespace(|| "PK"),
254 Some((self.pk.x, self.pk.y, self.pk.is_infinity)),
255 )?;
256 let cpk = pk.scalar_mul(&mut cs.namespace(|| "[c]PK"), c_bits)?;
257 let rcpk = cpk.add(&mut cs.namespace(|| "R + [c]PK"), &r)?;
258
259 let (rcpk_x, rcpk_y, _) = rcpk.get_coordinates();
260 let (sg_x, sg_y, _) = sg.get_coordinates();
261
262 cs.enforce(
263 || "sg_x == rcpk_x",
264 |lc| lc + sg_x.get_variable(),
265 |lc| lc + CS::one(),
266 |lc| lc + rcpk_x.get_variable(),
267 );
268
269 cs.enforce(
270 || "sg_y == rcpk_y",
271 |lc| lc + sg_y.get_variable(),
272 |lc| lc + CS::one(),
273 |lc| lc + rcpk_y.get_variable(),
274 );
275
276 let rx = AllocatedNum::alloc(cs.namespace(|| "rx"), || Ok(self.r.x))?;
277 let ry = AllocatedNum::alloc(cs.namespace(|| "ry"), || Ok(self.r.y))?;
278 let gx = AllocatedNum::alloc(cs.namespace(|| "gx"), || Ok(self.g.x))?;
279 let gy = AllocatedNum::alloc(cs.namespace(|| "gy"), || Ok(self.g.y))?;
280 let pkx = AllocatedNum::alloc(cs.namespace(|| "pkx"), || Ok(self.pk.x))?;
281 let pky = AllocatedNum::alloc(cs.namespace(|| "pky"), || Ok(self.pk.y))?;
282 let c = AllocatedNum::alloc(cs.namespace(|| "c"), || Ok(self.c))?;
283 let s = AllocatedNum::alloc(cs.namespace(|| "s"), || Ok(self.s))?;
284
285 poseidon_hash(
286 cs.namespace(|| "output hash"),
287 vec![rx, ry, gx, gy, pkx, pky, c, s],
288 &self.pc,
289 )
290 }
291
292 fn output(&self, z: &F) -> F {
293 let z_hash = Poseidon::<F, U8>::new_with_preimage(
294 &[
295 self.z_r.x,
296 self.z_r.y,
297 self.z_g.x,
298 self.z_g.y,
299 self.z_pk.x,
300 self.z_pk.y,
301 self.z_c,
302 self.z_s,
303 ],
304 &self.pc,
305 )
306 .hash();
307 debug_assert_eq!(z, &z_hash);
308
309 Poseidon::<F, U8>::new_with_preimage(
310 &[
311 self.r.x, self.r.y, self.g.x, self.g.y, self.pk.x, self.pk.y, self.c, self.s,
312 ],
313 &self.pc,
314 )
315 .hash()
316 }
317}