Ein Blattknoten ist als Tupel [encodedPath, value] definiert, und encodedPath verwendet die Hex-Prefix-Codierung. Ist es möglich, dass wir einen Blattknoten mit encodedPath haben, der nur das Präfix und keinen Teilpfad enthält?
Nehmen Sie die folgenden Daten ...
<5e 52> : 'val1'
<ac 40> : 'val2'
<ac 4f> : 'val3'
...würde der Trie so aussehen oder irre ich mich?
rootHash: [ <>, <>, <>, <>, <>, hashA, <>, <>, <>, <>, hashB, <>, <>, <>, <>, <>, <> ]
hashA: [ <3e 52>, 'val1' ]
hashB: [ <00 c4>, hashC ]
hashC: [ hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, hashE, <> ]
hashD: [ <20>, 'val2' ]
hashE: [ <20>, 'val3' ]
Beachten Sie, dass rootHashund hashCZweigknoten sind; hashBist ein Erweiterungsknoten; und hashA, hashDund hashEsind Blattknoten. Mein Zweifel bezieht sich auf hashDund hashEencodedPaths. Wenn ich es verstanden habe, ist es richtig, 20wie bei der HP-Codierung einen Blattknoten mit gerader Pfadlänge (in diesen Fällen 0) zu setzen, der das Präfix 2und ein zusätzliches 0Padding-Nibble erhalten sollte.
Ich habe den Trie im selben Format wie Sie erstellt (anhand der Informationen in https://github.com/ethereum/wiki/wiki/Patricia-Tree ) und dies führte mich zu demselben Ergebnis. Um Ihre Frage zu beantworten: Ja, wenn ein Blattknoten keine weiteren Nibbles im Teilpfad enthält, beenden Sie ihn mit dem Präfix 20 (2 für gerade Nibbles zählen im Pfad und 0 für Padding, wie Sie geschrieben haben) und keinem weiteren Pfad.
Der verschlüsselte Pfad wird als Bytearray gespeichert. Der Algorithmus funktioniert folgendermaßen: Bei einem codierten Pfad b als 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
Äthergeschworener Kanonist
meer212