我的账户
链视界

关注数字经济、区块链

亲爱的游客,欢迎!

已有账号,请

如尚未注册?

链视界 门户 资讯

a16z:链上可信设置仪式

作者:Valeria Nikolaenko and Sam Ragsdale


可信设置仪式是加密货币社区的痛点,也是兴奋点之一。仪式的目标是产生值得信赖的加密密钥,以确保加密货币钱包、区块链协议或零知识证明系统的安全。这些(有时是浮夸的)程序经常是一个特定项目安全的信任根基,因此正确处理它们非常重要。

区块链项目以许多创造性的方式举行仪式,涉及blowtorches、radioactive dust、airplanes,但所有这些都有一个共同点:它们都涉及一个集中的协调人。通过这项工作,我们展示了如何通过用智能合约取代中心化的协调者来分散这一过程。此外,我们正在开源一个库,允许任何人在以太坊链上运行这样一个仪式(被加密货币从业者称为Kate-Zaverucha-Goldberg——KZG)或 “power-of-tau ”仪式。任何人只需支付交易费用即可参与!

我们的去中心化方法有局限性,但它仍然是有用的。由于目前链上数据的限制,加密参数的大小必须保持简短,即不超过64KB。但参与者的数量没有上限,人们可以永久地继续提交贡献。这些短参数的应用包括小型零知识SNARKs、数据可用性采样和Verkle树。

可信设置仪式的历史和机制

在一个典型的可信设置仪式中,一群参与者将合作生成一组加密参数。每个参与方使用本地生成的秘密信息来生成有助于创建这些参数的数据。正确的设置可以确保秘密不被泄露,秘密只在协议指定的范围内使用,并且这些秘密在仪式结束时被完全销毁。只要仪式中至少有一方表现得诚实,不被破坏,并销毁其本地秘密,整个设置就可以被视为安全。(当然,这是假设数学是正确的,代码没有错误)。

一些最突出的仪式是由Zcash举办的,这是一个面向隐私的区块链项目。这些仪式的参与者产生了公共参数,旨在让Zcash用户构建和验证私人加密货币交易。六个参与者在2016年进行了第一个Zcash仪式,即Sprout。两年后,加密货币研究员Ariel Gabizon(现在是Aztec的首席科学家)在仪式的设计中发现了一个毁灭性的漏洞,这个漏洞是由一篇基础研究论文继承下来的。该漏洞可能使攻击者能够在不被发现的情况下创造无限的Zcash币。Zcash团队将这个漏洞保密了7个月,直到系统升级,Sapling(其仪式涉及90名参与者)解决了这个问题。虽然基于安全漏洞的攻击不会影响用户的交易隐私,但无限造假的前景破坏了Zcash的安全前提。(理论上不可能知道是否发生了攻击)。

另一个值得注意的可信设置的例子是主要为Semaphore设计的永久“power-of-tau”仪式,这是一种用于以太坊匿名信令的隐私保护技术。这个设置使用了BN254椭圆曲线,到目前为止有71个参与者。其他著名的项目后来使用这个设置在上面运行他们自己的仪式,包括Tornado.Cash(最近被美国政府制裁),Hermez网络,和Loopring。Aztec在BLS12_381椭圆曲线上为zkSync运行了一个类似的仪式,有176名参与者,这是一个“第二层”以太坊扩展解决方案,使用零知识rollups。Filecoin,一个去中心化的数据存储协议,在第一阶段和第二阶段分别有19和33个参与者,进行了一个分叉原始回购的仪式。Celo,一个第一层区块链,也为他们的轻客户端Plumo举行了一个仪式。

永久的仪式对参与者的数量没有限制。换句话说,不是信任其他人来运行一个可信的设置仪式,而是任何人都可以参与,以满足他们对安全的任何程度。一个值得信赖的参与者确保了所有结果参数的安全;这个链条就像它最强大的环节一样强大。正如其名称所暗示的那样,永久仪式可以永久运行,就像最初的“powers-of-tau ceremony”仪式的前提那样。也就是说,项目经常决定他们的仪式有一个具体的开始和结束时间,这样他们就可以把产生的参数嵌入到他们的协议中,而不必担心不断地更新它们。

以太坊计划为即将到来的ProtoDankSharding和DankSharding升级运行一个较小的可信设置仪式。这两个升级将增加以太坊链提供给客户的存储数据量。这些数据将有一个建议的30至60天的有效期。该仪式正在积极开发中,并计划在明年初运行六周。(更多细节见kzg-ceremony-specs:
https://github.com/ethereum/kzg-ceremony-specs/)它将成为迄今为止运行的最大的区块链可信设置仪式。

谈到可信设置仪式,偏执狂是一种美德。如果一台机器的硬件或软件被破坏,就会破坏其生成的秘密的安全性。泄露秘密的偷偷摸摸的旁门左道攻击也很难被排除。例如,一部手机可以通过记录CPU振动的声波来监视计算机的运行。在实践中,由于很难消除所有可能的侧信道攻击,包括那些仍未被发现或披露的攻击,甚至有人提议将机器飞到太空中,在那里举行仪式。

就目前而言,严肃的仪式参与者的游戏规则通常如下。购买一台新机器(未受污染的硬件)。通过移除所有的网卡(以防止本地秘密离开机器)来实现空气隔离。在一个遥远的未公开的地点,在法拉第笼中运行机器(以挫败可能的窥探者)。用大量的熵和难以复制的数据(如随机按键或视频文件)作为伪随机秘密发生器的种子(以使秘密难以破解)。最后,销毁机器(连同任何秘密的痕迹)将一切烧成灰烬。

协调可信的设置仪式

下面是一些以前的可信设置仪式参与者的有趣的引言:

  • “……用blowtorch有条不紊地逐件加热电子产品,直到所有东西都被烧黑……”——Peter Todd 在物理上销毁当地的秘密。
  • “我这里有一块布,上面有来自切尔诺贝利反应堆核心的石墨粉……你每四个脉冲(从连接到微控制器的盖革计数器)计数,你比较脉冲一和二之间的时间间隔以及脉冲三和四之间的时间间隔,如果它更大,你得到一个零,如果它更小,你得到一个一”。 “……我们即将坐上这架飞机,生成我们的随机数……”—— Ryan Pierce和Andrew Miller谈秘密生成。

Zcash power-of-tau仪式第41轮涉及一架飞机。

  • “销售人员说他们有13台电脑。我问我们是否可以从这13台中挑选一台。他问我是否有特别要找的东西(很困惑,因为它们都是一样的),我说我只是想随便挑一个。他说他不能让我们进入后面的仓库。我问他是否可以拿两个出来,这样我们就可以从这两个中挑选一个。他用手推车运出了两台。Jerry从这两台电脑中选择了一台,我们把它带到收银台结账”。 — Peter Van Valkenburgh 谈购买新机器。
  • “仪式的前几个小时是在一个用铝箔和保鲜膜制成的临时法拉第笼里进行的。我把笔记本电脑移出法拉第笼,因为它的通风条件很差,摸起来很热”。——Koh Wei Jie 谈侧面通道保护。
  • “……在山上举行了一部分仪式,没有邻居”。——Micheal Lapinski 谈关于侧通道保护。
  • “我选择使用周围的视频来产生足够的熵”——Muhd Amrullah谈关于随机值的产生。

Zcash联合创始人Zooko Wilcox的弟弟Za Wilcox在2016年破坏了一台用于生成随机数的电脑,用于一个可信的仪式。

所有这些仪式都依赖于一个集中的协调人。协调员是个人或私人服务器或其他一些实体,他们被委托登记和命令参与者,作为中继者,将前一个参与者的信息转发给下一个参与者,并为可审计性目的保留所有通信的集中日志。协调员通常还负责将日志永久地提供给公众;当然,集中式系统总是有可能出现数据丢失或管理不当的情况。(例如,Perpetual-power-of-tau存储在Microsoft Azure和Github上)。

我们觉得很讽刺的是,当去中心化是加密货币精神的核心原则时,加密货币项目必须依赖中心化的可信设置仪式。因此,我们决定展示直接在以太坊区块链上运行一个小型的永续权力的仪式的可行性。这个设置是完全去中心化的,无权限的,抗审查的,而且只要任何一个参与者是诚实的,就很安全(见免责声明)。参加仪式的费用只有29.26万到17.76 gas(按目前的价格计算约为7到400美元),这取决于所需的结果参数的大小(在这种情况下是8到1024个powers-of-tau)。(具体费用见下表——我们在文章后面会更详细地介绍这些计算方法)。

目前,我们建议不要将该代码用于除实验目的之外的其他用途,如果有人发现代码中有任何问题,请向我们报告,我们将非常感激。我们希望收集对我们方法的反馈和审计。

了解KZG或 “power-of-tau “仪式

让我们来探讨一下最流行的信任设置之一,这就是所谓的KZG(power-of-tau) 仪式。这要归功于以太坊联合创始人Vitalik Buterin,他关于可信设置的博文为我们在本节中的想法提供了参考。该设置生成了power-of-tau的编程,之所以被命名为“tau”,是因为“tau”刚好是用来表达参与者产生的秘密的变量。

pp = [[]1, [2]1, [3]1, …, [n]1; []2, [2]2, …, [k]2]

对于某些应用程序(例如,Groth16,一种由 Jens Groth 在 2016 年设计的流行 zkSNARK 证明方案),设置的第一阶段之后是第二阶段,即多方计算(MPC)仪式,为特定的 SNARK 电路生成参数.然而,我们的工作只关注第一阶段。第一阶段——tau 的生成——已经作为通用 SNARK(例如 PLONK 和 SONIC)以及其他密码学应用程序(例如 KZG 承诺、Verkle 树和数据可用性)的基础构建块非常有用采样(DAS)。一般来说,通用 SNARK 参数应该非常大,以便它们可以支持大而有用的电路。包含更多门的电路通常更有用,因为它们可以捕获大量计算; tau 的数量大致对应于电路中门的数量。因此,典型的设置大小为 |pp| = ~40 GB 并且能够支持具有 ~228 个门的电路。鉴于以太坊当前的限制,将如此大的参数放在链上是不可行的,但对小型 SNARK 电路、Verkle 树或 DAS 有用的较小的可信设置仪式可以在链上运行。

以太坊基金会计划为 200 KB 到 1.5 MB 的 power-of-tau 举办几个较小的仪式。虽然更大的仪式可能看起来更好,但考虑到更大的参数可以创建更有用的 SNARK 电路,事实上,更大的并不总是更好。某些应用程序,例如 DAS,特别需要一个更小的应用程序! [原因是非常技术性的,但如果你好奇,那是因为具有 n 次幂的设置(在 G1 中)只能使 KZG-commitments 对次数 ≤ n 的多项式,这对于确保KZG-承诺下面的多项式可以从任何n个评价中重建是至关重要的。这一特性使数据可用性采样成为可能:每次成功获得(采样)多项式的t个随机评价,就能保证多项式能以t/n的概率被完全重构。如果你想了解更多关于DAS的信息,请查看Buterin在以太坊研究论坛上的这篇帖子:
https://ethresear.ch/t/2d-data-availability-with-kate-commitments/8081。

我们设计了一个可以部署在以太坊区块链上的智能合约,以运行一个可信的设置仪式。该合约将公共参数(tower-of-tau)完全存储在链上,并通过用户的交易收集参与。

一个新的参与者首先会读取这些参数:

pp0 = ([]1, [2]1, [3]1, …, [n]1; []2, [2]2, …, [k]2) 。

然后对一个随机的秘密’进行采样,并计算出更新的参数:

pp1 = ([‘]1, [(‘)2]1, [(‘)3]1, …, [(‘)n]1; [‘]2, [(‘)2]2, …, [(‘ )k]2)。

并将其公布在链上,并提供证明,以证明三件事:

  1. 对离散逻辑的了解:参与者知道’。(证明对可信设置仪式的最新贡献是建立在所有之前的参与者的工作之上的)。
  2. pp1的形式良好:元素确实编程了增量权力。(验证了新参与者对仪式的贡献的形式良好性)。
  3. 更新是不递减的:’≠0。(这是为了防止攻击者试图通过删除所有参与者过去的工作来破坏系统。)

智能合约验证该证明,如果它是正确的,它将更新它所存储的公共参数。你可以在repo中找到更多关于数学的细节和它背后的推理。

计算gas成本

在链上运行设置的主要挑战是使可信的设置仪式尽可能地节省gas。理想情况下,提交一个贡献的成本不超过50美元。(大型项目可能会对贡献者的gas进行补贴,在这种情况下,数百名参与者每人花费100美元是比较容易想象的)。下面,我们将详细介绍设置中最昂贵的部分。较低的gas成本将降低贡献成本并允许构建更长的参数(更多的 tau 功率和更大的 SNARK 电路)!

我们的设置适用于elliptic curve BN254(也称为BN256、BN128和alt_bn128),它支持以太坊上的以下预编译合约:

  • ECADD允许添加两个elliptic curve点,即从[]1和[]1计算[+]1:gas成本150
  • ECMULT允许elliptic curve点与scalar相乘,即从a和[]1计算出[a*]1:gas成本为6,000。
  • ECPAIR允许对elliptic curve对的乘积进行检查,即计算e([1]1, [1]2)* … *e([1]1, [1]2) = 1 这相当于检查1*1+ … + k*k = 0 : gas成本34000 * k + 45000

如果以太坊启用BLS12_381(如EIP-2537中的建议),我们的设置合约也可以很容易地适用于这个其他curve。

让我们估计一下更新设置的gas成本([]1, [2]1, [3]1, …, [n]1; []2):

  1. 核实证明的gas成本。每个参与者更新设置,并提交一个有上述三个组成部分的证明。证明的第1和第3部分—“对离散日志的了解 ”和 “更新是不递减的”,验证起来非常便宜。挑战在于如何在链上验证第2部分,即“pp1的良好形式”。它需要一个大的多标度乘法(MSM)和两个配对。
  2. e(0[1]1 + 1[]1 + 2[2]1 + … + n-1[n-2]1, []2) = e([]1 + 1[2]1 + … +n-1[n-1]1, [1]2)。

其中0,…,n-1是伪随机抽样的scalars。就预编译的智能合约而言,需要:

(2n-4) x ECADD + (2n-4) x ECMULT + ECPAIRk=2 = (2n-4) x 6,150 + 113,000 gas。

储存数据的gas成本。每个参与者还将更新的数据存储在链上,作为calldata(每字节68个gas),占n*64*68个gas。(熟悉elliptic curve密码学的人可以注意到:存储压缩的点会使解压缩在整个成本中占主导地位,正如我们对n=256的测量一样)。

这给我们带来了以下的gas成本估算表,应该为未来的优化提供参考:

我们正在探索降低gas成本的解决方案,敬请关注。

开源库:evm-powers-of-tau

我们已经在
github.com/a16z/evm-power-of-tau上公开了我们基于EVM的仪式 repo。用我们的策略举行仪式很简单,也很透明:

  1. 部署存储和验证合约(合约/KZG.sol)。
  2. 贡献者从之前的交易calldata中读取仪式参数
  3. 贡献者在本地生成一个秘密,计算出更新的参数
  4. 贡献者生成他们的证明:pi1,pi2
  5. 贡献者通过KZG.potUpdate()将更新的参数提交给公共区块链上部署的智能合约。
  6. 智能合约将验证更新的有效性,如果提交的参数不符合要求,则会恢复原状。
  7. 多个贡献者可以永久地执行第2-5步,每个人都会增加仪式的安全性
  8. 每当开发人员对提交的数量和质量有信心时,他们可以查询区块链上的当前参数,并使用这些值作为他们的加密密钥

我们的 repo 使用 arkworks-rs 来计算第二和第三步(rust 计算可以在 src/pot_update.rs 中找到),但用户可能想写自己的。整个更新提交的端到端流程可以在test/integration_test.rs的集成测试中找到。

请注意,我们选择使用calldata在链上存储更新的power-of-tau参数,因为它比存储要便宜好几个数量级。在src/query.rs中可以找到一个基于ethers-rs的对该数据的查询。

最后,证明和详细的方程式可以在techreport/main.pdf的技术报告中找到。

未来的工作

在这个可信的设置仪式可以在生产中使用之前,我们建议首先对数学证明和样本实现进行全面审计。

在实施过程中,更新仪式的交易成本随着设置规模的增加而线性增长。对于大多数应用(SNARKs,DAS),我们希望设置n>=256,目前每次更新的成本为73美元。

我们也许能够通过有效更新计算的STARK证明和对更新值的向量承诺来实现亚线性验证成本增长。这种构造也将消除对Ethereum L1 BN254预编译的依赖,使其能够使用更受欢迎的BLS12-381 curve。

所有的仪式策略都是有取舍的。我们认为这种结构是坚实的,并且有很大的可验证的抗审查特性。但是,我们还是要提醒大家不要使用这种方法,直到有更多的工作来验证我们方法的合理性。

鸣谢
  • Dan Boneh–在这项工作的早期阶段提供了有用的反馈。
  • Joe Bonneau – 澄清了技术报告早期版本中的论述。
  • William Borgeaud – 感谢在TurboPlonk/Plonky2中对BLS的讨论。
  • Mary Maller – 对该方法的一般机械性的思考

编辑:Robert Hackett @rhhackett

(扫二维码 入群交流)

相关阅读

区块链百科
微信扫码
行业动态资讯早知道

Copyright © 2022 链视界 粤ICP备2021100744号   Designed by 链视界