See https://github.com/crate-crypto/go-kzg-4844
And https://github.com/ethereum/c-kzg-4844

for KZG libraries.

The below notes are very outdated.

[OUTDATED] EIP-4844 Implementer notes

EIP-4844 introduces "blob transactions", requiring changes in both execution and consensus layers.
See meta-spec for all resources.

This doc is meant as an implementation guide, clarifying "implementation details" of the different specs.
Initial write-up is focused at KZG performance, by @protolambda.

KZG

Learn what KZG is here: KZG polynomial commitments, by Dankrad Feist

In EIP-4844 we use this to commit to the "Blob of data". This is slower to compute than just hashing the data, but good for other things:

• The proof size, of one or more values, is always 48 bytes (compressed G1 BLS12-381 point)
• The polynomial commitment integrates very nicely with the data-recovery part of data-availability-sampling, required for full sharding (in the danksharding design)

We hide the complexity from the transaction itself by hashing the KZG commitment: this way we can version and abstract it away,
and change the hash pre-image to a different type of commitment (or with different parameters) later on.

versioned_hash = prefix_byte ++ hash(compress_serialize_g1(commit_to_poly(blob)))[1:]

The costly part is commit_to_poly, which is the evaluation of the polynomial at a secret point s.
We compute this with a linear combination of KZG_SETUP_LAGRANGE and the blob.

KZG Libraries

Q: Do I need a whole library to support blobs?
A: No! KZG is super simple. Just implement:

1. a linear combination to compute a KZG commitment
2. a single pairing verification to verify a KZG proof

The bare-bones version: geth datablobs prototype crypto/kzg/kzg.go.
One feature specific to EIP4844 that the go-kzg libraries do not have (yet): batch-verification. More about that in the Optimizations section.

Q: Are there libraries for the lazy buidler? Maybe I build fancy stuff on top of KZG, prototype sharding?
A: Yes! Commitments, proofs, optimized multi-proof generation and data-extension and data-recovery for sampling are all there already.

• go-kzg by Proto, based on python research code from Dankrad.
  It has two bls options:
  • It defaults to use kilic/bls12-381 for BLS. Go-ethereum adopted an older copy of that for previous BLS precompile work.
    kilic/bls12-381 is nice because it uses Go assembler for it's super simple toolchain and portability (beware though, kilic BLS is not written for 32 bit).
  • It also supports herumi/bls-eth-go-binary a BLS library Prysm used early on. It's relatively slow, but there for comparison.
  • BLST is not supported, Go bindings are insufficient and buggy for integration (might revisit this in the future).
• c-kzg by Ben Edgington, based on go-kzg. Using BLST, a highly optimized BLS library used by all Eth2 clients today.
  Note: there also java bindings to c-kzg available. Others higher-level languages may also want to wrap the c-library.

Benchmarks

Blob to commitment

The most essential benchmark is "time to go from blob to commitment", a.k.a. a G1 linear combination, with maybe some decoding/encoding work.

In EIP-4844 we use 4096 field elements per blob, so that's what we benchmark.
log2(4096) = 12, in the benchmarks we sometimes have different "scales", scale 12 is what matters here.

c-kzg

git clone [e-mail]:benjaminion/c-kzg.git
git clone [e-mail]:supranational/blst.git
cd blst && ./build.sh
cd ../c-kzg
cp ../blst/libblast.a lib/
cp ../blst/bindings/*.h inc/
cd src
make lib
lscpu | grep "Model name"
make kzg_proofs_bench

Collected outputs:

AMD Ryzen 9 5950X 16-Core Processor
commit_to_poly/scale_12 42376608 ns/op

go-kzg

Using Go 1.17

git clone [e-mail]:protolambda/go-kzg.git
cd go-kzg
# Kilic BLS (default)
go test -run $^ -bench BenchmarkCommit -benchtime=1s -v
# Herumi BLS
go test -tags=bignum_hbls -run $^ -bench BenchmarkCommit -benchtime=1s -v

Collected outputs:

AMD Ryzen 9 5950X 16-Core Processor
# Kilic BLS
BenchmarkCommit/scale_12-32                  198          57024504 ns/op
# Herumi BLS
BenchmarkCommit/scale_12-32                  100         101043962 ns/op

Notes:

• I think I can make Kilic BLS run faster, or at least thrash less memory, with Go-specific optimizations.
  But I am not a cryptographer, so I'm not making any changes without review :)
• Both Go-KZG or C-KZG are single-threaded. With 40-60 ms it may be worth it to parallelize the work.
• If you have a different machine, please run the same benchmarks and report the results, more data is nice to have!

Optimizations

40-60 ms for computing a KZG blob is not great:

• We have up to 2 per tx (MAX_BLOBS_PER_TX) and 16 blobs in a block (MAX_BLOBS_PER_BLOCK). Even if valid, a lot of work.
• There is a whole transaction pool to verify.
• Transactions may have valid blob data, but have an invalid KZG commitment or sign over a different versioned hash.
  The tx is invalid, and will not pay a fee. DoS risk there.

We can optimize by doing two things:

• By distributing the KZG commitment along with the input data, we only have to verify commitment and inputs match.
• Similar to batch-verification of aggregated attestations in Eth2 to save cost, we can batch-verify the commitments of blobs.

Description by George:

Batch verification works with multi-scalar-multiplication (MSM):
The MSM would look like this (for three blobs with two field elements each):

r_0(b0_0*L_0 + b0_1*L_1) + r_1(b1_0*L_0 + b1_1*L_1) + r_2(b2_0*L_0 + b2_1*L_1)

which we would need to check against the linear combination of commitments:

r_0*C_0 + r_1*C_1 + r_2*C_2

In the above:

• r are the random scalars of the linear combination
• b0 is the first blob, b0_0 is the first element of the first blob.
• L are the elements of the KZG_SETUP_LAGRANGE
• C are the commitments

By regrouping the above equation around the L points we can reduce the length of the MSM further
(down to just n scalar multiplications) by making it look like this:

(r_0*b0_0 + r_1*b1_0 + r_2*b2_0) * L_0 + (r_0*b0_1 + r_1*b1_1 + r_2*b2_1) * L_1

Essentially we multiply each blob with a secret random scalar, as well as the commitment,
so we can sum them up safely before verifying.

And so it reduces to two bls.LinCombG1 calls:

• multiplying the aggregated blob elements with KZG_SETUP_LAGRANGE
• multiplying the random scalars used during aggregation with the commitments

Benchmarking Batch-verification

Go 1.17, kilic BLS, kzg.VerifyBlobs in geth prototype

cpu: AMD Ryzen 9 5950X 16-Core Processor

# 16 blobs:
BenchmarkVerifyBlobs-32    	      20	  71193890 ns/op

# 128 blobs:
BenchmarkVerifyBlobs-32    	      13	 114886742 ns/op

I.e. from 57 to 71 milliseconds, but now verifying 16x as many blobs!

And from 57 to 114 for 128x as many. Batching is important

Memory optimization

To aggregate with constant memory, the blob elements and commitments can be aggregated on the fly,
i.e. we add the scaled blobs and commitments to running aggregates instead of aggregating at the very end.
This is a trade-off between memory and being able to optimize the linear combinations.

Tx Pool

Ethereum fetches txs with the devp2p protocol, many at a time.

However, in the case of go-ethereum it does not score down peers that return bad transactions
(as far as I understood from quick reverse engineering), and it verifies the transactions single-threaded one at a time.

Assuming the verification of regular txs is cheap, that's not really a problem.

For blob transactions we have to make some changes though:

• Refactor the processing of received txs to do one step at a time for all txs, instead of all steps for one tx.
  I.e. introduce "stages"
• Introduce a "stage" that does batch-verification of all transactions that were just received from the same peer.
  If anything is wrong with any of these, the peer we received it from should be held accountable (peer scoring/banning).
• If we still trust the peer when batch-verification fails, we can batch-verify the blobs of each individual transaction.

To aggregate many transactions without increasing memory by too much aggregating on the fly should help
(by parsing all blobs and commitments into deserialized []Fr and G1Point instances we double memory).

Staged validation, and the blobs verification stage, have been implemented in go-ethereum
here.
Peer-scoring was not changed, I need feedback on what is already there to integrate with.

BlobsSideCar

Similar to the transaction-pool in the execution-layer,
the consensus-layer also has to verify bundles of commitments and blob-data: known as the BlobsSidecar.

During gossip of sidecars however, only signed sidecars are distributed:
we only have 1 beacon block per 12 seconds, and only 1 sidecar of blobs.
So even if costly, the proposer signature check avoids DoS nicely.

However, because blobs are available for longer times, but the sidecar signatures are not
(and will definitely not be with sharding, when blobs are recovered from samples),
there are still other places to DoS: the request-response (a.k.a. sync protocol).

In that case we want to batch-verify all blobs in a single sidecar.
And when requesting multiple sidecars from the same peer, using e.g. blobs_sidecars_by_range v1,
we can aggregate all (or e.g. 20 at a time) received sidecars and batch-verify them all at once!

Again, when batch-verifying a lot of data (100 sidecars = 200 MiB worst-case) it makes sense to
aggregate on the fly to keep constant memory, and write the blobs to some temporary disk space until fully verified.