如何創建一個 merkle 樹，讓您可以插入和刪除元素，而無需重新計算整個事物？

我有一棵默克爾樹。這棵樹的元素按排序順序排列，因此任何人都可以創建證明樹中沒有某物的證據。到目前為止，一切都很好。

但是，我也希望能夠在樹中添加和刪除元素。如果我使用普通的默克爾樹，我必須重新計算大部分樹。例如，我有以下默克爾樹：

                   395
         /                     \
       85                       310
   /        \               /        \
 23          62          137          172
/  \        /  \        /   \        /   \
1    22    23    39    60     77    82     91

（例如，我對雜湊函式使用加法。）

我將 50 插入到默克爾樹的中間。

                              445
                      /                  \
                   354                    91
         /                     \           \
       85                       269         91
   /        \               /        \       \
 23          62          110          159     91
/  \        /  \        /   \        /   \     \
1    22    23    39    50     60    77     82    91

50 之後的每個 merkle 分支都發生了變化。我不得不執行雜湊函式 5 次。對於非常大的默克爾樹來說，這將變得非常笨拙。

我正在尋找具有以下屬性的默克爾樹：

1. **快速地。**我不需要重新計算整個事物（或整個事物的一半）來從中間插入或刪除某些東西。
2. **真正的。**如果我有一個 merkle 根，那麼應該只有一棵樹對應於那個 merkle 根。更改樹的任何部分都會導致驗證失敗。
3. 確定性。（可選）這基本上與前面的說法相反。如果我從 merkle 樹中取出元素，並從這些元素建構一個新的 merkle 樹，我應該得到相同的根雜湊。
4. **存在證明。**如果該元素在樹中，則擁有足夠多樹的人應該能夠證明該元素在樹中。這個證明應該相當小。
5. **不存在的證明。**如果某個元素不在樹中，那麼擁有足夠多樹的人應該能夠證明該元素不在樹中。這個證明應該相當小。

您可以使用 Merkleized 二進制樹。

您首先單獨散列集合中的所有元素。在此範例中，我使用 3 位散列函式而不是 256 位。

假設您的集合中有 5 個元素，它們散列為： A: 011 B: 101 C: 111 D: 001 E: 010

現在您將它們排列成一棵樹，使用密鑰雜湊的位作為拆分條件：

根

• 0

  • 0

    • 1：D

  • 1

    • 0：E
    • 1：一個

• 1

  • 0

    • 1：乙

  • 1

    • 1：C

現在，您將每個葉節點與完整的密鑰雜湊關聯，並將每個內部節點與其連接的子節點的雜湊關聯。

結果的根是：

• 快速更新：添加或刪除的雜湊操作數與雜湊函式中的位數成正比（並且不取決於樹中元素的數量）。
• 真實的：根送出到整個樹結構，因此間接送出到它的所有葉子。
• 確定性：插入/刪除操作的順序不影響樹結構。

一種可能的優化是壓縮從具有 1 個子節點的內部節點構造的分支。這導致以下結構：

根

• 0

  • 0：D

  • 1

    • 0：E
    • 1：一個

• 1

  • 0：乙
  • 1：C

現在操作在元素數量上平均是對數的，並且所有其他屬性仍然存在。

引用自：https://bitcoin.stackexchange.com/questions/51423