Understanding Ethereum’s RLP

In short as RLP, RLP is the package Ethereum used to serialize all objects to the array of bytes.
It is described on Yellow Paper with many formulas and is very difficult to understand.

Because Ethereum is a decentralized blockchain, that enables the execution of smart contracts and the storage of data on the blockchain, its need to be serialized or converted into a binary format, stored in a minimal amount of space in the blockchain.

RLP is a prefix-based encoding schema that encodes arbitrarily structured binary data(byte arrays) in a way that is easy to encode and decode.
RLP algorithm works by recursively encoding a list of items.

An item is defined as follows:

• A string(byte array)
• A list of “items” itself

For example:

• A string(byte array), includes an empty string
• A list containing any number of string
• A complex data structure like ["cat", ["dog", "mouse"], [], ["""]]

Walk through into Yellow Paper(Appendix B)

We have three formulas that describe arbitrarily structured binary data(byte arrays):

• T: Arbitrarily structured binary data, is a set of byte arrays and structural sequences
• L: Set of all tree-like structures that are not a single leaf
• O: Set of 8-bit bytes
• B: Set of all sequences of bytes(bytes array or a leaf in tree)
• We use disjoint union to distinguish the empty byte array(in B) vs empty list(in L).

We define the RLP function as RLP through two sub-functions:

• The first handling of the byte arrays
• The second handle the sequences of further values
  

We will deep dive into the first function that handles the byte array, RLP(B). If the value to be serialized is a
byte array, the RLP(B) will take one of three forms:

• A single byte less than 128(decimal), the output is same the input
• If the array bytes contain fewer than 56 bytes, then the output is equal to the input prefixed by the byte
  equal to the length of the array byte + 128
• Otherwise, the output is equal to the big-endian representation of the input length in front of the input and then preceded by (183 + the length of the big end of the input)
  

Second, we will see how the RLP(L) works. We use RLP(L) to encode each item, then concatenate the output.

• If the length is smaller than 56, the output is equal: 192 + length of item + item
• Otherwise, the output is equal: 247 + length of the big-endian of the length of item + the big-endian of the length of item + item
  

You can see s(x) is the recursive of RLP with each item.

RLP algorithm as code like(example from ethereum.org):

You can see the example in the Ethereum documentation with some inputs:

• A String “ethereum” => [“0x88”, “e”, “t”, “h”, “e”, “r”, “e”, “u”, “m”] => because the length of this
  string is 8 characters, is smaller than 56. So the output is encoded_length(8, 128) + input = chr(136) + “ethereum” = [“0x88”, “e”, “t”, “h”, “e”, “r”, “e”, “u”, “m”]
• A list [“ethereum”, “foundation”]:
  • Same as the example above, we got the output of rlp_encode("ethereum") = ["0x88", "e", "t", "h", "e", "r", "e", "u", "m"]
  • And rlp_encode("foundation") = ["0x8A", "f", "o", "u", "n", "d", "a", "t", "i", "o", "n"]
  • So, the output is rlp_encode(["ethereum", "foundation"]) = encode_length(20, 192) + ["0x88", "e", "t", "h", "e", "r", "e", "u", "m", "0x8A", "f", "o", "u", "n", "d", "a", "t", "i", "o", "n"] = ["0xD4", "0x88", "e", "t", "h", "e", "r", "e", "u", "m", "0x8A", "f", "o", "u", "n", "d", "a", "t", "i", "o", "n"]

RLP decoding

Because of the rules of RLP encoding, the input of RLP decoding is an array of binary data.

• Depending on the first byte in the input, we can determine the data type and the length of the data and offset.
• Depending on the data type and offset of data, decode the data correspondingly.
• Continue the loop to decode the remain of input.

With the RLP formulas, we can determine to rules of decoding the data type and offset by the following:

• If the range of the first byte is from [0x00, 0x7f], and the length of the input is 1, so the data type is a string and the data is the string itself.
• If the range of the first byte is from [0x80, 0xb7], the data type is a string, and the length of the string is equal to the first byte minus 0x80
• If the range of the first byte is [0xb8, 0xbf], and the length of the string whose length in bytes is equal to the first byte minus 0xb7 follows the first byte, and the string follows the length of the string;
• If the range of the first byte is [0xc0, 0xf7], and the concatenation of the RLP encodings of all items of the list which the total payload is equal to the first byte minus 0xc0 follows the first byte;
• If the range of the first byte is [0xf8, 0xff], and the total payload of the list whose length is equal to the first byte minus 0xf7 follows the first byte, and the concatenation of the RLP encodings of all items of the list follows the total payload of the list;

Source: Ethereum Docs

The pseudo code from Ethereum Docs:

Very difficult to fully understand with these formulas, so we need to debug to know what the output
when we use RLP to encode/decode arbitrarily structured binary data.

Go-ethereum RLP

If you don’t familiar with Golang, you can read other versions written by Typescript
With me, this version is easier to understand than the original version written by Golang

RLP package structures:

encode.go

First, let’s see the Encode interface

This interface has only one function, that takes io.Writer as the input, and write the output to io.Writer directly.
Everything is stored on Ethereum blockchain so uses RLP to encode. There are so many implementations:

Next, we have a function called func Encode(w io.Writer, val interface{}) error, that will take the w and v to encode to binary data.

This is main function that is called by the implementations to encode the input. Go-ethereum use encBufferFromWriter to reduce the allocation, we will go into it.

The main reason because the authors are using encBuffer struct to encode the input data. So, if the w is encBuffer type, we reuse it to encode the input.

But I have a question, why they need to create a new struct encBuffer to encode? Let’s see. In some previous of Go-ethereum, they don’t use this struct.
The struct encBuffer is:

and in encbuffer.go, we have a sync pool that stores encBuffer