1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
use crate::models::short_weierstrass::SWCurveConfig;
use ark_ff::{Field, One, Zero};
use core::marker::PhantomData;
use crate::{
hashing::{curve_maps::parity, map_to_curve_hasher::MapToCurve, HashToCurveError},
models::short_weierstrass::{Affine, Projective},
};
/// Trait defining the necessary parameters for the SWU hash-to-curve method
/// for the curves of Weierstrass form of:
/// y^2 = x^3 + a*x + b where ab != 0. From [\[WB2019\]]
///
/// - [\[WB2019\]] <https://eprint.iacr.org/2019/403>
pub trait SWUConfig: SWCurveConfig {
/// An element of the base field that is not a square root see \[WB2019, Section 4\].
/// It is also convenient to have $g(b/ZETA * a)$ to be square. In general
/// we use a `ZETA` with low absolute value coefficients when they are
/// represented as integers.
const ZETA: Self::BaseField;
}
/// Represents the SWU hash-to-curve map defined by `P`.
pub struct SWUMap<P: SWUConfig>(PhantomData<fn() -> P>);
impl<P: SWUConfig> MapToCurve<Projective<P>> for SWUMap<P> {
/// Checks if `P` represents a valid map.
fn check_parameters() -> Result<(), HashToCurveError> {
// Verifying that ZETA is a non-square
debug_assert!(
P::ZETA.legendre().is_qnr(),
"ZETA should be a quadratic non-residue for the SWU map"
);
// Verifying the prerequisite for applicability of SWU map
debug_assert!(!P::COEFF_A.is_zero() && !P::COEFF_B.is_zero(),
"Simplified SWU requires a * b != 0 in the short Weierstrass form of y^2 = x^3 + a*x + b ");
Ok(())
}
/// Map an arbitrary base field element to a curve point.
/// Based on
/// <https://github.com/zcash/pasta_curves/blob/main/src/hashtocurve.rs>.
fn map_to_curve(element: P::BaseField) -> Result<Affine<P>, HashToCurveError> {
// 1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
// 2. x1 = (-B / A) * (1 + tv1)
// 3. If tv1 == 0, set x1 = B / (Z * A)
// 4. gx1 = x1^3 + A * x1 + B
//
// We use the "Avoiding inversions" optimization in [WB2019, section 4.2]
// (not to be confused with section 4.3):
//
// here [WB2019]
// ------- ---------------------------------
// Z ξ
// u t
// Z * u^2 ξ * t^2 (called u, confusingly)
// x1 X_0(t)
// x2 X_1(t)
// gx1 g(X_0(t))
// gx2 g(X_1(t))
//
// Using the "here" names:
// x1 = num_x1/div = [B*(Z^2 * u^4 + Z * u^2 + 1)] / [-A*(Z^2 * u^4 + Z * u^2]
// gx1 = num_gx1/div_gx1 = [num_x1^3 + A * num_x1 * div^2 + B * div^3] / div^3
let a = P::COEFF_A;
let b = P::COEFF_B;
let zeta_u2 = P::ZETA * element.square();
let ta = zeta_u2.square() + zeta_u2;
let num_x1 = b * (ta + <P::BaseField as One>::one());
let div = a * if ta.is_zero() { P::ZETA } else { -ta };
let num2_x1 = num_x1.square();
let div2 = div.square();
let div3 = div2 * div;
let num_gx1 = (num2_x1 + a * div2) * num_x1 + b * div3;
// 5. x2 = Z * u^2 * x1
let num_x2 = zeta_u2 * num_x1; // same div
// 6. gx2 = x2^3 + A * x2 + B [optimized out; see below]
// 7. If is_square(gx1), set x = x1 and y = sqrt(gx1)
// 8. Else set x = x2 and y = sqrt(gx2)
let gx1_square;
let gx1;
debug_assert!(
!div3.is_zero(),
"we have checked that neither a or ZETA are zero. Q.E.D."
);
let y1: P::BaseField = {
gx1 = num_gx1 / div3;
if gx1.legendre().is_qr() {
gx1_square = true;
gx1.sqrt()
.expect("We have checked that gx1 is a quadratic residue. Q.E.D")
} else {
let zeta_gx1 = P::ZETA * gx1;
gx1_square = false;
zeta_gx1.sqrt().expect(
"ZETA * gx1 is a quadratic residue because legard is multiplicative. Q.E.D",
)
}
};
// This magic also comes from a generalization of [WB2019, section 4.2].
//
// The Sarkar square root algorithm with input s gives us a square root of
// h * s for free when s is not square, where h is a fixed nonsquare.
// In our implementation, h = ROOT_OF_UNITY.
// We know that Z / h is a square since both Z and h are
// nonsquares. Precompute theta as a square root of Z / ROOT_OF_UNITY.
//
// We have gx2 = g(Z * u^2 * x1) = Z^3 * u^6 * gx1
// = (Z * u^3)^2 * (Z/h * h * gx1)
// = (Z * theta * u^3)^2 * (h * gx1)
//
// When gx1 is not square, y1 is a square root of h * gx1, and so Z * theta *
// u^3 * y1 is a square root of gx2. Note that we don't actually need to
// compute gx2.
let y2 = zeta_u2 * element * y1;
let num_x = if gx1_square { num_x1 } else { num_x2 };
let y = if gx1_square { y1 } else { y2 };
let x_affine = num_x / div;
let y_affine = if parity(&y) != parity(&element) {
-y
} else {
y
};
let point_on_curve = Affine::<P>::new_unchecked(x_affine, y_affine);
debug_assert!(
point_on_curve.is_on_curve(),
"swu mapped to a point off the curve"
);
Ok(point_on_curve)
}
}
#[cfg(test)]
mod test {
#[cfg(all(
target_has_atomic = "8",
target_has_atomic = "16",
target_has_atomic = "32",
target_has_atomic = "64",
target_has_atomic = "ptr"
))]
type DefaultHasher = ahash::AHasher;
#[cfg(not(all(
target_has_atomic = "8",
target_has_atomic = "16",
target_has_atomic = "32",
target_has_atomic = "64",
target_has_atomic = "ptr"
)))]
type DefaultHasher = fnv::FnvHasher;
use crate::{
hashing::{map_to_curve_hasher::MapToCurveBasedHasher, HashToCurve},
CurveConfig,
};
use ark_ff::field_hashers::DefaultFieldHasher;
use ark_std::vec::*;
use super::*;
use ark_ff::{fields::Fp64, MontBackend, MontFp};
use hashbrown::HashMap;
use sha2::Sha256;
#[derive(ark_ff::MontConfig)]
#[modulus = "127"]
#[generator = "6"]
pub struct F127Config;
pub type F127 = Fp64<MontBackend<F127Config, 1>>;
const F127_ONE: F127 = MontFp!("1");
struct TestSWUMapToCurveConfig;
impl CurveConfig for TestSWUMapToCurveConfig {
const COFACTOR: &'static [u64] = &[1];
#[rustfmt::skip]
const COFACTOR_INV: F127 = F127_ONE;
type BaseField = F127;
type ScalarField = F127;
}
/// just because not defining another field
///
/// from itertools import product
/// p = 127
/// FF = GF(p)
/// for a,b in product(range(0,p), range(0,p)):
/// try:
/// E = EllipticCurve([FF(a),FF(b)])
/// if E.order() == p:
/// print(E)
/// except:
/// pass
///
/// y^2 = x^3 + x + 63
impl SWCurveConfig for TestSWUMapToCurveConfig {
/// COEFF_A = 1
const COEFF_A: F127 = F127_ONE;
/// COEFF_B = 63
const COEFF_B: F127 = MontFp!("63");
/// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
const GENERATOR: Affine<Self> = Affine::new_unchecked(MontFp!("62"), MontFp!("70"));
}
impl SWUConfig for TestSWUMapToCurveConfig {
const ZETA: F127 = MontFp!("-1");
}
/// test that MontFp make a none zero element out of 1
#[test]
fn test_field_element_construction() {
let a1 = F127::from(1);
let a2 = F127::from(2);
let a3 = F127::from(125);
assert!(F127::from(0) == a2 + a3);
assert!(F127::from(0) == a2 * a1 + a3);
}
#[test]
fn test_field_division() {
let num = F127::from(0x3d);
let den = F127::from(0x7b);
let num_on_den = F127::from(0x50);
assert!(num / den == num_on_den);
}
/// The point of the test is to get a simple SWU compatible curve and make
/// simple hash
#[test]
fn hash_arbitrary_string_to_curve_swu() {
let test_swu_to_curve_hasher = MapToCurveBasedHasher::<
Projective<TestSWUMapToCurveConfig>,
DefaultFieldHasher<Sha256, 128>,
SWUMap<TestSWUMapToCurveConfig>,
>::new(&[1])
.unwrap();
let hash_result = test_swu_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");
assert!(
hash_result.is_on_curve(),
"hash results into a point off the curve"
);
}
/// Use a simple SWU compatible curve and map the whole field to it. We observe
/// the map behaviour. Specifically, the map should be non-constant, all
/// elements should be mapped to curve successfully. everything can be mapped
#[test]
fn map_field_to_curve_swu() {
SWUMap::<TestSWUMapToCurveConfig>::check_parameters().unwrap();
let mut map_range: Vec<Affine<TestSWUMapToCurveConfig>> = vec![];
for current_field_element in 0..127 {
let element = F127::from(current_field_element as u64);
map_range.push(SWUMap::<TestSWUMapToCurveConfig>::map_to_curve(element).unwrap());
}
let mut counts =
HashMap::with_hasher(core::hash::BuildHasherDefault::<DefaultHasher>::default());
let mode = map_range
.iter()
.copied()
.max_by_key(|&n| {
let count = counts.entry(n).or_insert(0);
*count += 1;
*count
})
.unwrap();
assert!(
*counts.get(&mode).unwrap() != 127,
"a constant hash function is not good."
);
}
}