有沒有辦法簽署消息以便驗證任何子集？
我想知道是否有一個可以允許以下內容的方案：
- 愛麗絲簽署消息 $ M $ 帶簽名 $ S $ 並把它交給鮑勃和馬洛里。
- Bob 可以呈現任何子集 $ M $ ， 隨著 $ S $ , 給 Victor，他可以驗證子集是否匹配 $ M $ .
- 如果馬洛里改變了一些 $ M $ ，然後將比特的一個子集發送給 Victor，Victor 可以知道該消息已被篡改。（當然，Mallory 不應該能夠構造一個有效的簽名來驗證她的篡改位）。
例如，說
- 愛麗絲的訊息 $ M $ 是 $ 100100 $ ，簽名為 $ 101 $ .
- 鮑勃將派維克多 $ M[0]=1, M[4]=0, signature=101 $ , Victor 將驗證這些位是否匹配 $ M $ .
- 馬洛里將派維克多 $ M[0]=1, M[4]=1, signature=101 $ （這是惡意的，因為 $ M[4] $ 不等於*_* $ 1 $ 在 $ M $ ）。維克多會注意到這一點並拒絕驗證。
有這樣的方案嗎？
我認為有一些幼稚的解決方案（例如，簽名可能由幾個子簽名組成：每個位及其索引 $ M $ 已簽名，並且結果是連接的），但我希望簽名相對於消息的大小而言較短。
我們可以很容易地看到簽名必須至少與消息一樣大。否則，將無法驗證任意單個位。使用比特對消息進行
n簽名必須必然涉及可以驗證n不相關的 1 比特消息子集的簽名。但是，如果我們假設給 Bob 和 Mallory 的消息副本，則可能存在對整個消息進行計算但不傳輸整個消息的機會。這可以幫助減少簽名大小。
您可能對Merkle 樹感興趣。我不知道它們是否正是您正在尋找的東西，但它們提供了一些有趣的方法來證明有關消息的連續子集的事情。在最壞的情況下，您必須有效地將整個 Merkle 樹發送給 Victor。但是，為了顯示樹的一小部分，您可以將大部分資訊保留在消息之外。您只需為您發送的每一位顯示兄弟葉子，這不會顯示整個消息，同時仍將其作為子集進行身份驗證。
有一些加密貨幣算法可以利用它進行小額支付。Alice 生成一個硬幣列表，將它們放入 Merkle 樹中，然後獲取由 Victor 簽名的樹的頂部。然後，她將這個簽名的頂部交給 Bob，Bob 用 Victor（線上或離線）對其進行身份驗證。在此之後，Alice 可以簡單地向 Bob 發送一個硬幣，只需顯示它，以及證明它是她的硬幣列表的一部分所需的所有兄弟內部節點。當然，這些算法力求高效。它們按順序顯示硬幣，因此它們只需要顯示連續的子集，而不是您可能需要的任意子集。這將消息流量降低到
O(n log m)從鑄造n硬幣轉移出來的m硬幣。另一種方法是仔細選擇 Alice 建構的消息以具有您想要的屬性，而不是任意消息。 零知識證明充滿了巧妙的情況，其中 Bob 必須展示有關消息的資訊，同時仔細控制傳輸的資訊量。
S您絕對應該注意的一件事是 Eve 計算來自 just的消息以及 Bob 和 Victor 之間的消息流量是否存在任何問題。消息的內容可能會開始洩露。如果你知道一組n字節的內部節點，你可以暴力破解這些n字節，恢復 Bob 沒有透露的部分消息。但是，如果目標只是向 Victor 提供經過驗證的消息的子集，那可能是可以接受的。
命題：簽名由消息組成 $ M $ 和標準簽名 $ S $ 的 $ M $ 作為附錄，例如 $ S $ 根據 Ed25519。這允許驗證任何子集 $ M $ （通過檢查子集 $ M $ 反對全面 $ M $ , 和完整的 $ M $ 反對它的簽名 $ S $ ).
該提案揭示 $ M $ ，但這是不可避免的：如果可以驗證任何子集 $ M $ , 那麼可以很容易地找到 $ M $ 不管怎樣，一點一點。
出於同樣的原因，這個提議的規模損失將是最小的，如果 $ S $ 是最小的。