El Apéndice D del Libro Amarillo , al definir los tipos de nodos, establece (las cursivas son mías):
Hoja : una estructura de dos elementos cuyo primer elemento corresponde a los nibbles en la clave que aún no se han contabilizado por la acumulación de claves y ramas atravesadas desde la raíz. Se utiliza el método de codificación de prefijo hexadecimal y se requiere que el segundo parámetro de la función sea verdadero.
El Apéndice C define la codificación de prefijo hexadecimal HP
:
...El nibble inferior del primer byte es cero en el caso de un número par de nibbles y el primer nibble en el caso de un número impar. Todos los nibbles restantes (ahora un número par) encajan correctamente en los bytes restantes
Cuando se aplica al Merkle Tree, si la longitud de la clave es un número impar de nibbles, el primer nibble de la clave se almacena en el segundo nibble del prefijo , de lo contrario, el segundo nibble del prefijo se establece en 0. Si mira de cerca en el dibujo verás pequeñas flechas destinadas a representar esto. De cualquier manera (longitud de clave par o impar), el número total de nibbles siempre es par, lo que significa que el tamaño del árbol merkle siempre será un número entero de bytes.
Otra forma de poner esto podría ser:
Dada una clave k
con cierto número de nibbles, el byte de prefijo será:
prefix byte key byte(s)
[nibble0, nibble1]---> Node type [stored nibbles]
[0, 0] ----------> Extension Node, n (=length(k)) is even [k[0]...k[n-1]]
[1, k[0]] ----------> Extension Node, n (=length(k)) is odd [k[1]...k[n-1]]
[2, 0] ----------> Leaf Node, n (=length(k)) is even [k[0]...k[n-1]]
[3, k[0]] ----------> Leaf Node, n (=length(k)) is odd [k[1]...k[n-1]]
Si el OP lee esto... Creo que sería bueno dejar en claro que ☐ se refiere al primer mordisco de la clave original . Además, para evitar confusiones, creo que también sería una buena idea expresar ambos nibbles de los prefijos "pares"... En otras palabras, mostrar el prefijo 2 como 20 y el prefijo 0 como 00 en el diagrama para evitar confusiones. Solo mis $0.02.
Finalmente, no estoy seguro de que las claves originales que tienen un número impar de nibbles (por ejemplo, 0xa711355) sucedan alguna vez. El caso de uso de los árboles de Merkle Patricia es almacenar diccionarios (listas asociativas). Claramente, todas las claves se expresarán en bytes y no pueden tener un número impar de nibbles. Es cierto que, en teoría, las claves pueden ser cualquier número de bits. Pero en el mundo real, rara vez se ven claves que no sean un número entero de bytes. Eso estaría bien... extraño.
Por favor corrígeme si estoy equivocado. Solo trato de aprender como todos los demás. ;)
sharish
sharish
Sotavento
length(prefix+keys)
...