Feat/fri

[ThomasPiellard]

A basic version of the FRI protocol is now available, in ecc/curve/fr/fri.

The multiplicative version only has been implemented, it works on the prime-order subgroup of the corresponding curves.

The version is not tunable yet (only by hand), and should not be used unless careful choice of the parameters (e.g. rho, the number of rounds of verification) have been made.

It provides a working base for future work on FRI (possibly using ECFFT).

API

example:

  // random polynomial
  p := randomPolynomial(uint64(size), s)
  
  // create an iop interface, corresponding here to the FRI multiplicative version, radix 2.
  // iop implements the Iopp interface.
  iop := RADIX_2_FRI.New(uint64(size), sha256.New())
  
  // The Iopp interface implements the BuildProofOfProximity method, to create
  // a proof of proximity.
  proof, err := iop.BuildProofOfProximity(p)
  if err != nil {
  t.Fatal(err)
  }
  
  // The Iopp interface implements the VerifyProofOfProximity method, verifying
  // a proof of proximity.
  err = iop.VerifyProofOfProximity(proof)

Internally, a proof of proximity is a sequence of interactions between a prover and a verifier (made non interactive using Fiat Shamir), where each interaction consists of a Merkle path proof verification, and a consistancy check between one round to the next.

[gbotrel]

if rho is a constant, evaluation should be an array of size rho in the struct, not a slice

[gbotrel]

1-c is never < 0?

[ThomasPiellard]

no, here c is 0 or 1 here. The c-th entry contains the full Merkle path, the (1-c)-th the partial Merkle path.

[gbotrel]

remark; shouldn't his vary during the tests?

Similarly, randomPolynomial is not super random; (ie always the same form with coeff squared)

[gbotrel]

@ThomasPiellard

[gbotrel]

is it a constant? if it's not, should be made a parameter to the functions where it's needed.

[gbotrel]

deadcode

[gbotrel]

@yelhousni can you review before merge?

[gbotrel]

@ThomasPiellard why is this commented / in the PR ?