ELI5 ¿Cómo funciona un árbol Merkle-Patricia-trie?

Entiendo que Merkle tree son Hashes de Hashes, tienen la ventaja de que solo puedes verificar un subárbol. Pero ¿y Patricia ? ¿Qué significa un trio ? ¿Y cómo se usa en Ethereum?

Respuestas (2)

Trie (también llamado árbol digital, prefijo trie o radix trie)

Una estructura de datos de árbol ordenada que se utiliza para almacenar un conjunto dinámico o una matriz asociativa donde las claves suelen ser cadenas. La posición de un nodo en el árbol define la clave con la que está asociado. https://en.wikipedia.org/wiki/Trie

ingrese la descripción de la imagen aquí

Un trie para las teclas "A","to", "tea", "ted", "ten", "i", "in" y "inn".

Patricia - Algoritmo práctico para recuperar información codificada en alfanumérico ( fuente ) ( artículo original de Donald R. Morrison ). Un trie de Patricia es un trie de base binaria: elección binaria en cada nodo al atravesar el trie; esto se modifica en Ethereum.

ingrese la descripción de la imagen aquíFuente: https://en.wikipedia.org/wiki/File:An_example_of_how_to_find_a_string_in_a_Patricia_trie.png

En ethereum, se usa hexadecimal: X caracteres de un "alfabeto" de 16 caracteres. Por lo tanto, los nodos en el trie tienen 16 nodos secundarios (el "alfabeto" hexadecimal de 16 caracteres) y una profundidad máxima de X. Tenga en cuenta que un carácter hexadecimal se denomina "mordisco".

Merkle Patricia Trie

Como se describe aquí , el término Merkle implica que

el nodo raíz se convierte en una huella digital criptográfica de toda la estructura de datos

Ethereum modificado Merkle Patricia Trie

El papel amarillo describe un merkle patricia trie modificado. Esto define tres tipos de nodos diferentes; extensión, rama y hoja. Estos se describen, utilizando un estado mundial simplificado, en el siguiente diagrama:

ingrese la descripción de la imagen aquí

¿No debería una clave world-statecontener 8 nibble (32 bytes)? En su ejemplo (última imagen) contiene 7 nibbles, que son 28 bytes. @atomh33ls
@Alper gracias... Lo acorté para hacerlo más conciso. Creo que 8 nibbles son solo 4 bytes... y 7 son 3,5 bytes. Necesitaría 64 caracteres hexadecimales para 32 bytes...
¿Qué hacen el nodo hoja y los nodos de extensión del trie?
¡Gracias! ¿Cómo se sincroniza un árbol obsoleto con un árbol actualizado? (por ejemplo, cuando un cliente se conecta después de un día). ¿Simplemente descarga todo el árbol actualizado, o se recibe algún tipo de "diferencia" para la sincronización?
@HelinWang No hay problema, creo que esto depende de la implementación, por lo que sería mejor plantearlo como una nueva pregunta...
¡Gracias @atomh33ls! Acabo de hojear el código fuente de go eth trie, parece que hay otro tipo de nodo: hashNode, si mi comprensión es correcta, es una referencia a cualquier tipo de nodo ilustrado en su gráfico en la base de datos. Tal vez su gráfico podría mejorarse señalando eso.

'Trie' viene de la palabra recuperación, ya que solo usa el prefijo de una palabra para encontrarla en un diccionario. Es un árbol ordenado donde las claves suelen ser cadenas que terminan con un símbolo de terminal, y cada vértice representa un prefijo. La raíz de un trie suele ser una cadena vacía, como podemos ver en el diagrama tomado de wikipedia.

diagrama de wikipedia

Para obtener más información sobre la diferencia entre un árbol trie y radix (Patricia).

https://stackoverflow.com/questions/14708134/cuál-es-la-diferencia-entre-trie-y-radix-trie-data-structures

Se pueden encontrar más especificaciones del árbol Merkle Patricia que usa Ethereum en el blog de ethereum

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

ELI5 ¿Cómo funciona un árbol Merkle-Patricia-trie?
RespuestasAquíPolítica de privacidad1y, 10v