Oversight in fn test_sw_properties() ?

[rubdos]

Hi!

@Tarinn and I have been toying with some curves, of which one has a cofactor 2 (#490). I've put all parameters into a Short Weierstraß implementation, and it fails on test_sw_properties. More specifically, it fails on the assert!(!p.is_in_correct_subgroup_assuming_on_curve()); assertion below.

let mut x = BaseField::zero();
let mut i = 0;
loop {
    // y^2 = x^3 + a * x + b
    let rhs = x * x.square() + x * <Config as SWCurveConfig>::COEFF_A + <Config as SWCurveConfig>::COEFF_B;

    if let Some(y) = rhs.sqrt() {
        let p = Affine::new_unchecked(x, if y < -y { y } else { -y });
        if !<<$group as CurveGroup>::Config as CurveConfig>::cofactor_is_one() {
            assert!(!p.is_in_correct_subgroup_assuming_on_curve());
        }

        let g1 = p.mul_by_cofactor_to_group();
        if !g1.is_zero() {
            let g1 = Affine::from(g1);
            assert!(g1.is_in_correct_subgroup_assuming_on_curve());
            break;
        }
    }

    i += 1;
    x += BaseField::one();
}

We've been looking at this code, and we're not sure what exact property is being tested here. Our best guess is that this loop tries to find a low order point, and then assert that multiplying by the cofactor yields a point of either high order or zero.

This is our best guess, because it actually does not do that as-is. More specifically, finding such point fails for a curve in 1/h of curves because of the assert!(!p.is_in_correct_subgroup_assuming_on_curve()); assertion. There are only few SW curves with a cofactor in the curves crate, and most of them have a "high" cofactor, which would explain why this case was never hit.

Currently, the code loops over valid points in increasing x-order, starting from x=0. It then asserts that all points P encountered are of low order, until one is found such that h*P is not zero. If h*P is not zero, then it is asserted to be of high order, the loop is stopped, and the test succeeds. I am not sure whether this is some desired property of a short Weierstraß curve which I do not recognize, or it is an oversight.

If our guess is indeed the intention, I think this could be patched:

diff --git a/test-templates/src/groups.rs b/test-templates/src/groups.rs
index 3701907..f6d0c25 100644
--- a/test-templates/src/groups.rs
+++ b/test-templates/src/groups.rs
@@ -268,7 +268,9 @@ macro_rules! __test_group {
                 if let Some(y) = rhs.sqrt() {
                     let p = Affine::new_unchecked(x, if y < -y { y } else { -y });
                     if !<<$group as CurveGroup>::Config as CurveConfig>::cofactor_is_one() {
-                        assert!(!p.is_in_correct_subgroup_assuming_on_curve());
+                        if p.is_in_correct_subgroup_assuming_on_curve() {
+                            continue;
+                        }
                     }

                     let g1 = p.mul_by_cofactor_to_group();

Then again, if our guess is indeed the intention, this whole loop should probably be guarded only for cofactor curves, and should not be executed at all for prime order groups.

My question is: is our guess correct, that this assert should actually skip over the high order points, instead of failing on them?

I would be glad to submit patches to correct this, if this is indeed an oversight.

Git blame is a bit difficult to follow here, but this logic seems to stem from a combination of d415a01 and the later refactoring that happened in 77fb6ab.

[Pratyush]

I think this code was adapted from a test for checking the generators of a curve, which worked for specific curves where the generator was constructed by vent performing this iteration process until you hit something on the curve, and then multiplying that point by h.

I think longer term we should replace it checks that test is_on_curve and is_in_subgroup, but in the meanwhile your patch would be great.

[rubdos]

I see some options, then:

1. The patch I mentioned above
2. Guarding the whole loop with a cofactor_is_one() check
3. Rewrite the logic such that it actually tests h*P being on the curve.

What would you prefer here?

[rubdos]

The patch I mentioned above

FWIW, the patch has some problems, the continue; is not enough. You still need to increment i and x, so it'll need some refactoring anyway. I'll make a proposal and throw in a PR.