創建 Merkle 樹分支的規範方法是什麼？

我目前正在研究創建一些緊湊的 Merkle 樹分支，以證明給定的雜湊包含在給定的 Merkle 根中。我最初的想法是列出葉子、Merkle 根以及與給定葉子組合以構成 Merkle 根的所有雜湊值。

所以在這個例子中：

我會說

Leaf:  12c5
Root:  2f9c
Nodes: [d187, a8b5, 1328, d063]

但是，由於節點的順序對於創建 Merkle 根很重要，我還需要列出節點是在左側還是右側。

我想知道是否有一種規範的方式來列出這些資訊來創建 Merkle 分支？

如果你有葉子的索引，它描述了從它到根的路徑。

具體來說，二進製表示是從根開始的一系列左 (0) 和右 (1) 轉。如果您正在向上工作，最低有效位表示葉子是左 (0) 還是右 (1) 子節點，下一位表示葉子的父節點，依此類推。

這張圖很明顯：

每個節點上的數字是該節點在其層中的索引的二進製表示。

因此，僅列出正在證明其成員資格的葉子的索引就提供了足夠的資訊來驗證證明。

下面是一些用於驗證證明的簡單虛擬碼：

func isValidProof(leaf, index, nodes, root):
 currentNode = leaf
 for node in nodes:
   if index mod 2 == 0:
     currentNode = hash(currentNode, node)
   else:
     currentNode = hash(node, currentNode)
   index = index >> 1 // shift 1 right is essentially like dividing by 2, ignoring the remainder
 return currentNode == root

不確定規範的方式，但一種簡單的方法是使用額外的字節來編碼證明中每個節點散列旁邊的“左”或“右”。

所以而不是：

Leaf:  12c5
Nodes: [d187, a8b5, 1328, d063]

而是這樣做：

Leaf:  12c5
Nodes: [left|d187, right|a8b5, left|1328, right|d063]

為了節省一些空間，您可能希望使用一個位並分別發送“方向”：

Leaf:  12c5
Nodes: [d187, a8b5, 1328, d063]
Dirs:  [0,    1,    0,    1]

如果樹的深度是 8 的倍數，這非常有用。否則，您需要一些填充。

引用自：https://crypto.stackexchange.com/questions/31871