Documentation
¶
Overview ¶
Package fflonk provides fflonk commitment, based on shplonk.
See https://eprint.iacr.org/2020/081.pdf for shplonk See https://eprint.iacr.org/2021/1167.pdf for fflonk.
Example (BatchOpen) ¶
This example demonstrates how to open a list of polynomials on a list of points.
// sample a list of polynomials, we have 5 packs of polynomials,
// each pack will be opened on its own set of points.
nbPacks := 5
// The first set of polynomials contains 2 polynomials, the second 3, etc.
// The i-th set of polynomials is opened on the i-th set of points. The first
// set of point contains 4 points, the second 5, etc.
nbPolynomialsPerPack := []int{2, 3, 4, 5, 6}
nbPointsPerPack := []int{4, 5, 6, 7, 8}
points := make([][]fr.Element, nbPacks)
polynomials := make([][][]fr.Element, nbPacks)
for i := 0; i < nbPacks; i++ {
polynomials[i] = make([][]fr.Element, nbPolynomialsPerPack[i])
for j := 0; j < nbPointsPerPack[i]; j++ {
// random size for the polynomials
polynomials[i][j] = make([]fr.Element, j+10)
}
// random number of points per pack
points[i] = make([]fr.Element, i+5)
}
// commit to the folded Polynomials. In each pack, we fold the polynomials in a similar way
// as in the FFT. If the given pack contains 3 polynomials P1,P2,P3, the folded polynomial
// that we commit to is P1(X^t)+XP2(X^t)+X^2P3(X^t) where t is the smallest number dividing
// r-1 bounding above the number of polynomials, which is 3 here.
var err error
digests := make([]kzg.Digest, nbPacks)
for i := 0; i < nbPacks; i++ {
digests[i], err = FoldAndCommit(polynomials[i], testSrs.Pk)
if err != nil {
panic(err)
}
}
// compute the opening proof. We first pick a hash function that will be used for the FS challenge
// derivation.
hf := sha256.New()
proof, err := BatchOpen(polynomials, digests, points, hf, testSrs.Pk)
if err != nil {
panic(err)
}
// Check the opening proof. The claimed values of the i-th pack of polynomials are the evaluation
// of the i-th pack of polynomials, evaluated on the t-th powers of points[i], where t is the smallest
// integer bounding above the number of polynomials in the pack that divides r-1, the field on which
// the polynomials are defined.
//
// For instance, proof.ClaimedValues[i][j][k] contains the evaluation of the j-th polynomial of the i-th
// pack, on points[i][k]^t, where t is defined as above.
err = BatchVerify(proof, digests, points, hf, testSrs.Vk)
if err != nil {
panic(err)
}
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( ErrRootsOne = errors.New("fr does not contain all the t-th roots of 1") ErrNbPolynomialsNbPoints = errors.New("the number of packs of polynomials should be the same as the number of pack of points") ErrInonsistentFolding = errors.New("the outer claimed values are not consistent with the shplonk proof") ErrInconsistentNumberFoldedPoints = errors.New("the number of outer claimed values is inconsistent with the number of claimed values in the shplonk proof") )
Functions ¶
func BatchVerify ¶
func BatchVerify(proof OpeningProof, digests []kzg.Digest, points [][]fr.Element, hf hash.Hash, vk kzg.VerifyingKey, dataTranscript ...[]byte) error
BatchVerify uses a proof to check that each digest digests[i] is correctly opened on the set points[i]. The digests are the commitments to the folded underlying polynomials. The shplonk proof is verified directly using the embedded shplonk proof. This function only computes the consistency between the claimed values of the underlying shplonk proof and the outer claimed values, using the fft-like folding. Namely, the outer claimed values are the evaluation of the original polynomials (so before they were folded) at the relevant powers of the points.
func Fold ¶
Fold returns p folded as in the fft, that is ∑_{i<t}Pᵢ(Xᵗ)Xⁱ. Say max{degree(P_{i})}=n-1. The total degree of the folded polynomial is t(n-1)+(t-1). The total size is therefore t(n-1)+(t-1)+1 = tn.
func FoldAndCommit ¶
FoldAndCommit commits to a list of polynomial by intertwinning them like in the FFT, that is returns ∑_{i<t}Pᵢ(Xᵗ)Xⁱ for t polynomials
Types ¶
type OpeningProof ¶
type OpeningProof struct {
// shplonk opening proof of the folded polynomials
SOpeningProof shplonk.OpeningProof
// ClaimedValues ClaimedValues[i][j] contains the values
// of fʲᵢ on Sⱼ^{|(fʲᵢ)ᵢ|}
ClaimedValues [][][]fr.Element
}
Opening fflonk proof for opening a list of list of polynomials ((fʲᵢ)ᵢ)ⱼ where each pack of polynomials (fʲᵢ)ᵢ (the pack is indexed by j) is opened on a powers of elements in the set Sʲ (indexed by j), where the power is |(fʲᵢ)ᵢ|.
implements io.ReaderFrom and io.WriterTo
func BatchOpen ¶
func BatchOpen(p [][][]fr.Element, digests []kzg.Digest, points [][]fr.Element, hf hash.Hash, pk kzg.ProvingKey, dataTranscript ...[]byte) (OpeningProof, error)
BatchOpen computes a batch opening proof of p (the (fʲᵢ)ᵢ ) on powers of points (the ((Sʲᵢ)ᵢ)ⱼ). The j-th pack of polynomials is opened on the power |(fʲᵢ)ᵢ| of (Sʲᵢ)ᵢ. digests is the list (FoldAndCommit(p[i]))ᵢ. It is assumed that the list has been computed beforehand and provided as an input to not duplicate computations.
Source Files