Trie de Merkle Patricia

El estado de Ethereum (la totalidad de todas las cuentas, saldos y contratos inteligentes) se codifica en una versión especial de la estructura de datos conocida generalmente en informática como árbol de Merkle. Esta estructura es útil para muchas aplicaciones en criptografía porque crea una relación verificable entre todas las piezas individuales de datos entrelazadas en el árbol, lo que da como resultado un único valor raíz que se puede utilizar para demostrar cosas sobre los datos.

La estructura de datos de Ethereum es un "trie de Merkle Patricia modificado", llamado así porque toma prestadas algunas características de PATRICIA (el algoritmo práctico para recuperar información codificada en alfanumérico, por sus siglas en inglés) y porque está diseñado para la recuperación (retrieval) eficiente de datos de los elementos que componen el estado de Ethereum.

Un trie de Merkle Patricia es determinista y criptográficamente verificable: la única forma de generar una raíz de estado es calculándola a partir de cada pieza individual del estado, y se puede demostrar fácilmente que dos estados son idénticos comparando el hash raíz y los hashes que condujeron a él (una prueba de Merkle). Por el contrario, no hay forma de crear dos estados diferentes con el mismo hash raíz, y cualquier intento de modificar el estado con valores diferentes dará como resultado un hash raíz de estado diferente. Teóricamente, esta estructura proporciona el "santo grial" de la eficiencia O(log(n)) para inserciones, búsquedas y eliminaciones.

En un futuro próximo, Ethereum planea migrar a una estructura de árbol de Verkle, lo que abrirá muchas nuevas posibilidades para futuras mejoras del protocolo.

Requisitos previos

Para comprender mejor esta página, sería útil tener conocimientos básicos sobre hashes (opens in a new tab), árboles de Merkle (opens in a new tab), tries (opens in a new tab) y serialización (opens in a new tab). Este artículo comienza con una descripción de un árbol radix (opens in a new tab) básico y luego introduce gradualmente las modificaciones necesarias para la estructura de datos más optimizada de Ethereum.

Tries radix básicos

En un trie radix básico, cada nodo se ve de la siguiente manera:

[i_0, i_1 ... i_n, value]

Donde i_0 ... i_n representan los símbolos del alfabeto (a menudo binario o hexadecimal), value es el valor terminal en el nodo, y los valores en los slots i_0, i_1 ... i_n son NULL o punteros a (en nuestro caso, hashes de) otros nodos. Esto forma un almacén básico de (key, value).

Supongamos que desea utilizar una estructura de datos de árbol radix para persistir un orden sobre un conjunto de pares clave-valor. Para encontrar el valor actualmente asignado a la clave dog en el trie, primero convertiría dog en letras del alfabeto (dando 64 6f 67), y luego descendería por el trie siguiendo ese camino hasta encontrar el valor. Es decir, comienza buscando el hash raíz en una base de datos plana de clave/valor para encontrar el nodo raíz del trie. Se representa como una matriz de claves que apuntan a otros nodos. Usaría el valor en el índice 6 como clave y lo buscaría en la base de datos plana de clave/valor para obtener el nodo un nivel más abajo. Luego elegiría el índice 4 para buscar el siguiente valor, luego elegiría el índice 6, y así sucesivamente, hasta que, una vez que haya seguido la ruta: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, buscaría el valor del nodo y devolvería el resultado.

Hay una diferencia entre buscar algo en el "trie" y en la "base de datos" plana subyacente de clave/valor. Ambos definen disposiciones de clave/valor, pero la base de datos subyacente puede realizar una búsqueda tradicional de 1 paso de una clave. Buscar una clave en el trie requiere múltiples búsquedas en la base de datos subyacente para llegar al valor final descrito anteriormente. Refirámonos a esto último como un path para eliminar la ambigüedad.

Las operaciones de actualización y eliminación para los tries radix se pueden definir de la siguiente manera:

    def update(node_hash, path, value):
        curnode = db.get(node_hash) if node_hash else [NULL] * 17
        newnode = curnode.copy()
        if path == "":
            newnode[-1] = value
        else:
            newindex = update(curnode[path[0]], path[1:], value)
            newnode[path[0]] = newindex
        db.put(hash(newnode), newnode)
        return hash(newnode)

    def delete(node_hash, path):
        if node_hash is NULL:
            return NULL
        else:
            curnode = db.get(node_hash)
            newnode = curnode.copy()
            if path == "":
                newnode[-1] = NULL
            else:
                newindex = delete(curnode[path[0]], path[1:])
                newnode[path[0]] = newindex

            if all(x is NULL for x in newnode):
                return NULL
            else:
                db.put(hash(newnode), newnode)
                return hash(newnode)

Un árbol radix "Merkle" se construye vinculando nodos mediante resúmenes de hash criptográficos generados de forma determinista. Este direccionamiento por contenido (en la base de datos de clave/valor key == keccak256(rlp(value))) proporciona una garantía de integridad criptográfica de los datos almacenados. Si el hash raíz de un trie dado es de conocimiento público, entonces cualquiera con acceso a los datos de la hoja subyacente puede construir una prueba de que el trie incluye un valor dado en una ruta específica proporcionando los hashes de cada nodo que une un valor específico a la raíz del árbol.

Es imposible que un atacante proporcione una prueba de un par (path, value) que no existe, ya que el hash raíz se basa en última instancia en todos los hashes que se encuentran debajo de él. Cualquier modificación subyacente cambiaría el hash raíz. Puede pensar en el hash como una representación comprimida de información estructural sobre los datos, asegurada por la protección de preimagen de la función de hashing.

Nos referiremos a una unidad atómica de un árbol radix (por ejemplo, un solo carácter hexadecimal o un número binario de 4 bits) como un "nibble". Al recorrer una ruta un nibble a la vez, como se describió anteriormente, los nodos pueden referirse como máximo a 16 hijos, pero incluyen un elemento value. Por lo tanto, los representamos como una matriz de longitud 17. Llamamos a estas matrices de 17 elementos "nodos de rama".

Trie de Merkle Patricia

Los tries radix tienen una limitación importante: son ineficientes. Si desea almacenar un enlace (path, value) donde la ruta, como en Ethereum, tiene 64 caracteres de longitud (el número de nibbles en bytes32), necesitaremos más de un kilobyte de espacio adicional para almacenar un nivel por carácter, y cada búsqueda o eliminación tomará los 64 pasos completos. El trie de Patricia que se presenta a continuación resuelve este problema.

Optimización

Un nodo en un trie de Merkle Patricia es uno de los siguientes:

1. NULL (representado como la cadena vacía)
2. branch Un nodo de 17 elementos [ v0 ... v15, vt ]
3. leaf Un nodo de 2 elementos [ encodedPath, value ]
4. extension Un nodo de 2 elementos [ encodedPath, key ]

Con rutas de 64 caracteres, es inevitable que después de recorrer las primeras capas del trie, llegue a un nodo donde no exista una ruta divergente durante al menos parte del camino hacia abajo. Para evitar tener que crear hasta 15 nodos NULL dispersos a lo largo de la ruta, acortamos el descenso configurando un nodo extension de la forma [ encodedPath, key ], donde encodedPath contiene la "ruta parcial" para saltar hacia adelante (usando una codificación compacta que se describe a continuación), y la key es para la siguiente búsqueda en la base de datos.

Para un nodo leaf, que puede estar marcado por una bandera en el primer nibble de la encodedPath, la ruta codifica todos los fragmentos de ruta del nodo anterior y podemos buscar el value directamente.

Sin embargo, esta optimización anterior introduce ambigüedad.

Al recorrer rutas en nibbles, podemos terminar con un número impar de nibbles para recorrer, pero debido a que todos los datos se almacenan en formato bytes. No es posible diferenciar entre, por ejemplo, el nibble 1 y los nibbles 01 (ambos deben almacenarse como <01>). Para especificar una longitud impar, la ruta parcial tiene como prefijo una bandera.

Especificación: Codificación compacta de secuencia hexadecimal con terminador opcional

La señalización tanto de la longitud de la ruta parcial restante impar frente a par como del nodo hoja frente a extensión como se describió anteriormente reside en el primer nibble de la ruta parcial de cualquier nodo de 2 elementos. Dan como resultado lo siguiente:

Para una longitud de ruta restante par (0 o 2), siempre seguirá otro nibble de "relleno" 0.

    def compact_encode(hexarray):
        term = 1 if hexarray[-1] == 16 else 0
        if term:
            hexarray = hexarray[:-1]
        oddlen = len(hexarray) % 2
        flags = 2 * term + oddlen
        if oddlen:
            hexarray = [flags] + hexarray
        else:
            hexarray = [flags] + [0] + hexarray
        # hexarray ahora tiene una longitud par cuyo primer nibble son las banderas.
        o = ""
        for i in range(0, len(hexarray), 2):
            o += chr(16 * hexarray[i] + hexarray[i + 1])
        return o

Ejemplos:

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

Aquí está el código extendido para obtener un nodo en el trie de Merkle Patricia:

    def get_helper(node_hash, path):
        if path == []:
            return node_hash
        if node_hash == "":
            return ""
        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
        if len(curnode) == 2:
            (k2, v2) = curnode
            k2 = compact_decode(k2)
            if k2 == path[: len(k2)]:
                return get(v2, path[len(k2) :])
            else:
                return ""
        elif len(curnode) == 17:
            return get_helper(curnode[path[0]], path[1:])

    def get(node_hash, path):
        path2 = []
        for i in range(len(path)):
            path2.push(int(ord(path[i]) / 16))
            path2.push(ord(path[i]) % 16)
        path2.push(16)
        return get_helper(node_hash, path2)

Ejemplo de trie

Supongamos que queremos un trie que contenga cuatro pares de ruta/valor ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Primero, convertimos tanto las rutas como los valores a bytes. A continuación, las representaciones de bytes reales para las rutas se denotan por <>, aunque los valores todavía se muestran como cadenas, denotadas por '', para una comprensión más fácil (ellos también serían en realidad bytes):

<64 6f> : 'verb'
    <64 6f 67> : 'puppy'
    <64 6f 67 65> : 'coins'
    <68 6f 72 73 65> : 'stallion'

Ahora, construimos dicho trie con los siguientes pares clave/valor en la base de datos subyacente:

rootHash: [ <16>, hashA ]
    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
    hashB:    [ <00 6f>, hashC ]
    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Cuando se hace referencia a un nodo dentro de otro nodo, lo que se incluye es keccak256(rlp.encode(node)), si len(rlp.encode(node)) >= 32 de lo contrario node donde rlp.encode es la función de codificación RLP.

Tenga en cuenta que al actualizar un trie, es necesario almacenar el par clave/valor (keccak256(x), x) en una tabla de búsqueda persistente si el nodo recién creado tiene una longitud >= 32. Sin embargo, si el nodo es más corto que eso, no es necesario almacenar nada, ya que la función f(x) = x es reversible.

Tries en Ethereum

Todos los tries de Merkle en la capa de ejecución de Ethereum utilizan un trie de Merkle Patricia.

Desde un encabezado del bloque hay 3 raíces de 3 de estos tries.

1. stateRoot
2. transactionsRoot
3. receiptsRoot

Trie de estado

Hay un trie de estado global, y se actualiza cada vez que un cliente procesa un bloque. En él, un path es siempre: keccak256(ethereumAddress) y un value es siempre: rlp(ethereumAccount). Más específicamente, una account de Ethereum es una matriz de 4 elementos de [nonce,balance,storageRoot,codeHash]. En este punto, vale la pena señalar que este storageRoot es la raíz de otro trie de Patricia:

Trie de almacenamiento

El trie de almacenamiento es donde residen todos los datos del contrato. Hay un trie de almacenamiento separado para cada cuenta. Para recuperar valores en posiciones de almacenamiento específicas en una dirección dada, se requieren la dirección de almacenamiento, la posición entera de los datos almacenados en el almacenamiento y el ID del bloque. Estos luego se pueden pasar como argumentos al eth_getStorageAt definido en la API JSON-RPC, por ejemplo, para recuperar los datos en el slot de almacenamiento 0 para la dirección 0x295a70b2de5e3953354a6a8344e616ed314d7251:

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

{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

Recuperar otros elementos en el almacenamiento es un poco más complejo porque primero se debe calcular la posición en el trie de almacenamiento. La posición se calcula como el hash keccak256 de la dirección y la posición de almacenamiento, ambos rellenados a la izquierda con ceros hasta una longitud de 32 bytes. Por ejemplo, la posición para los datos en el slot de almacenamiento 1 para la dirección 0x391694e7e0b0cce554cb130d723a9d27458f9298 es:

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

En una consola de Geth, esto se puede calcular de la siguiente manera:

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

El path es por lo tanto keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Esto ahora se puede usar para recuperar los datos del trie de almacenamiento como antes:

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

{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Nota: El storageRoot para una cuenta de Ethereum está vacío por defecto si no es una cuenta de contrato.

Trie de transacciones

Hay un trie de transacciones separado para cada bloque, que nuevamente almacena pares (key, value). Una ruta aquí es: rlp(transactionIndex) que representa la clave que corresponde a un valor determinado por:

if legacyTx:
  value = rlp(tx)
else:
  value = TxType | encode(tx)

Puede encontrar más información sobre esto en la documentación de EIP-2718 (opens in a new tab).

Trie de recibos

Cada bloque tiene su propio trie de recibos. Un path aquí es: rlp(transactionIndex). transactionIndex es su índice dentro del bloque en el que se incluyó. El trie de recibos nunca se actualiza. Al igual que el trie de transacciones, hay recibos actuales y heredados. Para consultar un recibo específico en el trie de recibos, se requieren el índice de la transacción en su bloque, la carga útil del recibo y el tipo de transacción. El recibo devuelto puede ser de tipo Receipt que se define como la concatenación de TransactionType y ReceiptPayload o puede ser de tipo LegacyReceipt que se define como rlp([status, cumulativeGasUsed, logsBloom, logs]).

Puede encontrar más información sobre esto en la documentación de EIP-2718 (opens in a new tab).

Más información

• Trie de Merkle Patricia modificado: cómo Ethereum guarda un estado (opens in a new tab)
• Merkling en Ethereum (opens in a new tab)
• Comprendiendo el trie de Ethereum (opens in a new tab)