Weil_from_tate_pairing test fails occasionally

[mrdaybird]

Describe the bug
The curve::pairing::tests::weil_from_tate_pairing occasionally fails with invalid inverse panic.

To Reproduce
Steps to reproduce the behavior:
If the test is looped over a thousand times, it almost always fails. But it will take forever to complete in debug build, so --release flag is needed.

Context (please complete the following information):
This bug results in a failed CI test occasionally, which is annoying.

Additional context

ronkathon/src/curve/pairing.rs

Lines 70 to 78 in 9e8b0f9

	x = x.pow(2) * tangent_line::<C>(z, q) / vertical_line(2 * z, q);
	// Z <- 2Z
	z += z;
	if bit == '1' {
	if z + p == AffinePoint::Infinity {
	x *= line_function::<C>(z, p, q);
	} else {
	// f_{[2m+1],P} <- f_{2m,P}.(l_{Z,P}(Q)/v_{Z+P}(Q))
	x = x * line_function::<C>(z, p, q) / vertical_line(z + p, q);

After a little investigation, I noticed that vertical_line(2 * z, q), which is in the denominator, evaluates to zero sometimes.

This issue is also mentioned in Ben Lynn's thesis, along with the fact that zeros and poles of the intermediate functions cancel each other eventually. See Section 3.9.3

The intermediate functions evaluated during Miller’s algorithm have zeroes and poles that eventually cancel out.

One possible solution is to ignore the zeros and poles. But I am not sure of the correctness.
I tested against the following fix by looping over the test a few thousand times without any problem, maybe it is correct?

pub(crate) fn miller_loop<C: EllipticCurve + Debug + PartialEq, const R: usize>(
  p: AffinePoint<C>,
  q: AffinePoint<C>,
) -> C::BaseField {
  // Use the R to get a binary representation, then loop over the binary representation to do the
  // algorithm.
  let mut x = C::BaseField::ONE;
  let mut z = p;

  let r = format!("{:b}", R);
  let mut zeros = 0;
  for bit in r.chars().skip(1) {
    // f_{2m,P} <- f_{m,P}^2.(l_{[m]P,[m]P}(Q)/v_{[2m]P}(Q))
    let tangent = tangent_line::<C>(z, q);
    let vertical = vertical_line(2 * z, q);
    x = x.pow(2);
    if tangent != C::BaseField::ZERO {
      x = x * tangent;
    } else {
      zeros += 1;
    }
    if vertical != C::BaseField::ZERO {
      x = x / vertical;
    } else {
      zeros -= 1;
    }
    // Z <- 2Z
    z += z;
    if bit == '1' {
      if z + p == AffinePoint::Infinity {
        let line = line_function::<C>(z, p, q);
        if line == C::BaseField::ZERO {
          zeros += 1;
        } else {
          x *= line;
        }
      } else {
        // f_{[2m+1],P} <- f_{2m,P}.(l_{Z,P}(Q)/v_{Z+P}(Q))
        let line = line_function::<C>(z, p, q);
        let vertical = vertical_line(z + p, q);
        if line_function::<C>(z, p, q) == C::BaseField::ZERO {
          zeros += 1;
        } else {
          x *= line;
        }
        if vertical == C::BaseField::ZERO {
          zeros -= 1;
        } else {
          x /= vertical;
        }
      }
      // Z <- Z + P
      z += p;
    }
  }

  assert_eq!(zeros, 0);
  x
}

@lonerapier

[Autoparallel]

This issue is also mentioned in Ben Lynn's thesis, along with the fact that zeros and poles of the intermediate functions cancel each other eventually. See Section 3.9.3

I see you're a man of culture as well -- that thesis was awesome.

---

Let me look more into this and your solution. Zeros and poles should definitely just cancel out in projective space (they're inverses of each other, i.e., $\infty \cdot 0 = 1$)

[mrdaybird]

I see you're a man of culture as well -- that thesis was awesome.

I just had a cursory look at that thesis for this issue! But taking an overview of the contents, it has some very good stuff about practical cryptography, like Multiprecision Arithmetic!

Added it to my reading list!