Ethereum Building Blocks - Part 1: RLP

written Apr 2nd, 2014 in ethereum, rlp

In this series of blog posts I will try to write more about the parts that, when combined, make up the new cryptocurrency for social contracts Ethereum.

I write these posts mostly for myself to make sure I really understand the content but I reckon it might also be helpful as an introduction to anybody who wants to get involved with the development.

In this first installment I will be focussing on the serialization format used in Ethereum: Recursive Length Prefix (RLP).

Please note that I will be using ruby and the ruby-rlp gem as a reference in the code examples although the encoding part should be the same regardless of language.

What is RLP?

RLP is the serialization format that Ethereum uses to serialize objects to raw bytes. It only encodes the structure of the data which it encodes it doesn’t know anything about what kind of object it was before you encoded it. This reduces the overall size of the encoding but does require the decoder of the bytes to know what kind of object it is looking for.

What is RLP used for?

RLP’s is most often used in Ethereum when sending data over the wire and when saving the state in a Patricia Tree

Encoding data to RLP

There are four different rules when encoding data to RLP. Let’s define them one by one starting with the simplest and ending up with the hardest one.

When encoding one byte of data and this byte is smaller or equal to then 128 (or 0x7f in hex) you can just return the byte as is.

For instance

1.9.3p286 :004 > 15.to_rlp
=> [15]
1.9.3p286 :004 > 127.to_rlp
=> [127]
1.9.3p286 :005 > 128.to_rlp
=> [129, 128]

In the last example above you can see that once you go over the initial keyspace of 127 bytes the encoding changes. The following rule should be checked when it’s not a single byte.

When encoding a string between 0 and 55 bytes long the RLP encoding consists of the length of the string + 128 (or 0x80) followed by the original bytes of the object you are trying to encode.

Let’s try to do this by hand first so we can see what’s happening.

Let’s take the string “dog”, as this is a common example in the original whitepaper. Let’s convert the string “dog” to a byte array.

1.9.3p286 :009 > "dog".bytes.to_a
 => [100, 111, 103]

It’s easy to see that this array is three bytes long and the first rule we defined doesn’t apply anymore. So instead let’s convert it to RLP by the rule we just defined.

The length of the array is three. So the length byte we need to prepend to our data is 128 + 3 = 131. Adding that prefix to our original byte array should thus be [131,100,111,103].

1.9.3p286 :010 > "dog".to_rlp
 => [131, 100, 111, 103]

Good, that seems to work. However what if we wanted to encode a very long string? Let’s use the string “This sentence is more than 55 bytes long, I know this because I prepared it in advance.” for example. We could encode this the same way as we did with our previous example but in order to save bytes in the keyspace there is a different rule as soon as you exceed 55 bytes in length.

When encoding a string over 55 bytes the RLP encoding of said string consists of the length of the length of the string + 183 (0xb7) followed by the length (in binary) followed by the string.

Try reading that a few times before you move on. So what does this mean? Let’s take our example again: “This sentence is more than 55 bytes long, I know this because I prepared it in advance.” This string 87 bytes long. Our length of 87 fits in one byte. So the initial byte for our RLP encoding is 183 + 1 = 184. Next we have the actual length of our string which is 87. So we expect the RLP encoding to be [184, 87, 84,104,….]. Let’s verify.

1.9.3p286 :019 > "This sentence is more than 55 bytes long, I know this
because I prepared it in advance.".to_rlp
 => [184, 87, 84, 104, 105, 115, 32, 115, 101, 110, 116, 101, 110, 99,
 101, 32, 105, 115, 32, 109, 111, 114, 101, 32, 116, 104, 101, 110, 32,
 53, 53, 32, 98, 121, 116, 101, 115, 32, 108, 111, 110, 103, 44, 32, 73,
 32, 107, 110, 111, 119, 32, 116, 104, 105, 115, 32, 98, 101, 99, 97,
 117, 115, 101, 32, 73, 32, 112, 114, 101, 112, 97, 114, 101, 100, 32,
 105, 116, 32, 105, 110, 32, 97, 100, 118, 97, 110, 99, 101, 46]

That seems to work as well.

Now we also want to add support for encoding array’s of data. Thankfully we have some space left in our keyspace. This brings us to the next rule:

When encoding an array and the total length of this array is between 0 and 55 bytes the RLP encoding consists of the length of the array + 192 (0xc0) followed by the RLP encoded bytes of the items in the array we are trying to encode.

Now you might notice this is actually a lot like the encoding of the string, the offset is just different. Let’s try to do this one.

Let’s assume we want to encode the following array in ruby to RLP.

["dog", "cat"]

This time things work a bit differently, because we actually need to start from the inside. We first need to encode the strings “dog” and “cat” to RLP before we know the total length of the array. We already know “dog” is [131, 100, 111, 103]. “cat” is [131, 99, 97, 116]. Adding these array’s together gives us [131, 100, 111, 103, 131, 99,97,116]. The only that that’s left is adding the length prefix. There are 8 items in our byte array so the length prefix is 192 + 8 = 200. The complete RLP encoded array should in turn be [200, 131, 100, 111, 103, 131, 99,97,116].

1.9.3p286 :031 > ["cat", "dog"].to_rlp
=> [200, 131, 99, 97, 116, 131, 100, 111, 103]

Now if we go over the 55 byte limit set by the previous rule the next rule should be used instead.

When encoding an array and the total length of this array is over 55 bytes the RLP encoding consists of the length of the length + 247 (0x7f) followed by the length (in binary) followed by the RLP encoded bytes of the items in the array you are trying to encode.

This again has a familiar parallel with encoding a string longer then 55 bytes. I will just give a quick example as the logic we defined before can be re-used here.

1.9.3p286 :036 > ["this is a very long list", "you never guess how long it is", "indeed,
how did you know it was this long", "good job, that I can tell you in
honestlyyyyy"].to_rlp
 => [248, 144, 152, 116, 104, 105, 115, 32, 105, 115, 32, 97, 32, 118,
 101, 114, 121, 32, 108, 111, 110, 103, 32, 108, 105, 115, 116, 158,
 121, 111, 117, 32, 110, 101, 118, 101, 114, 32, 103, 117, 101, 115,
 115, 32, 104, 111, 119, 32, 108, 111, 110, 103, 32, 105, 116, 32, 105,
 115, 169, 105, 110, 100, 101, 101, 100, 44, 32, 104, 111, 119, 32, 100,
 105, 100, 32, 121, 111, 117, 32, 107, 110, 111, 119, 32, 105, 116, 32,
 119, 97, 115, 32, 116, 104, 105, 115, 32, 108, 111, 110, 103, 173, 103,
 111, 111, 100, 32, 106, 111, 98, 44, 32, 116, 104, 97, 116, 32, 73, 32,
 99, 97, 110, 32, 116, 101, 108, 108, 32, 121, 111, 117, 32, 105, 110,
 32, 104, 111, 110, 101, 115, 116, 108, 121, 121, 121, 121, 121]

Decoding data from RLP

Now decoding is much more language specific. Some languages might have more or less primitives to decode to than others. I will only give a small example how the ruby library handles it but decoding is too platform specific otherwise.

Let’s try to reverse our RLP encoding of the “dog” string: [131, 100, 111, 103]. We know that the first byte always defines what kind of structure we should expect. Let’s first check if we need to except a single byte. We can do this by checking if 131 is smaller than 128. This is obviously not the case so we can’t use the first rule we defined for the encoding. Let’s check if perhaps our second rule matches. In order to encode a string up to 55 bytes long we need to take the length of said string and add 128. This means that if we take a byte and check if it’s smaller than 128 + 55 = 183 we know if the rule matches.

In this case our first byte is 131, which is smaller than 183 so we can use our second rule to deconstruct this byte array. The reverse of the second rule is simply removing the length prefix from the byte array, the resulting array is [100,111,103]. This byte array could mean a lot of things depending on what is encoded in it. We are going to assume though that we know we expect a string here and are going to convert this byte array to string. 100 = d, 111 = 0, 103 = g. Looks like it’s working!

1.9.3p286 :041 > RLP.decoder([131, 100, 111, 103]).as_string
 => "dog"

Closing tips

It’s good to note that Ethereum uses big endians for encoding integers. Encoding the integer 1024 would result to [130, 4,0] in RLP and 256 would be [130,1,0]. Please note that all leading zeroes are discarded. In example [0,130,1,0] becomes [130,1,0]

If you want more examples you read the the test suite from the ruby library.

In the next article I will try to explain more about Patricia Trees in Ethereum and their uses.