使用給定的 SHA-256 最小化對消息的 ZK 證明的交換
考慮證明消息知識的問題 $ m $ 具有一定的公共 SHA-256 雜湊值 $ h $ , 不透露 $ m $ 或有關它的可用資訊，同時最小化資訊交換（通過假定提供完整性的雙向通道）。首先限制為單塊 SHA-256 ( $ m $ 小於 448 位）。
雙向的必要資訊流、交換次數和機率是否有明確的下界？ $ \varepsilon $ 得出錯誤的結論？
在SEC'2016 的訴訟程序中，目前的實現距離這有多遠，也許是 Irene Giacomelli、Jesper Madsen、Claudio Orlandi、ZKBoo：布爾電路的更快零知識？
獨立地，這樣的證明可以是非互動式的嗎（成為一個靜態證明，知道 $ m $ 散列到 $ h $ 用於製作證明，沒有說明證明的來源或新鮮度）？
要詳細回答這個問題的每個部分，幾乎需要一本書。在這裡，我將嘗試解決所有子問題，並每次都給出一個簡短的總結和指針。如果你想讓我開發一些特定的方面，你可以在評論中提問。我要說的大部分內容不會專門針對證明 SHA-256 原像的知識，而是來自關於零知識證明的一般結果。
編輯：底線
由於我的回答很長，這裡有一個較短的底線：
存在任意 NP 語句的零知識知識證明（特別是向 SHA256 證明原像的知識）
- 微小的資訊流（例如總共768 位，與語句的大小無關）
- 最少的互動（單輪，假設所有各方都可以使用全域可信參考字元串）
- “可實施”的具體效率（例如，那些證明系統已經實施、使用，並且在足夠簡單的陳述上具有合理的性能）
- 獎勵點：這些證明系統（通常是 SNARK）有一個很小的驗證者計算（甚至比在給定見證人的情況下檢查陳述是否真實更短！）
然而，這些“最優特性”通常是有代價的：高證明者計算。證明者成本通常是“漸近合理的”（例如，在檢查語句的電路大小上是準線性的），但具體而言非常高（涉及大常數）。因此，在實踐中，最常見的情況是人們寧願放棄其中一些最優特徵，以換取更合理的證明者成本。例如，NIST 候選後量子簽名Picnic v2使用了來自 MPC-in-the-head（ZKBoo 所屬的工作線）的 ZK 證明工作線的最新進展，這導致了線性證明電路的大小，但更好的計算成本。也有權衡，比如Ligero，具有“中等”證明者成本，以及大型實例上的較小證明大小（電路大小的平方根）。
**附加說明：**這與您的問題完全正交，但是由於您明確提到 SHA256，您可能有興趣知道有一些重要且富有成果的工作線追求相反的方向：建構新的候選抗碰撞雜湊函式（或塊零知識友好的密碼，流密碼等），從某種意義上說，它們的結構是針對一些現有的零知識證明系統量身定制的，並尋求優化這些原語的證明效率。標準範例包括 LowMC、Rasta、Trivium、Kreyvium 等。例如，Picnic NIST 候選簽名方案實際上是對基於 LowMC 的散列函式的原像的知識證明。
以下是問題的詳細答案。
雙向的必要資訊流、交換次數和機率是否有明確的下界？ $ \varepsilon $ 得出錯誤的結論？
這是一個深刻而廣泛的問題。讓我把它切成小塊。
交易所數量是否有明確的下限？
以下內容也應該回答您的最後一個問題：
獨立地，這樣的證明是否可以是非互動式的（成為一個靜態證明，證明 m 散列到 ℎ 的知識被用於製作證明，而沒有說明證明的來源或新鮮度）？
我在這裡對這個問題給出了部分答案。如果我們假設各方可以訪問一些公共參考字元串（CRS），在協議開始之前誠實生成並提供給所有各方，或者如果我們考慮純模型中的零知識（我們不要假設 CRS 或任何其他信任假設）。引用我的回答：
沒有 CRS： « 假設只有單向函式，我們需要非常多的輪次才能獲得 NP 的零知識證明。進一步假設存在抗碰撞雜湊函式，我們可以為 NP 建構五輪零知識證明。這本質上是我們所希望的最好的：在黑盒模擬下，NP 的 4 輪零知識證明會破壞多項式層次結構（但存在一些基於奇異假設的候選構造，例如指數知識假設或無密鑰多重衝突抗性雜湊函式，具有非黑盒模擬）。即使使用非黑盒模擬，NP 的 3 輪 ZK 證明也會打破不可區分性混淆. 此外， BPP 之外的語言根本不存在2 輪 ZK 證明。»
使用 CRS： « 在標准假設（例如因式分解）下，NP 中的每種語言都有一個非互動式（1 輪）零知識證明。»
因此，如果沒有 CRS，2 輪是沒有希望的，3 輪似乎不太可能；對於 CRS，在標准假設下一輪就足夠了。
（注意事項：為簡單起見，我沒有區分常見的參考字元串和常見的隨機字元串；如果想深入研究這些表徵的全部細節，這種差異很重要，但對於高水平來說並不完全重要概述）。
雙向的必要資訊流是否有明確的下界？
一個微不足道的下限是達到健全性錯誤 $ \varepsilon $ ，證明者消息的總長度必須至少為 $ \log(1/\varepsilon) $ ：根據零知識屬性，必須存在一個消息序列導致驗證者接受，即使證明了錯誤的陳述（否則，我們無法模擬），並且僅僅猜測這個序列已經與健全性錯誤界限相矛盾，如果總長度小於 $ \log(1/\varepsilon) $ .
事實上，我們不能做得更好——因為我們知道零知識證明的資訊流非常小。比語句本身的大小要小得多。更確切地說：
互動設置： 在互動設置中，假設抗碰撞雜湊函式，每個長度- $ n $ NP 中的陳述可以僅使用零知識證明 $ O(\log n) $ 位的總溝通。這就是著名的Killian 協議。
非互動設置： 在非互動設置中（一輪溝通，但我們假設一個CRS，這是必須的），這個比較亂。在隨機預言機模型中，您可以應用Fiat-Shamir 啟發式算法並使 Killian 的協議非互動式。這為您提供了一個啟發式候選非互動式零知識論證 (NIZK) $ O(\log n) $ 溝通。
但我們可以做得更好！
- 假設一個特定且非常強大的“指數知識”假設，NP 中的任何語句都存在一個 NIZK 證明系統，總共通信4 個組元素- 即任何語句的總通信量為 1024 位（假設 256 位橢圓曲線）。
- 在通用組模型中（在標準模型中給出了啟發式結構），我們甚至可以更進一步，只有三個組元素（768 位）。
- 我們還能再低一點嗎？單個元素是不可能的（在將組視為黑盒的模型中）。據我所知，2組元素是開放的。
- 最終，假設不可區分混淆（iO）這個非常強的概念，我們可以在指定驗證者設置（允許驗證者擁有一個秘密密鑰來檢查證明）中實現最佳的小 NIZK：在 iO 下，有一個指定的-實現健全性的驗證者NIZK $ 1/2 $ 與一位通信（因此，通過並行放大，它實現了健全性錯誤 $ \varepsilon $ 與通信 $ \log(1/\varepsilon) $ ）。由於 iO 是完全低效的，因此這種構造僅具有理論意義。
**總結：**在強假設下並假設一個 CRS，我們可以同時擁有最少的溝通和最少的互動。
目前的實現距離這有多遠？
這取決於您希望系統的計算效率如何——即，您是否願意為小型通信付費？
- 具有恆定大小證明的簡潔的非互動式知識證明 (SNARK) 已實現且可用。這是一個例子；但由於 SNARK 用於重要的應用程序，例如加密貨幣 zcash，因此可能有十幾個可用的實現。許多人應該實現恆定大小的證明，總共 768 或 1024 位。
- 然而，上述解決方案通常在證明方的計算上非常繁重（甚至沒有提到它依賴於相當極端的假設）。如果你想要更好的計算效率，通常會用它來換取證明大小，並依賴具有更大證明（但證明者計算量更小）的證明系統。ZKBoo 是一種可能的選擇，但它不再是最先進的。這方面工作的最新成果是Katz 等人的方案，它通過引入新技術來改進這些證明系統所依賴的 MPC-in-the-head 範式來改進 ZKBoo 和 ZKB++。在計算您關心的函式（在您的情況下為 SHA256）的布爾電路中，所得證明的大小仍然是線性的，但常數更小，穩健性誤差更好。這個結果是最新版 Picnic NIST 候選後量子簽名方案Picnic v2的基礎. 這個候選已經完全實現、優化和基準測試，你應該在他們的詳細規範中找到你想要的所有數據。（快速說明：以上所有內容都被描述為 NIZK，但他們所做的實際上是建構一個互動式零知識證明系統，然後使用 Fiat-Shamir 啟發式使其非互動式和啟發式安全）。
- 在 SNARK 和 Picnic 之間還有許多其他權衡。在這裡，我可以提到十幾個候選人（Aurora、STARKs……）。一個特別有趣的“中間點”是Ligero：它達到了證明大小 $ O(\sqrt{|C|}) $ ( $ C $ 作為布爾電路計算 SHA256，在您考慮的具體情況下），以合理的計算成本。實際上，該協議被用作為去中心化匿名加密貨幣提供解決方案的公司的基礎。
回答評論中的問題
我不明白的一件事是哪些技術會將 SHA-256 編碼為布爾 SAT 問題，或者是否（以及如何以及在何種程度上）利用規律性至關重要。根據那裡的第 5.1 節，可以免費提供很多 XOR 或很多 32 位加法。這很重要，因為我可以將 SHA-256 的大小近似為 3-SAT，但我不明白這是否相關。
是的，理論密碼學家傾向於忘記將您的實例編碼為 ZK 證明所基於的適當模型的“實際”問題：) 但這裡有一些細節：
- 從 MPC-in-the-head 技術（ZKBoo、ZKB++、Picnic、Picnic v2）建構的協議基本上可以從任何“MPC 風格”優化中受益。MPC 協議的變體太多，無法涵蓋每一個細節，但一個好的經驗法則如下：MPC 將處理布爾電路或算術電路。XOR 或加法不會花費任何費用。預設的“成本”是 AND 或乘法的數量。如果你的函式寫得很好，是算術和布爾運算的混合體（如 XOR、AND 和加法 $ \mathbb{Z}_{32} $ )，那麼您可以使用為有效評估這些操作而量身定制的 MPC 協議。但是我不能預設告訴你什麼是最好的選擇：這取決於目前的 MPC 文獻，每年有數百篇新論文。如果我以 Picnic 簽名方案為例，他們使用 MPC 協議，當電路是布爾電路時特別有效，具有 XOR 和 AND 門，具有任意數量的 XOR 門，但與門盡可能少。這就是為什麼他們用另一個散列函式 LowMC 替換 SHA256 的原因，LowMC 選擇最小化其布爾電路中與門的數量。
- 實現最小證明大小的 SNARK 依賴於不同的表示：二次跨度程序。因此，要獲得 SHA256 的 SNARK，您必須首先將 SHA256 編碼為二次跨度程序。我不知道這樣做的效率如何，但它已經完成了：SHA256在 libsnark 中實現。
- Ligero 依賴於將函式（例如 SHA256）表示為算術電路。然後，對於電路的每個門，根據門的類型，將一個約束添加到某個約束列表中，並在此表示之上建構一個“互動式 PCP”作為約束列表。至於 ZKBoo 等，他們可以通過不分解加法來獲得更好的結果 $ \mathbb{Z}_{32} $ 作為 XOR 和 AND，但通過將這些環加法直接視為單獨的約束（參見Ligero 論文，第 2100 頁）。SHA256 在他們的論文中被明確用作基準：它們的證明大小為 34kB，證明者執行時間為 140 毫秒，驗證者執行時間為 62 毫秒。
在全球範圍內回答您問題的第一部分：
我不明白的一件事是哪些技術會將 SHA-256 編碼為布爾 SAT 問題，或者是否（以及如何以及在何種程度上）利用規律性至關重要。
所有技術都可以“僅”將 SHA256 編碼為正確的表示形式（布爾電路、算術電路或二次跨度程序）。所有具體的實現都將嘗試盡可能多地優化這種表示，例如通過找到一種直接處理 SHA256 中涉及的環操作的方法。不幸的是，人們通常不會將“幼稚、無腦”的表示與優化的表示一起實現，因此很難估計不優化表示的成本是多少。但只是給出一個非常粗略的感覺，天真地僅使用 XOR 和 AND 表示 SHA256 可以提供比以更聰明的方式處理環加法時大兩個數量級的表示。