1. 引言

Mina系列博客有:

传统区块链验证

t

t

t笔交易所需时间为

Ω

(

t

)

\Omega(t)

Ω(t),Mina致力于实现:从gennesis到当前的所有历史交易的验证时间为constant

O

(

1

)

O(1)

O(1)(约200ms),即与交易数无关,实现所谓的succinct blockchain。
具体实现方法为,在每个区块内包含state validity 的succinct proof。当前区块commit的system state,可看成是由genesis state,经一系列有效的交易所达成的,若当前区块有效,则这一系列交易可看成是相应的witness。
不过,若是为每个区块都从genesis开始创建所有历史交易的有效性证明,这样的proof计算将是昂贵的,为此,可借助incrementally computable SNARKs来确保为每个区块计算proof的开销,与自前一区块开始增加的交易数呈正比(即与当前区块所增加的交易数呈正比)。

Mina采用account模式,而不是UTXO模式,因此Mina链的当前状态为a list of all account balances。
在Mina的每个区块中,包含了:

  • a commitment to this state (in a Merkle tree),而不是对所有state的commitment。为此,全节点无需存储整个state,但可根据当前最新区块头中的state commitment来高效验证account balances。

但是,Mina中的Prover(类似于Bitcoin中的miner),确实需要存储所有state,因为这些state作为witness,用于证明新区块的有效性。

Mina采用名为Ouroboros Samasika的proof-of-stake (PoS)共识机制。

当前,Mina的state proof size仅为864字节,验证时间约为200ms。任意支持这种级别计算的设备(如手机),都可在无需可信设备的情况下验证Mina系统的当前状态。

除incrementally computable SNARKs之外,Mina中采用了多种优化措施,其中最有效的优化措施有:

  • 1)parallel scan state:从高层来看,这将提高交易吞吐量,使其超过顺序计算证明的限制。核心思想是对所有仍需要纳入证明的块排队,并将它们的证明分发给parallel Provers。引入最新交易的特殊队列:以将交易确认延迟降低到最小证明时间所施加的限制之下。
  • 2)引入了一种特殊的激励结构,以最大限度地提高Prover在网络中的参与度。

在这里插入图片描述

2. succinct blockchains

2.0 相关定义

PPT:probabilistic polynomial time

λ

\lambda

λ:表示安全参数。
SNARKs定义为:
在这里插入图片描述
Signature of Knowledge (SoK):为数字签名的通用表达,将公钥替换为NP language中的an instance,正式的定义参见Groth和Maller 2017年论文Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs。SoK的概念与simulation-extractable non-interactive zero-knowledge argument的概念相关。在Mina中,依赖使用SNARKs构建的SoKs,从而可利用SoK的succinctness。(Mina采用的是Bowe和Gabizon 2018年论文《Making groth’s zk-snark simulation extractable in the random oracle model》中的simulation-extractable SNARK方案。)

定义2.1:

  • state:为a string

    s

    t

    {

    0

    ,

    1

    }

    λ

    st\in\{0,1\}^{\lambda}

    st{0,1}λ

  • block proof:为a value (或a set of values)

    π

    i

    B

    \pi_i^B

    πiB,包含了用于验证该区块是否有效的信息。

  • block:每个区块关联一个称为block producer的唯一一方。block

    B

    i

    =

    {

    s

    n

    i

    ,

    s

    t

    i

    ,

    π

    i

    B

    ,

    d

    i

    ,

    b-pk

    i

    ,

     b-sig

    i

    }

    B_i=\{sn_i, st_i,\pi_i^B, d_i,\text{b-pk}_i,\text{ b-sig}_i\}

    Bi={sni,sti,πiB,di,b-pki, b-sigi},其中

    s

    n

    i

    N

    sn_i\in\mathbb{N}

    sniN为serial number,

    s

    t

    i

    st_i

    sti为当前state,

    π

    i

    B

    \pi_i^B

    πiB为当前block proof,

    d

    i

    {

    0

    ,

    1

    }

    d_i\in\{0,1\}^*

    di{0,1}为当前block data,

    b-pk

    i

    \text{b-pk}_i

    b-pki为当前block producer的公钥,

    b-sig

    i

    \text{b-sig}_i

    b-sigi为当前公钥

    b-pk

    i

    \text{b-pk}_i

    b-pki

    {

    s

    n

    i

    ,

    s

    t

    i

    ,

    π

    i

    B

    ,

    d

    i

    }

    \{sn_i, st_i,\pi_i^B, d_i\}

    {sni,sti,πiB,di}的签名。

Mina链由一系列区块

C

=

{

B

1

,


,

B

n

}

C=\{B_1,\cdots,B_n\}

C={B1,,Bn}组成,其中序列号为严格单调递增的。第一个区块

B

1

B_1

B1称为genesis block。

len

(

C

)

=

n

\text{len}(C)=n

len(C)=n为当前区块高度。

定义2.2:
succinct blockchain protocol

Π

\Pi

Π由5个PPT算法组成

(

VerifyConsensus, UpdateConsensus, VerifyBlock, UpdateChainSummary, VerifyChainSummary

)

(\text{VerifyConsensus, UpdateConsensus, VerifyBlock, UpdateChainSummary, VerifyChainSummary})

(VerifyConsensus, UpdateConsensus, VerifyBlock, UpdateChainSummary, VerifyChainSummary)

  • VerifyConsensus(consensusState, consensusProof)

    /

    \text{VerifyConsensus(consensusState, consensusProof)}\rightarrow \top/\perp

    VerifyConsensus(consensusState, consensusProof)/:该算法的输入为

    consensusState 和 consensusProof

    \text{consensusState 和 consensusProof}

    consensusState  consensusProof,验证某个正确性与否分别输出

    \top或\perp

  • UpdateConsensus(consensusState, consensusProof)

    nextConsensusState

    \text{UpdateConsensus(consensusState, consensusProof)}\rightarrow \text{nextConsensusState}

    UpdateConsensus(consensusState, consensusProof)nextConsensusState:该算法的输入也为

    consensusState 和 consensusProof

    \text{consensusState 和 consensusProof}

    consensusState  consensusProof,输出为an updated consensus state。

  • VerifyChainSummary

    (

    S

    i

    )

    /

    \text{VerifyChainSummary}(S_i)\rightarrow \top/\perp

    VerifyChainSummary(Si)/:该算法验证某blockchain summary

    S

    i

    S_i

    Si是否有效。

  • VerifyBlock

    (

    S

    i

    1

    ,

    B

    i

    )

    /

    \text{VerifyBlock}(S_{i-1}, B_i)\rightarrow \top/\perp

    VerifyBlock(Si1,Bi)/:该算法验证某区块

    B

    i

    B_i

    Bi是否对应某blockchain summary

    S

    i

    1

    S_{i-1}

    Si1有效。作为验证的一部分,它会检查

    VerifyConsensus(consensusState

    i

    1

    ,

    consensusProof

    i

    )

    \text{VerifyConsensus(consensusState}_{i-1}, \text{consensusProof}_i)\rightarrow \top

    VerifyConsensus(consensusStatei1,consensusProofi),其中

    S

    i

    1

    S_{i-1}

    Si1包含了

    consensusState

    i

    1

    \text{consensusState}_{i-1}

    consensusStatei1

    π

    i

    B

    \pi_i^B

    πiB包含了

    consensusProof

    i

    \text{consensusProof}_i

    consensusProofi

    B

    i

    =

    (

    ,

    ,

    π

    i

    B

    ,

    ,

    ,

    )

    B_i=(\cdot,\cdot,\pi_i^B,\cdot,\cdot,\cdot)

    Bi=(,,πiB,,,)

  • UpdateChainSummary

    (

    S

    i

    1

    ,

    B

    i

    )

    S

    i

    \text{UpdateChainSummary}(S_{i-1}, B_i)\rightarrow S_i

    UpdateChainSummary(Si1,Bi)Si:该算法输入为blockchain summary

    S

    i

    1

    S_{i-1}

    Si1和新区块

    B

    i

    B_i

    Bi,输出为an updated blockchain summary

    S

    i

    S_i

    Si

以上succinct blockchain protocol

Π

\Pi

Π具有succinctness属性:

  • 所谓succinctness,是指:

    (

    VerifyConsensus, VerifyBlock, VerifyChainSummary

    )

    (\text{VerifyConsensus, VerifyBlock, VerifyChainSummary})

    (VerifyConsensus, VerifyBlock, VerifyChainSummary) 算法的运行时间为

    poly

    (

    λ

    )

    \text{poly}(\lambda)

    poly(λ),此外,任意时间

    t

    i

    t_i

    ti的blockchain summary

    S

    i

    S_i

    Si的size为

    poly

    (

    λ

    )

    \text{poly}(\lambda)

    poly(λ)(即,constant in the number of chain summary updates)。

Remark 2.1:
共识机制:算法对

(VerifyConsensus, UpdateConsensus)

\text{(VerifyConsensus, UpdateConsensus)}

(VerifyConsensus, UpdateConsensus) 构成共识机制。

  • 对于proof-of-work protocol(如Bitcoin):consensus sate中将包含多个之前的difficulty targets和block times(from which to compute the current difficulty target)。其consensus proof中将包含the proof-of-work itself以及a new to update the state with。
  • 对于Ouroboros Praos类型的proof-of-stake机制:consensus state中将包含当前的random seed、当前epoch的stakes的Merkle root、之前区块和block times的某些信息。其consensus proof中将包含(满足consensus state中目标阈值要求的)一个公钥 和 一个verifiable random function (VRF) evaluation proof。

succinct blockchain中包含3个角色:

  • 1)全节点:跟踪和验证blockchain summary的一方。具有合理资源的任意人都称为全节点。也就是说,不需要轻节点的角色来应对不断增长的区块链规模。
  • 2)产块者:负责产块的一方。
  • 3)产blockchain summary:负责生成blockchain summary的一方。

blockchain summary与底层链之间的关系为:

  • a summary is valid 当且仅当 the underlying blockchain is valid。
  • 根据blockchain summary,可通过extractability获得相应的底层链。

特别定义了递归提取:即已知serial number 为

i

i

i的某blockchain summary,an extractor(额外利用某些信息)可提取出序列化为

i

1

i-1

i1的blockchain summary和区块

B

i

B_i

Bi,使得满足相应的验证测试。此处extractor所使用的额外信息称为execution trace,定义为:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.1 succinct blockchain的安全属性

已知blockchain protocol

Π

\Pi

Π和execution

ε

\varepsilon

ε,令blockchain summary

S

S

S in

ε

\varepsilon

ε的底层链为

C

C

C,则相应的安全属性有:
在这里插入图片描述

3. Mina:为基于Recursive SNARKs的succinct blockchain

Recursive SNARKs又名“incrementally-computable SNARKs”,相关论文有:

3.1 incrementally-computable SNARKs

不同于[23]中的incrementally-computable SNARKs概念 和 [7\5]中的proof-carrying data (PCD)概念,为便于表述succinct blockchain,采用state-transition system概念:
在这里插入图片描述
即具有

poly

(

λ

)

\text{poly}(\lambda)

poly(λ)-size proof(验证时间也为

poly

(

λ

)

\text{poly}(\lambda)

poly(λ))来证明如下statement:

  • 存在state

    σ

    1

    \sigma_1

    σ1 和 一系列transitions

    t

    1

    ,


    ,

    t

    k

    T

    t_1,\cdots,t_k\in T

    t1,,tkT,使得

    Update

    (

    t

    k

    ,

    Update

    (

    t

    k

    1

    ,


    ,

    Update

    (

    t

    1

    ,

    σ

    1

    )

    )

    )

    =

    σ

    2

    \text{Update}(t_k,\text{Update}(t_{k-1}, \cdots, \text{Update}(t_1,\sigma_1)))=\sigma_2

    Update(tk,Update(tk1,,Update(t1,σ1)))=σ2成立。

换句话说,就是存在一组state-transition来连接2个state。对于succinct blockchain,可将state看成是account数据库(以及正确验证新区块所需的某些metadata),将transition看成是区块。

定义4.2:
针对state transition system

(

,

T

,

Update

)

(\sum, T,\text{Update})

(,T,Update)的incrementally-computable SNARKs中包含了一组算法

(sSetup, sProve, sVerify, sSim)

\text{(sSetup, sProve, sVerify, sSim)}

(sSetup, sProve, sVerify, sSim):
在这里插入图片描述

3.1.1 采用Recursive Proof Composition的Incrementally-computable SNARKs

Mina借助了[5] Ben-Sasson等人2014年论文Scalable zero knowledge via cycles of elliptic curves中的“cycle of elliptic curves”技术,构建了2个SNARKs:

  • Tick SNARKs:
  • Tock SNARKs:

Tick SNARKs和Tock SNARKs可相互高效verify对方的proof:

  • Tick SNARKs可高效验证Tock proof
  • Tock SNARKs可高效验证Tick proof

然后Mina将Tick SNARKs和Tock SNARKs定义为a “binary tree of proofs”:

  • 1)Tick SNARK:用于证明state transition at the “base” of the tree。
  • 2)采用Tock SNARK来包裹步骤1)中的Tick SNARK。
  • 3)采用Tick SNARK来将步骤2)中的2个Tock SNARK进行合并。

即整个过程中存在2个Tick SNARKs:

  • 一个Tick SNARK用于证明state transition
  • 一个Tick SNARK用于合并2个Tock proof

详细定义为:
在这里插入图片描述

3.1.2 transition system示例

以初始状态为

x

x

x,经

k

k

k次hash运算后的当前状态

x

=

H

(

H

(

H

(

x

)

)

)

x'=H(H(\cdots H(x)))

x=H(H(H(x)))为例,对应定义4.1中,state

\sum

为the union of domain and range of

H

H

H

T

T

T为a singleton set containing an empty string,相应的update函数为

Update(t,x)

=

H

(

x

)

\text{Update(t,x)}=H(x)

Update(t,x)=H(x)
相当于需使用SNARK来证明:
存在一系列transition

(

t

1

,


,

t

k

)

(t_1,\cdots,t_k)

(t1,,tk),使得

Update

(

t

k

1

,


,

Update

(

t

1

,

x

)

)

=

x

\text{Update}(t_{k-1},\cdots,\text{Update}(t_1,x))=x'

Update(tk1,,Update(t1,x))=x,其中

Update(t,y)

=

H

(

y

)

\text{Update(t,y)}=H(y)

Update(t,y)=H(y)

k

=

4

k=4

k=4,状态

x

0

,

x

4

x_0,x_4

x0,x4满足

H

(

H

(

H

(

H

(

x

0

)

)

)

)

=

x

4

H(H(H(H(x_0))))=x_4

H(H(H(H(x0))))=x4,相应的SNARK proofs组成的tree为:
在这里插入图片描述

3.2 Mina:采用Incrementally-computable SNARKs的succinct blockchain

可将blockchain updates看成是state transition system,从而可使用incrementally-computable SNARKs来构建succinct blockchain。

3.2.1 构建Mina协议

在这里插入图片描述

4. The Mina Protocol for Payment

在本节,将专注于支付应用场景,每一方都有具有一定balance的account,交易为将一方的balance转到另一方的账号。

4.1 用于支付的Mina框架

U

\mathcal{U}

U为Mina网络中的各方集合,Mina框架中包含以下概念:

  • 账号:每方都有一个账号,标记为

    (pk, balance,nonce)

    \text{(pk, balance,nonce)}

    (pk, balance,nonce),其中

    pk

    \text{pk}

    pk为该放的公钥,用于支付认证,balance

    N

    \in\mathbb{N}

    N,nonce

    I

    \in\mathbb{I}

    I用于防止交易重放。

  • 账本:将账本定义为所有账号的集合。通过

    L(pk)

    \text{L(pk)}

    L(pk)来引用某账号,通过类似

    L(pk).balance

    \text{L(pk).balance}

    L(pk).balance来访问该账号的balance。

  • 交易:交易为将Sender account的

    L(pk

    s

    ).balance

    \text{L(pk}_s\text{).balance}

    L(pks).balance 中的

    amt

    \text{amt}

    amt 个值 转移给Receiver的账号

    L(pk

    r

    ).balance

    \text{L(pk}_r\text{).balance}

    L(pkr).balance。将该交易表示为

    txn=(pk

    s

    , pk

    r

    , amt, nonce

    s

    , sig

    s

    )

    \text{txn=(pk}_s\text{, pk}_r\text{, amt, nonce}_s\text{, sig}_s\text{)}

    txn=(pks, pkr, amt, nonces, sigs),其中

    pk

    s

    ,

    pk

    r

    \text{pk}_s, \text{pk}_r

    pks,pkr分别为发送者和接收者的公钥,

    nonce

    s

    \text{nonce}_s

    nonces为发送者账号的nonce值,

    sig

    s

    \text{sig}_s

    sigs为发送者对

    (

    pk

    r

    ,

    amt, nonce

    s

    )

    (\text{pk}_r,\text{amt, nonce}_s)

    (pkr,amt, nonces)的签名。

  • 交易验证:已知交易

    txn

    \text{txn}

    txn和账本

    L

    \text{L}

    L,验证该交易有效性的算法为:
    在这里插入图片描述

  • 账本更新:已知账本

    L

    \text{L}

    L和一组交易

    {

    txn=(pk

    s

    , pk

    r

    , amt, nonce

    s

    , sig

    s

    )

    }

    \{\text{txn=(pk}_s\text{, pk}_r\text{, amt, nonce}_s\text{, sig}_s\text{)}\}

    {txn=(pks, pkr, amt, nonces, sigs)},更新账本的算法流程为:
    在这里插入图片描述

4.2 Mina中的SNARK

S

S

S

与定义4.2对应,Mina中的incrementally-computable SNARK定义为:
在这里插入图片描述

4.3 针对支付构建的Mina协议

(VerifyConsensus, UpdateConsensus)

\text{(VerifyConsensus, UpdateConsensus)}

(VerifyConsensus, UpdateConsensus)为Ouroboros Samasika共识机制,

H

H

H为防碰撞哈希函数。
在这里插入图片描述

5. Snark Workers

Mina中引入了2种优化:

  • 1)parallel scan state
  • 2)prover incentives

以上2种优化策略都是为了解决以下问题:

  • 由图3可知,需要

    S

    i

    1

    S_{i-1}

    Si1来计算

    S

    i

    S_i

    Si,从而有sequential dependency for SNARK proof computation,直观实现的化,会使block time至少为计算proof所需的事件。此外,block proposers由于有高的交易延迟(所谓交易延迟,是指交易打包进入a SNARK proof所需的延迟时间)需要消耗高内存。

采用以上2种优化策略的目的是使交易吞吐量最大化:最大限度地提高交易处理和验证的速度,使网络上有更多同时使用的用户。

5.1 Parallel Scan State

raw blockchain中的区块本质是顺序的(即通常区块无法并行)。但是借助SNARK中的incremental computability,SNARK的生成可并行化——通过将产块和计算SNARK这2部分解耦,来实现parallel scan state。
在Mina中,维护了一种特殊的队列,名为:work queue,当有新的区块proposed时,会将该新区块塞入work queue中。也就是说,网络中需要执行a queue of the ‘SNARK work’。
然后网络并行计算SNARK proofs:

  • 会计算出一个a tree of proofs,该tree的叶子节点对应the proofs proving validity of single blocks,其它proofs用于简单地证明the correctness of their children proofs。
  • 最终,root proof用于证明the correctness of all the blocks corresponding to the leaves of the tree。

比如,假设work queue中有一系列的区块

B

i

,

B

i

+

1

,


,

B

j

B_i,B_{i+1},\cdots,B_j

Bi,Bi+1,,Bj。root proof可证明the validity of each of blocks。将该root proof与证明

S

i

1

S_{i-1}

Si1有效性的SNARK proof结合,可生成用于证明the validity of

S

j

S_j

Sj的SNARK proof。如下图所示。下图中的tree,其本质与“transition system示例”的transition系统类似。
在这里插入图片描述
由此可见,通过仔细设计并行机制,可优化保证吞吐量能跟上交易增加的速度。直观方案中,交易延迟为

O

(

R

)

O(R)

O(R),其中

R

R

R为产块rate,而借助以上优化,交易延迟减为

O

(

log

(

R

)

)

O(\log(R))

O(log(R))
通过仔细设计数据结构,还可减少存储需求。直观方案中的存储为

O

(

R

)

O(R)

O(R),上述优化后存储需求为

2

R

1

+

O

(

1

)

2R-1+O(1)

2R1+O(1)

5.2 对Prover激励

生成SANRK proofs的一方称为snarker。通过对Prover激励来实现尽可能低的交易延迟(即减少区块生成 与 该区块被吸入到链的SNARK proof中 的时间差)。

提供的Prover激励结构如下:

  • 每个产块者将一个区块push到work queue时,要求pop一个区块来为其生成a proof validating the block。产块者会提交一个fee request和其所生成的SNARK proof,同时在同一个区块中包含一笔向(为该区块计算snark的)Prover支付fee的交易。通常情况下,这些费用是从产块者可能收到的交易费用中支付的。

本质上,每件SNARK work piece都有最低价格的拍卖。产块者希望为他们的proofs给snarkers支付尽可能低的费用,而snarkers希望为他们的proofs收取尽可能高的费用。因此,强制产块者同时也是(不同区块的)Prover,可强化系统的稳定性。
注意,这与直观方案中产块者同时要计算SNARK proof类似,但是,不同之处在于,产块者为work queue head的区块计算proof,而不是为其所产区块计算proof。

Remark 6.1:
已知a proof和相应的fee request,要求adversary不能对该fee request进行抨击,否则,攻击者可pass-off a different party’s proof as their own (by replacing the public key) (即占用别人的成果)或者修改某人的fee request。
借助signature of knowledge密码学原语可实现该功能。Mina采用的是Bowe和Gabizon 2018年论文《Making groth’s zk-snark simulation extractable in the random oracle model》中的simulation-extractable SNARK方案。

6. Ouroboros Samasika——succinct blockchain的PoS共识

针对constant-size succinct blockchain,共识中需要考虑以下2个分叉场景:

  • 1)Short-range fork rule:仅需要选择最长链。
  • 2)Long-range fork rule:adversary创建分叉并长期施加作用——如可能歪曲了leader selection从而创建了更长的adversarial chain。需要以依赖分叉伊始的少量几个slot中的density difference来选择分叉链。

在这里插入图片描述
Mina中每个epoch有

R

R

R个slots,某些slot可为空(即没有任何区块与其关联)。特别地,共识参数

f

f

f,表示the probability that any given slot has a block producer assigned to it。若没有产块者给某slot赋值,则该slot为空(即没有block)。【如令

k

=

10

,

f

=

0.5

,

R

=

240

k=10,f=0.5,R=240

k=10,f=0.5,R=240

Mina的共识协议中定义了3种参与方:

  • Alert parties:可访问所有所需资源,并同步。Alert parties享有full security guarantees,可要求相对低的质押来保证安全。
  • Potentially active parities(简称为active):只在协议执行过程中,可能会参与当前time slot的所有方。
  • Inactive parties:如因网络连接等无法访问参与协议所需资源的各方。

6.1 epoch随机值及leader选举

epoch

ep

\text{ep}

ep中所考虑的质押分布通常是epoch

ep-2

\text{ep-2}

ep-2的最后一个slot内的质押分布。处理质押分布,epoch随机值也会影响任意epoch的leader选举。特别地,epoch随机值派生自epoch

ep-1

\text{ep-1}

ep-1前2/3的特定区块信息。【将一个epoch前2/3区块的最后一个区块称为“lock checkpoint”,一个epoch的第一个区块称为“start checkpoint”。】
在这里插入图片描述