groupmap/
lib.rs

1//! Follows approach of `SvdW06` to construct a "near injection" from a field
2//! into an elliptic curve defined over that field. WB19 is also a useful
3//! reference that details several constructions which are more appropriate in other
4//! contexts.
5//!
6//! Fix an elliptic curve E given by y^2 = x^3 + ax + b over a field "F"
7//!   Let f(x) = x^3 + ax + b.
8//!
9//! Define the variety V to be
10//!   (x1, x2, x3, x4) : f(x1) f(x2) f(x3) = x4^2.
11//!
12//! By a not-too-hard we have a map `V -> E`. Thus, a map of type `F -> V` yields a
13//! map of type `F -> E` by composing.
14//! Our goal is to construct such a map of type `F -> V`. The paper `SvdW06` constructs
15//! a family of such maps, defined by a collection of values which we'll term `params`.
16//!
17//! OCaml implementation <https://github.com/o1-labs/snarky/blob/2e9013159ad0d1df0af681735b89518befc4be11/group_map/group_map.ml#L4>
18//! `SvdW06`: Shallue and van de Woestijne, "Construction of rational points on elliptic curves over finite fields." Proc. ANTS 2006. <https://works.bepress.com/andrew_shallue/1/download/>
19//! WB19: Riad S. Wahby and Dan Boneh, Fast and simple constant-time hashing to the BLS12-381 elliptic curve. <https://eprint.iacr.org/2019/403>
20//!
21
22#![no_std]
23#![deny(unsafe_code)]
24#![deny(clippy::all)]
25#![deny(clippy::pedantic)]
26#![deny(clippy::nursery)]
27
28extern crate alloc;
29
30use alloc::vec::Vec;
31use ark_ec::short_weierstrass::SWCurveConfig;
32use ark_ff::{Field, One, Zero};
33
34pub trait GroupMap<F> {
35    fn setup() -> Self;
36    fn to_group(&self, u: F) -> (F, F);
37    fn batch_to_group_x(&self, ts: Vec<F>) -> Vec<[F; 3]>;
38}
39
40#[derive(Clone, Copy)]
41pub struct BWParameters<G: SWCurveConfig> {
42    pub u: G::BaseField,
43    pub fu: G::BaseField,
44    pub sqrt_neg_three_u_squared_minus_u_over_2: G::BaseField,
45    pub sqrt_neg_three_u_squared: G::BaseField,
46    pub inv_three_u_squared: G::BaseField,
47}
48
49/// returns the right-hand side of the Short Weierstrass curve equation for a given x
50fn curve_eqn<G: SWCurveConfig>(x: G::BaseField) -> G::BaseField {
51    let mut res = x;
52    res *= &x; // x^2
53    res += &G::COEFF_A; // x^2 + A
54    res *= &x; // x^3 + A x
55    res += &G::COEFF_B; // x^3 + A x + B
56
57    res
58}
59
60/// finds i for i=start, start+1, ... s.t. f(i) is a valid field
61fn find_first<A, K: Field, F: Fn(K) -> Option<A>>(start: K, f: F) -> A {
62    let mut i = start;
63    loop {
64        match f(i) {
65            Some(x) => return x,
66            None => {
67                i += K::one();
68            }
69        }
70    }
71}
72
73/// ?
74fn potential_xs_helper<G: SWCurveConfig>(
75    params: &BWParameters<G>,
76    t2: G::BaseField,
77    alpha: G::BaseField,
78) -> [G::BaseField; 3] {
79    let x1 = {
80        let mut temp = t2;
81        temp.square_in_place(); // t2^2
82        temp *= &alpha; // t2^2 * alpha
83        temp *= &params.sqrt_neg_three_u_squared; // t2^2 * alpha * sqrt(-3u^2)
84        params.sqrt_neg_three_u_squared_minus_u_over_2 - temp // sqrt(-3u^2-u/2) - t2^2 * alpha * sqrt(-3u^2)
85    };
86
87    let x2 = -params.u - x1;
88
89    let x3 = {
90        let t2_plus_fu = t2 + params.fu;
91        let t2_inv = alpha * t2_plus_fu;
92        let mut temp = t2_plus_fu.square();
93        temp *= &t2_inv;
94        temp *= &params.inv_three_u_squared;
95        params.u - temp
96    };
97
98    [x1, x2, x3]
99}
100
101/// ?
102fn potential_xs<G: SWCurveConfig>(params: &BWParameters<G>, t: G::BaseField) -> [G::BaseField; 3] {
103    let t2 = t.square();
104    let mut alpha_inv = t2;
105    alpha_inv += &params.fu;
106    alpha_inv *= &t2;
107
108    let alpha = alpha_inv.inverse().unwrap_or_else(G::BaseField::zero);
109
110    potential_xs_helper(params, t2, alpha)
111}
112
113/// returns the y-coordinate if x is a valid point on the curve, otherwise None
114/// TODO: what about sign?
115pub fn get_y<G: SWCurveConfig>(x: G::BaseField) -> Option<G::BaseField> {
116    let fx = curve_eqn::<G>(x);
117    fx.sqrt()
118}
119
120fn get_xy<G: SWCurveConfig>(
121    params: &BWParameters<G>,
122    t: G::BaseField,
123) -> (G::BaseField, G::BaseField) {
124    let xvec = potential_xs(params, t);
125    for x in &xvec {
126        if let Some(y) = get_y::<G>(*x) {
127            return (*x, y);
128        }
129    }
130    panic!("get_xy")
131}
132
133impl<G: SWCurveConfig> GroupMap<G::BaseField> for BWParameters<G> {
134    fn setup() -> Self {
135        assert!(G::COEFF_A.is_zero());
136
137        // is Field(1) a valid x-coordinate? no? is Field(2) a valid x-coordinate? etc.
138        let (u, fu) = find_first(G::BaseField::one(), |u| {
139            let fu: G::BaseField = curve_eqn::<G>(u);
140            if fu.is_zero() {
141                None
142            } else {
143                Some((u, fu))
144            }
145        });
146
147        let two = G::BaseField::one() + G::BaseField::one();
148        let three = two + G::BaseField::one();
149
150        let three_u_squared = u.square() * three; // 3 * u^2
151        let inv_three_u_squared = three_u_squared.inverse().unwrap(); // (3 * u^2)^-1
152        let sqrt_neg_three_u_squared = (-three_u_squared).sqrt().unwrap();
153        let two_inv = two.inverse().unwrap();
154        let sqrt_neg_three_u_squared_minus_u_over_2 = (sqrt_neg_three_u_squared - u) * two_inv;
155
156        Self {
157            u,
158            fu,
159            sqrt_neg_three_u_squared_minus_u_over_2,
160            sqrt_neg_three_u_squared,
161            inv_three_u_squared,
162        }
163    }
164
165    fn batch_to_group_x(&self, ts: Vec<G::BaseField>) -> Vec<[G::BaseField; 3]> {
166        let t2_alpha_invs: Vec<_> = ts
167            .iter()
168            .map(|t| {
169                let t2 = t.square();
170                let mut alpha_inv = t2;
171                alpha_inv += &self.fu;
172                alpha_inv *= &t2;
173                (t2, alpha_inv)
174            })
175            .collect();
176
177        let mut alphas: Vec<G::BaseField> = t2_alpha_invs.iter().map(|(_, a)| *a).collect();
178        ark_ff::batch_inversion::<G::BaseField>(&mut alphas);
179
180        let potential_xs = t2_alpha_invs
181            .iter()
182            .zip(alphas)
183            .map(|((t2, _), alpha)| potential_xs_helper(self, *t2, alpha));
184        potential_xs.collect()
185    }
186
187    fn to_group(&self, t: G::BaseField) -> (G::BaseField, G::BaseField) {
188        get_xy(self, t)
189    }
190}
groupmap/lib.rs

groupmap/
lib.rs
