Use proptests to improve test coverage

[emmorais]

Proptest allows us to cover important edge cases in the implementation of arithmetic and cryptographic layers. Those edge cases, if not correctly implemented, could potentially lead to vulnerabilities. Having a robust testing framework is an important requirement for the construction of secure systems.

Things we need to do first:

• [ ] To help us find edge cases: #56
• [ ] For smaller polynomials: #59

Goals:

• [ ] Implement edge cases for the cyclotomic ring
• [ ] Establish the pattern that will be followed along the project. The goal of this task is not finish test coverage, but to initiate its utilization. As such, we must focus on a first set of tests, which later will serve as model to extend it to the whole project as we add more components. This means we want to define how those tests will be developed, leaving documentation that will make it easier to add new tests later.

Tasks:

• [ ] Set opt-level for the proptest and rand crates: https://proptest-rs.github.io/proptest/proptest/tips-and-best-practices.html#setting-opt-level

Specific tests:

• [ ] A test on a uniformly random polynomial with unlimited size coefficients, generated using rand_poly(). And if there is an inverse, check the inverse property.

[teor2345]

• Implement edge cases for the cyclotomic ring.

Unfortunately, proptest does not help with finding uncommon edge cases: https://proptest-rs.github.io/proptest/proptest/limitations.html

So if we want to find edge cases, we can:

• create tests with hard-coded known edge cases (this seems like another ticket), or
• use a polynomial which can be exhaustively explored at random (this ticket).

Currently Fq4 has 8 coefficients of 3 bits each: https://github.com/Inversed-Tech/eyelid/blob/3af9a81f0cf51d217b3124957e9c12a015ef3d2d/eyelid-match-ops/src/primitives/poly/fq/fq_tiny.rs#L10-L11

2^24 is a large solution space that could take a while to explore for expensive operations. For example, an exhaustive multiplication check on one coefficient would take ~10ms multiplication * 2^24 polynomial a * constant polynomial b = 2 days. (For 2 random polynomials, 8 coefficients would take tens of thousands of years.)

So we might want to do proptests with a single random parameter with 4 coefficients, and two random parameters with 2 coefficients. This is a trivial change after PR #47 merges, but the Karatsuba multiplication would need a bug fix to handle small numbers of coefficients. If the fix skips some of the code, we'd also need proptests with 8 and 2048 coefficients.

An exhaustive check on 4 or 2*2 coefficients would take 40 seconds.

I'll open a ticket for this, and add it to the description of this ticket.