Unit-testing field operations

[huitseeker]

in PRs such as #9, the topic came up of whether one operation was modulo the Pallas or the Vesta modulus. I'd like to suggest a general unit-testing practice for figuring it out.

Context:

• see here for references on the moduli involved, p and q,
• There's four fields involved: {Pallas, Vesta} x {Base, Scalar}, each with a specific modulus involved (one of p or q),

In general here are remarks for working with any field, when receiving its elements as bytes:

• In general, solidity arguments are uint256, which is more bits than needed for representing numbers modulo p or q. So there are uint256 numbers n s.t. p < n ≤ 2^256 -1 (resp. q < n ≤ 2^256-1), which correspond to a field element n mod p (resp. n mod q).
• But those numbers have two byte representations: n - p (resp. n - q), aka the canonical representation, and n, the non-canonical representation.
• It's always useful to unit-test the behavior of a field operation with non-canonical scalars. There are two possible behaviors for the operation: a/ failing with an incorrect argument error (safer) b/ reducing the number before pursuing (sometimes more performant, as it can save the caller a reduction in cases where that makes sense) (*). In our case, we shall be happy with what the equivalent Rust operation does, as first approximation.
• Note that for testing this behavior, it is not a good strategy to pick a random number 0 ≤ r ≤ 2^256-1 and run it through the operation, since in most cases, there won't be a reduction involved at all: since 2^254 < p, q ≤ 2^256-1, the chances of picking an r big enough at random are astronomically small.

From which I deduce a strategy for relieving confusion w.r.t field modulus:

• when seeing a scalar operation on Pallas (resp. Vesta), a good way of testing the behavior with a non-canonical scalar is to test with q+1 (resp p+1), this implements (*),
• but a good way of testing if the used modulus is wrong (i.e. the modulus of the other field), when you have a correct Rust implementation to compare to, is to also test with p+1 (resp q+1). For instance, given p < q, if there's an input p < n < q operated on with the modulus p whereas it should be operated on modulus q, it will be reduced in the "incorrect" implementation whereas it should not in the correct implementation. That should come out in the output of the operation.

[storojs72]

A little bit more context. While porting Nova algorithms from Rust to Solidity, we used to deal with modulo multiplication/addition. While executing multiplication/addition you have two uint256 values and you don't know what modulo (p or q) to use. While debugging, if Rust implementation is at hand and you can extract input and output, it is usually sufficient to just try one modulus and if Solidity output is not equal to Rust one, opposite modulus should be used.

When we talked about this, my impression was that there is some "magic" algorithm that allows deducing whether particular uint256 value is either Pallas or Vesta field element without having reference Rust implementation to compare arithmetics output. If such algorithm would exist, we could add proper input validation (to any relevant function) that stops/reverts execution, if unexpected field element is detected. That would help to resolve the confusion. But I now think that without some additional context, we can't say anything about uint256 value which is less than p and q.

My understanding of mentioned strategy, is that it gives 100% detection whether it is Pallas or Vesta field element, while straightforward trying one or opposite modulus may potentially outcome to the situation, when they both give same output and it is still hard to say what type of field elements were used, isn't it?

cc @huitseeker

[huitseeker]

When we talked about this, my impression was that there is some "magic" algorithm that allows deducing whether particular uint256 value is either Pallas or Vesta field element without having reference Rust implementation to compare arithmetics output.

I confirm that this magic does not exist, essentially because the serialization format of those numbers as bytes is not self-describing. You can only recover the correct element if you know which field you are expecting.

Basically, if p = Pallas.P_MOD, q = Vesta.P_MOD, n = 2^ 256-1, we have 0 < p < q < n. So if you see a 256 bit number x that:

• is s.t. 0 ≤ x < p, it can be a canonical {Pallas, Vesta} x {base, scalar} field element,
• is s.t. p ≤ x < q, it can be a canonical {Vesta base, Pallas scalar} field element, or a non-canonically encoded field element (with all fields as possibilities),
• is s.t. q < x < n, it’s a non-canonically encoded field element (with all fields as possibilities),

But there are two nuances here:

Same field randomized testing is still valuable

The fact that a function is meant to work with elements of a certain field also means it should give you some guarantees about what’s going to happen outside those elements.

For instance (and don’t take the following verbatim, I’m just riffing to convey a point here), here’s how I would draft a natspec for the documentation of the pallas decompress function:

/// @title Pallas Curve Point Decompression
/// @notice Takes a lower-endian, canonical form u256 as x-coordinate of a Pallas curve point. The highest bit represents the y-coordinate sign.
/// @dev Interprets 0u256 input as the infinity point. Reverts if input cannot represent a base field element in canonical form.
/// @param x A u256 representing the x-coordinate in lower-endian, canonical form. The highest bit is the sign bit for y-coordinate.
/// @return point A Point on the Pallas curve corresponding to x or the infinity point for null input.
function decompress(u256 x) public returns (Point memory point) {
  // function implementation goes here
}

Hopefully that gives more context as to the edge cases I expect to discover with randomized testing, even if the inputs is not of any wrong field. For example, the function above should revert on any input x s.t. p ≤ x < n.

Wrong field testing can (sometimes) detect more specific bugs in the implementation

Let’s assume I test the above function (pallas point decompression) with inputs x s.t. p < x < q, and y s.t. p < y <q. If I observe that my function reverts on y but not on x, there’s a good chance that I used a Vesta.P_MOD (== Pallas.R_MOD) where I should have used a Pallas.P_MOD in the implementation.

Does this make things more clear?

[storojs72]

Yes. Kind of. So, you are hinting on paying more attention on implementing functionality (that operates with field elements) with stricter input validation against input uint256s, and supplying more "negative" testing, when for example non-canonical representations are passed, while canonical ones are expected or when Pallas field elements passed, while Vesta ones are expected. Am I correctly understanding your point?

[huitseeker]

@storojs72 Yep, I believe you got it. Negative testing of the u256 representation rocks, and by being careful about which "use cases" we generate in that negative testing we can sometimes notice not only a mistake, but a field mismatch.