Change function signature T Inverse() to std::optional<T> Inverse()

[chokobole]

Issue type

Feature Request

Current behavior?

Currently Inverse() method returns a inverse and panics if failed using CHECK(). But this isn't GPU interoperable code. So I suggest it to change it to return std::optional<T> when it failed.

Expected Behavior?

Returns false if failed and true and populates the out parameter.

[saliaku]

hey i can take this up

[chokobole]

@saliaku Oh thanks :) That would be awesome! If you have any questions on this, please feel free to ask us.

[saliaku]

@chokobole can you tell me which files to work on so that it would be easier for me to work

[chokobole]

The Inverse() is located in

tachyon/tachyon/math/base/groups.h

Lines 79 to 86 in c6c7f83

	// Inverse: a⁻¹
	template <
	typename G2 = G,
	std::enable_if_t<internal::SupportsInverseInPlace<G2>::value>* = nullptr>
	[[nodiscard]] constexpr auto Inverse() const {
	G ret = *static_cast<const G*>(this);
	return ret.InverseInPlace();
	}

My idea is to change the content as follows.

  // Inverse: a⁻¹
  template <
      typename G2 = G,
      std::enable_if_t<internal::SupportsInverseInPlace<G2>::value>* = nullptr>
  [[nodiscard]] constexpr bool Inverse(G* inverse) const {
    *inverse = *static_cast<const G*>(this);
    return inverse->InverseInPlace();    
  }

Then it turns out you need to change all the InverseInPlace() correspondingly.

Then you need to change

tachyon/tachyon/math/finite_fields/prime_field.h

Lines 244 to 248 in c6c7f83

	constexpr PrimeField& InverseInPlace() {
	value_ = value_.template MontgomeryInverse<Config::kModulusHasSpareBit>(
	Config::kModulus, Config::kMontgomeryR2);
	return *this;
	}

  constexpr bool InverseInPlace() {
     return value_.template MontgomeryInverse<Config::kModulusHasSpareBit>(
        Config::kModulus, Config::kMontgomeryR2, &value_);
  }

Then it continues to

tachyon/tachyon/math/base/big_int.h

Lines 732 to 805 in c6c7f83

	template <bool ModulusHasSpareBit>
	constexpr BigInt MontgomeryInverse(const BigInt& modulus,
	const BigInt& r2) const {
	// See https://github.com/kroma-network/tachyon/issues/76
	CHECK(!IsZero());
	// Guajardo Kumar Paar Pelzl
	// Efficient Software-Implementation of Finite Fields with Applications to
	// Cryptography
	// Algorithm 16 (BEA for Inversion in Fp)
	BigInt u = *this;
	BigInt v = modulus;
	BigInt b = r2;
	BigInt c = BigInt::Zero();
	while (!u.IsOne() && !v.IsOne()) {
	while (u.IsEven()) {
	u.DivBy2InPlace();
	if (b.IsEven()) {
	b.DivBy2InPlace();
	} else {
	uint64_t carry = 0;
	b.AddInPlace(modulus, carry);
	b.DivBy2InPlace();
	if constexpr (!ModulusHasSpareBit) {
	if (carry) {
	b[N - 1] |= uint64_t{1} << 63;
	}
	}
	}
	}
	while (v.IsEven()) {
	v.DivBy2InPlace();
	if (c.IsEven()) {
	c.DivBy2InPlace();
	} else {
	uint64_t carry = 0;
	c.AddInPlace(modulus, carry);
	c.DivBy2InPlace();
	if constexpr (!ModulusHasSpareBit) {
	if (carry) {
	c[N - 1] |= uint64_t{1} << 63;
	}
	}
	}
	}
	if (v < u) {
	u.SubInPlace(v);
	if (b >= c) {
	b -= c;
	} else {
	b += (modulus - c);
	}
	} else {
	v.SubInPlace(u);
	if (c >= b) {
	c -= b;
	} else {
	c += (modulus - b);
	}
	}
	}
	if (u.IsOne()) {
	return b;
	} else {
	return c;
	}
	}

Here there is a CHECK() code to cause this issue.

  template <bool ModulusHasSpareBit>
  constexpr bool MontgomeryInverse(const BigInt& modulus,
                                     const BigInt& r2, BigInt* inverse) const {
    // See https://github.com/kroma-network/tachyon/issues/76
    if (IsZero()) return false;

     // ...

    if (u.IsOne()) {
      *inverse = b;
    } else {
      *inverse = c;
    } 
    return true;   
  }

I think this is a just start and if you compile this with the change above, you'll face many compile error because of the changing return type of Inverse(). This is how you can start with.

[chokobole]

The trade-off is other than this XXXInPlace() returns the reference of caller so that you can chain calling another method based on this reference. But InverseInPlace() can't do this.