KZG and FFT utils

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:

• KZG Data availability code by Dankrad
• Verkle and FFT code by Dankrad and Vitalik
• Reed solomon erasure code recovery with FFTs by Vitalik
• FFT explainer by Vitalik
• Kate explainer by Dankrad
• Kate amortized paper by Dankrad and Dmitry

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.