Cómo se forma el árbol de transacciones de Ethereum

Voy a estar en desacuerdo con la conversación en los comentarios a la otra respuesta. (¡Disculpas de antemano!)

Creo que lo que se describe en la pregunta es generalmente correcto, al menos por la forma en que entendí las cosas.

5. ¿El hash raíz de la transacción está presente en un bloque que apunta a raíces de árboles individuales o, de nuevo, es un árbol único como un árbol de estado (es decir, apunta a varios niveles de raíz)?

Un árbol individual/raíz de trio. El árbol/trie de estado es diferente porque a menudo estamos actualizando el estado existente de un bloque anterior, mientras que con las transacciones no puede suceder tal cosa.

No creo que el árbol/trie sea en realidad solo una lista (es decir, una sola ramificación hasta el final). En primer lugar, perderíamos las ventajas de usar un árbol/trie. Un árbol/trie nos da O(log _x n) recorrido, acceso, etc., mientras que una lista sería O(n) . En segundo lugar, en un árbol de Merkle son las hojas las que contienen los datos reales , con los nodos principales que contienen hashes intermedios hasta la raíz. Por lo tanto, una "lista de Merkle" solo podría contener una transacción, que sería el nodo final o la cola. (Pero entonces la cola sería lo mismo que la raíz... así que tal cosa no tiene sentido de todos modos).

En segundo lugar, del código Geth [1 , 2 , 3] , y creo que del Libro Amarillo [ecuación (176), aunque es difícil decir... ], el orden del árbol de transacciones es 16, es decir, cada El nodo tiene 16 nodos secundarios. De manera similar, la imagen aquí también tiene una etiqueta de "16" para cada uno de los árboles/intentos.

No estoy seguro de cómo se mantiene o traduce el orden de las transacciones en el árbol.

Descargo de responsabilidad: si estoy combinando el orden con el grado al describir la cantidad de niños por nodo en el árbol/trie anterior, entonces disculpas.

Absolutamente, la mejor manera de resolver esto que he encontrado es Ethereum Ontology aquí: https://github.com/ConsenSys/EthOn .

No sé si se le permite simplemente vincular a las respuestas, pero si no lo está, debería estarlo. Duplicar este trabajo en StackExchange sería un error.

Casi correcto.

Los árboles Transaction y Receipts son solo Merkle Trees, mientras que State Trie es un Merkle Patricia Trie. Dado que cada bloque de Ethereum contiene una lista de transacciones, y esta lista está "sólida congelada" (Buterin - https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/ ), no serviría de nada hágalo para que obtenga O (log (n)) leído, escrito o eliminado. Lo que importa es que puede dar una prueba de inclusión de Merkle. Además, ni los árboles de transacciones ni de recibos se conservan, se recrean según sea necesario (a diferencia del estado trie, por supuesto).

**Déjame aclarar algo

No necesita un Merkle Patricia Trie para la raíz de txn y la raíz de recibos, pero al menos en pyethereum así es como crean ambos intentos. Mi conjetura es mantener la coherencia, una función para todos los intentos. En común.py

def mk_receipt_sha(receipts): t = trie.Trie(EphemDB()) for i, receipt in enumerate(receipts): t.update(rlp.encode(i), rlp.encode(receipt)) return t.root_hash

Aquí hay un ejemplo de cómo se ve el trie de estado (para transacciones, simplemente reemplace Estado mundial simplificado en la parte superior derecha con Transacciones simplificadas donde son Claves transaction_indexy Valores transaction_content. Es simplificado ya que se omiten algunos detalles, como la codificación RLP)

Si no me equivoco, los cambios de estado se rastrean en un solo árbol de estado.

Merkle Patricia Trie es una estructura de datos inmutable. Cada vez que realice cambios en cualquier parte del trie, dará como resultado un nuevo trie con una raíz diferente con un hash diferente. Sin embargo, el nuevo trie podría tener punteros a subárboles del trie de estado anterior. Digamos que tuviste un intento con 3 niveles. Si desea cambiar algo en el nivel más bajo, debe crear un nuevo nodo en el segundo nivel y un nuevo nodo en el primer nivel (la raíz) que se registrará en la cadena de bloques.

Cada bloque tiene un hash de raíz de estado que apunta a la raíz que tiene el estado de las cuentas que participan en el conjunto de transacciones de ese bloque.

Cada bloque tiene el hash de la raíz del estado que apunta a la raíz del estado y tiene el estado de todas las cuentas, no solo las que participan en el conjunto de transacciones de ese bloque. Como mencioné anteriormente, cada vez que se cambia el estado de cualquier cuenta, se cambia la raíz de todo el árbol.

¿El hash raíz de la transacción está presente en un bloque que apunta a raíces de árboles individuales o, de nuevo, es un árbol único como un árbol de estado (es decir, apunta a varios niveles de raíz)?

Cada bloque tiene su propia prueba de transacción donde las claves son índices de transacción codificados en RLP dentro del bloque y los valores son transacciones codificadas en RLP.

Para resaltar esta diferencia, he creado dos diagramas para árboles de estado y de transacción.

En su primera imagen donde se representa el estado trie, apunta la raíz del estado del bloque 180994 a la raíz del estado anterior trie como su hijo izquierdo. Esto normalmente no debería suceder. Creo que lo que quisiste decir es que la nueva raíz debería apuntar al hijo izquierdo de la raíz anterior.

Creo que tu diagrama es correcto. Encontrar una transacción debería ser tan fácil como hacer una búsqueda binaria en los bloques. Considere la función:

find block where: someBlockT1 <= timestamp(tx) <= someBlockT2

Luego busque a través del Tx merkle trie que está contenido en el bloque devuelto.