Constantine

Constantine: High performance cryptography for proof systems and blockchain protocols

“A cryptographic system should be secure even if everything about the system, except the key, is public knowledge.”
— Auguste Kerckhoffs

This library provides constant-time implementation of cryptographic primitives with a particular focus on cryptography used in blockchains and zero-knowledge proof systems.

<!-- TOC -->

• Constantine
  • Public API: Curves & Protocols
    • Protocols
    • Elliptic Curves
    • General cryptography
    • Threadpool
  • Installation
    • From Rust
    • From Go
    • From C
    • From Nim
  • Dependencies & Requirements
  • Performance
  • Assembly & Hardware acceleration
  • Security
    • Disclaimer
    • Security disclosure
  • Why Nim
  • License

<!-- /TOC -->

The library aims to be a fast, compact and hardened library for elliptic curve cryptography needs, in particular for blockchain protocols and zero-knowledge proofs system.

The library focuses on following properties:

• constant-time (not leaking secret data via side-channels)
• performance
• generated code size, datatype size and stack usage

in this order.

Public API: Curves & Protocols

Protocols are a set of routines, designed for specific goals or a combination thereof:

• confidentiality: only the intended receiver of a message can read it
• authentication: the other party in the communication is the expected part
• integrity: the received message has not been tampered with
• non-repudiation: the sender of a message cannot repudiated it

Legend

• :white_check_mark:: Full support
• :building_construction:: Partial support:
  • in C, some APIs not provided.
  • in Rust, only low-level constantine-sys API available but no high-level wrapper.
• :see_no_evil:: Missing support

Protocols

Constantine supports the following protocols in its public API.

| | Nim | C | Rust | Go | |------------------------------------------------------------------------|:-----------------------:|:------------------:|--------------------|:------------------:| | Ethereum BLS signatures | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | Ethereum KZG commitments for EIP-4844 | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | Ethereum IPA commitments for Verkle Tries | :building_construction: | :see_no_evil: | :see_no_evil: | :see_no_evil: | | Ethereum Virtual Machine BN254 Precompiles ECADD, ECMUL, ECPAIRING | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | EVM BLS12-381 precompiles (EIP-2537) | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | EVM Misc: SHA256, modexp | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | Zk Accel layer for Halo2 proof system (experimental) | not applicable | not applicable | :white_check_mark: | not applicable |

Elliptic Curves

Constantine supports the following curves in its public API.

| | Nim | C | Rust | Go | |-------------------------------|:------------------:|:------------------:|--------------------|:-------------:| | BN254-Snarks | :white_check_mark: | :white_check_mark: | :white_check_mark: | :see_no_evil: | | BLS12-381 | :white_check_mark: | :white_check_mark: | :white_check_mark: | :see_no_evil: | | Pasta curves (Pallas & Vesta) | :white_check_mark: | :white_check_mark: | :white_check_mark: | :see_no_evil: |

For all elliptic curves, the following arithmetic is supported

• field arithmetic
  • on Fr (i.e. modulo the 255-bit curve order)
  • on Fp (i.e. modulo the 381-bit prime modulus)
• elliptic curve arithmetic:
  • on elliptic curve over Fp (EC 𝔾₁) with affine, jacobian and homogenous projective coordinates
  • on elliptic curve over Fp2 (EC 𝔾₂) with affine, jacobian and homogenous projective coordinates
  • including scalar multiplication, multi-scalar-multiplication (MSM) and parallel MSM

All operations are constant-time unless explicitly mentioned vartime.

For pairing-friendly curves Fp2 arithmetic is also exposed.
:building_construction: Pairings and multi-pairings are implemented but not exposed yet.

General cryptography

Constantine supports the following hash functions and CSPRNGs in its public API.

| | Nim | C | Rust | Go | |--------------------------------------------------------------|:------------------:|:------------------:|-------------------------|:------------------:| | SHA256 | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: | | Cryptographically-secure RNG from Operating System (sysrand) | :white_check_mark: | :white_check_mark: | :white_check_mark: | :white_check_mark: |

Threadpool

Constantine also exposes a high-performance threadpool for Nim that inherits performance and API from:

• Task parallelism API RFC: https://github.com/nim-lang/RFCs/issues/347

  • Weave data parallelism API:
    • spawn and sync
    • parallelFor and syncScope
      • parallelFor supports arbitrarily complex reduction. Constantine uses it extensively for parallel elliptic curve sum reductions.
    • isSpawned and isReady

• CPU Topology - Query the number of threads available at the OS/VM-level to run computations:

  • ctt_cpu_get_num_threads_os in C
  • getNumThreadsOS in Nim
  • constantine_core::hardware::get_num_threads_os in Rust

• https://github.com/mratsim/weave

• https://github.com/status-im/nim-taskpools

The threadpool supports nested parallelism to exploit high core counts and does not suffer from OpenMP limitations of nested parallel loops. For batching KZG verification, Constantine issues 3 multi-scalar multiplication in parallel, each using at 3 nested parallel loops.

See the following documents on the threadpool performance details, design and research:

• ./README-PERFORMANCE.md#parallelism
• ./docs/threadpool-design.md
• https://github.com/mratsim/weave/tree/7682784/research

Installation

[!IMPORTANT] Constantine can be compiled with:

• Nim v2.2.0

From Rust

1. Install clang compiler, for example:

   • Debian/Ubuntu sudo apt update && sudo apt install build-essential clang
   • Archlinux pacman -S base-devel clang

   [!TIP] We require Clang as it's significantly more performant than GCC for cryptographic code, especially for ARM where Constantine has no assembly optimizations. And Rust, like Clang both rely on LLVM.<br />This can be changed to any C compiler by deleting this line.

2. Install nim, it is available in most distros package manager for Linux and Homebrew for MacOS Windows binaries are on the official website: https://nim-lang.org/install_unix.html

   • Debian/Ubuntu sudo apt install nim
   • Archlinux pacman -S nim

3. Test both:

   • the experimental ZK Accel API (ZAL) for Halo2-KZG
   • Ethereum EIP4844 KZG polynomial commitments

   git clone https://github.com/mratsim/constantine
   cd constantine
   cargo test
   cargo bench
   

4. Add Constantine as a dependency in Cargo.toml

   • for Halo2-KZG Zk Accel Layer

     [dependencies]
     constantine-halo2-zal = { git = 'https://github.com/mratsim/constantine' }
     

   • for Ethereum EIP-4844 KZG polynomial commitments

     [dependencies]
     constantine-ethereum-kzg = { git = 'https://github.com/mratsim/constantine' }
     

Optionally, cross-language LTO between Nim and Rust can be used, see https://doc.rust-lang.org/rustc/linker-plugin-lto.html:

Add a .cargo/config.toml to your project with the following:

# .cargo/config.toml

[build]
rustflags="-Clinker-plugin-lto -Clinker=clang -Clink-arg=-fuse-ld=lld"

and modify Constantine's build.rs to pass CTT_LTO=1

    Command::new("nimble")
        .env("CC", "clang")
        .env("CTT_LTO", "1") // <--
        .arg("make_lib_rust")
        .current_dir(root_dir)
        .stdout(S