RLP and Nibbles — The Encoding Primitives

The previous page, Why a Trie, Not a Plain Merkle Tree, argued why Ethereum reaches for a Merkle-Patricia trie: it wants a structure that is keyed by address, cheap to update, and collapses to a single hash that every node can compare. But two words in that sentence hide a lot of machinery. To hash a node you must first turn it into bytes — and to do that in a way thousands of untrusting strangers all agree on, byte-for-byte, you need a serialization format that has exactly one valid output for any input. To key the trie by an address you must decide what a “path step” is — one bit? one byte? something in between?

This page builds the two primitives that answer those questions before the next page assembles them into nodes. RLP (Recursive Length Prefix) is Ethereum’s canonical serialization: the recipe that turns any nested arrangement of byte arrays into one definite byte string. Nibbles are the unit of a trie path: each key byte split into two 4-bit halves, so a key becomes a sequence of hex digits and the trie branches sixteen ways at each step. Together they are the substrate the whole state commitment stands on: node → RLP → keccak256 → the hash a parent references.

Why serialization is a consensus problem

Recall the throughline: untrusting strangers must agree on the state of a shared world computer. In the companion ethmini crate the state root is computed by sorting accounts and hashing their serialized bytes:

// ethmini/src/state.rs — the honest simplification
let mut sorted: Vec<(&Address, &Account)> = self.accounts.iter().collect();
sorted.sort_by_key(|(addr, _)| **addr);
let bytes = serde_json::to_vec(&entries).expect("world state is serialisable");
let root = Sha256::digest(&bytes);

That crate uses serde_json and SHA-256 to keep the teaching code readable. But notice the load-bearing line: the accounts are sorted first. Why? Because a HashMap iterates in a randomized order, so two honest nodes with identical state would otherwise serialize to different byte strings and hash to different roots — and disagree about a state they actually share. Sorting makes the bytes a function of the state and nothing else.

That single detail is the whole reason RLP exists. A consensus hash is only meaningful if the serialization feeding it is canonical: one input must map to exactly one byte string, on every machine, in every language, forever. If two encoders could produce two byte strings for the same logical node, they would compute two different hashes, and the network would fork over an ambiguity in a format, not a disagreement about the world. Real Ethereum replaces the crate’s JSON-and-sort shortcut with RLP precisely because JSON is not canonical — whitespace, key order, and number formatting all admit variation.

   same logical data
        │
        ├── encoder A ──▶ bytes₁ ──▶ keccak256 ──▶ hash₁   ✗ if bytes₁ ≠ bytes₂
        └── encoder B ──▶ bytes₂ ──▶ keccak256 ──▶ hash₂       the network forks

   canonicality:  one input ⟶ exactly one byte string ⟶ exactly one hash  ✓

RLP — Recursive Length Prefix

RLP has a deliberately tiny job. It does not know about integers, strings, addresses, or accounts. It knows about exactly two things:

1. a byte array (a “string” — any run of bytes, including empty), and
2. a list of items, where each item is itself either a byte array or another list.

Everything Ethereum serializes — a transaction, an account, a trie node — is first arranged into that nested shape (bytes and lists of bytes and lists of lists…), and RLP flattens it into one byte string. “Recursive” because a list can contain lists; “Length Prefix” because every item announces its length up front so a decoder can walk the bytes with no separators and no ambiguity.

Encoding a single byte array

RLP picks the shortest of a few cases, and the rules pin down which case is legal, so there is only one canonical output:

  A single byte in [0x00, 0x7f]:   encoded as ITSELF, no prefix.
      0x2a                      ─▶  0x2a                (one byte, done)

  A short string (0–55 bytes):     prefix 0x80 + length, then the bytes.
      "dog" = [0x64,0x6f,0x67]  ─▶  0x83 64 6f 67       (0x80+3, then "dog")
      ""    = []                ─▶  0x80                (empty string)

  A long string (56+ bytes):       prefix 0xb7 + (length-of-length),
                                    then the length, then the bytes.
      1024 bytes                ─▶  0xb9 04 00 <bytes>  (0xb7+2, len=0x0400)

The single-byte case is why 0x2a (42) encodes to just 0x2a: values below 0x80 are their own encoding, so the most common small values cost zero overhead. The moment a value could collide with a length prefix (0x80 and up) it gets a one-byte prefix instead. Canonicality lives in the rules: a single byte below 0x80 must not use the 0x81 xx form, and a length must be encoded with no leading zero bytes. A decoder that sees 0x81 2a or a length with a leading zero rejects the input as non-canonical rather than accepting a second spelling of the same value.

Encoding a list

A list uses the same idea, offset into a different prefix range so a decoder can tell a list from a string by the first byte alone:

  A short list (payload 0–55 bytes):  prefix 0xc0 + payload-length,
                                       then the concatenated encodings.
      ["cat","dog"]              ─▶  0xc8 83 63 61 74 83 64 6f 67
                                      └┬─┘ └─── "cat" ──┘ └── "dog" ──┘
                                     0xc0+8 (payload is 8 bytes total)

  A long list (payload 56+ bytes):    prefix 0xf7 + (length-of-length),
                                       then the length, then the encodings.

  The empty list []             ─▶  0xc0

The whole format is four prefix ranges — 0x00–0x7f bare byte, 0x80–0xbf string, 0xc0–0xff list, each split into short/long — and nothing else. There is no type tag for numbers, no field names, no schema. That minimalism is the point: fewer rules means fewer places two implementations can diverge, which is exactly what a consensus format wants.

By the numbers — RLP overhead

RLP’s prefix cost is small and predictable, which matters because every trie node and every transaction pays it.

  Payload size        Prefix bytes   Overhead
  ---------------------------------------------
  1 byte (< 0x80)     0              0%      (encoded as itself)
  1 byte (>= 0x80)    1              100%
  3 bytes  ("dog")    1              33%
  32 bytes (a hash)   1              ~3%
  55 bytes            1              ~1.8%
  56 bytes            2              ~3.6%    (crosses into "long" form)
  1 KiB               3              ~0.3%

  A branch node = a 17-item list of (mostly 32-byte) hashes.
  16 child hashes + 1 value  →  each child: 1 prefix + 32 bytes = 33 bytes
  list payload ≈ 17 × 33 = 561 bytes  →  long-list prefix = 3 bytes (~0.5%)

The takeaway: RLP overhead is a percent or two on real nodes. The cost of the trie is the many 32-byte hashes a node holds, not the encoding that wraps them.

Under the hood — why not just use Protobuf or JSON?

Ethereum predates most of today’s serialization ecosystem, but the deeper reason is canonicality, not history. General-purpose formats optimize for convenience — schemas, forward compatibility, human readability — and every one of those features is a place where two encoders can produce different bytes for the same value:

• JSON admits whitespace, key ordering, 1.0 vs 1, and Unicode escaping. No canonical form ships in the base spec.
• Protobuf does not guarantee canonical output: unknown fields, map ordering, and default-value elision all vary between libraries, and Google explicitly warns against relying on byte-equality.

RLP throws all of that away. It has no schema (so no schema-versioning ambiguity), no field names (so no ordering choice), and strict rules that make any non-shortest encoding invalid. A conformant RLP decoder that accepts a byte string will reject every other byte string that decodes to the same data. That is a strange property to want in an ordinary application — and exactly the property a hash-based consensus system cannot live without.

Nibbles — turning a key into a 16-way path

RLP answers “how do we turn a node into bytes.” Nibbles answer a different question: “as the trie walks from its root toward a key, what is one step?”

A key in the state trie is keccak256(address) — 32 bytes, 256 bits. The trie is a tree keyed by that key, so at each level it must consume some of the key to choose a child. The unit it consumes is a nibble: half a byte, 4 bits, one hexadecimal digit with 16 possible values (0–f).

   one key byte  =  0xA7  =  1010 0111
                     └┬─┘    └┬─┘ └┬─┘
                   split →   0xA   0x7     two nibbles

   key bytes:   A7 3F ...        (32 bytes)
   nibbles:     A 7 3 F ...      (64 nibbles, each 0–15)

So a 32-byte key becomes 64 nibbles, and at each node the trie reads one nibble and follows the corresponding one of sixteen children. This is why the structure is called a hexary (base-16) trie: every branch node has 16 slots, one per possible nibble value (plus a 17th slot for a value that ends exactly here — more on that on the next page).

// The whole of "nibble" logic: split each byte into hi and lo 4-bit halves.
fn to_nibbles(key: &[u8]) -> Vec<u8> {
    let mut out = Vec::with_capacity(key.len() * 2);
    for &b in key {
        out.push(b >> 4);   // high nibble: bits 7..4
        out.push(b & 0x0f); // low nibble:  bits 3..0
    }
    out
}
// to_nibbles(&[0xA7, 0x3F]) == [0xA, 0x7, 0x3, 0xF] == [10, 7, 3, 15]

That is the entire idea. A nibble is not a new data type — it is just a byte split in two so its value lands in 0..=15, the fan-out of one branch node.

Why 16, and not 2 or 256?

The nibble width is a design choice, and it is a direct trade of tree depth against node width — the same trade every trie makes. Call the branching factor b. Two quantities move in opposite directions as b changes:

• Depth — how many nodes you traverse (and, in a Merkle proof, how many hashes you carry) from root to a key. For a k-bit key, depth is k / log₂(b).
• Node width — how big each branch node is, since a branch must reserve a slot per possible child, and each occupied slot holds a 32-byte hash.

   Branching   Bits per   Max depth        Branch node
   factor b    step        (256-bit key)   slots
   --------------------------------------------------
   2  (binary) 1           256             2
   16 (hexary) 4            64              16    ← Ethereum
   256         8            32              256

A binary trie is shallow in fan-out but very deep — up to 256 levels — so a proof carries up to 256 sibling hashes: small nodes, long paths, big proofs. A 256-way trie is shallow (32 levels) but every branch node reserves 256 slots; even sparsely filled, the nodes are wide and wasteful, and RLP-encoding a mostly-empty 256-slot node is costly. 16 sits in the middle: 64-level worst case, 16-slot nodes. Combined with extension nodes (next page) that collapse long shared runs of nibbles, a hexary trie keeps both depth and width modest for the sparse, hash-scattered keys Ethereum actually stores.

By the numbers — depth vs. width for a 256-bit key

   binary (b=2):   depth ≤ 256,  node = 2 slots
                   proof ≈ 256 sibling hashes × 32 B ≈ 8 KiB (worst case)

   hexary (b=16):  depth ≤ 64,   node = 16 slots
                   proof ≈ 64 nodes, each up to 15 sibling hashes;
                   but shared prefixes are collapsed, so real proofs are
                   far shorter than the worst case.

   256-way (b=256): depth ≤ 32,  node = 256 slots
                    each branch reserves 256 hash slots — huge, sparse nodes.

The hexary choice is not the extreme on either axis; it is the compromise that keeps both proof size and node size tolerable.

Putting them together — the node → hash pipeline

RLP and nibbles meet at the moment a node is committed. Here is the pipeline every trie node runs through, and it is the sentence to carry into the next page:

   1. The node's fields (which children? which nibbles? what value?)
          │  arranged as nested byte-arrays and lists
          ▼
   2. RLP-encode  ─────────────▶  one canonical byte string
          │
          ▼
   3. keccak256(bytes)  ────────▶  a 32-byte node hash
          │
          ▼
   4. The PARENT stores this hash in one of its nibble-indexed slots,
      and the node itself is stored in the database under this hash as key.

Two consequences fall out of this pipeline, and both are why the trie works at all:

• The hash is the reference. A parent does not point to a child by memory address or by name; it holds the child’s keccak256(RLP(child)). Because RLP is canonical, that hash is a deterministic fingerprint of the entire subtree beneath it. Change one storage slot of one account and its leaf’s bytes change, so its hash changes, so its parent’s bytes change, so its hash changes — the edit ripples straight up to the state root. This is the Merkle property, and RLP’s canonicality is what makes it sound: the same subtree always hashes the same, on every node, in every client.
• A proof is just a chain of these encoded nodes. To prove one account’s value, a light client is handed the RLP bytes of each node along the nibble-path from root to leaf. It re-hashes each with keccak256, checks each hash appears in the slot the next nibble selects in its parent, and checks the top node hashes to the trusted state root. Nibbles tell it which slot to check at each step; RLP tells it what to hash. We build that proof in full in Merkle Proofs and Light Clients.

Keep the crate’s caveat in mind: ethmini hashes with SHA-256 and skips RLP entirely, because its goal is to show the state-machine idea, not reproduce Ethereum’s exact bytes. Real Ethereum uses keccak256 (the pre-standard Keccak, not the final SHA-3) over RLP. When we say “the hash a parent references” for the rest of this Part, that is the recipe: keccak256(RLP(node)).

The architect’s lens

RLP and nibbles are small, but they are a genuine design decision at the base of the state layer, so they earn the lens.

• Why does it exist? RLP exists to give Ethereum a canonical serialization — one input, one byte string, on every client — so that hashing a node yields the same value everywhere. Nibbles exist to define the step size of a trie path: 4 bits, so a key becomes a sequence of 16-way choices.
• What problem does it solve? They make a hash-based state commitment possible. Without a canonical encoding, two honest nodes could hash the same state to different roots and fork over a formatting difference; without a fixed path unit, there is no well-defined tree to walk. Nibbles also set the depth-vs-width balance of the whole trie.
• What are the trade-offs? RLP buys canonicality by giving up schemas, readability, and self-description — you must know a node’s shape out-of-band to decode it meaningfully. The 16-way nibble choice buys moderate depth at the cost of 16-slot branch nodes; a binary trie would give smaller nodes but far longer proofs.
• When should I avoid it? Off-chain, for ordinary application data, prefer a schema-ed format (Protobuf, JSON, CBOR) — you want their evolvability and tooling, and you don’t need byte-canonicality. RLP earns its keep only where a consensus hash depends on the exact bytes. (Newer Ethereum work leans toward SSZ for consensus-layer data for similar canonicality reasons.)
• What breaks if I remove it? Everything downstream of a node hash. No canonical encoding means no reproducible node hash, which means no reproducible state root, which means state proofs can’t verify and clients can’t agree on state. Remove nibbles and there is no defined path through the trie at all.

Check your understanding

1. Why must the serialization feeding a consensus hash be canonical, and what goes wrong on the network if it isn’t?
2. Encode the byte array "dog" ([0x64, 0x6f, 0x67]) and the single byte 0x2a in RLP. Why does 0x2a need no length prefix?
3. A key is the 32-byte value keccak256(address). How many nibbles is that, and how many children can a branch node have?
4. Explain the trade-off that makes Ethereum choose a 16-way trie over a binary or a 256-way one. Which quantity does each extreme make worse?
5. Write the four-step pipeline from a trie node to the hash its parent stores, and state which primitive does which job.

Show answers

1. A consensus hash is only meaningful if identical logical data always produces identical bytes. If serialization is non-canonical, two honest nodes can encode the same state differently, hash to different roots, and fork over a formatting ambiguity rather than any real disagreement about the world. Canonicality (one input → exactly one byte string) removes that failure mode.
2. "dog" → 0x83 64 6f 67: the 0x83 prefix is 0x80 + 3 (a short string of length 3), followed by the three payload bytes. 0x2a → 0x2a: any single byte below 0x80 is its own RLP encoding, so it needs no prefix; adding one (0x81 2a) would be a non-canonical second spelling and is rejected.
3. Each byte splits into two 4-bit nibbles, so 32 bytes = 64 nibbles, each a hex digit 0–f. A branch node has 16 child slots (one per nibble value), plus a 17th slot for a value terminating exactly at that node — making it a hexary trie.
4. The trade is tree depth vs. node width, set by the branching factor. A binary trie (b=2) has tiny 2-slot nodes but up to 256 levels, so proofs carry hundreds of sibling hashes (depth is worse). A 256-way trie (b=256) is shallow (32 levels) but every branch reserves 256 hash slots, making nodes huge and sparse (width is worse). 16 is the compromise: 64-level worst-case depth and 16-slot nodes.
5. (1) Arrange the node’s fields as nested byte-arrays and lists; (2) RLP-encode them into one canonical byte string; (3) keccak256 that string to get a 32-byte node hash; (4) the parent stores that hash in the nibble-indexed slot for the child, and the node is keyed by the hash in the database. Nibbles pick which slot; RLP produces what gets hashed.