##随机性研究简史[1]

    随机性一直是我们生活中不可或缺的一部分。很多古老的占卜仪式都是基于偶然性的：希腊人的抛骨（动物关节）占卜，中国人的抽签占卜，西非人的欧佩尔占卜链。在游戏和赌博中使用的类似骰子的物件也可以追溯到数千年前。

    -签卜-

    然而，直到16世纪，我们才开始发明出必要的工具和语言来真正理解概率和随机性。这些工具包含一些算数概念，例如分数和数字零。

    概率和随机性的研究始于一位名叫杰罗拉莫·卡达诺（GerolamoCardano）的人[2]。1501年出生于意大利的卡达诺知识渊博，是文艺复兴时期最具影响力的数学家之一。他也是一个臭名昭著的赌博成瘾者。由于嗜赌成性，卡达诺最终一贫如洗，变得默默无闻。然而，正是他在赌博方面的经历，使他得以写出《运气游戏书》——这是第一本系统分析概率和随机性的书。有趣的是，卡达诺打算将这本书保密。这本《运气游戏书》自写成到出版相隔一个世纪，远迟于卡达诺离世。

    -杰罗拉莫·卡达诺（1501-1576）-

    卡达诺对我们理解偶然性和随机性所做的主要贡献是提出了样本空间的概念。在最基本的层面上，计算事件的概率很简单，假设所有场景发生的可能性相同，计算可能导致该事件发生的场景数量，然后除以所有可能场景的总数（“样本空间”）。这个假设虽然只适用于掷骰子之类的问题，但是一个好的开端。

    紧随卡达诺其后的是伽利略和帕斯卡。伽利略是那个时代反叛知识分子精神的完美化身：与最强大的天主教会作对，并宣称地球不是宇宙的中心。伽利略写了很多重要的著作。在一个不是很出名的作品《关于骰子游戏的思考》中，他探讨了卡达诺同样感兴趣的类似主题。

    与费马和笛卡尔同时代的帕斯卡比卡达诺和伽利略走得更远。他发现了我们今天所说的帕斯卡三角。尽管其他国家（如：伊朗、中国和印度）的数学家早于帕斯卡几个世纪就发现了相同的三角排列，但帕斯卡三角是最全面的，而且增加了新的应用，尤其是在概率论领域。帕斯卡还介绍了“帕斯卡赌注”及数学期望的概念。

    从卡达诺、伽利略和帕斯卡播下的种子中，我们对概率和随机性的理解慢慢加深，随着时间的推移逐渐变得更加复杂和精妙。这是文艺复兴时期的共同主题：一些基础领域的突破（例如天文学、牛顿物理学、微积分、经验论）奠定了科学基础，创造了新的学科分支以及重大技术创新，并最终走向了工业革命。

    以下列出了我们在探索概率与随机性的过程中著名的里程碑：

    样本空间

    排列组合

    帕斯卡三角

    大数定律

    小数定律

    贝叶斯理论——条件概率

    正态分布&标准方差

    均值回归

    随机游走

    蒙特卡罗模拟

    伪随机性

    -正态分布（也称钟形曲线）——图源：DanKernler/CC4.0-

    两大最主要的理论发展是：蒙特卡罗模拟和伪随机性。主要原因是它们与当今世界联系密切。

    计算机的发明打开了通往全新随机性应用的大门：计算机模拟。这是有史以来第一次，我们可以以较低的成本一遍遍重复地做实验来“预测未来”，或者说是揭开隐藏的真相。计算机的出现解决了大量模拟实验的成本问题，这在以前是不可想象的。

    20世纪初，蒙特卡罗模拟技术的发明标志着人类历史上的一个重大转折点。在文艺复兴之前，人类经常生活在对随机性和不确定性的恐惧之中，到了20世纪后，我们逐渐提升了对随机性的理解，但仍在很大程度上让随机性决定了事物的走向。通过蒙特卡罗模拟技术，我们开始利用起了随机性，从当初的小白成为了现在的大师。

    值得注意的是，蒙特卡罗模拟的先驱包括约翰·冯·诺依曼和阿兰·图灵这两位现代计算机教父。

    如今，蒙特卡罗模拟的应用范围很广：举几个例子，有流体力学、商业、金融、人工智能等。关于蒙特卡罗模拟如何（结合其他技术）引导我们获得新发现，最近的AlphaGo事件就是最好的例子：AlphaGo拥有丰富的围棋资料库，利用完全超越我们想象的步法击败了最顶尖的人类选手。AlphaGo挑战了机器不可能具有创造性的观念，强迫我们重新思考“创造性”的真正含义。

    蒙特卡罗模拟方法的日益普及促进了“伪随机性”的发展（伪随机指的是看似随机，并非真正意义上的随机），因为良好的模拟需要能够密切反映现实中的随机性。这种过程产生的数字是确定的，但它们通过了被认为是“随机”的统计测试。相应地，伪随机性成为了一个全新领域的基石之一——也是计算机时代的产物：现代密码学。

    它引导我们走向了比特币。

    ##随机性在比特币中的作用

    比特币的一项主要创新是使用工作量证明来建立分布式共识。PoW提供了一个客观的尺度，以此帮助比特币网络参与者在无需建立互信关系的情况下达成共识。这与权益证明之类的方案不同，后者依赖对共识的主观诠释。本节假设PoW是实现区块链的唯一安全方式。（要复习PoW的相关内容，请阅读第1部分：剖析工作量证明。）

    PoW中的“工作”指的是寻找一个以连续的“0”为开头且“0”的数量超过一定下限的哈希输出。（哈希输入有一些限制，例如格式和时间戳等）

    比特币的PoW机制使用的是被称为SHA256的密码学哈希函数。密码学哈希函数的一个重要特征是单向性。这意味着不可能根据哈希输出一眼就推断出哈希输入。单向性很大程度上还取决于哈希输出的随机性。

    经证明这是非常关键的，因为如果哈希函数没有产生足够随机（“伪随机”）的输出，那么就可以从一个指定输出，即一个开头含特定个“0”的字符串，开始倒推。在最好的情况下，这会使工作量证明变得不可靠（校对注：即无法真实反映付出的工作量），在最坏的情况下则会让它变得毫无用处。

    简单来说，典型的PoW机制的运作流程是：（a）提出一个求解范围很广的问题，（b）没有捷径，（c）求解的唯一方式是强行随机搜索这个范围。就像在巨大的干草垛中寻找一根针一样。（正式的计算机科学术语是“无限概率迭代过程”——非常恰当）

    因此，哈希函数的随机性决定了证明的强度。

    ##哈希（提供）→随机性（支持）→工作量证明

    “…一个好的难题让每个矿工都有机会基于他们所贡献的哈希算力按比例解出下一个难题。这就好比随机投掷飞镖，不同尺寸的目标区域对应不同矿工拥有的挖矿算力。”——阿文德·纳拉亚南[3]

    没有正式的证据表明随机性是PoW的强制性要求，但从经验上看，这似乎是正确的。稍稍观察下就能发现，凡是非随机性求解的问题，求解和验证所需的工作量一样多。任何这样的机制在可扩展性方面都会受到严格限制（请记住，比特币难以在当前架构下扩展）。它还会过度青睐速度最快的矿工——以至于速度稍微慢一点的矿工什么都赚不到。

    基于随机性的PoW的另一个好处是挖矿资格的开放性很强：矿工可以随时加入或退出。他们可以在区块刚被发现时就立即加入，或者5分钟后再加入也没关系，他们获得下一个出块奖励的概率也不会改变。

    那为什么要使用哈希函数呢？这是实现随机性的唯一方式吗？可能不是。除了哈希，还有其他已知的方法可以模拟随机搜索的过程，例如整数分解或离散对数。

    因此，哈希很可能不是实现随机性的唯一手段，而随机性却是创建数字化工作量证明机制的必要前提。

    PoW机制分为两大类：

    计算密集型：随机搜索受处理器速度限制

    内存密集型：随机搜索受内存访问限制

    上述哪个类别更胜一筹还有待观察（我个人认为内存密集型逊色一点[4]），不过二者的内在机制是相同的：基于概率随机搜索大范围的解，且验证任意解的成本很低。

    总之，只要人类尚存，就会与随机性和不确定性死死纠缠。随着20世纪现代计算机和蒙特卡罗模拟的发明，我们第一次将随机性转变为我们的优势。在比特币中引入随机性标志着这一漫长旅途中的又一个里程碑。简而言之，随机性在工作量证明中起到了为“证明”背书的作用。如果没有随机性或足够好的伪随机性，工作量证明将变得无效。

    如果比特币能在未来成功地变成一种货币，那么它将成为我们迄今为止最重要、规模最大的随机性应用。

    感谢SteveLee和NicCarter提供的宝贵意见。

    [1]：有关随机性的详细历史，请参阅伦纳德·姆洛迪诺（LeonardMlodinow）的“醉汉走路：随机性如何控制我们的生活”。

    [2]：不要与加密货币Cardano混淆，具有讽刺意味的是，该加密货币是基于权益证明的。

    [3]：阿文德·纳拉亚南，《比特币和加密货币技术的全面介绍》一文的作者。

    [4]：内存密集型PoW方案的几个潜在问题：

    内存密集型PoW仍然需要计算，不过是在内存技术已经趋于平稳的假设下运行的，这使得内存成为挖矿操作的主要瓶颈。但如果这个假设被打破，你可能就要面对两股中心化力量（ASIC和内存），而非一股中心化力量（ASIC）。

    内存密集型PoW中使用的内存很可能在挖矿之外具有可再利用性。这可能会对网络安全产生负面影响，因为这可能会导致攻击者从其他人那里租用内存（因为任何可再利用的东西很有可能供应充分并出现偶尔的供应过剩），从而降低了多数攻击的成本。一般而言，出于比特币安全性的考虑，硬件的可再利用性是不可取的。