Tags: skaunov/hash_to_curve
Tags
initial commit Below are couple of notes to the initial commit. # 32 bytes split Initially I tried to fully fill `BigUint56` 35 bytes when reducing _uniform bytes_ to `u`, but it turned out that `primefield` `from_bytes` reduces input only once, so 32 bytes are most natural to feed it. ```noir // remainder in LE: [0, 0, 0, 209, 3, 0, 0, 1] global remainder_35bytes = BaseField{ val: BigUint56 { limbs: [0xa1000000000000, 0x07a2000e90, 0x01, 0x00, 0x00] } }; ``` ```noir let mut tv_lo = [0; 35]; let mut tv_hi = [0; 13]; ``` # `map_to_curve` I confused `q` for the order curve in <F.2.1.> and went with <F.2.1.1.>, but since it's actually equal to `p` for `secp256k1` let's also try <F.2.1.2.>. > https://www.rfc-editor.org/rfc/rfc9380.html#name-sqrt_ratio-for-any-field \ <F.2.1.2.> and <F.2.1.3.> aren't suitable as remainder of `secp256k1` order is $1$ for both of the cases highly likely <https://docs.rs/ff/latest/ff/trait.Field.html#tymethod.sqrt_ratio> is best brief explainer currently Let me leave <F.2.1.1.> variant from the RFC here just in case. This also has funny halving, which never been replaced for a bit shift. ```noir /* TODO double-check -- manually calculated; order of the curve $-1$: $mod 64 = 0$, $mod 128 = 64$ */ global c1 = 6; // "the largest integer such that 2^c1 divides q - 1" global c2 = BigUint56 { limbs: [0xff497a3340d905, 0xbb739abd2280ee, 0xfffffffffffaea, 0xffffffffffffff, 0x03ffffff] }; global c3 = BigUint56 { limbs: [0x7fa4bd19a06c82, 0x5db9cd5e914077, 0xfffffffffffd75, 0xffffffffffffff, 0x01ffffff] }; global c4 = BigUint56 { limbs: [0x3f, 0x00, 0x00, 0x00, 0x00] }; global c5 = BigUint56 { limbs: [0x20, 0x00, 0x00, 0x00, 0x00] }; global c6 = BaseField{ val: BigUint56 { limbs: [0x9e0f6d02cba7a0, 0x8431b70e0cfdc7, 0x27cfb1d215d250, 0xb5877a6a6d6565, 0x93923169] } }; global c7 = BaseField{ val: BigUint56 { limbs: [0x01ef0098089407, 0x568fced9765fc0, 0x5cefdf457ec7d7, 0x64d52537cabc37, 0x9df6e0ef] } }; // <F.2.1.1.> fn sqrt_ratio_1(u: BaseField, v: BaseField) -> (bool, BaseField) { // TODO analyze implications for _map_to_curve_ implementation assert(!v.is_zero()); // let c2 = ScalarField::modulus().to_biguint56().div( // BigUint56::from_u56(2.pow_32(c1) as u56) // ).0; let mut tv1 = c6; // `c6` // *`pow` comes as #stub* let tv2 = v.pow(c4); // `c4` let tv3 = tv2.square().mul(v); // ~~[orderSecp256k1]~~ /* TODO double check I didn't lost $1$ or something when using `ScalarField::modulus()` for `secp256k1` order in `c2` which is used in `c3` */ /* also due to the structure of those `c` constansts it's easy to verify myself with the assertion (to be removed from production; could be move to tests, btw) */ /* TODO *it's important to note `val` stores Montgomery form*, which should be handled with care and reduced when taken outside */ /* assert(ScalarField::modulus().to_biguint56().div( BigUint56::from_u56(2.pow_32(6) as u56) ).1.is_zero()); */ let tv5 = u.mul(tv3).pow(c3); // `c3` let tv5 = tv5.mul(tv2); let tv2 = tv5.mul(v); let tv3 = tv5.mul(u); let tv4 = tv3.mul(tv2); let tv5 = tv4.pow(c5); // `c5` let isQR = tv5.eq(BaseField::one()); let mut tv2 = tv3.mul(c7); // `c7` let mut tv5 = tv4.mul(tv1); let mut tv3 = cmov(tv2, tv3, isQR); let mut tv4 = cmov(tv5, tv4, isQR); // /* I have a hunch current Noir is very conservative on the loop ranges, so it's a TODO simplify the range when more sophisticated will be available for i in c1..=2 { */ for j in 2..c1 { let i = c1 - j; // tv5 = i - 2; tv5 = tv4.pow(BigUint56::from_u56(2.pow_32(i - 2) as u56)); let e1 = tv5.eq(BaseField::one()); tv2 = tv3.mul(tv1); tv1 = tv1.square(); tv5 = tv4.mul(tv1); tv3 = cmov(tv2, tv3, e1); tv4 = cmov(tv5, tv4, e1); } // // #stub // (false, BaseField::zero()) (isQR, tv3) /* [orderSecp256k1]: for the sake of current focus on `secp256k1` its order is defined as a constant here, which later can be refactored to a parameter */ } // Actually seems it can be replaced with a constant. ~~TODO~~ // `checked` is useful when developing fn biguint56_half_checked(divident: BigUint56) -> BigUint56 { let (result, check) = divident.div(BigUint56::from_u56(2)); assert(check.eq(BigUint56::zero())); result } fn biguint56_half(divident: BigUint56) -> BigUint56 { // divident.div(BigUint56::from_u56(2)).0 // TODO switch from `checked` to skimmed when release biguint56_half_checked(divident) } ``` ## `redox-ecc` Also during analysis I tried to use `redox-ecc::weierstrass::sswu`, where I didn't see enough perspective, and which yielded _sqrt_ snippets. ```noir // TODO $+1$ and $-1$ for $p$ is messed up in square rooting // pub fn map_to_curve_redox(u: BaseField) -> (BaseField, BaseField) { // let t1 = u.square().mul(Z); // let t2 = t1.square(); // let x1 = inv0(t1.add(t2)); // let e1 = x1.is_zero(); // let x1 = x1.add(BaseField::one()); // let x1 = cmov(x1, c2, e1); // let x1 = x1.mul(c1); // let gx1 = x1.square().add(A).mul(x1).add(B); // let x2 = t1.mul(x1); // let t2 = t1.mul(t2); // let gx2 = gx1.mul(t2); // // #stub // (BaseField::zero(), BaseField::zero()) // } // fn is_square(elem: BaseField) -> (bool, BaseField) { // let (res, proof) = is_square_prove(elem); // if res { // assert(proof.square().eq(elem)); // (true, proof) // } // // TODO double-check I correctly remember squares are interleaved with non-squares // else { // assert(proof.square().eq(elem.add(BaseField::one()))); // (false, BaseField{val: BigUint56{ // limbs: [0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff] // }}) // } // } // unconstrained fn is_square_prove(elem: BaseField) -> (bool, BaseField) { // // TODO make constants? #halfmodulus // let res = elem.pow( // BaseField::modulus().to_biguint56().sub(BigUint56::one()).div(BigUint56::from_u56(2)).0 // ); // if res.eq(BaseField::zero()) | res.eq(BaseField::one()) { // (true, sqrt_util(elem)) // } // // TODO check the edge on adding one // else {(false, sqrt_util(elem.add(BaseField::one())))} // } unconstrained fn sqrt_util(elem: BaseField) -> BaseField {elem.pow( // #halfmodulus BaseField::modulus().to_biguint56().add(BigUint56::one()).div(BigUint56::from_u56(2)).0 )} unconstrained fn sqrt_3mod4(x: BaseField) -> BaseField{ let c1 = BaseField::modulus().val.add(BigUint56::one()).div(BigUint56::from_u56(4)); println(c1.1); x.pow(c1.0) } #[test] fn halving_debugging() { println(sqrt_3mod4(BaseField::from_u56(11))); } ```