Historical page retained for compatibility. It may contain superseded assumptions, incomplete plans, or outdated links and is not current canonical content. See the Archive for context.

• original material: 2023-02-04 to 2023-02-05
• consolidated: 2026-08-09
• archive status: historical reference

Overview

Here we review cryptographic and mathematic primitives

For each primitive we review

• Cryptographic Primitive
• Applications
• Implementations (codebases)
• Zero Knowledge relationships/improvements

This consolidated archive page brings the previously separate primitive pages into one document while preserving their original material and references.

Reference implementations and primitive families

Overview

Cryptographic and Mathematic Primitives

Reference Implementations

• bloom filter

  • geth bloombits (go): Package bloombits implements bloom filtering on batches of data.

• int_to_bytes

  • lighthouse int_to_bytes (rust): The Eth 2.0 specification uses int.to_bytes(2, 'little'), which throws an error if int doesn't fit within 3 bytes. The specification relies upon implicit asserts for some validity conditions, so we ensure the calling function is aware of the error condition as opposed to hiding it with a modulo.

• leaky bucket

  • prysm: leaky bucket as a meter

• linked list

  • prysm (go): doubly linked list

• merkle patrica tries

  • geth trie (go): Package trie implements Merkle Patricia Tries.
  • geth database (go): Trie is a Ethereum Merkle Patricia trie.

• merkle trees

  • prysm sparse_merkle (go): defines utilities for sparse merkle tries for Ethereum consensus.
  • lighthouse cached_tree_hash (rust): Sparse Merkle tree suitable for tree hashing vectors and lists.
  • lighthouse tree_hash (rust): Convenience method for MerkleHasher which also provides some fast-paths for small trees.minimum_leaf_count will only be used if it is greater than or equal to the minimum number of leaves that can be created from bytes.
  • lighthouse tree_hash_derive (rust):
  • tendermint go (go): Merkle Tree For smaller static data structures that don't require immutable snapshots or mutability; for instance the transactions and validation signatures of a block can be hashed using this simple merkle tree logic.
  • paritytech binary-merkle-trie (rust): implements a simple binary Merkle Tree utilities required for inter-op with Ethereum bridge & Solidity contract.
  • snowbridge merkle.go
  • snowbridge merkleization.rs

• merkle_proof explainer

  • lighthouse merkle_proof (rust): efficiently represents a Merkle tree of fixed depth where only the first N indices are populated by non-zero leaves (perfect for the deposit contract tree).
  • snowbridge simplified_mmr_proof.go
  • snowbridge merkle-proof rust
  • snowbridge MerkleProof.sol
  • npm package eth-proof

• Merkle Mountain Range

  • paritytech merkle-mountain-range (rust)
  • harmony mmr (go): Adds a merkle mountain range to harmony's core protocol to support light clients (WIP) PR4198

• queues

  • prysm (go): priority queue
  • snowbridge MMRProof.sol
  • snowfork merkle-mountain-range

• safe-arithmetic

  • lighthouse safe_arith (rust): Library for safe arithmetic on integers, avoiding overflow and division by zero.

• slice

  • prysm (go)

• tries

  • paritytech trie: Utility functions to interact with Substrate's Base-16 Modified Merkle Patricia tree ("trie").

• Verifiable Delay Function

  • harmony vdf (go): Package vdf is a proof-of-concept implementation of a delay function and the security properties are not guaranteed.

• Verfiable Random Function

  • harmony vrf (go): A VRF is a pseudorandom function f_k from a secret key k, such that that knowledge of k not only enables one to evaluate f_k at for any message m, but also to provide an NP-proof that the value f_k(m) is indeed correct without compromising the unpredictability of f_k for any m' != m. https://ieeexplore.ieee.org/document/814584
  • paritytech vrf: Primitives for VRF-based consensus engines. Schnorrkel-based VRF.

• tree

  • paritytech fork-tree (rust): Utility library for managing tree-like ordered data with logic for pruning the tree while finalizing nodes.

SHA-2

difference between sha256 and kecakk256

• Argon 2
  • Argon2: eference C implementation of Argon2.
  • x/crypto Argon2 (go): Package argon2 implements the key derivation function Argon2.
  • rust-argon2 (rust): Rust library for hashing passwords using Argon2.
  • node-argon2 (typescript): Bindings to the reference Argon2 implementation.
• blake
  • blake2 hash function
    • ethereum-go-ethereum (go): Package blake2b implements the BLAKE2b hash algorithm defined by RFC 7693 and the extendable output function (XOF) BLAKE2Xb.
    • bsc blake2b (go): Package blake2b implements the BLAKE2b hash algorithm defined by RFC 7693 and the extendable output function (XOF) BLAKE2Xb.
  • blake3
    • blake3 rust crate (rust): BLAKE3 is based on an optimized instance of the established hash function BLAKE2 and on the original Bao tree mode.
    • zeebo blake3 (go) : Pure Go implementation of BLAKE3 with AVX2 and SSE4.1 acceleration.
• keccak256 hash function
  • prysm (go)
  • lighthouse (rust): wrapper over two SHA256 crates: sha2 and ring
  • bsc crypto (go)
  • harmony hash (go)
  • snowbridge keccak
• sha256
  • tendermint tmhash

• ECIES (go): a hybrid encryption scheme
  • ethereum-go-ethereum (go)
  • bsc ecies (go)
• ascii armored encryption uses ed25519
  • ethereum-go-ethereum (go)
  • bsc signify (go)
  • tenderming armor (go)
• ChaCha20-Poly1305: an authenticated encryption with additional data (AEAD) algorithm
  • tendermint xchacha20poly1305 (go)
• XSalsa20 (go): XSalsa20 is a stream cipher based upon Salsa20 but with a much longer nonce: 192 bits instead of 64 bits.
  • tendermint xsalsa20symmetric (go): secret must be 32 bytes long. Use something like Sha256(Bcrypt(passphrase)). The ciphertext is (secretbox.Overhead + 24) bytes longer than the plaintext.

• prysm (go)

• RECURSIVE-LENGTH PREFIX (RLP) SERIALIZATION

  • ethereum rlp
  • harmony rlp

• Simple Serialize

  • snowbridge ssz.rs

• Merkle Patricia Trie

• prysm: contains generic containers that are protected either by Mutexes or atomics underneath the hood.

• hash functions
  • Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (video)

References

• Bloom Filter Wikipedia: A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.
• Bloom Filters Explainer: The bloom filter essentially consists of a bit vector of length m, represented by the central column.
• Bloomfilter Lesson 11 - Blockchain Academy: Blockchain Introduction Technical – Beginner to Intermediate Lesson 11 – Bloomfilter.
• Cuckoo Hashing: a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al.
• Cukoo Hashing Visualization: Visualization of Cukoo Hashing an elegant method for resolving collisions in hash tables.
• Fast Fourier Transforms: Vitaliks explaniner on Fast Fourier Transforms. Trigger warning: specialized mathematical topic, with special thanks to Karl Floersch for feedback.
• Merkle Trees/Merkle Proofs Lesson 10 - Blockchain Academy: Blockchain Introduction Technical – Beginner to Intermediate Lesson 10 – Merkle Trees/Merkle Proofs.

Signature schemes in consensus protocols

Overview

Both sides of the bridge need to verify what happened on the other side. To do that, the verification logic is often encapsulated inside a light client, manifested as a smart contract on the chain which the verification needs to be executed. The light client needs to follow consensus and signature verification mechanisms based on the signing algorithm and the elliptical curve used on the other side. For example, if chain A has 21 validators signing each block using ECDSA algorithm on secp256k1 curves, then chain A's light client, executed on chain B, must extract the signatures from the block headers presented to the light client, and follow the ECDSA signature verification algorithm to verify the content of the block header indeeds produces the 21 signatures contained in the block header, given the public keys of the 21 validators.

Here, we present a reference table for these signature schemes and how they are used in the consensus protocols of different blockchains. We limit our initial scope to Ethereum, Polygon, Avalanche, BSC, Harmony, Cosmos, and Polkadot only (and their undelying technologies). Note that we are only looking at how signatures are used in consensus, not elsewhere in the blockchain stack, as all these protocols use ECDSA on secp256k1 for accounts in EVM interactions.

Resources

Algorithms

ECDSA

• Wikipedia
• Standard: SEC 2: Recommended Elliptic Curve Domain Parameters

BLS

• Wikipedia
• Paper: Short Signatures from the Weil Pairing
• Tutorial: BLS signatures: better than Schnorr
• Analysis: Secret Sharing and Threshold Signatures with BLS
• Deep dive: BLS Signatures in Solidity

EdDSA

• Wikipedia
• GoLang

Curves

• Curve database

secp256k1

• Bitcoin Wiki
• Tutorial: A Bluffer’s Guide to secp256k1

BLS12-381

• Deep dive: BLS12-381 For The Rest Of Us
• Intro: BLS12-381: New zk-SNARK Elliptic Curve Construction
• Paper: Fast and simple constant-time hashing to the BLS12-381 elliptic curve
• Benchmark: BLS: Is it really that slow
• EIP: EIP-2537: Precompile for BLS12-381 curve operations
• EVM launch: Targeting Shanghai upgrade May 2023

BN254

• Definition
• Paper: Pairing-Friendly Elliptic Curves of Prime Order
• Deep Dive: BLS Signatures in Solidity
• Speed Optimization: New software speed records for cryptographic pairings

Usage in ZKP

• A survey of elliptic curves for proof systems

Signing Implementations

The Standard Curve Database is a good starting point for existing signing algorithms. Base implementations such as golang crypto and rust crypto provide good reference codebases.

• bcrypt
  • cosmos-sdk bcrypt
• bip-0039
  • lighthouse (rust)
• bls
  • ethereum-prysm
• bls-12-381
  • ethereum EIP-2537: Precompile for BLS12-381 curve operations
  • ethereum-go-ethereum (go)
  • harmony bls (go): uses harmony bls repository
    • bls Harmony forked from herumi/bls_: written in C++, supports Go, Rust, WebAssembly (Node.js)
  • prysm (go)
  • lighthouse (rust): provides a wrapper around several BLS implementations to provide Lighthouse-specific functionality.
  • lighthouse (rust): Provides path-based hierarchical BLS key derivation, as specified by EIP-2333.
    • Aurora Rainbow Bridge Implementation: Implementations
      • blst
      • fake_crypto
      • milagro: support for Apache Milagro
  • lighthouse (rust): Provides a JSON keystore for a BLS keypair, as specified by EIP-2335.
  • bsc bls12381 (go)
  • blst: blst (pronounced 'blast') is a BLS12-381 signature library focused on performance and security. It is written in C and assembly.
• bn256
  • ethereum-go-ethereum (go)
  • bsc bn256 (go)
• ecdsa
  • bsc crypto (go): toECDSA creates a private key with the given D value. The strict parameter controls whether the key's length should be enforced at the curve size or it can also accept legacy encodings (0 prefixes).
  • paritytech ecdsa (rust)
  • cosmos-sdk ecdsa
• ed25519 golang
  • tendermint ed25519 (go): GenPrivKey generates a new ed25519 private key. It uses OS randomness in conjunction with the current global random seed in tendermint/libs/common to generate the private key.
  • paritytech ed25519 (rust)
  • Ed25519: Ed25519.sol
  • cosmos-sdk ed25519
• secp256k1
  • ethereum-go-ethereum (go)
  • prysm (go)
  • bsc secp256k1
  • tendermint secp256k1 (go): GenPrivKeySecp256k1 hashes the secret with SHA2, and uses that 32 byte output to create the private key.
  • cosmos-sdk secp256k1
  • snowbridge secp256k1
• secp256r1
  • cosmos-sdk secp256r1
• sr25519: schnorr over ristretto25519
  • chainsafe go-schnorrkel (go): This repo contains the Go implementation of the sr25519 signature algorithm (schnorr over ristretto25519). The existing Rust implementation is here.
  • paritytech substrate-bip39 (rust): his is a crate for deriving secret keys for Ristretto compressed Ed25519 (should be compatible with Ed25519 at this time) from BIP39 phrases.
  • paritytech sr25519 rust
  • tendermint sr25519 (go): GenPrivKeyFromSecret hashes the secret with SHA2, and uses that 32 byte output to create the private key.
  • snowbridge sr25519

Light clients

Overview

References

• Building Helios: Fully trustless access to Ethereum: a Rust-based Ethereum light client we developed that provides fully trustless access to Ethereum.
• Annotated Ethereum Roadmap

Fraud proofs

Overview

Following is an excerpt from Fraud and Data Availability Proofs

Light clients, also known as Simple Payment Verification (SPV) clients, are nodes which only download a small portion of the data in a blockchain, and use indirect means to verify that a given chain is valid. Instead of validating blocks, they assume that the chain favoured by the blockchain’s consensus algorithm only contains valid blocks, and that the majority of block producers are honest. By allowing such clients to receive fraud proofs generated by fully validating nodes that show that a block violates the protocol rules, and combining this with probabilistic sampling techniques to verify that all of the data in a block actually is available to be downloaded so that fraud can be detected, we can eliminate the honest-majority assumption for block validity, and instead make much weaker assumptions about a minimum number of honest nodes that rebroadcast data. Fraud and data availability proofs are key to enabling on-chain scaling of blockchains while maintaining a strong assurance that on-chain data is available and valid. We present, implement, and evaluate a fraud and data availability proof system.

Here is an overview of how NEAR bridge uses this in an optimistic approach

The leading NEAR Ethereum Bridge today Near Rainbow Bridge uses an optimistic approach. Following is an excerpt from NearOnEthClient ².

we adopt the optimistic ³ approach where NearOnEthClient verifies everything in the NEAR header except the signatures. Then anyone can challenge a signature in a submitted header within a 4-hour challenge window. The challenge requires verification of a single Ed25519 signature which would cost about 500k Ethereum gas (expensive, but possible).

Footnotes

Fast Fourier transforms

Overview

References

• Fast Fourier Transforms

Weak subjectivity

Overview

Following is an excerpt from Analysis on Weak Subjectivity in Ethereum 2.0 ¹ .

Weak subjectivity ⁴ is a social-consensus-driven approach for solving the fun- damental “nothing-at-stake” problem of proof-of-stake protocols. In particular, it addresses the problem in the presence of long-range forks, while the slash- ing mechanism handles the case of short-range forks. Specifically, the current weak subjectivity mechanism deals with the following two types of long-range attacks ⁵

– Exploiting retired validators: Adversaries can create and reveal a new chain branching from a certain block on the canonical chain, after 2/3 of validators who were active for the block have exited. Note that such validators can still justify and finalize conflicting blocks at earlier slots without being slashed after they have exited.

– Exploiting diverging validator sets: Adversaries can build a new chain until the validator set for the new chain is sufficiently different from that of the canonical chain. The larger the difference between the two validator sets, the lower the accountable safety tolerance. For example, if the intersection of the two sets is smaller than 2/3 of each set, then it is possible to have conflicting blocks to be finalized without any validators violating the slashing conditions.

It is unknown whether this mechanism can deal with other types of long-range attacks, if any, in general.

The current weak subjectivity mechanism employs a social consensus layer in parallel to maintain sufficiently many checkpoints (called weak subjectivity check- points) so that there exist no conflicting finalized blocks that are descendants of the latest weak subjectivity checkpoint. In other words, the purpose of the latest weak subjectivity checkpoints is to deterministically identify the unique canonical chain even in the presence of conflicting finalized blocks caused by the long-range attacks.

References

Articles and guides

• Weak Subjectivity in Eth2.0: This document is aimed for Eth2.0 client teams to understand weak subjectivity periods and their implication.

• Phase 0 -- Weak Subjectivity Guide: This document is a guide for implementing the Weak Subjectivity protections in Phase 0.

Documentation

• Ethereum Docs: WEAK SUBJECTIVITY: This refers to a chain that can progress objectively after some initial seed of information is retrieved socially.

• Teku Docs: Weak Subjectivity: The weak subjectivity period refers to how far behind the chain head a node can be before 1/3 of validators may have exited since the node was last in sync.

Implementations

• Prysm: weak_subjectivity_checks.go
  • NewWeakSubjectivityVerifier validates a checkpoint, and if valid, uses it to initialize a weak subjectivity verifier.
  • VerifyWeakSubjectivity verifies the weak subjectivity root in the service struct.

Footnotes