Árvore Merkle Patricia

Uma árvore Merkle Patricia fornece uma estrutura de dados criptograficamente autenticada que pode ser usada para armazenar todas as ligações (key, value).

A Merkle Patricia Tries é totalmente determinística, significando que Tries - testes - com a mesma ligação (key, value) são com certeza idênticas - até o último byte. Isto significa que elas têm o mesmo hash raiz, fornecendo a máxima eficiência o(log(n)) para inserções, buscas e exclusões. Além disso, elas são mais simples de entender e codificar do que alternativas mais complexas baseadas em comparação, como as árvores vermelho-pretas.

Pré-requisitos

Para entender melhor esta página, seria útil ter conhecimento básico sobre hashes(opens in a new tab), Árvores Merkle(opens in a new tab), árvores(opens in a new tab) e serialização(opens in a new tab).

Árvores radix básicas

Em uma árvore radix básica, cada nó se parece com o seguinte:

1    [i_0, i_1 ... i_n, value]

Onde i0 ... in representa o símbolo do alfabeto (muitas vezes binário ou hex), value é o valor terminal no nó, e os valores nos slots i0 . . in são ou NULL ou ponteiros para (em nosso caso, hashes de) outros nós. Isto forma um armazenamento básico (key, value).

Digamos que você queria usar uma estrutura de dados da árvore radix para persistir em uma ordem em um conjunto de pares de valor-chave. Para encontrar o valor atualmente relacionado com a chave dog na árvore, primeiro você converteria dog em letras do alfabeto (dando 64 6f 67), e então desceria pela árvore seguindo o caminho até encontrar o valor. Ou seja, você começa por procurar o hash raiz em uma base de dados texto chave/valor para encontrar o nó raiz da árvore. Ele é representado como uma matriz de chaves apontando para outros nós. Use o valor no índice 6 como uma chave e procure na base chave/valor para obter o nó um nível abaixo. Em seguida, escolha o índice 4 para procurar o próximo valor, depois escolha o índice 6 e assim por diante. Uma vez tendo seguido o caminho: root-> 6 -> 4 -> 6 -> 15 -> 6 -> 7, procure o valor do nó e retorne o resultado.

Há uma diferença entre buscar algo na árvore e no banco de dados base subjacente (chave/valor). Ambos definem arranjos chave/valor, mas o DB subjacente pode fazer uma tradicional busca de 1 passo pela chave. Procurar uma chave na árvore requer várias buscas no banco de dados subjacente para obter o valor final descrito acima. Vamos nos referir a este último como um path para eliminar ambiguidade.

As operações de atualização e exclusão em árvores radix são simples, e podem ser definidas da seguinte forma:

1    def update(node,path,value):
2        if path == '':
3            curnode = db.get(node) if node else [ NULL ] * 17
4            newnode = curnode.copy()
5            newnode[-1] = value
6        else:
7            curnode = db.get(node) if node else [ NULL ] * 17
8            newnode = curnode.copy()
9            newindex = update(curnode[path[0]],path[1:],value)
10            newnode[path[0]] = newindex
11        db.put(hash(newnode),newnode)
12        return hash(newnode)
13
14    def delete(node,path):
15        if node is NULL:
16            return NULL
17        else:
18            curnode = db.get(node)
19            newnode = curnode.copy()
20            if path == '':
21                newnode[-1] = NULL
22            else:
23                newindex = delete(curnode[path[0]],path[1:])
24                newnode[path[0]] = newindex
25
26            if all(x is NULL for x in newnode):
27                return NULL
28            else:
29                db.put(hash(newnode),newnode)
30                return hash(newnode)
Exibir tudo

Uma árvore Radix "Merkle" é construída ligando os nós usando digests de hash criptográficos gerados deterministicamente. Este endereçamento de conteúdo (no BD chave/valor key == keccak256(rlp(value))) fornece uma integridade criptográfica garantida do dado armazenado. Se o hash raiz de um Trie - teste - determinado for conhecido publicamente, então, qualquer um com acesso aos dados da folha subjacente poderá fornecer uma prova de que o Trie - teste - inclui um determinado valor em um caminho específico, fornecendo os hashes de cada nódulo que se junta a um valor específico para a raiz da árvore.

É impossível para um atacante fornecer uma prova de um par (path, value) que não exista, já que o hash raiz é, em última análise, baseado em todos os hashes abaixo dele. Qualquer modificação subjacente alteraria o hash raiz. Você pode pensar no hash como uma representação comprimida de informações estruturais sobre os dados, seguros pela proteção pré-imagem da função de hash.

Vamos nos referir a uma unidade atômica de uma árvore de radix (por exemplo, um único caractere hexadecimal, ou número binário de 4 bits) como um "nibble". Ao percorrerem um caminho um nibble de cada vez, conforme descrito acima, os nós podem fazer referência a 16 filhos, no máximo, mas incluir um elemento value. Portanto, nós os representamos como uma faixa de comprimento 17. Chamamos esses arrays de 17 elementos de "branch nodes".

Árvore Merkle Patricia

As árvores radix têm uma grande limitação: são ineficientes. Se você quiser armazenar uma vinculação (path, value) em que o caminho tem, como no Ethereum, 64 caracteres de comprimento (o número de nibbles em bytes32), você vai precisar de mais de um kilobyte de espaço extra para armazenar um nível por caractere, e cada busca ou exclusão precisará das 64 etapas completas. A árvore Patricia apresentada aqui resolve esta questão.

Otimização

Um nó em uma árvore Merkle Patricia é um dos seguintes:

1. NULL (representado como a string vazia)
2. branch Um nó de 17 itens [ v0 ... v15, vt ]
3. leaf Um nó de 2 itens [ encodedPath, value ]
4. extension Um nó de 2 itens [ encodedPath, key ]

Com caminhos de 64 caracteres, é inevitável que depois de atravessar as primeiras poucas camadas da árvore, você alcançe um nó em que não existe caminho divergente para pelo menos parte do caminho para baixo. Para evitar ter que criar até 15 nós esparsos NULL ao longo do caminho, encurtamos a descida configurando um nó de extension do formulário [ encodedPath, key ], em que encodedPath contém o "caminho parcial" a ignorar (usando uma codificação compacta descrita abaixo), e a key é para a próxima pesquisa no banco de dados.

Para um nó de leaf, que pode ser marcado por um flag na primeira nibble do encodedPath, o caminho codifica todos os fragmentos de caminho do nó anterior e podemos procurar o value diretamente.

Esta otimização acima, porém, introduz ambiguidade.

Quando atravessamos caminhos em nibbles, podemos acabar com um número ímpar de nibbles para percorrer, mas porque todos os dados são armazenados no formato bytes. Não é possível diferenciar entre, por exemplo, o nibble 1 e os nibbles01 (ambos devem ser armazenados como <01>). Para especificar comprimento ímpar, o caminho parcial é precedido com um flag.

Especificação: Codificação compacta de sequência hexadecimal com terminador opcional

A sinalização de largura restante do caminho parcial, par ou ímpar, e de nó leaf vs nó de extensão conforme descrito acima reside no primeiro nibble do caminho parcial de qualquer nó de 2 elementos. Eles resultam no seguinte:

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

Para um comprimento restante de caminho par (0 ou 2), sempre seguirá um outro nibble "padding" 0.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
Exibir tudo

Exemplos:

1    > [ 1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [ 0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [ 0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [ f, 1, c, b, 8, 10]
8    '3f 1c b8'

Aqui está o código estendido para obter um nó na árvore Merkle Patricia:

1    def get_helper(node,path):
2        if path == []: return node
3        if node = '': return ''
4        curnode = rlp.decode(node if len(node) < 32 else db.get(node))
5        if len(curnode) == 2:
6            (k2, v2) = curnode
7            k2 = compact_decode(k2)
8            if k2 == path[:len(k2)]:
9                return get(v2, path[len(k2):])
10            else:
11                return ''
12        elif len(curnode) == 17:
13            return get_helper(curnode[path[0]],path[1:])
14
15    def get(node,path):
16        path2 = []
17        for i in range(len(path)):
18            path2.push(int(ord(path[i]) / 16))
19            path2.push(ord(path[i]) % 16)
20        path2.push(16)
21        return get_helper(node,path2)
Exibir tudo

Árvore de exemplo

Suponha que nós queremos uma árvore contendo quatro pares de caminho/valor ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

Primeiro, convertemos ambos caminhos e valores para bytes. Abaixo, representações reais em bytes para caminhos são indicadas por <>, embora valores ainda sejam mostrados como strings, denotado por '', para melhor compreensão (eles, também, seriam bytes):

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coin'
4    <68 6f 72 73 65> : 'stallion'

Agora, construímos uma árvore com os seguintes pares chave/valor no banco de dados subjacente:

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Quando um nó é referenciado dentro de outro nó, o que é incluído é H(rlp. ncode(x)), onde H(x) = keccak256(x) if len(x) >= 32 else x e rlp. ncode é a função de codificação RLP.

Observe que, ao atualizar uma árvore, é necessário armazenar o par chave/valor (keccak256(x), x) em uma tabela de pesquisa persistente se o nó recém-criado tem comprimento >= 32. Entretanto, se o nó é menor do que isso, não é preciso armazenar nada, já que a função f(x) = x é reversível.

Árvores no Ethereum

Todas as árvores Merkle na camada de execução do Ethereum usam uma árvore Merkle Patricia.

Do cabeçalho do bloco há 3 raízes dessas 3 árvores.

1. stateRoot
2. transactionsRoot
3. receiptsRoot

Árvore de estado

Existe um estado global da árvore que é atualizado toda vez que um cliente processa um bloco. Nela, um path é sempre: keccak256(ethereumAddress) e um value é sempre: rlp(ethereumAccount). Mais especificamente uma conta Ethereum é uma array de 4 itens [nonce,balance,storageRoot,codeHash]. Neste ponto, vale a pena notar que este storageRoot é a raiz de outra árvore Patricia:

Árvore de armazenamento

Árvore de armazenamento é onde todos os dados de contrato se encontram. Há uma árvore de armazenamento separada para cada conta. Para recuperar valores em posições específicas de armazenamento em um determinado endereço, o endereço de armazenamento, posição inteira dos dados armazenados no armazenamento, e a ID do bloco, são necessárias. Eles podem então ser passados como argumentos para eth_getStorageAt definido na API JSON-RPC, por exemplo, para recuperar os dados no slot de armazenamento 0 para o endereço 0x295a70b2de5e3953354a6a8344e616ed314d7251:

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}
4

Recuperar outros elementos no armazenamento é um pouco mais complicado, porque a posição na árvore de armazenamento deve ser calculada primeiro. A posição é calculada como o hash keccak256 do endereço e da posição de armazenamento, ambos alinhados à esquerda com zeros para um comprimento de 32 bytes. Por exemplo, a posição para os dados no slot 1 de armazenamento para o endereço 0x391694e7e0b0cce554cb130d723a9d27458f9298 é:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

Em um console Geth, isso pode ser calculado da seguinte forma:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

O path é, portanto, keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Isso agora pode ser usado para recuperar os dados da árvore de armazenamento como antes:

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Nota: O storageRoot para uma conta Ethereum está vazio pelo padrão se ele não for uma conta de contrato.

Árvore de transações

Há uma árvore de transações separada para cada bloco, armazenando novamente pares (key, value). Um caminho aqui é: rlp(transactionIndex) que representa a chave que corresponde a um valor determinado por:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

Mais informações sobre isso podem ser encontradas na documentação do EIP 2718(opens in a new tab).

Árvore de recibos

Cada bloco tem sua própria árvore de recibos. Um path aqui é: rlp(transactionIndex). transactionIndex é seu índice dentro do bloco que é minerado. A árvore de recibos nunca é atualizada. De maneira similar à árvore de Transações, existem recibos atuais e legados. Para consultar um recibo específico na árvore de Recibos, o índice da transação em seu bloco, o payload do recibo e o tipo de transação são necessários. O recibo retornado pode ser do tipo Receipt, que é definido como a concentração de TransactionType e ReceiptPayload, ou pode ser do tipo LegacyReceipt, que é definido como rlp([status, acumulativoGasUsed, logsBloom, logs]).

Mais informações sobre isso podem ser encontradas na documentação do EIP 2718(opens in a new tab).

Leitura Adicional

• Árvore Merkle Patricia modificada: como o Ethereum salva um estado(opens in a new tab)
• Fazendo Merkle no Ethereum(opens in a new tab)
• Entendendo a árvore Ethereum(opens in a new tab)