技术解读 | 何在不使用工作量证明的情况下实现公平且高效的提议

Taraxa 发布在 链圈子 区块链 海盗号 20072

作者:Steven Pu,Taraxa创始人

前言

在之前的技术解读文章中我们讲到了区块排序的问题。本文我们将继续探索如何在不使用工作量证明(PoW)的情况下实现公平且高效的提议。

 

POW之美

 

Pow是一种简单而又优雅的共识算法。每个节点解决一个简单的加密难题,解答方案通过快速猜测得出,谁第一个猜对就选谁生成下一区块。

就这么简单。

这个简单的算法同时提供了真正的随机性——来进行公平且去中心化的区块提议;一定的延迟——确保有足够的时间来广播,最大程度降低分叉概率;经济上的抵押——通过硬件和电力投资来实现,这样矿工就有既得利益来诚实工作。

那么PoW哪里不好?我们为什么非要搭个不一样的?

 

并行处理是罪魁祸首

早期并排工作的装配线

简单又优雅的PoW机制有一个关键问题,那就是它的难题是可以高度并行处理的。这些难题通常是一个哈希函数,节点只是不停生成随机字符串,用哈希法进行处理,然后看得出的哈希值是否符合特定条件。如果你只是一名玩家(例如一台机器、一个线程),假设你平均能在N秒后猜对答案。但如果你是一百名玩家,那么平均你猜对答案的时间就是N/100秒,因为你可以轻松分配工作。举个例子,假如一共有M种可能的答案,你可以安排玩家1号测试答案1到答案M/100,再安排玩家2号测试答案M/100到答案M/200,以此类推。

在PoW区块链系统中工作的矿工们通常会购买大量的专用电脑,或者专用集成电路(ASIC),并调用程序协调这些ASIC的分工来猜答案,所以平均算下来他们猜中正确答案的速度会快些。随时时间的推移,不同的矿工决定抱团来分担他们ASIC集团的工作,因此就有了矿池。

对于比特币这样的网络,如果矿工猜答案猜得太快,它有一套内部算法可以提高猜答案的难度,最终将出块时间维持在平均10分钟左右一块的速度。因此,矿工猜得越快,谜题难度越大,这样也就激励了矿工通过ASIC提速或者搭建更多的ASIC。

矿机速度越来越快,数量越来越多,消耗的能量也越来越多,直到维护网络的能耗高得离谱。

因此,PoW共识的哈希函数能够并行处理这一事实,是造成其负面经济动机的罪魁祸首。它推动了一场矿工间硬件设备的竞争,消耗了大量的能源。

 

设计目标:随机延迟

所以,如果我们想要设计一套不像PoW那么浪费资源的系统,但同时又能做到随机延迟的话,我们需要达成以下设计目标:
  • 真正的随机性以确保公平与去中心化
  • 延迟不可以通过并行而降低,以最大程度减少能耗
下面我们来看看如何优化:

通过可验证随机函数实现随机性

白噪音就是自然出现的一种随机源

真正的随机性更多的是一个哲学问题。我们在说“随机”的时候,我们真正想要的是“不可预测”。如果我们的机制输出的结果是网络任何参与方都无法预测的,那么我们就认为这个结果是随机的,且是公正的。

许多加密函数似乎都能生成随机输出,例如哈希函数和签名机制。但是,他们并不是专门为了生成不可预测的输出而设计的,且观察者能够在给定足够大量样本的情况下得出模式。

在1999年,一篇由Micali,Rabin和Vadhan撰写的论文发表了,他们描述了一种可验证的随机函数(VRF),这个函数是专门为了生成高度不可预测的输出而设计的。后来,Micali教授成立了Algorand项目,之后该项目核心成员Sergey Gorbunov写了一篇更详细且更容易理解的文章。如果你对VRF的更多技术处理感兴趣,可以参阅上述文章和论文。

在Taraxa的区块DAG架构里,VRF为随机延迟提供了随机性。VRF的输出是:

  • 区块DAG的级别(L):在提议者打包区块时,这里的“级别”就是锚定链的长度+1。所以,如果你是提议者,你计算了当前的锚定链L,发现了你将要搭建幽灵指针(pointer)的边界上的终结块,那么你提议的区块级别就是L+1。需要注意的是,这里的定义与常说的“深度”是不同概念。
  • 最新Period区块的区块哈希(P):这是在区块DAG中最新完成的区块,能够通过一个并行PBFT流程(下一篇文章会详述)实现真正的最终确认。考虑到在边界上提议者尚未接收到最新确认的Period区块(P),所以协议会有一定的容忍,即最新Period区块的上一个区块哈希也是可接受的。
  • 区块提议者的秘密VRF密钥(SK)这个是搭建VRF函数所需要的。这与交易签名机制不同,是专门为每个节点生成用于搭建VRF的。
VRF函数的输出分两块:
  • v是一个伪随机值,用于确定延迟长度。
  • p是一个证明,其他节点可以用其来验证VRF已诚实且正确地执行。可以把它当作一个签名,有了提议者的VRF公钥,任意其他节点都可以轻松确定计算的正确性。
最终,我们可以写成一个简单的方程式:

VRF(L, P, SK) → (v, p)

延迟难度成型函数

在VRF的输出(延迟难度或延迟长度)转换为延迟之前,我们会需要让其形成一定的分布。分布的特征大致如下:
  • 需要有一个最小延迟,因为我们不能让区块立即生成,不然会没有时间进行适当的网络广播
  • 需要有一个最大延迟,因为我们不希望整个网络堵塞,也不希望长时间不生产块
  • 部分提议者速度要快,而剩下一部分要慢,这与合格提议者数量以及整个网络的直径(也就是一个区块到达大多数提议节点所需的时间)有关
因此,最终的成型函数可能是这样的(输入项是VRF的输出项即x轴,输出项是成型后的延迟难度系数即y轴):

 

成型函数

设成型函数为S,我们可以得出以下公式:

S(v) = d

这里d就是下一阶段的难度系数。

 

可验证延迟函数的延迟

Token 像个公交卡,能自身产生价值转移,联盟链没有原生的价值转移。国家打击的是传销盘,但其实还有很多的具有价值的代币,当行业发展和公众认知到一定程度的时候,优质的公链能避免一刀切的状况。等到这个时候,联盟链和公链的合作可能更多

 

独自辛苦独自忙,无人并肩共作战=(

正如本文开头讨论的那样,PoW好是好,但并行处理是其“风评被害”的罪魁祸首。于是,可验证延迟函数(VDF)出现了,这个函数是专门为了模拟无法通过并行处理加速的延迟而设计的。

如果一个函数符合以下两点简单的标准,那么就可以严格将其归为VDF:

  • 必须是顺序的,这种情况下无人能够通过多个并行处理来加快VDF函数的计算,这一点与PoW不同。
  • 必须是可简单验证的,观察者能够简单地进行验证(也就是其用来验证的时间远比计算函数的时间短),确认VDF计算正确且出现的是适当的延迟,这一点与PoW相似。
Boneh et al.,Pietrzak和Wesolowski等人都提出了满足这些标准的VDF。特别是,Pietrzak和Wesolowski都基于在未知顺序的组别里重复平方的原理,各自独立地提出了高度相似的方法,这些方法能够有效抵抗并行处理。

让我们在更高层次测试一下这些函数吧,因为数学是非常复杂的。

这些VDF的构建是执行重复平方的计算,这些计算是无法并行处理的,因为每次迭代都需要上一次迭代的输入,且任何给定迭代中不会提供关于未来迭代的信息。换句话说,除非你一步步完成所有迭代,否则你无法知晓答案。这一点确保了这个函数是顺序的。

而让VDF能够简单验证的是,你可以用包含VDF中间输入与最终输出的随机线性组合来搭建一个证明。这些限线性组合的计算很简单,因为比起计算整个VDF来说,它涉及的步骤要少很多。简单地类比一下就是,计算整个曲线中的所有数值(计算整个VDF)与选个箭头往前推几步(证明VDF的有效性)的差距。箭头前进几步所花费的时间显然比计算少得多。这一点确保了这个函数是可简单验证的。

在Taraxa,我们在VDF中设置了以下几个输入项:

  • 父哈希(gP),或者你新创建的区块通过一个幽灵指针所指向的父区块
  • 所有交易的哈希(Tx),你计划打包到区块中的所有交易的哈希,所以你无法事先计算VDF
  • d,上一步的难度系数
所以,在节点提议区块之前,VDF函数计算长这样:

VDF(gP, Tx, d) = z

在实践中,为了确保对输出项z的验证是非交互的,节点提议者需要将中间证明以及最终输出项插入提议区块中。

所以,对计算VDF函数的节点来说,他们可能会遇到类似这样的延迟(这是个极简的视图,不考虑其他完成有效工作例如打包区块、处理交易等所导致的延迟):

出于解说需要,这是从均匀分布中生成的。

截至撰稿时,VDF仍旧是极具实验性的技术,且正在经历积极的研究与测试。Taraxa会与开源领域最优秀的人以及学术社区合作学习,确保我们的账本采用的是最稳定、最高效、最安全的方案。

本文链接:https://www.8btc.com/media/624055
转载请注明文章出处

文章标签: VDF
评论
登录 账号发表你的看法,还没有账号?立即免费 注册