證明你有ķķK記憶體字節
愛麗絲買了一個全新的硬碟， $ K $ （和 $ K \sim 10^{12} $ ) 字節大小。她對自己的購買感到非常高興，並告訴鮑勃這件事。Bob聲稱他還買了一個 $ K $ 字節硬碟。愛麗絲在這方面並不真正信任鮑勃，所以她要求他證明他的主張：
- 愛麗絲給鮑勃一個 $ O(\ln(K)) $ 她產生的大小問題。
- 問題只有在有的情況下才能解決 $ K $ 字節的記憶體。
- Bob 發回一個 $ O(\ln(K)) $ 大小的解決方案。
- Alice 驗證解決方案。
特別是，可能有兩種不同的情況：
- Alice 無需執行與 Bob 相同的操作即可驗證解決方案（在這種情況下，她甚至不需要 $ K $ -bytes 硬碟本身）
- Alice 使用她自己的硬碟計算與 Bob 相同的解決方案。
我們可以使用什麼問題？如果 Alice 和 Bob 之間的通信性質發生了一些變化（例如，需要雙向通信以上是可以的），那是完全可以的，但通信的規模永遠不應增長到類似 $ \Theta(K) $ .
我嘗試過的解決方案
（如果您不需要靈感，請隨意跳過此部分！）
- 使用 $ \Theta(K) $ 通信，Alice 顯然可以生成 $ K $ 隨機字節，將它們發送給 Bob 並要求他計算其中一些子集的雜湊值，她將僅在發送整個有效負載後發送。（我們需要數據子集的雜湊值，否則 Bob 可以在接收字節時隨時計算雜湊值）。但是這個解決方案顯然被拋棄了，因為它需要太多的溝通。
- Alice 發送一個種子，Bob 用種子生成隨機數來填充 $ K $ 字節，然後他對字節進行排序併計算雜湊。然而，一個 $ O(K^2) $ （及時）存在允許 Bob 通過重複重新生成隨機數來提取第一個、第二個、第三個……項目來計算雜湊的解決方案。所以這實際上並不能證明 Bob 有 $ K $ -字節硬碟。
- Alice 發送一個種子，Bob 用種子生成隨機數來填充 $ K $ 字節，然後進行混洗程序以隨機獲取小塊並將它們散列在一起，或對它們進行異或，或以這種方式進行任何操作，以便在幾次迭代後每個字節相互依賴，並且不可能計算部分隨時隨地的解決方案。Alice 然後詢問總結果子集的散列（甚至是總散列）。這可能會奏效，但它存在在磁碟上產生大量隨機 I/O 的問題，這實際上可能會損壞現實生活中的非 SSD 硬碟。
- Bob 生成一系列工作證明（如在比特幣探勘中）。Bob 然後在序列上生成一棵 Merkle 樹並將根發送給 Alice。愛麗絲要求 $ N $ 隨機工作證明，Bob 將 Merkle 樹上從根到葉的整個導航發回，Alice 驗證一切。但是，Bob 可以只保存第一個 $ L $ Merkle 樹的層，並在旅途中重新計算記憶的最後一個節點下的所有葉子。如果他儲存 $ 10^9 $ 值，例如，他只需要重新計算 $ 10^3 $ 葉子，這在旅途中是可行的。
在過去的幾年中，在相關問題上進行了大量工作。正如 Thomas Perst 提到的，這個問題被認為是記憶困難的功能，可證明（在一些理想化的模型中）需要一些空間來評估。
然而，僅 MHF 只是這類原語中最弱的一個。已經設計了許多原語來增強具有其他理想屬性的 MHF，例如有效的驗證。您正在尋找的東西可能最好通過瞬態空間的證明來捕捉，您可以證明在計算過程中使用了給定數量的空間，因此可以在比使用的空間小得多（多對數）的時間和空間中驗證證明證明者。
我建議閱讀這篇文章的介紹，它確實解決了您的問題，並且如果您想深入了解該主題，還可以提供許多有趣的參考資料。大多數結構使用具有特定組合屬性的圖（例如擴展圖和深度強韌圖），這意味著在圖上玩某種遊戲（卵石遊戲）的難度下限。這些下限然後轉化為隨機預言模型中記憶體使用的界限。
我至少看到了一種做你想做的事情的方法：記憶硬函式。
Alice 只需要儲存一個值 $ m $ 及其雜湊 $ H(m) $ ， 在哪裡 $ H $ 是一個記憶硬函式，其中參數被縮放，因此您無法計算 $ H(m) $ 除非您超過某個記憶體門檻值。參見例如這篇文章，它提供了一個可證明的記憶體硬散列函式。Alice 只需要儲存短值 $ m $ 和 $ H(m) $ ，但有人（可能是愛麗絲）需要計算 $ H(m) $ 預先發送給 Alice。