RLP encoding

Recursive Length Prefix (Yellow Paper Appendix B), the canonical serialization Ethereum uses for accounts, block headers, transactions, receipts, and Merkle-Patricia trie nodes. RLP encodes a recursive structure of byte strings and lists; it imposes no type semantics, only a minimal length-prefixed framing.

A byte < 0x80 is its own encoding; strings of length n ≤ 55 use 0x80 + n; longer strings use 0xb7 + |len| followed by the big-endian length. Lists mirror this with the 0xc0/0xf7 prefix bands over an already-encoded payload. Integers encode as their minimal big-endian byte string with no leading zeros. Decoding proceeds one level at a time; a field reference retains the complete encoded item as a source slice and its content length without copying; the content is always the corresponding suffix.

Malformed RLP terminates validation with fatal_error(RlpDecode) at the point where the invalid encoding is detected.

Constants

RLP's short-form threshold and the fixed encoded widths used throughout the execution-layer data model.

let RLP_SHORT_LENGTH_LIMIT

let RLP_SHORT_LENGTH_LIMIT : int(55) = 55

let RLP_WORD_LENGTH_LIMIT

let RLP_WORD_LENGTH_LIMIT : int(32) = WORD_BYTE_LENGTH

let RLP_UINT64_LENGTH_LIMIT

let RLP_UINT64_LENGTH_LIMIT : int(8) = EIGHT_BYTE_LENGTH

let RLP_ENCODED_WORD_LENGTH

let RLP_ENCODED_WORD_LENGTH : int(33) = 33

let RLP_ENCODED_ADDRESS_LENGTH

let RLP_ENCODED_ADDRESS_LENGTH : int(21) = 21

type rlp_scratch_length

An RLP byte count that can be materialized in the scratch arena. The host scratch-region limit is enforced while recursive collection totals are accumulated.

type rlp_scratch_length = range(0, scratch_region_bound)

type rlp_natural_valid

Values accepted by the generic natural-number RLP helpers. Canonical RLP is unbounded; optimized builds refine values entering the native encoder.

type rlp_natural_valid('value : Int) -> Bool = 0 <= 'value

type rlp_natural_increment_valid

Natural values that can be incremented while counting encoded bytes.

type rlp_natural_increment_valid('value : Int) -> Bool = 0 <= 'value

type rlp_natural_size

Encoded width returned by the generic natural-number RLP helper.

type rlp_natural_size = nat

function rlp_scratch_small_length

function rlp_scratch_small_length(value) = value

function rlp_scratch_length_add

function rlp_scratch_length_add(left, right) =
    if right <= sizeof(scratch_region_bound) - left then {
        left + right
    } else {
        fatal_error(RlpDecode)
    }

The encoders

function rlp_nat_length_byte

function rlp_nat_length_byte(value : range(0, 255)) -> byte =
    get_slice_int(8, value, 0)

function rlp_byte_length_byte

function rlp_byte_length_byte(value) = {
    assert(value <= 255);
    let length = value;
    get_slice_int(8, length, 0)
}

function rlp_length_word

function rlp_length_word(value) = {
    word_of_nat_byte_count(value)
}

function rlp_minimal_word_len

function rlp_minimal_word_len(w) = {
    word_byte_length(w)
}

function rlp_natural_increment

function rlp_natural_increment(value) = value + 1

function rlp_minimal_uint_len

Computes a natural's minimal big-endian byte length recursively.

function rlp_minimal_uint_len(n) =
    if n == 0 then {
        0
    } else {
        let remaining_length = rlp_minimal_uint_len(n / 256);
        rlp_natural_increment(remaining_length)
    }

function rlp_length_prefix_len

function rlp_length_prefix_len(len) =
    if len <= RLP_SHORT_LENGTH_LIMIT then {
        1
    } else {
        let length_word = rlp_length_word(len);
        1 + rlp_minimal_word_len(length_word)
    }

function rlp_string_size

function rlp_string_size(len, first) = {
    if (len == 1) & (first[7] == bitzero) then {
        1
    } else {
        rlp_length_prefix_len(len) + len
    }
}

function rlp_input_slice_size

function rlp_input_slice_size(data) = {
    let len = data.len;
    let first =
        if len == 0 then 0x00 else slice_byte(data, 0);
    rlp_string_size(len, first)
}

function rlp_materialized_slice_size

Returns the materializable RLP width of a byte slice after its caller has selected the backing region and loaded the first byte.

function rlp_materialized_slice_size(length : rlp_scratch_length, first : byte) -> rlp_scratch_length =
    if (length == 1) & (first[7] == bitzero) then {
        1
    } else {
        let prefix_size = rlp_length_prefix_len(length);
        let prefix_length = rlp_scratch_small_length(prefix_size);
        rlp_scratch_length_add(length, prefix_length)
    }

function rlp_scratch_region_size

Returns the materializable RLP width of a scratch-backed byte slice.

function rlp_scratch_region_size(data : ScratchSlice) -> rlp_scratch_length = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_materialized_slice_size(data.len, first)
}

function rlp_log_data_size

Returns the materializable RLP width of a retained log-data slice.

function rlp_log_data_size(data : LogDataSlice) -> rlp_scratch_length = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_materialized_slice_size(data.len, first)
}

function rlp_uint_word_size

function rlp_uint_word_size(w) = {
    let len = rlp_minimal_word_len(w);
    let first =
        if len == 1 then word_low_byte(w) else 0x00;
    if (len == 1) & (first[7] == bitzero) then {
        1
    } else {
        1 + len
    }
}

function rlp_uint_nat_size

function rlp_uint_nat_size(n) = {
    if n < sizeof(word_modulus) then {
        let word = u256(n);
        rlp_uint_word_size(word)
    } else {
        /* n >= 2^256 implies a minimal encoding of at least 33 bytes, so the
         * single-byte RLP case is unreachable on this branch. */
        let len = rlp_minimal_uint_len(n);
        if len <= RLP_SHORT_LENGTH_LIMIT then {
            1 + len
        } else {
            1 + rlp_minimal_uint_len(len) + len
        }
    }
}

function rlp_uint_u64_size

function rlp_uint_u64_size(n) =
    if n < 2 ^ 7 then {
        1
    } else if n < 2 ^ 8 then {
        2
    } else if n < 2 ^ 16 then {
        3
    } else if n < 2 ^ 24 then {
        4
    } else if n < 2 ^ 32 then {
        5
    } else if n < 2 ^ 40 then {
        6
    } else if n < 2 ^ 48 then {
        7
    } else if n < 2 ^ 56 then {
        8
    } else {
        9
    }

function rlp_word_size

function rlp_word_size() -> int(33) = RLP_ENCODED_WORD_LENGTH

function rlp_addr_size

function rlp_addr_size() -> int(21) = RLP_ENCODED_ADDRESS_LENGTH

function rlp_list_size

function rlp_list_size(content_len) = {
    rlp_length_prefix_len(content_len) + content_len
}

function rlp_scratch_list_size

Adds the canonical list prefix to a materializable RLP content length.

function rlp_scratch_list_size(content_len : rlp_scratch_length) -> rlp_scratch_length = {
    let prefix_size = rlp_length_prefix_len(content_len);
    let prefix_length = rlp_scratch_small_length(prefix_size);
    rlp_scratch_length_add(content_len, prefix_length)
}

function rlp_input_scratch_slice_size

Returns the materializable RLP width of a source-backed byte slice.

function rlp_input_scratch_slice_size(data : StatelessInputSlice) -> rlp_scratch_length = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_materialized_slice_size(data.len, first)
}

function rlp_scratch_scratch_slice_size

function rlp_scratch_scratch_slice_size(data : ScratchSlice) -> rlp_scratch_length =
    rlp_scratch_region_size(data)

function rlp_log_scratch_slice_size

Sizes a retained log-data slice for the materializable overload.

function rlp_log_scratch_slice_size(data : LogDataSlice) -> rlp_scratch_length =
    rlp_log_data_size(data)

function rlp_write_string_prefix

function rlp_write_string_prefix(len, first) = {
    if (len == 1) & (first[7] == bitzero) then {
        return ()
    };
    if len <= RLP_SHORT_LENGTH_LIMIT then {
        let length_byte = rlp_length_byte(len);
        let prefix = add_bits(0x80, length_byte);
        scratch_push_byte(prefix)
    } else {
        let length_word = rlp_length_word(len);
        let length_len = rlp_minimal_word_len(length_word);
        let length_byte = rlp_length_byte(length_len);
        let prefix = add_bits(0xb7, length_byte);
        scratch_push_byte(prefix);
        scratch_push_word_be(length_word, length_len)
    }
}

function rlp_write_list_prefix

function rlp_write_list_prefix(content_len) = {
    if content_len <= RLP_SHORT_LENGTH_LIMIT then {
        let length_byte = rlp_length_byte(content_len);
        let prefix = add_bits(0xc0, length_byte);
        scratch_push_byte(prefix)
    } else {
        let length_word = rlp_length_word(content_len);
        let length_len = rlp_minimal_word_len(length_word);
        let length_byte = rlp_length_byte(length_len);
        let prefix = add_bits(0xf7, length_byte);
        scratch_push_byte(prefix);
        scratch_push_word_be(length_word, length_len)
    }
}

function rlp_write_input_slice

Appends a source-backed byte slice as an RLP string.

function rlp_write_input_slice(data : StatelessInputSlice) -> unit = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_write_string_prefix(data.len, first);
    scratch_push_slice(data)
}

function rlp_write_scratch_slice

Appends a scratch-backed byte slice as an RLP string.

function rlp_write_scratch_slice(data : ScratchSlice) -> unit = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_write_string_prefix(data.len, first);
    scratch_push_slice(data)
}

function rlp_write_log_data_slice

Appends a retained log-data slice as an RLP string.

function rlp_write_log_data_slice(data : LogDataSlice) -> unit = {
    let first =
        if data.len == 0 then 0x00 else slice_byte(data, 0);
    rlp_write_string_prefix(data.len, first);
    scratch_push_slice(data)
}

function rlp_write_uint_word

function rlp_write_uint_word(w) = {
    let len = rlp_minimal_word_len(w);
    let first =
        if len == 1 then word_low_byte(w) else 0x00;
    rlp_write_string_prefix(len, first);
    let word = u256(w);
    scratch_push_word_be(word, len)
}

function rlp_write_uint_nat

function rlp_write_uint_nat(n) =
    if n < sizeof(word_modulus) then {
        let word = u256(n);
        rlp_write_uint_word(word)
    } else {
        fatal_error(InvalidConfig)
    }

function rlp_write_uint_u64

function rlp_write_uint_u64(n) = {
    let word = u256(n);
    rlp_write_uint_word(word)
}

function rlp_write_word

Appends one full-width EVM word as an RLP byte string.

function rlp_write_word(w : word) -> unit = {
    rlp_write_string_prefix(WORD_BYTE_LENGTH, 0x00);
    scratch_push_word_be(w, WORD_BYTE_LENGTH)
}

function rlp_write_addr

Appends one Ethereum address as an RLP byte string.

function rlp_write_addr(a : address) -> unit = {
    rlp_write_string_prefix(ADDRESS_BYTE_LENGTH, a[0]);
    scratch_push_address(a)
}

The scratch encoder

An encoder reserves its complete output before the first write. The expected length is checked once at the boundary, keeping allocation and scratch lifetime out of domain callers while leaving primitive writes direct and allocation-free.

type RlpEncoder

One exact-size RLP construction in the shared scratch arena.

struct RlpEncoder = {
    start : source_pointer,
    expected_len : source_length,
}

function rlp_encoder_begin

function rlp_encoder_begin(expected_len) =
    struct { start = scratch_reserve(expected_len), expected_len = expected_len }

function rlp_encoder_finish

Finishes an exact-size construction and retains its encoded bytes.

function rlp_encoder_finish(encoder : RlpEncoder) -> ScratchSlice = {
    let encoded = scratch_finish(encoder.start);
    assert(encoded.len == encoder.expected_len, "RLP encoder length");
    encoded
}

function rlp_encoder_rewind

Releases every byte appended by an encoder after its result is consumed.

function rlp_encoder_rewind(encoder : RlpEncoder) -> unit =
    scratch_rewind(encoder.start)