vortex

package
v0.0.0-...-4af87b5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 6, 2024 License: Apache-2.0 Imports: 25 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrInvalidVerifierInputs flags a verifier input with invalid dimensions.
	ErrInvalidVerifierInputs = errors.New("invalid verification input")
)
View Source 
var (
	ErrPNotOfSizeCardinality = errors.New("p should be of size cardinality")
)

Functions

func AllocateCircuitVariablesWithMerkleTree 

func AllocateCircuitVariablesWithMerkleTree(
	verifyCircuit *VerifyOpeningCircuitMerkleTree,
	proof OpeningProof,
	ys [][]field.Element,
	entryList []int,
	roots []types.Bytes32)

allocate the variables for the verification circuit with Merkle trees

func AssignCicuitVariablesWithMerkleTree 

func AssignCicuitVariablesWithMerkleTree(
	verifyCircuit *VerifyOpeningCircuitMerkleTree,
	proof OpeningProof,
	ys [][]field.Element,
	entryList []int,
	roots []types.Bytes32)

AssignCicuitVariablesWithMerkleTree assign the variables for the verification circuit with Merkle trees

func FFTInverse 

func FFTInverse(api frontend.API, p []frontend.Variable, genInv fr.Element, cardinality uint64) ([]frontend.Variable, error)

computes fft^-1(p) where the fft is done on <generator>, a set of size cardinality. It is assumed that p is correctly sized.

The fft is hardcoded with bls12-377 for now, to be more efficient than bigInt... It is assumed that p is of size cardinality.

func FFTInverseBLS12377 

func FFTInverseBLS12377(_ *big.Int, inputs []*big.Int, results []*big.Int) error

FFTInverseBLS12377 hint for the inverse FFT on BN254 (the frField is harcoded...)

func GnarkVerifyCommon 

func GnarkVerifyCommon(
	api frontend.API,
	params GParams,
	proof GProofWoMerkle,
	x frontend.Variable,
	ys [][]frontend.Variable,
	randomCoin frontend.Variable,
	entryList []frontend.Variable,
) ([][]frontend.Variable, error)

func GnarkVerifyOpeningWithMerkleProof 

func GnarkVerifyOpeningWithMerkleProof(
	api frontend.API,
	params GParams,
	roots []frontend.Variable,
	proof GProof,
	x frontend.Variable,
	ys [][]frontend.Variable,
	randomCoin frontend.Variable,
	entryList []frontend.Variable,
) error

func VerifyOpening 

func VerifyOpening(v *VerifierInputs) error

VerifyOpening verifies a Vortex opening proof, see VerifierInputs for more details. The function returns an error on failure. The function validates the dimensions of the items in the proof and returns an error if they are inconsistent with the parameters. If the provided parameters are invalid themselves the function may panic.

Types

type EncodedMatrix 

type EncodedMatrix []smartvectors.SmartVector

EncodedMatrix represents the witness of a Vortex matrix commitment, it is represented as an array of rows.

type GParams 

type GParams struct {
	Key         ringsis.Key
	HasherFunc  func(frontend.API) (hash.FieldHasher, error)
	NoSisHasher func(frontend.API) (hash.FieldHasher, error)
}

Gnark params

func (*GParams) HasNoSisHasher 

func (p *GParams) HasNoSisHasher() bool

type GProof 

type GProof struct {
	GProofWoMerkle
	MerkleProofs [][]smt.GnarkProof
}

Opening proof with Merkle proofs

type GProofWoMerkle 

type GProofWoMerkle struct {

	// columns on against which the linear combination is checked
	// (the i-th entry is the EntryList[i]-th column). The columns may
	// as well be dispatched in several matrices.
	// Columns [i][j][k] returns the k-th entry of the j-th selected
	// column of the i-th commitment
	Columns [][][]frontend.Variable

	// domain of the RS code
	RsDomain *fft.Domain

	// Rate of the RS code, Blowup factor in Vortex, inverse rate to be precise
	Rate uint64

	// Linear combination of the rows of the polynomial P written as a square matrix
	LinearCombination []frontend.Variable
}

Opening proof without Merkle proofs

type MerkleCommitment 

type MerkleCommitment field.Element

MerkleCommitment represents a (merkle-mode) Vortex commitment

type OpeningProof 

type OpeningProof struct {
	// Columns against which the linear combination is checked (the i-th
	// entry is the EntryList[i]-th column). The columns may as well be
	// dispatched in several matrices. Columns [i][j][k] returns the k-th entry
	// of the j-th selected column of the i-th commitment
	Columns [][][]field.Element

	// Linear combination of the Reed-Solomon encoded polynomials to open.
	LinearCombination smartvectors.SmartVector

	// MerkleProofs store a list of [smt.Proof] (Merkle proofs) allegedly
	// attesting the membership of the columns in the commitment tree.
	//
	// MerkleProofs[i][j] corresponds to the Merkle proof attesting the j-th
	// column of the i-th commitment root hash.
	MerkleProofs [][]smt.Proof
}

OpeningProof represents an opening proof for a Vortex commitment. The proof possibly relates to several commitments simultaneously. This corresponds to the batch settings.

func (*OpeningProof) Complete 

func (proof *OpeningProof) Complete(
	entryList []int,
	committedMatrices []EncodedMatrix,
	trees []*smt.Tree,
)

Complete completes the proof adding the columns pointed by entryList (implictly the random positions pointed to by the verifier).

type Params 

type Params struct {
	// Key stores the public parameters of the ring-SIS instance in use to
	// hash the columns.
	Key ringsis.Key
	// BlowUpFactor corresponds to the inverse-rate of the Reed-Solomon code
	// in use to encode the rows of the committed matrices. This is a power of
	// two and
	BlowUpFactor int
	// Domain[0]: domain to perform the FFT^-1, of size NbColumns is meant to
	// be run over the non-encoded rows when RS encoding.
	// Domain[1]: domain to perform FFT, of size BlowUp * NbColumns is meant
	// to be obtain the codeword when RS encoding.
	Domains [2]*fft.Domain
	// NbColumns number of columns of the matrix storing the polynomials. The
	// total size of the polynomials which are committed is NbColumns x NbRows.
	// The Number of columns is a power of 2, it corresponds to the original
	// size of the codewords of the Reed Solomon code.
	NbColumns int
	// MaxNbRows number of rows of the matrix storing the polynomials. If a
	// polynomial p is appended whose size if not 0 mod MaxNbRows, it is padded
	// as p' so that len(p')=0 mod MaxNbRows.
	MaxNbRows int
	// HashFunc is an optional function that returns a `hash.Hash` it is used
	// when vortex is used in "Merkle-tree" mode. In this case, the hash
	// function is mandatory.
	HashFunc func() hash.Hash
	// NoSisHashFunc is an optional hash function that is used in place of the
	// SIS. If it is set,
	NoSisHashFunc func() hash.Hash
}

Params collects the public parameters of the commitment scheme. The object should not be constructed directly (use [NewParamsSis] or [NewParamsNoSis]) instead nor be modified after having been constructed.

func NewParams 

func NewParams(
	blowUpFactor int,
	nbColumns int,
	maxNbRows int,
	sisParams ringsis.Params,
	merkleHashFunc func() hash.Hash,
) *Params

NewParams creates and returns a Params:

  • blowUpFactor: inverse-rate of the RS code ( > 1). Must be a power of 2.
  • nbColumns: the number of columns in the witness matrix
  • maxNbRows: the maximum number of rows in the witness matrix
  • sisParams: the parameters of the SIS instance to use to hash the columns
  • merkleHashFunc: the hash function to use to hash the SIS hashes into a Merkle-tree.

func (*Params) CommitMerkle 

func (p *Params) CommitMerkle(ps []smartvectors.SmartVector) (encodedMatrix EncodedMatrix, tree *smt.Tree, colHashes []field.Element)

Commit to a sequence of columns and Merkle hash on top of that. Returns the tree and an array containing the concatenated columns hashes. The final short commitment can be obtained from the returned tree as: 

tree.Root()

And can be safely converted to a field Element via field.Element.SetBytesCanonical

func (*Params) HasSisReplacement 

func (p *Params) HasSisReplacement() bool

HasSisReplacement returns true if the parameters are set to not use SIS

func (*Params) InitOpeningWithLC 

func (params *Params) InitOpeningWithLC(committedSV []smartvectors.SmartVector, randomCoin field.Element) *OpeningProof

InitOpeningWithLC initiates the construction of a Vortex proof by returning the encoding of the linear combinations of the committed row-vectors contained in committedSV by the successive powers of randomCoin.

The returned proof is partially assigned and must be completed using [WithEntryList] to conclude the opening protocol.

In the batch settings, the committedSV must be provided as the flattened list of the committed matrices. This contrasts with the API of the other functions and is motivated by the fact that this is simpler to construct in our settings.

func (*Params) NumEncodedCols 

func (p *Params) NumEncodedCols() int

NumEncodedCols returns the number of columns in the encoded matrix, equivalently this is the size of the codeword-rows.

func (*Params) RemoveSis 

func (p *Params) RemoveSis(h func() hash.Hash) *Params

RemoveSis set the Vortex parameters to use another hash function than SIS

type VerifierInputs 

type VerifierInputs struct {
	// Params are the public parameters
	Params Params
	// MerkleRoots are the commitment to verify the opening for
	MerkleRoots []types.Bytes32
	// X is the univariate evaluation point
	X field.Element
	// Ys are the alleged evaluation at point X
	Ys [][]field.Element
	// OpeningProof contains the messages of the prover
	OpeningProof OpeningProof
	// RandomCoin is the random coin sampled by the verifier to be used to
	// construct the linear combination of the columns.
	RandomCoin field.Element
	// EntryList is the random coin representing the columns to open.
	EntryList []int
}

VerifierInputs represents the statement made by the prover in the opening protocol of Vortex. It stands for univariate evaluation as desribed in the paper. The struct stands for the input of the checks of the verifier, it does not cover the construction of the random coins.

Thus, the caller is responsible for handling the construction of RandomCoin and EntryList as they are the random coins. It can be done by sampling them at random in the interactive setting or using the Fiat-Shamir heuristic.

In our settings, the caller is a function in a framework managing the random coins as Vortex is used a sub-protocol of a larger protocol.

type VerifyOpeningCircuitMerkleTree 

type VerifyOpeningCircuitMerkleTree struct {
	Proof      GProof                `gnark:",public"`
	Roots      []frontend.Variable   `gnark:",public"`
	X          frontend.Variable     `gnark:",public"`
	RandomCoin frontend.Variable     `gnark:",public"`
	Ys         [][]frontend.Variable `gnark:",public"`
	EntryList  []frontend.Variable   `gnark:",public"`
	Params     GParams
}

Final circuit - commitment using Merkle trees

func (*VerifyOpeningCircuitMerkleTree) Define 

func (circuit *VerifyOpeningCircuitMerkleTree) Define(api frontend.API) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.