在不完全重建樹的情況下驗證 Merkle 根的正確性
假設 Alice 有一個值列表，Bob 向 Alice 發送了一個 Merkle 根，他聲稱該根用於這個值列表。Merkle 樹的構造算法當然是相互了解的。
然後 Alice 可以從列表中選擇任意值並向 Bob 詢問他們的 Merkle 證明。
假設 Alice 想要避免建構整個樹來驗證 Bob 的 Merkle 根。在 Bob 提供了 N 個 Merkle 證明之後，她如何確定 Bob 的 Merkle 根是正確的？換句話說，Bob 在 N 次查詢後對 Merkle 根撒謊的機率是多少？
編輯：
我有一個答案，但我認為它不正確。假設我們有一棵樹，總共有 M 個節點（計算所有層），並且該樹中的每個證明都包含 N 個雜湊作為證明中的數據點。如果 Alice 要求 K 個不同的證明，那麼她可以以 (N*K)/M 的確定性確定根是正確的。
似乎很天真，但這樣的下限只是一個下限，因為它不止於此。該樹由具有原像抗性的雜湊組成，因此這不僅僅是計算已知數據點與總數據點的問題……或者是嗎？
編輯＃2：
另一種配方：
給定一個已知的任意值向量 V 和通過為 V 建構 Merkle 樹建構的 Merkle 根 R，如果我有 N 個 Merkle 證明，我如何確定 R 是從 V 中誠實正確地建構的？
顯然我可以重建樹，因為我擁有（或可以計算）所有 V，但可以說我不想這樣做，因為它很耗時等。
換句話說，Bob 在 N 次查詢後對 Merkle 根撒謊的機率是多少？
好吧，這是鮑勃可以作弊的一種方式；他可以拿清單 $ M $ 價值觀$$ V_1, V_2, …, V_M $$而不是基於此形成 Merkle 樹，而是選擇一個值 $ c $ 索引和值 $ V’c \ne V_c $ , 而是形成列表$$ V_1, V_2, …, V{c-1}, V’c, V{c+1}, …, V_M $$並基於該列表形成 Merkle 樹（並給 Alice 計算的根，該根與原始列表中的根的機率很大）。
然後，當愛麗絲給他 $ K $ 指數為基礎 $ K $ 證明，他根據修改後的列表和他計算的樹形成它們。只有當她要求的索引之一恰好是索引時，他才會被檢測為作弊 $ c $ ; 如果她要求的索引都不是索引 $ c $ ，那麼她將收到的證明都是有效的並且彼此一致（因為它們對應於自洽的默克爾樹，顯示的葉子是她期望的值）
Bob 被發現作弊的機率，即 Alice 選擇的指標之一的機率是 $ c $ ， 是 $ K/M $ . 因此，針對任何策略的檢測機率僅此而已（如果 Bob 可以採用更好的策略，它可能會更小）。
因此，要以 0.99 的機率檢測 Bob 作弊，我們有 $ K > 0.99M $ ; 到那時，如果 Alice 自己重新計算這棵樹，實際上計算量會減少。
對我們來說似乎很有趣，因為如果列表的建構成本很高，它可能是一種時空證明形式
現在，將問題視為工作量證明會更有趣（空間證明不起作用，因為可以計算樹和身份驗證路徑而不會顯著增加所需的計算量）；顯然，我上面給出的作弊策略並沒有解決這個問題，因為 Bob 正在做全部的工作。如果我有更多時間，我會嘗試更多地調查…