看zk-SNARK的文章或者資料的時(shí)候您没，經(jīng)常會(huì)碰到一些算法名稱，比如Groth16扣草，GGPR13等等了牛。這些名稱是由算法提出的作者名稱或者名稱首字母以及相應(yīng)的年份組成。Groth16辰妙，是由Jens?Groth在2016年提出的算法鹰祸。GGPR13，是由Rosario?Gennaro密浑，Craig?Gentry蛙婴，BryanParno，Mariana?Raykova在2013年提出的算法尔破。
零知識(shí)證明（zk-SNARK )街图，從QSP/QAP到Groth16浇衬，期間也有很多學(xué)者專家，提出各種優(yōu)化（優(yōu)化計(jì)算時(shí)間餐济，優(yōu)化證明的大小耘擂，優(yōu)化電路的尺寸等等）。Groth16提出的算法颤介，具有非常少的證明數(shù)據(jù)（2/3個(gè)證明數(shù)據(jù)）以及一個(gè)表達(dá)式驗(yàn)證梳星。
Groth16論文（On the Size of Pairing-based Non-interactive Arguments）的下載地址：
https://eprint.iacr.org/2016/260.pdf
本文主要從工程應(yīng)用理解的角度介紹Groth16算法的證明和驗(yàn)證過程。文章中所用的中文字眼可能和行業(yè)中不一樣滚朵，歡迎批評指出冤灾。
Proofs?- 在零知識(shí)證明的場景下，Proofs指具有完美的完備性（Completeness）以及完美的可靠性（Soundness）辕近。也就是韵吨，具有無限計(jì)算資源也無法攻破。
Arguments?- 在零知識(shí)證明的場景下移宅，Arguments是指具有完美的完備性以及多項(xiàng)式計(jì)算的可靠性归粉。也就是，在多項(xiàng)式計(jì)算能力下漏峰，是可靠的糠悼。
Schwartz-Zippel 定理?- 假設(shè)是個(gè)n元多項(xiàng)式，多項(xiàng)式總的階為d浅乔。如果
是從有限集合S中隨機(jī)選取倔喂，則的概率是小于等于。簡單的說靖苇，如果多元多項(xiàng)式席噩，在很大的集合中隨機(jī)選取參數(shù)，恰好函數(shù)f等于0的概率幾乎為0贤壁。
https://brilliant.org/wiki/schwartz-zippel-lemma/
線性（Linear）函數(shù)?- 假設(shè)函數(shù)f滿足兩個(gè)條件：1.??2.悼枢，則稱函數(shù)f為線性函數(shù)。
Affine 函數(shù)?- 假設(shè)函數(shù)g脾拆，能找到一個(gè)線性函數(shù)f馒索，滿足，則稱函數(shù)g為Affine函數(shù)名船。也就是绰上，Affine函數(shù)是由一個(gè)線性函數(shù)和偏移構(gòu)成。
Trapdoor函數(shù)?- 假設(shè)一個(gè)Trapdoor函數(shù)f包帚，很容易，但是非常難运吓。但是渴邦，如果提供一個(gè)secret疯趟，也非常容易。
QAP的定義為"
Relation"：谋梭。也就是說信峻，statements為， witness為瓮床，并且的情況下盹舞，滿足如下的等式：
的階為n。
設(shè)置過程：隨機(jī)選取隘庄，生成踢步。
證明過程：隨機(jī)選擇兩個(gè)參數(shù)，計(jì)算
驗(yàn)證過程：
驗(yàn)證過程丑掺，計(jì)算如下的等式是否成立：
注意获印，設(shè)置過程中的x是一個(gè)值，不是代表多項(xiàng)式街州。在理解證明/驗(yàn)證過程的時(shí)候兼丰，必須要明確，A/B/C的計(jì)算是和CRS中的參數(shù)成線性關(guān)系（NILP的定義）唆缴。在明確這一點(diǎn)的基礎(chǔ)上鳍征，可以看出的參數(shù)能保證A/B/C的計(jì)算采用統(tǒng)一的參數(shù)。因?yàn)闀?huì)包含
子項(xiàng)面徽，要保證和C相等艳丛，必須采用統(tǒng)一的參數(shù)。參數(shù)增加隨機(jī)因子斗忌，保證零知識(shí)（驗(yàn)證者無法從證明中獲取有用信息）质礼。參數(shù)保證了驗(yàn)證等式的最后兩個(gè)乘積獨(dú)立于的參數(shù)。
完備性證明（Completeness)：
完備性證明织阳，也就是驗(yàn)證等式成立眶蕉。
可靠性證明 (Soundness):
Groth16算法證明的是statistical knowledge soundness，假設(shè)證明者提供的證明和CRS成線性關(guān)系唧躲。也就是說造挽，證明A可以用如下的表達(dá)式表達(dá)(A和CRS的各個(gè)參數(shù)成線性關(guān)系）：
同理，B/C都可以寫成類似的表達(dá)：
從Schwartz-Zippel 定理弄痹，我們可以把A/B/C看作是的多項(xiàng)式饭入。觀察
這個(gè)驗(yàn)證等式，發(fā)現(xiàn)一些變量的限制條件：
1）?(等式的右邊沒有)
不失一般性肛真，可以假設(shè)谐丢。
2）?（等式右邊）
不失一般性，可以假設(shè)。
3）(等式的右邊沒有因子)
也就是乾忱。
在上述三個(gè)約束下讥珍，A/B的表達(dá)式變成：
4）等式的右邊沒有
不失一般性，
5）等式的右邊沒有
不失一般性窄瘟，衷佃。
6）等式的右邊沒有，?
所以?
7）等式的右邊沒有和
所以蹄葱，氏义。
在上述七個(gè)約束下，A/B的表達(dá)式變成：
再看驗(yàn)證的等式：
觀察图云，因?yàn)椴淮嬖?惯悠，所以，琼稻。
也就是說
代入驗(yàn)證等式吮螺，所以可以推導(dǎo)出：
，
如果帕翻，假設(shè)鸠补，對于，則
代入A/B嘀掸，可以獲取以下等式：
在證明和CRS線性關(guān)系下紫岩，所有能使驗(yàn)證等式成立的情況下，等式必須成立睬塌。也就說泉蝌，能提供正確證明的，肯定知道witness揩晴。
5
QAP的NIZK Arguments
從QAP的NILP可以演化為QAP的NIZK Arguments勋陪。也就是說Groth16算法并不是完美的可靠，而是多項(xiàng)式計(jì)算情況下可靠硫兰。QAP的定義為"Relation"
也就是說诅愚，在一個(gè)域中，statements為劫映， witness為违孝，并且的情況下，滿足如下的等式（的階為n）：
也就是說泳赋，三個(gè)有限群, 對應(yīng)的生成元分別是雌桑。為了方便起見，也為了和論文的表達(dá)方式一致祖今，的計(jì)算用表示校坑，的計(jì)算用表示拣技。
設(shè)置過程：隨機(jī)選取，生成耍目。
證明過程：隨機(jī)選擇兩個(gè)參數(shù)过咬，計(jì)算
驗(yàn)證過程：驗(yàn)證如下的等式是否成立。
很容易發(fā)現(xiàn)制妄，驗(yàn)證過程的等式也可以用4個(gè)配對函數(shù)表示:
證明過程和QAP的NILP的證明過程類似，不再詳細(xì)展開泵三。
6
證明元素的最小個(gè)數(shù)
論文指出zk-SNARK的最少的證明元素是2個(gè)耕捞。上述的證明方式是需要提供3個(gè)證明元素（A/B/C）。論文進(jìn)一步說明烫幕，如果將電路進(jìn)行一定方式的改造俺抽，使用同樣的理論，可以降低證明元素為2個(gè)较曼，但是磷斧，電路的大小會(huì)變的很大。
總結(jié)：Groth16算法是Jens Groth在2016年發(fā)表的算法捷犹。該算法的優(yōu)點(diǎn)是提供的證明元素個(gè)數(shù)少（只需要3個(gè)）弛饭，驗(yàn)證等式簡單，保證完整性和多項(xiàng)式計(jì)算能力下的可靠性萍歉。Groth16算法論文同時(shí)指出侣颂，zk-SNARK算法需要的最少的證明元素為2個(gè)。目前Groth16算法已經(jīng)被ZCash枪孩，F(xiàn)ilecoin等項(xiàng)目使用憔晒。
