Un nodo hoja se define como la tupla [encodedPath, value], y encodedPath usa la codificación Hex-Prefix. ¿Es posible que tengamos un nodo hoja con encodedPath que solo tenga el prefijo y no incluya una ruta parcial?
Tomando los siguientes datos...
<5e 52> : 'val1'
<ac 40> : 'val2'
<ac 4f> : 'val3'
... ¿el trie se vería así o estoy equivocado?
rootHash: [ <>, <>, <>, <>, <>, hashA, <>, <>, <>, <>, hashB, <>, <>, <>, <>, <>, <> ]
hashA: [ <3e 52>, 'val1' ]
hashB: [ <00 c4>, hashC ]
hashC: [ hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, hashE, <> ]
hashD: [ <20>, 'val2' ]
hashE: [ <20>, 'val3' ]
Tenga en cuenta que rootHashy hashCson nodos de rama; hashBes un nodo de extensión; y hashA, hashDy hashEson nodos hoja. Mi duda está relacionada con hashDy hashEencodedPaths. Si entendí que es correcto poner 20como en HP codificar un nodo de hoja con una longitud de ruta uniforme (en estos casos 0) debería obtener el prefijo 2y un 0nibble de relleno adicional.
Construí el trie en el mismo formato que tú (dada la información en https://github.com/ethereum/wiki/wiki/Patricia-Tree ) y esto me llevó al mismo resultado. Para responder a su pregunta: Sí, si un nodo de hoja no contiene nibbles adicionales en la ruta parcial, lo finaliza con el prefijo 20 (2 para nibbles pares cuentan en la ruta y 0 para relleno, como escribió) y no más camino.
La ruta codificada se almacenará como un bytearray. El algoritmo funciona así: dada una ruta codificada b como un bytearray:
# Python style code
flag = b[0] & 0xF0
nodetype = flag & 0x2
parity = flag & 0x1
partial_path = []
# parity odd?
if parity:
partial_path.append(b[0] & 0x0F)
# append all other bytes from the encoded path (or do nothing if there is no encoded path)
for item in b[1:]:
partial_path.append(item)
# extension node
if not nodetype:
# do stuff ...
# and so on
Canonista juramentado
mar212