1use bellperson::{
  2  gadgets::{boolean::AllocatedBit, num::AllocatedNum},
  3  ConstraintSystem, SynthesisError,
  4};
  5use ff::{PrimeField, PrimeFieldBits};
  6use nova_snark::{gadgets::ecc::AllocatedPoint, traits::circuit::StepCircuit};
  7use subtle::Choice;
  8
  9// An affine point coordinate that is on the curve.
 10#[derive(Clone, Copy, Debug)]
 11pub struct Coordinate<F>
 12where
 13  F: PrimeField<Repr = [u8; 32]>,
 14{
 15  pub x: F,
 16  pub y: F,
 17  pub is_infinity: bool,
 18}
 19
 20impl<F> Coordinate<F>
 21where
 22  F: PrimeField<Repr = [u8; 32]>,
 23{
 24  // New affine point coordiante on the curve so is_infinity = false.
 25  pub fn new(x: F, y: F) -> Self {
 26    Self {
 27      x,
 28      y,
 29      is_infinity: false,
 30    }
 31  }
 32}
 33
 34// An ECDSA signature
 35#[derive(Clone, Debug)]
 36pub struct EcdsaSignature<Fb, Fs>
 37where
 38  Fb: PrimeField<Repr = [u8; 32]>,
 39  Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
 40{
 41  pk: Coordinate<Fb>, // public key
 42  r: Coordinate<Fb>,  // (r, s) is the ECDSA signature
 43  s: Fs,
 44  c: Fs,             // hash of the message
 45  g: Coordinate<Fb>, // generator of the group; could be omitted if Nova's traits allow accessing the generator
 46}
 47
 48impl<Fb, Fs> EcdsaSignature<Fb, Fs>
 49where
 50  Fb: PrimeField<Repr = [u8; 32]>,
 51  Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
 52{
 53  pub fn new(pk: Coordinate<Fb>, r: Coordinate<Fb>, s: Fs, c: Fs, g: Coordinate<Fb>) -> Self {
 54    Self { pk, r, s, c, g }
 55  }
 56}
 57
 58// An ECDSA signature proof that we will use on the primary curve
 59#[derive(Clone, Debug)]
 60pub struct EcdsaCircuit<F>
 61where
 62  F: PrimeField<Repr = [u8; 32]>,
 63{
 64  pub r: Coordinate<F>,
 65  pub g: Coordinate<F>,
 66  pub pk: Coordinate<F>,
 67  pub c: F,
 68  pub s: F,
 69  pub c_bits: Vec<Choice>,
 70  pub s_bits: Vec<Choice>,
 71}
 72
 73impl<F> EcdsaCircuit<F>
 74where
 75  F: PrimeField<Repr = [u8; 32]>,
 76{
 77  // Creates a new [`EcdsaCircuit<Fb, Fs>`]. The base and scalar field elements from the curve
 78  // field used by the signature are converted to scalar field elements from the cyclic curve
 79  // field used by the circuit.
 80  pub fn new<Fb, Fs>(num_steps: usize, signatures: &[EcdsaSignature<Fb, Fs>]) -> (Vec<F>, Vec<Self>)
 81  where
 82    Fb: PrimeField<Repr = [u8; 32]>,
 83    Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
 84  {
 85    let mut z0 = Vec::new();
 86    let mut circuits = Vec::new();
 87    for (i, signature) in signatures.iter().enumerate().take(num_steps) {
 88      let r = Coordinate::new(
 89        F::from_repr(signature.r.x.to_repr()).unwrap(),
 90        F::from_repr(signature.r.y.to_repr()).unwrap(),
 91      );
 92
 93      let g = Coordinate::new(
 94        F::from_repr(signature.g.x.to_repr()).unwrap(),
 95        F::from_repr(signature.g.y.to_repr()).unwrap(),
 96      );
 97
 98      let pk = Coordinate::new(
 99        F::from_repr(signature.pk.x.to_repr()).unwrap(),
100        F::from_repr(signature.pk.y.to_repr()).unwrap(),
101      );
102
103      let c_bits = Self::to_le_bits(&signature.c);
104      let s_bits = Self::to_le_bits(&signature.s);
105      let c = F::from_repr(signature.c.to_repr()).unwrap();
106      let s = F::from_repr(signature.s.to_repr()).unwrap();
107
108      let circuit = EcdsaCircuit {
109        r,
110        g,
111        pk,
112        c,
113        s,
114        c_bits,
115        s_bits,
116      };
117      circuits.push(circuit);
118
119      if i == 0 {
120        z0 = vec![r.x, r.y, g.x, g.y, pk.x, pk.y, c, s];
121      }
122    }
123
124    (z0, circuits)
125  }
126
127  // Converts the scalar field element from the curve used by the signature to a bit represenation
128  // for later use in scalar multiplication using the cyclic curve used by the circuit.
129  fn to_le_bits<Fs>(fs: &Fs) -> Vec<Choice>
130  where
131    Fs: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
132  {
133    let bits = fs
134      .to_repr()
135      .iter()
136      .flat_map(|byte| (0..8).map(move |i| Choice::from((byte >> i) & 1u8)))
137      .collect::<Vec<Choice>>();
138    bits
139  }
140
141  // Synthesize a bit representation into circuit gadgets.
142  fn synthesize_bits<CS: ConstraintSystem<F>>(
143    cs: &mut CS,
144    bits: &[Choice],
145  ) -> Result<Vec<AllocatedBit>, SynthesisError> {
146    let alloc_bits: Vec<AllocatedBit> = bits
147      .iter()
148      .enumerate()
149      .map(|(i, bit)| {
150        AllocatedBit::alloc(
151          cs.namespace(|| format!("bit {}", i)),
152          Some(bit.unwrap_u8() == 1u8),
153        )
154      })
155      .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
156      .unwrap();
157    Ok(alloc_bits)
158  }
159}
160
161impl<F> StepCircuit<F> for EcdsaCircuit<F>
162where
163  F: PrimeField<Repr = [u8; 32]> + PrimeFieldBits,
164{
165  fn arity(&self) -> usize {
166    8
167  }
168
169  // Prove knowledge of the sk used to generate the Ecdsa signature (R,s)
170  // with public key PK and message commitment c.
171  // [s]G == R + [c]PK
172  fn synthesize<CS: ConstraintSystem<F>>(
173    &self,
174    cs: &mut CS,
175    _z: &[AllocatedNum<F>],
176  ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
177    let g = AllocatedPoint::alloc(
178      cs.namespace(|| "G"),
179      Some((self.g.x, self.g.y, self.g.is_infinity)),
180    )?;
181    let s_bits = Self::synthesize_bits(&mut cs.namespace(|| "s_bits"), &self.s_bits)?;
182    let sg = g.scalar_mul(cs.namespace(|| "[s]G"), s_bits)?;
183    let r = AllocatedPoint::alloc(
184      cs.namespace(|| "R"),
185      Some((self.r.x, self.r.y, self.r.is_infinity)),
186    )?;
187    let c_bits = Self::synthesize_bits(&mut cs.namespace(|| "c_bits"), &self.c_bits)?;
188    let pk = AllocatedPoint::alloc(
189      cs.namespace(|| "PK"),
190      Some((self.pk.x, self.pk.y, self.pk.is_infinity)),
191    )?;
192    let cpk = pk.scalar_mul(&mut cs.namespace(|| "[c]PK"), c_bits)?;
193    let rcpk = cpk.add(&mut cs.namespace(|| "R + [c]PK"), &r)?;
194
195    let (rcpk_x, rcpk_y, _) = rcpk.get_coordinates();
196    let (sg_x, sg_y, _) = sg.get_coordinates();
197
198    cs.enforce(
199      || "sg_x == rcpk_x",
200      |lc| lc + sg_x.get_variable(),
201      |lc| lc + CS::one(),
202      |lc| lc + rcpk_x.get_variable(),
203    );
204
205    cs.enforce(
206      || "sg_y == rcpk_y",
207      |lc| lc + sg_y.get_variable(),
208      |lc| lc + CS::one(),
209      |lc| lc + rcpk_y.get_variable(),
210    );
211
212    let rx = AllocatedNum::alloc(cs.namespace(|| "rx"), || Ok(self.r.x))?;
213    let ry = AllocatedNum::alloc(cs.namespace(|| "ry"), || Ok(self.r.y))?;
214    let gx = AllocatedNum::alloc(cs.namespace(|| "gx"), || Ok(self.g.x))?;
215    let gy = AllocatedNum::alloc(cs.namespace(|| "gy"), || Ok(self.g.y))?;
216    let pkx = AllocatedNum::alloc(cs.namespace(|| "pkx"), || Ok(self.pk.x))?;
217    let pky = AllocatedNum::alloc(cs.namespace(|| "pky"), || Ok(self.pk.y))?;
218    let c = AllocatedNum::alloc(cs.namespace(|| "c"), || Ok(self.c))?;
219    let s = AllocatedNum::alloc(cs.namespace(|| "s"), || Ok(self.s))?;
220
221    Ok(vec![rx, ry, gx, gy, pkx, pky, c, s])
222  }
223
224  fn output(&self, _z: &[F]) -> Vec<F> {
225    vec![
226      self.r.x, self.r.y, self.g.x, self.g.y, self.pk.x, self.pk.y, self.c, self.s,
227    ]
228  }
229}