1use std::ops::Neg;
2
3use crate::proofs::{
4 field::{field, FieldWitness},
5 witness::Witness,
6};
7
8pub mod bw19 {
9 use super::*;
10
11 struct Spec<F: FieldWitness> {
12 b: F,
13 }
14
15 #[derive(Clone, Copy)]
16 pub struct Params<F: FieldWitness> {
17 u: F,
18 fu: F,
19 sqrt_neg_three_u_squared_minus_u_over_2: F,
20 sqrt_neg_three_u_squared: F,
21 inv_three_u_squared: F,
22 b: F,
23 }
24
25 impl<F: FieldWitness> Params<F> {
26 fn create_impl() -> Self {
27 let b = F::PARAMS.b;
28
29 fn first_map<F: FieldWitness, T>(f: impl Fn(F) -> Option<T>) -> T {
30 let mut v = F::zero();
31 let one = F::one();
32 loop {
33 match f(v) {
34 Some(x) => return x,
35 None => v += one,
36 }
37 }
38 }
39
40 let curve_eqn = |u: F| (u * u * u) + b;
41
42 let (u, fu) = first_map(|u| {
43 let fu = curve_eqn(u);
44 if u.is_zero() || fu.is_zero() {
45 None
46 } else {
47 Some((u, fu))
48 }
49 });
50
51 let three_u_squared = u * u * F::from(3);
52 let sqrt_neg_three_u_squared = three_u_squared.neg().sqrt().unwrap();
53
54 Self {
55 u,
56 fu,
57 sqrt_neg_three_u_squared_minus_u_over_2: (sqrt_neg_three_u_squared - u)
58 / F::from(2),
59 sqrt_neg_three_u_squared,
60 inv_three_u_squared: F::one() / three_u_squared,
61 b,
62 }
63 }
64
65 pub fn create() -> Self {
66 cache!(Self, Self::create_impl())
67 }
68 }
69
70 pub fn potential_xs<F: FieldWitness>(
71 t: F,
72 params: &Params<F>,
73 w: &mut Witness<F>,
74 ) -> (F, F, F) {
75 let square = |x: F, w: &mut Witness<F>| field::mul(x, x, w);
76
77 let t2 = field::mul(t, t, w);
78 let alpha = {
79 let alpha_inv = field::mul(t2 + params.fu, t2, w);
80 field::div(F::one(), alpha_inv, w)
81 };
82 let x1 = {
83 let t2_squared = square(t2, w);
84 let temp = field::mul(t2_squared, alpha, w) * params.sqrt_neg_three_u_squared;
85 params.sqrt_neg_three_u_squared_minus_u_over_2 - temp
86 };
87 let x2 = params.u.neg() - x1;
88 let x3 = {
89 let t2_plus_fu = t2 + params.fu;
90 let t2_inv = field::mul(alpha, t2_plus_fu, w);
91 let temp = {
92 let t2_plus_fu_squared = square(t2_plus_fu, w);
93 field::mul(t2_plus_fu_squared, t2_inv, w) * params.inv_three_u_squared
94 };
95 params.u - temp
96 };
97 (x1, x2, x3)
98 }
99}
100
101use ark_ff::{FpParameters, One};
102use mina_curves::pasta::Fp;
103
104use self::tock::Conic;
105
106use super::{
107 field::{Boolean, GroupAffine, ToBoolean},
108 transaction::make_group,
109};
110
111fn sqrt_exn<F: FieldWitness>(x: F, w: &mut Witness<F>) -> F {
112 w.exists(x.sqrt().unwrap())
113}
114
115fn is_square<F: FieldWitness>(x: F) -> bool {
116 use ark_ff::BigInteger;
117
118 let modulus_minus_one_div_two = F::Params::MODULUS_MINUS_ONE_DIV_TWO.to_64x4();
119 let s = x.pow(modulus_minus_one_div_two);
120 s.is_zero() || s.is_one()
121}
122
123fn sqrt_flagged<F: FieldWitness>(x: F, w: &mut Witness<F>) -> (F, Boolean) {
124 let is_square = w.exists(is_square(x).to_boolean());
125 let m = non_residue::<F>();
126 let v = w.exists_no_check(match is_square {
127 Boolean::True => x,
128 Boolean::False => x * m,
129 });
130 (sqrt_exn(v, w), is_square)
131}
132
133fn non_residue<F: FieldWitness>() -> F {
134 cache!(F, {
135 let mut i = F::from(2);
136 let one = F::one();
137 loop {
138 if !is_square(i) {
139 break i;
140 } else {
141 i += one;
142 }
143 }
144 })
145}
146
147pub fn bw19_wrap<F: FieldWitness>(
148 x: F,
149 params: &bw19::Params<F>,
150 w: &mut Witness<F>,
151) -> GroupAffine<F> {
152 let potential_xs = bw19::potential_xs(x, params, w);
153 wrap(potential_xs, w)
154}
155
156pub fn wrap<F: FieldWitness>(potential_xs: (F, F, F), w: &mut Witness<F>) -> GroupAffine<F> {
157 let y_squared =
158 |x: F, w: &mut Witness<F>| field::muls(&[x, x, x], w) + (F::PARAMS.a * x) + F::PARAMS.b;
159
160 let (x1, x2, x3) = potential_xs;
161
162 let (y1, b1) = sqrt_flagged(y_squared(x1, w), w);
163 let (y2, b2) = sqrt_flagged(y_squared(x2, w), w);
164 let (y3, b3) = sqrt_flagged(y_squared(x3, w), w);
165
166 Boolean::assert_any(&[b1, b2, b3], w);
167
168 let x1_is_first = b1.to_field::<F>();
169 let x2_is_first = (b1.neg().and(&b2, w)).to_field::<F>();
170 let x3_is_first = (b1.neg().and(&b2.neg(), w).and(&b3, w)).to_field::<F>();
171
172 let x3_is_first_y3 = field::mul(x3_is_first, y3, w);
174 let x2_is_first_y2 = field::mul(x2_is_first, y2, w);
175 let x1_is_first_y1 = field::mul(x1_is_first, y1, w);
176 let x3_is_first_x3 = field::mul(x3_is_first, x3, w);
177 let x2_is_first_x2 = field::mul(x2_is_first, x2, w);
178 let x1_is_first_x1 = field::mul(x1_is_first, x1, w);
179
180 let (x, y) = (
181 (x1_is_first_x1 + x2_is_first_x2 + x3_is_first_x3),
182 (x1_is_first_y1 + x2_is_first_y2 + x3_is_first_y3),
183 );
184 make_group(x, y)
185}
186
187mod tock {
188 use super::*;
189
190 use ark_ff::{SquareRootField, Zero};
191
192 #[derive(Clone, Debug)]
194 pub struct S<F: FieldWitness> {
195 pub u: F,
196 pub v: F,
197 pub y: F,
198 }
199
200 #[derive(Clone, Debug)]
201 pub struct Conic<F: FieldWitness> {
202 pub z: F,
203 pub y: F,
204 }
205
206 #[derive(Clone, Debug)]
207 pub struct Spec<F> {
208 pub a: F,
209 pub b: F,
210 }
211
212 #[derive(Clone, Debug)]
213 pub struct Params<F: FieldWitness> {
214 pub u: F,
215 pub u_over_2: F,
216 pub projection_point: Conic<F>,
217 pub conic_c: F,
218 pub spec: Spec<F>,
219 }
220
221 fn tock_params_impl() -> Params<Fp> {
222 let a = Fp::PARAMS.a;
223 let b = Fp::PARAMS.b;
224
225 fn first_map<F: FieldWitness, T>(f: impl Fn(F) -> Option<T>) -> T {
226 let mut v = F::zero();
227 let one = F::one();
228 loop {
229 match f(v) {
230 Some(x) => return x,
231 None => v += one,
232 }
233 }
234 }
235
236 fn first<F: FieldWitness>(f: impl Fn(F) -> bool) -> F {
237 first_map(|x| match f(x) {
238 true => Some(x),
239 false => None,
240 })
241 }
242
243 let three_fourths = Fp::from(3) / Fp::from(4);
244 let curve_eqn = |u: Fp| (u * u * u) + (a * u) + b;
245
246 let u = first(|u: Fp| {
247 let check = (three_fourths * u * u) + a;
248 let fu = curve_eqn(u);
249
250 !(check.is_zero()) && !(fu.is_zero()) && !(is_square(fu.neg()))
251 });
252
253 let conic_c = (three_fourths * u * u) + a;
254 let conic_d = curve_eqn(u).neg();
255
256 let projection_point = first_map(|y: Fp| {
257 let z2 = conic_d - (conic_c * y * y);
258
259 if is_square(z2) {
260 Some(Conic {
261 z: z2.sqrt().unwrap(),
262 y,
263 })
264 } else {
265 None
266 }
267 });
268
269 Params {
270 u,
271 u_over_2: u / Fp::from(2),
272 projection_point,
273 conic_c,
274 spec: Spec { a, b },
275 }
276 }
277
278 pub fn params() -> Params<Fp> {
279 cache_one!(Params<Fp>, { tock_params_impl() })
280 }
281}
282
283fn field_to_conic(t: Fp, params: &tock::Params<Fp>, w: &mut Witness<Fp>) -> tock::Conic<Fp> {
284 let tock::Conic { z: z0, y: y0 } = params.projection_point;
285
286 let one = Fp::one();
287
288 let ct = params.conic_c * t;
289 let s = field::div_by_inv(
290 Fp::from(2) * ((ct * y0) + z0),
291 field::mul(ct, t, w) + one,
292 w,
293 );
294
295 tock::Conic {
296 z: z0 - s,
297 y: y0 - field::mul(s, t, w),
298 }
299}
300
301fn conic_to_s(p: Conic<Fp>, params: &tock::Params<Fp>, w: &mut Witness<Fp>) -> tock::S<Fp> {
302 let Conic { z, y } = p;
303 let u = params.u;
304 let v = field::div_by_inv(z, y, w) - params.u_over_2;
305 tock::S { u, v, y }
306}
307
308fn s_to_v_truncated(s: tock::S<Fp>, w: &mut Witness<Fp>) -> (Fp, Fp, Fp) {
309 let tock::S { u, v, y } = s;
310
311 (v, (u + v).neg(), u + field::mul(y, y, w))
312}
313
314pub fn to_group(t: Fp, w: &mut Witness<Fp>) -> GroupAffine<Fp> {
315 let params = tock::params();
316
317 let potential_xs = {
318 let conic = field_to_conic(t, ¶ms, w);
319 let s = conic_to_s(conic, ¶ms, w);
320 s_to_v_truncated(s, w)
321 };
322
323 wrap(potential_xs, w)
324}