Reducing Participation Costs via Incremental Verification for Ledger Systems学习笔记

1. 引言

Weikeng Chen等人2020年论文《Reducing Participation Costs via Incremental Verification for Ledger Systems》。

相关代码见：

• IVLS（ incrementally verifiable ledger system ）：https://github.com/arkworks-rs/ivls
• PCD（Proof-Carrying Data）：https://github.com/arkworks-rs/pcd
• Non-native field arithmetic：https://github.com/arkworks-rs/nonnative
• Constraints of Marlin：https://github.com/arkworks-rs/marlin
• Constraints of Marlin’s polynomial commitments：https://github.com/arkworks-rs/poly-commit

账本系统为运行在P2P网络的许多servers（又名“全节点”）之上的应用，可提供强一致性保证。典型的账本系统有：仅支持basic payments的 cryptocurrencies，以及支持rich smart contracts的 cryptocurrencies。

但是，这种强一致性保证，源自high participation costs。本文重点关注如何降低账本系统中的participation costs。

1.1 何为participation cost？

所谓Participation costs，是指： 账本系统中的servers（“全节点”）为维护the entire application state，需根据某种共识协议，为每笔新交易（或区块内的一堆交易）运行相应的state transition。 新加入到网络中的server（“全节点”），需要下载每笔交易并执行迄今为止的每个state transition。随着交易数量的增加，其带宽和computation costs会线性增长。如截止2020年，Bitcoin账本已超过300GB，为获得最新状态，下载和执行每笔交易所需时间要数天，具体取决于机器。

此外，对于想要与该application交互的client，其：

• 要么需要自己像server（“全节点”）一样，维护整个application state；【client需要运行与其无关的计算，如处理系统内的所有payments。且使得client无法在weak devices（如手机）上运行。】
• 要么需要向某server回复关于当前状态（甚至过去交易状态）的请求。【要求client信任某server返回的结果是正确的。】

对于P2P账本系统来说，高participation cost意味着中心化（集中到少数能维护整个application state的参与者）。

1.2 通过cryptographic proofs来避免交易的re-execution

在验证state transition时，可利用密码学证明来避免交易的re-execution。

直白来说，密码学证明使得任何人都可生成一个短字符串来证明计算的正确性，相比于证明计算本身，验证该证明的速度为exponentially faster。 借助密码学证明，可为transition的正确性生成证明，对应有transition前后的application state的2个short commitments。这样，验证最新state仅需要:

• 下载所有的state commitments和transition proofs（远少于下载所有的交易）
• 并验证所有transition proofs（工作量远小于re-executing所有交易）

transition proofs可同时减少servers和clients端的participation costs，但是servers和clients仍需要处理每个transition proof。对于新加入（或重新加入）的参与者，处理到当前状态为止的所有transition proofs的cost仍与state transitions的数量呈线性关系。对于长期离线的client来说，这样的开销仍然是昂贵的。

为解决以上问题，直观的方案是引入untrusted operator来为batches of transactions生成transition proofs。这就是流行的“layer-2扩容解决方案”。但是，由于batches的size通常不能太大，并未根本性地解决该问题。

1.3 Incremental verification

Valiant 2008年论文《“Incrementally verifiable computation or proofs of knowledge imply time/space efficiency》中介绍了incrementally verifiable computation（IVC）：

• 用于capture an everlasting computation，其每个中间状态都伴随有一个易于验证的proof来证明其相对于 初始状态（而不是前一状态） 的正确性。

IVC是通过密码学证明的递归组成来实现的，即生成的证明：

• 既证明当前state transition的正确性。
• 又证明prior proof的正确性。

相比于直接执行，验证的速度要exponentially speedup，从而保证基于previous proof生成proof的cost 与 过去state transitions的数量 无关。

incremental verification可大幅降低账本系统的participation costs。使得，验证最新状态仅需要：

• 下载当前状态（或a short commitment to it）
• 以及下载a short proof，该proof可证明其相对于初始状态的正确性。

1.4 实现该潜力中

区块链社区已认识到incremental verification的潜力，并开始做相关研究。如在基于proof-of-stake的Mina链上做了相应实践。以及基于Nakamoto共识的支付系统相关研究有：Kattis等人2020年论文 Proof of necessary work: Succinct state verification with fairness guarantees。

不过，当前针对账本系统的incremental verification研究仍处于早期：

• 首先，当前研究仍是简单的用户到用户的转账交易，而不是更丰富的应用（如结合隐私或智能合约）。
• 第二，密码学证明的最新进展，如 [CHMMVW20; GWC19; BGH19; COS20; BCMS20; BCLMS20] 要优于 [KB20; BMRS20]这些需要需要可信设置的proof system。

1.5 相关研究

Mina团队论文[BMRS20]（首次2018年，2020年扩展了）《Coda: Decentralized cryptocurrency at scale》中基于proof-of-stake共识协议涉及了incrementally verifiable payment system。Mina对Ouroboros Genesis协议《Ouroboros Genesis: Composable proof-of-stake blockchains with dynamic availability》进行了修改，使得其chain selection rule可通过a small-space algorithm实现。从而获得一个适用于增量状态更新的共识协议。

Kattis等人2020年论文[KB20]《Proof of necessary work: Succinct state verification with fairness guarantees》中，设计了基于proof of necessary work共识协议的incrementally verifiable payment system。在该论文中，展示了如何修改Nakamoto共识协议，与proof-computation结合，以保证solve puzzles的过程是“抗摊销的”，从而保证了mining过程的公平性。

2. 本文主要贡献

本文主要贡献有：

• 1）incrementally verifiable ledger systems。Valiant的IVC概念有用但不足以用于账本系统的incremental verification。

  • 首先，IVC是指automata computations（arbitrary transitions of a small application state），而账本系统中的应用，包含的transition functions为，每笔交易，会make few accesses to a large application state。
  • 其次，IVC是指一个算力强大entity长期运行state transitions，然后，将其传给另一抢到entity（Valiant撑起为“multi-generational computation”）。而账本系统中，运行state transitions的许多方可能有一段时间是offline的，然后再online，要求能高效“catch up” from when they left to the latest state。
  • 第三，账本系统中的client并不想要存储整个application state，而是通过向存储了完整state的server请求其所选择的信息，应要能保证完整性。

  本文引入了incrementally verifiable ledger system（IVLS）的密码学原语，我们称其为IVLS compiler。

• 2）incrementally verifiable applications。通过对应用的state、transactions、transition functions进行精巧设计，本文的IVLS可实现五类应用：

  • 2.1）基于UTXO的转账（Bitcoin的bare-bones版本）
  • 2.2）基于账号的转账，相关研究有 [KB20; BMRS20]
  • 2.3）保留隐私的转账，如Zerocash [Ben+14]
  • 2.4）保留隐私的去中心化计算，如Zexe [BCGMMW20]
  • 2.5）key transparency [MBBFF15]——一种流行的公钥设施

• 3）本文以Rust语言对IVLS primitive做了原型实现，主要贡献有：

  • 3.1）Recursing a universal SNARK based on pairings：基于pairing的，incremental verification with a universal (application-independent) setup。采用R1CS约束，Marlin Verifier。
  • 3.2）Incremental verification for private payments：模拟Zerocash的incrementally verifiable版本实现。隐私转账的递归验证。
  • 3.3）Incremental verification reduces participation costs：一项实证评估，通过对十年“bare-bones”比特币的测量来验证参与成本的降低。可配置为circuit-specific setup或universal setup，也可配置不同的MNT cycles（对应low-security和high-security level）。

3. 账本系统的participation costs

一个账本系统中，包含了：

• heavy servers：负责维护application state
• lightweight client：负责perform queries to the current state（或 to consult past transactions）

本文所说的participation costs主要包含以下两方面的开销：

• 同步开销：servers和clients都可能会go offline，然后再“catch up” to the current state of the system。（当servers或clients初始加入时，需从创世状态开始同步）。servers和clients会通过验证其是一系列交易的正确结果，来验证当前状态的完整性。
• 查询开销：client仅存储一个短的state承诺值，然后想要确保servers回复的查询请求对应正确的状态。clients可能还会查询之前的应用状态，因为应用可能会“forget”某些client仍关心的信息（如基于UTXO支付系统中已花费的某笔交易）。若client仅维护当前状态的承诺值，其需要确保用于回答该查询的先前状态在当前应用程序状态历史中。

接下来，按：no proofs、有transition proofs、有recursive proofs（为incremental verification的基础）这三种情况下的participation costs对比：

• 1）No proofs：无proofs时，servers或clients若想要对某application state有信心，必须自上次online开始，自己下载并执行每笔交易（会引起高的同步开销），以此来派生出相应的application cost。这样其实clients与servers并无差别，为验证有效性，clients也必须维护a copy of the current application state。client的query cost（查询开销）等同于execute该query over this local copy。
• 2）Transition proofs：无需执行每个state transition，servers或clients可下载每个state transition、proof以及next state承诺值。servers还会下载当前application state，并检查final commitment为该current state的承诺值。而clients不再需要整个application state，查询开销也有所不同：client仅需使用state的承诺值来验证每个responses。 相比于no proofs，transition proofs有重大改进，借助batch技术可进一步减少开销[OWWB20; LNS20]。但是，同步开销仍然与state transitions的数量呈线性关系，当servers/clients掉线较长时间时，相应的开销仍不可忽略。 3）Recursive proofs：递归证明会进一步压缩servers和clients的同步开销，移除任何与state transitions数呈线性关系的开销。servers和clients仅需要验证一个proof，证明当前状态是正确的，以及可能再验证另一个lightweight proof，证明当前状态是基于之前状态的延伸。Prover可递归地组合prior proofs，以减少proving cost。有递归证明的查询开销 与 transition proofs的查询开销 相当，因为clients仍然需要检查their queries were correctly executed using a commitment to the state。

4. IVLS（incrementally verifiable ledger system）定义

ledger system为a pair LS=(F, C)，其中：

• F为名为transition function的 read-write program：定义了transactions如何修改状态，即给定某交易tx为输入，对当前state S的query access，F会输出 y y y，以及a state update Δ \Delta Δ（表示为 ( y , Δ ) = F S ( t x ) (y,\Delta)=F^S(tx) (y,Δ)=FS(tx)），将 Δ \Delta Δ应用于old state s，即可获得新state S ′ S' S′（表示为 S ′ = S + Δ S'=S+\Delta S′=S+Δ）。
• C为名为client function的 read-only program：定义了client对state的查询类型，即诶定某query x和query access to a state S，C输出a query answer y y y（表示为 y = C S ( x ) y=C^S(x) y=CS(x)）。