Cryptographic Primitives

• Hashing
• Merkle Trees
  • Binary Merkle Tree
  • Binary Merkle Sum Tree
  • Sparse Merkle Tree
• Public-Key Cryptography

Hashing

All hashing is done with SHA-2-256 (also known as SHA-256), defined in FIPS 180-4.

Merkle Trees

Three Merkle tree structures are used: a Binary Merkle Tree (to commit to bytecode), a Binary Merkle Sum Tree (to commit to transactions and collected fees) and a Sparse Merkle Tree (to commit to contract storage, i.e. state).

Binary Merkle Tree

A specification for the Binary Merkle Tree is here.

Binary Merkle Sum Tree

The Binary Merkle Sum Tree is an extension of the tree defined in RFC-6962.

The root pair (fee, digest) of an empty tree is:

(0x0000000000000000, hash()) = (0x0000000000000000, 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855)

The root pair of a tree with one leaf:

(leaf.fee, hash(0x00 ++ leaf.fee ++ serialize(leaf)))

The root pair of a tree with two or more leaves is defined recursively:

(left.fee + right.fee, hash(0x01 ++ left.fee ++ left.digest ++ right.fee ++ right.digest))

In other words, the root pair is 40 bytes (8 for fee sum, 32 for hash digest).

Sparse Merkle Tree

A specification for the Sparse Merkle Tree is here.

A specification describing a suite of test vectors and outputs of a Sparse Merkle Tree is here.

Public-Key Cryptography

Consensus-critical data is authenticated using ECDSA, with the curve secp256k1. A highly-optimized library is available in C (https://github.com/bitcoin-core/secp256k1), with wrappers in Go (https://pkg.go.dev/github.com/ethereum/go-ethereum/crypto/secp256k1) and Rust (https://docs.rs/crate/secp256k1).

Public keys are encoded in uncompressed form, as the concatenation of the x and y values. No prefix is needed to distinguish between encoding schemes as this is the only encoding supported.

Deterministic signatures (RFC-6979) should be used when signing, but this is not enforced at the protocol level as it cannot be.

Signatures are represented as the r and s (each 32 bytes), and v (1-bit) values of the signature. r and s take on their usual meaning (see: SEC 1, 4.1.3 Signing Operation), while v is used for recovering the public key from a signature more quickly (see: SEC 1, 4.1.6 Public Key Recovery Operation). Only low-s values in signatures are valid (i.e. s <= secp256k1.n//2); s can be replaced with -s mod secp256k1.n during the signing process if it is high. Given this, the first bit of s will always be 0, and can be used to store the 1-bit v value.

v represents the parity of the Y component of the point, 0 for even and 1 for odd. The X component of the point is assumed to always be low, since the possibility of it being high is negligible.

Putting it all together, the encoding for signatures is:

|    32 bytes   ||           32 bytes           |
[256-bit r value][1-bit v value][255-bit s value]

This encoding scheme is derived from EIP 2098: Compact Signature Representation.