Dejando de lado la parte de la red, podríamos decir que Ethereum es una máquina de estados en la que las transacciones modifican estados en la red Ethereum. Un estado puede expresarse como un par clave-valor. Aunque hay varias formas de representar un par clave-valor, la especificación de Ethereum define el Trie Patricia Merkle modificado (también conocido como MPT) como el método para guardar estados.
Básicamente, el MPT es una combinación del trie Patricia y el árbol Merkle, con algunas optimizaciones adicionales que se ajustan a las características de Ethereum. Por lo tanto, una comprensión de la Patricia trie y el árbol de Merkle debe preceder a la comprensión de MPT.
Patricia trie es una estructura de datos que también se llama árbol Prefix, árbol radix o trie. Trie utiliza una clave como camino para que los nodos que comparten el mismo prefijo también puedan compartir el mismo camino. Esta estructura es la más rápida para encontrar prefijos comunes, es sencilla de implementar y requiere poca memoria. Por lo tanto, se utiliza comúnmente para la implementación de tablas de enrutamiento, sistemas que se utilizan en máquinas de baja especificación como el router.
Árbol de Merkle
El árbol de Merkle es un árbol de hashes. Los nodos hoja almacenan datos. Los nodos padre contienen el hash de sus hijos, así como el valor del hash de la suma de los hashes de sus hijos. Dado que todos los nodos, excepto los nodos hoja, contienen un hash, el árbol de Merkle también se conoce como árbol de hash.
Descubrir si dos nodos diferentes tienen los mismos datos o no puede hacerse eficientemente con el árbol de Merkle. Primero hay que comparar el valor Top Hash de los dos nodos. Si son iguales, entonces los dos nodos tienen los mismos datos. Por ejemplo, si mira la imagen anterior, cuando hay cuatro nodos (L1, L2, L3, L4), sólo tiene que comprobar si tienen el mismo Top Hash o no. Si el Top Hash es diferente y quiere saber qué datos son diferentes, debe comparar el Hash 0 con el Hash1 y comprobar qué rama es diferente. Haciendo esto, eventualmente encontrará qué datos son diferentes.
Merkle Patricia Trie
En el MPT, así como en el árbol de Merkle, cada nodo tiene un valor hash. El hash de cada nodo se decide por el valor hash sha3 de su contenido. Este hash también se utiliza como la clave que se refiere al nodo. Go-ethereum utiliza levelDB, y parity utiliza rocksDB para almacenar estados. Son almacenamientos de clave-valor. Las claves y los valores guardados en el almacenamiento no son los valores-clave del estado de Ethereum. El valor que se guarda en el almacenamiento es el contenido del nodo MPT mientras que la clave es el hash de este nodo.
Los valores-clave del estado de Ethereum se utilizan como rutas en el MPT. El nibble es la unidad utilizada para distinguir los valores clave en el MPT, por lo que cada nodo puede tener hasta 16 ramas. Además, como un nodo tiene su propio valor, un nodo rama es una matriz de 17 elementos compuesta por 1 valor de nodo y 16 ramas.
Un nodo que no tiene un nodo hijo se llama nodo hoja. Un nodo hoja se compone de dos elementos: su ruta y su valor. Por ejemplo, digamos que la clave «0xBEA» contiene 1000 y la clave «0xBEE» contiene 2000. Entonces, debería haber un nodo rama con la ruta «0xBE» y, bajo ese nodo, se adjuntarán dos nodos hoja con dos rutas («0xA» y «0xE»).
En el MPT, hay un tipo más de nodos aparte de los nodos rama y los nodos hoja. Son los nodos de extensión. Un nodo de extensión es un nodo optimizado del nodo rama. En el estado de Ethereum, con bastante frecuencia, hay nodos rama que sólo tienen un nodo hijo. Esta es la razón por la que el MPT comprime los nodos de rama que contienen sólo un hijo en nodos de extensión que tienen una ruta y el hash del hijo.
Dado que tanto el nodo hoja como el nodo de extensión son una matriz de dos elementos, debería haber una forma de distinguir estos dos nodos diferentes. Para hacer tal distinción, el MPT añade un prefijo a la ruta. Si el nodo es una hoja y la ruta consta de un número par de nibbles, se añade 0x20 como prefijo. Si la ruta consta de un número impar de nibbles, debe añadir 0x3 como prefijo. Si el nodo es un nodo de extensión y la ruta consta de un número par de nibbles, se añade 0x00 como prefijo. Si está formado por un número impar de nibbles, debe añadir 0x1 como prefijo. Como la ruta que consta de un número impar de nibbles recibe un nibble como prefijo y la ruta que consta de un número par de nibbles recibe dos nibbles como prefijo, una ruta siempre se expresa como un byte.
(Para la versión original en coreano, haga clic aquí)