'CryptoYC'
研究|Mina背后的理想乡:递归零知识证明
🌿

研究|Mina背后的理想乡:递归零知识证明

零知识证明是指证明者向验证者证明一个陈述是正确的,而无需透露除了该陈述正确以外的任何信息。比如阿里巴巴知道开启堆满了财宝山洞大门的咒语, 四十大盗抓住他让他说出咒语,如果他告诉强盗,他就失去了价值,会被强盗杀死。所以阿里巴巴为了不让强盗听到咒语,让强盗站在自己身后一定距离之外。并且约定,如果他的咒语打不开山洞大门,强盗就可以杀了自己,如果打开了,那么就说明自己的咒语是正确的。在这个过程中,强盗并不能获得咒语,但是阿里巴巴通过山门打开,可以向强盗证明咒语的正确性。在这里四十大盗就是验证者,阿里巴巴是证明者。在现实生活中也有很多场景运用了0知识证明。

0 知识应用场景:

1. 信用评分高于 700

2. 证明纳税但不透漏收入

所以一个零知识证明就是:

证明一个秘密 → 程序计算 → 算数电路 → 多项式 → 证明

Figure 1: 算数电路图
Figure 1: 算数电路图

Note:把程序计算问题用算数电路转化是因为要把电路进一步化为数学模型,即多项式。就可以通过输入,导线,乘法门或加法门验证多项式的正确性。

递归零知识证明

正常的链如果需要验证,需要下载从创始区块开始的所有区块才可以进行验证。而递归零知识可以让验证者不用从头开始验证区块,只需下载当前区块进行简单验证即可,因为它的每一次证明都会将前一个块的证明封装进来,所以最新的区块会包括从创始区块到目前区块的证明,而且区块大小只有22kb,用台式机进行次验证,只需要几毫秒就可以完成。举个简单的递归证明例子,当你出去旅游一周,为了记录每天去了哪里,选择用照片来做证明。那么第一天你站在一个景点前照了一张相,第二天你去了两一个景点,手中拿着第一天的照片,所以第二天的照片上有你第二天去的景点,手中照片包括了第一天去的景点日期和你自己,以此类推,第七天出来的照片就包含了从第一天到最后一天所有去过的景点和去的时间,并且最后这个证据只是一张照片,前面的照片都可以不需要,就可以证明这一周的旅游轨迹。

因此Mina也会把这个过程称作snapshop(快照)。这就是为什么Mina的块一直是22kb的原因,每一个块都包括了前一个区块的证明和现在状态,下一个区块只需要将已经证明的加上现在的状态做成一个块储存起来,做个状态转换的证明,所以虽然计算是递增的,但块的大小是不会变的。

简洁区块协议

Mina的区块固定22kb是因为Mina链本质是一个简洁区块链,所以我们先来看简洁区块链的区块都包含哪些信息,

image

由 sn_i ∈ N 生成,sn_i 是序列号,st_i 为目前状态,π^B_i 区块证明,d_i 是 data, b-pk_i 块生产者的公钥 b-sig_i 签名。一个简洁区块链协议Π的特点是有五 个算法的元组(验证共识,更新共识,验证区块,更新链,验证链),定义如下:验证共识(验证状态,共识证明)→ ⊤/⊥:这个算法将验证状态和共识证明作为input,根据某些正确性的 output 来进行验证 True 和 False。更新共识(共识状态,共识证明)→ 下一个共识状态:这个算法依然能将共识状态和共识证明作为input,然后output一个共识状态。

验证链摘要(S_i)→ ⊤/⊥: 该算法验证区块链摘要 S_i 是否是有效的。作为验证的一部分,会核对第一个算法,验证共识(验证状态 i-1,共识证明 i ) → ⊤, S_i-1 包含共识状态 i-1,π^B_i 包含共识证明 i,区块证明 π^B_i 被包含在区块 B_i 中。

验证区块(S_i-1, B_i)→ ⊤/⊥:验证区块 B_i 是否合理,关于给定区块摘要 S_i-1

更新链摘要(S_i, B_i)→ S_i:这个算法用区块链摘要 S_i-1 和新块 B_i 生成一个更新的区块链摘要 S_i。S_i = (σ_i , snarks_i),当 block 是有效的,summary才是有效的。

这里的共识机制是由算法对(验证共识,更新共识)组成。

Mina 证明系统

1. 状态转换系统

Mina建立了一个证明系统,叫做Pickles。包含两个SNARKs,Tick SNARKs和Tock SNARKs分别用来证明和验证。简单来讲,Pickls就是状态转换系统。类似于比特币里的UTXO,Mina 的状态转换系统是一个元组(Σ,T,Update),Σ 代表状态的集合,T是转换的集合,Update是(非确定性的)多项式时间可计算函数,函数为 Update:T × Σ → Σ。当然,Update在无法为某个input 生成新状态时, 可能会“抛出异常”。在状态转换上,我们想要证明:存在一个状态 σ1,和一个状态序列 t1, t2, . . . , tk ∈ T,有Update(tk,Update(t_k-1, . . .,Update(t1, σ1))) = σ2, 并将这两个状态转换之间做个简洁的证明。而且生成的每个区块恒定 22kb大小,在Tick曲线上证明的计算,结果可以通过Tock椭圆曲线验证。

2. 用递归证明做 Snarks 递增计算

在SNARKs递增计算上,采用了“循环的椭圆曲线”技术,就可以用一个来验证另一个的证明。具体需要两个Tick SNARKs(base和merge),一个用来证明状态转换,另一个用来合并两个Tock证明。Tock SNARKs 用来wrap Tick证明。

3.Tick 和 Tock 定义

3.1 The base SNARK

基于Tick的SNARK 用来证明单个转换证明,被称作“base”SNARK。

Statement:(σ1, σ2) ∈ Σ²

Witness:t ∈ T

Computation: ∃ t ∈ T, s.t Update(t, σ1) = σ2, 我们用 σ1 →Tick σ2 来表示该证明

3.2 The merge SNARK

基于Tick的SNARK用来合并两个Tock proof,被称作“merge”SNARK。

Statement:(σ1, σ3) ∈ Σ²

Witness:σ2 ∈ Σ 和 Tock-proofs π1, π2

Computation:∃σ2∈Σ 和Tock-proofs π1, π2 s.t Verify_Tock((σ1, σ2), π1)和 Verify_Tock((σ1, σ3), π2), 该证明用 σ1 →Tick σ3 来表示,而从σ1到σ2 和σ2到σ3的转换,都有SNARK证明。

3.3 The wrap SNARK

基于Tock的SNARK用来证明一个 Tick proof,被称作“wrap”SNARK。

Statement:(σ1, σ2) ∈ Σ²

Witness:π

Computation:∃ Tick proof π s.t VerifyTick((σ1, σ2), π) 用 σ1→Tick σ2 来表示该证明。但这个SNARK仅仅wrap一个 Tick SNARK进Tock SNARK,以便用另一个 Tick SNARK 就能有效的证明它。

Note:Statement是公开信息,相当于某个计算电路的input;Witness就是零知识证明中,需要被隐藏的部分。

下图图示就是一个转换系统的例子

Figure 2: TickTock
Figure 2: TickTock

所以在这个过程中,zk-SNARK 程序使用上一个状态,该状态的证明以及新的交易作为输入,验证上一个状态,检查新状态的交易是否有效,有效就会产生新的状态及证明。最后可以证明从状态x0到x4是真实有效的。

总结

Mina优化了单层递归证明,用” 循环椭圆曲线” 技术建立了新的递归证明pickles系统来证明状态的转换,包括交易证明和区块证明。证明系统中有两个 Snarks:Tick Snark和Tock Snark。在Tick里面又分base和merge用来证明和合并交易,Tick则用来验证。因为证明是可以被验证的,所以不需要区块包含之前所有的证明就可以验证当前区块的正确性。形成了恒定 22kb 的简介区块链。

参考文献

1.Mina技术白皮书:

2.zk-SNARK 论文链接:http://rujia.uk/resource/ZK-SNARK.pdf