Blockchain

在 Ethereum Modified Merkle-Particia 樹中,前綴、鍵和值分別表示什麼?

  • May 17, 2018

在此處輸入圖像描述

葉節點中的前綴“3☐”是什麼意思?

黃皮書的附錄 D ,在定義節點類型時,狀態(斜體是我的):

:一個包含兩項的結構,其第一項對應於鍵中的半字節,這些字節尚未通過從根遍歷的鍵和分支的累積來解釋。採用十六進制前綴編碼方式,要求函式 第二個參數為真。

附錄 C 定義了十六進制前綴編碼HP

…在偶數半字節的情況下,第一個字節的低半字節為零,在奇數的情況下,第一個半字節為零。所有剩餘的半字節(現在是偶數)都適合剩餘的字節

應用於 Merkle 樹時,如果密鑰長度為奇數個半字節,則密鑰的第一個半字節儲存在前綴的第二個半字節中,否則將前綴的第二個半字節設置為 0。如果仔細觀察在圖中,您會看到用於描繪這一點的微小箭頭。無論哪種方式(偶數或奇數密鑰長度),半字節的總數始終是偶數,這意味著默克爾樹的大小將始終是整數字節。

另一種說法可能是:

給定一個k帶有一些半字節的鍵,前綴字節將是:

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]]

引用自:https://ethereum.stackexchange.com/questions/12941