Feat/plookup

[ThomasPiellard]

Summary

This PR integrates plookup, the vector version and table version, and a protocol to prove that 2 commitments are permuted versions of one another.

Description

The protocol relies on the KZG commitment scheme but it can be used with any polynomial commitment scheme.

Table

A Table is a slice of fr.Element, on which the Sort method can be called. The API takes Table as parameters.

Lookup vector

func ProveLookupVector(srs *kzg.SRS, f, t Table) (ProofLookupVector, error) where the srs is the public srs used for KZG. It generates a proof that f contains only elements that are in t. f and t need not be of the same size.

The verification function is ProveLookupVector(srs *kzg.SRS, f, t Table) (ProofLookupVector, error).

Lookup table

func ProveLookupTables(srs *kzg.SRS, f, t []Table) (ProofLookupTables, error) generates a proof that of the columns of f (represented by a list of Table) are all in t. The rows of f and t need this time to be of the same size.

The verification function is VerifyLookupTables(srs *kzg.SRS, proof ProofLookupTables) error `

Permutation

func Prove(srs *kzg.SRS, t1, t2 []fr.Element) (Proof, error), generates a proof the t1 and t2 are permuted versions of one another.

The verification function is Verify(srs *kzg.SRS, proof Proof) error

Example

Here is a full example for generating a lookup vector proof.

First, one needs to generate the public lookup vector:

        srs, err := kzg.NewSRS(8192, big.NewInt(13))
	if err != nil {
		t.Fatal(err)
	}

	// lookup vector, publicly available
	lookupVector := make(Table, 4096)
	for i := 0; i < 4096; i++ {
		lookupVector[i].SetUint64(uint64((3 * i) % 4096))
	}

The public lookup vector needs to be committed somewhere. We commit it, but before we sort it. The reason is that in the proof, there is a commitment to the sorted version of the lookup vector.

       // domain to switch basis
	d := fft.NewDomain(4096, 0, false)

	// The lookup vector is committed somewhere. We commit it, but before we sort it.
	sort.Sort(lookupVector)
	clookupVector := make([]fr.Element, 4096)
	copy(clookupVector, lookupVector)
	d.FFTInverse(clookupVector, fft.DIF, 0)
	fft.BitReverse(clookupVector)
	lookupVectorCommitment, _ := kzg.Commit(clookupVector, srs)

Now we generate a vector whose entries are in the lookup vector.

        // vector composed of elements in the lookupVector
	fvector := make(Table, 1000)
	for i := 0; i < 1000; i++ {
		fvector[i].Set(&lookupVector[(8*i)%4096])
	}

We build the proof:
proof, _ := ProveLookupVector(srs, fvector, lookupVector)

Now to verify the proof, we check that the t field in the proof corresponds to the commitment of the lookup vector. It will because the lookup vector has been committed sorted. Were that not the case, the prover should have had published a permutation proof the the tfield of the proof is a commitment of a permuted version of the lookup vector.

          // check that the proof.t field corresponds to the public lookup commitment
          if !proof.t.Equal(&lookupVectorCommitment) {
	          t.Fatal("public commitment is not recognized")
          }
          
          err = VerifyLookupVector(srs, proof)
          if err != nil {
	          t.Fatal(err)
          }

The reason why the lookupVectorCommitment is done as a side step and is not in the the signature. of VerifyLookupVector is that the proof is a standalone object, and I can imagine that in certain situations one would only want to check consistency of a proof alone.

Internal

The implementation follows the ideas of the paper with some adaptations. The permutation proof is used for a technical reason but can be useful in itself for various protocols. The technical reason is the following. In the LookupTable version, the rows of t are folded using a random challenge, and then the LookupVector is called on the result, but the LookupVector prover needs to sort the table t beforehand. The LookupVector proof contains a commitment to the sorted version of t. In the vector case it's not a problem because t can be committed sorted. In the Table case, it becomes a problem because the challenge changes each time, so the order cannot be known in advance. The solution that I came up with is to generate a permutation proof that the folded commitment of t is in fact a permutation of the folded commitment of the public t.

Note: at some point in the plookup protocol, 2 vectors f and t need to be concatenated, and sorted so the values of f appear in the same order as in t. I didn't find an efficient algo to do it, so I just concatenated the 2 vectors and sorted the result. If an efficient algo to do so can be found then the permutation proof can be avoided.

Status

The tests are passing.
The algos do not use channel or anything and the efficiency can be improved.