Zhuang's Diary

言之有物，持之以恒

Posted on Edited on

Run the command:

1
sudo apt-get install build-essential

Chances are you will need things like gcc to actually do the building so you might as well install those as well. The build-essential package will install other tools used along with make.

Posted on Edited on

zksync 与其他 layer2 方案相比较，优缺点如何？ ==> https://mp.weixin.qq.com/s/drgDM5mCZsBQdTIfszO97g

先说结论如下图：

在区块链 layer1 (以太坊) 中，所有的计算过程和数据存储都在主链进行（交易数据存在区块中，全节点执行所有计算过程）；但 layer2 不同，我们可以根据 layer2 如何解决这两个扩展相关的瓶颈问题（计算 & 数据存储）来对他们分类，正如上图的二阶矩阵所示。

Plasma

Plasma 由 Vitalik Buterin 和 Joseph Poon 在 2017 年共同提出；Plasma 作为被寄予厚望的理论思想，可以说是开启了以太坊扩展研究的先驱。将其放在矩阵右下角。

从本质来说，Plasma 的思想相对直观。为了获得更好的扩展性，Plasma 将计算和数据存储都迁移到 layer 2 进行；由 layer 2 的执行者周期性地向主链递交 Merkle 根形式的 “状态承诺” 。如果执行者递交无效的状态，用户可以向主链上的智能合约提供错误性证明（fraud proof）；一旦确认执行者出现欺诈行为，则智能合约会罚没他的保证金。

虽然这个想法简单优雅，但细节实现起来却是困难重重。最大的问题就出在数据可用性（data availability）。虽然说可以通过错误性证明，使得提供无效承诺的执行者在主链上遭到惩罚，但用户如果想要提供错误性证明，首先得取得构造出错误承诺的错误数据。这时候问题就来了，如果 plasma 的执行者拒绝在主链上公开数据，那用户能怎么办？这可能会导致主网上记载的 layer2 状态被推进到错误的状态，且无法对执行者追责。

针对这个问题， Plasma 衍生出一些相应的方案，如延长资产从 layer 2 退出的时间，当出现作恶行为，就能够允许大量资产从 Plasma 链退出。但经过这些年的摸索，可行的方案还没有真正实现；这也促使二阶矩阵其他象限的方案的出现。

zkRollup

zkRollup 通过一种间接的方式解决了数据可用性问题，将所有 layer2 上的交易数据，作为参数发送到主链上的某个智能合约内。这意味任何人都能通过观察区块链上的 “calldata（数据调用）” 来获得 layer2 的所有数据，但这同时让 zkRollup 能带来的可扩展性优势仅限于计算这一个维度上了。

zkRollup 则是靠着在主链完成零知识证明，保证无效的状态绝不会发生。因为所有计算都被 “汇总” 到证明里，所以无需信任或是检查执行者。

zkRollup 对数据存储方面也带来了一定程度上的扩展性提升。举例来说，zkRollups 可以发送压缩过的数据给智能合约，而且全节点不需要将 calldata 存储在活跃状态里面，减轻了全节点的使用负担。在 zkRollup 链上无需包含签名数据，因为零知识证明就足以证明交易的有效性。

zkRollup 部署难度较高，安全性要求较高，所以现有的 zkRollup 技术只专注于应用在某几个特定项目，如 Loopring 的去中心化 layer2 交易所。

zkRollup 的零知识证明模型：

  1. 状态树(State Merkle Tree)

Ha 是 account tree 的高度。Hb 是 balance tree 的高度.

  1. 金额打包

金额和费用使用的是科学计数法： sign * mantissa * (radix ^ exponent)，其中的 mantissa 和 exponent 被封装在 zkSync 之中。

Optimistic Rollup

Optimistic Rollup 保留 calldata，可以在主链获得所有 layer2 的数据。同时 Optimistic Rollup 采用错误性证明（跟 Plasma 方案一样），对提交无效状态的执行者进行惩罚。

相比于 Plasma 和 zkRollup， Optimistic Rollup 做了一些权衡，所以带来的扩展性提升幅度最小。Optimistic Rollup 不依赖于什么过于前沿的技术或悬而未决的问题，实际推广中 Optimistic Rollup 更好落地。有多个团队（比如 “Optimism Group” ）都已接近将 Optimistic Rollup 架构部署到主网上。

Validium

Validium 选择将 layer2 的交易数据放在链下，因而比 rollup 架构有着更高的扩展性。验证计算方面，Validium 采用零知识证明。如先前在讨论 zkRollup 时提到的，这样做会导致 Validium 在目前的应用部署，只能局限于特定目的（普适性低），比如 StarkEx 就是面向去中心化交易所的方案。

但这些权衡使得 Validium 在某些方面优于 Plasma 。在主网进行零知识证明验证能避免执行者提供无效状态，也能降低执行者不公开数据造成的后果。举例来说，想要勾结执行者，让状态错误地转变为 “把他人的钱转到自己账户” 是不可能办到的；因此 Validium 不需要在协议中设计 “大量资金退出” 激励博弈，也不需要延长资金从 layer2 退出的时间。

正如其他研究者指出的，零知识证明并不是解决数据可用性问题的灵丹，比如（恶意）执行者修改自己所控制的账户的状态是没有问题的，然后积压关于这些交易的数据，这会导致某些用户想退出资金时，无法提供 Merkle proof 。

=======================另一组比较方法=======================

为了简化问题，我们的评估将从以下四个方面着手，分别是：

  1. 安全性（Security）
  2. 性能（Performance）/经济性（economics）
  3. 易用性（Usability）
  4. 其他

希望我们的综合比较可以帮助开发者评估不同的扩容解决方案，并采用最适合其需求的解决方案。

除了这些问题之外，我们还汇总了一张对照表（译者注：这张表是本文的重点），可作为与解决方案提供商对话的起点。我们尽了最大努力保持对比的中立和客观，但是在表格里简洁地表达不同方法的细微差别仍然是一项艰巨的任务。我们希望更多的上下文能弥补这一问题。

非常感谢 Georgios Konstantopoulos（Layer 2独立研究员），John Adler，Ben Jones，JD Kanani，Patrick McCorry，Justin Drake（以太坊基金会）和Brecht Devos（Loopring 路印），感谢他们对该表的审查和更正。

注：
0 某些研究完全不认为侧链应被归入 L2 范畴，可见：https://twitter.com/gakonst/status/1146793685545304064
1 要看相关升级机制的实现，不过一般来说都可以
2 有非常复杂的限制
3 为保证与 EVM 的可组合性，吞吐量的上限是 300 TPS
4 这个参数实际上是可调的，但大部分研究员都觉得 1 到 2 周时间比较安全
5 要看相关的实现。zkSync 是不需要的，但 Loopring 需要
7 理论上来说，可以通过流动性提供商缓解这个问题，但是会让整个方案的资金利用效率性变差

Posted on Edited on

zksync 是用于以太坊的、可扩展的、隐私交易的引擎。它目前的功能范围包括以太币（ETH）和ERC20代币的隐私交易。zkSync建立在ZK Rollup架构上。zk Rollup 的本质是将链上的用户状态压缩存储在一棵 hash 树中，并将用户状态的变更转移到链下来，同时通过 zkSNARK 的证明来保证该链下用户状态变更过程的正确性。在链上直接处理用户状态的变更成本是比较高的，但是仅仅利用链上的智能合约来验证一个零知识证明的 PROOF 是否正确，成本是相对低很多的。另外必要的转账信息也会被和证明一起提交到合约，方便用户查账。用户具有存款、转账、取款等动作。通常，资产位于L1之上，经过存款动作即为将资产转移至Rollup L2。位于Rollup L2之上的字长方可转移。

step1 准备工作

https://github.com/matter-labs/zksync/blob/master/docs/setup-dev.md

Docker、node（10.20.1以上，版本以10为基准，不建议11 或者12 ）、Yarn、Axel、gnu-sed、Envsubst、Rust、JQ、PSQL、Diesel、solc、drone cli都是必须要安装的。

1.1 环境配置：

讲下面的环境变量加入shell profile，以zsh为例：

1
2
3
4
5
6
# Add path here:
export ZKSYNC_HOME=/path/to/zksync
export PATH=$ZKSYNC_HOME/bin:$PATH

# If you're like me, uncomment:
# cd $ZKSYNC_HOME

ZKSYNC_HOME 是zksync项目的目录即可，例如/home/will/documents/zksync/ 。

1.2 zshrc 配置

1
2
3
echo "fpath=(~/.zsh_comp $fpath)" >> ~/.zshrc

mkdir -p ~/.zsh_comp

1.3 制作命令文件

1
2
3
4
5
#compdef zksync

cmds=( ${(uf)"$(grep -oE '^[a-zA-Z0-9_.-]+:([^=]|$)' $ZKSYNC_HOME/Makefile | sed 's/[^a-zA-Z0-9_.-]*$//')"} )

_describe 'zksync make cmds' cmds

1.4 source zshrc 文件后，zksync命令即可用。

step2 zksync设置本地开发环境

2.1 初始化

1
zksync init

首次初始化需要一次性下载 8 GB 的配置文件。如遇到初始化问题，请参看zksync plonk-setup 命令。本人网速580KB/s的情况下，接近4个小时完成下载。

Posted on Edited on

将可聚合子向量承诺应用于无状态加密货币 ==> https://eprint.iacr.org/2020/527.pdf

0.摘要

可聚合子向量承诺（aSVC, An aggregatable subvector commitment）方案是一种向量承诺（VC）方案，可以将多个证明聚合到单个小的子向量证明中。本文中，我们对aSVC进行了形式化处理，通过恒定大小的多项式承诺，给出了素数阶组的有效构造，并使用它来引向高效的无状态加密货币。

aSVC支持：

  • 在 O(n log n) 时间内计算所有n个 O(1) 大小的证明

  • 在 O(1) 时间内更新证明

  • 将b个证明汇总到 O(1) 大小的子向量证明，时间为 O(b log2 b)。

重要的是，我们的方案具有 O(n) 大小的证明密钥，O(1) 大小的验证密钥和 O(1) 大小的更新密钥。相比之下，先前在素数阶组中具有恒定大小证明的方案：

  • 需要 O(n2) 时间来计算所有证明

  • 需要 O(n) 大小的更新密钥来更新 O(1) 中的证明时间

  • 或不支持汇总证明。

    此外，基于隐藏顺序组的方案：

  • 具有更大的具体证明大小和计算时间

  • 不支持证明更新

我们使用aSVC具有非常低的通信和计算开销，在此基础上，构建无状态加密货币。 具体来说，大小固定的可聚合证明将每个块的证明开销减少到一个组元素。 相反，以前的工作需要O(b log n)组元素，其中b是每个块的交易数。 此外，较小证明将区块验证时间从O(b log n)配对减少到只有两个配对和O(b)大小的多幂运算。最后，与先前工作中的O(b log n)相比，aSVC较小的更新密钥仅占用O(b)区块空间。同样，它们的可验证性将矿工存储从O(n)减少到O(1)。最终结果将是一种无状态的加密货币超过了现有技术。

1.介绍

在无状态加密货币中，矿工和加密货币用户都不需要存储完整的区块链。取而代之的是，使用经过身份验证的数据结构（ADS, authenticated data structure）对由用户帐户余额组成的区块链状态进行身份验证。这样，矿工仅存储区块链状态的简要摘要。 尽管如此，矿工仍然可以验证用户发送的交易，这些用户现在提供了他们有足够余额的证明。 此外，矿工仍可以提议新的区块，并且用户可以在新区块发布时轻松地同步或更新其证明。

由于无状态加密货币的诸多优势，已引起越来越多的关注：

  • 针对摘要的无状态事务验证要比针对已存储数据库的有状态验证更好地扩展
  • 无状态加密货币消除了矿工或整个节点验证区块所需的数百GB的存储空间
  • 无状态性通过允许矿工有效地从一个碎片切换到另一个碎片，使碎片变得更加容易
  • 由于验证块是无状态且高效的，因此任何人都可以成为完整节点，从而产生更具弹性的分布式加密货币

先前的工作显示了如何使用RSA累加器或Merkle哈希树有效地获取基于UTXO的无状态加密货币。但是，对于基于帐户的加密货币，当前的解决方案要么具有比理想的证明大小大的值，要么基于隐蔽的组，而后者实际上要慢一些。因此，本文的重点是改善基于帐户的无状态加密货币的具体和渐进复杂性。（在[Zah18，But16，Cor16，Pat17，Eth17，Yan16]中深入讨论了基于帐户和基于UTXO的设计的优缺点。）

向量承诺（VC）中基于帐户的无状态加密货币。先前的工作开创了在任何矢量承诺（VC）方案之上构建基于帐户的无状态加密货币的想法。在较高级别，VC方案允许证明方计算向量v = [v0, v1, . . . , vn−1]的简洁承诺c，此处具有n个元素，其中vi∈Zp。重要的是，证明者可以生成证明πi，证明vi是v中位于位置i的元素，并且任何验证者都可以根据承诺c对其进行检查。

证明者需要证明密钥prk来提交向量并计算证明，而验证者需要验证密钥vrk来验证证明（通常|vrk| << |prk|）。某些VC方案支持更新：如果向量中的一个或多个元素发生更改，则可以有效地更新承诺和证明。 为此，需要绑定到更新位置j的更新密钥upkj。证明，验证和更新密钥一起被称为VC的公共参数。

1.1本文的贡献

如果基础VC具有：

  • 具有亚线性时间验证的亚线性大小的可更新证明

  • 可更新承诺

  • 亚线性大小的更新密钥

则可以从VC有效地构建无状态加密货币。我们说这样的VC方案具有”可扩展的更新”。不幸的是，大多数VC没有可伸缩的更新，或者如果具有，它们的证明和更新密钥大小也并不理想。最后，虽然可以通过可伸缩的更新来增强隐藏顺序组中的方案，但是其具体性能与原始顺序组中的方案不匹配。在本文中，我们提出了一种具有可扩展更新的新型VC，它具有最佳的证明大小，并使用它来构建有效的无状态加密货币。

具有可伸缩更新的可聚合子向量承诺（aSVC）。 我们提出了可聚合子向量承诺（aSVC）的新概念，即支持承诺更新，证明更新以及将证明聚合为子向量证明的SVC。 然后，我们构建了一个在配对友好组上具有可伸缩更新的aSVC。 我们的aSVC在多个方面都优于以前的工作：

  • 具有恒定大小的 I-subvector 证明：一组元素。
  • 具有恒定大小的更新密钥：两个组元素（或在无状态加密货币设置中使用时，一个组元素）
  • 它可以在O(1)时间内更新证明和承诺
  • 它可以使用O(|I|)幂和O(|I| log2 |I|)场运算将多个证明快速聚合为 I-subvector
  • 我们的aSVC可以通过用于多项式承诺的预计算证明的新技术，在O(n log n)时间内快速计算所有证明

Vitalik提出一个新思想：使用部分分数分解来聚合多项式承诺中的证明。我们不仅使用此功能来汇总证明，还可以减少更新密钥的大小。此外，为了证明aSVC的安全性，我们必须加强KZG多项式承诺的安全性定义，并证明它们仍然可以满足aSVC。最后，aSVC可用于通过有效更新，可更新的基本零知识数据库，匿名凭证和无状态智能合约验证来改进可验证的数据库。

以下内容转自 ==> https://mp.weixin.qq.com/s/ifelfFEsHc71SijQ5MC4jQ

不需要账本就能记账听上去不可思议，但其思路是简单的：在以前，节点有账本，一笔交易来后它翻看账本，查询交易是否合法；在以后，节点没有账本，交易发送方在提交交易的同时需要提交一个密码学证明（为了区分，后文特指密码学证明时都用proof表示），自己证明自己的这笔交易是合法的。

可出块节点为什么能够通过一个proof来判断某笔交易是否合法？这里涉及到两个密码学的重要概念，第一个叫「成员证明」。它指的是通过某种方法，证明个体是群体的一部分。如果能够证明某个账户状态是整个账本状态的一部分，出块节点当然就能相信这个账户状态，并以此为根据进行交易合法性的判断。第二个叫「向量承诺」，它可以将群体，不管这个群体有多庞大，压缩成仅仅一个数，然后给出成员证明，该成员证明表明的是某个个体是属于这个数背后所关联的群体的，且能证明个体在群体中的位置，以及进行证明的更新。

可聚合子向量承诺（aSVC）的工作过程是这样的：

  1. 初始化分片，即在账本建立时确定账户的初始情况。假设某个分片建立时有100个账户，这些账户都有初始的余额，我们需要用v(i)代表第i个账户，它是（地址i，余额i）这样的一对值；用V代表全部账户，它是（地址1，余额1）（地址2，余额2）……（地址100，余额100）这样的一组值。同时需要生成两个值，第一个叫c，它是对V的承诺，代表的是此时该分片所有账户和账户里的余额。出块节点手中都握有c，（可以对比Merkle树根来便于理解），它是将来用于验证的摘要。第二个叫π(i)，它是对v(i) 是V的成员的证明，代表第i个账户及该账户的余额是在总账本V中。每个账户都握有且只握有自己的π(i)，它是将来发送交易时提交给出块节点的proof。在初始化阶段，承诺和证明的生成是需要初始「状态」的。

  2. 第一笔交易。账户 i 发起整个分片的第一笔交易，此时它需要把π(i)和交易一起提交给出块节点，出块节点对π(i)进行计算，看结果是否与自己手中的c相符合，如果一致就可以相信发送方账户确实有多少余额，并以此判断它提交的交易是否合法。

  3. 接下来是关键之处：对c和π(i)进行更新。

c（对整个账本的承诺）不再是根据状态生成，它是用第一笔交易发生之前的c，以及第一笔交易引起的余额变动生成的；π(i)（账户对自己的证明）也不是根据状态生成，它是用第一笔交易发生之前的π(i)，以及第一笔交易对该账户的改变生成的。

在完成c和π(i)的更新之后，出块节点手中便有了可以承诺所有用户新余额的新承诺（新c），账户手中也有了可以证明自己新余额的新proof（新π(i)）。

以此类推，每笔交易都会改变一次c，改变一次全部π(i)，但这种改变不再依赖于状态数据，它取决于旧的c和π(i)，以及上一笔交易；当需要验证一笔新交易时，出块节点手中总有最新的c，它通过c和账户提供的π(i)就能判断某笔交易是否合法，是否可被打包进区块。

那么到这一步，就终于实现了「不需要账本就能记账」，不管对于出块节点，还是对于账户，它们手中握着的都是某种密码学的证明，而不是账本的状态。另需一提的是，无状态与分片似乎是绝配，但无状态并不是针对分片的一种设计，它是针对公链的一种设计。

aSVC的设计目标是要成为一个高效的成员证明，降低上述过程中的通信开销和计算开销，使得这种方案可用于无状态区块链的实现。从论文来看，使用aSVC方案，c和π(i)的大小仅为几十个字节，π(i)的更新时间为O(1)，验证时间也为O(1)，该方案还支持把多个proof聚合为一个O(1)大小的proof，这种低开销的实现正是aSVC的意义所在。不过就像Vitalik在以太坊研究者论坛中展开的相关讨论，aSVC还需要做进一步的优化。

文章的最后是对全文的简要总结：分布式系统的状态分片设计与密码学的成员证明设计相结合，实现以太坊2.0在性能上突破。

  1. 为了安全，以太坊2.0的状态分片需要随机分配出块节点。

  2. 如果出块节点需要账本，账本同步会成为新的性能瓶颈，账本存储也会影响PoS的去中心化。

  3. 是否有不需要账本就能验证余额的方式？

  4. 第一个思路转变：把查找账本的方式改为证明账本的方式。这需要借助于密码学来完成。

  5. 第二个思路转变：把证明账本状态的方式改为证明交易行为的方式，实现无状态和无需账本的记账。这需要借助于密码学来完成。

  6. 密码学的工具有很多，当有了目标后，需要根据应用需求选择和组合适当的工具形成方案，并对方案进行优化。

在文章中我们用自然语言描述了aSVC的工作，如果你感兴趣，可以通过aSVC 的API定义来更清晰地了解它。如下图所示：第一个红框是初始化时生成承诺c，第二个红框是根据交易更新c；第一个绿框是初始化时生成证明π(i)，第二个绿框是根据交易更新π(i)；蓝框是出块节点用c和π(i)做验证。

在上述过程中，最核心的工作是**根据交易引发的变动把旧的c变成新的c，把旧的π(i)变成新的π(i)**。不但要能够完成更新，且这种更新的开销是可以被接受的，这是aSVC要解决的关键问题。我们以c的更新为例来介绍aSVC是如何做的。

如前文所述，c承诺的是V，从c到新c，实际上就是从承诺V到承诺一个新的V。对V来说，它是由一系列的点构成的，（地址1，余额1）是一个点，（地址2，余额2）是另一个点……（地址100，余额100）是第100个点。

借助于拉格朗日插值法，可以把这一系列的点变成一个多项式（该多项式代表的曲线经过所有这些点），这意味着可以把对一系列点的承诺变成对一个多项式的承诺；从c到新c，也就等价于从承诺一个多项式到承诺另一个多项式。

而多项式有着各种神奇的属性，对多项式及多项式变换的承诺可以是小的、快速的。那么通过这种从点到多项式的转化，就可以把c的更新开销变为可接受的。

但这只是对aSVC方案思路的一个简单、片面的介绍，在该方案中还使用了诸多其他工具和方法，而且它依然在追求更好的设计。

如果你想更多的了解它，可以去阅读原论文，其中的3.1节和4.1节是最有助于理解整篇论文的部分。

Posted on Edited on

Scalable，transparent， and post-quantum secure computational ==> https://eprint.iacr.org/2018/046.pdf 部分内容翻译：

0 介绍

可扩展式验证的计算完整性，超过密文数据集

本文讨论的问题基于如下假设：想象警察 Police(P) 是负责国家法医DNA档案数据库 database(D)，声称一个即将任命(或者据称可能发生腐败案)的DNA档案文件 profile(p)没有出现在D中。加密协议能否说服怀疑者相信警察的声称，并且不进入D或p，不依赖于任何外部信任方（例如，首席大法官）和具有”合理”计算资源？

DNA配置文件匹配 (DNA profile match, DPM) 示例是一个普遍问题的特殊情况。某一方(party, P)在数据集(D)上执行计算(C)能会有错误报告，而不是正确输出 (C(D))，提出了计算完整性问题 (computational integrity ,CI)，以确保P确实报告C(D)。当数据集 D 是公开时，任何有兴趣验证 CI 的一方 (verifier, V) 都可以在 D 上重新执行 C 并将其输出与 P 报告输出进行比较，因为客户可能会检查餐厅账单，或作为一个新的比特币节点将验证其区块链。此原始的解决方案无法扩展，因为验证器 (Tv)花费的时间与执行程序 (Tc)所需的时间一样大，V 必须读取完整的数据集D。基于加密哈希函数的承诺方案常用于计算大型数据集 Dt，t 时刻状态的”指纹”哈希为cmt。通常，与 Dt 相比，cmt 的长度可以忽略不计，作为公告可以很容易地张贴在块链上。但是，CI 的方案中，我们希望解决扩展性问题，也就是增加参数和计算深度的问题，其中验证时间和计算复杂度近似于 logTc 和 |cmt|(cmt的bit长度)，而不是 Tc 和 |Dt|；至少 验证时间/通信 应该严格小于 Tc 和 |Dt|。

当数据集 D 包含机密数据时，无法再实现原始的解决方案，并且负责D的P方可能以保密的面纱隐瞒违反计算完整性的行为。当对机密数据强制实施 CI 的方法则依赖于”受信任方”，例如审计师或会计师代表公众验证计算。此解决方案不提供可扩展，就像数据公开的方案一样。更糟糕的是，它要求公众信任第三方，这创造了一个潜在的协议中的失败点，因为第三方可能违反协议，如收到恶意方贿赂或胁迫。

零知识(ZK)证明和论证系统是取代人工审核员的自动化协议。为了保证计算完整性同时基于机密数据，实现有效的计算，消除腐败并降低成本。ZK系统中，S和计算C是一对随机算法，S=(P, V)；证明人 P 是用于证明计算完整性的算法；验证人 V 检验这样子的证明(proofs)。S 的完整性和健全性意味着 P 可以有效地证明所有真相，但无法说服 V 任何谬论。关于 ZK 系统针对通用计算的可扩展式验证，最早出现在1990年代，基于 Probabilistically Checkable Proofs (PCP) 这一篇论文。PCP 定理提供了一种平衡，证明人构建证明花费的时间(Tp)和验证人验证的时间(Tv)的平衡。这种平衡意味着生成证明的时间多项式式增加(Tp=Tc多项式)，同时验证时间指数式增加(Tv=logTc多项式)。

基于PCP定理（ZK-PCP）的ZK系统具有三个附加优点，这使得公众信任计算完整性至关重要。

(一) 这些构建安全的假设被建造起来了。即交互式解决方案具有抗碰撞哈希函数，非交互式函数具有对随机函数(“随机预言模型”) 的通用访问权限，这些理论基础在目前认为还不会受到大型量子计算机的影响，我们称之为后量子安全(post-quantum secure)。量子计算机规模以及对后量子密码协议的需求都在增长，如，美国国家标准与技术研究院技术(NIST)强调了后量子安全ZK解决方案的重要性。

(二) ZK-PCP是知识证明(proof of knowledge, POK)系统，或者当如上所述实现时，是知识论证(argument of knowledge, ARK)系统。非正式地，在DPM示例的背景下，ZK-ARK是一个证明，使公众相信警察已经使用了“真实的”数据集Dt和总统候选人DNA配置文件p，总统候选人的承诺是先前已经宣布过的。

(三) 最重要的是，ZK-PCP是透明的 (或“公共随机性”)，这意味着验证者使用的随机性是公共的。特别是，与更加新一些的ZK解决方案（包括Zcash加密货币使用的解决方案）相比，ZK-PCP不需要外部受信任的设置阶段。透明性对于能否取得公众信任至关重要，因为它限制了当事人P滥用系统的能力，因为，只要在可观察的宇宙中存在不可预测的事物，透明的系统就是公众可能会信赖的系统。

综上所述，ZK-PCP是确保公众对机密数据CI信任的最佳方法，并具有六项核心优点。

(一) 透明性；

(二) 普遍性—适用于任何有效的计算C，即使它需要上述Dt之类的辅助输入；

(三) 机密性，即零知识性(ZK)—请勿破坏Dt等辅助输入；

(四) 后量子安全；

(五) 基于知识的证明(或者论据)；

(六) 可扩展的验证。

虽然 ZK-PCP在上个世纪90年代已经被知晓，但并没有被实现，因为“PCP定理产生的证明既漫长又复杂，以至于要花费数千年的时间来生成和检验它们，并且将需要比宇宙中原子更多的存储位”。ZK系统在为通用计算的努力过程中，仍没有完全实现 (一) — (六) 的替代技术上，尽管某些算法对于某些具体的电路尺寸和计算开销是有效的。

1 本文的主要贡献

我们在IOP(Interactive Oracle Proofs)模型中提出了一个（双重）可扩展和透明的ZK系统的新结构（Scalable Transparent IOP of Knowledge, ZK-STIK）。我们将该系统实现为ZK-STARK，并将其应用于概念验证POC“有意义”的计算，该计算本质上是高度顺序的，如前面介绍的DPM问题。我们实现了如下两点：

(一) 验证时间严格小于原始运行时间 (Tv<Tc)

(二) 通信复杂度严格小于见证人大小

本系统中核心创新和改进性能的主要来源是对IOP模型的扩展，包括快速FRI (Fast Reed-Solomon (RS) IOP of Proximity (IOPP)) 协议，这里的IOP是 Interactive Oracle Proofs，还有一个新的算法规程。我们强调，验证时间和验证大小适用于为任意见证者定义的任何计算，尽管加速实现的具体点取决于计算的复杂性。

DNA档案匹配计算

ZK-STARK是一个“有意义”的概念验证(POC)，特别适用于DNA档案匹配问题(DNA profile match (DPM))。该计算做出了以下场景假设：假设警察(充当证明人P)负责国家法医DNA档案数据库(D)，并且在先前时间的t，发布数据库状态Dt(例如，在区块链上)隐藏承诺cmt。警察现在声称，即将任命的和据称腐败的总统候选人的DNA档案p没有出现在Dt中，因此希望以可扩展的方式创建一个有说服力的证据，使得公众认为DPM计算正确无误，并且警方报告的输出(关于p和Dt)是正确的。

在超过50个国家/地区中使用的DNA图谱的主要标准是联合DNA索引系统(CODIS)格式； 根据该标准，个人由其DNA的短串联重复序列(STR)表示，针对一组20个“核心基因”进行了测量。假定对CODIS数据库状态Dt的承诺(commitment) cmt是公共信息(如，在时间t，公开于区块链之上)，对于总统候选人简历p的承诺是cmp。我们假设p是由独立实验室提取的，然后在公开发布cmp时将其(秘密地)交给了警察。 假设警察宣布：

“该值a是在具有承诺cmt的数据库中，对具有承诺cmp的档案文件进行匹配搜索的结果”

答案是三种可能性之一：“不匹配”，“部分匹配”或“完全匹配”。公开(开源)计算C是将由可信任的第三方执行的用于验证上述声明的计算。此计算需要三个公共输入(cmt, cmp和A)，以及两个机密输入：DNA文档数据库D’和个人DNA文档文件p’。当且仅当公共输入(cmt, cmp, A)和机密输入(D’, p’)满足以下三个条件时，计算C则成功终止：

(i)针对机密输入D’的承诺cm’与公开输入cmt相等；

(ii)针对机密输入p’的承诺cmp’与公开输入cmp相等；

(iii)在机密数据集D’中对机密输入p’进行匹配搜索后，得到输出则会公开宣布结果a.

令|D(n)|为数据集D(n)的比特长度，n为DNA档案的条目数量(每条档案为40字节长度)。令CC(n)为ZK-STARK的通信复杂度，数据集仍然为D(n)，例如，在证明人与验证人之间，总的通信比特值。令Tc(n)为原始验证计算C在D上执行时，数据量为n时，所耗费的时间。令Tv(n)为V验证所耗费的时间。以上时间是同为一台物理服务器上测试所得。

2 讨论 — 权力下放的社会职能的应用

以比特币为首的加密货币通过建议完全分布式的货币体系来代替法定货币，加密货币同时正在破坏已建立的金融系统。 金钱只是可以分布式的社会功能之一，法律合同已经被以太坊区块链中的自动智能合同取代。 在本节结束时，我们将讨论ZK-STARK系统对分散式公共分类账的两个预期影响。

可扩展性

现如今，在区块链中进行了激烈的讨论，围绕着适当的方式来扩展交易吞吐量，而又不会增加参与网络的节点的时间和空间。正如其中一位作者首次指出的那样，并且最近被数种加密货币计划所采用，完全可扩展的证明系统(即使没有零知识)也可以通过成倍地减少验证时间来解决可扩展性问题。更详细地讲，单个“证明人节点”可以在准线性时间内生成一个证明，该证明将说服其他节点接受账本当前状态是有效的，而无需那些节点原始地重新数据库查询计算，也不需要存储整个区块链的状态。

隐私性

ZK证明的保密性已被用于增强加密货币的互换能力和隐私能力。最近在Zcash加密货币中实现并使用一种特殊的零知识证明，即ZK-SNARK，它基于密码学指数知识(knowledge of exponent, KOE)的假设，以完整地维护其条目的分布式注册表，该注册表隐藏着未动用资金的承诺。

ZK-SNARK(zero-knowledge succint non-interactive arguments of knowledge。Zero knowledge：零知识证明；Succinctness：证据信息较短，方便验证；Non-interactivity：无交互，证明者基本上只要提供一个字符串义工验证。对于区块链来说，这一点至关重要，意味着可以把该消息放在链上公开验证；Arguments：证明过程是计算完好（computationally soundness）的，证明者无法在合理的时间内造出伪证（破解）。跟计算完好对应的是理论完好（perfect soundness)，密码学里面一般都是要求计算完好；knowledge：对于一个证明者来说，在不知晓特定证明 (witness) 的前提下，构建一个有效的零知识证据是不可能的。

ZK-SNARK是不是透明的，因为它们需要一个“设置阶段setup phase”，该阶段使用了非公开的随机性，如果受到损害，则可以用来损害系统的安全性。展望未来，ZK-STARK可以替代ZK-SNARK，透明地实现Zcash的可替代性和机密性。当前，ZK-SNARK比ZK-STARK证明size小约1000倍，因此用ZK-STARK替换ZKSNARK还需要进行更多的研究以缩短证明长度，或者使用可增量验证的计算来汇总和压缩多个ZK-STARK证明。例如，ZK-SNARK的证明size为几百bytes，ZK-STARK的证明size为几百Kbytes。

3 与其他的ZK系统相比较

hPKC — Homomorphic public-key cryptography 同态公钥密码，如Pinocchio和libSNARK。

DLP — Discrete logarithm problem 离散对数问题，如BulletProofs。

IP — Interactive Proofs 交互式证明。如Hyrax。

MPC — Secure multi-party computation 多方安全计算。如ZKBoo、Ligero。

IVC — Incrementally Verifiable Computation 增量可验证计算。如hPKC-based IVC。

具体测试指标

测试均基于同一个硬件服务器，基于同样的DPM问题。

Arithmetic circuit complexity as standard measuring yard — 算术电路复杂度作为标准测量场。此处测试的所有系统(包括ZK-STARK)均为算术化之后的运算，将计算完整性(CI)语句简化为相关的有限域上的低次多项式系统。我们强调ZK-STARK也可以在素数场上运行，但代码中尚未实现。

在DPM计算中，数据库中具有n条数据，算术电路的参数如下：

总结

在上述以对照的方式进行测试，ZK-STARK是测量的所有电路尺寸中生成证明最快的，特别是与libSNARK相比较，速度快了近10倍。在小电路情况下，ZKBoo和Ligero的通信时间更短，验证更快。在深度较小的电路的情况下，Hyrax的通信时间更短，验证更快。在同一固定电路上多次重复的计算，BulletProofs, Pinocchio, libSNARK的通信时间更短，验证更快。但是，对于一般的大规模计算，ZK-STARK的验证时间和通信复杂性优于其他透明系统。换句话说，我们对ZK-STARK的实践表明，对于实际相关的具体计算(例如DPM)，已经充分体现了完全可伸缩性和透明性的优势，并表明我们的系统类型对于构建可伸缩性解决方案很有用， 例如，用于分布式的加密货币。