kzg

package module
v0.0.0-...-2b8a2f7 Latest Latest
Warning

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

 Go to latest Published: Nov 23, 2022 License: MIT Imports: 4 Imported by: 0

README

KZG and FFT utils

This repo is from https://github.com/protolambda/go-kzg with adjustments made to integrate with https://github.com/hyperproofs/hyperproofs-go

This repo is super experimental.

This is an implementation in Go, initially aimed at chunkification and extension of data, and building/verifying KZG proofs for the output data. The KZG proofs, or Kate proofs, are built on top of BLS12-381.

Part of a low-latency data-availability sampling network prototype for Eth2 Phase 1. See https://github.com/protolambda/eth2-das

Code is based on:

Features:

  • (I)FFT on F_r
  • (I)FFT on G1
  • Specialized FFT for extension of F_r data
  • KZG
    • commitments
    • generate/verify proof for single point
    • generate/verify proofs for multiple points
    • generate/verify proofs for all points, using FK20
    • generate/verify proofs for ranges (cosets) of points, using FK20
  • Data recovery: given an arbitrary subset of data (at least half), recover the rest
  • Optimized for Data-availability usage
  • Change Bignum / BLS with build tags.

BLS

Currently supported BLS implementations: Herumi BLS and Kilic BLS (default).

Field elements (Fr)

The BLS curve order is used for the modulo math, different libraries could be used to provide this functionality. Note: some of these libraries do not have full BLS functionality, only Bignum / uint256. The KZG code will be excluded when compiling with a non-BLS build tag.

Build tag options:

  • (no build tags, default): Use Kilic BLS library. Previously used by bignum_kilic build tag. kilic/bls12-381
  • -tags bignum_hbls: use Herumi BLS library. herumi/bls-eth-go-binary
  • -tags bignum_hol256: Use the uint256 code that Geth uses, holiman/uint256
  • -tags bignum_pure: Use the native Go Bignum implementation.

Benchmarks

See BENCH.md for benchmarks of FFT, FFT in G1, FFT-extension, zero polynomials, and sample recovery.

License

MIT, see LICENSE file.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CommitToEvalPoly 

func CommitToEvalPoly(secretG1IFFT []bls.G1Point, eval []bls.Fr) *bls.G1Point

KZG commitment to polynomial in evaluation form, i.e. eval = FFT(coeffs). The eval length must match the prepared KZG settings width.

func GenerateTestingSetup 

func GenerateTestingSetup(secret string, n uint64) ([]bls.G1Point, []bls.G2Point)

GenerateTestingSetup creates a setup of n values from the given secret. **for testing purposes only**

Types

type FFTSettings 

type FFTSettings struct {
	MaxWidth uint64
	// the generator used to get all roots of unity
	RootOfUnity *bls.Fr
	// domain, starting and ending with 1 (duplicate!)
	ExpandedRootsOfUnity []bls.Fr
	// reverse domain, same as inverse values of domain. Also starting and ending with 1.
	ReverseRootsOfUnity []bls.Fr
}

func NewFFTSettings 

func NewFFTSettings(maxScale uint8) *FFTSettings

func (*FFTSettings) DASFFTExtension 

func (fs *FFTSettings) DASFFTExtension(vals []bls.Fr)

Takes vals as input, the values of the even indices. Then computes the values for the odd indices, which combined would make the right half of coefficients zero. Warning: the odd results are written back to the vals slice.

func (*FFTSettings) ErasureCodeRecover 

func (fs *FFTSettings) ErasureCodeRecover(vals []*bls.Fr) ([]bls.Fr, error)

func (*FFTSettings) FFT 

func (fs *FFTSettings) FFT(vals []bls.Fr, inv bool) ([]bls.Fr, error)

func (*FFTSettings) FFTG1 

func (fs *FFTSettings) FFTG1(vals []bls.G1Point, inv bool) ([]bls.G1Point, error)

func (*FFTSettings) InplaceFFT 

func (fs *FFTSettings) InplaceFFT(vals []bls.Fr, out []bls.Fr, inv bool) error

func (*FFTSettings) RecoverPolyFromSamples 

func (fs *FFTSettings) RecoverPolyFromSamples(samples []*bls.Fr, zeroPolyFn ZeroPolyFn) ([]bls.Fr, error)

func (*FFTSettings) ShiftPoly 

func (fs *FFTSettings) ShiftPoly(poly []bls.Fr)

unshift poly, in-place. Multiplies each coeff with 1/shift_factor**i

func (*FFTSettings) UnshiftPoly 

func (fs *FFTSettings) UnshiftPoly(poly []bls.Fr)

unshift poly, in-place. Multiplies each coeff with shift_factor**i

func (*FFTSettings) ZeroPolyViaMultiplication 

func (fs *FFTSettings) ZeroPolyViaMultiplication(missingIndices []uint64, length uint64) ([]bls.Fr, []bls.Fr)

Calculate the minimal polynomial that evaluates to zero for powers of roots of unity that correspond to missing indices.

This is done simply by multiplying together `(x - r^i)` for all the `i` that are missing indices, using a combination of direct multiplication (makeZeroPolyMulLeaf) and iterated multiplication via convolution (reduceLeaves)

Also calculates the FFT (the "evaluation polynomial").

type FK20MultiSettings 

type FK20MultiSettings struct {
	*KZGSettings
	// contains filtered or unexported fields
}

func NewFK20MultiSettings 

func NewFK20MultiSettings(ks *KZGSettings, n2 uint64, chunkLen uint64) *FK20MultiSettings

func (*FK20MultiSettings) DAUsingFK20Multi 

func (ks *FK20MultiSettings) DAUsingFK20Multi(polynomial []bls.Fr) []bls.G1Point

Computes all the KZG proofs for data availability checks. This involves sampling on the double domain and reordering according to reverse bit order

func (*FK20MultiSettings) FK20Multi 

func (ks *FK20MultiSettings) FK20Multi(polynomial []bls.Fr) []bls.G1Point

For a polynomial of size n, let w be a n-th root of unity. Then this method will return k=n/l KZG proofs for the points 

proof[0]: w^(0*l + 0), w^(0*l + 1), ... w^(0*l + l - 1)
proof[0]: w^(0*l + 0), w^(0*l + 1), ... w^(0*l + l - 1)
...
proof[i]: w^(i*l + 0), w^(i*l + 1), ... w^(i*l + l - 1)
...

func (*FK20MultiSettings) FK20MultiDAOptimized 

func (ks *FK20MultiSettings) FK20MultiDAOptimized(polynomial []bls.Fr) []bls.G1Point

FK20 multi-proof method, optimized for dava availability where the top half of polynomial coefficients == 0

type FK20SingleSettings 

type FK20SingleSettings struct {
	*KZGSettings
	// contains filtered or unexported fields
}

func NewFK20SingleSettings 

func NewFK20SingleSettings(ks *KZGSettings, n2 uint64) *FK20SingleSettings

func (*FK20SingleSettings) DAUsingFK20 

func (fk *FK20SingleSettings) DAUsingFK20(polynomial []bls.Fr) []bls.G1Point

Computes all the KZG proofs for data availability checks. This involves sampling on the double domain and reordering according to reverse bit order

func (*FK20SingleSettings) FK20Single 

func (fk *FK20SingleSettings) FK20Single(polynomial []bls.Fr) []bls.G1Point

Compute all n (single) proofs according to FK20 method

func (*FK20SingleSettings) FK20SingleDAOptimized 

func (fk *FK20SingleSettings) FK20SingleDAOptimized(polynomial []bls.Fr) []bls.G1Point

Special version of the FK20 for the situation of data availability checks: The upper half of the polynomial coefficients is always 0, so we do not need to extend to twice the size for Toeplitz matrix multiplication

type KZGSettings 

type KZGSettings struct {
	*FFTSettings

	// setup values
	// [b.multiply(b.G1, pow(s, i, MODULUS)) for i in range(WIDTH+1)],
	SecretG1 []bls.G1Point
	// [b.multiply(b.G2, pow(s, i, MODULUS)) for i in range(WIDTH+1)],
	SecretG2 []bls.G2Point
}

func NewKZGSettings 

func NewKZGSettings(fs *FFTSettings, secretG1 []bls.G1Point, secretG2 []bls.G2Point) *KZGSettings

func (*KZGSettings) CheckProofMulti 

func (ks *KZGSettings) CheckProofMulti(commitment *bls.G1Point, proof *bls.G1Point, x *bls.Fr, ys []bls.Fr) bool

Check a proof for a KZG commitment for an evaluation f(x w^i) = y_i The ys must have a power of 2 length

func (*KZGSettings) CheckProofSingle 

func (ks *KZGSettings) CheckProofSingle(commitment *bls.G1Point, proof *bls.G1Point, x *bls.Fr, y *bls.Fr) bool

Check a proof for a KZG commitment for an evaluation f(x) = y

func (*KZGSettings) CommitToPoly 

func (ks *KZGSettings) CommitToPoly(coeffs []bls.Fr) *bls.G1Point

KZG commitment to polynomial in coefficient form

func (*KZGSettings) CommitToPolyUnoptimized 

func (ks *KZGSettings) CommitToPolyUnoptimized(coeffs []bls.Fr) *bls.G1Point

KZG commitment to polynomial in coefficient form, unoptimized version

func (*KZGSettings) ComputeProofMulti 

func (ks *KZGSettings) ComputeProofMulti(poly []bls.Fr, x uint64, n uint64) *bls.G1Point

Compute KZG proof for polynomial in coefficient form at positions x * w^y where w is an n-th root of unity (this is the proof for one data availability sample, which consists of several polynomial evaluations)

func (*KZGSettings) ComputeProofSingle 

func (ks *KZGSettings) ComputeProofSingle(poly []bls.Fr, x uint64) *bls.G1Point

Compute KZG proof for polynomial in coefficient form at position x

func (*KZGSettings) ToeplitzPart2 

func (ks *KZGSettings) ToeplitzPart2(toeplitzCoeffs []bls.Fr, xExtFFT []bls.G1Point) (hExtFFT []bls.G1Point)

Performs the second part of the Toeplitz matrix multiplication algorithm

func (*KZGSettings) ToeplitzPart3 

func (ks *KZGSettings) ToeplitzPart3(hExtFFT []bls.G1Point) []bls.G1Point

Transform back and return the first half of the vector

type ZeroPolyFn 

type ZeroPolyFn func(missingIndices []uint64, length uint64) ([]bls.Fr, []bls.Fr)

Source Files

View all Source files

Directories

Path Synopsis

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.