什麼是 SNARK？
它是什麼意思，它的用途是什麼，我最近經常聽到這個詞。
從我聽說過的上下文來看，它似乎與零知識有關？
我假設你熟悉 $ P $ 和 $ NP $ . 此外，我對 SNARK 的了解主要基於Parno 等人的工作。，其他工作可能在一些細節上有所不同。
因此，SNARK 是一種簡潔的非互動式知識論證。暫時將“知識”部分放在一邊，讓我們看一下“普通”簡潔的非互動式參數（在上面連結的工作中稱為 SNARG）。參數是計算上合理證明的另一個名稱。您可能知道證明系統的健全性屬性是無法“證明”錯誤斷言（在所考慮的系統中）的屬性的技術術語。
傳統的非互動式證明系統具有“完美的健全性”，這意味著絕對不可能證明虛假陳述。例如，給定一個 $ NP $ -語言 $ L $ , 如果證明者想向驗證者證明某個詞 $ x $ 在 $ L $ ，他可以簡單地出示一個證人 $ w $ 為了 $ x $ . 然後，驗證者將接受輸入 $ (x,w) $ 並確信 $ x $ 確實在 $ L $ . 另一方面，如果 $ x $ 實際上不在 $ L $ , 它沒有任何 $ NP $ - 證人，因此驗證者將始終拒絕任何聲稱的證人 $ w $ 為了 $ x $ . 這在安全意義上是非常好的：驗證者可以確定惡意的證明者永遠不會欺騙它相信一個陳述是真實的，而實際上它是錯誤的。然而，問題在於，一個 $ NP $ 見證人不能太小（如果我們允許 $ NP $ 證人太小，那我們就“縮水” $ NP $ 到它比通常認為的要小）。
具有完美可靠性的證明系統讓人想起具有完美保密性的密碼系統，例如一次性密碼：即使是具有無限計算能力的對手也無法“破解”它們（對於密碼系統，這意味著解密消息；對於證明系統，這意味著證明虛假陳述）。然而，為如此強大的安全性付出的代價是效率損失，這通常被認為對於此類系統而言太高而無法實用。出路是認識到在實踐中不存在具有無限計算能力的對手。我們並不真正關心這樣的對手是否會破壞我們的系統，如果沒有有效的對手（即，沒有在多項式時間內執行的對手）可以以不可忽略的機率破壞我們的系統，我們會感到滿意. 而且，就像密碼系統一樣，以這種方式放寬我們的要求可以讓系統更有效率：在 Parno 等人的工作中。證明是恆定大小的，而傳統的 $ NP $ 證人在聲明的大小中有大小多項式。
最後，一個簡潔的非互動式論證 $ NP $ -語言 $ L $ 是一個非互動和計算健全的證明系統 $ L $ 證明簡潔的地方。Parno 等人在不同的作品中對後一個術語的定義可能略有不同。將其定義為“安全參數中的多項式”。這樣的證明系統由三種算法組成 $ \mathsf{Gen} $ （密鑰生成）， $ \mathsf{P} $ （證明），和 $ \mathsf{V} $ （驗證）：
- $ \mathsf{Gen} $ 通常由驗證者執行。它作為輸入 $ 1^k $ ( $ k $ 作為安全參數）並輸出一些密鑰對， $ \mathsf{priv} $ 和 $ \mathsf{pub} $ .
- $ \mathsf{P} $ （證明算法）作為輸入 $ \mathsf{pub} $ ， 一個字 $ x \in L $ 和一個 $ NP $ -見證 $ w $ 為了 $ x $ ，並輸出證明 $ \pi $ .
- $ \mathsf{V} $ （驗證算法）作為輸入 $ \mathsf{priv} $ , $ x $ 和 $ \pi $ , 並返回 $ 0 $ 或者 $ 1 $ 取決於驗證者是否“接受”證明 $ x $ 在 $ L $ .
系統必須滿足以下三個屬性（我在這裡非正式地陳述）：
- **完美的完整性：**如果 $ x $ 在 $ L $ 和 $ w $ 是一個 $ NP $ - 見證 $ x $ , 那麼證明 $ \pi $ 證明者在輸入時產生 $ (x,w) $ 將始終被驗證者接受。
- **簡潔性：**長度 $ \pi $ 是多項式在 $ k $ . 請注意，這個多項式是通用的，並且可能不依賴於實例的長度（即， $ |x| $ ), 語言 $ L $ , 或定理 $ x\in L $ 被證明。
- **計算穩健性：對於在輸入上執行的任何多項式時間對手 $ (1^k,\mathsf{pub}) $ 並產生一對 $ (x,\pi) $ , 的機率 $ x $ 不在 $ L $ 那_ $ (x,\pi) $ 被接受 $ \mathsf{V} $ 可以忽略不計 $ k $ .
最後，什麼是簡潔的非互動式知識論證（SNARK）？如果您注意以上內容，驗證者返回的事實 $ 1 $ 在一些輸入 $ (x,\pi) $ 僅證明 $ x $ 在 $ L $ ，但不排除證明者生成該對的可能性 $ (x,\pi) $ 以非標準的方式，不知道 $ NP $ - 見證 $ x $ . SNARK 通過要求一個額外的屬性來做到這一點：
- 可提取性：適用於任何多項式時間證明者 $ \mathsf{P}^* $ 在輸入上執行 $ (\mathsf{pub},z) $ （在哪裡 $ z $ 是一些輔助輸入）並產生一對 $ (x,\pi) $ , 有一個多項式時間提取器 $ \mathcal{E}_{\mathsf{P}^} $ 也在輸入上執行 $ (\mathsf{pub},z) $ 和生產 $ w $ , 這樣的機率 $ (x,\pi) $ 被驗證者接受並且* $ w $ 不是一個 $ NP $ - 見證 $ x $ 可以忽略不計 $ k $ .
非正式地，可提取性屬性表示對於任何需要一些輸入的算法 $ z $ 並產生一個有效的對 $ (x,\pi) $ ，有一個提取器算法，它採用相同的輸入並輸出 $ NP $ -見證 $ w $ 為了 $ x $ . 因此，我們認為第一個算法“知道” $ w $ ，因為可以計算 $ w $ 僅有效地使用第一個算法已知的數據。