ark_ec/hashing/curve_maps/
wb.rs

1use core::marker::PhantomData;
2
3use crate::{models::short_weierstrass::SWCurveConfig, CurveConfig};
4use ark_ff::batch_inversion;
5use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial, Polynomial};
6
7use crate::{
8    hashing::{map_to_curve_hasher::MapToCurve, HashToCurveError},
9    models::short_weierstrass::{Affine, Projective},
10    AffineRepr,
11};
12
13use super::swu::{SWUConfig, SWUMap};
14type BaseField<MP> = <MP as CurveConfig>::BaseField;
15
16/// [`IsogenyMap`] defines an isogeny between curves of
17/// form `Phi(x, y) := (a(x), b(x)*y)`.
18///
19/// The `x` coordinate of the codomain point only depends on the
20/// `x`-coordinate of the domain point, and the
21/// `y`-coordinate of the codomain point is a multiple of the `y`-coordinate of the domain point.
22/// The multiplier depends on the `x`-coordinate of the domain point.
23/// All isogeny maps of curves of short Weierstrass form can be written in this way. See
24/// [\[Ga18]\]. Theorem 9.7.5 for details.
25///
26/// We assume that `Domain` and `Codomain` have the same `BaseField` but we use both
27/// `BaseField<Domain>` and `BaseField<Codomain>` in our fields' definitions to avoid
28/// using `PhantomData`
29///
30/// - [\[Ga18]\] Galbraith, S. D. (2018). Mathematics of public key cryptography.
31pub struct IsogenyMap<
32    'a,
33    Domain: SWCurveConfig,
34    Codomain: SWCurveConfig<BaseField = BaseField<Domain>>,
35> {
36    pub x_map_numerator: &'a [BaseField<Domain>],
37    pub x_map_denominator: &'a [BaseField<Codomain>],
38
39    pub y_map_numerator: &'a [BaseField<Domain>],
40    pub y_map_denominator: &'a [BaseField<Codomain>],
41}
42
43impl<Domain, Codomain> IsogenyMap<'_, Domain, Codomain>
44where
45    Domain: SWCurveConfig,
46    Codomain: SWCurveConfig<BaseField = BaseField<Domain>>,
47{
48    fn apply(&self, domain_point: Affine<Domain>) -> Result<Affine<Codomain>, HashToCurveError> {
49        match domain_point.xy() {
50            Some((x, y)) => {
51                let x_num = DensePolynomial::from_coefficients_slice(self.x_map_numerator);
52                let x_den = DensePolynomial::from_coefficients_slice(self.x_map_denominator);
53
54                let y_num = DensePolynomial::from_coefficients_slice(self.y_map_numerator);
55                let y_den = DensePolynomial::from_coefficients_slice(self.y_map_denominator);
56
57                let mut v: [BaseField<Domain>; 2] = [x_den.evaluate(&x), y_den.evaluate(&x)];
58                batch_inversion(&mut v);
59                let img_x = x_num.evaluate(&x) * v[0];
60                let img_y = (y_num.evaluate(&x) * y) * v[1];
61                Ok(Affine::new_unchecked(img_x, img_y))
62            },
63            None => Ok(Affine::identity()),
64        }
65    }
66}
67
68/// Trait defining the necessary parameters for the WB hash-to-curve method.
69///
70/// This method is used for curves in Weierstrass form defined by:
71///
72/// `y^2 = x^3 + a*x + b` where `b != 0`, but `a` can be zero,
73/// as seen in curves like BLS-381.
74///
75/// For more information, refer to \[WB2019\].
76///
77/// - [\[WB2019\]] <http://dx.doi.org/10.46586/tches.v2019.i4.154-179>
78pub trait WBConfig: SWCurveConfig + Sized {
79    // The isogenous curve should be defined over the same base field but it can have
80    // different scalar field type IsogenousCurveScalarField :
81    type IsogenousCurve: SWUConfig<BaseField = BaseField<Self>>;
82
83    const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self>;
84}
85
86pub struct WBMap<P: WBConfig> {
87    swu_field_curve_hasher: PhantomData<SWUMap<P::IsogenousCurve>>,
88    curve_params: PhantomData<fn() -> P>,
89}
90
91impl<P: WBConfig> MapToCurve<Projective<P>> for WBMap<P> {
92    /// Checks if `P` represents a valid map.
93    fn check_parameters() -> Result<(), HashToCurveError> {
94        match P::ISOGENY_MAP.apply(P::IsogenousCurve::GENERATOR) {
95            Ok(point_on_curve) => {
96                debug_assert!(point_on_curve.is_on_curve(),
97			      "the isogeny maps the generator of its domain: {} into {} which does not belong to its codomain.",P::IsogenousCurve::GENERATOR, point_on_curve);
98            },
99            Err(e) => return Err(e),
100        }
101
102        SWUMap::<P::IsogenousCurve>::check_parameters().unwrap(); // Or ?
103        Ok(())
104    }
105
106    /// Map random field point to a random curve point
107    /// inspired from
108    /// <https://github.com/zcash/pasta_curves/blob/main/src/hashtocurve.rs>
109    fn map_to_curve(
110        element: <Affine<P> as AffineRepr>::BaseField,
111    ) -> Result<Affine<P>, HashToCurveError> {
112        // first we need to map the field point to the isogenous curve
113        let point_on_isogenious_curve = SWUMap::map_to_curve(element).unwrap();
114        P::ISOGENY_MAP.apply(point_on_isogenious_curve)
115    }
116}
117
118#[cfg(test)]
119mod test {
120    use crate::{
121        hashing::{
122            curve_maps::{
123                swu::SWUConfig,
124                wb::{IsogenyMap, WBConfig, WBMap},
125            },
126            map_to_curve_hasher::MapToCurveBasedHasher,
127            HashToCurve,
128        },
129        models::short_weierstrass::SWCurveConfig,
130        short_weierstrass::{Affine, Projective},
131        CurveConfig,
132    };
133    use ark_ff::{field_hashers::DefaultFieldHasher, fields::Fp64, MontBackend, MontFp};
134
135    #[derive(ark_ff::MontConfig)]
136    #[modulus = "127"]
137    #[generator = "6"]
138    pub(crate) struct F127Config;
139    pub(crate) type F127 = Fp64<MontBackend<F127Config, 1>>;
140
141    const F127_ZERO: F127 = MontFp!("0");
142    const F127_ONE: F127 = MontFp!("1");
143
144    /// The struct defining our parameters for the target curve of hashing
145    struct TestWBF127MapToCurveConfig;
146
147    impl CurveConfig for TestWBF127MapToCurveConfig {
148        const COFACTOR: &[u64] = &[1];
149
150        const COFACTOR_INV: F127 = F127_ONE;
151
152        type BaseField = F127;
153        type ScalarField = F127;
154    }
155
156    /// E: Elliptic Curve defined by y^2 = x^3 + 3 over Finite
157    /// Field of size 127
158    impl SWCurveConfig for TestWBF127MapToCurveConfig {
159        /// COEFF_A = 0
160        const COEFF_A: F127 = F127_ZERO;
161
162        /// COEFF_B = 3
163        const COEFF_B: F127 = MontFp!("3");
164
165        /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
166        const GENERATOR: Affine<Self> = Affine::new_unchecked(MontFp!("62"), MontFp!("70"));
167
168        /// We use `()` because the point (0, 0) is not on the curve.
169        type ZeroFlag = ();
170    }
171
172    /// Testing WB19 hashing on a small curve
173    /// E_isogenous : Elliptic Curve defined by y^2 = x^3 + 109*x + 124 over Finite
174    /// Field of size 127
175    /// Isogenous to E : y^2 = x^3 + 3
176    struct TestSWU127MapToIsogenousCurveConfig;
177
178    /// First we define the isogenous curve
179    /// sage: E_isogenous.order()
180    /// 127
181    impl CurveConfig for TestSWU127MapToIsogenousCurveConfig {
182        const COFACTOR: &[u64] = &[1];
183
184        const COFACTOR_INV: F127 = F127_ONE;
185
186        type BaseField = F127;
187        type ScalarField = F127;
188    }
189
190    /// E_isogenous : Elliptic Curve defined by y^2 = x^3 + 109*x + 124 over Finite
191    /// Field of size 127
192    impl SWCurveConfig for TestSWU127MapToIsogenousCurveConfig {
193        /// COEFF_A = 109
194        const COEFF_A: F127 = MontFp!("109");
195
196        /// COEFF_B = 124
197        const COEFF_B: F127 = MontFp!("124");
198
199        /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
200        const GENERATOR: Affine<Self> = Affine::new_unchecked(MontFp!("84"), MontFp!("2"));
201
202        /// We use `bool because the point (0, 0) could be on the curve.
203        type ZeroFlag = bool;
204    }
205
206    /// SWU parameters for E_isogenous
207    impl SWUConfig for TestSWU127MapToIsogenousCurveConfig {
208        /// NON-SQUARE = - 1
209        const ZETA: F127 = MontFp!("-1");
210    }
211
212    /// E_isogenous : Elliptic Curve defined by y^2 = x^3 + 109*x + 124 over Finite
213    /// Field of size 127
214    /// With psi: E_isogenous -> E
215    /// psi = (psi_x(x,y), psi_y(x,y))
216    /// where
217    /// psi_x: (-57*x^13 - 21*x^12 + 10*x^11 + 34*x^10 + 40*x^9 -
218    /// 13*x^8 + 32*x^7 - 32*x^6 + 23*x^5 - 14*x^4 + 39*x^3 + 23*x^2 + 63*x +
219    /// 4)/(x^12 - 13*x^11 + 11*x^10 - 33*x^9 - 30*x^8 + 30*x^7 + 34*x^6 - 44*x^5 +
220    /// 63*x^4 - 20*x^3 - 10*x^2 + 31*x + 2)
221    ///
222    /// psi_y: (10*x^18*y + 59*x^17*y + 41*x^16*y + 48*x^15*y - 7*x^14*y + 6*x^13*y +
223    /// 5*x^12*y + 62*x^11*y + 12*x^10*y + 36*x^9*y - 49*x^8*y - 18*x^7*y - 63*x^6*y
224    /// - 43*x^5*y - 60*x^4*y - 18*x^3*y + 30*x^2*y - 57*x*y - 34*y)/(x^18 + 44*x^17
225    /// - 63*x^16 + 52*x^15 + 3*x^14 + 38*x^13 - 30*x^12 + 11*x^11 - 42*x^10 - 13*x^9
226    /// - 46*x^8 - 61*x^7 - 16*x^6 - 55*x^5 + 18*x^4 + 23*x^3 - 24*x^2 - 18*x + 32)
227    const ISOGENY_MAP_TESTWBF127: IsogenyMap<
228        '_,
229        TestSWU127MapToIsogenousCurveConfig,
230        TestWBF127MapToCurveConfig,
231    > = IsogenyMap {
232        x_map_numerator: &[
233            MontFp!("4"),
234            MontFp!("63"),
235            MontFp!("23"),
236            MontFp!("39"),
237            MontFp!("-14"),
238            MontFp!("23"),
239            MontFp!("-32"),
240            MontFp!("32"),
241            MontFp!("-13"),
242            MontFp!("40"),
243            MontFp!("34"),
244            MontFp!("10"),
245            MontFp!("-21"),
246            MontFp!("-57"),
247        ],
248
249        x_map_denominator: &[
250            MontFp!("2"),
251            MontFp!("31"),
252            MontFp!("-10"),
253            MontFp!("-20"),
254            MontFp!("63"),
255            MontFp!("-44"),
256            MontFp!("34"),
257            MontFp!("30"),
258            MontFp!("-30"),
259            MontFp!("-33"),
260            MontFp!("11"),
261            MontFp!("-13"),
262            MontFp!("1"),
263        ],
264
265        y_map_numerator: &[
266            MontFp!("-34"),
267            MontFp!("-57"),
268            MontFp!("30"),
269            MontFp!("-18"),
270            MontFp!("-60"),
271            MontFp!("-43"),
272            MontFp!("-63"),
273            MontFp!("-18"),
274            MontFp!("-49"),
275            MontFp!("36"),
276            MontFp!("12"),
277            MontFp!("62"),
278            MontFp!("5"),
279            MontFp!("6"),
280            MontFp!("-7"),
281            MontFp!("48"),
282            MontFp!("41"),
283            MontFp!("59"),
284            MontFp!("10"),
285        ],
286
287        y_map_denominator: &[
288            MontFp!("32"),
289            MontFp!("-18"),
290            MontFp!("-24"),
291            MontFp!("23"),
292            MontFp!("18"),
293            MontFp!("-55"),
294            MontFp!("-16"),
295            MontFp!("-61"),
296            MontFp!("-46"),
297            MontFp!("-13"),
298            MontFp!("-42"),
299            MontFp!("11"),
300            MontFp!("-30"),
301            MontFp!("38"),
302            MontFp!("3"),
303            MontFp!("52"),
304            MontFp!("-63"),
305            MontFp!("44"),
306            MontFp!("1"),
307        ],
308    };
309    impl WBConfig for TestWBF127MapToCurveConfig {
310        type IsogenousCurve = TestSWU127MapToIsogenousCurveConfig;
311
312        const ISOGENY_MAP: super::IsogenyMap<'static, Self::IsogenousCurve, Self> =
313            ISOGENY_MAP_TESTWBF127;
314    }
315
316    /// The point of the test is to get a simple WB compatible curve
317    /// and make simple hash
318    #[test]
319    fn hash_arbitrary_string_to_curve_wb() {
320        use sha2::Sha256;
321        let test_wb_to_curve_hasher = MapToCurveBasedHasher::<
322            Projective<TestWBF127MapToCurveConfig>,
323            DefaultFieldHasher<Sha256, 128>,
324            WBMap<TestWBF127MapToCurveConfig>,
325        >::new(&[1])
326        .unwrap();
327
328        let hash_result = test_wb_to_curve_hasher.hash(b"if you stick a Babel fish in your ear you can instantly understand anything said to you in any form of language.").expect("fail to hash the string to curve");
329
330        assert!(
331            hash_result.x != F127_ZERO && hash_result.y != F127_ZERO,
332            "we assume that not both a and b coefficienst are zero for the test curve"
333        );
334
335        assert!(
336            hash_result.is_on_curve(),
337            "hash results into a point off the curve"
338        );
339    }
340}
ark_ec/hashing/curve_maps/wb.rs

ark_ec/hashing/curve_maps/
wb.rs
