Teaser
Read this if you've read the Feist-Khovratovits KZG multi-reveal scheme (https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf) and you're looking for a nicely-stated, typo free, succinct version of the proof.
Dare to read this if you're not afraid of FFT/NTT manipulation...
Read this if you've never heard of NTT over EC vectors...
Abstract
Danksharding is the new sharding design proposed for the Ethereum 2.0 blockchain, which introduces significant simplifications compared to previous designs. In Danksharding, the Beacon block is a periodic data structure, constructed by a Builder, whose primary concern is to enable Validators to verify the correctness and availability of its data, using constant-time sampling and verification. This report provides a mathematical analysis of the Beacon block construction process, including new structural and processing improvements and alternatives.
Introduction
Danksharding is central to Ethereum’s rollup-centric roadmap [1]. The idea is to provide space for large blobs of data, which are verifiable and available, without attempting to interpret them. The blobs data space is expected to be used by layer-2 rollup protocols, supporting high throughput transactions.
The main innovation introduced by Danksharding is the merged-fee-market, which is enabled by enforcing of a single proposer per slot. Danksharding introduces separation of Proposers and Builders, to avoid high system requirements on Validators. The Builders bid for the right to choose the contents of the slot, while the Proposer selects the highest bidder. Only block Builders need to process the entire block, while Validators and users can download and verify parts or all of the data very efficiently through data-availability-sampling [2].
This report is focused on the Beacon block building process. Bearing very high computational complexity, optimization of the block building process is invaluable. This, in our opinion, is best done via thorough understanding of the mathematical models supporting the process. The block building process is broken down to five stages: data organization, coefficient extraction, data interpolation, KZG commitments, and KZG proofs.
The processing per stage is described in detail, attempting to be as self-contained as possible. The reader is encouraged to obtain some basic understanding of Discrete-Fourier-Transform (DFT) [3] prior to reading the report.
One outcome of the report is reinforcement of the notion that the basic computationally dominant primitives, required by Danksharding, are highly correlated with ones required for Zero-Knowledge-Proofs. Amongst those primitives are Multi-Scalar-Multiplications (MSM), Number-Theoretic-Transforms (NTT), a new class of NTT — NTT over EllipticCurve (EC) group-element vectors (ECNTT), and various lower-lever finite-field arithmetic primitives, such as modular-multiplier, EC-adder etc.
The report structure follows the chronological order of the processing stages, presenting required mathematical tools as needed.
Read on below, or see the full paper on Github:
https://github.com/ingonyama-zk/papers/blob/main/danksharding_math.pdf
Acknowledgements
The author would like to thank Karthik Inbasekar, Dmytro Tymokhanov, and Omer Shlomovits for helpful discussions.
References
[1] Vitalik Buterin. Proto-danksharding faq. https://notes.ethereum.org/@vbuterin/proto_danksharding_faq
[2] Vitalik Buterin. An explanation of the sharding + das proposal. https://hackmd.io/@vbuterin/sharding_proposal
[3] Discrete fourier transform. https://en.wikipedia.org/wiki/Discrete_Fourier_transform
[4] Ben Edgington. Bls12-381 for the rest of us. https://hackmd.io/@benjaminion/bls12-381
[5] Dankrad Feist. Data availability encoding. https://notes.ethereum.org/@dankrad/danksharding_encoding
[6] E.R. Berlekamp. Algebraic coding theory. Aegean Park Press, Laguna Hills, CA, USA, 1984
[7] Dankrad Feist. Kzg polynomial commitments. https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html, 2020
[8] Dankrad Feist and Dmitry Khovratovich. Fast amortized kate proofs. https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf, 2020
[9] Vitalik Buterin. Quadratic arithmetic programs: from zero to hero. https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649, 2016
[10] Ray Li. Roots of Unity. https://theory.stanford.edu/~rayyli/static/contest/lectures/Ray%20Li%20rootsofunity.pdf, 2021
Full Paper on Github:
https://github.com/ingonyama-zk/papers/blob/main/danksharding_math.pdf
