Rafael Pass 等人于 2017 年在密码学顶会之一的 Eurocrypt 发表了论文 Analysis of the Blockchain Protocol in Asynchronous Networks。该论文基于前人的一系列工作在异步网络环境下对区块链协议进行了系统性的分析以及抽象，给出了形式化的模型和主要定理。根据这些模型和定理，我们可以准确地理解区块链协议各种安全属性的依赖条件以及边界。包括 Ouroboros 和 DFINITY 在内的热门项目的论文均以本文的模型和部分结论为基础进行安全性证明，可以说，这篇文章是区块链共识研究的必读之作。

本文则是基于 Rafael Pass 等人的这篇论文，对论文进行了概括性的讲解，省去了原文中的具体证明步骤以及诸如致谢之类的段落，主要阐述预备知识、核心思想、理论模型、证明思路、相关工作、以及主要结论。

前言

本文预先假设读者对区块链和分布式系统有基本的了解，了解比特币原理，尤其是它的共识协议。对于有对应中文翻译的关键术语，本文会在括号内提供英文原文，对于没有对应中文翻译的术语，直接采用英文原文。另外，笔者所能获得的论文原文有大量笔误（→_→），阅读十分辛苦。

带有**[论文]**字样的系列都是对优秀学术论文的概括性讲解，讲解通常会分为两到三篇博文，分为概述和细节两个部分，有些论文可能还需要稍微讲解一下证明思路和技巧。想要快速了解论文核心思想和贡献的读者可以直接阅读概述版本，细节版本会保留原文的主要细节。

背景

历史上的分布式系统的研究主要是在许可 (permissioned) 环境下进行的，在这种环境下，系统参与者的数量和参与者的身份是公共知识 (Common Knowledge)，也就是公开的事实。与许可环境不同的分布式系统设计是从点对点 (peer-to-peer) 系统开始的，例如 Napster 和做文件分享的 Gnutella。这些系统的成功促成了学术界研究的热潮，例如 Freenet [CSWH00], Chord [SMK+01], 和 Pastry [DR01]。这些系统的新颖之处在于他们是非许可 (Permissionless) 环境下的。但是大家普遍认为这样的分布式系统，即使网络环境很健壮，通常也无法容忍恶意行为。在这样的系统下，我们没有办法保证任意两个节点状态一致。一个显而易见的做法是使用拜占庭容错算法，但是这样的算法要求一大部分(通常是 $\frac{2}{3}$ 以上)的参与者都不是恶意的。于是，在非许可环境下，一个攻击者可以使用被称作女巫攻击 (Sybil Attack) 的手段模拟出大量的参与者，从而轻易地控制住参与者中的绝大多数。事实上，Barak 等人的文献 [BCL+05] 证明了这是非许可模型的一个根本性难题。

中本聪的区块链

2008年，中本聪 (Satoshi Nakamoto) 发表了著名的“区块链协议”克服了上述问题。他的协议基于计算性难题（又叫做 moderately hard functions 或者 proofs of work）。中本聪的区块链协议的核心（也叫做 Nakamoto 共识），用一句话概括，是一种维护不可更改的公开有序账本上的记录的方法。例如，在比特币应用程序中，这些记录就是交易。记录可以随时被添加到账本的末尾，并且也只能被添加到末尾；另外，协议保证以前添加的记录无法被删除或重排；并且，对于所有诚实的用户来讲，帐本上的数据是一致的。显然，传统的拜占庭共识协议也可以用来实现这种不可更改的有序记录，但是 Nakamoto 共识协议之所以令人惊叹，是因为它在一个完全非许可的环境中运作。

我们之前说到，传统的共识协议无法被应用到非许可环境的原因之一是他们要求诚实参与者的数目为大多数。中本聪则另辟蹊径，他尝试在假设诚实参与者提供的总算力而不是总数目为大多数的情况下设计系统。那么这样的设计是否是安全的呢？

中本聪的论文中清楚地说明了该系统的一致性 (consistency) 足以支持一个金融交易系统，而事实上比特币证明了这一点。设计这样的系统的困难之处在于，系统需要有足够的能力去阻止欺骗行为和双花攻击，而中本聪做到了。

为了从理论的角度去分析这样的协议在什么条件下安全，以及这些条件是否有界，上界是多少。我们首先需要对区块链协议进行形式化地建模。

大致说来，在中本聪的协议中，每个参与者都自己维护着被称为区块链的本地的一条链 (chain)。链内包含着区块 (block)，区块内包含着记录 (record)。每个区块由一个三元组 $(h_{-1},\eta,\mathsf{m})$ 组成，其中 $h_{-1}$ 是指向链中前一个区块的指针，$\mathsf{m}$ 是块的记录部分，$\eta$ 是一个工作量证明 (proof-of-work)——基于 $(h_{-1},\mathsf{m})$ 得出的计算性难题的一个解。从这点来讲，工作量证明可以被认为是整个区块链中的“无密钥数字签名”。

另外，Nakamoto 协议引入了挖矿难度参数 $p$。假设 $\eta$ 是一个字符串并且 $\mathsf{H}(h_{-1},\eta,\mathsf{m}) < D_p$，那么工作量证明 $\eta$ 被认为是有效的。其中，$\mathsf{H}$ 是散列函数（这里我们采用随机预言机 (random oracle) 建模），$D_p$ 是一个给定的取值，需要使得上述不等式成立的概率小于 $p$。为了修正系统参与者的人数和网络延迟的变化而产生的影响，在实践中，难度参数 $p$ 需要通过一些外部过程自适应地修正。

在安全性的证明中，经常会用到随机预言机模型，这个模型通常将实际的具体的哈希函数理想化地看作一个完美的哈希函数，因此，假定了这样的哈希函数对于敌手是没有漏洞的。

在协议执行过程中，任意时刻，每个参与者都试图通过挖矿 (mining) 产生新的块来增加自己链的长度：当收到某个记录 $\mathsf{m}$ 后，参与者会任意选择一个 $\eta$ 并根据 $\mathsf{m}$ 和 $h{-1}$ 按照前文提到的不等式检查 $\eta$ 是否是一个有效的工作量证明。如果是，组成 $(h_{-1},\eta,\mathsf{m})$，成为新的块，然后扩展自己的本地链并将链广播给其他所有的参与者（广播通过某种 gossip 协议进行，我们此处不讨论）。每当参与者收到比本地链更长的链时，就会切换到更长的链上进行挖矿。

这种方法下，我们需要考虑的一个根本问题就是诚实的参与者最终是否会收敛到相同的最长链，即相同的有序记录列表。或者换一个说法就是，系统是否会进入一个状态，这个状态下参与者们具有不一致的本地链。

Nakamoto 协议达到了一致性吗？

如果像 Nakamoto 协议打算做的那样，在有消息延迟的网络上执行，这种情况下所有参与者就整条链达成一致十分困难，甚至是不现实的。例如，一些参与者可能已经收到了“最后一个块”，而其他参与者由于消息延迟则还没有，当这些参与者终于收到这所谓的“最后一个块”的时候，别的一些参与者可能又收到了新的区块。如此下来所有参与者很有可能永远无法就整条链达成一致。因此，这样的“一致性”的定义太强了。相反，正如 Nakamoto [Nak08] 所说的那样，适合区块链的一致性应该是要求诚实的参与者在不考虑潜在的一小部分的，$T$ 个在链末端的“未确认的”块的情况下，对当前的链达成一致。我们称这样的一致性为 $T$-consistency。

那么，定义好了适合区块链的一致性要求之后，下一步就是证明给定的区块链协议是否满足这样的安全属性。密码学文献普遍采用的方法是证明这个性质有可能无法保持，但是种情况出现的概率是由一个可忽略函数所描述。那么，这样的“可忽略”是相对于什么可忽略呢？我们可以发现，随着 $T$ 的增加，这样的一致性会越来越容易保持，因此，我们只需证明 $T$-consistency 不能保持的概率相对于 $T$ 可以被忽略即可。

可忽略函数有正式的定义，通常，我们认为一个函数 $\epsilon(\cdot)$ 是可忽略的 (negligible)，如果对于每一个多项式 $p(\cdot)$，总是存在一个 $\kappa_0$ 使得 $\epsilon(\kappa) \leqslant \frac{1}{p(\kappa)}$ 对于所有的 $\kappa \geqslant \kappa_0$ 均成立。直观地来讲，可忽略函数就是比任何一个多项式函数都要下降得快的函数。

如果我们证明了这一点，那么就能够保证各个诚实参与者对于一个足够大的 $T$，除了可以忽略的概率以外，“已确认的”区块将永远不会从链中消失（比如出现了分叉，而分叉链的长度超越了原来的链）。这正是区块链的应用所需要的——例如，对于比特币，就能够确保参与者不能把同一笔钱花两次。

中本聪的论文 [Nak08] 假设敌手只采用特定的攻击策略（即攻击者试图比诚实参与者生成链的速度更快），由此提供了对 $T$-consistency 的初步分析。他的分析没有考虑更复杂的攻击策略，比如敌手可能会试图“分裂参与者”让他们在不同的链上挖矿。Garay，Kiayas 和 Leonardos [GKL15] 最近的一篇论文提供了一个更正式的模型，用于研究 Nakamoto 的区块链协议。然而，他们的分析只考虑了同步网络下的快速攻击策略，也就是说，在特定回合中发送的消息会在下一个回合没有任何延迟地到达，但敌手在发送自己的消息之前必须看到之前诚实参与者发送的所有消息。在这个模型中，他们证明了在参与者数量固定（但不知道确切的数量）的条件下，区块链协议满足一致性。

然而，同步假设是一个非常强的，可能不切实际的假设。Nakamoto 的协议明确地被设计为是在具有消息延迟的网络中工作，并且实际上也正是在这样的网络（即因特网）中执行的。因此，我们还需要分析区块链协议在更实际的异步网络环境下满足一致性的程度。

但是首先，同步还是异步对协议的安全性分析有多大的影响呢？

网络延迟的影响

异步网络意味着对抗方控制了诚实方之间的消息传递。在一个完全异步的环境中，对抗方可以随意延迟消息，一致性无法被满足（论文中有证明）。对抗方只需控制一小部分算力就可以很容易地使来自诚实方的消息延迟足够长的时间，长到对抗方确保能够拿出比所有诚实方更长的链（这条链可以包含任何对抗方想要的记录），从而随时可以使得诚实方切换到对抗方的链。甚至，只要挖矿难度参数 $p$ 超过 $\frac{1}{\rho n \Delta}$，这样的攻击在部分同步的环境中依然成立。其中， $\rho$ 是对抗方持有的算力比例，$n$ 是所有参与者的数量。部分同步的环境下，存在关于网络延迟的先验约束 $\Delta$，也就是说，攻击者可以随意延迟消息，只要消息在 $\Delta$ 时间内抵达，而这个 $\Delta$ 是公开已知的。

另一方面，Decker 和 Wattenhofer [DW13] 已经通过实验观察到，增加 Nakamoto 协议中的网络延迟会导致分叉增加。他们注意到（通过启发式计算）攻击者可以利用网络延迟以少于 50% 的算力来发动攻击打破一致性。被 Decker 和 Wattenhofer 的工作启发，Sompolinsky 和 Zohar [SZ15] 提供了在有（有界）延迟的网络中的区块链协议的初步分析。他们展示了如何扩展中本聪的分析以处理（有界）延迟，但是再一次，就像中本聪那样，他们只考虑了特定的攻击策略。例如，他们没有考虑 block-withholding（又叫 pre-mining）攻击：攻击者挖出区块但不广播，供之后的攻击使用 [mtg10，ES14]。此外，他们的分析只表明一致性在 $T$ 趋于无穷时成立，因此，即使限制了攻击策略，他们得出的结论对实际应用也用处不大。

问题提出

通过上面的分析，我们可以看出，异步的环境对于攻击者非常有利，并且使得安全性分析非常困难。这就留下了一个待解决的问题——在任意攻击策略以及 $\Delta$-有界延迟下，提供针对 Nakamoto 区块链协议，或者任何非许可环境下的共识协议的分析。在本论文中，作者提出了这样的问题：

当 Nakamoto 区块链协议在 $\Delta$-有界延迟的异步网络下执行时是否满足一致性？

如前文所述，Garay 等人 [GKL15] 为 $\Delta = 1$ （即，消息在下一个时间步长中到达）的特殊情况提供了肯定的答案。Sampolinsky 和 Zohar [SZ15] 表明，某些攻击策略在 $\Delta$-有界延迟网络中（在 $T$ 趋于无穷时）不能打破 Nakamoto 协议的一致性。

实际上，Garay 等人的结果也可以被看作 $\Delta$-有界延迟，只不过这个 $\Delta$-有界延迟是有特定的结构的，那就是时间必须被分割成 $\Delta$ 长度的时间区间，在任意时间区间内发送的消息都会被延迟到时间区间结束。

另外，在“工作量证明”的非许可环境下处理网络延迟（假设大多数算力都是诚实的）比在“传统的”许可环境下更具挑战性。因为在许可环境中，任何同步协议都可以被转化成一种在 $\Delta$-延迟网络中也是安全的协议，只需要要求所有诚实参与者总是在回复任何消息之前“等待”（什么事都不做）$\Delta$ 个时间步长。这种方法在工作量证明的环境下是无法使用的——当诚实的参与者“等待” $\Delta$ 时，对抗方可以尝试解决难题。对抗方可以利用这一点间接增加其计算资源。

论文主要贡献

论文的作者解决了上述问题。作者的分析不仅仅是前人工作的组合，事实上，作者处理了 [SZ15] 的分析中省略了的一些攻击策略，而处理这些攻击策略需要一种完全不同的证明技术。此外，作者的分析还考虑了适应性恶意行为 (adaptive corruption) 以及新参与者的加入。需要强调的是，这是第一个形式化处理新参与者产生的分析。

下面大致概括了作者的主要工作。

考虑了网络延迟的一致性定理

考虑具有挖矿难度 $p$ （即一次随机预言机查询成功概率为 $p$） 的 Nakamoto 协议，并考虑有 $n$ 个参与者的一次协议执行，他们中的每个人都具有相同的算力。我们假设协议按轮次（时间步长）进行。在每一轮中每个参与者能够进行一次随机预言机查询（因为参与者算力相同）；对抗方控制的比例为 $\rho$ 的参与者能够进行 $\rho n$ 次随机预言机查询（参考 [GKL15]，诚实参与者需要并行进行查询，对抗方可以相互勾结，所以可以串行查询）。

设 $\alpha = 1-(1-p)^{(1-\rho)n}$ 是存在某个诚实参与者一轮成功解决难题挖出一个块的概率，并且设 $\beta = \rho n p$ 是攻击者一轮可以挖掘的区块数量的期望。当 $p \ll 1/n$（在实践中需要考虑的情况）时，我们有 $\alpha \approx p(1-\rho)n$，并且因此 $\frac{\alpha}{\beta} \approx \frac{1-\rho}{\rho}.$

注释 $(1-p)$ 是一轮无法成功挖出块的概率，$(1-\rho)n$ 为诚实参与者的个数。由于诚实参与者只能并行挖矿，$(1-p)^{(1-\rho)n}$ 是一轮之内没有任何一个诚实参与者挖出区块的概率。相应的，$\alpha = 1-(1-p)^{(1-\rho)n}$ 便是存在某个诚实参与者一轮挖出区块的概率。由于攻击者可以串行挖矿，$\beta$ 是和攻击者人数 $\rho n$ 正相关的。

当 $p \ll 1/n$ 时，设 $f(p) = (1-p)^{(1-\rho)n}$， 由泰勒展开可知 $$ \begin{aligned} f(p) &\approx f(0) + pf’(0) + \frac{p^2}{2}f^{\prime\prime}(0) \\\
&\approx 1 - p(1-\rho)n, \end{aligned} $$ 所以 $\alpha \approx p(1-\rho)n.$

基于上述假设和分析，作者给出以下定理：

定理 1.1 设存在 $\delta > 0$ 使得 $$\alpha(1 - 2(\Delta + 1)\alpha) \geqslant (1 + \delta)\beta$$ 成立。那么，在随机预言机模型下，除了关于 $T$ 指数小的概率，Nakamoto 协议满足 $T$-consistency ，假设网络的延迟为 $\Delta$-有界。

其中，$\delta$ 我们可以理解为一个调节安全性的参数，$\delta$ 越大，协议对“安全”的要求就越高，定理也就越难以成立。这个定理当然是对上一个部分我们提出的问题的很好的回答，但实际上，这只是作者工作的一部分，$T$-consistency 也只是区块链协议中我们需要考虑的众多安全属性中的一个。

什么是“区块链”

论文的另一个贡献是形式化地定义了“区块链”的抽象概念，并且提出了一些大家关心的安全属性。这样做好处有两点，一是我们可以忽略区块链协议的实现细节从而简化应用；二是从此可以形式化地研究协议可以被优化到什么程度。在此之前，我们是不清楚中本聪的协议能被优化到何种程度的。

值得注意的是，这里的“区块链”并不是通常意义上的我们常说的区块链。既不是指中本聪提出的“区块链协议”（中本聪提出的更为具体）；也不是我们说的“区块链系统”（目前的各种公链项目不仅仅是更为具体的实现，还包括了很多其他的协议和子系统，例如智能合约、p2p网络等等）。

前文提到了中本聪的区块链协议的模型，这里论文在其上做了抽象以适用于不同的具体的区块链协议。论文中给出，一个区块链是一个交互协议，其中每个参与者有一个本地变量 $\mathsf{state}$，包含了一个被称作链的消息列表 $m$，参与者们接收被称作记录或者消息或者一批消息的输入，并尝试将这些输入包含到自己和他人的链里面。

一个安全的区块链需要满足以下性质：

  • consistency ：在任意时刻，以相对于 $T$ 压倒性的 (overwhelming) 概率，两个诚实参与者的链只能在最后$T$个区块有所不同；
  • future-self consistency ：在任意两个时刻 $r, s$，以相对于 $T$ 压倒性的概率，任意诚实参与者在 $r$ 和 $s$ 的链只能在最后 $T$ 个区块有所不同；
  • $g$-chain growth ：以相对于 $T$ 压倒性的概率，在任意时刻，诚实参与者的链在过去的 $\frac{T}{g}$ 轮中，至少增长了 $T$ 个消息。称 $g$ 为该协议的 chain growth ；
  • $\mu$-chain quality ：以相对于 $T$ 压倒性的概率，任意诚实参与者的链中的连续 $T$ 个消息中，诚实参与者提供的消息所占比例至少为 $\mu$，称 $\mu$ 为该协议的 chain quality 。

以相对于 $T$ 的压倒性的概率成立的意思是，不成立的概率是一个关于 $T$ 的可忽略函数。

另一个我们之后会用到的一个安全属性是 consistent length ——对于任意诚实参与者，如果在某一轮 $r$ 他的链长度为 $k$，那么在 $r + \Delta$ 轮之后所有诚实参与者的链长度都至少为 $k$。显然，$\mu$-chain quality 可以推导出 consistent length 。

img

图1：满足 consistency 的一种情况

中本聪考虑过的 [Nak08] consistency 对于应用通常是不够的。因为它不排除一些允许参与者在不同的链 $\vec m_1, \vec m_2$ 之间振荡的协议。比如在偶数回合中，所有参与者都用 $\vec m_1$ 作为他们的链，并且在奇数回合用 $\vec m_2$。显然，这样的协议是有风险的（例如对于比特币来讲）。因此，为了防止这种情况，作者引入了 future-self consistency 这一属性。

img

图2：满足 future-self consistency 的情况

以前的工作中，Sampolinsky 和 Zohar [SZ15] 明确考虑了 chain growth 的下界（但他们只考虑了 chain growth 的期望）；Garay 等人 [GKL15] 在他们的一个证明中隐含了 chain growth 的下界；[KP15] 明确地将其作为一个安全属性。在本论文中，作者额外引入了 chain growth 的上界，作者的后续的一些论文 [PS16a，PS16b] 中，这个属性起到了重要作用。

img

图3：$\mu$-chain quality：诚实者的消息比例为 0.6

比特币论坛 [mtg10] 里首次讨论了 chain quality ；Eyal 和 Sirer [ES14] 的自私挖矿攻击 (selfi sh mining attacks) 中明确提出了基于比特币应用的 chain quality ；该属性首次由 Garay 等人 [GKL15] 命名并形式化。

上述模型描述了在比特币等区块链应用背后的核心协议的抽象，在这样的抽象模型之上，我们可以构建应用——例如比特币一类的数字货币 (cryptocurrency)，以及以太坊一类的智能合约(smart contract)。本文中，作者为了说明这些安全属性的作用，详细讨论了公共账本 (public ledger)。数字货币本质上就是公共账本类型的应用。

作者证明了任何满足这些属性的区块链协议都可以被用来构造公共账本。公共账本需要满足

  • persistence ：如果消息被添加到公共账本，它永远不会被删除；
  • liveness ：如果所有诚实参与者想要向账本添加一些消息，那么最终消息应该出现在账本上面。

Garay 等人 [GKL15] 同样提出了公共账本需要满足的上述两个属性，但他们使用了比该论文作者稍弱的定义。并且，尽管他们展示了如何在同步模型中使用 Nakamoto 协议构建这样的公共帐本，但是除了上述两个属性之外他们还使用了额外的依赖于具体协议的属性去建立模型。Kiayias 和 Panagiotakos [KP15] 证明了，除了 chain quality 以外，只要额外再满足 chain growth 就可以不依赖具体协议地证明 liveness ，但证明 persistence 仍然需要通过分析具体的协议。该论文的作者通过引入 future-self consistency 的概念巧妙地解决了这个问题，使得 persistence 能够在不依赖具体协议的情况下被证明。至此，persistence 和 liveness 都能够直接从刚刚我们定义的区块链抽象模型中推导出来，这也正是该论文的理论模型的优美之处。

具体地来讲，作者通过 $g$-chain growth 和 $\mu$-chain quality 推导出了 liveness ；通过 consistency ，future-self consistency 和 consistent length 推导出了 persistence 。

Pass 和 Shi [PS16a，PS16b] 的后续工作进一步证明了他们关于区块链的抽象概念及其安全属性的作用。

主要定理

该论文的主要结果表明 Nakamoto 协议达到了包括一致性在内的之前提到的所有安全条件。根据“考虑了网络延迟的一致性定理”这一节所述，我们知道 $\alpha$ 是存在某个诚实参与者一轮成功挖出一个块的概率，$\beta$ 是攻击者一轮可以挖掘的区块数量的期望。设 $\gamma = \frac{\alpha}{1+\Delta\alpha}$ ，那么 $\gamma$ 是 $\alpha$ 的带有网络延迟的版本。前面讲过，通过延迟消息，攻击者可以获得额外的计算时间。那么，对于 Nakamoto 协议有以下定理：

定理 1.2 设存在 $\delta > 0$，使得 $$\alpha(1-2(\Delta + 1)\alpha) \geqslant (1 + \delta)\beta.$$ 则 Nakamoto 协议满足 consistency ，future-self consistency ，$\mu$-chain quality 以及 $g$-chain growth 。其中 $g = \frac{\gamma}{1+\delta}$ 且 $\mu = 1-(1+\delta)\frac{\beta}{\gamma}.$

显然，这个定理比定理 1.1 要强得多。

注意当 $p \ll 1/n\Delta$（在实践中需要考虑的情况），我们有 $\gamma \approx \alpha \approx (1-\rho)np$，因此 $\frac{\gamma}{\beta} \approx \frac{1-\rho}{\rho}$。这样，有如下推论：

推论 1.3 设 $\rho < \frac{1}{2}$。对于每一个 $n$，$\Delta$，存在某个足够小的 $p_0 = \Theta(\frac{1}{\Delta n})$，使得具有挖矿参数 $p \leqslant p_0$ 的 Nakamoto 协议满足 consistency , future-self consistency , $1-\frac{\rho}{1-\rho}$-chain quality 和 $\frac{pn}{2}$-chain growth 。

这样，只要 $\rho < \frac{1}{2}$，Nakamoto 协议就能保证诚实参与者提交的消息最终会在链上收敛，只要 $\rho < \frac{1}{3}$，链上一半的消息都是诚实参与者提交的。作者的论文中提到，他给出的 chain quality 的边界和 Garay 等人 [GKL15] 的无延迟（也就是 $\Delta = 1$）的结果是一致的，并且由于自私挖矿攻击 [mtg10, ES14] 的存在，这个边界已经是最优的了。

主要定理只解决了 Nakamoto 协议的安全边界分析问题，但是仍然有一个遗留问题：是否存在这样的一个满足论文中给出的抽象模型的，比 Nakamoto 协议更优的协议？这样的设计是存在的，在 Pass 和 Shi 的之后的一篇论文 [PS16a] 里面有详细的设计和证明。那篇论文的结果表明，我们可以“放大” Nakamoto 协议的 chain quality 到“接近最优”，也就是使得其达到 $1-(1-\delta)\rho$，其中 $\delta$ 为一个任意小的常数。

“最优” chain quality ，也就是 $1-\rho$，表示比例为 $\rho$ 的攻击者恰好在链上拥有 $\rho$ 的区块。

Nakamoto 协议真的是非许可的吗？

有意思的是，上述定理只表明，对于每一个 $n$ 和 $\Delta$，都存在某一个挖矿难度系数 $p$ 使得协议安全。这样看来似乎协议需要事先知道 $n$，因此协议不是非许可的。这个问题接下来会通过实验说明，协议只需要事先知道参与人数 $n$ 的一个非常粗略的上界即可（当然，这个上界越松弛，协议的效率越低）。

我们还注意到上述定理中，关于 chain growth 的下界的结论实际上没有对 $p$ 做任何假设。这意味着诚实参与者可以在初始配置阶段先估计出 chain growth ，并由此推断出一个弱的参与者数上限 $n$，然后使用这个新的上限来运行协议。事实上，比特币就是用类似的方法来动态更新 $p$ 。

实验解释

为了更直观地解释定理，论文作者还给出了实验，实验对现实世界数据进行了估计。在 2016 年早些时候，比特币网络总体约为每秒 $10^{18}$ 次哈希运算 [Blo16]。在当时，一些公司出售可以达到每秒 $10^{12}$ 次哈希运算的挖矿硬件。为了和这些现实数据保持一致，作者考虑了 $n = 10^5$ 个参与者，并且 $\Delta = 10^{13}$。$\Delta$ 的取值在给定算力下，大致和 10s 的网络延迟一致。“$10s$”这个数据的的估计是基于大多数连接比特币网络的算力网速超过 1mb/s 的事实。基于这样的设定，每一个区块大约需要 1s 的时间传播，网络的直径小于 10 跳。这些假设与 Decker 和 Wattenhofer [DW13] 的经验测量结果一致——在 2012 年夏季的一段时间，他们计算出的平均区块时间约为 10.55m，$\Delta$ 的加权平均值（他们的模型允许 $\Delta$ 服从一个长尾分布）约为11.37s。他们的测量结果由网站 bitcoinstats.com 在 2016 年佐证。

Nakamoto 协议的难度参数反映了所有参与者发现区块的时间的期望。因此，我们可以通过改变 $c$ 来观察一致性与参数 $p = \frac{1}{n\Delta \cdot c}$ 的关系。这里，$c$ 可以被理解为以网络延迟数表示的区块时间的期望。

作者根据 $\rho$ 的变化画出 $c$ 的图线，如图 4 所示，描述了在 Nakamoto 协议中，什么时候作者给出的一致性定理是成立的。蓝色图线描绘了当 $\alpha(1-(2\Delta+2)\alpha) > \beta$ 时，也就是 Nakamoto 协议保持一致性时，$\rho$ 的数值计算最大值。红色图线显示何时最好的攻击策略能够成功地打破一致性。

img

图4：$n = 10^5$ 并且 $\Delta = 10^{13}$ 时 $\rho$ 随着 $c$ 的变化

Nakamoto 协议试图通过改变难度参数 $p$ 来维持 10 分钟的区块时间。对于一个约为 10s 的 $\Delta$ 而言，这样的区块时间和 $c = 60$ 对应（因为区块时间的期望是 60 个 $\Delta$）。在此范围内，Nakamoto 协议以及作者的攻击策略给出了基本相同的结果：Nakamoto 协议可以容忍 $\rho < 49.57%$ 的敌手，而最好的攻击策略在 $\rho > 49.79%$ 的时候成功。如果我们非常保守地估计网络延迟为 1m，那么 $c = 10$，Nakamoto 协议能在 47.2％ 的攻击者比例下保持一致性。

值得注意的是，当 $c$ 很小的时候，上述分析所给出的边界并不是最紧的（因为这时红色的线高于蓝色的线很多），这是因为对于作者给出的攻击策略而言，只分析敌手完全控制链的情况。然而，当 $c$ 很小时，即使没有任何敌手从中作梗，诚实的参与者们也有很大可能不会收敛在同一条链。

相关工作

在有故障的参与者存在的情况下达成共识的问题，也被称为分布式共识问题，由 Pease，Shostak 和 Lamport [PSL80] 首先给出。已经在过去 40 年里得到比较充分的研究。其基本问题是指，由可靠的和经过认证的配对网络通道连接的 $n$ 方，希望在有敌手控制其中一部分参与者的情况下，就一个共同输出达成一致。这个问题的许多方面都被研究过，通过放松敌手控制的比例，改变参与者可用的信道，协议是确定性的还是随机性的以及参与者的计算能力是否有限等等。有些协议只考虑了 fail-stop 类型的敌手，而其他的则考虑了拜占庭环境（其中一些参与者是试图扰乱协议的恶意攻击者）。在拜占庭协议 (Byzantine Agreement/BA) 版本的问题中，Castro 和 Liskov [CL99] 实现了一个足以被用到文件系统中的副本库 (replication library)。随后，其他工作则考虑了 Paxos 的“快速”或“简单”版本 [MA05，Lam10，Lam11]。然而，所有这些工作都假定参与者数量 $n$，以及参与者的身份是公开的知识。

Okun [Oku05a，Oku05b，OB08] 在一个“没有端口发现的匿名（同步）模型”（其中，处理器没有标识符，无法将消息与其来源关联）中考察 BA; Okun 证明了确定性协议的不可能性以及概率协议的可行性。Aspnes 等人 [AJK05] 展示了如何在预处理步骤中使用工作量证明为各方分配临时身份，分配的身份数量与计算能力成正比。经过预处理，一个标准的经过验证的 BA 协议就可以应用在其上。然而，上述两种工作都不是在点对点网络中。在点对点网络中，新用户是可以在协议执行期间加入和离开的。

Garay，Kiayias 和 Leonardas [GKL15] 提供了 Nakamoto 协议的分析，并提出两个基于 Nakamoto 协议的多实例环境下的满足 BA 所有属性的协议。他们只考虑了同步网络，并且没有新的参与者加入或退出。

参考文献

[AJK05] J. Aspnes, C. Jackson, and A. Krishnamurthy. Exposing computationally-challenged byzantine impostors, 2005.

[BCL+05] Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin. Secure computation without authentication. In CRYPTO’05, 2005.

[Blo16] Blockchain.info. Hash rate for blockchain. https://blockchain.info/charts/hash-rate, February 2016.

[CL99] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI’99, 1999.

[CSWH00] I. Clarke, O. Sandberg, B. Wiley, and T.W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability, 2000.

[DR01] P. Druschel and A. Rowstron. Past: Persistent and anonymous storage in a peer-to-peer networking environment. In HotOS 2001, pages 65-70, 2001.

[DW13] Christian Decker and Roger Wattenhofer. Information propagation in the bitcoin network. In IEEE International Conference on Peer-to-Peer Computing, pages 1-10, 2013.

[ES14] Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security, pages 436-454. Springer, 2014.

[GKL15] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology-EUROCRYPT 2015, pages 281-310. Springer, 2015.

[KP15] Aggelos Kiayias and Giorgos Panagiotakos. Speed-security tradeoffs in blockchain protocols, 2015.

[Lam10] Leslie Lamport. Byzantizing paxos by refinement, 2010.

[Lam11] Leslie Lamport. Leaderless byzantine paxos. In DISC’11, 2011.

[MA05] Jean-Philippe Martin and Lorenzo Alvisi. Fast byzantine consensus. In DSN’05, 2005.

[mtg10] mtgox. https://bitcointalk.org/index.php?topic=2227.msg29606#msg29606, 2010.

[Nak08] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.

[Oku05a] M. Okun. Agreement among unacquainted byzantine generals. In DISC’05, pages 499-500, 2005.

[Oku05b] M. Okun. Distributed computing among unacquainted processors in the presence of byzantine failures, 2005.

[OB08] M. Okun and A. Barak. Efficient algorithms for anonymous byzantine agreement. Theor. Comp. Sys., 42:222-238, 2008.

[PS15] Rafael Pass and Abhi Shelat. Micropayments for decentralized currencies. In CCS’15, 2015.

[PS16a] Rafael Pass and Elaine Shi. Fruitchains: An (almost) optimally fair blockchain, 2016.

[PS16b] Rafael Pass and Elaine Shi. Hybrid consensus, 2016.

[PSL80] M. C. Pease, R. E. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27:228-234, 1980.

[SZ15] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction processing in bitcoin. In Financial Cryptography and Data Security, pages 507-527. Springer, 2015.

[SMK+01] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIG-COMM’01, 2001.