tensorcommitment

package
v0.12.1 Latest Latest
Warning

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

Go to latest
Published: Oct 5, 2023 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrWrongSize           = errors.New("polynomial is too large")
	ErrNotSquare           = errors.New("the size of the polynomial must be a square")
	ErrProofFailedHash     = errors.New("hash of one of the columns is wrong")
	ErrProofFailedEncoding = errors.New("inconsistency with the code word")
	ErrProofFailedOob      = errors.New("the entry is out of bound")
	ErrMaxNbColumns        = errors.New("the state is full")
	ErrCommitmentNotDone   = errors.New("the proof cannot be built before the computation of the digest")
)

Functions

func Verify

func Verify(proof Proof, digest Digest, l []fr.Element, h hash.Hash) error

Verify a proof that digest is the hash of a polynomial given a proof proof: contains the linear combination of the non-encoded rows + the digest: hash of the polynomial l: random coefficients for the linear combination, chosen by the verifier h: hash function that is used for hashing the columns of the polynomial TODO make this function private and add a Verify function that derives the randomness using Fiat Shamir

Note (alex), A more convenient API would be to expose two functions, one that does FS for you and what that let you do it for yourself. And likewise for the prover.

Types

type Digest

type Digest [][]byte

commitment (TODO Merkle tree for that...) The i-th entry is the hash of the i-th columns of P, where P is written as a matrix √(m) x √(m) (m = len(P)), and the ij-th entry of M is p[m*j + i].

type Proof

type Proof struct {

	// list of entries of ̂{u} to query (see https://eprint.iacr.org/2021/1043.pdf for notations)
	EntryList []int

	// columns on against which the linear combination is checked
	// (the i-th entry is the EntryList[i]-th column)
	Columns [][]fr.Element

	// Linear combination of the rows of the polynomial P written as a square matrix
	LinearCombination []fr.Element

	// small domain, to retrieve the canonical form of the linear combination
	Domain *fft.Domain

	// root of unity of the big domain
	Generator fr.Element
}

Proof that a commitment is correct cf https://eprint.iacr.org/2021/1043.pdf page 10

func BuildProof

func BuildProof(params *TcParams, linComb []fr.Element, entryList []int, openedCols [][]fr.Element) Proof

Reconstruct the proof from the prover's outputs

type TcParams

type TcParams struct {
	// 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

	// NbRows number of rows of the matrix storing the polynomials. If a polynomial p is appended
	// whose size if not 0 mod NbRows, it is padded as p' so that len(p')=0 mod NbRows.
	NbRows int

	// Domains[1] used for the Reed Solomon encoding
	Domains [2]*fft.Domain

	// Rho⁻¹, rate of the RS code ( > 1)
	Rho int

	// Function that returns a fresh hasher. The returned hash function is used for hashing the
	// columns. We use this and not directly a hasher for threadsafety hasher. Indeed, if different
	// thread share the same hasher, they will end up mixing hash inputs that should remain separate.
	MakeHash func() hash.Hash
}

TcParams stores the public parameters of the tensor commitment

func NewTCParams

func NewTCParams(codeRate, NbColumns, NbRows int, makeHash func() hash.Hash) (*TcParams, error)

NewTensorCommitment returns a new TensorCommitment * ρ rate of the code ( > 1) * size size of the polynomial to be committed. The size of the commitment is then ρ * √(m) where m² = size

type TensorCommitment

type TensorCommitment struct {

	// State contains the polynomials that have been appended so far.
	// when we append a polynomial p, it is stored in the state like this:
	// state[i][j] = p[j*nbRows + i]:
	// p[0] 		| p[nbRows] 	| p[2*nbRows] 	...
	// p[1] 		| p[nbRows+1]	| p[2*nbRows+1]
	// p[2] 		| p[nbRows+2]	| p[2*nbRows+2]
	// ..
	// p[nbRows-1] 	| p[2*nbRows-1]	| p[3*nbRows-1] ..
	State [][]fr.Element

	// same content as state, but the polynomials are displayed as a matrix
	// and the rows are encoded.
	// encodedState = encodeRows(M_0 || .. || M_n)
	// where M_i is the i-th polynomial laid out as a matrix, that is
	// M_i_jk = p_i[i*m+j] where m = \sqrt(len(p)).
	EncodedState [][]fr.Element

	// number of columns which have already been hashed (atomic)
	NbColumnsHashed int

	// counts the number of time `Append` was called (atomic).
	NbAppendsSoFar int
	// contains filtered or unexported fields
}

TensorCommitment stores the data to use a tensor commitment

func NewTensorCommitment

func NewTensorCommitment(params *TcParams) *TensorCommitment

Initializes an instance of tensor commitment that we can use start appending value into it

func (*TensorCommitment) Append

func (tc *TensorCommitment) Append(ps ...[]fr.Element) ([][]byte, error)

Append appends p to the state. when we append a polynomial p, it is stored in the state like this: state[i][j] = p[j*nbRows + i]: p[0] | p[nbRows] | p[2*nbRows] ... p[1] | p[nbRows+1] | p[2*nbRows+1] p[2] | p[nbRows+2] | p[2*nbRows+2] .. p[nbRows-1] | p[2*nbRows-1] | p[3*nbRows-1] .. If p doesn't fill a full submatrix it is padded with zeroes.

func (*TensorCommitment) BuildProofAtOnceForTest

func (tc *TensorCommitment) BuildProofAtOnceForTest(l []fr.Element, entryList []int) (Proof, error)

BuildProofAtOnceForTest builds a proof to be tested against a previous commitment of a list of polynomials. * l the random linear coefficients used for the linear combination of size NbRows * entryList list of columns to hash l and entryList are supposed to be precomputed using Fiat Shamir

The proof is the linear combination (using l) of the encoded rows of p written as a matrix. Only the entries contained in entryList are kept.

func (*TensorCommitment) Commit

func (tc *TensorCommitment) Commit() (Digest, error)

Commit to p. The commitment procedure is the following: * Encode the rows of the state to get M' * Hash the columns of M'

func (*TensorCommitment) ProverComputeLinComb

func (tc *TensorCommitment) ProverComputeLinComb(l []fr.Element) ([]fr.Element, error)

BuildProof builds a proof to be tested against a previous commitment of a list of polynomials. * l the random linear coefficients used for the linear combination of size NbRows * entryList list of columns to hash l and entryList are supposed to be precomputed using Fiat Shamir

The proof is the linear combination (using l) of the encoded rows of p written as a matrix. Only the entries contained in entryList are kept.

func (*TensorCommitment) ProverOpenColumns

func (tc *TensorCommitment) ProverOpenColumns(entryList []int) ([][]fr.Element, error)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL