基于前一篇文章，我们已经对整个Layer2，Rollup，和ZK-Rollup有了一个基本认知。如果还没有详细了解的话，请翻阅CryptoYC Insight｜Rollup 学习笔记。接下来我们以zkSNARK为例详细了解ZK-Rollup如何实现。
本文将围绕三大问题，以Zcash为例详细了解零知识证明和ZK-Rollup的交易流程。
想要了解零知识证明，首先需要对整个ZK-Rollup过程有一个认知，否则很难形象认知以下问题：
下面我们围绕这三大问题，以Zcash为例详细了解ZK-Rollup的交易流程。需要注意的是，很多涉及到具体数字之类的问题，笔者还是有所省略，欢迎读者提出质疑并与笔者讨论。
这里不再详细介绍Zcash，只需要知道其为一种加密货币即可。**在Zcash的ZK-Rollup中，一共存有两种账本，分别为承诺账本(Commitment Notes)和零化账本(Nullifier Notes)。**与比特币类似，Zcash追踪所有还未花费的货币(比特币中称为UTXO，Unspent Transaction Outputs)，而每笔交易被记录于零化账本中。承诺账本中的例子如下Hi = hash(pk , r , m ).这里Hi为用户i，pki是其钱包地址，也是公钥，存在与之对应的只有账户持有人才有的密钥ski，mi为金额值，为方便理解，这里统一为1BTC，ri为每笔钱的序列号。可以理解成，每张印出来的钱，在承诺账本中都有它的金额，持有人地址，及该钱的序列号。
**零化账本初始为空。**若Alice和Bob想要交易，如Alice为H1=\mathrm{hash}(pk1,r1,1).她想给Bob转1BTC，那么她按如下步骤进行：
其他节点接收到前2条消息，查找零化账本中此条哈希值是否已经存在，若已经存在说明这1BTC被花费过了。若不存在，则说明还未被花费，于是在验证者验证完第3条后，其他节点将H2更新至承诺账本，并将nf1更新至零化账本中。
至此，在完全不了解零知识证明的具体实现方法和实例的情况下，我们至少已经了解前2个问题的答案。
接下来为了深入了解第3个问题，我们需要拆分成几个小问题，然后带着这些问题去理解一个例子。
具体证明：
想要了解怎么证明及验证，我们需要了解证明的角色，问题如何转化，以及最终证明的过程。这里我们给出一个反方向证明的过程，从需要证明的内容一步步转化，以便于理解。
**零知识证明里一共有2个角色，证明者与验证者。**以zkSNARK为例，其全称为零知识简洁非交互信息证明(Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)。这里零知识代表证明者想要在不透露信息的情况下说服验证者我有一定的秘密信息。简洁代表证明的验证应当是非常迅速，通常在几毫秒内就可完成。而非交互意味着验证者与证明人之间不需要提前沟通或者实时沟通，如验证者发送消息，证明者回复等循环往复。
这⾥以交易⽣成中的⼀条为例，证明⼈(即Alice)想要证明⾃⼰持有密钥 。验证者这⾥已知的信息 是Alice的钱包地址，也即公钥 。sk1 pk1 为防⽌太过抽象，我们举⼀个简单的RSA密码体制的例⼦。这⾥取2个随机素数 ，将其乘积记为 ，Alice选取 且 ，并求得其逆元 使得 。该体系中， 为公钥，⽽ 为密钥。p, q N = p ⋅ q e < r = φ(N) = (p − 1)(q − 1) (e, r) = 1 d e ⋅ d ≡ 1 mod r (N, e) (d) 证明可以转化为已知 e ，证明证明者知道 d 使得 e ⋅ d ≡ 1 mod r ，换句话说使得 e ⋅ d = a ⋅ r + 1, a ∈ N
接下去的问题归约会有⼀些难度，这⾥仅作⼀些直观上的解释，便于理解。从问题转化中，我们已经 有⼀个等式，对于验证者来说有三个未知量( d, a, r )和⼀个已知量( e )。将等式作如下变换 e ⋅ d + (−a ⋅ r) = 1, 并令 c1 = e ⋅ d, c2 = −a, c3 = r，c4 = c2 ⋅ c3 , c5 = c1 + c4 ，我们得到 c5 = 1. QAP(Quadratic Arithmetic Program)问题归约定义为
Source: https://blog.deversifi.com/6-pillars-of-professional-trading-speed/
这⾥整除的概念就简单举个例⼦，f(x) = x 2 + x 能被g(x) = x + 1整除，余多项式为h(x) = x 。f(x) = x 2 + x g(x) = x + 1 h(x) = x 这⾥应⽤QAP我们知道，证明者Alice应该有系数c1 , ..., c5 ，和多项式P(x) 。⽽验证者知道⼀个次 数为1的多项式 T(x) (这⾥先忽略次数为1的原因，⼤致原因为乘法只⽤到了⼀次)。c1 , ..., c5 P (x) T (x) 这⾥证明者想要说服验证者，只需要证明存在整系数多项式(或者说系数在有限数域 上的多项式， 形象的理解是任何⼤于等于p的数在该数域⾥都会写成除以p所剩的余数，如 ) Fp 2p + 1 ≡ 1 mod p）H(x) ，使得 P (x) = L(x) ⋅ R(x) − O(x) = H(x) ⋅ T (x). (1)
⼀个有趣的事实是，两个次数⾄多为d的不同多项式 ，⾄多有d个相交的点。简单的例⼦ 如 ，我们可以得出 唯⼀的解 f(x), g(x) f(x) = ax + b, g(x) = cx + d f(x) = g(x) x = . c − a b − d 应⽤于我们的问题上，可以说任意取⼀个点 ，若 ，则有很⼤概率我们可以 得到(1)式成⽴。当然也存在很低概率 恰巧只是两个多项式的交点。但是如果Alice能够知道点 ， 她可以编造随机多项式 s P (s) = H(s) ⋅ T (s) s s H(x) 为进⼀步防⽌Alice得知验证者取的点 ，也为了双向零知识(即我不知道你取了什么点，你不知道我 有什么样⼀个函数)，验证者需要进⼀步隐藏⾃⼰的取值点 。接下来我们介绍同态隐藏 (Homomorphic Hiding)。
同态隐藏的定义很简单，⼀个从实数域上打到特定空间的映射 E : R → S ，满⾜以下3个特点：1. 对于任意给定的像点 E(a) ，从计算⻆度⽽⾔找到其原像 a 是困难的；2. 对于任意不同原像 a, b ∈ R, E(a) = E(b) ; 3. 对于任意 a, b ∈ R, E(a + b) 可以由 E(a), E(b) 表⽰(加法同态)；最简单的例⼦就是 当然它不满⾜第1条特点，但是对于理解第2，3条特点有很⼤帮助。对 于不同 ，显然 ，且 。E(a) = a, a, b E(a) = E(b) E(a + b) = E(a) + E(b) 稍微复杂⼀点，但是更加贴近真实情况的是有限数域 的乘法群 (简单来说就是 )， 这样的群被证明为循环群，也就是说整个群可以被表⽰为 Fp Fp ∗ Fp − {0} Fp = ∗ {1, α, α , ..., α }. 2 p−2 定义E(a) = α a ，那么我们也有以上3个性质，读者可以⾃⾏验证。其中第⼀点的性质来源于离散 对数问题。
离散对数问题(Discrete Logarithm) 给定乘法群( )，⼀个n阶元素 ( 是由⽣成的⼦群)。找 到唯⼀的整数 ，使得 G, ⋅ α ∈ G, β ∈< α > < α > α 0 ≤ a ≤ n − 1 α a = β. 这个整数 a 被记为 logα β ，称为 β 的离散对数。在现代密码体制中，离散对数问题(Discrete Logarithm)被认为是困难的。虽然没有证据证明该问题是 NP-Complete，但⽬前也没有找到⼀个多项式时间内的算法解离散对数问题。为什么同态隐藏可以隐藏取值点 s ？因为任意系数在 Fp 上的d次多项式都可以被表⽰为 P (x) = a0 + a1x + ... + adx . d 那么只需要给定 E(1), E(x), ..., E(x d ) ，我们就可以计算 E(P (x)) = (E(1)) ⋅ a0 (E(x)) ⋯(E(x )) a1 d ad 这是因为 E(P (x)) = α a0+a1x+⋅+adx = d α ⋅ a0 α a1x ⋯α adx = d (α) ⋅ a0 (α ) ⋯(α ) . x a1 x d ad 下⼀步我们将⽤同态隐藏来使得Alice随机验证多项式。
在现代密码体制中，离散对数问题(Discrete Logarithm)被认为是困难的。虽然没有证据证明该问题是 NP-Complete，但⽬前也没有找到⼀个多项式时间内的算法解离散对数问题。为什么同态隐藏可以隐藏取值点 s ？因为任意系数在 Fp 上的d次多项式都可以被表⽰为 P (x) = a0 + a1x + ... + adx . d 那么只需要给定 E(1), E(x), ..., E(x d ) ，我们就可以计算 E(P (x)) = (E(1)) ⋅ a0 (E(x)) ⋯(E(x )) a1 d ad 这是因为 E(P (x)) = α a0+a1x+⋅+adx = d α ⋅ a0 α a1x ⋯α adx = d (α) ⋅ a0 (α ) ⋯(α ) . x a1 x d ad 下⼀步我们将⽤同态隐藏来使得Alice随机验证多项式。
使⽤同态隐藏随机验证多项式 在证明过程中，证明者Alice有私密多项式 ，且验证者知道多项式 。为验证Alice真的有正确的多项式 ，⾸先验证者取⽣成元 ，作为同态隐藏的 底。然后随机选取 ，想要验证 。P (x),L(x), R(x), O(x), H(x) T (x) P (x) g ∈ Fp ∗ s ∈ Fp E(P (s)) 由步骤4我们得知，如果验证者发送 则证明者Alice可以计算 并将结 果返回给验证者。这样做还存在3个问题：E(1), E(s), ..., E(s ) d E(P (s)) 如果证明者作弊怎么办。若Alice不知道多项式 ，但是随便计算了⼀个值，返回给验证者， 验证者如何验证Alice知道多项式系数？1. P (x) 如何验证等式 成⽴？即使Alice可以返回 ，验证者知 道 的情况下，依旧没法计算 2. P (x) = H(x) ⋅ T (x) E(P (s)), E(H(s)) E(T (s)) E(P (s)) = E(H(s) ⋅ T (s)), 因为 E(H(s)) ⋅ E(T (s)) = E(H(s) + T (s)) 。我们仍需要⼀个验证⼿段。如何保障⾮交互式？⽬前所有的计算与验证均在交互式情况下进⾏，⽽Alice要进⾏zkSNARK就要 保证⾮交互。
Source: https://blog.deversifi.com/6-pillars-of-professional-trading-speed/
实际上，这⾥Zcash取的是有限域内椭圆曲线的⼀个⾼效pairing映射。也即zkSNARK的简洁性。在Alice接收到 (E1 (1), E1 (s), ..., E1 (s ), E (α), E (αs), ..., E (αs )) d 2 2 2 d 后，她计算 ，并且发布给验证者。验证者⾃⼰可 以计算 ，并验证：a = E1 (P (s)), b = E2 (α ⋅ P (s)), c = E1 (H(s)) d = E2 (α ⋅ T (s)) • f(a, E2 (α)) = f(E1 (1), b) ，也就是说 f(E1 (P (s), E2 (α)) = f(E1 (1), E2 (α ⋅ P (s))) • f(c, d) = f(E1 (1), b) ，也就是说 f(E1 (H(s)), E2 (α ⋅ T (s))) = f(E1 (1), E2 (α ⋅ P (s))) 从而验证P (x) = H(x) ⋅ T (x) 。
为了达到⽆交互，只需要在初始状态下⽣成随机 α ∈ Fp ∗ , s ∈ Fp ，和 (E1 (1), E1 (s), ..., E1 (s ), E (α), E (αs), ..., E (αs )). d 2 2 2 d Alice与验证者都使⽤该序列，进⾏证明和验证即可。这种初始设定叫做Common Reference String Model(CRS)。
这⾥也预防了验证者恶意发送验证值的情况，该设定下验证者也没有 的信息。否则在验证者恶 意发送 d次随机数 s的情况下，P(x) 的系数向量可以被解开。事实上，这仍是笔者的⼀个疑问。
至此我们已经用具体例子完成了一次零知识证明的全部过程，感谢阅读。
仅为展示和提供相关信息，文章不构成任何投资建议。如发现文章含敏感或不当信息，欢迎致信