Cryptographic Primitives

• date: 2023-02-04
• last updated: 2023-02-04

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.