前言

在區塊鏈背景下，zk-SNARK 是一種先進的安全技術，可以增強隱私並確保加密交易的透明度。

Zk-SNARK 允許在不泄露知識的情況下證明知識，從而保證用戶信息的絕對保護。

Zcash 是領先的加密貨幣，採用 zk-SNARK 技術實現交易完全匿名化，確保高安全性，不暴露用戶個人信息。這提高了用戶進行在線交易時的安全性和可靠性。

在“探索 ZK-SNARK”研究系列的第 1 部分中，我將深入探討有關 zk-SNARK 的重要細節以及該技術背後的底層算法和加密，非常詳細且易於您理解。

zk-SNARK 的概念和作用機制

zk-SNARK 基礎知識

Zk-SNARK的全稱是Zero-Knowledge Succinct Non-Interactive Argument of Knowledge，大致翻譯爲“Concise and non-interactiveproof of non-knowledge discovery”（我這樣翻譯是爲了更容易理解）。這是一種證明結構，允許一方（證明者）證明其擁有某些信息，例如密鑰，而無需透露該信息，也不需要與另一方（驗證者）合作。

目前，zk-SNARK 是最流行的證明系統。

我們將把首字母縮略詞“zk-SNARK”分解成更小的組成部分，以最清楚地檢查它們的含義。

  • “零知識”：這意味着輸入信息將被隱藏，不會透露給驗證者。換句話說，驗證者無法知道有關該知識的任何信息，只能知道其有效性。

  • “Succinct”（短）：這意味着生成的證明很小，大約幾百字節，並且驗證很快。這是SNARK帶來的第一個好處。

  • “非交互”：這是 SNARK 的第二個好處，雙方（證明者和驗證者），證明由從證明者到驗證者的單個消息組成，無需來回通信。

  • “知識論證”：是一個技術術語，意思是如果驗證者接受證明，那麼證明者必須實際上知道與被驗證的聲明相關的祕密（而不僅僅是讓驗證者相信該陳述是真實的）。

作用機制

從數學上講，zk-SNARK 由 3 種算法組成：

  • 密鑰生成（KG）：這是一種密鑰生成算法，它將生成一對密鑰，一個用於證明（pk），一個用於驗證（vk）。密鑰生成算法將安全參數 λ 和 C 程序作爲輸入，然後輸出密鑰。此步驟也稱爲可信設置步驟。我們將在下面的部分詳細介紹它。(pk, vk) = KG(λ, C)

  • 證明（P）：該證明算法將通過輸入證明密鑰 pk、陳述 x 和證人 w 來進行證明。輸出是證明 prf.prf = P(pk, x, w)

  • 驗證（V）：驗證算法將驗證密鑰 vk、語句 x 和證明 prf 作爲輸入。輸出是接受或拒絕。

驗證結果 = V(vk, x, prf)

ZK-SNARK 的優點

  • ZK-SNARK 帶來了許多重要的好處，特別是在增強各種應用程序的匿名性、安全性、可擴展性和交易效率方面。以下是軟件應用程序的 2 個主要優勢：

    1. 隱私：“零知識”屬性允許隱藏與計算相關的敏感數據，同時仍然證明語句的正確性。換句話說，zk-snark 在不泄露個人信息的情況下進行交易，保持交易信息的匿名性和安全性。這在 Zcash 等加密貨幣中非常有用，用戶可以在不透露交易金額、來源或目的地的情況下發送資金。

    2. 可擴展性：由於證明大小小，驗證時間短，驗證者可以快速知道計算是否忠實執行，而無需重新運行計算，從而減少驗證複雜計算所需的時間和資源，從而提高系統性能和可靠性，同時還有助於降低成本並增強其可擴展性。

值得信賴的設立儀式

信任建立過程是一個重要步驟，只需執行一次即可生成一組必要的數據，以便以後每次部署加密協議時使用。

在 ZK-SNARK 中，此信任設置步驟對於生成證明和驗證密鑰是必要的。然後將這些密鑰公開，允許參與者使用它們來創建和驗證證據。

對於每個新的 C 程序，需要執行新的可信設置，因爲它取決於該 C 程序的詳細信息。在設置過程中，KG 密鑰生成過程使用祕密 lambda 和 C 程序作爲輸入來生成公鑰 (pk) 和驗證密鑰 (vk)。

（pk，vk）= KG（λ，C）

因此，可靠的設置過程不是標準的，應該針對每個新程序單獨進行。

有毒廢物（有毒廢物）

可靠的設置需要一個名爲 lamda 的祕密參數。這個參數通常被稱爲“有毒廢物”，有時會導致 zk-SNARK 難以應用於實際應用。

這是因爲，誰掌握了這個參數，就有能力製造假證據。具體來說，lambda 持有者可以爲任何具有公共輸入 x 的 C 程序生成一個名爲 fakeProof 的假證明，這樣

V（vk，x，fakeProof）= true

在不知道祕密證人 w 的情況下被判定爲真實。這是災難性的！

爲 zk-SNARK 生成公共參數的最有效方法是通過某人生成公鑰和私鑰對（類似於 ECDSA 密鑰對），然後銷燬私鑰。但令人擔憂的是，如何確定這邊確實消除了那些“有毒廢物”？

因此，爲了解決這個問題，應用了多方計算（Multi-Party Computation，MPC）。

MPC 是一種加密協議，允許多方參與分佈式計算，而任何一方都無法訪問另一方的機密數據。

在每個信任建立過程中，多方共同參與該過程以生成必要的加密組件，例如公鑰（pk）和驗證密鑰（vk）。各方都爲此過程貢獻了部分機密數據。

此過程後各方的最終目標是徹底消除有毒廢物。這種情況下的可靠性假設是，只要 n 個參與者之一是誠實的，最終結果就保證是安全的。

在信任設置期間，n 方中的每一方都會攜帶其祕密 lambda 來共同生成證明和驗證密鑰。

爲了讓這個設置失敗，需要所有 n 方都懷有惡意並互相分享他們的祕密。然而，只要其中一方決定不泄露其祕密，信託的建立過程仍然會成功，從而不可能產生虛假證據。

zk-snark 背後的數學和編碼

數學基礎

羣論

ZK-SNARK 利用羣論對橢圓曲線和其他羣進行計算，特別是在使用雙線性配對和相關算法時。

簡單地說，羣就是一組元素{a,b,c,…}結合二元運算，這裏用“•”表示。

如果集合和運算滿足以下屬性，則稱爲羣：

  • 閉包：對於組 G 中的所有 a 和 b，運算 a • b 也必須在 G 中。

  • 結合性：對於 G 中的所有 a、b 和 c，運算 (a • b) • c 必須等於 a • (b • c)。

  • 單位元素：G 中必須有一個元素 e，使得對於 G 中的每個元素 a，操作 e • a 和 a • e 等於 a。這個元素是獨一無二的。

  • 逆元素：對於 G 中的每個元素 a，G 中必須有一個元素 b，通常稱爲 a^-1，使得操作 a • b 和 b • a 等於來自單元 e 的操作。

子羣

當羣中元素的子集服從該羣的所有屬性時，該集合稱爲原羣的子羣。

字段

域是一種特殊的代數結構，其中一組元素執行兩個基本運算：加法和乘法。每個領域都必須遵守一系列基本公理，這些公理定義並保證了其一般屬性。

以下是域必須滿足的公理，其中 a、b 和 c 是域 F 的任意元素：

  1. 加法和乘法的結合性：a + (b + c)= (a + b) + c 且 a · (b · c) = (a · b) · c

  2. 加法和乘法的交換律：a + b = b + a 和 a · b = b · a

  3. 加法和乘法方程：F 中存在兩個不同的元素 0 和 1，使得 a + 0 = a 和 a · 1 = a

  4. 加法逆元：對於 F 中的每個 a，F 中都存在一個元素，表示爲 -a，稱爲 a 的加法逆元，使得 a + (−a) = 0

  5. 乘法逆元：對於 F 中的每個 a≠ 0，F 中存在一個元素，表示爲 a^ -1，稱爲 a 的乘法逆元，使得 a · a^ -1 = 1

  6. 乘法相對於加法的分佈：a· (b + c) = (a·b) + (a·c)

字段的示例包括具有加法和乘法的實數集，以及以素數爲模的整數，其中定義了加法和乘法。

有限域

在 ZK-SNARK 中，所有運算都在有限域中執行，其中值和運算以素數爲模或基於素數多項式定義。

有限域是具有有限數量元素的域，例如以 p 爲模的整數集，其中 p 是素數。

對於有限域，域中元素的數量（稱爲域的階）可以是：

  • 一些素數（素數域）

  • 或者素數的冪（擴展域）

在簡單素數域中，元素可以用 0 到 p-1 之間的整數表示，其中 Zp = {0, 1, …, p-1}。

Zp 的擴展稱爲乘法羣 Zp*，由與 p 互質的元素組成，即 Zp* = {1, …, p-1}。

有限域生成器

在每個有限域中，都存在一個稱爲生成器的元素，它能夠使用其求冪生成羣中的所有元素。

例如，考慮素數域中的羣 Z5* Z5 = {0, 1, 2, 3, 4}，則 Z5* = {1, 2, 3, 4}。 在 Z5* 組中，乘法是二元運算，並且乘法以模 5 執行；例如，乘以 3 × 4 不會得到 12，而是得到 2，因爲 12 mod 5 = 2。

羣 Z5* 是循環羣並具有生成元 2 和 3，因爲：

  • 對於生成器 2，我們有：

2^0=1，

2^1 = 2，

2^2=4，

2^3=3，

2^4 = 1（重複循環）

  • 對於生成器 3，我們有：

3^0=1，

3^1 = 3，

3^2=4，

3^3=2，

3^4 = 1（重複循環）

這些屬性使 Z5* 成爲一個強大的加密操作組，並且通常用於 ZK-SNARK 等加密算法中。

羣同態

同態是兩個相似的代數結構（例如羣或域）之間的映射，並且它們保留該結構內的運算。

具體來說，同態是從 A 組到 B 組的映射 f，當這兩個組具有相同的二元運算（例如乘法或加法）時。此映射保留了操作，這意味着：

如果 ⋅ 是 A 組和 B 組結構中的二元運算，則對於 A 組中的每個元素 a 和 b，映射 f 滿足條件：

f ( x ⋅ y )= f ( x )⋅ f ( y )

這確保了應用於組 A 中的元素的運算結果在通過 f 映射到組 B 後，仍然與直接對組 B 執行的運算相同。

同態是處理雙線性對屬性的基礎，使得 zk-SNARK 中生成和驗證證明的過程更加高效。

多項式

多項式是構建二次算術程序 (QAP) 的核心組成部分，其中問題通過多項式表示並通過多項式評估和承諾來解決。

多項式是由變量和常數組成的數學表達式，使用加法、乘法和非負整數指數求冪。

例如，多項式 5x² + 2x + 8 就是一個很好的例子。

當考慮多項式方程時，它可以表示數字之間無數個不同的方程。例如，如果方程 A(x) + B(x) = C(x) 成立，那麼它對於 x 的所有值也成立，例如：

A（0）+B（0）=C（0）

A（1）+ B（1）= C（1）

A（2）+B（2）=C（2）

A（3）+B（3）=C（3）

等等。

關於多項式的次數，由多項式中變量的最大冪決定。例如，多項式 6x⁴ + 2x³ + 3 的次數爲 4，因爲變量 x 的最高次方爲 4。

密碼學

哈希函數

哈希函數廣泛用於在加密協議中創建“承諾”，有助於確保數據無法在未經檢測的情況下被修改。

哈希函數是一種算法或數學函數，可將可變長度的輸入數據字符串轉換爲固定長度的輸出字符串（稱爲哈希值）。

哈希函數表示公式可以描述如下：

f（米）= H

其中 f 是哈希函數，m 是消息，H 是結果哈希值。

哈希函數具有許多重要的屬性，使其在許多密碼應用程序中非常有用。這些屬性包括：

  • 原像抵抗：從數學上講，從哈希值中檢索原始消息非常困難。

  • 第二個原像抵抗：給定一個特定的輸入消息及其哈希值，很難找到另一個產生相同哈希值的消息。

  • 抗碰撞性：很難找到產生相同哈希值的兩個不同消息。

好的哈希函數的一個非常理想的特性是雪崩效應。 這是輸入的微小變化會導致輸出發生較大變化的特性，使輸出顯得隨機且難以區分。

加密

簡而言之，加密是將輸入消息（明文）轉換爲看似隨機的輸出（密文）的過程，以便只有授權人員才能解碼和理解該信息。加密基於密鑰的使用，密鑰是發送者和接收者用來加密和解密信息的一組數學值。

加密算法有兩種類型：對稱加密和非對稱加密。

對稱加密

在對稱加密中，通信過程中涉及的所有各方都使用相同的密鑰來加密和解密消息。該密鑰在雙方之間保密，以確保交換信息的安全。

非對稱加密

在非對稱加密（也稱爲公鑰加密）中，有兩種類型的密鑰：用於加密的公鑰和用於解密的私鑰。私鑰由接收者保密（因此稱爲“私鑰”），而公鑰可以與任何想要發送機密信息的人廣泛共享（因此稱爲“私鑰”）。

非對稱加密廣泛應用於以下幾種情況：

  • 發送安全消息：發送者使用接收者的公鑰對消息進行加密，然後將其發送給接收者。只有擁有私鑰的接收者才能解密並讀取消息。

  • 證明私鑰的所有權（瞭解）：在證明私鑰所有權的過程中，發送者使用其私鑰對消息進行加密（或簽名），然後將其發送給接收者。接收者使用發送者的公鑰來解密消息。此過程通常稱爲數字簽名，如此加密的消息稱爲“數字簽名”。由此，數字簽名證明該消息是由擁有相應私鑰的人發送的，並且還有助於驗證消息中信息的完整性。

同態加密（Homomorphic crypto）

同態加密在高級零知識證明的設計中具有很大影響力，因爲它允許對加密數據進行計算而無需解密它們。

同態加密是一種特殊類型的加密，允許直接對加密數據執行計算。這意味着可以對加密數據執行額外的計算，而無需密鑰。這些計算的結果保持加密狀態，確保安全性，而不會泄露原始數據內容。

在實踐中，允許對加密數據進行各種任意計算的全同態加密仍然存在很多侷限性，尚未得到廣泛應用。然而，對同態結構進行某些操作是可行的，並且已經在實際應用中得到應用。

這些操作包括加密數據的加法和乘法，這爲無需解密的安全數據處理開闢了新的可能性。

橢圓曲線密碼術 (ECC)

在 ZK-SNARK 中，由於實現雙線性配對的分組操作，橢圓曲線發揮着重要作用。 ECC（橢圓曲線密碼學）提供了一個用於創建和驗證零知識證明的高效平臺。

橢圓曲線是滿足特定數學方程的一組點。橢圓曲線的方程具有以下形式：

其中，a和b是已知常數。該方程的圖形如下所示：

橢圓曲線有許多不同的表示形式，但該技術主要是尋找滿足特定數學方程的點。

橢圓曲線的特性使其在許多數學領域，尤其是密碼學領域非常重要。

橢圓曲線的一個有趣的特性是它們的水平對稱性。曲線上的任何點都可以反映在 x 軸上，同時保持曲線完整。這意味着，如果您在曲線上取任意兩點並通過它們畫一條線，該線將在第三個點處與曲線相交。

想象一下這是一場檯球遊戲，球從一個點射出，當它擊中橢圓曲線時，它會垂直向上或垂直向下彈起，具體取決於它相對於 x 軸的位置。

橢圓曲線的一個有趣的特性是，您可以在曲線上“點”兩個點來創建一個新點。您還可以連續“點”一個點以在曲線上創建不同的點。

但有趣的是，如果你知道終點和起點，計算從起點到終點所需的“點”數量是非常困難的！

想象一下一個人在一個房間裏獨自玩耍，按照遊戲規則擊球。然後其他人進來看看球的最終位置。即使他們知道初始位置和比賽規則，如果不從頭開始回顧整個比賽，他們也無法知道球被擊中了多少次。這在密碼學中創造了一種特殊的屬性，稱爲不可逆性，並且是許多強大應用程序（例如陷門函數）的基礎。

橢圓曲線上的離散對數是一個難題，它支撐着基於橢圓曲線的密碼學。與分解不同的是，沒有捷徑可以解決這個問題，這使得破解橢圓曲線密碼學比使用 RSA 和 Diffie-Hellman 更難。

雖然 ECC 通過較短的密鑰提供了高級別的安全性，但它在低功耗設備上仍然保留了良好的性能。這使得 ECC 成爲資源有限的移動設備和系統上的加密應用程序的理想選擇。

在本節的最後，我闡述了 zk-SNARK 背後的一些基本數學和編碼概念，在下一部分中，我將詳細闡述更高級的概念，例如二次算術程序、橢圓曲線配對。

感謝您閱讀本文。如果您喜歡這篇文章，別忘了關注並留下掌聲。

文章來源：團隊技術/研究 – AlphaTrue

參考來源：

1.來源​​：Reitwiessner，C.（2016）。簡而言之，zkSNARKs。以太坊博客，6，1-15。https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf

2. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-7-61d639c2ef02

3. https://celo.academy/t/zk-snarks-proofs-as-a-privacy-solution-on-the-blockchain/1961

4.來源：Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022)。zk-snarks 綜述。arXiv 預印本 arXiv:2202.06877。https://arxiv.org/pdf/2202.06877.pdf

5. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-8-262f923f1537

6. https://medium.com/@hira.siddiqui/from-zero-to-hero-in-zero-knowledge-proofs-part-2-ef17ce470f2d

7. Easttom, W. (2022). 現代密碼學：加密和信息安全的應用數學。Springer Nature。

8. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/