Ethereum Under the Hood- Part 2 (RLP Encoding)-ver 0.3
Tags: ethereum, blockchain, cryptocurrency
Published: 2021-03-10 13:36:17

---
title: Ethereum Under the Hood- Part 2 (RLP Encoding)-ver 0.3
published: true
date: 2021-03-09 05:15:06 UTC
tags: ethereum,blockchain,cryptocurrency
canonical_url: https://medium.com/coinmonks/ethereum-under-the-hood-part-2-rlp-encoding-ver-0-3-c37a69781855
---

Orignal published date:[Apr 25, 2018](https://medium.com/coinmonks/ethereum-under-the-hood-part-ii-i-933411deebe1?source=post_page-----933411deebe1--------------------------------) ·

_Update: Grammar fixes_

_Part-2 of the article, if you have not gone through Part-1, please do. We will cover how Ethereum uses_ **_Recursive Length Prefix_** _to encode data and state in this article._

This is a slightly longer read, so get yourself some coffee and be prepared to get confused, I did reading about RLP

**The Problem:**

Ethereum is a global computer and data to be processed by Ethereum has to be sent across the wire compactly and efficiently. Ethereum team chose **Recursive Link Prefix** decoding/encoding algorithm to achieve the above-stated goals. If you go through articles on Ethereum there are references to the “[stack machines](https://github.com/ethereum/wiki/wiki/Ethereum-Development-Tutorial#state-machine)” and its usage in Ethereum, so let’s cover them for a little bit.

**The Stack Machine:**

Let’s briefly touch on what is a [Stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)).

![](https://cdn-images-1.medium.com/max/700/0*KoN3TUmCCfGoiRzQ.png)<figcaption><strong>Stack Machine</strong></figcaption>

[Source: Wiki](https://en.wikipedia.org/wiki/File:Lifo_stack.png)

The Ethereum Virtual Machine(EVM) is a Stack-based machine which stores instructions and data in a stack-based using the LIFO(Last In First Out) method. Let’s take the example of a string “ **cat** ” and see how it’s **pushed** into a stack

```
['c','a','t'] 
so the PUSH operation will be:
**PUSH(‘c’)   
PUSH(‘a’)   
PUSH(‘t’)** When data has to be retrieved POP function is used in the order it was put in:
**POP('t')  
POP('a')  
POP('c')**  
```

Ethereum Stack has certain restrictions. The Stack depth is maxed out at [1024](https://ethereum.stackexchange.com/questions/26938/why-is-the-evm-stack-limited-to-1024) elements, and max word size per instruction is 256 bits or max of 32 bytes. I think of this as how broad the instruction set can be, as depicted in the diagram below.

![Stack](https://cdn-images-1.medium.com/max/888/0*smlie3lAWS7nnMOs.png)<figcaption>Ethereum Stack Machine(1024 elements max height, 32 bytes max word size)</figcaption>

Stack Machines are ideal to have a mini-compiler implemented. Let’s take an expression

```
[**[0x12344**]**,[(a+b\*c/d**), **'x', 9]** ]
```

A couple of things to consider, there are two items on the above array. A hex value and expression. Think of hex value (0x12344) as an Ethereum address and the expression as the state change information. Note that the max size of the word is 256 bits. Let’s consider [(a+b\*c/d), ‘x’, 9]. The whole expression is less than 32 bytes. Why 32 bytes you ask? Here is a good [stack exchange](https://ethereum.stackexchange.com/questions/7382/rationale-behind-256-bit-words-in-evm)discussion on that topic.

Check out this youtube video about [Stack Machines](https://www.youtube.com/watch?v=GtKJ-ccF3oI)

**Byte Arrays and Items** :

Let’s [recap](https://medium.com/@deepakraous/ethereum-under-the-hood-part-i-ver-0-1-4f2fb24b3d68) some concepts which we learned from the previous article. All data in Ethereum is [serialized](https://stackoverflow.com/questions/3784143/what-is-the-difference-between-serializing-and-encoding) and deserialized as a [byte-array](https://stackoverflow.com/questions/4019837/what-do-we-mean-by-byte-array). Put, an array of bytes is a [byte-array](https://stackoverflow.com/questions/4019837/what-do-we-mean-by-byte-array), it’s worth repeating some examples of these byte-arrays.

**RLP** encoding function accepts an **item** or a collection of  **items**

- A string (i.e., byte array) is an item
- A list of items is also an item

**_Examples of item and items_**

- **“Bitcoin”**
- **[[] ]**
- **[“Lion” ]**
- **[[ “cat”, 123, ‘d’, ‘o’, ‘g’] ]**

**Now, what is _Recursive Link Prefix_ (RLP)?**

RLP is a set of rules to encode and decode structures and data. _Part II. I_ focus on **RLP encoding; we** will cover **RLP**  **decoding** in _part II.II_ of the article in later posts. Let us recap what’s inside of an RLP. If you recall in the previous [article](https://medium.com/@deepakraous/ethereum-under-the-hood-part-i-ver-0-1-4f2fb24b3d68) we discussed **“items”** , all “items” are **byte-arrays**. RLP function accepts one parameter of type  **object.**

A critical aspect of RLP is that it leaves encoding rules of specific structure to the top level layers, for example, if there is another structure, e.g. {“abc” }. RLP will consider this as a string element and will leave the encoding to the top level layers

```
_function_ encodeRLP**(rawData)**{ 
  .....,
 return encodedData #type bytearray;
}_function_ decodeRLP**(bytearray stateInfo)**{
  .....,
  return decodeData #raw;
}
```

Let’s get into those RLP **encoding** rules for these objects :

_Tip: I would suggest to open up an_ [_ASCII_](https://www.asciitable.com/)_ chart._

### RLP encoding rules are defined as follows:

**_Rule 1: When encoding a payload with 1 byte and value in that byte falls within the following range [0x00, 0x7f], in other words within [0, 127] then encode the single byte as RLP itself_**

```
$ 120 to rlp
**_78_**   
$ 127 to rlp
**_7F_**  
$ "a" to rlp
**a**
```

so encoding 120 into RLP results in **_78_** and 127 results in **_7F,_** and for “a”, encoding results in “ **a** ” and the byte size is 1 and encoding rule#1 applies.

**_Rule 2: When encoding a string (in byte array) which falls between 0 and 55 bytes apply the following logic._**

**0x80+length(string),string**

```
string "dog" to byte-array in hex is [0x64,0x6f,0x67] and size of the byte array is 3
```

Let us encode item “ **dog** ” into RLP, the size aka length of byte array is 3, so encoding into RLP will result in

[0x80+3,0x64,0x6f,0x67] -> [**0x83** , 0x64, 0x6f, 0x67]

e.g.: Another example would be “ **hello world** ” of RLP encoding. Size of “hello world” is 11 bytes.

```
$ "hello world" to rlp
 [**0x8B** 0x68 0x65 0x6C 0x6C 0x6F 0x20 0x77 0x6F 0x72 0x6C 0x64]
```

**_Rule 3: When encoding a string (in byte array) greater than 55 bytes apply the following rule._**

```
1)0xb7+length_in_bytes(byte_size(string)) 
2)length(string)
3)encoded string  
Join 1,2,3
```

Let’s take an example string “Hello there, I am a very very long string, and I am going get encoded in RLP!”. The length of the **string** is **76,** so rule 3 applies. Let’s get a couple of prereqs out of the way.

```
_a)len raw string = 76   
b)byte\_size(string) =76   
c)length\_in\_bytes(byte\_size(string) ) = 1_   
```

Following the steps laid out by rule#3

1. 0xb7 + 1
2. 76
3. “Hello there, I am a very very long string, and I am going get encoded in RLP!”
4. (0xb7+1) , 76, “Hello there, I am a very very long string, and I am going get encoded in RLP!”

So the final RLP encoding in hex is:

```
**B84C** _48656C6C6F2074686572652C204920616D206120766572792076657279206C6F6E6720737472696E6720616E64204920616D20676F696E672067657420656E636F64656420696E20524C5021_
```

**_Rule 4: When encoding a list and the encoded payload in the list is between 0–55 bytes apply the following encoding rule._**

```
1)0xc0+length of (list)) 
2)Encoded string
Join 1,2
```

Given an input to RLP encoding with **[“dog”, “mouse”, “tigers”, 127]**

We need to encode the payload within the list first.

- “dog” : **0x83** , 0x64, 0x6F, 0x67
- “mouse” : **0x85**  ,0x6D, 0x6F ,0x75, 0x73, 0x65
- “tigers” : **0x86** , 0x74 ,0x69 ,0x67 ,0x65 ,0x72 ,0x73
- 127 : 0x7F

Now the list with the encoded payload looks like this:

[**0x83** 0x64 0x6F 0x67 **0x85** 0x6D 0x6F 0x75 0x73 0x65 **0x86** 0x74 0x69 0x67 0x65 0x72 0x73 **0x7F**] and the length of the list is 18(12 in hex)

so final output of this rule is:

1. 0xc0+12 :  **0xd2**
2. [**0x83** 0x64 0x6F 0x67 **0x85** 0x6D 0x6F 0x75 0x73 0x65 **0x86** 0x74 0x69 0x67 0x65 0x72 0x73 **0x7F **]
3. Union of 1 and 2
4. Final output : **0xd2**  **0x83** 0x64 0x6F 0x67 **0x85** 0x6D 0x6F 0x75 0x73 0x65 **0x86** 0x74 0x69 0x67 0x65 0x72 0x73  **0x7F**

**_Rule 5 : When encoding a list and the encoded payload in the list is greater than 55 bytes apply the following encoding rule._**

```
1)0xf7+length_in_bytes(item 2)
2)length(payload)
3)Encoded payload
Join 1,2,3
```

I would let you do the rest, very similar to the rule above.

**Finally a couple of notes**

- RLP encodes positive integers in [Big Endian format,](https://betterexplained.com/articles/understanding-big-and-little-endian-byte-order/)and discards the leading zeros, and integer value zero is the same as an empty byte array.
- There are certain constants for empty lists, string, and integer 0

```
1) Empty List **[]** encoded to **0xC0**
2) Empty String **""** encoded to **0x80**
3) Integer **0** encoded to **0x80**
```

Recap Recap Recap

My recommendation is to let this digest and come back to the article again. I am not 100% sure on some of the finer details either, but I did get some useful perspectives on the design decision and some fantastic help from the good folks at stack-exchange.

Let’s recap:

- RLP is a set of rules to encode an item or a list of items.
- RLP has a different set of rules based on the size of the payload.
- Strings is a byte array.
- Empty strings, lists have a predefined value.
- RLP is used [due](https://ethereum.stackexchange.com/questions/19092/why-was-rlp-chosen-as-the-low-level-protocol-encoding-algorithm) to its capability to compact data and is simple.

_Tip: Try reading the_ [_rationale_](https://github.com/ethereum/wiki/wiki/Design-Rationale) _on the design decisions on why the Ethereum team choose RLP. There are various implementations of RLP. I would recommend going through them. I did refer to implementation in_ [_Elixir_](https://elixir-lang.org/) _and Ruby._

There are also other great medium posts on RLP which I entirely referred to go and will continue to do for future reference. Check out my [implementation](https://github.com/deepakraous/elixir_rlp) with some help of code snippets from [girishramnani](https://medium.com/u/555875ec10a0?source=post_page-----933411deebe1--------------------------------), and many thanks to [@kvkalidindi](http://twitter.com/kvkalidindi) for proofreading and valuable comments.

In the next article, _Part 3_ **_,_** we will cover **RLP decoding** with some reference to implementations.

References:

- [Ethereum Building Blocks - Part 1: RLP](http://hidskes.com/blog/2014/04/02/ethereum-building-blocks-part-1-rlp/)
- [Data structure in Ethereum. Episode 1: Recursive Length Prefix (RLP) Encoding/Decoding.](https://medium.com/@phansnt/data-structure-in-ethereum-episode-1-recursive-length-prefix-rlp-encoding-decoding-d1016832f919)
- [Understanding the ethereum trie](https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/)

* * *