affine versioned pairing supporting for BitVM

[PayneJoe]

Description

This PR propose is to give caller an another more option to choose when do pairing. In current implementation, the coefficients of divisor line function is computed through projective coordinates as it's more efficient (than affine coordinates) when computing pairings, while it's not when verifying pairings (recursive snark). As Andrija and Liam stated in 5.2 section of On Proving Pairings.

So for supporting verifying pairings for BN254 in BitVM, I add one more optional method for pairing.

closes: #XXXX

---

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [x] Targeted PR against correct branch (master)
• [x] Linked to GitHub issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [x] Wrote unit tests
• [x] Updated relevant documentation in the code
• [x] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [x] Re-reviewed Files changed in the GitHub PR explorer

[swasilyev]

So this pairing computation results in another target group element?

[PayneJoe]

So this pairing computation results in another target group element?

the test result proves that it's equal with current pairing result (same element of Gt), even so for the sake of consistency with script implementation in BitVM we need a benchmark, this pairing in arkworks is my benchmark

[swasilyev]

Eh. Why then we need code that computes the same result in a supposedly slower way?

[PayneJoe]

Eh. Why then we need code that computes the same result in a supposedly slower way?

Okay, let me introduce a naive and toy case to explain why we need that, what the benchmark actually mean.

If I want to implement a division algorithm for two numbers (whatever number is okay, even big integer) with javascript language, say a / b. I might need a benchmark to test if my javascript versioned algorithm is right. By now we do not have the same algorithm (a / b) implementation in C++, we only have the equivalence algorithm, say a * 1/b.

So if I use assertion javascript(a / b) == c++(a * 1/b) in my unit test, someone else may argue that this test is not convincing enough since the two algorithms are not consistent with each other, javascript(a / b) == c++(a / b) is just what I want.

[PayneJoe]

Eh. Why then we need code that computes the same result in a supposedly slower way?

PS: Most of the time, you are computing pairings (in snark verifier), so projective is your option, if you are verifying pairings, affine is your option. It's the best option for recursive snark.

[weikengchen]

I think what will happen with this PR is that it would be held off until the R1CS gadget for verifying affine pairing is done. If the value is the same, we do not need this in algebra, and the R1CS witness generation would be in R1CS.