fawkes_crypto/circuit/
ecc.rs

1// Assuming JubJub curves with cofactor=8 only
2
3use crate::{
4    circuit::{bool::CBool, cs::{CS, RCS}, mux::c_mux3, num::CNum},
5    core::signal::Signal,
6    ff_uint::Num,
7    native::ecc::{EdwardsPoint, EdwardsPointEx, JubJubParams, MontgomeryPoint},
8};
9
10#[derive(Clone, Signal)]
11#[Value = "EdwardsPoint<C::Fr>"]
12pub struct CEdwardsPoint<C: CS> {
13    pub x: CNum<C>,
14    pub y: CNum<C>,
15}
16
17#[derive(Clone, Signal)]
18#[Value = "MontgomeryPoint<C::Fr>"]
19pub struct CMontgomeryPoint<C: CS> {
20    pub x: CNum<C>,
21    pub y: CNum<C>,
22}
23
24impl<C: CS> CEdwardsPoint<C> {
25    pub fn double<J: JubJubParams<Fr = C::Fr>>(&self, params: &J) -> Self {
26        let v = &self.x * &self.y;
27        let v2 = v.square();
28        let u = (&self.x + &self.y).square();
29        Self {
30            x: (&v * Num::from(2)).div_unchecked(&(Num::ONE + params.edwards_d() * &v2)),
31            y: (&u - &v * Num::from(2)).div_unchecked(&(Num::ONE - params.edwards_d() * &v2)),
32        }
33    }
34
35    pub fn mul_by_cofactor<J: JubJubParams<Fr = C::Fr>>(&self, params: &J) -> Self {
36        self.double(params).double(params).double(params)
37    }
38
39    pub fn add<J: JubJubParams<Fr = C::Fr>>(&self, p: &Self, params: &J) -> Self {
40        let v1 = &self.x * &p.y;
41        let v2 = &p.x * &self.y;
42        let v12 = &v1 * &v2;
43        let u = (&self.x + &self.y) * (&p.x + &p.y);
44        Self {
45            x: (&v1 + &v2).div_unchecked(&(Num::ONE + params.edwards_d() * &v12)),
46            y: (&u - &v1 - &v2).div_unchecked(&(Num::ONE - params.edwards_d() * &v12)),
47        }
48    }
49
50    pub fn assert_in_curve<J: JubJubParams<Fr = C::Fr>>(&self, params: &J) {
51        let x2 = self.x.square();
52        let y2 = self.y.square();
53
54        (params.edwards_d() * &x2 * &y2).assert_eq(&(&y2 - &x2 - Num::ONE));
55    }
56
57    pub fn assert_in_subgroup<J: JubJubParams<Fr = C::Fr>>(&self, params: &J) {
58        let preimage_value = self
59            .get_value()
60            .map(|p| p.mul(Num::from(8).checked_inv().unwrap(), params));
61        let preimage = self.derive_alloc::<Self>(preimage_value.as_ref());
62        preimage.assert_in_curve(params);
63        let preimage8 = preimage.mul_by_cofactor(params);
64
65        (&self.x - &preimage8.x).assert_zero();
66        (&self.y - &preimage8.y).assert_zero();
67    }
68
69    pub fn subgroup_decompress<J: JubJubParams<Fr = C::Fr>>(x: &CNum<C>, params: &J) -> Self {
70        let preimage_value = x.get_value().map(|x| {
71            EdwardsPoint::subgroup_decompress(x, params)
72                .unwrap_or(params.edwards_g().clone())
73                .mul(Num::from(8).checked_inv().unwrap(), params)
74        });
75        let preimage = CEdwardsPoint::alloc(x.get_cs(), preimage_value.as_ref());
76        preimage.assert_in_curve(params);
77        let preimage8 = preimage.mul_by_cofactor(params);
78        (x - &preimage8.x).assert_zero();
79        preimage8
80    }
81
82    // assume nonzero subgroup point
83    pub fn into_montgomery(&self) -> CMontgomeryPoint<C> {
84        let x = (Num::ONE + &self.y).div_unchecked(&(Num::ONE - &self.y));
85        let y = x.div_unchecked(&self.x);
86        CMontgomeryPoint { x, y }
87    }
88
89    // assume subgroup point, bits
90    pub fn mul<J: JubJubParams<Fr = C::Fr>>(&self, bits: &[CBool<C>], params: &J) -> Self {
91        fn gen_table<C: CS, J: JubJubParams<Fr = C::Fr>>(
92            p: &EdwardsPointEx<C::Fr>,
93            params: &J,
94        ) -> Vec<Vec<Num<C::Fr>>> {
95            let mut x_col = vec![];
96            let mut y_col = vec![];
97            let mut q = p.clone();
98            for _ in 0..8 {
99                let MontgomeryPoint { x, y } = q.into_montgomery().unwrap();
100                x_col.push(x);
101                y_col.push(y);
102                q = q.add(&p, params);
103            }
104            vec![x_col, y_col]
105        }
106        let cs = self.get_cs();
107
108        match self.as_const() {
109            Some(c_base) => {
110                let c_base = c_base.into_extended();
111                let mut base = c_base;
112                if base.is_zero() {
113                    self.derive_const(&EdwardsPoint::zero())
114                } else {
115                    let bits_len = bits.len();
116                    let zeros_len = (2 * bits_len) % 3;
117                    let zero_bits = vec![CBool::from_const(cs, &false); zeros_len];
118                    let all_bits = [bits, &zero_bits].concat();
119
120                    let all_bits_len = all_bits.len();
121                    let nwindows = all_bits_len / 3;
122
123                    let mut acc = EdwardsPoint {
124                        x: Num::ZERO,
125                        y: -Num::ONE,
126                    }
127                    .into_extended();
128
129                    for _ in 0..nwindows {
130                        acc = acc.add(&base, params);
131                        base = base.double().double().double();
132                    }
133
134                    let mp = acc.negate().into_montgomery().unwrap();
135
136                    let mut acc = CMontgomeryPoint::from_const(cs, &mp);
137                    let mut base = c_base;
138
139                    for i in 0..nwindows {
140                        let table = gen_table::<C, J>(&base, params);
141                        let res = c_mux3(&all_bits[3 * i..3 * (i + 1)], &table);
142                        let p = CMontgomeryPoint {
143                            x: res[0].clone(),
144                            y: res[1].clone(),
145                        };
146                        acc = acc.add(&p, params);
147                        base = base.double().double().double();
148                    }
149
150                    let res = acc.into_edwards();
151                    CEdwardsPoint {
152                        x: -res.x,
153                        y: -res.y,
154                    }
155                }
156            }
157            _ => {
158                let base_is_zero = self.x.is_zero();
159                let dummy_point = CEdwardsPoint::from_const(cs, params.edwards_g());
160                let base_point = dummy_point.switch(&base_is_zero, self);
161
162                let mut base_point = base_point.into_montgomery();
163
164                let mut exponents = vec![base_point.clone()];
165
166                for _ in 1..bits.len() {
167                    base_point = base_point.double(params);
168                    exponents.push(base_point.clone());
169                }
170
171                let empty_acc = CMontgomeryPoint {
172                    x: CNum::from_const(cs, &Num::ZERO),
173                    y: CNum::from_const(cs, &Num::ZERO),
174                };
175                let mut acc = empty_acc.clone();
176
177                for i in 0..bits.len() {
178                    let inc_acc = acc.add(&exponents[i], params);
179                    acc = inc_acc.switch(&bits[i], &acc);
180                }
181
182                acc = empty_acc.switch(&base_is_zero, &acc);
183
184                let res = acc.into_edwards();
185                CEdwardsPoint {
186                    x: -res.x,
187                    y: -res.y,
188                }
189            }
190        }
191    }
192
193    // assuming t!=-0
194    pub fn from_scalar<J: JubJubParams<Fr = C::Fr>>(t: &CNum<C>, params: &J) -> Self {
195        fn check_and_get_y<C: CS, J: JubJubParams<Fr = C::Fr>>(
196            x: &CNum<C>,
197            t: &CNum<C>,
198            params: &J,
199        ) -> (CBool<C>, CNum<C>) {
200            let g = (x.square() * (x + params.montgomery_a()) + x) / params.montgomery_b();
201
202            let y_value = g.get_value().map(|g| {
203                let _y = match g.sqrt() {
204                    Some(g_sqrt) => g_sqrt,
205                    _ => (g * params.montgomery_u()).sqrt().unwrap(),
206                };
207                let _t = t.get_value().unwrap();
208                if (_y*_t).is_even() {
209                    _y
210                } else {
211                    -_y
212                }
213            });
214
215
216            let y:CNum<C> = x.derive_alloc(y_value.as_ref());
217
218            (&y*t).assert_even();
219
220
221            let y2 = y.square();
222
223            let is_square = (&g - &y2).is_zero();
224            let isnot_square = (&g * params.montgomery_u() - &y2).is_zero();
225
226            (&is_square ^ &isnot_square).assert_const(&true);
227            (is_square, y)
228        }
229
230        let t2g1 = t.square() * params.montgomery_u();
231
232        let x3 = -Num::ONE / params.montgomery_a() * (&t2g1 + Num::ONE);
233        let x2 = x3.div_unchecked(&t2g1);
234
235        let (is_valid, y2) = check_and_get_y(&x2, &t, params);
236        let (_, y3) = check_and_get_y(&x3, &t, params);
237
238        let x = x2.switch(&is_valid, &x3);
239        let y = y2.switch(&is_valid, &y3);
240
241        CMontgomeryPoint { x, y }
242            .into_edwards()
243            .mul_by_cofactor(params)
244    }
245}
246
247impl<C: CS> CMontgomeryPoint<C> {
248    // assume self != (0, 0)
249    pub fn double<J: JubJubParams<Fr = C::Fr>>(&self, params: &J) -> Self {
250        let x2 = self.x.square();
251        let l = (Num::from(3) * &x2 + Num::from(2) * params.montgomery_a() * &self.x + Num::ONE)
252            .div_unchecked(&(Num::from(2) * params.montgomery_b() * &self.y));
253        let b_l2 = params.montgomery_b() * &l.square();
254        let a = params.montgomery_a();
255
256        Self {
257            x: &b_l2 - &a - Num::from(2) * &self.x,
258            y: l * (Num::from(3) * &self.x + a - &b_l2) - &self.y,
259        }
260    }
261
262    // assume self != p
263    pub fn add<J: JubJubParams<Fr = C::Fr>>(&self, p: &Self, params: &J) -> Self {
264        let l = (&p.y - &self.y).div_unchecked(&(&p.x - &self.x));
265        let b_l2 = params.montgomery_b() * &l.square();
266        let a = params.montgomery_a();
267
268        Self {
269            x: &b_l2 - &a - &self.x - &p.x,
270            y: l * (Num::from(2) * &self.x + &p.x + a - &b_l2) - &self.y,
271        }
272    }
273
274    // assume any nonzero point
275    pub fn into_edwards(&self) -> CEdwardsPoint<C> {
276        let y_is_zero = self.y.is_zero();
277        CEdwardsPoint {
278            x: self.x.div_unchecked(&(&self.y + y_is_zero.to_num())),
279            y: (&self.x - Num::ONE).div_unchecked(&(&self.x + Num::ONE)),
280        }
281    }
282}
283
fawkes_crypto/circuit/ecc.rs

fawkes_crypto/circuit/
ecc.rs
