Serialização de prefixo de comprimento recursivo (RLP)

A serialização de Prefixo de Comprimento Recursivo (RLP - Recursive Length Prefix) é amplamente usada nos clientes de execução do Ethereum. O RLP padroniza a transferência de dados entre nós em um formato eficiente em termos de espaço. O objetivo do RLP é codificar matrizes (arrays) de dados binários aninhados arbitrariamente, e o RLP é o principal método de codificação usado para serializar objetos na camada de execução do Ethereum. O principal objetivo do RLP é codificar a estrutura; com exceção de números inteiros positivos, o RLP delega a codificação de tipos de dados específicos (por exemplo, strings, floats) para protocolos de ordem superior. Inteiros positivos devem ser representados em formato binário big-endian sem zeros à esquerda (tornando assim o valor inteiro zero equivalente à matriz de bytes vazia). Inteiros positivos desserializados com zeros à esquerda devem ser tratados como inválidos por qualquer protocolo de ordem superior que use RLP.

Mais informações no yellow paper do Ethereum (Apêndice B) (opens in a new tab).

Para usar o RLP para codificar um dicionário, as duas formas canônicas sugeridas são:

usar [[k1,v1],[k2,v2]...] com chaves em ordem lexicográfica
usar a codificação de Árvore Patricia de nível superior, como o Ethereum faz

Definição

A função de codificação RLP recebe um item. Um item é definido da seguinte forma:

uma string (ou seja, matriz de bytes) é um item
uma lista de itens é um item
um número inteiro positivo é um item

Por exemplo, todos os seguintes são itens:

uma string vazia;
a string contendo a palavra "cat";
uma lista contendo qualquer número de strings;
e estruturas de dados mais complexas como ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].
o número 100

Observe que, no contexto do restante desta página, 'string' significa "um certo número de bytes de dados binários"; nenhuma codificação especial é usada e nenhum conhecimento sobre o conteúdo das strings está implícito (exceto conforme exigido pela regra contra inteiros positivos não mínimos).

A codificação RLP é definida da seguinte forma:

Para um número inteiro positivo, ele é convertido na matriz de bytes mais curta cuja interpretação big-endian é o número inteiro e, em seguida, codificado como uma string de acordo com as regras abaixo.
Para um único byte cujo valor está no intervalo [0x00, 0x7f] (decimal [0, 127]), esse byte é sua própria codificação RLP.
Caso contrário, se uma string tiver de 0 a 55 bytes de comprimento, a codificação RLP consistirá em um único byte com valor 0x80 (dec. 128) mais o comprimento da string seguido pela string. O intervalo do primeiro byte é, portanto, [0x80, 0xb7] (dec. [128, 183]).
Se uma string tiver mais de 55 bytes de comprimento, a codificação RLP consistirá em um único byte com valor 0xb7 (dec. 183) mais o comprimento em bytes do comprimento da string em formato binário, seguido pelo comprimento da string, seguido pela string. Por exemplo, uma string de 1024 bytes de comprimento seria codificada como \xb9\x04\x00 (dec. 185, 4, 0) seguida pela string. Aqui, 0xb9 (183 + 2 = 185) como o primeiro byte, seguido pelos 2 bytes 0x0400 (dec. 1024) que denotam o comprimento da string real. O intervalo do primeiro byte é, portanto, [0xb8, 0xbf] (dec. [184, 191]).
Se uma string tiver 2^64 bytes de comprimento ou mais, ela não poderá ser codificada.
Se a carga útil (payload) total de uma lista (ou seja, o comprimento combinado de todos os seus itens sendo codificados em RLP) tiver de 0 a 55 bytes de comprimento, a codificação RLP consistirá em um único byte com valor 0xc0 mais o comprimento da carga útil seguido pela concatenação das codificações RLP dos itens. O intervalo do primeiro byte é, portanto, [0xc0, 0xf7] (dec. [192, 247]).
Se a carga útil total de uma lista tiver mais de 55 bytes de comprimento, a codificação RLP consistirá em um único byte com valor 0xf7 mais o comprimento em bytes do comprimento da carga útil em formato binário, seguido pelo comprimento da carga útil, seguido pela concatenação das codificações RLP dos itens. O intervalo do primeiro byte é, portanto, [0xf8, 0xff] (dec. [248, 255]).

De forma sucinta:

Intervalo	Byte 1	Byte 2	...	Byte 9	Byte 10	Significado
`0x00-0x7f`	`0ppppppp`					string de byte único
`0x80-0xb7`	`10nnnnnn`	`pppppppp`	`...`			string curta (0-55 bytes)
`0xb8-0xbf`	`10111NNN`	`nnnnnnnn`	`...`	`nnnnnnnn`/`pppppppp`	`pppppppp`	string longa, N+1 bytes para o comprimento, depois a carga útil
`0xc0-0xf7`	`11nnnnnn`	`pppppppp`	`...`			lista curta (0-55 bytes)
`0xf8-0xff`	`11111NNN`	`nnnnnnnn`	`...`	`nnnnnnnn`/`pppppppp`	`pppppppp`	lista longa, N+1 bytes para o comprimento, depois a carga útil

p = carga útil (payload)
n = comprimento (número de bytes da carga útil)
N = deslocamento do comprimento do comprimento (seguem N+1 bytes de n)

Em código, isso é:

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        return encode_length(len(input), 0x80) + input
    elif isinstance(input, list):
        output = ''
        for item in input:
            output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L, offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    return to_binary(int(x / 256)) + chr(x % 256)

Exemplos

a string "dog" = [ 0x83, 'd', 'o', 'g' ]
a lista [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
a string vazia ('null') = [ 0x80 ]
a lista vazia = [ 0xc0 ]
o número inteiro 0 = [ 0x80 ]
o byte '\x00' = [ 0x00 ]
o byte '\x0f' = [ 0x0f ]
os bytes '\x04\x00' = [ 0x82, 0x04, 0x00 ]
a representação teórica de conjuntos (opens in a new tab) de três, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
a string "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

Decodificação RLP

De acordo com as regras e o processo de codificação RLP, a entrada da decodificação RLP é considerada uma matriz de dados binários. O processo de decodificação RLP é o seguinte:

de acordo com o primeiro byte (ou seja, prefixo) dos dados de entrada e decodificando o tipo de dados, o comprimento dos dados reais e o deslocamento (offset);
de acordo com o tipo e o deslocamento dos dados, decodificar os dados de forma correspondente, respeitando a regra de codificação mínima para números inteiros positivos;
continuar a decodificar o restante da entrada;

Entre eles, as regras de decodificação de tipos de dados e deslocamento são as seguintes:

os dados são uma string se o intervalo do primeiro byte (ou seja, prefixo) for [0x00, 0x7f], e a string for exatamente o próprio primeiro byte;
os dados são uma string se o intervalo do primeiro byte for [0x80, 0xb7], e a string cujo comprimento é igual ao primeiro byte menos 0x80 seguir o primeiro byte;
os dados são uma string se o intervalo do primeiro byte for [0xb8, 0xbf], e o comprimento da string cujo comprimento em bytes é igual ao primeiro byte menos 0xb7 seguir o primeiro byte, e a string seguir o comprimento da string;
os dados são uma lista se o intervalo do primeiro byte for [0xc0, 0xf7], e a concatenação das codificações RLP de todos os itens da lista cuja carga útil total é igual ao primeiro byte menos 0xc0 seguir o primeiro byte;
os dados são uma lista se o intervalo do primeiro byte for [0xf8, 0xff], e a carga útil total da lista cujo comprimento é igual ao primeiro byte menos 0xf7 seguir o primeiro byte, e a concatenação das codificações RLP de todos os itens da lista seguir a carga útil total da lista;