前言
在上一部分中，我們基本瞭解了 zk-SNARK 背後的數學和密碼學基礎。現在我將繼續深入研究更新且相當複雜的概念，以便您可以更深入地瞭解 zk-SNARK 背後的技術！
算術電路（算術電路）
運算電路的概念
算術電路是有向無環圖 (DAG)，或者簡單地說，有向無環圖，由以下部分組成：
節點充當加法門和乘法門。
邊緣代表建立在有限場 Fp 上的導體。 一根電線將一個端口的輸出連接到另一個端口的輸入。每個端口有兩個輸入和一個輸出。
算術電路以最終輸出結束。上圖展示了一個算術電路的示例，我們可以看到數據如何被處理並通過每個門以產生最終結果。
算術電路告訴我們 zk-SNARK 如何處理和證明計算，而不透露任何信息。算術電路可以用圖表來描述，其中包含系統排列的算術運算。
算術電路的運算
考慮上圖，算術電路允許我們計算
查看上圖，我們看到該過程從第一個內核門開始，該內核門接收 s1 和 s2 作爲輸入，並生成 s4 作爲輸出。接下來，s4 和 s3 被輸入到第二個內核門以產生最終輸出 s5。
對於 m 端口、n 線電路，我們將確定
見證人 s = (s1, s2, s3,…, sn)
分配給電路的n條線，使得每個門的輸入和輸出滿足由門的操作確定的約束。
一個 m 門、n 線運算電路確定見證人之間的關係
s = (s1, s2, …, sn)
這樣對於一個常數
然後
上述約束屬於一組 m rank-1 約束，其目的是模擬算術電路中乘法器門的輸入和輸出之間的關係
特定的 1 級約束的一個示例是 Eq
s1 。 s2 – s3 = 0。
該方程描述了電路中的乘法器門，它接受兩個輸入 s1 和 s2，然後產生輸出 s3。 因此，s1 和 s2 的乘積必須等於 s3 才能滿足方程。
像這樣的一組 m 個 1 級約束可以概括爲二次算術程序。
QAP 是一種工具，用於將算術電路轉換和簡化爲更容易驗證操作而無需重新渲染整個電路的形式。
二次算術程序
zk-SNARK 的核心在於二次算術程序（QAP）。 QAP 可以代表任何算術電路，包括加法門和乘法門。基於 QAP，證明者可以證明他知道輸入值，而無需透露有關該值或程序內部行爲的任何信息。
zk-SNARK研究員Eran Tromer從基本數學原理出發，得出了zk-SNARK構建流程如下：
上面的步驟可以分爲兩半。在本文中，將深入解釋該過程的“前半部分”。該過程的“前半部分”可以認爲是從“計算”到“QAP”的步驟，這是將初始計算轉換爲可用於建立 zk-SNARK 的數學形式的部分。
我將用最容易理解的方式解釋如下：
在我們可以使用 zk-SNARK 解決任何計算問題之前，我們必須將問題轉換爲合適的“形式”。這種形式稱爲 QAP，即“二次算術程序”。
一旦我們將問題轉換爲 QAP，我們將繼續通過一些特定的輸入來解決它。找到的解決方案稱爲“見證”。這就像我們解決完一個謎題並知道答案一樣。
現在我們有了答案，我們需要創建一種方法來證明我們知道答案而不透露答案。這個過程創建了一個“非泄露證據”，這意味着它允許我們證明我們知道答案，而不必說出來。
最後，其他人可以使用單獨的過程來檢查我們創建的證據，以確認我們確實知道答案，而無需知道答案實際上是什麼！
例如：我們有以下等式：
x**3 + x + 5 == 37（建議答案爲 3）
我們將通過編寫一個簡單的計算機程序來證明我們知道上述數學方程的解，而不必揭示解，如下所示：
qevel 函數將計算方程 x**3 + x + 5 的值。當我們將數字 3 代入 x 時，函數將返回 35，這就是我們想要的結果。
然而，在這種情況下我們會看到編程語言的侷限性。該語言僅支持基本算術運算（+、-、*、/）和固定指數的冪（x**7，而不是 x**y）。它不支持餘數除法（%）或比較（>、<、≤、≥），因爲在有限循環羣算術中沒有直接執行取模或比較的有效方法。
這裏的解決方案是我們可以擴展該語言以支持其他操作，例如餘數除法和比較
例如：
如果 x < 5：y = 7；否則：y = 9
將它們轉換爲算術：
y = 7 * (x < 5) + 9 * (x >= 5)
您可以參考一個編譯器，該編譯器可用於將代碼轉換爲 vbuterin 實現的 zk-SNARK 可用的形式（僅用於教育目的；尚未準備好在實踐中爲 zk-SNARK 創建 QAP）
壓平
轉換爲這種形式的QAP的第一步是“扁平化”步驟，簡單來說，這是對編程代碼進行改造以使其更簡單的步驟，每行只執行一個基本操作。
在上面的示例中，初始計算機程序具有複雜的數學表達式。 “扁平化”過程將這個表達式分成小部分，每個部分只進行一個簡單的計算：
符號_1 = x * x
將 x 與其自身相乘以創建一箇中間值，稱爲 sym_1
y = 符號_1 * x
然後將中間值 sym_1 再次乘以 x 得到 y，按照精確計算 x^3
符號 2 = y + x
添加剛剛用 x 計算出的 y
~輸出 = sym_2 + 5
最後將 sym_2 加 5 得到最終結果，並在 out 前加一個 ~ 表示這是程序的最終結果。
非常容易理解！這種“扁平化”過程有助於準備要由 zk-SNARK 處理的代碼，因爲 zk-SNARK 要求編程代碼採用簡單的形式，可以輕鬆轉換爲它可以使用的數學形式。
通往 R1CS 的大門
接下來，我們將進行一系列的計算，將它們轉換成稍微複雜的形式，稱爲（rank-1約束系統），縮寫爲R1CS。
R1CS 是三個向量 (a, b, c) 的組序列，R1CS 的解是向量 s，其中 s 必須滿足以下方程：
s.a * s.b – s.c = 0
這將檢查輸出值是否是兩個輸入值的正確乘積。如果滿足所有這些條件，我們就有了系統的精確解向量。
我們可以看下圖來更好地理解R1CS：
首先，我們將定義系統中使用的變量，我將提供映射變量的步驟如下：
“~one”（第一個下標代表數字1）
“x”（輸入變量）
“~out”（輸出變量）
“sym_1”、“y”、“sym_2”（中間變量）
向量“s”將包含所有這些變量的值，按照定義的順序。
#我們將給出第一個門的三元組（a，b，c）（對於x * x乘法）：
向量 a 和 b 都包含值 [0, 1, 0, 0, 0, 0] 。每個向量中第二個位置的數字 1 表示將在計算中使用變量 x 的值。具體來說，該值與其自身相乘，因爲 a 和 b 都將權重放在位置 x 處
向量 c 的值爲 [0, 0, 0, 1, 0, 0] ，第四個位置爲數字 1，表示根據 a 和 b 計算出的值將與向量 s 中的變量 sym_1 進行比較
a = [0, 1, 0, 0, 0, 0] ：指定變量“x”參與計算。
b = [0, 1, 0, 0, 0, 0] ：再次指定“x”將與其自身相乘。
c = [0, 0, 0, 1, 0, 0] ：結果將存儲在變量“sym_1”中
當“x = 3”時，計算結果爲“3 * 3 = 9”，滿足約束“sym_1 = x * x”
#接下來是第二個門（用於 sym_1 * x 乘法）：
類似地，a = [0, 0, 0, 1, 0, 0]：指定“sym_1”（如果“x = 3”則爲9）
b = [0, 1, 0, 0, 0, 0] ：指定“x”（如果“x = 3”則爲 3）
c = [0, 0, 0, 0, 1, 0] : 結果將保存在“y”中
計算結果爲“9 * 3 = 27”，滿足約束條件
#接下來是第三個門（用於 x + y 加法）
相似的，
a = [0, 1, 0, 0, 1, 0] ：指定“x”和“y”
b = [1, 0, 0, 0, 0, 0] ：使用值“1”（代表“~one”），以便正確執行加法。
c = [0, 0, 0, 0, 0, 1] : 結果保存到“sym_2”
計算結果爲“3 + 27 = 30”，滿足約束“sym_2 = x + y”
#最後是第四個門（用於 sym_2 + 5 加法）：
相似的，
a = [5, 0, 0, 0, 0, 1] ：使用“~one”中的值“5”和“sym_2”中的值“1”
b = [1, 0, 0, 0, 0, 0] ：再次“~one”，以便正確執行加法。
c = [0, 0, 1, 0, 0, 0] : 結果保存到“~out”
計算結果爲“30 + (5*1) = 35”，滿足約束“~out = sym_2 + 5”
三列 A、B 和 C 對應於向量“a”、“b”和“c”。 C列底部的數字“35”是最終結果（“~out”）
比較 (s . a) * (s . b) 和 (s . c)，它們必須相等（它們的差必須爲 0）
此時，向量“s”將包含以下值：
1：這是虛擬變量 ~one 的值，它始終爲 1，表示常量 1。
3：這是輸入變量 x 的值。
35：這是期望的值，程序的最終結果（變量~out）。
9：x * x 的結果，存儲在 sym_1 中。
27：sym_1 * x 的結果，存儲在 y 中。
30：y + x 的結果，存儲在 sym_2 中。
最後，完整的R1CS拼湊起來如下圖：
R1CS 至 GAP
下一步是採用此 R1CS 並將其轉換爲 QAP 形式，但不是像 R1CS 那樣使用向量和點積
QAP 使用“多項式”，因爲它們具有特殊的數學屬性，可以使測試過程變得更容易。
拉格朗日插值是一種繪製經過一系列已知點的曲線（多項式）的方法。如果您有特定數量的點並且想要一條接觸所有這些點的曲線（多項式），拉格朗日插值將幫助您找到該曲線。
例如：假設我們想要一個經過 (1, 3)、(2, 2) 和 (3, 4) 的多項式。我們首先創建一個通過 (1, 3)、(2, 0) 和 (3, 0) 的多項式。
一種簡單的方法是計算 (x-2) 和 (x-3) 的乘積。該函數將具有曲線形狀，在 x=1 處上升並在 x=2 和 x=3 處切割水平軸。
如下：
現在，我們只需要“調整”它，使 x=1 處的高度正確：
這使得多項式和圖形將顯示如下：
然後我們對剩下的兩個點進行同樣的操作，得到另外兩個多項式，將三個多項式相加，得到：
原始算法需要 O(n^3) 時間來計算，因爲 n 個點中的每一個都需要 O(n^2) 來乘以多項式。然而，通過更聰明的思考，我們可以將這個時間減少到 O(n^2)。
應用 FFT 變換等算法，我們可以更快地減少計算時間，這對於具有數千個門的 zk-SNARK 等應用非常重要。
我們將應用拉格朗日插值來變換 R1CS，通過獲取每個向量 a 的第一個值，然後使用此插值爲每個向量創建多項式，以便在索引特定數字處評估多項式時，我們得到 a 的第一個值對應的向量。
對向量 b 和 c 的第一個值執行相同的操作，然後依次將此方法應用於每個向量的下一個元素。
我們將得到如下結果：
該算法使用一系列遞增係數來創建多項式：
該多項式是正在考慮的 QAP（二次算術程序）版本的參數的一部分。
需要注意的是，對於每個使用 zk-SNARK 驗證的功能，這些參數只需要設置一次；一旦設置完畢，它們就可以重複使用。
當計算 x=1 處的所有多項式時，過程非常簡單，因爲您只需將所有係數相加（因爲對於所有 k 值，1^k 始終等於 1），我們將得到以下結果：
當多項式 A 在 x = 1 處求值時，除第二個結果爲 1 外，所有結果均爲 0
當在 x = 1 處計算多項式 B 時，除第二個結果爲 1 外，所有結果也均爲 0。
當多項式 C 在 x = 1 處計算時，所有結果均爲 0，除了第四個結果爲 1。
我們看到這裏的向量三元組（a，b，c）與我們上面創建的第一個邏輯門完全相同。
文章來源：Team Tech/Research AlphaTrue
參考來源：
Chen, T., Lu, H., Kunpittaya, T., 和 Luo, A. (2022)。zk-snarks 綜述。arXiv 預印本 arXiv:2202.06877。https://arxiv.org/pdf/2202.06877.pdf
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
https://eprint.iacr.org/2012/215.pd
