fri

Documentation

Overview

Package fri provides the FRI (multiplicative) commitment scheme.

Index

• Variables
• func GetRho() int
• type Digest
• type IOPP
  • func (iopp IOPP) New(size uint64, h hash.Hash) Iopp
• type Iopp
• type MerkleProof
• type OpeningProof
• type ProofOfProximity
• type Round

Variables

var (
	ErrLowDegree            = errors.New("the fully folded polynomial in not of degree 1")
	ErrProximityTestFolding = errors.New("one round of interaction failed")
	ErrOddSize              = errors.New("the size should be even")
	ErrMerkleRoot           = errors.New("merkle roots of the opening and the proof of proximity don't coincide")
	ErrMerklePath           = errors.New("merkle path proof is wrong")
	ErrRangePosition        = errors.New("the asked opening position is out of range")
)

Functions

func GetRho

func GetRho() int

GetRho returns the factor ρ = size_code_word/size_polynomial

Types

type Digest

type Digest []byte

Digest commitment of a polynomial.

type IOPP

type IOPP uint

IOPP Interactive Oracle Proof of Proximity

const (
	// Multiplicative version of FRI, using the map x->x², on a
	// power of 2 subgroup of Fr^{*}.
	RADIX_2_FRI IOPP = iota
)

func (IOPP) New

func (iopp IOPP) New(size uint64, h hash.Hash) Iopp

New creates a new IOPP capable to handle degree(size) polynomials.

type Iopp

type Iopp interface {

	// BuildProofOfProximity creates a proof of proximity that p is d-close to a polynomial
	// of degree len(p). The proof is built non interactively using Fiat Shamir.
	BuildProofOfProximity(p []fr.Element) (ProofOfProximity, error)

	// VerifyProofOfProximity verifies the proof of proximity. It returns an error if the
	// verification fails.
	VerifyProofOfProximity(proof ProofOfProximity) error

	// Opens a polynomial at gⁱ where i = position.
	Open(p []fr.Element, position uint64) (OpeningProof, error)

	// Verifies the opening of a polynomial at gⁱ where i = position.
	VerifyOpening(position uint64, openingProof OpeningProof, pp ProofOfProximity) error
}

Iopp interface that an iopp should implement

type MerkleProof

type MerkleProof struct {

	// Merkle root
	MerkleRoot []byte

	// ProofSet stores [leaf ∥ node_1 ∥ .. ∥ merkleRoot ], where the leaf is not
	// hashed.
	ProofSet [][]byte
	// contains filtered or unexported fields
}

merkleProof helper structure to build the merkle proof At each round, two contiguous values from the evaluated polynomial are queried. For one value, the full Merkle path will be provided. For the neighbor value, only the leaf is provided (so ProofSet will be empty), since the Merkle path is the same as for the first value.

type OpeningProof

type OpeningProof struct {
	ProofSet [][]byte

	// ClaimedValue value of the leaf. This field is exported
	// because it's needed for protocols using polynomial commitment
	// schemes (to verify an algebraic relation).
	ClaimedValue fr.Element
	// contains filtered or unexported fields
}

MerkleProof used to open a polynomial

type ProofOfProximity

type ProofOfProximity struct {

	// ID unique ID attached to the proof of proximity. It's needed for
	// protocols using Fiat Shamir for instance, where challenges are derived
	// from the proof of proximity.
	ID []byte

	// round contains the data corresponding to a single round
	// of fri. There are nbRounds rounds of Interactions.
	Rounds []Round
}

ProofOfProximity proof of proximity, attesting that a function is d-close to a low degree polynomial.

It is composed of a series of Interactions, emulated with Fiat Shamir,

type Round

type Round struct {

	// stores the Interactions between the prover and the verifier.
	// Each interaction results in a set or merkle proofs, corresponding
	// to the queries of the verifier.
	Interactions [][2]MerkleProof

	// evaluation stores the evaluation of the fully folded polynomial.
	// The fully folded polynomial is constant, and is evaluated on a
	// a set of size \rho. Since the polynomial is supposed to be constant,
	// only one evaluation, corresponding to the polynomial, is given. Since
	// the prover cannot know in advance which entry the verifier will query,
	// providing a single evaluation
	Evaluation fr.Element
}

round contains the data corresponding to a single round of fri. It consists of a list of Interactions between the prover and the verifier, where each interaction contains a challenge provided by the verifier, as well as MerkleProofs for the queries of the verifier. The Merkle proofs correspond to the openings of the i-th folded polynomial at 2 points that belong to the same fiber of x -> x².