The RLP protocol is a procedure used to serialize (convert to a stream of bytes) a nested data structure. It is used in Ethereum and it was first proposed in the yellow paper. In this text, I would like to go over the inner workings of the protocol and the reasons behind some choices that may appear odd at first glance.

The Basics

In RLP, an object is defined as a stream of bytes. A nested data structure is an object and it is composed of a sequence of objects too. This is formally defined in the yellow paper with equations 178 to 180.

\[T \equiv \mathbb{L} \uplus \mathbb{B}\] \[\mathbb{L} \equiv \{ \mathbf{t} : \mathbf{t} = (\mathbf{t}[0],\mathbf{t}[1],\ldots) \wedge \forall n < \lVert \mathbf{t} \rVert : \mathbf{t}[n] \in \mathbb{T} \}\] \[\mathbb{B} \equiv \{ \mathbf{b} : \mathbf{b} = (\mathbf{b}[0],\mathbf{b}[1],\ldots) \wedge \forall n < \lVert \mathbf{b} \rVert : \mathbf{b}[n] \in \mathbb{O} \}\]

Here, $\mathbb{T}$ is the set of all possible nested data structures, $\mathbb{L}$ is the set of all sequences of data structures and $\mathbb{B}$ is the set of all sequences of bytes ($\mathbb{O}$ is the set of all possible bytes). As the name suggests, an nested data structure is recursive and so is its definition.

All in all, these formulas elegantly define what an RLP object is. RLP is meant to serialize the object into a new object that would belong to $\mathbb{B}$. In order to achieve this, a form of protocol needs to be conceived. It would be used to encode and decode the data structure.

The Protocol

Before looking at the protocol, let us think about how one would encode a nested data structure into a byte stream.

Given the definitions of the previous section, a nested data structure is essentially a list of objects of the same nature as the one being describe with this sentence. The recursion stops when the object is no longer a list of objects but rather an explicit list of bytes. Similarly, a nested data structure could be viewed as a tree of objects. A leaf is a list of bytes whereas any non-leaf nodes are list of abstract objects. This distinction must be reflected in the protocol. When encoding, one must recursively encode objects until a leaf (list of bytes) is encountered and explicitely label that branch as being a leaf. This is usually done using a header to the actual data. When decoding, this header would be used to know how to interpret the data.

In Ethereum, equations 181 to 186 make this distinction. If you have taken the time to look at the different cases in those formulas, you have probably wondered why is there an additional distinction between short leaves, long leaves, short objects and long objects. This is because RLP aims to minimize the amount of bytes for the encoding. It can be particularly useful if the objects to serialize are small but numerous.

The author of RLP decided to use a single byte for the header. The catch is that since there are only two cases to the encoding (a leaf or a non leaf), most of the values that a byte can take remain unused. A single bit would have sufficed. That being said, since the byte is the smallest unit representable in a machine, we are stuck with it. The author decides to use the remaining values for very small sequences.

A leaf that is a single byte long is encoded in the header immediately as long as its value is lower than 128. Then, for leaves of length smaller than 56, the size is encoded into the header and it is concatenated with the data. Finally, for anything longer or equal to 56 bytes, up to 8 extra bytes are used to encode the length and the amount of these bytes is encoded in the header.

\[R_b(\mathbf{x}) \equiv \begin{cases} \mathbf{x} & \lVert \mathbf{x} \rVert = 1 \wedge \mathbf{x}[0] < 128\\ (128 + \lVert \mathbf{x} \rVert) \cdot \mathbf{x} & \lVert \mathbf{x} \rVert < 56\\ (183 + \lVert \text{BE}(\lVert \mathbf{x} \rVert) \rVert) \cdot \text{BE}(\lVert \mathbf{x} \rVert) \rVert) & \quad\text{otherwise}\\ \end{cases}\]

For non-leaves, objects that are at most 56 bytes long have their length encoded in the header. For longer objects, up to 8 bytes are used to encode their size and the amount of these bytes is encoded in the header. In this case, the data is a concatenation of the RLP encoding of each children node.

\[R_l(\mathbf{x}) \equiv \begin{cases} (128 + \lVert s(\mathbf{x}) \rVert) \cdot s(\mathbf{x}) & \lVert s(\mathbf{x}) \rVert < 56\\ (247 + \lVert \text{BE}(\lVert s(\mathbf{x}) \rVert) \rVert) \cdot \text{BE}(\lVert s(\mathbf{x}) \rVert) \rVert) & \quad\text{otherwise} \\ \end{cases}\]

These choices may look odd but they are made in the goal of minimizing the amount of bytes of the encoding. A simpler protocol could be devised where each object uses a byte to distinct leaves from non leaves and 8 bytes to represent the size. This protocol would end up using a lot more bytes than RLP. Here is a figure that shows the amount of bytes used by RLP and a more naive protocol:

makes the distinction between a short object and a long object.

Performance

At first glance, the recursive prefixing of the data with a header is severely inneficient. As a matter of fact, if a regular string like object is used and if headers are appended using new copies, every byte in a leaf will be written $O(h) \equiv O(\log{n})$ times, where $h$ is the height of the tree and $n$ is the number of nodes in the tree. All in all, the encoding would take about $O(n\log{n})$ time. This can be made more efficient. The fact that arrays grow from left to right is a simple programming choice. One could use reverse arrays (writting the data and the header in the reverse order and dropping the header after the data and reversing the whole byte array at the end) or right to left growing arrays. The resulting time complexity would end up being $\Theta(n)$.

Conclusion

RLP is not so difficult to understand. The constants were chosen with space minimization in mind.

References

• Wood, Gavin. (2020-09-05). Ethereum: A Secure Decentralised Generalised Transaction Ledger. Petersburg Version.