Skip to content

Tags: skaunov/hash_to_curve

Tags

v0.1.1

Toggle v0.1.1's commit message
Bump `noir-bigint` `dependencies`

v0.1.0

Toggle v0.1.0's commit message
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)));
}
```