Parallelized multi-backend KZG library for Ethereum Data Sharding (aka Proto-Danksharding, EIP-4844)

The goal is to create a parallelized KZG library for Ethereum Data Sharding (aka Proto-Danksharding, EIP-4844) that supports multiple ECC (Elliptic-curve cryptography) backend libraries.

Backend ECC libraries

Support for multiple backend ECC libraries is implemented via Traits. Such an approach allows to easy change backend ECC libraries as all the crates shared the same interface (see benchmarks and tests). The current state of supported backend ECC libraries:

Backend ECC	FFT/DAS	EIP-4844 (non-parallel)	EIP-4844 (parallel)	c-kzg-4844 drop-in replacement	GPU acceleration
blst	✔️	✔️	✔️	✔️	✔️ via sppark
constantine	✔️	✔️	✔️	✔️	❌
mcl	✔️	✔️	✔️	✔️	❌
arkworks5	✔️	✔️	✔️	✔️	❌
arkworks4	✔️	✔️	✔️	✔️	❌
arkworks3	✔️	✔️	✔️	✔️	✔️ via sppark and wlc_msm
zkcrypto	✔️	✔️	✔️	✔️	❌

Additional setup steps for ECC libraries

• For all backends:
  1. Set up rust. Only latest rust version is tested on CI, so it is better to use this one.
  2. C/C++ compiler:
     • Debian/Ubuntu: sudo apt update && sudo apt install build-essential
     • Archlinux: pacman -S base-devel
     • Windows: rustup automatically sets up visual studio C++ compiler, make sure it is present.
• For constantine:
  1. Set up nim. It is recommended to use choosenim, and set up 2.0.2 nim version.
  2. Clang compiler:
     • Debian/Ubuntu: sudo apt update && sudo apt install clang
     • Archlinux: pacman -S clang
     • Windows: you can install "C++ Clang tools for Windows" from visual studio installer
• For mcl:
  1. GMP:
     • Debian/Ubuntu: sudo apt instal libgmp-dev
     • MacOS: brew install gmp

blst, arkworks3, arkworks4, arkworks5 and zkcrypto do not require additional setup steps.

Drop-in replacement for c-kzg-4844

We aim to expose an identical C interface compared to c-kzg-4844 so that rust-kzg could work as a drop-in replacement for c-kzg-4844. If you already use c-kzg-4844 bindings you can try faster paralellized rust-kzg without any changes to your code-base by simply replacing the binary. Instructions for C#, Java, Nodejs, Python, Rust bindings are available here.

By default, C bindings are disabled. To enable them, compile static library with feature flag c_bindings:

cargo rustc -p rust-kzg-blst --release --crate-type=staticlib --features=c_bindings

Multi-scalar multiplication

Multiple multi-scalar multiplication algorithms are implemented in the library. Most of them are ECC backend agnostic and have both sequential and parallel versions.

Example

The best place to look for examples is tests directory.

Currently, the ECC backend is set by pointing Cargo to the corresponding crate:

[dependencies]
kzg = { git = "https://github.com/grandinetech/rust-kzg.git", package = "rust-kzg-blst" }
kzg_traits = { git = "https://github.com/grandinetech/rust-kzg.git", package = "kzg" }

Benchmarks

Benchmarks run on every Github build. However, it's best to run them on a dedicated machine. Tautvydas rendered nice charts for results he got on cloud servers:

Blob to KZG commitment

Compute KZG proof

Verify KZG proof

Compute blob KZG proof

Verify blob KZG proof

Verify blob KZG proof batch

Click to expand (blobs count 32 to 1)

Verify blob KZG proof batch (count 32)

Verify blob KZG proof batch (count 16)

Verify blob KZG proof batch (count 8)

Verify blob KZG proof batch (count 4)

Verify blob KZG proof batch (count 2)

Verify blob KZG proof batch (count 1)

Fast Fourier transform (FFT)

Multi-scalar multiplication (MSM)

GPU acceleration

GPU-accelerated multi-scalar multiplication is available for arkworks3 and blst backends.

Multi-scalar multiplication

Blob to KZG commitment

Compute KZG proof

Compute blob KZG proof

Authors

The project is developed numerous contributors led by Saulius Grigaitis. The project is heavily based on the c-kzg-4844, c-kzg, go-kzg, and other libraries.