Estructura de Datos Trie en Ethereum: Funciones y Aplicaciones
Clase 8 de 28 • Ethereum Developer Program 1ª Edición
Contenido del curso
Ethereum a menudo se denomina "máquina de estado" y utiliza un almacenamiento de datos original para registrar estados (cuentas) y transacciones. Ethereum utiliza una estructura de datos conocida como “trie” como base principal de su base de datos. Es importante conocer comprenderla para profundizar tu conocimiento sobre Ethereum.
Qué es un trie
Es una estructura de datos que es más rápida para encontrar prefijos comunes, fácil de implementar y requiere poca memoria. Como Ethereum usa Merkle Tree para almacenar eficientemente el hash en bloques, trie se usa como una estructura de datos central de almacenamiento de datos.
Ethereum utiliza "Modified Merkel Patricia Trie", que se inventó con Merkle Tree, Patricia Tree (Trie) y algunas mejoras. "Modified Merkel Patricia Trie" se utiliza como la estructura de datos principal en los 4 tipos que implementa Ethereum:
- “world state trie”
- “account storage trie”
- “transaction trie”.
- “transaction receipt trie”
El diagrama de arriba muestra la estructura de un Merkel Patricia Trie. Se compone principalmente de tres tipos de nodos: nodo de extensión, nodo de rama y nodo de hoja. Cada nodo se decide por el valor hash sha3 de su contenido y el hash se utiliza como clave.
Arquitectura del trie de estado de Ethereum
Como se mencionó anteriormente, el trie de estado tiene cuatro tipos. Cada tipo se construye con un Merkle Patricia Trie y solo el nodo raíz (nodo superior del trie de estado) se almacena en bloque para almacenar de repuesto. Puede ver toda la arquitectura en el siguiente diagrama.
Puedes ver que solo se almacenan en el bloque tres tries de estado principales: world state trie, transaction trie y tries receipt trie. Y, account storage trie (trie de contenido de almacenamiento de cuenta) construye un nodo de hoja en world state trie.
World state
El world state es un mapeo entre direcciones (cuentas) y estados de cuenta.
El world state no se almacena en la cadena de bloques, pero el yellow paper establece que se espera que las implementaciones almacenen estos datos en un trie (también conocido state trie). El world state puede verse como el estado global que se actualiza constantemente mediante la ejecución de transacciones.
Toda la información sobre las cuentas de Ethereum vive en el world state y se almacena en el world state trie. Si deseas conocer el saldo de una cuenta o el estado actual de un contrato inteligente, consulta el world state para recuperar el estado de esa cuenta.
Account storage
Account storage trie es donde se almacenan los datos asociados con una cuenta. Esto solo es relevante para cuentas de contrato y todos los datos del contrato inteligente se conservan en el Account storage trie como una asignación entre enteros de 32 bytes.
En Ethereum existe 2 tipos de cuentas:
- Cuentas de propiedad externa (EOA): es una cuenta que tienen los usuarios regulares, que pueden usar para enviarse Ether entre sí e implementar contratos inteligentes.
- Cuentas de contrato: es una cuenta que se crea cuando se implementa un contrato inteligente. Cada contrato inteligente tiene su propia cuenta Ethereum.
Cada cuenta tiene un estado -account state- que contiene información sobre la cuenta de Ethereum. Por ejemplo, almacena cuánto Ether tiene y la cantidad de transacciones enviadas por la cuenta. El account state o estado de la cuenta tiene 4 campos.
- nonce: número de transacciones enviadas desde esta dirección (si se trata de una cuenta de propiedad externa - EOA) o el número de creaciones de contratos realizadas por esta cuenta.
- balance: ether total (en wei) propiedad de esta cuenta.
- storageRoot: hash del nodo raíz del account storage trie
- codeHash: para cuentas de contrato, el hash del código EVM de esta cuenta. Para EOA, esto estará vacío.
Transaction trie
El transaction trie registra transacciones en Ethereum. La transacción juega un papel central para cambiar los estados, ya que Ethereum es una máquina de "estado" basada en transacciones. Una vez que la transacción se registra en un bloque, no se puede cambiar de forma permanente para probar el saldo de cuentas (world state trie).
Las transacciones son las que hacen que el estado cambie del estado actual al estado siguiente. En Ethereum, existen tres tipos de transacciones:
- Transacciones que transfieren valor entre dos EOA (p. ej., cambiar los saldos de las cuentas del remitente y el destinatario).
- Transacciones que envían una llamada a un contrato (por ejemplo, establecer un valor en el contrato inteligente mediante el envío de una llamada que ejecuta un método para establecer un valor).
- Transacciones que implementan un contrato (por lo tanto, cree una cuenta, la cuenta del contrato).
Los campos de una transacción son:
- nonce: número de transacciones enviadas por la cuenta que creó la transacción.
- gasPrice: valor (en wei) que se pagará por unidad de gas por los costos de cómputo de ejecutar esta transacción.
- gasLimit: cantidad máxima de gas que se utilizará al ejecutar esta transacción.
- to:
- Si esta transacción transfiere ether, la dirección de la cuenta EOA que recibirá una transferencia de valor.
- Si esta transacción está enviando un mensaje a un contrato (por ejemplo, llamando a un método en el contrato inteligente), esta es la dirección del contrato.
- Si esta transacción está creando un contrato, este valor siempre está vacío.
- value:
- Si esta transacción transfiere ether, la cantidad en wei que se transferirá a la cuenta del destinatario.
- Si esta transacción envía un mensaje a un contrato, la cantidad de wei a pagar por el contrato inteligente que recibe el mensaje.
- Si esta transacción está creando un contrato, esta es la cantidad de wei que se agregará al saldo del contrato creado.
- v, r, s: valores utilizados en la firma criptográfica de la transacción utilizada para determinar el remitente de la transacción.
- data: input de la llamada de mensaje. Por ejemplo, imagina que estás intentando ejecutar un método de establecimiento en un contrato inteligente, el campo de datos contendría el identificador del método y el valor que se debe pasar como parámetro (solo para la transferencia de valor y el envío de una llamada de mensaje a un contrato inteligente).
- init: el código EVM utilizado para la inicialización del contrato (solo para la creación de contratos).
Como el transaction trie se construye con “Modified Merkel Patricia Trie”, solo el nodo raíz se almacena en el bloque, específicamente, en el block header.
Anatomía de un bloque
Un bloque se divide en dos:
- El encabezado - block header: esta es la estructura que contiene el hash de su bloque predecesor (también conocido como bloque padre), construyendo una cadena garantizada criptográficamente.
- El cuerpo - block body: contiene una lista de transacciones que se han incluido en este bloque y una lista de encabezados paralelos o que surgieron a la vez que este (ommer).
Algunos de los campos que contiene un encabezado de bloque son:
- parentHash: hash del encabezado del bloque anterior. Cada bloque contiene un hash del bloque anterior, hasta el primer bloque de la cadena. Así se protegen todos los datos contra modificaciones (cualquier modificación en un bloque anterior cambiaría el hash de todos los bloques posteriores al bloque modificado).
- beneficiary: cuenta de Ethereum que obtendrá la recompensa por minar este bloque.
- transactionsRoot: hash del nodo raíz del transaction trie. Este trie contiene todas las transacciones en el cuerpo del bloque.
- receiptsRoot: cada vez que se ejecuta una transacción, Ethereum genera un recibo de transacción que contiene información sobre la ejecución de la transacción. Este campo es el hash del nodo raíz del transaction receipt trie.
- number: número de bloques de antepasados. Esto representa la altura de la cadena (cuántos bloques hay en la cadena). El bloque de génesis tiene el número cero.
Transaction receipt trie
El transaction receipt trie registra los recibos (resultados) de las transacciones. El recibo es el resultado de la transacción que se ejecuta con éxito. El recibo incluye un hash de transacción, número de bloque, cantidad de gas utilizado y dirección del contrato, etc.
Los campos de un recibo son:
- blockHash: hash del bloque en el que estaba la transacción.
- blockNumber: número del bloque en el que estaba la transacción.
- transactionHash: hash de la transacción.
- transactionIndex: entero indicando el índice de la transacción dentro del bloque.
- from: cuenta que envió la transacción.
- to: cuenta que recibió la transacción.
- gasUsed: cantidad de gas usada por esta transacción.
- logs: una lista de logs que haya generado la transacción.
- status: indica si la transacción se realizó con éxito o tuvo algún error.
Para recapitular…
Ethereum tiene 4 tipos de tries para almacenar información:
- El world state trie contiene el mapeo entre direcciones y estados de cuenta. El hash del nodo raíz se incluye en un bloque (en el campo stateRoot) para representar el estado actual cuando se creó ese bloque. Solo hay un world state trie.
- El account storage trie contiene los datos asociados con un contrato inteligente. El hash del nodo raíz se incluye en el estado de la cuenta (en el campo storageRoot). Hay un account storage trie para cada cuenta.
- El transaction trie contiene todas las transacciones incluidas en un bloque. El hash del nodo raíz se incluye en el encabezado del bloque (en el campo transactionRoot). Hay un transaction trie por bloque.
- El transaction receipt trie contiene todos los recibos de transacción para las transacciones incluidas en un bloque. El hash del nodo raíz también se incluye en el encabezado del bloque (en el campo de receiptsRoot); Hay un transaction receipt trie por bloque.
💡 Para mayor referencia, visita los textos originales State in Ethereum, Ethereum Virtual Machine y Ethereum State Trie Architecture Explained