当前位置:  首页 →区块链百科 →正文

比特币PoW的基石——随机性

2018-12-12 14:35:45 华尔街之狼

比特币的共识机制是PoW,是工作量证明。在矿工中,谁有权来记账?是通过选举的方式?还是通过谁拥有的token更多的方式?而比特币采用了计算谜题的方式,谁的算力大,谁就更有可能获得解,谁就能够获得记账权。而在这个算力证明的背后,是基于随机性原理。

比特币的随机性

随机性是构成比特币PoW的基石。但我们是如何到这一步的?

 

随机性研究简史

随机性一直是生活中不可或缺的一部分。很多古老的占卜仪式都是基于偶然性的:希腊人抛掷黄芪(动物指关节),中国人求签,西非人用占卜链。在游戏和博彩中使用类似于骰子的设备有几千年的历史了。

然而,直到16世纪,我们才开始获得必要的工具和语言,用以理解偶然性和随机性。这些工具包括算术概念,比如分数和零数。

我们对偶然性和随机性的研究始于一位名为Gerolamo Cardano的人。Cardano于1501年出生于意大利,他知识渊博,是文艺复兴时期最具有影响力的数学家之一。他也是出名的赌博上瘾者。由于他沉迷赌博,Cardano最终陷入贫困和泯然于众人。然而,他在赌博方面的经历,促使他最终撰写出一本名为“偶然性游戏的书”。(译者注:这是市值前十的Cardano项目取名的原因吗?用文艺复兴时期数学家命名的?是巧合还是?有谁知道?)

这是第一本系统性阐述偶然性和随机性的书籍。有意思的是,Cardano并没有打算出版,选择保密。在他去世很长时间,直到撰写后的一个世纪才得以出版。

在理解偶然性和随机性方面,Cardano的主要贡献在于提出样本空间的概念。在最基本的层面上,计算事件的概率涉及计算简单的任务,这些任务主要是计算可能导致所述事件的场景数量。然后,将其除以所有可能场景的总数(也就是所谓“样本空间”),同时假设所有场景可能性一致。这种假设只适用于掷骰子等问题,但这也是一个不错的开始。

在Cardano之后,伽利略和帕斯卡也进入这个领域。伽利略是那个时代反叛知识精神的完美体现:跟强大的天主教会对立,他宣称地球不是宇宙的中心。伽利略出版了很多重要著作。其中一本不太知名的著作是“关于骰子游戏的思考”,其中探讨了Cardano所关注的类似主题。

帕斯卡跟费尔马和笛卡尔是同时代的人,他在这个偶然性和随机性领域比Cardano和伽利略研究更深入。他发现了所谓的“帕斯卡三角”(译注:在中国称为杨辉三角,中国南宋数学家杨辉在1261著述中提到该规律。)

尽管其他文明的数学家(比如伊朗、中国和印度)比帕斯卡更早发现相同的三角形,但帕斯卡的工作最全面且增加了创新应用,特别是在概率论领域。帕斯卡还阐述了“帕斯卡的赌注”和数学期望的概念。

由于Cardano、伽利略和帕斯卡的努力,我们对偶然性和随机性的理解逐步提升,并随着时间的推移变得更加复杂和精致。这是文艺复兴时期的一个共同主题:一些底层的突破——比如占星术、牛顿物理学、微积分、经验主义等,这些奠定了科学的基础,并带来了新的知识分支以及重大的技术革新,最终导致了工业革命。

在我们剖析偶然性和随机性的过程中,以下是值得注意的里程碑列表:

l 样本空间

l 排列和组合

l 帕斯卡三角

l 大数定律

l 小数定律

l 贝叶斯定律——条件概率

l 钟形曲线和标准偏差

l 回归均值

l 随机漫步

l 蒙特卡罗模拟

l 伪随机性

两个主要的发展很突出:蒙特卡罗模拟和伪随机性。特别是因为它们在当今世界中具有高度的相关性。

计算机的发明为随机性的全新应用打开了一扇门:计算机模拟。有史以来第一次,我们有一种“预测”未来的方法,或通过廉价的实验揭示隐藏的真相。机器提供的大量模拟在以前是不可想像的。

20世纪早期蒙特卡罗模拟的发明标志着人类历史的一个重大转折点。在文艺复兴之前,人类经常处于对随机性和不确定性的恐惧之中。直到20世纪,我们慢慢开始逐步提升,以更好得理解它,但仍然在很大程度上让随机性决定了事物的流动。通过蒙特卡罗模拟,我们开始让随机性为我们工作。学徒已经成为大师。

蒙特卡罗模拟的早期开拓者包括John Von Neumann和Alan Turing,两位都是现代计算机的教父。

如今,蒙特卡罗模拟有很多应用:流体力学、商业、金融、人工智能等。最近案例有AlphaGo,它就是很好的案例,它显示了蒙特卡罗模拟和其他技术结合后,可以给我们带来新的发现:AlphaGo能够用完全超出我们想象的举动来击败最好的人类选手。AlphaGo挑战了机器不可能有创造性的这一想法,并迫使我们重新思考什么是“创造力”的含义。

蒙特卡罗方法的日益普及刺激了“伪随机性”的发展,(伪随机过程是指过程看似是随机的,但实际上它不是。)因为好的模拟需要能够密切反映现实的随机性。这个过程产生的数字是确定性的,但它们通过了被认为是“随机”的统计测试。反过来,伪随机性成为一个全新领域的基石之一——也是计算机时代的一个孩子——现代密码学。

这将我们带到了比特币。

 

随机性在比特币中扮演的角色

比特币的一项主要创新就是使用工作量证明来构建分布式共识。PoW提供了一个客观的尺度,通过这个尺度,比特币网络的参与者可以达成共识,而无须相信网络上的任何人。它跟PoS机制不同,PoS依赖于对共识的主观解释。

PoW中的W(work)涉及到寻找哈希输出,该输出具有最小前导零数。(哈希输入有一些限制,例如格式化、时间戳等。)

比特币PoW机制使用的加密哈希函数称为SHA256。加密哈希函数的一个重要特征是它们是单向的。这意味着仅通过哈希输出来推演哈希输入是不可行的。它们是单向的原因很大程度上是因为哈希输出的随机性。

这证明是非常关键的,因为如果哈希功能不能产生足够的随机(“伪随机”)输出,那么,就可以从所需的输出开始,也就是:具有特定数量的前导零的字符串,并从那里向后开始工作。这将使得“证明”最好情况下是不可靠,最坏情况下是无用。

简单来说,典型PoW的机制所做的是(a)它提出一个问题,该问题的解存在于非常巨大的范围内,(b)没有捷径,且(c)找到解的唯一方法是使用暴力计算和随机搜索这个巨大的范围。就像在巨大的干草堆中寻找针一样。(计算机科学的官方术语是:“无限概率迭代程序”——相当拗口)

由此,哈希函数的随机性决定了证明(proof)有多强。

 

哈希(提供)→随机性(支持)→工作证明

“...好的谜题给予每个矿工赢得下一道谜题的机会,而机会与他们贡献的哈希算力总量成比例。想象一下,随机投掷飞镖,而标靶大小跟矿工持有的算力相对应。”——Arvind Narayanan

没有正式的证据表明,随机性是PoW的强制性要求。但是,从经验上看,这似乎是正确的。还有一个简单观察,就是说任何问题,如果它的解是非随机的,往往需要花费努力去验证,而首先计算解的所耗费努力也一样多。任何这样的机制都会导致扩展性受限制(请记住,比特币很难扩展)。它会不成比例地偏好最快的矿工——而稍微慢一些的矿工可能一无所得。

基于随机性的PoW的另一个好处是它在挖矿方面是开放的,任何人都可以成为矿工,来去自由。如果他们在一个区块找到后立即加入,或者五分钟之后加入,都没有关系,他们获得下一个区块奖励的机会不会发生变化。

哈希怎么样?它是获得随机性的唯一方法吗?可能不是。除了哈希之外,还有其他方法来模拟随机搜索过程,例如整数分解或离散对数。

因此,哈希很可能不是实现随机性的唯一手段,而随机性是创建数字PoW的必要前提。

PoW方案分两大类:

  • 计算限制:随机搜索受制于处理器速度
  • 内存限制:随机搜索受制于内存访问

关于一个PoW类别是否真的比其他的更好还有待观察,(我个人认为内存限制更糟糕,但潜在机制是一样的:在一个巨大规模的范围内,进行概率和随机的搜索,任何解可以被廉价验证。)

总言之,只要人类存在,我们就会因为随机性和不确定性而挣扎。在20世纪,现代计算和蒙特卡罗模拟发明出来,这第一次使得我们可以把随机性为我所用。在比特币中使用随机性标志着另外一个漫长旅途的里程碑。简言之,工作量证明中的“证明”是由随机性所支持的。如果没有随机性或者真正良好的伪随机性,工作量证明将无效。

如果比特币能够成为未来的货币,它将代表我们迄今为止最重要和最大规模的随机性的应用。

文章来源丨medium.com 编译丨蓝狐笔记

BB财经原创,作者华尔街之狼,转载请注明出处:http://www.bbcaijing.cn/baike/35542.html