>
>
>
>
>>
Deixando de lado a parte da rede, poderíamos dizer que Ethereum é uma máquina de estados 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 maneiras de representar um par de valores chave, a especificação Ethereum define o Merkle modificado Patricia Trie (também conhecido como MPT) como o método para salvar estados.
Basicamente, MPT é uma combinação de Patricia trie e Merkle tree, com poucas otimizações adicionais que se encaixam nas características do Ethereum. Assim, uma compreensão da Patricia trie e Merkle tree deve preceder a compreensão do MPT.
Patricia trie é uma estrutura de dados que também é chamada Prefix tree, radix tree ou trie. Trie usa uma chave como caminho para que os nós que compartilham o mesmo prefixo também possam compartilhar o mesmo caminho. Esta estrutura é mais rápida em encontrar prefixos comuns, simples de implementar, e requer pouca memória. Assim, ela é comumente usada para implementar tabelas de roteamento, sistemas que são usados em máquinas de baixa especificação como o roteador.
>
Merkle Tree
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. Como todos os nós exceto os nós foliares contêm um hash, a árvore Merkle é também conhecida como árvore de hash.
>>
Descobrir se dois nós diferentes têm ou não os mesmos dados pode ser feito eficientemente com a árvore Merkle. Primeiro você tem que comparar o valor do Top Hash dos dois nós. Se eles forem os mesmos, então os dois nós têm os mesmos dados. Por exemplo, se você olhar para a figura acima, quando há quatro nós (L1, L2, L3, L4), você só precisa verificar se eles têm o mesmo Top Hash ou não. Se o Top Hash for diferente e você quiser saber quais dados são diferentes, você deve comparar Hash 0 com Hash1 e verificar qual ramo é diferente. Ao fazer isso, você eventualmente vai descobrir quais dados são diferentes.
Merkle Patricia Trie
No MPT, assim como na árvore Merkle, 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 é usado como a chave que se refere ao nó. Go-ethereum usa levelDB, e parity usa rocksDB para armazenar estados. Eles são armazenamentos de valor chave. As chaves e valores salvos no armazenamento não são os valores chave do estado Ethereum. O valor que é armazenado no armazenamento é o conteúdo do nó MPT enquanto a chave é o hash deste nó.
Valores chave do estado Ethereum são usados como caminhos no MPT. Nibble é a unidade usada para distinguir os valores chave no MPT, assim cada nó pode ter até 16 ramos. Além disso, como um nó tem seu próprio valor, um nó de ramo é um conjunto de 17 itens composto de 1 valor de nó e 16 ramos.
Um nó que não tem um nó filho é chamado de nó de folha. Um nó de folha é composto de dois itens: seu caminho e 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ó ramo com o caminho “0xBE” e, sob esse nó, dois nós folha com dois caminhos (“0xA” e “0xE”) serão anexados.
>
>
No MPT, há mais um tipo de nó além dos nós ramo e os nós folha. Eles são nós de extensão. Um nó de extensão é um nó otimizado do nó de ramificação. No estado Ethereum, com bastante freqüência, há nós de ramificação que têm apenas um nó filho. Esta é a razão pela qual o MPT comprime 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.
Desde que tanto o nó folha quanto o nó de extensão são um conjunto de dois itens, deve haver uma maneira de distinguir estes dois nós diferentes. Para fazer tal distinção, o MPT adiciona um prefixo ao caminho. Se o nó é uma folha e o caminho consiste em um número par de mordidelas, você adiciona 0x20 como um prefixo. Se o caminho consistir de um número ímpar de mordidelas, você deve adicionar 0x3 como um prefixo. Se o nó for um nó de extensão e o caminho consistir em um número par de mordidelas, você adiciona 0x00 como um prefixo. Se o caminho consistir em um número ímpar de mordidelas, você deve adicionar 0x1 como prefixo. Como o caminho que consiste num número ímpar de mordidelas recebe uma mordidela como prefixo e o caminho que consiste num número par de mordidelas recebe duas mordidelas como prefixo, um caminho é sempre expresso como um byte.
(Para a versão original coreana, clique aqui)