fri

Documentation

Index

• Variables
• type ProofOfProximity
• type RadixTwoFri
  • func NewRadixTwoFri(size uint64, h hash.FieldHasher, gen big.Int) RadixTwoFri
  • func (s RadixTwoFri) VerifyProofOfProximity(api frontend.API, proof ProofOfProximity) error
• type Round

Variables

var DeriveQueriesPositions = func(_ *big.Int, inputs []*big.Int, res []*big.Int) error {

	pos := inputs[0].Uint64()
	s := inputs[1].Uint64()
	nbSteps := inputs[2].Uint64()

	res[0].SetUint64(pos)
	for i := 1; i < int(nbSteps); i++ {
		a := res[i-1].Uint64()
		t := (a - (a % 2)) / 2
		b := convertCanonicalSorted(int(t), int(s/2))
		res[i].SetUint64(uint64(b))
		s = s / 2
	}

	return nil
}

deriveQueriesPositions derives the indices of the oracle function that the verifier has to pick, in sorted form. * pos is the initial position, i.e. the logarithm of the first challenge * size is the size of the initial polynomial * The result is a slice of []int, where each entry is a tuple (iₖ), such that the verifier needs to evaluate ∑ₖ oracle(iₖ)xᵏ to build the folded function (cf gnark-crypto).

In inputs, there are, in this order: * position: the initial position of the challenge (the log of the challenge) * size: the size of the multiplicative group * nbSteps: the number of steps for a round

outputs: * slice of positions to query during a round

Types

type ProofOfProximity

type ProofOfProximity struct {

	// rounds a round consists of completely folding a polynomial using FFT like structure, using
	// challenges sent by the verifier.
	Rounds []Round
}

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

type RadixTwoFri

type RadixTwoFri struct {
	// contains filtered or unexported fields
}

radixTwoFri empty structs implementing compressionFunction for the squaring function.

func NewRadixTwoFri

func NewRadixTwoFri(size uint64, h hash.FieldHasher, gen big.Int) RadixTwoFri

NewRadixTwoFri creates an FFT-like oracle proof of proximity. * h is the hash function that is used for the Merkle proofs * gen is the generator of the cyclic group of unity of size \rho * size

func (RadixTwoFri) VerifyProofOfProximity

func (s RadixTwoFri) VerifyProofOfProximity(api frontend.API, proof ProofOfProximity) error

VerifyProofOfProximity verifies the proof, by checking each interaction one by one.

type Round

type Round struct {

	// interactions series of queries from the verifier, each query is answered with a
	// Merkle proof.
	Interactions [][2]merkle.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 (cf gnark-crypto).
	Evaluation frontend.Variable
}

Round a single round of interactions between prover and verifier for fri.