Consensys / linea-arithmetization

17 stars 18 forks source link

ECPAIRING test vectors #822

Open OlivierBBB opened 3 days ago

OlivierBBB commented 3 days ago

Below is a description of many of the various tests scenarios which we should cover in the arithmetization to test it. We also include some tests (with large n's) that are of use potentially for GNARK + the glue as they will test the circuit's ability to accumulate the results of Miller loops and do a large final exponentiation.

1 point:
========

- ICP fail / success
  - Failure cases: 2 * 2 * 2 - 1 = 7 ways to fail;
    - coordinates out of range for small point
    - small point not on the curve
    - coordinates out of range for large point
  - Success: 1 way to succeed
    - well-formedness of pair of points:
      - Failure: 2 ways to fail ( B not on C2 ? on C2  but not on G2 ?)
      - Success: 4 ways of succeeding:

         | small point A | ≡ ∞ | ≠ ∞ |
         | large point B | ≡ ∞ | ≠ ∞ |

         ( ★  ) case analysis:
          - [B ≡ ∞]: should trigger nothing (CS_ECPAIRING = 0, CS_G2_MEMBERSHIP = 0)
          - [B ≠ ∞] ∧ [A ≡ ∞]: should trigger nothing (CS_ECPAIRING = 0, CS_G2_MEMBERSHIP = 1)
          - [B ≠ ∞] ∧ [A ≠ ∞]: should trigger nothing (CS_ECPAIRING = 1, CS_G2_MEMBERSHIP = 0)

FAILURE_KNOWN_TO_RAM: 7 + 2  test scenarios
RAM_SUCCESS: 3 cases (or 4 is we include the distinction on [A ≡ ∞ ?] in the first case)

n points:
=========

n = number of pairs of points (n = 2, 3, 4 for the extensive tests; and maybe some larger thing to test GNARK's ability to chain the Miller loops)

- ICP failure:
- ICP success:
  - one or more of the B_k are malformed [check with 1 malformed and also with 2 or more]:
    - expect to see: (SUCCESS_BIT = 0, CS_ECPAIRING = 0, CS_G2_MEMBERSHIP = 1 @ first malformed k)
    - we have 2 ways to be malformed but we can be malformed (1) more than once (2) for different reasons
  - all of the B_k are wellformed
    - expect to see: (SUCCESS_BIT = 1)
    - if TRIVIAL_PAIRING = 1 case (all B_k's are infinity) then the arithmetization sets the RESULT to 1 + the arithmetization sets the SUCCESS_BIT = 1)
    - it TRIVIAL_PAIRING = 0
      - k by k we have the same analysis as in the 1 point case ( ★  )

FAILURE_KNOWN_TO_RAM:
- 7 + (2 * n + 4 * n(n-1)/2 + ...) = 7 + (1 + 2)^n test scenarios (the same as before + we have a choice for where it fails, how often, several failure conditions at once etc ...) 2 * n ≡ 2 ways to fail at a position 1 ≤ k ≤ n, 4 * n(n-1)/2 ways to fail at 2 positions etc ...

RAM_SUCCESS test cases we want to test:
- TRIVIAL_PAIRING = 1
  - all the B_k's are ∞, and we can freely select the A_k's to be a mixture of ∞'s and nontrivial points
  - 2 ^ n choices for (which of the A_k are ≡ ∞)
- TRIVIAL_PAIRING = 0
  - all of the pairs of points are ACCEPTABLE_PAIR_OF_POINTS
  - only some are and we require CS_G2_MEMBERSHIP_TEST