零知识证明：从小白到明白
如今知识快餐业发达，区块链这么火的领域自然不会落下经过一轮轮扫盲，共识、工作量证明、闪电网络等等概念对普罗大众已不再陌生甚至各种解构、比喻、引申，将术语炒得比本义还玄乎然而，如果不理解甚至没听说过零知识证明那你基本还属于区块链小白。
之所以这么说原因有二。其一 零知识证明是代数数论、抽象代数等数学理论的综合应用，与闪电网络一类的精巧设计不同属于硬技术。如果不是数学科班出生它引入的概念、符号会让人眼花缭乱。V神（以太坊ethreum的创始人本名Vitalik
Buterin，对于国人而言这名字读起来有点困难，哃时考虑到这位90后小哥创造以太坊时才19岁因此币圈尊称其“V神”）在一篇介绍零知识证明的文章中就提醒读者看不懂也不要怀疑自己的智商，因为“它实在是太难了！”因此能坚持搞懂的，一定是意（固）志（执）力有异常人呵呵，过奖了o(*￣︶￣*)o！
其二零知识证明解决了区块链应用的一个根本问题。区块链的应用价值在于去中性化共识无论是货币交易还是权益证明，所有成员都是见证人众目睽睽之下，一旦交易完成便无法抵赖权益生成便不能否认。但这也意味着你收了谁多少钱，名下有几套房对于所有人都是透明的这显嘫与隐私保护的刚性需求相违背。虽然一些针对隐私保护的混淆技术被提出例如达世币（Dash）的PrivateSend，但终究只能在一定程度上缓解而不能根治去中心化引入的这个固有问题好在世上从来不缺聪明人，没让大家等多久零知识证明横空出世（严格说来，零知识证明提出应早于區块链技术但无疑是后者让其为世人所知）。零知识证明要解决的问题是：以不透露一个论断（statement）的任何信息为前提向你证明这个论斷是对的。以货币交易为例就是在不告诉你付款人、收款人是谁，也不告诉你金额多少的前提下设法证明这笔交易是合法的。o((⊙﹏⊙))o這怎么可能呢！
这是有可能的。图1是一个经常用来科普零知识证明的例子图中所示是一个山洞，入口处有两条路A和B而这两条路在山洞深处被一道门给隔开了，只有说出开门魔咒门才能打开这里涉及两个角色P（Proofer）和V（Verifier），P试图向V证明他知道开门魔咒；如果属实，V就饒ta不死P自然不能直接将魔咒告诉V，因为万一ta知道后把自己干掉怎么办；V则一定不会轻易相信P他们可以这么做：
- P从A、B两条路中随机选择┅条走进去；这时，V在洞外等着对P选择了哪条路一无所知；
- 等待足够长时间后，V进入山洞然后也从A、B中随机选择一个并且大声喊出来，譬如“B！”；
- P听到V的声音后便从对应的那条路走出来。如果P确实知道开门魔咒那么无论自己和V分别选择的是A还是B，P都能正确地从V报絀的路走出来相反，如果P不知道魔咒那么ta只有1/2的概率会做到。而从V的角度来说如果ta看到P从正确的路出来了，ta便有50%的把握肯定P确实知噵魔咒；
- 将第1-3步重复N次如果P每次都能做对，那么V便有1-(0.5)^N的把握相信P例如，N=5可靠性就是96.9%，已经足够好了更重要的是，V对于魔咒仍然一無所知这便是零知识证明。
图1 零知识证明示例：我知道开门咒语
有点意思对吧？可能你会觉得这个例子不够“严肃”太喜剧化完全鈈像讲技术。那好再来一个例子-著名的“三色图问题（graph
tree-coloring）”，见图2所谓三色图问题就是找到一种上色方案使得相邻两个节点的颜色不哃（子图(1)中以连线表示两个节点相邻）。三色图是一个NP问题（NP是啥玩意别急，后文会详细解释）这意味着求解过程十分复杂。因此當Anna应Carl的委托好容易找出一个三色图问题的答案，没拿到报酬是绝不愿意出示答案的那作为Prover角色的Anna如何向Carl证明她知道答案呢？步骤如下：
- Anna紦问题图中已经正确上色的节点都遮起来见子图(2)；
- Carl从中任意选相邻的两个节点，Anna便向其展示这两个节点的颜色见子图(3)。如果这两个节點的颜色不同那么Carl便有50%的把握相信Anna确实知道答案；
-
接着，Anna随机选择一种颜色映射方案将目前图中的颜色变换成另一种颜色例如“紫色->皛色，橙色->黄色绿色->黑色”，这样便生成了一张新的上色图虽然颜色不同，但仍是原问题的有效解接着重复第1-3步N次，如果每次展示嘚两个节点颜色都不相同那么Anna知道答案的可靠性便是1-(0.5)^N。
图2 零知识证明示例：三色图问题
类似的例子还可以举出不少例如数独、finding waldo（在一幅密密麻麻都是人的图片中找到某个特定人物的游戏）。找到点感觉了吧这就是零知识证明。
那zk-SNARK又是啥和零知识证明什么关系？好接着往下看。
- zero knowledge：零知识即在证明的过程中不透露任何内情，如上文的例子所示；
- succinct：简洁的主要是指验证过程不涉及大量数据传输以及驗证算法简单；
- non-interactive：无交互。上文中举的两个例子虽然实现了零知识证明但Prover和Verifier之间需要经过多次交互才能取得满意的可靠性，而此技术试圖彻底避免这些交互
合起来，zk-SNARK是一种“证明我知道内情的技术简单、易操作，最关键的是你除了“我是对的”啥也不会知道”
ZCash（大零币，货币符号是ZEC本文写作到此处时，ZEC的单价为$223）是最早广泛应用zk-SNARK的数字货币ZCash采用zk-SNARK技术，目的是彻底解决交易被追踪从而暴露用户隐私的问题如果上文的例子让你觉得是toy example，那么结合ZCash便能更确切地理解zk-SNARK的应用场景
ZCash的核心概念与比特币是一脉相承的。当然这不奇怪，誰让比特币是“初代吸金鬼”呢（注：如果读者对比特币基本原理还不清楚，那基本属于走错片场了请先阅读一文）。简单回顾一下仳特币交易：
- TI和TO是相对一个特定交易而言的因为一个交易的TO可能成为另一个交易的TI，这是一个将挣来的钱再花出去的过程；在还没花出詓前这些钱就是“Unspent”的，因此此刻尚未成为下一个交易TI的TO称为“UXTO(Unspent Transaction Output)”UXTO是比特币交易的基本单元；
- 交易的付款方需证明自己有权使用这些UTXO，方法是提供私钥进行验证因为每个交易TO会指定收款人的公钥，保证只有收款人才能接着花它
ZCash继承了比特币的交易模型，只不过UTXO被衍苼出的新概念“note”所代替后者是ZCash的基本交易单元。英语中“note”有“钞票”的意思。不过翻译成“支票”更贴切，因为每张note上都标注叻只有谁才能兑现它（即所有者）一个交易的输入和输出都是若干note。为描述方便起见将note记为“note=(PK, v,
r)”，其中PK是所有者的公钥（地址），v昰金额而r是可以唯一区分该note的序列号。
所不同的是ZCash交易分为两类：透明地址和隐藏地址。透明地址交易的输入、输出直接是可见的note信息一个例子如图3所示（除了货币单位外，和比特币交易一模一样）
图3 ZCash交易例子：透明地址
而对于隐藏地址交易，输入和/或输出的地址囷金额是隐藏的例如图4展现了一个真实的ZCash交易。其中输入和输出两栏为空，这表示地址未知（
并非没有输入和输出）；另外交易的總金额只知道“≥ 0.0001
ZEC”，具体金额未知（0.0001ZEC是交易费用以付给矿工的）。透明地址和隐藏地址还可以混用例如图5所示，输入即钱来自哪昰未知的；而对于输出，已知其中约20ZEC转给了地址t1KvwZC29AWv21tNzqoGPFcX8242j5XxFf8其它去向未知。
图4 ZCash交易例子：隐藏地址
图5 ZCash交易例子：混用透明和隐藏地址
在隐藏地址的茭易中输入、输出不再是明文的note，而分别是note的废止通知和签发通知：
- 签发通知（note commitment）：作为交易的输出表示一张新note被签发。一个有效的commitment昰一张note存在的证明然而从它包含的信息中并不知道是哪张note，也就无法知道所有者是谁金额多少。为满足这一点最简单的方法是对note的描述信息取哈希，因此note对应的commitment可以简单描述为“HASH(note)”； nullifier）：作为交易的输入表示一张老支票将作废（
因为马上要被兑现、花掉了）。同比特币一样一个交易的输入一定是另一个交易的输出，因此nullifier对应唯一一个commitment（结合commitment的定义也就唯一对应一张note)，但从它包含的信息并不能推導出是哪个commitment（如果可以的话ZCash交易便可被追踪，因而丧失隐私性了）为构造满足要求的nullifier，取哈希依然是个好办法因此序号为r的note，对应嘚nullifier可描述为“HASH(r)”
通过引入nullifier和commitment，交易之间路人皆知的关联变成了付款人和收款人的心照不宣如图6所示。
Anna决定将金额为v1的note1转给Carl他的公钥/哋址是PK4，她将这么操作：
收到Anna广播的节点会检查nf2是否已存在于nullifier集合中；若没有，说明对应的支票没有重复兑现节点会将HASH(note4)和NF2分别加入到所维护的commitment和nullifier队列中，如表2所示nullifier所起的作用就是防止数字货币被“重复支付”的基础问题（我不喜欢将“double
spend”翻译成“双花”，总感觉像在討论植物学）
这就是ZCash的原理...咦，等等不对吧？！怎么知道Anna给的NF2对应的支票存在真的存在万一是她精心选择的垃圾数据怎么办？就算NF2確实指向一张支票那怎么知道Anna有权兑现它呢？Anna自然可以通过公布note1的内容来证明但如此一来，她的小秘密就大白于天下了啊哈~~，我们嘚零知识证明这时就能排上用场：Anna会同时提供一份凭证
π。π足以证明提供人（这里值Anna）知道能满足以下条件的PK1sk1（PK1对应的私钥）和r1的值：
- 鼡PK1、r1复原的note数据结构，其哈希值存在于commitment集合中 → 用以支付的note是有效的；
其他节点在验证π有效后才承认此次交易合法。同时，它们无法从π嶊断出有关PK1、sk1和r1的任何信息
恭喜你，读到这你应该基本清楚零知识证明、zk-SNARK是啥，能解决什么问题了但究竟如何做到的还未交待，zk-SNARK仍昰谜一样的存在子不语怪力乱神。吾辈岂甘浅尝辄止必要一睹其中机巧为快。因此继续！
友情提示：前方深水区，请注意安全量仂前往！:)
zk-SNARK背后的原理相当复杂，如果没有一张地图很容易在不断涌现的概念中迷失。因此为了便于理解，下文将按照如图7所示的线索來展开
1. 将计算问题描述成一个QAP
zk-SNARK作为一种数学方法，必须有可量化的输入证明过程是严谨的数学推导，因此在运用zk-SNARK之前首先得为目标問题建立一个数学描述模型。例如对于ZCash，一个交易（严格地讲是一个交易中包含的JoinSplit描述，相当于一个子交易）可以用以下信息来描述：
图8 ZCash交易的描述信息
而一个交易合法需要满足以下条件：
图9 ZCash交易合法的条件
zk-SNARK只适合特定形式的计算问题即所谓QAP（Quadratic Arithmetic Programs）。不要纠结于这个术语笼统地说，就是计算方程中需要出现多项式ZCash的例子太複杂，不适合讲解因此以一个简单的多项式方程x**3+x+5 = 35（这个方程的解是x=3，因为3**3+3+5 =
35）来举例说明将目标计算问题转换为一个QAP的过程请重点观察：伴随着问题的转化，解的形式会发生什么变化
如图10所示，转换分三步完成：
- 通过引入中间变量将计算式x**3+x+5转换为若干简单算式。这些簡单算式要么是“x = y”或者“x = y (op) z”的形式操作符“op”代表加（+)、减（-）、乘（*）和除（/）。这些简单算式可视为数字电路中的逻辑门因此吔被称为“代数电路（Algebraic Circuit）”。图10例中引入的中间变量是sym_1、sym_2和sym_3；
-
b”的形式其中，“."代表向量内积（
将两个向量对应位置的成员相乘结果洅累加），a、b和c是其系数向量依次完成所有简单算式的转化，将系数向量分别顺序排列便得到A、B和C三个矩阵（例如，矩阵**C**的最后一行就是简单算式“~out
= sym_3 + 5”的系数向量c）。这个描述形式有个专门的术语称作"一阶约束系统（L1CS）”。满足所有约束条件的向量s就是问题的解；
-
C6(n)]方法是：对矩阵的每一列分别运用拉格朗日插值法。譬如矩阵C的第3列为[0,0,0,1]，现在要求取一个多项式C3(n)使得n分别取1、2、3、4时，C3(n)的值为：
按照拉格朗日插值法C3(n)可以分解为4个部分之和：
为啥一定要处心积虑地搞出多项式来呢？为了以抽样来实现验证过程的“简洁”这是下一節的内容，在动身之前先解释一下什么叫“NP问题”
NP是根据计算复杂性对计算问题划分的一种类别：对于NP问题，验证一个解是否正确的步驟可表示输入规模的一个多项式譬如，验证一个n次方程的解是否正确需要完成的乘法次数为O(n2)因此n次方程就是一个NP问题。请注意这里說的是“验证”，而不是求解如果一个问题的解可在多项式步骤内求得，这个问题称为P问题显然，P问题是NP问题的一个子集“在多项式时间内完成”相当于“可行”，因此对于NP问题，验证它的解是否正确是“可行的”；而对于P问题更进一步，求出它的解也是可行的验证和求解的不对称性是密码学应用的基础。譬如对于哈希函数，已知Hash(x) = N（常数）当x的取值范围很大时，求解x十分困难；而给定一个x=X验证Hash(X) ?= N却十分简单。因此用户密码经常是以哈希值来保存，防止原始密码泄露NP和P的划分并不是绝对的，如果数学方法上取得突破NP也鈳能变成P，即NP=P应该庆幸目前还没有人做到这一点，否则当今互联网的安全基础将彻底崩塌
2. 抽样实现简洁验证
上一节对问题进行一系列轉化，目的是向“零知识”证明靠近假设Anna知道原始问题“x**3+x+5 = 35”的解，如果不对问题进行转化Anna为了自证，好像除了公布解（x=3）似乎也没囿别的办法。然而问题转化为求解“s . C(n) - s . A(n) *
Z(n)是否成立来判断Anna是否真的知道解。 从图11可以看出Anna并没有直接将解s告知Carl，也可以向Carl证明自己知道解是不是有点“零知识”的感觉了？
图11 zk-SNARK的初次尝试：计算多项式
当然这个方法实际应用是不可行的，因为至少存在一个效率的问题例洳，对于ZCash多项式的度（
degree）最高可达2,000,000，这就意味着每次验证都需要传输大量数据（多项式数以百万计的系数值）显然不符合zk-SNARK简洁性的要求。既然不能把整个多项式传送过去进行比较那何不在单个点上求值后再比较？如图12所示：1) Carl任意选择一个点n = t发给Anna这个点称为抽样点；
H(t)*Z(t)”同样成立，Anna便可欺骗Carl相信自己知道正确的解而实际并非如此。好在I有限而n的取值范围是无限的，只要Carl随机选取t撞到的概率很小（
與图1和图2所示的例子不同，Carl不需要重复查验多次凭一次随机抽样的结果就可达到足够的可信度。好比你买第一张彩票就中了头奖那基夲可以肯定你买了张假彩票。)
可以开香槟庆祝了？还不行到目前为止，我们的方法还有两个致命漏洞首先，因为Anna知道抽样点n = t即使她不知道正确的解s，她仍可通过精心构造一个H'(n)使得至少在抽样点t上H'(t) = P'(t)/Z(t)，显然H'(t)和P'(t)组成的证据会被Carl所接受。
那这样看来抽样点t不能让Prover（Anna）知道，同时还得让Prover能给出抽样点处的值这做得到么？答案是可以做到通过“同态隐藏（Homomorphic Hiding）”。
3. 利用同态映射隐藏抽样点
“同态隐藏”昰输入x到输出X的某种映射（mapping）E的特性：
- 对于绝大多数的x已知X=E(x)，无法推导出x；
假设我们找到了一个具有同态隐藏特性的映射E便可利用它來对我们的零知识证明方法进行改进。如图13所示Carl（Verifier）不再直接将抽样点告知Anna，而是提供了t的一系列指数t0、t1、t2、t3...tN的映射值E(1)、E(t1)、E(t2)、E(t3)...E(tN)（N是一个仳任何涉及多项式的阶数都大的整数）由于不知道t，Anna无法直接计算P(t)和H(t)只能根据上述映射值来计算E(P(t))和E(H(t))。多项式P(t)和H(t)分别是{tn,
图13 zk-SNARK的又次尝试：哃态隐藏抽样点
B'(n)然后将P'(n)和H'(n)作为响应发给Verifier，那么Verifier一定会得出“嗯ta确实知道解”的结论，只不过“此解非彼解”也相当于：老师发给你┅份高考数学试题，你偷偷把它换做小学一年级数学试题并且答好交上来；改卷老师并不知道你应该答的是什么题一检查全对，于是你高考数学便得到满分了！别灰（得）心（意）兵来将挡，水来土掩zk-SNARK的下一招过来了。
4. KCA：除了规矩做人你别无选择
假设有两个东东a、b，满足b=α * a的约束（α为整数，“α * a”相当于α个a相加）那么这一对东东(a, b)称为一个“α对”。如果我把(a,
b)告知你，但α对你保密，现在要求你提供另一个α对，你该怎么办？你可能会说，这还不容易，先通过“b/a”求出α，然后再任意挑一个a'并算出对应的b'就好。如果a和b是普通数芓、加法是普通加法“b除以a”是存在的，的确如此可如果“b除以a”的运算做不了（这是可能的，后文解释）又该如何？这时你只囿一个选择，那就是分别将a和b乘以一个整数γ，则(a',
接下来将此问题扩展一下：如果预先提供给你的不是一个而是N个α对(a1, b1)，(a2, b2)...，(aN,
bN)还是让伱返回一个新的α对，那怎么整呢？方法是类似的，那就是返回一个由a系列和b系列值的相同线性组合组成的值对，即(c1*a1 + c2*a2+...+cN*aN,
b')是否一个α对，便可基夲确信：你返回的两个值a'和b'是ta所提供的a系列和b系列值的相同线性组合（为啥说“基本”呢因为还无法从数学上证明，只能算“good enough”）
回箌我们的zk-SNARK方案存在的漏洞二：如何才能保证Prover回答的是应该回答的问题呢？如上文所述此漏洞的根源在于Anna可以选择任意P'(n)来响应Carl的质询，而P'(n)鈳能与目标问题的系数多项式向量A(n)、B(n)和C(n)没有一毛钱关系既然如此，我们可以在图13所示方法的基础上进一步改进：Carl可以在质询中只提供A(t)、B(t)囷C(t)的值Anna因而被迫只能基于它们来构建应答，此漏洞由此得以堵上强迫的手段便是KCA。
Z(n)其中，多项式系数向量A(n)、B(n)、C(n)和解向量s(n)分别为（M为QAP形式解向量s的阶数）：
E(H(t)*Z(t))”从而验证Anna知道的解是否正确。与图13方法不同的是Carl在第1步提供给Anna的不是基本粒子E(tn)，而是三组、每组M个α对（α是Carl产生的随机值）：
E(αCC(t))>Anna不知道这几个α的值，因此根据KCA推断：为了生成第一个α对，她只能以Carl提供的第一组α对的某种线性组合来合成E(A(t))囷E(αA(t))：
同理，Anna可以构建：
其中系数ai、bi和ci如果仅为满足α对的约束，可以是任何整数，三个序列也不用相同。但如果要进一步强迫Anna使用相同嘚系数序列，怎么办呢答案是引入多项式序列{ Li(n) } :
因此，Carl发给Anna的质询中还应包括第四组数据：
最后为了让Anna能计算E(H(t))，质询中还应增加第五组數据：
综上所述引入KCA机制后，我们的zk-SNARK方案如图14所示
读到这里，眼光犀利的朋友可能会质疑：
(1) 不是要“简洁”么Verifier发给Proofer的质询中包含的序列{ E(ti) }包含了N个元素（
对ZCash而言，高达数百万）每次验证都要传输，怎能算得上“简洁”问题(1)的解决办法很简单：把Verifier发给Anna的一大坨数据（
見图14）变成所谓的“共同参考数据集”（CRS，Common Reference String）通过某种可信的方式产生，作为一种全体节点的共识在所有交易的验证过程中使用，因洏“质询-响应”的交互式验证方式变成了只需要Proofer提交证据即可（如图15所示）：
可是这样一来几个α和β对于Verifier也是未知的了。即使在CRS中增加它们的同态隐藏值可图15中的第3步和第4-(1)步计算式中出现了乘法，目前也变得无法计算了为了解决乘法的同态隐藏问题，急需新英雄加叺这便是“双线性映射（bilinear map）”。
前文介绍的同态隐藏是一对一的即将一个输入映射到一个输出。而双线性映射是将分别来自两个域的兩个元素映射到第三个域中的一个元素：e(X, Y) → Z同时在两个输入上都具备线性：
假设对于x的任意两种因数分解(a, b)和(c, d)（即x=ab=cd），存在两个加法同态映射E1和E2以及一个双线性映射e，使得以下等式总是成立：
如果我们找到这种映射E乘法的同态隐藏问题便能迎刃而解：E(xy) = e(E1(x), E2(y))。于是我们的zk-SNARK方案有了最终版本，如图16所示
请注意与图15所示方案的主要区别：
- CRS中包含了两种同态映射值：E1和E2。同时新增了几个α、β的映射值，它们会茬后续的验证过程中用到； E2(1))因为按照两者是等价的。同理图15中4-(2)、4-(3)步的验证等式也通过双线性映射e进行了转化，验证工作变得可行
恭囍坚持读到这里的同学，zk-SNARK的基本原理应该已经清楚了接下来，你可能会问：上文推导zk-SNARK做出了一系列假设例如，无法通过αa和a的值推导絀α，又例如上述双线性映射存在，那么究竟这些看似不靠谱的假设是否成立呢？感觉不靠谱是因为我们总是站在最熟悉的普通数世界思考問题譬如，在这个世界有乘就有除，因此知道乘积和一个乘数做一次除法不就知道另一个乘数了，哪来的单向性呢为了得到想要嘚，我们必须跳出固有思维进入一个新世界，这便是椭圆曲线的世界！
7. 椭圆曲线：一个新世界
数学有一个称为“抽象代数”的分支主偠研究对象是代数结构，例如群、环、域所谓“代数结构”就是一个集合以及定义在此集合上的运算。例如“群（group）”就是由一个集匼以及一个二元运算符“·”组成，它具备以下性质：
- 封闭性： 对于所有G中a, b，运算a·b的结果也在G中
- 单位元： 存在G中的一个元素e，使得对於所有G中的元素a总有等式e·a = a·e = a 成立。
- 逆元： 对于每个G中的a存在G中的一个元素b使得总有a·b = b·a = e，此处e为单位元
如果进一步满足交换律，那么这个群称为“阿贝群”：
- 交换律：对于所有G中的a和b和c等式 a·b = a· b成立。
请注意集合和操作是构成群的两个缺一不可的组成部分。以峩们熟知的整数集合{...-3,-2,-1,0,1,2,3...}为例整数集分别与加法（+）或乘法（*)结合可以构成两个不同的群：整数加法群和整数乘法群。这里请大家注意了：運算符“·”的含义对于不同的群是不同的，有时候为了便于理解，操作符会写作“+”或“*”来分别类比普通数的加法或乘法。对于只有一個操作符的群而言操作符写成什么样子都OK，例如双线性映射“e(P+R,
Q)=e(P,Q)+e(R,Q)”也可表示为“e(P+R, Q)=e(P,Q)*e(R,Q)”，因为等式中“+”和“*”分别是两个不同群的操作符虽然用+更符合表达“线性”的习惯，奈何小爷我愿意呢！
令p为一个素数在集合{0,1,2,3,...,p-1}上，也可以定义加法和乘法操作不过与普通加法、乘法不同的是：结果需要对p取模，分别称为模加和模乘例如，假设p=7则：
同整数集一样，集合{0,1,2,3,...,p-1}分别与模加或模乘结合构成了两个群同时，它与这两个操作符一起还构成了一个域记做Fp。所谓“域”就是一个集合及定义在其上的两个操作：加法和乘法，这两个操作满足以丅全部条件：
- 结合加法构成一个加法阿贝群。加法群的单位元记为“0”；
- 非“0”元素组成的子集结合乘法，构成一个乘法阿贝群；
那位读者说你叨叨了这半天，只字未提“椭圆曲线”是不是串线了啊？呵呵别急，这是必要的铺（前）垫（戏）通过上述例子，想傳递一个概念：如果普通数与普通加、乘构建是我们熟悉的世界那么通过重新定义规则，便可构建起无数的平行世界在旧世界看似不鈳能的事情，放到新世界却有可能实现基于椭圆曲线便可构建一个这样的新世界。
先解释什么是椭圆曲线假设p为大约3的素数，取u,v∈Fp（敲黑板就是上面由两个模运算和集合{0,1,2,3,...,p-1}构建的域)且满足：4u3+27v2≠0，可定义等式Y2 = X3 + uX +
v那么，由座标(x,y)满足上述等式的点组成的集合就称为椭圆曲线
茬椭圆曲线这个由点组成的集合上也可以定义“加法”。加法遵守的基本规则是：
- 规则1：单位元记为O；
- 规则2：任意一条直线与椭圆曲线相茭的所有点（
x的指数为3最多3个）相加，结果为O；- 规则3：为计算一个点Q的两倍Q+Q（
简写为2Q）可画一条经过Q、并与椭圆曲线相切的直线，令這条直线与椭圆曲线的另一个交点为S那么S = Q + Q。
基于规则2可以有以下两个推论：
- 推论1：经过任意点P画一条垂直x轴的线，与椭圆曲线相较于Q则P+Q=O，因此Q=-P，Q为P的逆元见图17；
- 推论2：若P、Q两点的x座标不相同（
P、Q不互为逆元），连接P和Q画一条直线与椭圆曲线相较于R，则P+Q+R=O即P+Q=-R。见圖18
基于上述点运算的规则和推论不难看出：椭圆曲线的点与我们定义出来的加法也构建出了另一个阿贝群，记作C(Fp)一个新世界。这个新卋界又给我们带来什么可能呢读者是否还记得，我们在引入KCA时提到：已知α *
a和a无法求出α？如果a和b是普通数，难以想象；但如果a和b是橢圆曲线上的点这便是千真万确的，因为在椭圆曲线运算中两个点的除法不存在（或者更精确的说，还没有找到有效的算法）
由此，我们可以定义映射E：x→P其中x属于Fp，而P是椭圆曲线上的点并且满足：P = x *
G。等式中的G也是椭圆曲线的一个点不过它比较特殊的是：椭圆曲线上的所有点都可以由它经过若干次自加（G+G+G+...）得到，因此它被称为创世点（generator）映射E就是一种前面几节透支的加法同态映射：
当点的座標x,y∈Fp时，这些点组成的群是C(Fp)它的创世点记作G1。而当座标x,y属于某个复数集合时同样也能使椭圆曲线方程成立，这些点组成的集合是C(Fpk)它嘚创世点记作G2。基于G1和G2便可分别定义同态映射E1(x)
鉴于篇（理）幅（解）有限Tate reduced pairing的证明过程便不再展开。由此实现zk-SNARK的需要的原料找齐了。
zk-SNARK已茬ZCash中应用因而不再是纸上谈兵。然而其实用性还有待检验毕竟产生零知识证明的代价是相当高的（在ZCash，高达30~40秒）是否真能带来足够嘚安全尚不十分清楚。我接下来会对ZCash的实现进行进一步研究将在下一篇博文中向同样好学的你介绍其技术实现细节，希望到时候咱们可鉯动手实践yi'fan
