Ethereum Merkle Patricia Trie (nodo de extensión)

Cada vez que se agrega un nuevo elemento al trie, el algoritmo puede decidir si insertar una rama, una hoja o una extensión. Digamos que necesita insertar 3 pares clave-valor:

"0x01": 1
"0x01234": 2
"0x01235": 3

Después de insertar "0x01", el trie se verá así ( hash0es root):

<hash0> leaf ["0x01", 1]

Después de insertar "0x01234" ( hash1es root):

<hash1> extension ["0x01", <hash2>]
<hash2> branch [NULL,NULL,<hash3>,..<13 NULLs>.., 1]
<hash3> leaf ["0x34", 2]

Después de insertar "0x01235" ( hash4es root):

<hash4> extension ["0x01", <hash5>]
<hash5> branch [NULL,NULL,<hash6>,..<13 NULLs>.., 1]
<hash6> extension ["0x3", <hash7>]
<hash7> branch [NULL,NULL,NULL,NULL,<hash8>,<hash9>..<10 NULLs>.., NULL]
<hash8> leaf ["", 2]
<hash9> leaf ["", 3]

Generalmente, al insertar un par clave-valor:

• si se detuvo en un nodo NULL, agregue un nuevo nodo de hoja con la ruta restante y reemplace NULL con el hash de la nueva hoja.
• si se detuvo en un nodo de hoja, debe convertirlo en un nodo de extensión y agregar una nueva rama y 1 o 2 hojas.
• si se detuvo en un nodo de extensión, lo convierte en otra extensión con una ruta más corta y crea una nueva rama y 1 o 2 hojas. Si la nueva ruta resulta estar vacía, la convierte en una rama.

Al eliminar un par clave-valor:

• si hay una rama que tiene un solo nibble no NULL y un valor NULL, esta rama se puede reemplazar con una hoja o una extensión.
• si hay una extensión que apunta a otra extensión oa una hoja, se puede colapsar en una sola extensión/hoja.
• si hay una rama con todos los nibbles NULL y un valor no NULL, se puede convertir en una hoja.

Lo más probable es que me haya perdido algunos casos, pero espero que la idea general sea clara. Al agregar/eliminar pares clave-valor, el algoritmo puede tomar la decisión localmente en el nodo actual, no es necesario crear primero una versión descomprimida del trie y luego empaquetarla.

No estoy seguro de si cada implementación tiene su propia forma de hacerlo, pero la forma en que se hace en la implementación del cliente geth se asemeja a su enfoque en 2). Básicamente, un nodo de extensión se crea cada vez que una ruta dada en el trie contiene uno o más nodos de rama sucesivos con un solo nodo secundario. El nodo de extensión reemplaza estos nodos de rama (conceptualmente, no en la práctica). Esto se puede detectar fácilmente antes de crear los nodos de rama mirando la clave del nodo de hoja que se va a insertar. Para aclarar:

Suponga que tiene un trie que consta de 4 nodos, A, B, C y D:

        A
        |
        B      
       / \
      2   6
     /     \
    C       D

Las letras son nodos, los números son índices de nodos de rama

A es un nodo de extensión, B es un nodo de rama y C,D son nodos de valor.

Mostraré claves en formato decimal para facilitar la lectura. También es importante distinguir entre dos claves diferentes. Una es la clave acumulada de un nodo de valor, que es la clave completa que define el camino hacia él. En una transacción de Ethereum, por ejemplo, sería el índice de transacción. Las llaves se cortan en mordiscos. Y luego está la (llamémosla) clave de nodo , que es la clave contenida dentro de un nodo de valor o nodo de extensión. Esta clave será una subsección de la correspondiente clave acumulada. Además, dado que las claves se dividen en nibbles, cada nodo de rama puede tener 16 (2^4) hijos.

Digamos que la clave acumulada de C es [1,5,4,2,7,9] y la clave acumulada de D es [1,5,4,6,7,14].

Eso significaría que la clave de nodo de A es [1,5,4], la clave de nodo de C es [7,9] y la clave de nodo de D es [7,14].

Agreguemos un nodo de valor E con clave acumulada [1,5,12,11,7,7].

No describiré el algoritmo recursivo completo con todas las posibilidades ( encuéntrelo aquí ), pero en nuestro caso sucede lo siguiente, comenzando en el nodo raíz:

1. Los dos primeros nibbles de la clave de nodo de A y la clave acumulada de E son iguales, así que cree un nodo de extensión F con la clave de nodo [1,5].
2. Cree un nodo de rama G con nodos secundarios en los índices 4 (siguiente mordisco de la clave de A) y 12 (siguiente mordisco de la clave de E).
3. Dado que el nodo de extensión inicial A no tiene nibbles restantes, haga referencia a B directamente en G.
4. Como sabemos que tuvimos que crear una nueva rama para el nodo E, sabemos que no seguirán otros nodos después, así que solo haga referencia al nodo de valor en sí mismo en el índice 12 de G.

El nuevo trio es:

        F
        |
        G      
       / \
      4   12
     /     \
    B       E
   / \
  2   6
 /     \
C       D

F es un nodo de extensión, B,G son nodos de rama, C,D,E son nodos de valor. Sus claves de nodo son:

F:[1,5] C:[7,9] D:[7,14] E:[11,7,7]

Sé que esto no cubre todos los casos, pero espero que esto ayude, para obtener más información sobre Ethereum trie, consulte:

Fuente1 , Fuente2 , Fuente3