Merkle 樹（雜湊樹）中的成員身份和非成員身份證明

如果我們只知道 Merkle 根和數據塊，並且我們想知道這個塊是這個 merkle 樹的成員。我們需要知道與數據塊相關的從葉子到根的所有塊，而忽略其餘的塊。

但是，這是如何以及有什麼意義呢？

如果系統做這麼多的工作來查找與我們擁有的這個數據塊相關的塊。它還不如直接做一個簡單的搜尋，首先找出給定的數據塊是否存在。

當我們使用排序的默克爾樹來證明非成員身份時，這變得更加令人困惑。請解釋一下這兩個證明中的概念和發生了什麼

如果您不使用 merkle 樹，則檢查成員資格是 O(n) 操作，而不是使用 merkle 樹的 O(log n)。您無需遍歷集合中的每個項目，而是沿著深度為 O(log n) 的默克爾樹的一個分支前進。

但是，在沒有排序的情況下，證明非成員仍然需要 O(n) 步驟。排序可以通過僅查看與非元素相鄰的葉節點來證明非成員資格。

我在這裡找到了這個非常有用的簡短摘要。

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