Modified Merkle Patricia Trie - Como o Ethereum salva um estado
Deixando de lado a parte da rede, poderíamos dizer que Ethereum é uma state machine onde as transações modificam os estados na rede Ethereum_. Um estado pode ser expresso como um par de valores-chave. Embora existam várias formas de representar um par de valores chave, a especificação _Ethereum define o Modified Merkle Patricia Trie (também conhecido como MPT) como o método para salvar estados.
Basicamente, o MPT é uma combinação de Patricia trie e Merkle tree, com poucas otimizações adicionais que se ajustam às características do Ethereum. Assim, uma compreensão do Patricia trie e da Merkle tree deve preceder a compreensão do MPT.
Patricia Trie
Patricia trie é uma estrutura de dados que também é chamada de árvore de prefixo, árvore de radix ou trie. A Trie utiliza uma chave como caminho para que os nós que partilham o mesmo prefixo possam também partilhar o mesmo caminho. Esta estrutura é mais rápida emencontrar prefixos comuns, de simples implementação, e que requerem pouca memória. Assim,ela é normalmente utilizada para implementar tabelas de roteamento, sistemas que são utilizados em máquinas de baixa especificação, como o router.
** Exemplo de Patricia Trie**
Merkle Tree
A Merkle Tree é uma árvore de hashes. Os nós das folhas armazenam dados. Os nós pais contém o hash dos seus filhos, bem como o valor do hash da soma dos hashes dos seus filhos. Uma vez que todos os nós, exceto os nós-folha, contém um hash, a árvore Merkle é também conhecida como uma árvore de hash.
Exemplo de Merkle Tree
Descobrir se dois nós diferentes têm os mesmos dados ou não, pode ser feito eficientemente com a Merkle trie. Primeiro você tem que comparar o valor do top _Hash dos dois nós. Se forem os mesmos, então os dois nós têm os mesmos dados. Por exemplo, se você olhar para a figura acima, onde existem quatro nós (L1, L2, L3, L4), você só precisa verificar se eles têm ou não o mesmo _Top Hash. Se o Top Hash for diferente e você quiser saber quais dados são diferentes, você deve comparar o Hash 0 com o Hash1 e verificar qual ramo é diferente. Ao fazer isso,você acabará descobrindo quais dados são diferentes.
Merkle Patricia Trie
No MPT, bem como na Merkle Tree, cada nó tem um valor de hash. O valor de hash de cada nó é decidido pelo valor de hash sha3 do seu conteúdo. Este hash é também utilizado como a chave que se refere ao nó. A Go-ethereum usa levelDB, e a parity usa rocksDB para armazenar estados. São armazenamentos de valor chave. As chaves e valores guardados na memória não são os valores chave do estado Ethereum. O valor que é armazenado na memória é o conteúdo do nó MPT, enquanto a chave é o hash deste nó.
Os valores chave do estado Ethereum são utilizados como caminhos no MPT. Nibble é a unidade utilizada para distinguir os valores chave no MPT, de modo que cada nó pode ter até 16 ramos. Adicionalmente, uma vez que um nó tem o seu próprio valor, um nó de um ramo é um conjunto de 17 itens, composto por 1 nó de valor e 16 ramos.
Um nó que não tem um nó filho é chamado de nó folha. Um nó de folha é composto por dois itens: o seu caminho e o seu valor. Por exemplo, digamos que a chave "0xBEA" contém 1000 e a chave "0xBEE" contém 2000. Então, deve haver um nó de ramo com o caminho "0xBE", e, sob esse nó, dois nós de folha com dois caminhos ("0xA" e "0xE") serão anexados.
No MPT, há mais um tipo de nó para além dos nós de ramo e dos nós foliares. Eles são os nós de extensão. Um nó de extensão é um nó optimizado do nó de ramificação. No estado Ethereum, com bastante frequência, existem nós de ramificação que têm apenas um nó filho. Esta é a razão pela qual o MPT compacta os nós de ramos que contêm apenas um filho em nós de extensão, que têm um caminho e o hash do filho.
Uma vez que tanto o nó folha como o nó de extensão são um conjunto de dois itens, deve haver uma forma de distinguir estes dois nós diferentes. A fim de fazer tal distinção, o MPT acrescenta um prefixo ao caminho. Se o nó é uma folha e o caminho consiste num número par de nibbles, você deve adicionar 0x20 como um prefixo. Se o caminho consistir num número ímpar de nibbles, você deve adicionar 0x3 como prefixo. Se o nó for um nó de extensão e o caminho consistir num número par de nibbles, você deve acrescentar 0x00 como prefixo. Se consistir num número ímpar de nibbles, você deve adicionar 0x1 como um prefixo. Como o caminho que consiste num número ímpar de nibbles recebe um nibble como prefixo, e o caminho que consiste num número par de nibbles recebe dois nibbles como prefixo, um caminho é sempre expresso como um byte.
Link para o texto original em koreano
Artigo escrito por seulgi kim e traduzido para o português por Rafael Ojeda
Latest comments (0)