摘要
公共分类账是一个防篡改的数据序列，每个人都可以读取和扩充。 公共分类账有无数且引人注目的用途。他们可以在众目睽睽之下保护各种 交易（例如所有权、销售和付款）按照其发生的确切顺序排列。 公共分类账不仅可以遏制腐败，还可以实现非常复杂的应用程序，例如 加密货币和 smart contracts。他们致力于彻底改变民主社会的方式 运行。然而，按照目前的实施情况，它们的扩展性很差，无法发挥其潜力。 Algorand 是一种真正民主且有效的实施公共账本的方式。 与之前不同 基于工作量证明的实现，它需要的计算量可以忽略不计，并且 生成的交易历史不会以极高的概率“分叉”。 Algorand 基于（一种新颖且超快的）消息传递拜占庭协议。 具体而言，我们仅将 Algorand 描述为一个货币平台。
介绍
金钱变得越来越虚拟。据估计，美国约 80% 今天的美元仅作为分类帐条目 [5] 存在。其他金融工具也纷纷效仿。 在一个理想的世界中，我们可以依靠一个普遍信任的中央实体，免疫 对于所有可能的网络攻击，金钱和其他金融交易可以完全电子化。 不幸的是，我们并不生活在这样的世界中。因此，去中心化的加密货币，例如 如Bitcoin [29]，以及“smart contract”系统，例如Ethereum，已被提议为[4]。 在 这些系统的核心是一个共享账本，它可靠地记录一系列交易， *这是第二作者[24]的ArXiv论文的更正式（异步）版本，一篇论文 它本身基于 Gorbunov 和 Micali [18] 的理论。 Algorand 的技术是以下目标的对象 专利申请： US62/117,138 US62/120,916 US62/142,318 US62/218,817 US62/314,601 PCT/US2016/018300 US62/326,865 62/331,654 US62/333,340 US62/343,369 US62/344,667 US62/346,775 US62/351,011 US62/653,482 US62/352,195 US62/363,970 US62/369,447 US62/378,753 US62/383,299 US62/394,091 US62/400,361 US62/403,403 US62/410,721 US62/416,959 US62/422,883 US62/455,444 US62/458,746 US62/459,652 US62/460,928 US62/465,931以防篡改的方式，与付款和合同一样多样化。 选择的技术 保证这种防篡改的是 blockchain。 区块链支持以下应用程序 加密货币 [29]、金融应用 [4] 和物联网 [3]。几种技巧 已提议管理基于 blockchain 的账本：工作量证明 [29]、权益证明 [2]、 实用的拜占庭容错 [8] 或某种组合。 然而，目前分类账的管理效率较低。例如，Bitcoin 的 proof-of-work 方法（基于 [14] 的原始概念）需要大量计算，是浪费 并且扩展性很差[1]。此外，它事实上将权力集中在极少数人手中。 因此，我们希望提出一种新的方法来实现公共分类账，提供 由受信任且不可侵犯的权威机构运行的集中式系统的便利性和效率，无需 当前分散实施的低效和弱点。我们称我们的方法为 Algorand，因为我们根据目前构建的账本使用算法随机性进行选择， 一组验证者，负责构建下一个有效交易块。自然地， 我们确保此类选择可证明不受操纵且不可预测，直到 最后一刻，但也表明他们最终是普遍清楚的。 Algorand 的方法是相当民主的，从某种意义上说，无论是原则上还是事实上 创建不同类别的用户（如 Bitcoin 中的“矿工”和“普通用户”）。在 Algorand “所有 权力属于所有用户”。 Algorand 的一个值得注意的特性是，它的交易历史记录可能只分叉非常小的交易。 概率（例如，万亿分之一，甚至 10−18）。 Algorand 还可以解决一些法律问题 和政治担忧。 Algorand 方法适用于 blockchains，更一般地，适用于生成 防篡改的块序列。我们实际上提出了一种新方法——替代，并且 比 blockchains 更有效，这可能具有独立利益。 1.1 Bitcoin 的假设和技术问题 Bitcoin是一个非常巧妙的系统，启发了大量后续研究。然而，它 也是有问题的。让我们总结一下它的基本假设和技术问题—— 实际上，基本上所有基于 proof-of-work 的加密货币都共享这些加密货币，例如 Bitcoin。 对于此摘要，只需回想一下，在 Bitcoin 中，用户可能拥有多个公钥 在数字签名方案中，金钱与公钥相关联，并且付款是 将一定数量的资金从一个公钥转移到另一个公钥的数字签名。本质上， Bitcoin 将所有已处理的付款组织在区块链中，B1、B2、. 。 ., 每个由多个组成 付款，使得 B1 的所有付款以任何顺序进行，然后是 B2 的所有付款以任何顺序进行， 等等，构成了一系列有效的支付。每个区块平均每 10 分钟生成一次。 这个区块序列是一条链，因为它的结构是为了确保任何变化，即使是 在单个块中，渗透到所有后续块中，从而更容易发现任何更改 付款历史记录。 （正如我们将看到的，这是通过在每个块中包含一个加密货币来实现的 前一个的hash。）这样的块结构被称为blockchain。 假设：诚实的大多数计算能力 Bitcoin 假设没有恶意 实体（也不是协调的恶意实体的联盟）控制着大部分计算 专门用于区块生成的电力。事实上，这样的实体能够修改 blockchain，从而根据需要重写付款历史记录。特别是，它可以进行付款\(\wp\)， 获得所支付的利益，然后“抹掉”任何 \(\wp\) 的痕迹。 技术问题1： 计算浪费 Bitcoin 的 proof-of-work 阻止方法 生成需要大量的计算。目前，仅有几百人 系统中数千个公钥，前500名最强大的超级计算机只能聚集 仅占 Bitcoin 玩家所需总计算能力的 12.8%。这个 如果更多的用户加入系统，计算量将大大增加。 技术问题2：权力集中 今天，由于数量过多 需要计算，用户试图使用普通桌面（更不用说一个 手机），预计会赔钱。事实上，为了用普通计算机计算一个新的块， 计算所需电力的预期成本超出了预期奖励。 仅使用专门构建的计算机池（除了“挖掘新块”之外不执行任何操作），一台 可能期望通过生成新区块来获利。因此，今天事实上有两个 不相交的用户类别：仅进行支付的普通用户和专门的矿池， 只搜索新块。 因此，截至最近，块的总计算能力不足为奇。 一代仅集中在五个池内。在这种情况下，假设大多数 诚实的计算能力变得不那么可信。 技术问题3：歧义 在 Bitcoin 中，blockchain 不一定是唯一的。确实 它的最新部分经常分叉：blockchain 可能是——比如说——B1，. 。 。 , Bk, B′ k+1，B′ k+2，根据 一个用户，B1，. 。 。 , Bk, B′′ k+1，B′′ k+2，B′′ 根据另一位用户的说法，k+3。只有在几个块之后 已添加到链中，是否可以合理确定前 k + 3 个块将是相同的 对于所有用户。因此，人们不能立即依赖最后一个区块中包含的付款 链条。更谨慎的做法是等待，看看区块是否足够深入 blockchain 因此足够稳定。 另外，还提出了对 Bitcoin.1 的执法和货币政策担忧。 1.2 Algorand，简而言之 设置 Algorand 在非常艰难的环境中工作。简而言之， (a) 免许可和许可环境。 Algorand 甚至可以高效、安全地工作 在完全无需许可的环境中，允许任意多个用户加入 系统随时进行，无需任何审查或任何形式的许可。当然，Algorand 有效 在许可的环境中甚至更好。 1Bitcoin 付款提供的（伪）匿名可能会被滥用于洗钱和/或融资 犯罪分子或恐怖组织。传统的纸币或金条，原则上可以提供完美的 匿名性，应该会带来同样的挑战，但这些货币的物理性大大减慢了货币流通速度 转移，以便执法机构能够进行一定程度的监督。 “印钞”的能力是民族国家最基本的权力之一。因此，原则上，大规模 采用独立浮动的货币可能会削弱这种力量。然而，目前 Bitcoin 还远未实现 对政府货币政策构成威胁，但由于其可扩展性问题，可能永远不会构成威胁。(b) 非常敌对的环境。 Algorand 抵御非常强大的对手，他可以 (1) 在任何他想要的时间立即腐蚀任何他想要的用户，前提是，在 无许可环境下，系统中2/3的资金属于诚实用户。 （在一个 许可的环境下，不考虑钱，只要有2/3的用户是诚实的就够了。） (2) 完全控制并完美协调所有腐败用户；和 (3) 安排所有消息的传送，前提是每条消息 m 由诚实用户发送 在 \(\lambda\)m 时间内达到 95% 的诚实用户，这完全取决于 m 的大小。 主要性能 尽管存在我们强大的对手，在 Algorand • 所需的计算量极小。本质上，无论有多少用户 在系统中，一千五百个用户中的每一个必须执行最多几秒钟的操作 计算。 • 新区块在 10 分钟内生成，并且实际上永远不会离开 blockchain。 例如，预计第一个实施例中生成块的时间会更少 比 Λ + 12.4\(\lambda\)，其中 Λ 是在点对点八卦中传播区块所需的时间 时尚，无论选择什么块大小，\(\lambda\) 是传播 1,500 个 200Blong 消息的时间。 （因为在真正去中心化的系统中，Λ 本质上是一种内在的延迟，在 Algorand 块生成的限制因素是网络速度。）第二个实施例有 实际上经过实验测试（通过？），表明在不到 40 的时间内生成了一个块 秒。 此外，Algorand 的 blockchain 的分叉概率可以忽略不计（即小于 1） 以一万亿计），因此用户可以在新区块中立即进行支付 块出现。 • 所有权力都属于用户自己。 Algorand 是一个真正的分布式系统。特别是， 不存在可以控制哪些交易的外源实体（如 Bitcoin 中的“矿工”） 被认可。 Algorand 的技术。 1. 一种新的、快速的拜占庭协议。 Algorand 通过生成一个新块 一种新的加密、消息传递、二进制拜占庭协议 (BA) 协议，BA⋆。协议 BA⋆不仅满足一些附加属性（我们将很快讨论），而且速度也非常快。 粗略地说，它的二进制输入版本由一个 3 步循环组成，其中玩家 i 发送一个 向所有其他玩家发送消息 mi。在完整同步的网络中执行，具有更多 超过 2/3 的玩家是诚实的，概率 > 1/3，在每次循环后协议结束 协议。 （我们强调协议 BA⋆满足拜占庭协议的原始定义 Pease、Shostak 和 Lamport [31] 的版本，没有任何削弱。） Algorand 利用这个二进制 BA 协议在我们不同的通信中达成一致 模型，在每个新块上。然后通过规定数量的区块来验证商定的区块 适当验证者的数字签名，并通过网络传播。 2. 密码排序。虽然速度非常快，但 BA⋆ 协议将受益于进一步的 数百万用户播放时的速度。因此，Algorand 选择 BA⋆ 的球员为所有用户集合的一个小得多的子集。避免不同类型的权力集中 问题，每个新区块 Br 将通过新的 BA⋆ 执行来构建并达成一致， 由一组单独选定的验证者，SV r。原则上，选择这样一个集合可能会像 直接选择Br。我们通过一种我们称之为“拥抱”的方法来解决这个潜在的问题 莫里斯 \(\cdot\) 赫利希（Maurice Herlihy）富有洞察力的建议，密码抽签。排序的做法是 从大量符合条件的个人中随机选择官员[6]。 （进行了排序 跨越几个世纪：例如，雅典、佛罗伦萨和威尼斯共和国。在现代司法中 系统中，通常采用随机选择来选择陪审团。最近还进行了随机抽样 David Chaum [9] 提倡选举。）当然，在去中心化系统中，选择 随机选择每个验证者集合 SV r 的成员所需的随机硬币是有问题的。 因此，我们求助于密码学，以便从所有用户群体中选择每个验证者集， 以保证自动（即不需要消息交换）和随机的方式。 本质上，我们使用密码学函数来自动确定，从前一个块 Br−1，用户，领导者，负责提议新区块 Br，验证者集合 SV r，在 负责就领导者提出的区块达成一致。由于恶意用户可能会影响 Br−1 的组成（例如，通过选择它的一些付款），我们专门构建和使用 额外的输入，以证明第 r 个区块的领导者和验证者集 SV r 确实是 随机选择的。 3. 数量（种子） Qr.我们使用 blockchain 中的最后一个块 Br−1 自动确定下一个验证者集和负责构建新区块的领导者 Br。这种方法的挑战在于，只需在支付方式中选择略有不同的支付方式 上一轮，我们强大的对手对下一个领导者获得了巨大的控制权。即使他 只控制系统中1/1000的玩家/金钱，他可以保证所有的领导者 恶意的。 （参见直觉第 4.1 节。）这一挑战是所有 proof-of-stake 方法的核心， 据我们所知，到目前为止，这个问题还没有得到令人满意的解决。 为了应对这一挑战，我们有目的地构建并不断更新一个单独的、仔细的 定义的数量 Qr，可以证明，它不仅是不可预测的，而且也是不可影响的，由我们 强大的对手。我们可以将 Qr 称为第 r 个种子，因为 Algorand 从 Qr 中选择， 通过秘密密码抽签，所有在生成中扮演特殊角色的用户 第 r 个块。 4. 秘密密码分类和秘密凭证。随机且明确地使用当前最后一个区块 Br−1，以选择验证者集和负责的领导者 仅仅构建新区块 Br 还不够。由于在生成 Br 之前必须知道 Br−1， Br−1 中包含的最后一个不受影响的量 Qr−1 也必须已知。据此，所以 是负责计算区块 Br 的验证者和领导者。因此，我们强大的对手 在他们参与任何有关 Br 的讨论之前，可能会立即腐蚀他们所有人，以便获得 完全控制他们认证的区块。 为了防止这个问题，领导者（实际上也是验证者）秘密地了解他们的角色，但可以 计算一个适当的凭证，能够向每个人证明确实具有该角色。当 用户私下意识到他是下一个区块的领导者，首先他秘密地组装他的 自己提议的新区块，然后将其与他自己的区块一起传播（以便可以被认证） 凭证。这样，虽然对手会立即意识到谁是下一个领导者 阻止是，尽管他可以立即腐蚀他，但对手要阻止他就为时已晚了。 影响新区块的选择。确实，他不能再“回拨”领导的消息了强大的政府无法将维基解密病毒式传播的信息放回瓶子里。 正如我们将看到的，我们不能保证领导者的唯一性，也不能保证每个人都确定谁是领导者 就是，包括领导本人！但是，在 Algorand 中，将保证取得明确的进展。 5. 球员可替换性。在他提出一个新的区块后，领导者可能会“死”（或者被 被对手腐蚀了），因为他的工作已经完成了。但是，对于 SV r 中的验证者来说，事情就少了 简单。事实上，负责用足够多的签名来验证新区块 Br， 他们必须首先在领导者提议的区块上运行拜占庭协议。问题是， 无论效率如何，BA⋆需要多个步骤以及> 2/3的玩家的诚实。 这是一个问题，因为出于效率原因，BA⋆的参与者集由小集SV r组成 从所有用户集中随机选择。因此，我们强大的对手虽然无法 腐败了所有用户的1/3，当然可以腐败SV r的所有成员！ 幸运的是，我们将证明通过以点对点方式传播消息来执行的协议 BA⋆ 是玩家可替换的。这一新颖的要求意味着协议正确且 即使每个步骤都是由全新的、随机的执行，也能有效地达成共识 以及独立挑选的球员。因此，对于数百万用户来说，每一小部分玩家 与 BA 的一个步骤相关联，很可能与下一组有空的交集。 另外，BA⋆不同阶段的玩家集合可能会有完全不同的 基数。此外，每组的成员都不知道下一组的玩家是谁 是，并且不秘密传递任何内部状态。 可替换球员的属性实际上对于击败动态且非常强大的球员至关重要 我们设想的对手。我们相信可替换球员协议将在许多方面发挥至关重要的作用 上下文和应用程序。特别是，它们对于安全执行小型子协议至关重要 嵌入到一个更大的玩家世界中，对手是一个充满活力的对手，他们甚至能够腐败 玩家总数中的一小部分，不难腐蚀较小范围内的所有玩家 子协议。 附加属性/技术：懒惰的诚实 诚实的用户遵循他的规定 说明，其中包括在线和运行协议。因为 Algorand 仅具有适度的 计算和通信要求，在线并运行协议“ 背景”并不是重大牺牲。当然，诚实的玩家中也有一些“缺席”，比如 由于突然失去连接或需要重新启动，会被自动容忍（因为 我们总是可以认为这样的少数玩家暂时是恶意的）。然而，我们要指出的是， Algorand 可以简单地进行调整，以便在新模型中工作，在该模型中诚实的用户 大部分时间都在离线状态。我们的新模型可以非正式地介绍如下。 懒惰的诚实。粗略地说，用户 i 是懒惰但诚实的，如果 (1) 他遵循他的所有规定 当他被要求参加协议时的指示，并且 (2) 他被要求参加 很少会遵守该协议，并且会提前发出适当的通知。 有了如此宽松的诚实观念，我们可能会更加确信诚实的人会 当我们需要它们时就在手边，并且 Algorand 保证，在这种情况下， 即使在给定时间点，系统也可以安全运行 大多数参与的玩家都是恶意的。1.3 密切相关的工作 工作量证明方法（如引用的 [29] 和 [4]）与我们的方法非常正交。也是如此 基于消息传递拜占庭协议或实用拜占庭容错的方法 （如引用的 [8]）。事实上，这些协议不能在所有用户组中运行，也不能， 在我们的模型中，仅限于一小部分用户。事实上，我们的强大对手是我的 立即破坏一小部分负责实际运行 BA 协议的所有用户。 我们的方法可以被认为与权益证明 [2] 有关，从某种意义上说，用户的“权力” 区块建设中的资金与他们在系统中拥有的资金成正比（而不是——比如说—— 他们存入“托管”的资金）。 最接近我们的论文是 Pass 和 Shi [30] 的 Sleepy Consensus Model。为了避免 proof-of-work 方法需要大量计算，他们的论文依赖于（并且友善地 学分）Algorand 的秘密密码抽签。有了这个关键的共同点，几个 我们的论文之间存在显着差异。特别是， (1) 它们的设置仅被允许。相比之下，Algorand 也是一个无需许可的系统。 (2) 他们使用中本风格的协议，因此他们的 blockchain 经常分叉。虽然 放弃 proof-of-work，在他们的协议中，要求秘密选出的领导人延长 最长有效（更丰富的意义上）blockchain。因此，分叉是不可避免的，人们必须等待 该区块在链中足够“深入”。 事实上，与对手一起实现他们的目标 能够自适应损坏，它们需要一个深度为 Poly(N) 的块，其中 N 代表 系统中的用户总数。请注意，即使假设可以生成一个块 一分钟内，如果有 N = 1M 用户，则需要等待大约 2M 年 一个区块变成 N 2 深，大约需要 2 年时间才能让一个区块变成 N 深。相比之下， Algorand 的 blockchain 分叉的概率可以忽略不计，即使对手腐败 用户可以立即自适应地使用它的新块，并且可以立即依赖它。 (3) 他们不处理单独的拜占庭协议。 从某种意义上说，他们只是保证 “最终就一系列不断增长的价值观达成共识”。他们的协议是状态复制协议，而不是 比 BA 更重要，并且不能用于就个人利益价值达成拜占庭协议。 相比之下，如果需要的话，Algorand 也只能使用一次，以使数百万用户能够快速 就特定的利息价值达成拜占庭协议。 (4) 它们需要弱同步时钟。也就是说，所有用户的时钟都偏移了一个小时间 δ。相比之下，在 Algorand 中，时钟只需要（本质上）具有相同的“速度”。 (5) 他们的协议适用于懒惰但诚实的用户或诚实的大多数在线用户。 他们善意地赞扬 Algorand 提出了诚实用户集体下线的问题，并感谢 对此提出了懒惰诚实模型。他们的协议不仅适用于懒惰的人 诚实模型，但也在他们的对抗性昏昏欲睡模型中，对手选择哪些用户 哪些是在线的，哪些是离线的，前提是大多数在线用户在任何时候都是诚实的。2 2他们论文的原始版本实际上只考虑了对抗性昏昏欲睡模型中的安全性。 的 Algorand 的原始版本（先于他们的版本）也明确设想假设给定的大多数 在线玩家总是诚实的，但明确地将其排除在考虑范围之外，转而支持懒惰的诚实模型。 （例如，如果在某个时间点，一半的诚实用户选择下线，那么大多数用户 网上的内容很可能是恶意的。因此，为了防止这种情况发生，对手应该强迫他的大部分 腐败的玩家也会下线，这显然违背了他自己的利益。）请注意，一个拥有多数票的协议 如果大多数在线用户总是恶意的，那么懒惰但诚实的玩家就可以正常工作。之所以如此，是因为 足够数量的诚实玩家知道自己在某个罕见的时间点将发挥至关重要的作用，因此会选择 在那些时刻不要离线，也不能被对手强迫离线，因为他不知道谁是 诚实的玩家可能是至关重要的。(6) 他们需要简单诚实的多数。相比之下，当前版本的 Algorand 需要 2/3 诚实的多数。 我们身边的另一篇论文是 Ouroboros：一种可证明安全的权益证明区块链协议， 作者：Kiayias、Russell、David 和 Oliynykov [20]。他们的系统也出现在我们的系统之后。它还 使用密码抽签以可证明的方式免除工作量证明。然而，他们的 系统又是一种中本风格的协议，其中分叉是不可避免且频繁的。 （然而，在他们的模型中，区块不需要像昏昏欲睡的共识模型那么深。） 而且， 他们的系统依赖于以下假设：用作者自己的话说，“（1） 网络高度同步，（2）大多数选定的利益相关者都可以根据需要使用 参与每个时代，（3）利益相关者不会长时间离线， (4) 损坏的自适应性会受到一个小的延迟的影响，该延迟以轮数为线性单位进行测量 安全参数。”相比之下，Algorand 极有可能是无分叉的，并且 不依赖这 4 个假设中的任何一个。特别是，在 Algorand 中，对手能够 瞬间腐蚀他想要控制的用户。
预备知识
2.1 密码原语 理想的哈希。 我们将依赖于一个高效可计算的密码 hash 函数 H， 将任意长的字符串映射为固定长度的二进制字符串。遵循悠久的传统，我们建模 H 作为一个随机 oracle，本质上是一个将每个可能的字符串 s 映射到随机和 独立选择（然后固定）所选长度的二进制字符串 H(s)。 在本文中，H 具有 256 位长输出。事实上，这样的长度足够短，可以使 系统高效且足够长以确保系统安全。例如，我们希望 H 具有碰撞弹性。也就是说，应该很难找到两个不同的字符串 x 和 y 使得 H(x) = H(y)。 当 H 是具有 256 位长输出的随机 oracle 时，找到任何这样的字符串对确实是 困难。 （随机尝试并依赖生日悖论，需要 2256/2 = 2128 试验。） 数字签名。 数字签名允许用户相互验证信息 无需共享任何共享密钥。 数字签名方案由三个快速 算法：概率密钥生成器 G、签名算法 S 和验证算法 V。 给定一个安全参数 k（一个足够大的整数），用户 i 使用 G 生成一对 k 位密钥（即字符串）：“公共”密钥 pki 和匹配的“秘密”签名密钥 ski。至关重要的是，一个 公钥不会“背叛”其相应的秘密密钥。也就是说，即使了解 pki，也不能 除了我之外，还有人能够在不到天文时间的时间内计算出滑雪。 用户 i 使用ski 对消息进行数字签名。对于每个可能的消息（二进制字符串）m, i 首先 hashes m，然后对输入 H(m) 和 ski 运行算法 S，以生成 k 位字符串 sigpki(m) \(\triangleq\)S(H(m), 滑雪) .3 3 由于 H 具有抗碰撞能力，因此实际上不可能通过签署 m 来“意外地签署”不同的 消息 m′。二进制串 sigpki(m) 被称为 i 对 m 的数字签名（相对于 pki），可以表示为 当公钥 pki 从上下文中清晰可见时，更简单地表示为 sigi(m)。 每个知道 pki 的人都可以用它来验证 i 生成的数字签名。具体来说，关于 输入 (a) 玩家 i 的公钥 pki，(b) 消息 m，以及 (c) 字符串 s，即 i 被称为 消息 m 的数字签名，验证算法 V 输出 YES 或 NO。 我们要求数字签名方案具有以下属性： 1. 合法签名总是经过验证的：如果 s = sigi(m)，则 V (pki, m, s) = Y ES；和 2. 数字签名很难伪造：在不了解滑雪知识的情况下，找到这样的字符串的时间 对于从未由 i 签名的消息 m，V (pki, m, s) = Y ES 的长度是天文数字。 （遵循 Goldwasser、Micali 和 Rivest [17] 的强大安全要求，这是事实 即使可以获得任何其他消息的签名。） 因此，为了防止其他人代表他签署消息，玩家必须保留他的 签署密钥滑雪秘密（因此称为“秘密密钥”），并使任何人都可以验证消息 他确实签名了，我有兴趣公开他的密钥 pki（因此称为“公钥”）。 一般来说，消息 m 无法从其签名 sigi(m) 中检索。为了虚拟地进行交易 具有满足概念上方便的“可检索性”属性的数字签名（即， 保证签名者和消息可以很容易地从签名中计算出来，我们定义 SIGpki(m) = (i, m, sigpki(m)) 和 SIGi(m) = (i, m, sigi(m))，如果 pki 明确。 独特的数字签名。 我们还考虑满足以下条件的数字签名方案（G，S，V） 以下附加属性。 3.独特性。很难找到满足以下条件的字符串 pk′、m、s 和 s′ s̸=s′ 和 V (pk', m, s) = V (pk', m, s') = 1。 （请注意，唯一性属性也适用于不是合法生成的字符串 pk′ 公钥。 然而，特别是，唯一性属性意味着，如果人们使用 指定密钥生成器 G 来计算公钥 pk 以及匹配的密钥 sk， 因此知道 sk，他基本上也不可能找到两个不同的数字 相同消息相对于 pk 的签名。） 备注 • 从独特的签名到可验证的随机函数。 相对于数字 具有唯一性属性的签名方案，映射 m \(\to\) H(sigi(m)) 关联到 每个可能的字符串 m，一个唯一的、随机选择的 256 位字符串，以及该字符串的正确性 给定签名 sigi(m) 即可证明映射。 即理想的hashing和数字签名方案本质上满足唯一性 提供可验证随机函数的基本实现，如所介绍的和 米卡利、拉宾和瓦丹 [27]。 （他们最初的实现必然更复杂， 因为他们不依赖于理想的 hashing。）• 数字签名的三种不同需求。在 Algorand 中，用户 i 依赖数字 签名为 (1) 验证我自己的付款。在此应用程序中，密钥可以是“长期的”（即，用于 在很长一段时间内对许多消息进行签名）并且来自普通的签名方案。 (2) 生成凭证，证明 i 有权在第 r 轮的某些步骤 s 中采取行动。在这里， 密钥可以是长期的，但必须来自满足唯一性属性的方案。 (3) 验证i在其执行的每个步骤中发送的消息。 这里，键必须是 短暂的（即在第一次使用后被销毁），但可以来自普通的签名方案。 • 小成本的简化。为简单起见，我们设想每个用户 i 都有一个长期密钥。因此，这样的密钥必须来自具有唯一性的签名方案 财产。这种简单性的计算成本很小。事实上，通常独特的数字 签名的生成和验证成本比普通签名稍高。 2.2 理想化的公共账本 Algorand 尝试模仿以下基于理想化公共分类账的支付系统。 1. 初始状态。金钱与个人公钥（私人生成和 归用户所有）。令 pk1, . 。 。 , pkj 是初始公钥，a1, . 。 。 , aj 各自的 初始金额单位，则初始状态为 S0 = (pk1, a1), . 。 。 , (pkj, aj), 假设这是系统中的常识。 2. 付款。设 pk 为当前拥有 \(\geq\)0 货币单位的公钥，pk′ 为另一个公钥 key，a′是不大于a的非负数。那么，（有效）支付 \(\wp\) 是一个数字 签名，相对于pk，指定a′货币单位从pk到pk′的转移，一起 以及一些附加信息。在符号中， \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), 其中 I 代表任何被认为有用但不敏感的附加信息（例如，时间 信息和付款标识符），以及任何被视为敏感的其他信息（例如， 付款原因，可能是 pk 和 pk' 所有者的身份，等等）。 我们将 pk（或其所有者）称为付款人，将每个 pk'（或其所有者）称为收款人，将 a' 称为收款人 付款金额\(\wp\)。 通过付款免费加入。请注意，用户可以随时通过以下方式加入系统 生成自己的公钥/密钥对。相应地，出现在中的公钥pk' 上面的支付\(\wp\)可能是新生成的公钥，从未“拥有”任何钱 之前。 3.魔法账本。在理想化系统中，所有付款都是有效的，并以防篡改的方式显示 L组付款清单“贴在天上”供大家查看： L = 支付 1，支付 2，. 。 。 ,每个区块 PAY r+1 包含自区块出现以来所有支付的集合 支付 r。在理想的系统中，一个新的块会在固定（或有限）的时间后出现。 讨论。 • 更一般的支付和未花费的交易输出。 更一般地，如果公钥 pk 拥有金额 a，那么 pk 的有效支付 \(\wp\) 可以转移金额 a′ 1、a′ 2、. 。 ., 分别对应键 pk′ 1、pk′ 2、. 。 .,只要P j a′ j\(\leq\)a。 在 Bitcoin 和类似系统中，公钥 pk 拥有的资金被分成单独的 金额，并且 pk 进行的支付 \(\wp\) 必须全部转移这样的隔离金额 a。 如果 pk 希望仅将 a 的一小部分 a′ < a 转移到另一个密钥，那么它还必须将 余额，未使用的交易输出，到另一个密钥，可能是 pk 本身。 Algorand 也适用于具有隔离金额的密钥。然而，为了集中精力 Algorand 的新颖方面，从概念上讲，坚持我们更简单的付款方式更简单 以及具有与其关联的单一金额的密钥。 • 当前状态。理想化方案不直接提供有关当前情况的信息 系统的状态（即每个公钥有多少货币单位）。此信息 可以从魔法账本中推断出来。 在理想的系统中，活跃用户不断存储和更新最新的状态信息， 否则他就必须重建它，要么从头开始，要么从上次他 计算了一下。 （在本文的下一版本中，我们将增强 Algorand 以使其能够 用户以有效的方式重建当前状态。） • 安全和“隐私”。 数字签名保证任何人都无法伪造付款 另一个用户。在支付\(\wp\)中，公钥和金额不是隐藏的，而是敏感的 信息我是。事实上，只有 H(I) 出现在 \(\wp\) 中，并且由于 H 是理想的 hash 函数，因此 H(I) 是一个随机的 256 位值，因此无法找出我比 只是猜测而已。然而，为了证明我是什么（例如，证明付款的原因） 付款人可以直接透露 I。所透露的 I 的正确性可以通过计算 H(I) 来验证 并将结果值与 \(\wp\) 的最后一项进行比较。事实上，由于 H 具有碰撞弹性， 很难找到第二个值 I′ 使得 H(I) = H(I′)。 2.3 基本概念和符号 密钥、用户和所有者 除非另有说明，每个公钥（简称“密钥”）都是长期的，并且与具有唯一性的数字签名方案相关。我加入的公钥 当系统中已有另一个公钥 j 向 i 付款时，系统将执行此操作。 对于颜色，我们将钥匙拟人化。我们将密钥 i 称为“他”，表示我是诚实的，我发送 并接收消息等。 User 是 key 的同义词。当我们想要区分一个键时 对于它所属的人，我们分别使用术语“数字密钥”和“所有者”。 免许可和许可系统。 如果数字密钥是免费的，则系统是无需许可的 随时加入，一个所有者可以拥有多个数字钥匙；并获得许可，否则。独特的表现 Algorand 中的每个对象都有一个唯一的表示。特别是， 每个集合 {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . 。 .} 以预先指定的方式排序：例如，first 按字典顺序先在 x 中，然后在 y 中，依此类推。 同速时钟 没有全局时钟：相反，每个用户都有自己的时钟。用户时钟 不需要以任何方式同步。然而，我们假设它们都具有相同的速度。 例如，当根据用户i的时钟是中午12点时，根据用户i的时钟，可能是下午2:30 另一个用户j的时钟，但是当根据i的时钟为12:01时，根据i的时钟为2:31 到j的时钟。也就是说，“一分钟对于每个用户来说都是相同的（充分、本质上相同）”。 回合 Algorand 以逻辑单元组织，r = 0, 1, . 。 .，称为回合。 我们一贯使用上标来表示轮次。表示非数字量 Q （例如，字符串、公钥、集合、数字签名等）指的是一轮r，我们简单地写成Qr。 仅当 Q 是一个真正的数字（而不是可解释为数字的二进制字符串）时，才执行 我们写成Q(r)，这样符号r就不能被解释为Q的指数。 在（a的开始）r > 0轮时，所有公钥的集合是PKr，系统状态是 锶= n 我，一个(r) 我，. 。 。 : i \(\in\) PKro , 其中a(r) 我 是公钥 i 可用的金额。请注意，PKr 可从 Sr，并且Sr还可以为每个公钥i指定其他组件。 对于第0轮，PK0是初始公钥的集合，S0是初始状态。 PK0 和 S0 被假设为系统中的常识。为简单起见，在 r 轮开始时，所以 是 PK1, . 。 。 ，PKr 和 S1，。 。 。 ，先生。 在r轮中，系统状态从Sr转变为Sr+1：象征性地， r轮：Sr−→Sr+1。 付款方式 在 Algorand 中，用户不断进行付款（并以以下方式传播） 第 2.7 节中描述）。用户 i \(\in\)PKr 的支付 \(\wp\) 具有相同的格式和语义 就像在理想系统中一样。即， \(\wp\)= SIGi(i, i′, a, I, H(I)) 。 付款 \(\wp\) 在第 r 轮中单独有效（简称为第 r 轮付款），如果 (1) 其金额 a 小于或等于 a(r) i ，并且 (2) 它不会出现在任何官方支付集 PAY r′ 中，因为 r′ < r。 （如下所述，第二个条件意味着 \(\wp\) 尚未生效。 如果 i 的一组 r 轮付款的金额之和最多为 a(r)，则它们集体有效 我。 支付方式 r 轮支付集 P 是 r 轮支付的集合，使得对于每个用户 i，支付 P 中的 i 个（可能没有）集体有效。所有 r 轮支付集的集合是 PAY(r)。一轮R 如果 P 的超集不是第 r 轮支付集，则支付集 P 是最大的。 我们实际上建议支付 \(\wp\)也指定一轮 \(\rho\)， \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) ， 对于某个固定的非负整数 k.4，在 [\(\rho\), \(\rho\) + k] 之外的任何一轮都无效 4这简化了检查\(\wp\)是否已变得“有效”（即，它简化了确定某些支付集是否 PAY r 包含 \(\wp\)。当 k = 0 时，如果 \(\wp\)= SIGi(r, i, i′, a, I, H(I)) 且 \(\wp\)/\(\varepsilon\)PAY r，则 i 必须重新提交 \(\wp\)。官方支付 对于每一轮 r，Algorand 公开选择（以稍后描述的方式） 单个（可能是空的）支付集，PAY r，该轮的官方支付集。 （本质上，PAY r 代表 “实际”发生的 R 轮付款。） 与理想系统（和Bitcoin）一样，（1）新用户j进入系统的唯一途径 是属于给定回合 r 的官方支付集 PAY r 的付款的接收者；和 (2) PAY r 根据本轮的状态 Sr 确定下一轮的状态 Sr+1。 象征性地， 支付 r : Sr −→Sr+1。 具体来说， 1.第r+1轮的公钥集合PKr+1，由PKr和所有的集合的并集组成 首次出现在 PAY r 付款中的收款人密钥；和 2.金额a(r+1) 我 用户 i 在第 r + 1 轮中拥有的资产是 ai(r) 的总和，即 我在上一轮中拥有的金额（如果 i ̸\(\varepsilon\)PKr 则为 0）— 以及金额总和 根据PAY r的付款方式支付给i。 总之，就像在理想系统中一样，每个状态 Sr+1 都可以从之前的付款历史中扣除： 支付0，. 。 。 , 支付 r。 2.4 区块和已验证的区块 在 Algorand0 中，对应于一轮 r 的块 Br 指定： r 本身；的支付集合 r 轮，支付 r；需要解释的数量 Qr 以及前一个块的 hash H(Br−1)。 因此，从某个固定块 B0 开始，我们有一个传统的 blockchain： B1 = (1, 支付 1, Q0, H(B0)), B2 = (2, 支付 2, Q1, H(B1)), B3 = (3, 支付 3, Q2, H(B2)), 。 。 。 在 Algorand 中，块的真实性实际上是由一条单独的信息来保证的， “区块证书”CERT r，它将 Br 变成经过验证的区块 Br。因此，魔法账本 通过已证明的块的顺序来实现， B1、B2、. 。 。 讨论 正如我们将看到的，CERT r 由一组 H(Br) 的数字签名组成， SV r 的大多数成员，以及每个成员确实属于的证明 到 SV r。当然，我们可以将证书 CERT r 包含在块本身中，但是会发现它 概念上更清晰，以将其分开。） 在 Bitcoin 中，每个块必须满足一个特殊属性，即必须“包含 加密难题”，这使得区块生成需要大量计算，并且分叉不可避免 而且并不罕见。相比之下，Algorand 的 blockchain 有两个主要优点：它是用 最小的计算量，并且它不会以极高的概率分叉。每个块Bi是 一旦进入blockchain，就安全地结束。2.5 可接受的故障概率 为了分析 Algorand 的安全性，我们指定概率 F，我们愿意使用该概率 接受出现问题的情况（例如，验证者集 SV r 没有诚实多数）。 与加密 hash 函数 H 的输出长度的情况一样，F 也是一个参数。 但是，在这种情况下，我们发现将 F 设置为一个具体值很有用，以便获得更直观的结果 掌握这样一个事实：在 Algorand 中，确实可以同时享受足够的安全 和足够的效率。为了强调F是可以根据需要设置的参数，在第一个 和第二实施例我们分别设置 F = 10−12 和 F = 10−18 。 讨论 请注意，10−12 实际上小于万亿分之一，我们相信这样的 在我们的应用中选择 F 就足够了。让我们强调 10−12 不是概率 对手可以用它伪造诚实用户的付款。所有付款均以数字方式进行 签名，因此，如果使用正确的数字签名，伪造付款的概率为 远低于 10−12，事实上，本质上是 0。我们愿意容忍的坏事件 概率 F 是 Algorand 的 blockchain 分叉。请注意，我们设置 F 和 在一分钟长的回合中，预计 Algorand 的 blockchain 中出现分叉的频率为 （大约）190 万年一次。相比之下，在 Bitcoin 中，分叉经常发生。 要求较高的人可以将F设置为较低的值。为此，在我们的第二实施例中 我们考虑将 F 设置为 10−18。注意，假设每秒生成一个区块，1018 是迄今为止宇宙所花费的估计秒数：从大爆炸到现在 时间。因此，在 F = 10−18 的情况下，如果一秒内生成一个区块，则应该预期其年龄为 宇宙看到一个叉子。 2.6 对抗模型 Algorand 被设计为在非常对抗的模型中是安全的。让我们解释一下。 诚实用户和恶意用户 如果用户遵循所有协议说明，则他是诚实的，并且 完全有能力发送和接收消息。用户是恶意的（即拜占庭，在 分布式计算的用语）如果他可以任意偏离他规定的指令。 对手 对手是一种高效的（技术上多项式时间）算法，以颜色拟人化，他可以在任何他想要的时间立即对任何他想要的用户进行恶意攻击（主题 仅限于他可以破坏的用户数量的上限）。 对手完全控制并完美协调所有恶意用户。他采取一切行动 代表他们，包括接收和发送他们的所有消息，并可以让他们偏离 他们以任意方式规定的指示。或者他可以简单地隔离发送损坏的用户 并接收消息。让我们澄清一下，没有其他人会自动得知用户 i 是恶意的， 尽管我的恶意可能会通过对手让他采取的行动而显现出来。 然而这个强大的对手， • 不具备无限的计算能力，无法成功伪造数字 诚实用户的签名，除非概率可以忽略不计；和• 不能以任何方式干扰诚实用户之间的消息交换。 此外，他攻击诚实用户的能力受到以下假设之一的限制。 诚信占多数金钱 我们考虑诚实多数货币 (HMM) 的连续体 假设：即对于每个非负整数 k 且实数 h > 1/2， HHMk > h：每轮 r 中的诚实用户拥有的所有资金中的一部分大于 h 系统在 r −k 轮。 讨论。 假设所有恶意用户完美地协调他们的行动（就好像被控制一样） 由单一实体（即对手）造成的）是一个相当悲观的假设。之间也完美协调 很多个人是很难实现的。也许协调只发生在不同的群体中 的恶意玩家。但是，由于无法确定恶意用户的协调程度 可能会享受，我们最好是安全而不是后悔。 假设攻击者也可以秘密地、动态地、立即地破坏用户 悲观的。毕竟，实际上，完全控制用户的操作应该需要一些时间。 例如，假设 HMMk > h 意味着，如果实施一轮（平均） 那么，在一分钟内，某一轮的大部分资金将留在诚实的手中 如果 k = 120，则至少 2 小时；如果 k = 10, 000，则至少 1 周。 请注意，HMM 假设和之前的诚实多数计算能力 假设是相关的，因为计算能力可以用金钱购买， 如果恶意用户拥有大部分资金，那么他们就可以获得大部分算力。 2.7 沟通模式 我们设想消息传播——即“点对点八卦”5——是唯一的手段 沟通。 临时假设：全网消息及时传递。 对于 本文的大部分内容我们假设每条传播的消息都到达了几乎所有诚实的用户 及时。我们将在第 10 节中删除这个假设，在第 10 节中我们处理网络 分区，无论是自然发生的还是敌对引起的。 （正如我们将看到的，我们只假设 在网络的每个连接组件内及时传递消息。） 捕获传播消息（在整个网络中）的及时传递的一种具体方法是 以下： 对于所有可达性 \(\rho\) > 95% 且消息大小 \(\mu\) \(\in\)Z+，存在 \(\lambda\) \(\rho\),\(\mu\) 使得， 如果诚实的用户在时间 t 传播 \(\mu\) 字节消息 m， 那么到时间 t + \(\lambda\) \(\rho\),μ 时，m 至少达到诚实用户的一小部分 \(\rho\)。 5本质上，如Bitcoin中，当用户传播消息m时，每个活跃用户i第一次接收m， 随机且独立地选择适当少量的活跃用户，即他的“邻居”，他将 m 转发给他们， 可能直到他收到他们的确认为止。当没有用户接收时 m 的传播终止 m 第一次。然而，如果没有明确且单独地设想一种由另一个用户/存储库等获取最新的 blockchain 的机制，则上述属性无法支持我们的 Algorand 协议。 事实上，构建一个新的区块 Br 不仅需要一组适当的验证者及时接收轮次 r 消息，还有前几轮的消息，以便知道 Br−1 和所有其他先前的消息 块，这是确定 Br 中的付款是否有效所必需的。 以下 假设就足够了。 消息传播 (MP) 假设： 对于所有 \(\rho\) > 95% 且 \(\mu\) \(\in\)Z+，存在 \(\lambda\) \(\rho\),\(\mu\) 这样，对于所有时间 t 以及诚实用户在 t −\(\lambda\) \(\rho\),μ 之前传播的所有 \(\mu\) 字节消息 m， m 在时间 t 之前被至少一小部分 \(\rho\) 的诚实用户接收。 协议 Algorand ' 实际上指示一小部分用户中的每一个（即，一个 Algorand ' 中一轮的给定步骤，传播（小）规定大小的单独消息， 我们需要限制完成这些指示所需的时间。我们通过充实议员来做到这一点 假设如下。 对于所有 n、\(\rho\) > 95% 且 \(\mu\) \(\in\)Z+，存在 \(\lambda\)n,\(\rho\),\(\mu\)，使得对于所有时间 t 和所有 \(\mu\) 字节 消息 m1, . 。 。 , mn，每个都由诚实用户在 t −\(\lambda\)n,\(\rho\),μ, m1,... 之前传播。 。 。 , mn 收到, 到时间 t，至少有一小部分 \(\rho\) 是诚实用户。 注意事项 • 上述假设故意简单，但也比我们论文中所需的更强。6 • 为简单起见，我们假设\(\rho\) = 1，因此不再提及\(\rho\)。 • 我们悲观地假设，只要对手不违反 MP 假设，对手 完全控制所有消息的传递。特别是在不被诚实的人注意到的情况下 用户，对手他可以任意决定哪个诚实的玩家接收哪个消息， 并任意加速传递他想要的任何消息。7
传统环境下的 BA 协议 BA⋆
正如已经强调的，拜占庭协议是 Algorand 的关键要素。确实是通过 使用这样的 BA 协议使得 Algorand 不受分叉的影响。然而，为了防止我们的 强大的对手，Algorand 必须依赖于满足新的玩家可替换性的 BA 协议 约束。此外，要使 Algorand 高效，这样的 BA 协议必须非常高效。 BA 协议最初是为理想化的通信模型、同步完整的通信模型而定义的。 网络（SC 网络）。这样的模型可以更简单地设计和分析 BA 协议。 6给定诚实百分比 h 和可接受的故障概率 F，Algorand 计算上限 N， 一个步骤中验证者的最大数量。因此，MP 假设仅需要在 n \(\leq\) N 时成立。 此外，如上所述，无论有多少其他消息可以同时传播，MP 假设都成立。 乔丹的。然而，正如我们将看到的，在 Algorand 中，消息在基本上不重叠的时间内传播 间隔，在此期间传播单个块，或者最多 N 个验证者传播一个小块（例如 200B） 消息。因此，我们可以用更弱但也更复杂的方式重申 MP 假设。 7例如，他可以立即获知诚实玩家发送的消息。因此，恶意用户 i′ 是 被要求与诚实用户 i 同时传播消息，总是可以基于以下条件选择自己的消息 m′ 消息 m 实际上是由 i 传播的。用分布式计算的术语来说，这种能力与冲刺有关 文学。因此，在本节中，我们为 SC 网络引入一种新的 BA 协议 BA⋆，并忽略 完全是球员可替换性的问题。 BA⋆协议是具有独立价值的贡献。 事实上，它是迄今为止已知的 SC 网络最有效的加密 BA 协议。 为了在我们的 Algorand 协议中使用它，我们稍微修改 BA⋆，以考虑到我们的不同 沟通模型和上下文，但请确保在第 X 节中强调如何使用 BA⋆ 在我们实际的协议 Algorand ' 内。 我们首先回顾一下 BA⋆ 的运作模式和拜占庭协议的概念。 3.1 同步完整网络和匹配对手 在 SC 网络中，有一个公共时钟，在每个积分时间 r = 1, 2,... 处滴答作响。 。 。 在每次点击 r 时，每个玩家 i 都会立即同时发送一个 留言先生 i,j（可能是空消息）发送给每个玩家 j，包括他自己。每个先生 收到 i,j 此时，玩家 j 单击 r + 1 以及发送者 i 的身份。 再次强调，在通信协议中，如果玩家遵循所有规定，那么他就是诚实的 指令，以及其他恶意行为。所有恶意玩家均被完全控制且完美 由对手协调，特别是立即收到所有发送给 恶意玩家，并选择他们发送的消息。 攻击者可以在任何奇怪的时间立即对任何诚实的用户进行恶意点击 他希望，仅受限于恶意玩家数量的可能上限。也就是说， 对手“不能干扰诚实用户 i 已经发送的消息”，这将是 照常交付。 对手还具有额外的能力，可以在每个偶数轮中立即看到 当前诚实玩家发送的消息，并立即使用该信息进行选择 恶意玩家同时发送的消息会打勾。 备注 • 对手的力量。上面的设定是非常对抗性的。事实上，在拜占庭协议中 文学作品中，许多场景都不太具有敌意。然而，一些更具对抗性的设置 也被考虑过，对手在看到诚实玩家发送的消息后，我 在给定时间单击 r，可以立即从网络上删除所有这些消息 损坏i，选择当前恶意i在单击r时发送的消息，并让它们 照常交付。对手的预期力量与他在我们的环境中所拥有的力量相匹配。 • 物理抽象。设想的通信模型抽象出一个更物理的模型， 其中每对玩家 (i, j) 通过单独的私有通信线路 li,j 连接。 也就是说，没有其他人可以注入、干扰或获取有关通过该消息发送的消息的信息 李杰。对手获取 li,j 的唯一方法是破坏 i 或 j。 • 隐私和身份验证。在 SC 网络中，消息隐私和身份验证得到保证 通过假设。相比之下，在我们的通信网络中，消息被传播 点对点之间，身份验证由数字签名保证，并且不存在隐私。 因此，要在我们的设置中采用协议 BA⋆，每条交换的消息都应该进行数字签名 （进一步确定发送的状态）。幸运的是，我们的 BA 协议 考虑在 Algorand 中使用不需要消息隐私。3.2 拜占庭协议的概念 拜占庭协议的概念是由 Pease Shostak 和 Lamport [31] 提出的 二进制情况，即每个初始值都由一位组成。不过很快就被延长了 为任意初始值。 （参见 Fischer [16] 以及 Chor 和 Dwork [10] 的调查。） 协议，我们指的是任意值协议。 定义 3.1。在同步网络中，设P为n个玩家协议，其玩家集是公共的 玩家之间的知识，t 是一个正整数，使得 n \(\geq\)2t + 1。 我们说 P 是一个 任意值（分别为二进制） (n, t) - 健全性 \(\sigma\) \(\varepsilon\)(0, 1) 的拜占庭协议 如果，对于每组不包含特殊符号 \(\bot\) 的值 V（分别，对于 V = {0, 1}），在 执行过程中，最多 t 个玩家是恶意的，并且每个玩家 i 都以 初始值 vi \(\in\)V ，每个诚实玩家 j 以概率 1 停止，输出一个值 outi \(\in\)V \(\cup\){\(\bot\)} 从而以至少 \(\sigma\) 的概率满足以下两个条件： 1. 协议：对于所有诚实玩家 i，存在 out \(\varepsilon\)V \(\cup\){\(\bot\)} 使得 outi = out。 2. 一致性：如果对于某个值 v \(\in\)V ，对于所有诚实的玩家 vi = v，则 out = v。 我们将 out 称为 P 的输出，将每个 outi 称为玩家 i 的输出。 3.3 BA 符号 # 在我们的 BA 协议中，玩家需要计算有多少玩家向他发送了给定消息 给定的步骤。因此，对于可能发送的每个可能值 v，
s
我（五） （或者当 s 清楚时只是#i(v)）是 i 在步骤 s 中从其接收 v 的玩家 j 的数量。 回想一下，玩家 i 从每个玩家 j 接收到一条消息，如果 玩家是 n，那么，对于所有 i 和 s，P v#s i(v) = n。 3.4 二进制 BA 协议 BBA⋆ 在本节中，我们提出一个新的二进制 BA 协议 BBA⋆，它依赖于更多的诚实性 超过三分之二的玩家并且速度非常快：无论恶意玩家可能做什么， 每次执行其主循环都会使玩家以 1/3 的概率达成一致。 每个玩家都有自己的数字签名方案的公钥，满足唯一签名 财产。由于该协议旨在在同步完整网络上运行，因此没有 需要一个玩家我签署他的每条消息。 数字签名用于在步骤 3 中生成足够通用的随机位。（在 Algorand 中， 数字签名也用于验证所有其他消息。） 该协议需要一个最小的设置：一个公共随机字符串 r，独立于玩家的 键。 （在 Algorand 中，r 实际上被数量 Qr 代替。） BBA⋆协议是一个三步循环，玩家反复交换布尔值，并且 不同的玩家可能会在不同的时间退出这个循环。玩家 i 通过传播退出这个循环， 在某个步骤中，要么是特殊值 0，要么是特殊值 1，从而指示所有玩家 “假装”他们在以后的所有步骤中分别从 i 接收 0 和 1。 （或者说：假设玩家 j 从另一个玩家 i 收到的最后一条消息有点 b。然后，在任意一步 其中他没有收到来自 i 的任何消息，j 的行为就好像我向他发送了位 b。） 该协议使用计数器 \(\gamma\)，表示其 3 步循环已执行的次数。 BBA⋆开始时，\(\gamma\) = 0。（人们可能认为\(\gamma\)是一个全局计数器，但实际上它是增加的 每次执行循环时由每个单独的玩家执行。） 有 n \(\geq\)3t + 1，其中 t 是恶意玩家的最大可能数量。一个二进制 字符串 x 用二进制表示形式（可能有前导 0）为 x 的整数来标识； lsb(x) 表示 x 的最低有效位。 协议BBA⋆ (通信) 步骤1. [币固定为0步骤] 每个玩家i发送bi。 1.1 如果#1 i (0) \(\geq\)2t + 1，则i设置bi = 0，发送0，输出outi = 0， 并停止。 1.2 如果#1 i(1)\(\geq\)2t+1，那么，则i设bi=1。 1.3 否则，i 设置 bi = 0。 (通信) 步骤2. [硬币固定为1步骤] 每个玩家i发送bi。 2.1 如果#2 i(1)\(\geq\)2t+1，则i设bi=1， 发送 1, 输出outi = 1， 并停止。 2.2 如果#2 i(0)\(\geq\)2t+1，则设bi=0。 2.3 否则，i 设置 bi = 1。 (通信)步骤3.[硬币翻转步骤]每个玩家i发送bi和SIGi(r,\(\gamma\))。 3.1 如果#3 i(0)\(\geq\)2t+1，则i设bi=0。 3.2 如果#3 i(1)\(\geq\)2t+1，则i设bi=1。 3.3 否则，令 Si = {j \(\in\)N 在步骤 3 中向 i 发送了正确的消息}， i 设 bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\))));将 \(\gamma\)i 增加 1；并返回步骤 1。 定理3.1。当 n \(\geq\)3t + 1 时，BBA⋆是一个二元 (n, t)-BA 协议，稳健性为 1。 定理 3.1 的证明在 [26] 中给出。它对我们的环境的适应以及玩家的可替换性 属性新颖。 历史评论 概率二进制 BA 协议首先由 Ben-Or 在 异步设置 [7]。 BBA⋆协议是对我们的公钥设置的新颖改编 Feldman 和 Micali [15] 的二进制 BA 协议。他们的协议是第一个按预期工作的协议 恒定的步数。它的工作原理是让玩家自己实现一个共同的硬币， 拉宾提出的概念，他通过外部受信任方 [32] 实施了该概念。3.5 分级共识和GC协议 让我们回想一下，对于任意值，共识的概念比拜占庭协议弱得多。 定义 3.2。设 P 是一个协议，其中所有参与者的集合都是共同知识，并且每个参与者 玩家 i 私下知道任意初始值 v′ 岛 我们说 P 是一个 (n, t) 分级共识协议，如果在 n 个玩家的每次执行中， 其中大多数 t 都是恶意的，每个诚实的玩家 i 都会停止输出价值等级对 (vi, gi)， 其中gi \(\in\){0, 1, 2}，从而满足以下三个条件： 1. 对于所有诚实的玩家 i 和 j，|gi −gj| \(\leq\)1。 2. 对于所有诚实玩家 i 和 j，gi, gj > 0 ⇒vi = vj。 3. 如果 v′ 1 = \(\cdots\) = v′ 对于某个值 v，n = v，则对于所有诚实玩家 i，vi = v 且 gi = 2。 历史注释 分级共识的概念只是源自分级共识的概念。 广播，由 Feldman 和 Micali 在 [15] 中提出，通过强化十字军的概念 协议，由 Dolev [12] 引入，并由 Turpin 和 Coan [33].8 完善 在 [15] 中，作者还提供了一个 3 步（n，t）分级广播协议，gradecast，用于 n\(\geq\)3t+1。后来发现了 n > 2t+1 的更复杂的 (n, t) 分级广播协议 作者：Katz 和 Koo [19]。 下面的两步协议 GC 由 Gradecast 的最后两步组成，用我们的表达式表示 符号。为了强调这一事实，并匹配第 4.1 节协议 Algorand ' 的步骤，我们 分别命名2和3的GC步骤。 气相色谱协议 步骤 2. 每个玩家 i 发送 v′ 我对所有玩家。 步骤 3. 每个玩家 i 向所有玩家发送字符串 x 当且仅当 #2 i(x)\(\geq\)2t+1。 输出确定。每个玩家 i 输出计算如下的对 (vi, gi)： • 如果对于某些x，#3 i (x) \(\geq\)2t + 1，则 vi = x 且 gi = 2。 • 如果对于某些x，#3 i (x) \(\geq\)t + 1，则 vi = x 且 gi = 1。 • 否则，vi = \(\bot\)且gi = 0。 定理3.2。如果n\(\geq\)3t+1，则GC是一个(n，t)分级的广播协议。 该证明紧随 [15] 中协议等级广播的证明，因此被省略。9 8本质上，在分级广播协议中，(a) 每个玩家的输入都是杰出玩家的身份 玩家，发送者，具有任意值 v 作为附加私有输入，并且 (b) 输出必须满足 与分级共识的属性 1 和 2 相同，加上以下属性 3′：如果发送者是诚实的，则 vi = v 且 对于所有诚实的玩家 i，gi = 2。 9确实，在他们的协议中，在步骤 1 中，发送者将自己的私有值 v 发送给所有玩家，并且每个玩家都让 v′ i 由他在步骤 1 中实际从发送者收到的值组成。3.6 协议 BA⋆ 现在我们通过二进制 BA 协议 BBA⋆ 来描述任意值 BA 协议 BA⋆ 以及 分级共识协议 GC。下面，每个玩家i的初始值为v′ 岛 协议 BA⋆ 步骤 1 和 2. 每个玩家 i 在输入 v′ 上执行 GC i，从而计算一对(vi，gi)。 步骤 3，. 。 。每个玩家 i 执行 BBA⋆——如果 gi = 2，初始输入为 0，否则为 1——所以 来计算位outi。 输出确定。如果 outi = 0，则每个玩家 i 输出 vi，否则输出 \(\bot\)。 定理3.3。每当 n \(\geq\)3t + 1 时，BA⋆是一个稳健性为 1 的 (n, t)-BA 协议。 证明。我们首先证明一致性，然后证明一致性。 一致性证明。假设对于某个值 v \(\in\)V , v′ i = v. 那么，根据性质 3 分级共识，GC执行后，所有诚实玩家输出(v,2)。因此，0 是 BBA⋆执行结束时所有诚实玩家的最初一点。因此，根据协议 二进制拜占庭协议的属性，在 BA⋆ 执行结束时，对于所有诚实的人，outi = 0 玩家。这意味着 BA⋆ 中每个诚实玩家 i 的输出是 vi = v。 ✷ 协议证明。由于 BBA⋆ 是一个二进制 BA 协议， (A) 对于所有诚实玩家 i，outi = 1，或者 (B) 对于所有诚实的玩家 i，outi = 0。 在情况 A 中，所有诚实玩家都输出 \(\bot\) 为 BA⋆，因此协议成立。现在考虑情况 B。 这种情况下，在执行BBA⋆时，至少一个诚实玩家i的初始位为0。（事实上，如果 所有诚实玩家的初始位为 1，然后，根据 BBA⋆ 的一致性属性，我们将有 对于所有诚实的 j，outj = 1。）因此，在执行 GC 后，i 对某些输出对 (v, 2) 因此，根据分级共识的属性 1，对于所有诚实的玩家 j，gj > 0。因此，通过 分级共识的属性 2，对于所有诚实的玩家 j，vj = v。这意味着，在年底 BA⋆，每个诚实玩家 j 输出 v。因此，协议在情况 B 中也成立。 ✷ 由于一致性和一致性都成立，所以 BA⋆ 是一个任意值的 BA 协议。 历史注释 Turpin 和 Coan 第一个证明，对于 n \(\geq\)3t+1，任何二元 (n, t)-BA 协议可以转换为任意值 (n, t)-BA 协议。减少任意值 通过分级共识的拜占庭协议到二进制拜占庭协议更加模块化， 更干净，并简化了对 Algorand 协议 Algorand ' 的分析。 泛化 BA⋆用于 Algorand Algorand 即使所有通信都是通过 八卦。然而，尽管呈现在传统且熟悉的通信网络中，所以 为了更好地与现有技术进行比较并更容易理解，协议 BA⋆works 也在八卦网络中。事实上，在 Algorand 的详细实施例中，我们将呈现它 直接用于八卦网络。我们还应该指出，它满足球员的可替换性 在设想的非常对抗性的模型中，对于 Algorand 的安全至关重要的财产。
任何在八卦通信网络中工作的 BA 播放器可替换协议都可以是 在本发明的Algorand系统中安全地使用。特别是 Micali 和 Vaikunthanatan 已将 BA⋆ 扩展到与大多数诚实玩家的高效合作。那 协议也可以在 Algorand 中使用。
Algorand 的两个实施例
正如所讨论的，在非常高的水平上，一轮 Algorand 理想地按如下方式进行。首先，随机一个
选定的用户（领导者）提议并流通一个新区块。
（这个过程最初包括
选择一些潜在的领导者，然后确保至少在大部分时间里，
出现单一的共同领导者。）其次，随机选择一个用户委员会，并且
就领导者提出的区块达成拜占庭协议。 （这个过程包括
BA 协议的每一步均由单独选定的委员会运行。）商定的区块
然后由给定阈值 (TH) 的委员会成员进行数字签名。这些数字签名
进行流通，以便每个人都可以确定哪个是新区块。 （这包括流通
签名者的凭证，并仅验证新区块的 hash，确保每个人
一旦明确了 hash ，就保证能够学习该块。）
在接下来的两节中，我们将介绍 Algorand、Algorand ' 的两个实施例
1 和 Algorand ′
2、
在大多数诚实用户的假设下工作。在第 8 节中，我们展示了如何采用这些
在诚实多数资金假设下工作的实施例。
Algorand '
1 仅假设 > 2/3 的委员会成员是诚实的。此外，在
Algorand ′
1、达成拜占庭协议的步骤数被限制在适当高的水平
数，因此保证在一定时间内以压倒性的概率达成协议
固定步骤数（但可能需要比 Algorand ' 的步骤更长的时间
2）。在
在最后一步尚未达成协议的极少数情况下，委员会同意
空块，始终有效。
Algorand ′
2 假设委员会中诚实成员的数量总是大于
或等于固定阈值 tH （这保证了，以压倒性的概率，至少
2/3的委员会成员是诚实的）。另外，Algorand ′
2 允许拜占庭协议
可以通过任意数量的步骤达到（但可能比 Algorand ' 更短的时间
1）。
很容易得出这些基本实施例的许多变体。特别是，这很容易，因为
Algorand ′
2、修改Algorand′
1 以便能够任意达成拜占庭协议
步数。
两个实施例共享以下共同核心、符号、概念和参数。
4.1
共同核心
目标
理想情况下，对于每一轮 r，Algorand 将满足以下属性：
1. 完美的正确性。所有诚实的用户都同意同一个区块。
2. 完整性 1. 在概率 1 的情况下，Br、PAY r 的支付集最大。10
10由于支付集被定义为包含有效支付，并且诚实的用户只进行有效支付，因此最大
PAY r 包含所有诚实用户的“当前未偿”付款。当然，仅仅保证完美的正确性是微不足道的：每个人总是选择官方的
付款集 PAY r 为空。但在这种情况下，系统的完整性为 0。不幸的是，
保证完美的正确性和完整性 1 在存在恶意的情况下并不容易
用户。 Algorand 因此采用了更现实的目标。非正式地，让 h 表示百分比
诚实的用户中，h > 2/3，Algorand 的目标是
以压倒性的概率保证接近 h 的完美正确性和完整性。
优先考虑正确性而不是完整性似乎是一个合理的选择：付款未在
一轮可以在下一轮中处理，但如果可能的话，应该避免分叉。
领导拜占庭协议
完美的正确性可以保证如下。一开始
在第r轮中，每个用户i构建自己的候选块Br
i ，然后所有用户都到达拜占庭
就一个候选区块达成一致。根据我们的介绍，所采用的 BA 协议需要
2/3 诚实多数，并且是玩家可替换的。它的每个步骤都可以由一个小的和
随机选择一组验证者，他们不共享任何内部变量。
不幸的是，这种方法没有完整性保证。之所以如此，是因为候选人
诚实用户的群体很可能彼此完全不同。因此，最终
商定的区块可能总是具有非最大支付集的区块。事实上，它可能永远是
空块，B\(\varepsilon\)，即支付集为空的块。我们将默认为空。
Algorand ' 避免了这种完整性问题，如下所示。首先，选择 r 轮的领导者 \(\ell\)r。
然后，\(\ell\)r 传播他自己的候选块 Br
\(\ell\)r。最后，用户就区块达成一致
他们实际上是从 \(\ell\)r 收到的。因为，只要 \(\ell\)r 是诚实的，就具有完美的正确性和完整性
1 都成立，Algorand ′ 确保 \(\ell\)r 是诚实的，概率接近 h。 （当领导者
恶意的，我们不关心商定的区块是否是一个具有空支付集的区块。毕竟，一个
恶意领导者 \(\ell\)r 可能总是恶意选择 Br
\(\ell\)r 是空块，然后诚实地
传播它，从而迫使诚实的用户就空块达成一致。）
领导者选拔
在 Algorand 中，第 r 个块的形式为 Br = (r, PAY r, Qr, H(Br−1)。
正如引言中已经提到的，数量 Qr−1 被仔细构造为
基本上无法被我们非常强大的对手操纵。 （在本节后面，我们将
提供一些关于为什么会出现这种情况的直觉。）在一轮 r 开始时，所有用户都知道
blockchain 到目前为止，B0，. 。 。 , Br−1，他们从中推导出前一轮的用户集：
是，PK1，. 。 。 , PKr−1。第 r 轮的潜在领导者是用户 i，使得
.H
西吉
r, 1, Qr−1
\(\leq\)p。
让我们解释一下。
请注意，由于数量 Qr−1 是块 Br−1 的一部分，并且底层
签名方案满足唯一性属性 SIGi
r, 1, Qr−1
是唯一的二进制字符串
与 i 和 r 相关。因此，由于 H 是随机的 oracle，H
西吉
r, 1, Qr−1
是一个随机的256位
与 i 和 r 唯一关联的长字符串。符号“.”在H前面
西吉
r, 1, Qr−1
是
小数（在我们的例子中为二进制）点，因此 ri \(\triangleq\).H
西吉
r, 1, Qr−1
是 a 的二元展开式
与 i 和 r 唯一关联的 0 到 1 之间的随机 256 位数字。因此概率
ri 小于或等于 p 本质上是 p。 （我们的潜在领导者选择机制已经
受到 Micali 和 Rivest [28] 的小额支付计划的启发。）
选择概率 p，以便以压倒性的（即 1 −F）概率，至少有一个
潜在的验证者是诚实的。 （事实上，p 被选为此类概率中最小的。）请注意，由于 i 是唯一能够计算自己签名的人，因此他独自一人可以
确定他是否是第一轮的潜在验证者。但是，通过透露他自己的凭据，
\(\sigma\)r
我\(\triangleq\)SIGi
r, 1, Qr−1
，我可以向任何人证明自己是 r 轮的潜在验证者。
领导者 \(\ell\)r 被定义为潜在领导者，其 hashed 凭证小于
hashed 所有其他潜在领导者 j 的凭证：即 H(\(\sigma\)r,s
\(\ell\)r ) \(\leq\)H(\(\sigma\)r,s
j）。
请注意，由于恶意 \(\ell\)r 可能不会透露他的凭证，因此第 r 轮的正确领导者可能会
永远不会被知道，除非有不可能的联系，\(\ell\)r确实是r轮的唯一领导者。
最后让我们提出最后一个但重要的细节：用户 i 可以成为潜在的领导者（因此
仅当他属于该系统至少 k 轮时，才是 r 轮的领导者。这保证了
Qr 和所有未来 Q 量的不可操纵性。事实上，潜在的领导者之一
实际上将确定 Qr。
验证者选择
r 轮的每个步骤 s > 1 都由一小组验证者 SV r,s 执行。
同样，每个验证者 i \(\in\)SV r,s 都是从系统中已有 k 轮的用户中随机选择的
在 r 之前，再次通过特殊量 Qr−1。具体来说，i \(\in\)PKr−k 是 SV r,s 中的验证者，如果
.H
西吉
r, s, Qr−1
\(\leq\)p′。
再一次，只有我知道他是否属于 SV r,s，但是，如果是这样，他可以通过以下方式证明这一点：
展示他的证书 \(\sigma\)r,s
我
\(\triangleq\)H(SIGi
r, s, Qr−1
）。验证者 i \(\in\)SV r,s 发送消息 mr,s
我，在
r 轮的步骤 s，该消息包含他的凭证 \(\sigma\)r,s
i ，以便使验证者能够
下一步要认识到 Mr,s
我
是合法的step-s消息。
选择概率 p' 以确保在 SV r,s 中，令 #good 为
诚实用户和#bad 恶意用户的数量，以下的概率是压倒性的
两个条件成立。
对于实施例Algorand'
1：
(1) #好 > 2 \(\cdot\) #坏并且
(2) #good + 4 \(\cdot\) #bad < 2n，其中 n 是 SV r,s 的预期基数。
对于实施例Algorand'
2：
(1) #good > tH 且
(2) #good + 2#bad < 2tH，其中 tH 是指定阈值。
这些条件意味着，以足够高的概率，(a) 在 BA 的最后一步中
协议中，至少会有给定数量的诚实玩家对新区块 Br 进行数字签名，
(b) 每轮只有一个区块可能具有必要数量的签名，以及 (c) 使用的 BA
协议（在每一步）拥有所需的 2/3 诚实多数。
澄清区块生成
如果 r 轮领导者 \(\ell\)r 是诚实的，则相应的区块
是这样的形式
溴=
r, PAY r, SIG\(\ell\)r Qr−1
, H
Br−1
,
其中支付集 PAY r 是最大的。 （回想一下，根据定义，所有支付集集体有效。）
否则（即，如果 \(\ell\)r 是恶意的），Br 具有以下两种可能形式之一：
溴=
r、支付 r、SIGi
Qr−1
, H
Br−1
和
溴 = 溴
\(\varepsilon\) \(\triangleq\)
r, \(\emptyset\), Qr−1, H
Br−1
。在第一种形式中，PAY r 是一个（不一定是最大的）支付集，它可能是 PAY r = \(\emptyset\)；我是
r 轮的潜在领导者。 （然而，我可能不是领导者\(\ell\)r。如果如果
\(\ell\)r 对他的凭证保密并且不暴露自己。）
第二种形式出现在 BA 协议的 R 轮执行中，所有诚实的参与者
输出默认值，即空块Br
\(\varepsilon\) 在我们的应用中。 （根据定义，可能的
BA 协议的输出包括默认值，一般用 \(\bot\) 表示。参见第 3.2 节。）
请注意，虽然两种情况下的支付集都是空的，但 Br =
r, \(\emptyset\), SIGi
Qr−1
, H
Br−1
和溴
\(\varepsilon\) 是语法上不同的块，出现在两种不同的情况下：分别是“所有
BA 协议的执行过程非常顺利”，并且“在执行过程中出现了问题”
BA协议，默认值为output”。
现在让我们直观地描述一下Algorand′的第r轮区块Br的生成是如何进行的。
第一步，每个符合条件的玩家，即每个玩家 i \(\in\) PKr−k，检查他是否是潜在的
领导者。如果是这种情况，那么我会被问到，使用他迄今为止看到的所有付款，以及
当前 blockchain，B0，. 。 。 ，Br−1，秘密准备最大支付集，PAY r
我，并且偷偷地
组装他的候选块，Br =
r，支付 r
我,SIGi
Qr−1
, H
Br−1
。也就是说，他不仅
包含在 Br 中
i ，作为其第二个组成部分，即刚刚准备好的支付集，而且，作为其第三个组成部分，
他自己的 Qr−1 签名，最后一个区块 Br−1 的第三个组成部分。最后他宣扬自己的
round-r-step-1 消息，先生，1
i ，其中包括 (a) 他的候选块 Br
i , (b) 他的正确签名
他的候选块的（即他对 Br 的 hash 的签名）
i 和 (c) 他自己的凭证 \(\sigma\)r,1
我,证明
他确实是 r 轮的潜在验证者。
（请注意，直到诚实的 i 发出他的消息 mr,1
i ，对手不知道我是
潜在的验证者。如果他想腐蚀诚实的潜在领导人，对手也可以
腐败的随机诚实玩家。然而，一旦他看到 Mr,1
i ，因为它包含 i 的凭证，
对手知道并可能腐蚀 i，但无法阻止 mr,1
i ，通过病毒传播，来自
覆盖系统中的所有用户。）
在第二步中，每个选定的验证者 j \(\in\)SV r,2 尝试识别该轮的领导者。
具体来说，j 采用第 1 步凭证 \(\sigma\)r,1
i1 , . 。 。 , \(\sigma\)r,1
中，包含在正确的步骤 1 消息 mr,1 中
我
他已经收到； hashes 全部，即计算 H
\(\sigma\)r,1
i1
, . 。 。 , H
\(\sigma\)r,1
在
;找到凭证，
\(\sigma\)r,1
\(\ell\)j ，其 hash 按字典顺序最小；并考虑 \(\ell\)r
j 成为 r 轮的领导者。
回想一下，每个考虑的凭证都是 Qr−1 的数字签名，即 SIGi
r, 1, Qr−1
是
由 i 和 Qr−1 唯一确定，H 是随机的 oracle，因此每个 H(SIGi
r, 1, Qr−1
是 r 轮中每个潜在领导者 i 唯一的随机 256 位长字符串。
由此我们可以得出结论，如果 256 位字符串 Qr−1 本身是随机且独立的
选择后，r 轮所有潜在领导者的 hashed 证书将被选中。事实上，所有
潜在的领导者是明确定义的，他们的资历也是如此（无论是实际计算的还是
不是）。此外，第 r 轮的潜在领导者集合是第 r 轮用户的随机子集
r −k，作为一个诚实的潜在领导者，我总是正确地构建和传播他的信息，先生
我，
其中包含我的凭据。因此，由于诚实用户的百分比为 h，无论
恶意的潜在领导者可能会这样做（例如，透露或隐藏自己的凭据），最低限度
hashed 潜在领导者凭证属于诚实的用户，每个人都必然会识别他
成为 r 轮的领导者 \(\ell\)r。因此，如果 256 位字符串 Qr−1 本身是随机的并且
独立选择，概率为 h (a) 领导者 \(\ell\)r 是诚实的，并且 (b) \(\ell\)j = \(\ell\)r 对于所有人
诚实的第 2 步验证者 j．
实际上，hashed 凭证是随机选择的，但取决于 Qr−1，即不是随机和独立选择的。然而，我们将在分析中证明 Qr−1 是
足够不可操纵以保证一轮的领导者在概率上是诚实的
h′ 足够接近 h：即 h′ > h2(1 + h −h2)。例如，如果 h = 80%，则 h′ > .7424。
确定了本轮的领导者（当领导者 \(\ell\)r 诚实时，他们正确地做到了这一点），
步骤 2 验证者的任务是开始执行 BA，使用他们认为的初始值
成为领导者的块。实际上，为了尽量减少所需的沟通量，
验证者 j \(\in\)SV r,2 不使用，作为他的输入值 v′
j 到拜占庭协议，块 Bj
他实际上已经收到了来自\(\ell\)j（用户j认为是领导者）的信息，但是领导者，但是
该块的 hash，即 v′
j = H(Bi)。因此，在 BA 协议终止后，验证者
最后一步的不计算所需的 round-r 块 Br，而是计算（验证和
传播）H(Br)。因此，由于 H(Br) 是由足够多的验证者进行数字签名的
BA协议的最后一步，系统中的用户将意识到H(Br)是新的hash
块。然而，它们还必须检索（或等待，因为执行是完全异步的）
阻止 Br 本身，协议确保其确实可用，无论对手如何
可能会。
异步和定时
Algorand ′
1 和 Algorand ′
2 具有显着程度的异步性。
之所以如此，是因为对手在安排消息传递方面有很大的自由度
传播。另外，一轮中的总步数是否有上限，还有
方差由实际采取的步数贡献。
一旦他获得了 B0 的证书，. 。 。 , Br−1，用户 i 计算 Qr−1 并开始工作
在第r轮上，检查他是否是潜在的领导者，或者是第r轮的某些步骤中的验证者。
假设我必须在步骤 s 采取行动，鉴于所讨论的异步性，我依赖于各种
确保他在采取行动之前拥有足够的信息的策略。
例如，他可能会等待从验证者处接收至少给定数量的消息
上一步，或者等待足够的时间以确保他收到足够的消息
上一步的许多验证者。
种子 Qr 和回溯参数 k
回想一下，理想情况下，Qr 的数量应该
随机且独立，尽管它们足够不可被操纵
对手。
乍一看，我们可以选择 Qr−1 与 H 一致
支付 r−1
，从而避免
在 Br−1 中明确指定 Qr−1。然而，基本分析表明，恶意用户可能
利用这种选择机制。11 一些额外的努力表明，无数其他
11我们正处于第 r -1 轮的开始。因此，Qr−2 = PAY r−2 是公开的，而对手则是私下的
知道他控制的潜在领导者是谁。
假设攻击者控制 10% 的用户，并且
恶意用户 w 很有可能成为第 r -1 轮的潜在领导者。也就是说，假设
H
信号发生器
r−2, 1, Qr−2
规模如此之小，以至于诚实的潜在领导者实际上不太可能成为
r -1 轮的领导者。 （回想一下，由于我们通过秘密的加密抽签机制选择潜在的领导者，
对手不知道谁是诚实的潜在领导者。）因此，对手处于令人羡慕的境地
选择他想要的支付集 PAY ′ 的位置，并使其成为第 r -1 轮的正式支付集。然而，
他可以做得更多。他还可以确保（）他的恶意用户之一将很有可能成为领导者
也是 r 轮的，这样他就可以自由选择 PAY r 是什么。 （等等。至少在很长一段时间内，也就是说，
只要这些高概率事件确实发生。）为了保证（），对手的行为如下。让支付′
是对手在第 r -1 轮中偏好的支付集。然后，他计算 H(PAY ′) 并检查是否对于某些
已经是恶意玩家 z，SIGz(r, 1, H(PAY ′)) 特别小，即足够小，以至于具有很高的
z 概率将成为 r 轮的领先者。如果是这种情况，那么他指示 w 选择他的候选块基于传统区块数量的替代方案很容易被对手利用，以确保
恶意领导人非常频繁。相反，我们具体地、归纳地定义我们的品牌
新数量 Qr 以便能够证明它是不可被对手操纵的。即，
如果 Br 不是空块，则 Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r)，否则 Qr \(\triangleq\)H(Qr−1, r)。
Qr 的这种构造为何有效的直觉如下。暂时假设
Qr−1 是真正随机且独立选择的。那么Qr也会如此吗？当 \(\ell\)r 诚实时
答案是（粗略地说）是的。之所以如此是因为
H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256
是一个随机函数。然而，当 \(\ell\)r 是恶意的时，Qr 不再由 Qr−1 唯一定义
和\(\ell\)r。 Qr 至少有两个单独的值。继续为 Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r)，
另一个是H(Qr−1,r)。首先我们要论证的是，虽然第二个选择有些武断，
第二选择是绝对强制性的。原因是恶意的 \(\ell\)r 总是会导致
第二步的诚实验证者将接收完全不同的候选块。12 一旦
确实如此，通过 BA 协议很容易确保该区块最终达成一致
r 轮将是默认轮次，因此不会包含任何人的 Qr−1 数字签名。但是
该系统必须继续下去，为此，它需要 r 轮的领导者。如果这个领导者自动
并公开选择，那么对手就会轻易地腐蚀他。如果是之前选择的
Qr−1 通过相同的过程，\(\ell\)r 将再次成为 r+1 轮中的领先者。我们特别建议
使用相同的秘密加密抽签机制，但应用于新的 Q 数量：即，
H(Qr−1, r)。通过将此量作为 H 的输出，可以保证输出是随机的，
并通过将 r 作为 H 的第二个输入，而 H 的所有其他用途都有一个或 3 个以上输入，
“保证”这样的 Qr 是独立选择的。同样，我们对替代 Qr 的具体选择
没关系，重要的是\(\ell\)r对于Qr有两种选择，这样他的机会就可以加倍
让另一个恶意用户作为下一个领导者。
对于控制恶意 \(\ell\)r 的对手来说，Qr 的选项甚至可能更多。
例如，令 x、y 和 z 为 r 轮的三个恶意潜在领导者，使得
H
\(\sigma\)r,1
x
<H
\(\sigma\)r,1
y
对于某些步骤 s 所期望的，在 SV r,s 中拥有恶意领导者或恶意多数 他。 — 对于每轮 r 的步骤 1，选择 n1 以便以压倒性的概率获得 SV r,1 ̸= \(\emptyset\)。 • 重要参数的选择示例。 — H 的输出长度为 256 位。 — h = 80%，n1 = 35。 — Λ = 1 分钟且 \(\lambda\) = 10 秒。 • 协议的初始化。 协议从时间 0 开始，r = 0。由于不存在“B−1”或“CERT −1”， 从语法上讲，B−1 是一个公共参数，其第三个组件指定 Q−1，并且所有用户 在时间 0 知道 B−1。
Algorand ′
1 在本节中，我们构建了在以下假设下工作的 Algorand ' 版本。 诚实的大多数用户假设：每个 PKr 中超过 2/3 的用户是诚实的。 在第 8 节中，我们展示了如何用所需的诚实多数来替换上述假设 金钱假设。 5.1 附加符号和参数 符号 • m \(\in\)Z+：二进制BA协议中的最大步数，3的倍数。 • Lr \(\leq\)m/3：随机变量，代表看到 1 所需的伯努利试验次数， 当每次试验为 1 时，概率为 ph 2 并且最多有 m/3 次试验。如果所有试验都失败了 Lr \(\triangleq\)m/3。 Lr 将用于确定生成区块 Br 所需时间的上限。 • tH = 2n 3 + 1：协议结束条件所需的签名数量。 • CERT r：Br 的证书。它是来自适当验证者的 H(Br) 的一组 tH 签名 朗德河 参数 • 各种参数之间的关系。 — 对于第 r 轮的每一步 s > 1，选择 n 使得以压倒性的概率， |HSV r,s| > 2|MSV r,s| 和 |HSV r,s| + 4|MSV r,s| < 2n。 h的值越接近1，n需要越小。特别是，我们使用（变体 of) Chernoffbounds 以确保所需条件以压倒性概率成立。 — m 的选择使得 Lr < m/3 以压倒性的概率出现。 • 重要参数的选择示例。 — F = 10−12。 — n \(\approx\)1500，k = 40，m = 180。5.2 在 Algorand ' 中实现临时密钥 1 正如已经提到的，我们希望验证者 i \(\in\)SV r,s 对他的消息 mr,s 进行数字签名 我 步骤的 r 轮中的 s，相对于临时公钥 pkr,s i ，使用临时秘密密钥 skr,s 我 那个 他在使用后立即销毁。因此，我们需要一种有效的方法来确保每个用户都可以 验证 pkr,s 我 确实是用来验证我的 Mr,s 签名的密钥 我。我们这样做是通过（尽最大努力 据我们所知）基于身份的签名方案的新用途。 在较高层面上，在这样的方案中，中央机构 A 生成一个公共主密钥 PMK， 以及相应的秘密主密钥 SMK。给定玩家 U 的身份 U，A 计算， 通过SMK，得到一个相对于公钥U的秘密签名密钥skU，并私下将skU给 U.（事实上，在基于身份的数字签名方案中，用户U的公钥就是U本身！） 这样，如果 A 在计算出他想要启用的用户的密钥后销毁 SMK 产生数字签名，并且不保留任何计算出的密钥，那么 U 是唯一一个 可以对与公钥 U 相关的消息进行数字签名。因此，任何知道“U 的名字”的人， 自动知道 U 的公钥，因此可以验证 U 的签名（也可能使用 公共主密钥 PMK）。 在我们的应用中，权限 A 是用户 i，所有可能用户 U 的集合与 比如说 S = {i}\(\times\){r′, 中的圆步对 (r, s)。 。 。 , r′ +106}\(\times\){1, . 。 。 , m+3}，其中 r′ 是给定的 一轮，m + 3 是一轮内可能发生的步数的上限。这个 方式，pkr，s 我 \(\triangleq\)(i, r, s)，这样每个人都看到i的签名SIGr,s PKR,S 我（先生，s 我）可以，以压倒性的 概率，立即在 r' 之后的前一百万轮 r 中验证它。 换句话说，i首先生成PMK和SMK。然后，他公开PMK是i的主人 任意一轮 r \(\in\)[r′, r′ + 106] 的公钥，并使用 SMK 私下生成和存储秘密 关键 skr,s 我 对于每个三元组 (i, r, s) \(\in\)S。完成后，他摧毁了 SMK。如果他确定自己不是 SV r,s 的一部分，那么我可能会离开 skr,s 我 单独（因为协议不要求他验证 r) 轮步骤 s 中的任何消息。否则，我首先使用 skr,s 我 对他的消息进行数字签名 Mr,s 我 , 和 然后摧毁skr,s 我。 请注意，当他第一次进入系统时，我可以公开他的第一个公共主密钥。也就是说， 将 i 带入系统的相同支付 \(\wp\)（在 r′ 轮或接近 r′ 轮），也可能 根据 i 的要求，指定 i 的任意轮 r \(\in\)[r′, r′ + 106] 的公共主密钥是 PMK — 例如，通过 包括一对 (PMK, [r', r' + 106]) 形式。 另请注意，由于 m + 3 是一轮中的最大步数，假设一轮 只需一分钟，如此生成的临时密钥的存储将持续近两年。同时 时间，这些短暂的密钥不会花太长时间来生成。使用基于椭圆曲线 在具有 32B 密钥的系统中，每个秘密密钥的计算时间为几微秒。因此，如果 m + 3 = 180， 那么所有 180M 密钥可以在不到一小时的时间内计算出来。 当当前回合接近 r′ + 106 时，为了处理接下来的一百万回合，i 生成一个新的 (PMK′, SMK′) 对，并通过以下方式告知他的下一个临时密钥存储是什么 - 例如 - 让 SIGi(PMK', [r' + 106 + 1, r' + 2 \(\cdot\) 106 + 1]) 输入一个新块，或者作为 单独的“交易”或作为付款一部分的一些附加信息。通过这样做， 我通知每个人，他/她应该在接下来的时间里使用 PMK′ 来验证我的临时签名 万发。等等。 （请注意，遵循此基本方法，无需其他方法即可实现临时密钥 使用基于身份的签名当然是可能的。例如，通过 Merkle trees.16) 16在这个方法中，我生成一个公私密钥对（pkr,s 我,skr,s 我 ) 对于 —say— 中的每个回合步对 (r, s)当然也可以采用其他方式实现临时密钥，例如通过 Merkle trees。 5.3 匹配 Algorand ′ 的步骤 1 与BA⋆的那些 正如我们所说，一轮在 Algorand ' 1 最多有 m + 3 步。 步骤 1. 在这一步中，每个潜在领导者 i 计算并传播他的候选区块 Br 我， 连同他自己的凭证，\(\sigma\)r,1 我。 回想一下，这个凭证明确地标识了 i。之所以如此，是因为 \(\sigma\)r,1 我 \(\triangleq\)SIGi(r, 1, Qr−1)。 潜在验证者 i 还传播其正确的数字签名 H(Br 我）。 不涉及付款或凭证，i 的此签名与他的短暂公共相关 密钥 pkr,1 i ：也就是说，他传播 sigpkr,1 我 (H(Br 我））。 鉴于我们的惯例，而不是传播 Br 我 和 sigpkr,1 我 (H(Br 我）），他本可以 传播的 SIGpkr,1 我 (H(Br 我））。 然而，在我们的分析中，我们需要显式访问 sigpkr,1 我 (H(Br 我））。 步骤 2. 在这一步中，每个验证者 i 设置 \(\ell\)r 我将成为具有 hashed 证书的潜在领导者 是最小的，并且 Br i 是 \(\ell\)r 提出的区块 我。因为，为了效率，我们 希望就 H(Br) 达成一致，而不是直接就 Br 达成一致，我传播他想要的信息 在 BA⋆ 的第一步中以初始值 v′ 传播 我 = H(Br 我）。也就是说，他传播 v′ 我， 当然，是在短暂签署之后。 （即，在相对于正确的临时签名后 公钥，在本例中为 pkr,2 i .) 当然，我也传输了他自己的凭证。 由于 BA⋆ 的第一步包含了分级共识协议 GC 的第一步， Algorand '的2对应于GC的第一步。 步骤3. 在这一步中，每个验证者i \(\in\)SV r,2 执行BA⋆的第二步。也就是说，他发送 他会在 GC 第二步中发送相同的消息。再说一次，我的信息是短暂的 签名并附有我的证书。 （从现在开始，我们将省略验证者 短暂地签署他的消息并传播他的凭证。） 步骤 4. 在这一步中，每个验证器 i \(\in\)SV r,4 计算 GC 的输出 (vi, gi)，并且短暂地 签署并发送与他在 BA⋆第三步中发送的相同的消息，即在 BBA⋆的第一步，如果gi = 2则初始位为0，否则为1。 步骤 s = 5，. 。 。 , m + 2。这样的步骤，如果达到的话，对应于 BA⋆ 的步骤 s -1，因此 BBA⋆的步骤s -3。 由于我们的传播模型足够异步，因此我们必须考虑以下可能性 在这样的步骤 s 的中间，通过证明他的信息到达验证者 i \(\in\)SV r,s 该块 Br 已被选择。在这种情况下，i 停止自己执行第 r 轮 Algorand ′，并开始执行他的回合（r + 1）指令。 {r′，. 。 。 , r′ + 106} \(\times\) {1, . 。 。 ，m+3}。 然后他以规范的方式对这些公钥进行排序，存储第 j 个公钥 键入 Merkle tree 的第 j 个叶子，并计算他公开的根值 Ri。当他想要签名的时候 与密钥 pkr,s 相关的消息 我 , i 不仅提供了实际的签名，还提供了 pkr,s 的验证路径 我 相对于Ri。请注意，此身份验证路径还证明了 pkr,s 我 存储在第 j 个叶子中。其余的 详细信息可以轻松填写。因此，除了相应的指令之外，验证器 i \(\in\)SV r,s 的指令 BBA⋆的步骤s -3，包括检查BBA⋆的执行是否在先前已停止 步骤s′。由于 BBA⋆ 只能在 Coin-Fixed-0 Step 或 Coin-Fixed-1 Step 中停止， 指令区分是否 A（结束条件 0）：s′ -2 ≡0 mod 3，或 B（结束条件1）：s′ -2 ≡1 mod 3。 事实上，在情况 A 中，块 Br 是非空的，因此需要额外的指令来 确保我正确重建 Br 及其正确的证书 CERT r。在情况 B 中， 块 Br 为空，因此指示 i 设置 Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), 并计算 CERT r。 如果在执行步骤 s 的过程中，我没有看到任何证据表明块 Br 已经 生成后，他发送的消息与他在 BBA⋆的步骤 s -3 中发送的消息相同。 步骤 m + 3。如果在步骤 m + 3 期间，i \(\in\)SV r,m+3 看到块 Br 已经在 先前的步骤 s'，然后他按照上面所解释的进行。 否则，我不会发送他在 BBA⋆的步骤 m 中发送的相同消息，而是 根据他掌握的信息，指示计算 Br 及其相应的 证书 CERT r。 事实上，回想一下，我们将一轮的总步数设置为 m + 3。 5.4 实际协议 回想一下，在第 r 轮的每个步骤 s 中，验证者 i \(\in\)SV r,s 使用他的长期公钥对 出示他的凭证 \(\sigma\)r,s 我 \(\triangleq\)SIGi(r, s, Qr−1)，以及 SIGi Qr−1 如果 s = 1。验证者 i 使用他的临时密钥 skr,s 我 签署他的 (r, s) 消息 mr,s 我。为简单起见，当 r 和 s 为 清楚，我们写 esigi(x) 而不是 sigpkr,s i (x) 表示 i 的值的固有临时签名 x 在第 r 轮的步骤 s 中，并写入 ESIGi(x) 而不是 SIGpkr,s i (x) 表示 (i, x, esigi(x))。 第 1 步：区块提案 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 1 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i \(\in\)SV r,1 或 不。 • 如果i /\(\varepsilon\)SV r,1，则i 立即停止自己执行步骤1。 • 如果 i \(\in\)SV r,1，即，如果 i 是潜在领导者，那么他将收取具有以下特征的第 r 轮付款： 到目前为止已传播给他并计算最大支付集 PAY r 我来自他们。接下来，他 计算他的“候选块” Br 我 = (r, 支付 r i , SIGi(Qr−1), H(Br−1))。最后，他计算出 消息先生，1 我 = (Br i , esigi(H(Br i )), \(\sigma\)r,1 i ), 销毁他的临时密钥 skr,1 我，然后 传播 mr,1 我。评论。 在实践中，为了缩短步骤 1 的全局执行时间，重要的是 (r, 1)- 消息是有选择地传播的。 也就是说，对于系统中的每个用户 i，对于第一个 (r, 1)- 他收到并成功验证的消息，17 玩家 i 像往常一样传播它。对于所有的 其他 (r, 1) - 玩家 i 收到并成功验证的消息，只有在 hash 时他才会传播它 它包含的凭证的值是所包含凭证的 hash 值中最小的 到目前为止，他已收到并成功验证的所有 (r, 1) 消息中。此外，按照建议 作者：Georgios Vlachos，每个潜在领导者 i 也传播他的凭证 \(\sigma\)r,1 是有用的 我 分别：这些小消息的传播速度比块更快，确保 mr,1 的及时传播 j 的 其中包含的凭据具有较小的 hash 值，而使那些具有较大的 hash 值 很快消失。 第二步：分级共识协议GC的第一步 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 2 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i 是否 \(\in\)SV r,2 或 不。 • 如果i /\(\varepsilon\)SV r,2 则i 立即停止自己执行步骤2。 • 如果i \(\in\)SV r,2，则在等待一段时间t2 \(\triangleq\) \(\lambda\) + Λ 后，i 的行为如下。 1. 他找到用户\(\ell\)使得H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) 对于所有凭证 \(\sigma\)r,1 j 是的一部分 到目前为止他收到的已成功验证的 (r, 1) 消息。 2. 如果他收到来自 \(\ell\) 的有效消息 mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b 则 i 集 v′ 我 \(\triangleq\)H(Br \(\ell\));否则我设置 v′ 我\(\triangleq\) \(\bot\)。 3.我计算消息mr,2 我 \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),c 销毁了他的临时密钥 斯克罗,2 i ，然后传播 mr,2 我。 a本质上，用户i私下决定r轮的领导者是用户\(\ell\)。 b再次，玩家\(\ell\)的签名和hashes都已成功验证，并且PAY r \(\ell\) 溴 \(\ell\) 是有效的支付集 回合 r — 尽管我不检查是否 PAY r \(\ell\) 是否为 \(\ell\) 的最大值。 c消息 mr,2 我 表示玩家 i 考虑 v′ i 是下一个块的 hash ，或者考虑下一个 块为空。 17也就是说，所有签名都是正确的，并且该块及其 hash 都是有效的 - 尽管我没有检查 所包含的支付集对于其提议者来说是否是最大的。
步骤3：GC第二步 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 3 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i \(\in\)SV r,3 或 不。 • 如果i /\(\varepsilon\)SV r,3，则i 立即停止自己执行步骤3。 • 如果i \(\in\)SV r,3，则在等待一段时间t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ 后，i 的行为如下。 1. 如果存在一个值 v′ ̸= \(\bot\)，使得所有有效消息中 mr,2 j 他已收到， 其中超过 2/3 的形式为 (ESIGj(v′), \(\sigma\)r,2 j ), 没有任何矛盾, a 然后他计算消息 mr,3 我 \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 我）。否则，他计算 mr,3 我 \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 我）。 2. 我销毁了他的临时密钥 skr,3 i ，然后传播 mr,3 我。 a即他没有收到两条分别包含ESIGj(v′)和不同ESIGj(v′′)的有效消息， 来自玩家 j。从现在开始，除了稍后定义的结束条件外，每当诚实的玩家 想要给定形式的消息，相互矛盾的消息永远不会被计算或被认为是有效的。步骤4：GC的输出和BBA的第一步⋆ 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 4 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i \(\in\)SV r,4 或 不。 • 如果i /\(\varepsilon\)SV r,4，则i 立即停止自己执行步骤4。 • 如果i \(\in\)SV r,4，则在等待一段时间t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ 后，i 的行为如下。 1. 他计算 GC 的输出 vi 和 gi，如下所示。 (a) 如果存在一个值 v′ ̸= \(\bot\)，使得在所有有效消息中 mr,3 j 他有 收到的，其中超过 2/3 的形式为 (ESIGj(v′), \(\sigma\)r,3 j ), 然后他设置 vi \(\triangleq\)v′ 和 gi \(\triangleq\)2。 (b) 否则，如果存在一个值 v′ ̸= \(\bot\)，使得在所有有效消息中 先生,3 j 他收到的，超过 1/3 的形式是 (ESIGj(v′), \(\sigma\)r,3 j ), 那么 他设置 vi \(\triangleq\)v′ 和 gi \(\triangleq\)1.a (c) 否则，他设置 vi \(\triangleq\)H(Br \(\varepsilon\) ) 和 gi \(\triangleq\)0。 2. 他计算 BBA⋆的输入 bi，如下： 如果 gi = 2，则 bi \(\triangleq\)0，否则 bi \(\triangleq\)1。 3. 他计算消息 mr,4 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), 毁掉了他短暂的 密钥 skr,4 i ，然后传播 mr,4 我。 a可以证明，情况(b)中的v′如果存在，则必定是唯一的。
步骤 s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3：BBA⋆的硬币固定至 0 步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 知道 Br−1。 • 用户i 根据Br−1 的第三个分量计算Qr−1 并检查i 是否\(\in\)SV r,s。 • 如果i /\(\varepsilon\)SV r,s，则i 立即停止自己执行步骤s。 • 如果i \(\in\)SV r,s 那么他的行为如下。 – 他等待一段时间 ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ 过去。 – 结束条件 0：如果在等待期间的任意时间点，存在 字符串 v ̸= \(\bot\) 和步骤 s′ 使得 (a) 5 \(\leq\) s′ \(\leq\) s, s′ −2 eq 0 mod 3 — 也就是说，步骤 s′ 是一个 Coin-Fixed-To-0 步骤， (b) i 至少收到了 tH = 2n 3 + 1 条有效消息 mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a 和 (c) 我收到一条有效消息 mr,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) 其中 v = H(Br j), 然后，我立即停止自己执行步骤 s（实际上是回合 r），而无需 传播任何东西；设 Br = Br j ;并将自己的 CERT r 设置为消息集 mr,s′−1 j 子步骤(b).b – 结束条件 1：如果在等待期间的任意时间点，存在 步骤 s' 使得 (a’) 6 \(\leq\)s′ \(\leq\)s, s′ -2 eq 1 mod 3 — 即，步骤 s′ 是 Coin-Fixed-To-1 步骤，并且 (b’) i 已收到至少 tH 条有效消息 mr,s’−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c 然后，我立即停止自己执行步骤 s（实际上是回合 r），而无需 传播任何东西；设 Br = Br \(\varepsilon\) ;并将自己的 CERT r 设置为消息集 mr,s′−1 j 子步骤(b’)的。 – 否则，在等待结束时，用户 i 执行以下操作。 他将 vi 设置为所有有效投票的第二部分中 vj 的多数票 先生,s−1 j 他已经收到了。 他计算 bi 如下。 如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)0。 否则，如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)1。 否则，他设置 bi \(\triangleq\)0。 他计算了消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), 毁掉了他短暂的 密钥 skr,s i ，然后传播 mr,s 我。 a 即使玩家 i 也收到了来自 j 的签名为 1 的消息，来自玩家 j 的此类消息也会被计数。 结束条件 1 也有类似的情况。如分析所示，这样做是为了确保所有诚实的用户都知道 Br 彼此相距 \(\lambda\) 时间内。 b 用户 i 现在知道 Br 并且他自己的 r 轮结束。他仍然以普通用户的身份帮助传播消息，但是 不作为 (r, s) 验证者发起任何传播。特别是，他帮助传播了他的所有信息 CERT r，这对于我们的协议来说已经足够了。注意，他还应该为二进制 BA 协议设置 bi \(\triangleq\)0，但是 bi 无论如何，在这种情况下是不需要的。类似的事情适用于所有未来的指示。 c在这种情况下，vj 是什么并不重要。步骤 s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3：BBA⋆的硬币固定到 1 步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i 是否 \(\in\)SV r,s 或 不。 • 如果i /\(\varepsilon\)SV r,s，则i 立即停止自己执行步骤s。 • 如果 i \(\in\)SV r,s 那么他执行以下操作。 – 他等待一段时间 ts \(\triangleq\)(2s −3)\(\lambda\) + Λ 过去。 – 结束条件 0：与 Coin-Fixed-To-0 步骤相同的指令。 – 结束条件 1：与 Coin-Fixed-To-0 步骤相同的说明。 – 否则，在等待结束时，用户 i 执行以下操作。 他将 vi 设置为所有有效投票的第二部分中 vj 的多数票 先生,s−1 j 他已经收到了。 他计算 bi 如下。 如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)0。 否则，如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)1。 否则，他设置 bi \(\triangleq\)1。 他计算了消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), 毁掉了他短暂的 密钥 skr,s i ，然后传播 mr,s 我。
步骤 s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3：BBA⋆的硬币真实翻转步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i 是否 \(\in\)SV r,s 或 不。 • 如果i /\(\varepsilon\)SV r,s，则i 立即停止自己执行步骤s。 • 如果 i \(\in\)SV r,s 那么他执行以下操作。 – 他等待一段时间 ts \(\triangleq\)(2s −3)\(\lambda\) + Λ 过去。 – 结束条件 0：与 Coin-Fixed-To-0 步骤相同的指令。 – 结束条件 1：与 Coin-Fixed-To-0 步骤相同的说明。 – 否则，在等待结束时，用户 i 执行以下操作。 他将 vi 设置为所有有效投票的第二部分中 vj 的多数票 先生,s−1 j 他已经收到了。 他计算 bi 如下。 如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)0。 否则，如果超过所有有效 mr,s−1 的 2/3 j 他收到的是以下形式的 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他设置 bi \(\triangleq\)1。 否则，令 SV r,s−1 我 是（r，s -1）验证者的集合，他从这些验证者那里收到了有效的 消息 mr,s−1 j 。他设置 bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 我 H(\(\sigma\)r,s−1 j ））。 他计算了消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), 毁掉了他短暂的 密钥 skr,s i ，然后传播 mr,s 我。
步骤 m + 3：BBA⋆a的最后一步 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 m + 3 知道 Br−1。 • 用户 i 根据 Br−1 的第三个分量计算 Qr−1 并检查 i \(\in\)SV r,m+3 或 不。 • 如果i /\(\varepsilon\)SV r,m+3，则i 立即停止自己执行步骤m+3。 • 如果 i \(\in\)SV r,m+3 那么他执行以下操作。 – 他等待一段时间 tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ 过去。 – 结束条件 0：与 Coin-Fixed-To-0 步骤相同的指令。 – 结束条件 1：与 Coin-Fixed-To-0 步骤相同的说明。 – 否则，在等待结束时，用户 i 执行以下操作。 他设置了 i \(\triangleq\)1 和 Br \(\triangleq\)Br ǫ。 他计算消息 mr,m+3 我 = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 我 ），毁了他的 临时密钥 skr,m+3 我 ，然后传播 mr,m+3 我 证明 Br.b a极有可能 BBA⋆在此步骤之前已结束，为了完整性，我们指定此步骤。 b 步骤 m + 3 中的证书不必包含 ESIGi(outi)。我们将其包含在内只是为了统一： 现在，无论在哪个步骤生成证书，它们都具有统一的格式。非验证者重建 Round-r 区块 系统中每个用户 i 的说明： 用户 i 一旦知道就开始自己的回合 r Br−1，并等待块信息如下。 – 如果在这样的等待期间和任何时间点，存在一个字符串 v 和一个步骤 s′，这样 那个 (a) 5 \(\leq\) s′ \(\leq\) m + 3 其中 s′ −2 ≡0 mod 3， (b) i 已收到至少 tH 条有效消息 mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ），以及 (c) 我收到一条有效消息 mr,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) 其中 v = H(Br j), 然后，i立即停止自己执行r轮；设 Br = Br j;并设置了自己的 CERT r 是消息集 mr,s′−1 j 子步骤(b)的。 – 如果在等待期间的任意时间点，存在步骤 s'，使得 (a’) 6 \(\leq\)s′ \(\leq\)m + 3 其中 s′ -2 ≡1 mod 3，并且 (b’) i 已收到至少 tH 条有效消息 mr,s’−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), 然后，i立即停止自己执行r轮；设 Br = Br ǫ;并设置了自己的 CERT r 是消息集 mr,s′−1 j 子步骤(b’)的。 – 如果在等待期间的任何时间点，i 至少收到了 tH 条有效消息 先生，米+3 j = (ESIGj(1), ESIGj(H(Br \(\varepsilon\) )), \(\sigma\)r,m+3 j )，然后我停止自己执行 r 轮 立即设置 Br = Br ϫ ，并将自己的 CERT r 设置为消息集 mr,m+3 j 为 1 和 H(Br ）。 5.5 Algorand ' 的分析 1 我们为分析中使用的每轮 r \(\geq\) 0 引入以下符号。 • 令Tr 为第一个诚实用户知道Br−1 的时间。 • 设Ir+1 为区间[T r+1, T r+1 + \(\lambda\)]。 注意协议初始化时T 0 = 0。对于每个 s \(\geq\)1 且 i \(\in\)SV r,s，回想一下 \(\alpha\)r,s 我 和 \(\beta\)r,s 我 分别是玩家i的步骤s的开始时间和结束时间。而且， 回想一下，对于每个 2 \(\leq\) s \(\leq\) m + 3，ts = (2s −3)\(\lambda\) + Λ。此外，令 I0 \(\triangleq\){0} 且 t1 \(\triangleq\)0。 最后，回想一下 Lr \(\leq\)m/3 是代表伯努利试验次数的随机变量 需要看到 1，当每次试验都是 1 的概率 ph 2 并且最多有 m/3 次试验。如果全部 试验失败则 Lr \(\triangleq\)m/3。 在分析中我们忽略计算时间，因为它实际上相对于所需的时间可以忽略不计 来传播消息。无论如何，通过使用稍大的 \(\lambda\) 和 Λ，计算时间可以 直接纳入分析。下面的大多数陈述都“压倒性地” 概率”，我们在分析中可能不会反复强调这一事实。5.6 主要定理 定理 5.1。对于每轮 r \(\geq\)0，以下属性以压倒性的概率成立： 1. 所有诚实的用户都同意同一个区块 Br。 2. 当领导者 \(\ell\)r 诚实时，区块 Br 由 \(\ell\)r 生成，Br 包含最大支付集 \(\ell\)r 在时间 \(\alpha\)r,1 收到 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ 并且所有诚实用户此时都知道 Br 间隔Ir+1。 3. 当领导者 \(\ell\)r 恶意时，T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ 并且所有诚实用户都知道 Br 在时间间隔Ir+1内。 4. Lr 的 ph = h2(1 + h −h2)，并且领导者 \(\ell\)r 是诚实的，概率至少为 ph。 在证明我们的主要定理之前，让我们先说两点。 评论。 • 块生成和真实延迟。生成块Br的时间定义为T r+1 −T r。 也就是说，它被定义为某个诚实用户第一次学习 Br 和 一些诚实的用户第一次学习 Br−1。当 R 轮领导者诚实时，我们的属性 2 主定理保证生成 Br 的准确时间是 8\(\lambda\) + Λ 时间，无论怎样 h > 2/3 的精确值可能是。当领导者恶意时，性质 3 意味着 生成 Br 的预期时间上限为 ( 12 ph + 10)\(\lambda\) + Λ，同样无论精确度如何 h.18 的值 然而，生成 Br 的预期时间取决于 h 的精确值。 事实上，根据性质 4，ph = h2(1 + h −h2) 并且领导者至少有概率是诚实的 ph，因此 E[T r+1 −T r] \(\leq\)h2(1 + h −h2) \(\cdot\) (8\(\lambda\) + Λ) + (1 −h2(1 + h −h2))(( 12 h2(1 + h −h2) + 10)\(\lambda\) + Λ)。 例如，如果 h = 80%，则 E[T r+1 -T r] \(\leq\)12.7\(\lambda\) + Λ。 • \(\lambda\) 与Λ。请注意，验证者在步骤 Algorand ' 中发送的消息的大小是主导的 通过数字签名密钥的长度，即使数字签名密钥的数量可以保持固定， 用户数量巨大。另请注意，在任何步骤 s > 1 中，验证者的预期数量 n 相同 无论用户数是100K、100M、100M都可以使用。之所以如此，是因为 n 仅 取决于 h 和 F。因此，总而言之，除非突然需要增加密钥长度， 无论用户数量有多大，\(\lambda\) 的值都应该保持不变 可预见的未来。 相比之下，对于任何交易率，交易数量随着交易数量的增加而增长。 用户。因此，为了及时处理所有新交易，块的大小应该 也随着用户数量的增长而增长，导致 Λ 也增长。因此，从长远来看，我们应该 \(\lambda\) << Λ。因此， \(\lambda\) 的系数宜取较大，实际上是一个系数 Λ 为 1。 定理 5.1 的证明。我们通过归纳法证明性质 1-3：假设它们在 r −1 轮中成立 （不失一般性，当 r = 0 时，它们自动成立“round -1”），我们证明它们 朗德河 18确实，E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ。由于 Br−1 由归纳假设唯一定义，因此集合 SV r,s 被唯一定义 对于第 r 轮的每个步骤 s。通过n1的选择，SV r,1 ̸=\(\emptyset\)以压倒性的概率。我们现在 陈述以下两个引理，在第 5.7 节和第 5.8 节中证明。在整个归纳过程中 两个引理的证明，第0轮的分析几乎与归纳步骤相同， 当差异发生时我们会强调它们。 引理 5.2。 [完整性引理] 假设属性 1-3 在 r−1 轮中成立，当领导者 \(\ell\)r 是诚实的，具有压倒性的概率， • 所有诚实的用户都同意同一个区块 Br，该区块由 \(\ell\)r 生成并包含最大 \(\ell\)r 在时间 \(\alpha\)r,1 收到的付款集 \(\ell\)r \(\in\)Ir;和 • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ 并且所有诚实用户在时间间隔Ir+1 内都知道Br。 引理 5.3。 [健全性引理] 假设属性 1-3 在 r -1 轮中成立，当领导者 \(\ell\)r 是恶意的，以压倒性的概率，所有诚实用户都同意同一个区块 Br，T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ 并且所有诚实用户在时间间隔 Ir+1 内都知道 Br。 通过将引理 5.2 和 5.3 应用于 r = 0 和归纳步骤，性质 1-3 成立。最后， 我们将性质 4 重述为以下引理，并在第 5.9 节中证明。 引理 5.4。给定 r 之前每一轮的属性 1-3，Lr 的 ph = h2(1 + h −h2)，并且 领导者 \(\ell\)r 是诚实的，概率至少为 ph。 将以上三个引理结合在一起，定理 5.1 成立。 ■ 下面的引理陈述了关于 r 轮的几个重要属性，给定电感 假设，并将用于上述三个引理的证明。 引理 5.5。假设属性 1-3 对于 r -1 轮成立。对于第 r 轮的每个步骤 s \(\geq\)1 且 每个诚实的验证者 i \(\in\) HSV r,s，我们有 (a) \(\alpha\)r,s 我 \(\varepsilon\)Ir； (b) 如果玩家 i 等待了一段时间 ts，则 \(\beta\)r,s 我 \(\varepsilon\)[T r + ts, T r + \(\lambda\) + ts] 对于 r > 0 且 \(\beta\)r,s 我 = ts，r = 0；和 (c) 如果玩家 i 等待了时间 ts，则到时间 \(\beta\)r,s 我，他已收到所有消息 由所有诚实验证者发送 j \(\in\)HSV r,s′ 对于所有步骤 s′ < s。 此外，对于每个步骤 s \(\geq\)3，我们有 (d) 不存在两个不同的参与者 i, i′ \(\in\)SV r,s 以及相同的两个不同的值 v, v′ 长度，使得两个玩家都等待了一定时间 ts，超过所有玩家的 2/3 有效消息 mr,s−1 j i 收到的玩家已经为 v 签名，且超过所有有效玩家的 2/3 消息 mr,s−1 j 球员 i′ 收到 v′ 的签名。 证明。性质 (a) 直接从归纳假设得出，因为玩家 i 知道 Br−1 时间间隔 Ir 并立即开始自己的步骤 s。性质 (b) 直接从 (a) 得出：因为 玩家 i 在行动之前等待了一段时间 ts，\(\beta\)r,s 我 = \(\alpha\)r,s 我 + ts。注意 \(\alpha\)r,s 我 = 0 为 r = 0。 我们现在证明性质(c)。如果 s = 2，则根据性质 (b)，对于所有验证者 j \(\in\) HSV r,1 我们有 \(\beta\)r,s 我 = \(\alpha\)r,s 我 + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j + Λ。由于每个验证者 j \(\in\)HSV r,1 在时间 \(\beta\)r,1 发送他的消息 j 并且消息到达所有诚实的人 最多 Λ 时间内的用户，时间为 \(\beta\)r,s 我 玩家 i 已收到所有验证者发送的消息 HSV r,1 根据需要。 如果 s > 2，则 ts = ts−1 + 2\(\lambda\)。根据性质 (b)，对于所有步骤 s′ < s 且所有验证者 j \(\in\) HSV r,s′， \(\beta\)r,s 我 = \(\alpha\)r,s 我 + ts \(\geq\)T r + ts = T r + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = T r + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ j + \(\lambda\)。 由于每个验证者 j \(\in\)HSV r,s′ 在时间 \(\beta\)r,s′ 发送他的消息 j 并且消息到达所有诚实的人 最多 \(\lambda\) 时间内的用户，到时间 \(\beta\)r,s 我 玩家 i 已收到所有诚实验证者发送的所有消息 在 HSV r,s' 中，对于所有 s' < s。因此性质(c)成立。 最后，我们证明性质（d）。请注意，验证者 j \(\in\)SV r,s−1 最多签署两个东西 步骤 s -1 使用它们的临时密钥：与输出相同长度的值 vj hash 函数，如果 s −1 \(\geq\)4，则还有一点 bj \(\in\){0, 1}。这就是为什么在引理的陈述中 我们要求 v 和 v′ 具有相同的长度：许多验证者可能都签署了 hash 值 v 和位 b，因此都通过了 2/3 阈值。 为了矛盾起见，假设存在所需的验证者 i、i′ 和值 v、v′。 请注意，MSV r,s−1 中的一些恶意验证者可能同时签署了 v 和 v′，但每个诚实的验证者 HSV r,s−1 中的验证者最多签署了其中一个。根据性质 (c)，i 和 i′ 均已收到 HSV r,s−1 中所有诚实验证者发送的所有消息。 令 HSV r,s−1(v) 为已签署 v、MSV r,s−1 的诚实 (r, s −1) 验证者集合 我 集合 i 收到有效消息的恶意 (r, s −1) 验证者的数量，以及 MSV r,s−1 我 (五) MSV r,s−1 的子集 我 我从谁那里收到了有效的消息签名 v. 根据以下要求 i 和 v，我们有 比率 \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 我 （五）| |HSV r,s−1| + |MSV r,s−1 我 |
2 3. (1) 我们首先展示 |MSV r,s−1 我 （五）| \(\leq\)|HSV r,s−1(v)|。 (2) 否则，根据参数之间的关系，以压倒性的概率 |HSV r,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 我 |，因此 比率 < |HSV r,s−1(v)| + |MSV r,s−1 我 （五）| 3|MSV r,s−1 我 | < 2|MSV r,s−1 我 （五）| 3|MSV r,s−1 我 | \(\leq\)2 3、 矛盾不等式 1. 接下来，根据不等式 1 我们有 2|HSV r,s−1| + 2|MSV r,s−1 我 | < 3|HSV r,s−1(v)| + 3|MSV r,s−1 我 （五）| \(\leq\) 3|HSV r,s−1(v)| + 2|MSV r,s−1 我 | + |MSV r,s−1 我 （五）|。 结合不等式2， 2|HSV r,s−1| < 3|HSV r,s−1(v)| + |MSV r,s−1 我 （五）| \(\leq\)4|HSV r,s−1(v)|, 这意味着 |HSV r,s−1(v)| > 1 2|HSV r,s−1|。类似地，根据 i′ 和 v′ 的要求，我们有 |HSV r,s−1(v′)| > 1 2|HSV r,s−1|。 由于诚实的验证者 j \(\in\)HSV r,s−1 破坏了他的临时密钥 skr,s−1 j 传播前 在他的消息中，攻击者无法伪造 j 的签名以获得 j 未签名的值，之后 得知 j 是验证者。因此，上面的两个不等式意味着 |HSV r,s−1| \(\geq\)|HSV r,s−1(v)| + |HSV r,s−1(v′)| > |HSV r,s−1|，矛盾。因此，所需的 i、i'、v、v' 不存在，并且 性质 (d) 成立。 ■ 5.7 完整性引理 引理 5.2。 [完整性引理，重述] 假设属性 1-3 对于 r−1 轮成立，当 领导者 \(\ell\)r 是诚实的，有压倒性的概率， • 所有诚实的用户都同意同一个区块 Br，该区块由 \(\ell\)r 生成并包含最大 \(\ell\)r 在时间 \(\alpha\)r,1 收到的付款集 \(\ell\)r \(\in\)Ir;和 • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ 并且所有诚实用户在时间间隔Ir+1 内都知道Br。 证明。根据归纳假设和引理 5.5，对于每个步骤 s 和验证器 i \(\in\) HSV r,s， \(\alpha\)r,s 我 \(\varepsilon\)Ir。下面我们一步步分析该协议。 步骤1。 根据定义，每个诚实验证者 i \(\in\) HSV r,1 传播所需的消息 mr,1 我 在 时间\(\beta\)r,1 我 =\(\alpha\)r,1 我 ，其中 mr,1 我 = (Br i , esigi(H(Br i )), \(\sigma\)r,1 i ), Br 我 = (r, 支付 r i , SIGi(Qr−1), H(Br−1)), 并支付 i 是我在时间 \(\alpha\)r,1 之前看到的所有付款中的最大付款集 我。 步骤2。 任意固定一个诚实验证者 i \(\in\) HSV r,2。根据引理 5.5，当玩家 i 完成时 在时间 \(\beta\)r,2 等待 我 =\(\alpha\)r,2 我 + t2，他已经收到HSV r,1中验证者发送的所有消息，包括 先生,1 \(\ell\)r 。根据 \(\ell\)r 的定义，PKr−k 中不存在其凭证为 hash 的其他玩家 值小于 H(\(\sigma\)r,1 \(\ell\)r）。当然，对手在看到 H(\(\sigma\)r,1 \(\ell\)r) 非常小，但那时玩家 \(\ell\)r 已经销毁了他的临时密钥和消息 mr,1 \(\ell\)r 已被传播。因此验证者 i 将自己的领导者设置为玩家 \(\ell\)r。因此，在时间 \(\beta\)r,2 我， 验证者 i 传播 mr,2 我 = (ESIGi(v′ i), \(\sigma\)r,2 i ), 其中 v′ 我 = H(Br \(\ell\)r）。当 r = 0 时，唯一的区别 是 \(\beta\)r,2 我 = t2 而不是在一个范围内。对于未来的步骤也可以说类似的话，我们 不会再强调它们。 步骤 3. 任意固定一个诚实验证者 i \(\in\) HSV r,3。根据引理 5.5，当玩家 i 完成时 在时间 \(\beta\)r,3 等待 我 =\(\alpha\)r,3 我 + t3，他已收到 HSV r,2 中验证者发送的所有消息。 通过参数之间的关系，以压倒性的概率 |HSV r,2| > 2|MSV r,2|。此外，没有诚实的验证者会签署相互矛盾的消息，而对手 在诚实验证者销毁其对应的签名后，无法伪造该签名 临时密钥。因此，我收到的所有有效 (r, 2) 消息中超过 2/3 来自 诚实的验证者，形式为 mr,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), 不矛盾。 因此，在时间 \(\beta\)r,3 我 玩家 i 传播 mr,3 我 = (ESIGi(v′), \(\sigma\)r,3 i ), 其中 v′ = H(Br \(\ell\)r）。步骤 4。 任意固定一个诚实验证者 i \(\in\) HSV r,4。根据引理 5.5，玩家 i 已收到所有 当 HSV r,3 中的验证者在时间 \(\beta\)r,4 完成等待时发送的消息 我 =\(\alpha\)r,4 我 + t4。类似于 步骤 3，i 收到的所有有效 (r, 3) 消息中超过 2/3 来自诚实的验证者，并且 mr,3 形式的 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j）。 因此，玩家 i 设置 vi = H(Br \(\ell\)r), gi = 2 且 bi = 0。在时间 \(\beta\)r,4 我 =\(\alpha\)r,4 我 +t4 他传播 先生,4 我 = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 我）。 步骤 5。 任意固定一个诚实验证者 i \(\in\) HSV r,5。 根据引理 5.5，我将拥有的玩家 如果他一直等到时间 \(\alpha\)r,5，则接收到 HSV r,4 中验证者发送的所有消息 我 + t5。请注意 |HSV r,4| \(\geq\)tH.19 另请注意，HSV r,4 中的所有验证者均已签署 H(Br \(\ell\)r）。 作为 |MSV r,4| < tH，不存在任何 v′ ̸= H(Br \(\ell\)r) 可能由 tH 签署 SV r,4 中的验证者（必然是恶意的），因此玩家 i 在他完成之前不会停止 收到了 tH 个有效消息 mr,4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j）。设 T 为时间 后一个事件发生。其中一些消息可能来自恶意玩家，但因为 |MSV r,4| < tH，其中至少有一个来自 HSV r,4 中的诚实验证者，并且在时间之后发送 Tr+t4。因此，T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ，到时间 T 时，玩家 i 也收到了 消息先生，1 \(\ell\)r 。通过构建协议，玩家 i 在时间 \(\beta\)r,5 处停止 我 = T 无 传播任何东西；设 Br = Br \(\ell\)r；并将他自己的 CERT r 设置为 (r, 4) 消息的集合 0 和 H(Br \(\ell\)r) 他已经收到了。 步骤 s > 5。 类似地，对于任何步骤 s > 5 和任何验证者 i \(\in\) HSV r,s，玩家 i 将有 如果他一直等到时间 \(\alpha\)r,s，则接收到 HSV r,4 中验证者发送的所有消息 我 + ts。由 同样的分析，玩家 i 停止而不传播任何内容，设置 Br = Br \(\ell\)r（并设置自己的 CERT 正确）。当然，恶意验证者可能不会停止，并且可能会任意传播 消息，但因为 |MSV r,s| < tH，通过归纳，tH 验证者无法签署其他 v′ 在任何步骤 4 \(\leq\) s′ < s 中，因此诚实的验证者只会停止，因为他们已经收到了有效的 tH (r, 4)-0 和 H(Br \(\ell\)r）。 Round-r 街区的重建。 第 5 步的分析适用于一般诚实 用户 i 几乎没有任何变化。事实上，玩家 i 在间隔 Ir 中开始自己的回合 r，并且 仅当他收到 H(Br) 的 tH 个有效 (r, 4) 消息时，才会在时间 T 停止 \(\ell\)r）。再次因为 这些消息中至少有一条来自诚实的验证者，并且在时间 T r + t4 之后发送，玩家 i 有 还收到了 Mr,1 \(\ell\)r 到时间 T。因此他设置 Br = Br \(\ell\)r 与适当的 CERT r。 剩下的只是证明所有诚实用户在时间间隔 Ir+1 内完成他们的 r 轮。 通过第 5 步的分析，每个诚实验证者 i \(\in\)HSV r,5 都知道 \(\alpha\)r,5 上或之前的 Br 我 + t5 \(\leq\) Tr + \(\lambda\) + t5 = Tr + 8\(\lambda\) + Λ。由于 T r+1 是第一个诚实用户 ir 知道 Br 的时间，所以我们有 T r+1 \(\leq\)T r + 8\(\lambda\) + Λ 根据需要。而且，当玩家ir认识Br时，他已经帮助传播了信息 他的 CERT r。请注意，所有这些消息都将在时间 \(\lambda\) 内被所有诚实的用户收到，即使 19严格来说，这种情况发生的可能性非常高，但不一定是压倒性的。 然而，这 概率稍微影响协议的运行时间，但不影响其正确性。当h=80%时，则 |HSV r,4| \(\geq\)tH 的概率为 1 −10−8。如果此事件没有发生，则协议将继续进行另一个事件 3 个步骤。由于这种情况在两个步骤中不发生的概率可以忽略不计，因此协议将在步骤 8 结束。 期望的话，需要的步数差不多是5。玩家 ir 是第一个传播它们的玩家。此外，根据上面的分析我们有 T r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ，因此所有诚实用户都收到了 mr,1 \(\ell\)r 乘以时间 T r+1 + \(\lambda\)。据此， 所有诚实的用户都知道时间间隔 Ir+1 = [T r+1, T r+1 + \(\lambda\)] 内的 Br。 最后，对于 r = 0，我们实际上有 T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ。将一切结合在一起， 引理 5.2 成立。 ■ 5.8 健全性引理 引理 5.3。 [可靠性引理，重述] 假设属性 1-3 对于 r -1 轮成立，当 领导者\(\ell\)r是恶意的，以压倒性的概率，所有诚实的用户都同意同一个区块 Br，T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ 并且所有诚实用户在时间间隔 Ir+1 内都知道 Br。 证明。我们分别考虑协议的两个部分，GC 和 BBA⋆。 GC。 根据归纳假设和引理 5.5，对于任何步骤 s \(\in\){2, 3, 4} 和任何诚实的 验证者 i \(\in\) HSV r,s，当玩家 i 在时间 \(\beta\)r,s 行动时 我 = \(\alpha\)r,s 我 + ts，他已收到所有发送的消息 由所有诚实的验证者在步骤 s' < s 中进行验证。我们在步骤 4 中区分了两种可能的情况。 情况 1. 没有验证者 i \(\in\) HSV r,4 设置 gi = 2。 在这种情况下，根据定义，对于所有验证者 i \(\in\) HSV r,4，bi = 1。也就是说，他们从一个 就二进制 BA 协议中的 1 达成一致。他们可能没有就他们的 vi 达成一致， 但这并不重要，正如我们将在二进制 BA 中看到的那样。 情况 2. 存在一个验证器 ˆi \(\in\)HSV r,4 使得 gˆi = 2。 在这种情况下，我们表明 (1) 对于所有 i \(\in\)HSV r,4，gi \(\geq\)1， (2) 存在一个值 v′，使得 vi = v′ 对于所有 i \(\in\)HSV r,4，并且 (3) 存在有效消息 mr,1 \(\ell\) 来自一些验证者 \(\ell\) \(\in\)SV r,1 使得 v′ = H(Br \(\ell\)）。 事实上，由于玩家 ˆi 是诚实的并且设置 gˆi = 2，所以超过所有有效消息的 2/3 mr,3 j 他收到了相同的值 v′ ̸= \(\bot\)，并且他设置了 vˆi = v′。 根据引理 5.5 中的性质 (d)，对于任何其他诚实的 (r, 4) 验证者 i，它不可能比 超过所有有效消息的 2/3 mr,3 j i′ 收到的值具有相同的值 v′′ ̸= v′。 因此，如果 i 设置 gi = 2，则 i 也必须看到 v′ 的多数票数 > 2/3，并且设置 vi = v′，根据需要。 现在考虑任意验证者 i \(\in\) HSV r,4 且 gi < 2。与 Property 的分析类似 (d) 在引理 5.5 中，因为玩家 ˆi 已经看到 v′ 超过 2/3 多数，超过 1 2|HSV r,3|诚实的 (r, 3)-验证者已签署 v′。因为我已经收到了诚实的 (r, 3) 验证者的所有消息 时间\(\beta\)r,4 我 =\(\alpha\)r,4 我 + t4，他特别收到了超过 1 2|HSV r,3|来自他们的消息 对于 v′。因为 |HSV r,3| > 2|MSV r,3|, i 看到 v′ 占 > 1/3 多数。据此，玩家 i 设 gi = 1，且性质 (1) 成立。 玩家 i 是否一定设置 vi = v′？假设存在一个不同的值 v′′ ̸= \(\bot\)，使得 玩家 i 也看到 v′′ 的投票率超过 1/3。其中一些消息可能来自恶意 验证者，但至少其中一个来自某个诚实的验证者 j \(\in\)HSV r,3：确实，因为 |HSV r,3| > 2|MSV r,3|我已收到来自 HSV r,3（一组恶意软件）的所有消息 我收到有效 (r, 3) 消息的验证者占所有有效消息的 < 1/3 他收到的消息。根据定义，玩家 j 必须在所有有效 (r, 2) 消息中看到超过 2/3 的 v′′ 消息 他已经收到了。然而，我们已经发现其他一些诚实的 (r, 3) 验证者已经看到 v′ 的 2/3 多数（因为他们签署了 v′）。根据引理 5.5 的性质 (d)，这不能 发生并且这样的值 v'' 不存在。因此玩家 i 必须根据需要设置 vi = v′， 且性质(2)成立。 最后，考虑到一些诚实的 (r, 3) 验证者已经看到超过 2/3 的大多数 v'，一些（实际上， 超过一半的）诚实的（r，2）验证者已经签署了 v' 并传播了他们的消息。 通过构建协议，那些诚实的 (r, 2) 验证者必须收到有效的 留言先生，1 \(\ell\) 来自某个玩家 \(\ell\) \(\varepsilon\)SV r,1 且 v′ = H(Br \(\ell\))，因此性质(3)成立。 BBA⋆。 我们再次区分两种情况。 情况 1. 所有验证者 i \(\in\) HSV r,4 都有 bi = 1。 这发生在 GC 的情况 1 之后。作为 |MSV r,4| < tH，在这种情况下 SV r,5 中没有验证器 可以收集或生成位 0 的有效 (r, 4) 消息。因此，HSV r,5 中没有诚实的验证者 会停下来，因为他知道一个非空块 Br。 此外，虽然位 1 至少有 tH 个有效 (r, 4) 消息，但 s′ = 5 不满足 s′ −2 ≡1 mod 3，因此 HSV r,5 中没有诚实的验证者会停止，因为他知道 Br = Br ǫ。 相反，每个验证者 i \(\in\) HSV r,5 在时间 \(\beta\)r,5 起作用 我 =\(\alpha\)r,5 我 + t5，当他收到所有 由 HSV r,4 发送的消息遵循引理 5.5。因此，玩家 i 看到 1 的票数超过 2/3 并设置 bi = 1。 在步骤 6 中，这是一个 Coin-Fixed-To-1 步骤，虽然 s′ = 5 满足 s′ −2 ≡0 mod 3，但有 不存在位 0 的有效 (r, 4) 消息，因此 HSV r,6 中的验证器不会停止，因为 他知道一个非空块 Br。然而，当 s′ = 6 时，s′ −2 ≡1 mod 3 且确实存在 |HSV r,5| \(\geq\)tH 来自 HSV r,5 的位 1 的有效 (r, 5) 消息。 对于每个验证者 i \(\in\) HSV r,6，遵循引理 5.5，在时间 \(\alpha\)r,6 或之前 我 + t6 玩家我 已收到来自 HSV r,5 的所有消息，因此我停止传播任何内容并设置 溴 = 溴 ǫ。他的 CERT r 是第 tH 个有效 (r, 5) 消息 mr,5 的集合 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) 当他停下来时，他收到了。 接下来，让玩家 i 成为步骤 s > 6 中的诚实验证者或一般诚实用户（即， 非验证者）。类似于引理5.2的证明，玩家i设置Br = Br ǫ 并设定了自己的 CERT r 是 tH 个有效 (r, 5) 消息 mr,5 的集合 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) 他有 收到。 最后，与引理 5.2 类似， Tr+1\(\leq\) 分钟 i\(\in\)HSV r,6 \(\alpha\)r,6 我 + t6 \(\leq\) T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ， 并且所有诚实用户在时间间隔 Ir+1 内都知道 Br，因为第一个诚实用户 i 知道 Br 帮助在他的 CERT r 中传播 (r, 5) 消息。 情况 2. 存在一个验证者 ˆi \(\in\)HSV r,4 且 bˆi = 0。 这种情况发生在 GC 的情况 2 之后，并且是更复杂的情况。通过GC分析， 在这种情况下，存在有效消息 mr,1 \(\ell\) 使得 vi = H(Br \(\ell\)) 对于所有 i \(\in\) HSV r,4。注意事项 HSV r,4 中的验证者可能无法就他们的 bi 达成一致。 对于任何步骤 s \(\in\){5, . 。 。 , m + 3} 且验证者 i \(\in\)HSV r,s，根据引理 5.5 玩家 i 将有 收到 HSV r,4 中所有诚实验证者发送的所有消息 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 如果他已经等待 时间 ts。我们现在考虑以下事件 E：存在一个步骤 s\(\geq\)5，使得对于第一个 在二进制 BA 中的时间，某个玩家 i\(\in\)SV r,s（无论是恶意的还是诚实的）应该停止 不传播任何东西。我们使用“应该停止”来强调这样一个事实：如果玩家 i 是恶意的，那么他可能会假装按照协议他不应该停止，并且 传播对手选择的消息。 此外，通过协议的构建， (E.a) i能够收集或生成至少 tH 个有效消息 mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) 对于相同的 v 和 s′，其中 5 \(\leq\) s′ \(\leq\) s 且 s′ −2 ≡0 mod 3；或 (E.b) i 能够收集或生成至少 tH 个有效消息 mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) 对于相同的 s′，其中 6 \(\leq\) s′ \(\leq\) s 且 s′ −2 ≡1 mod 3。 因为诚实的 (r, s' -1) 消息在被发送之前被所有诚实的 (r, s') 验证者接收到。 在步骤 s' 中完成等待，并且因为对手在不迟于 诚实的用户，不失一般性，我们有 s′ = s 并且玩家 i 是恶意的。请注意 我们不要求 E.a 中的值 v 是有效块的 hash ：这一点将会变得清楚 分析中，v = H(Br \(\ell\)）在此子事件中。 下面我们首先分析事件E之后的情况2，然后表明s的值本质上是 根据 Lr 进行分配（因此事件 E 发生在步骤 m + 3 之前，具有压倒性的优势） 给定参数关系的概率）。首先，对于任何步骤 5 \(\leq\)s < s， 每个诚实的验证者 i \(\in\) HSV r,s 都等待时间 ts 并设置 vi 为大多数投票者 他收到的有效 (r, s−1) 消息。由于玩家 i 已收到所有诚实的 (r, s−1) 消息 遵循引理 5.5，因为 HSV r,4 中的所有诚实验证者都签署了 H(Br \(\ell\)) 以下案例 GC 的 2，并且由于 |HSV r,s−1| > 2|MSV r,s−1|对于每个 s，通过归纳我们有该玩家 i 已设定 vi = H(Br \(\ell\)）。 这同样适用于每个诚实的验证者 i \(\in\) HSV r,s，他们不会在不传播的情况下停止 任何东西。现在我们考虑步骤 s 并区分四个子情况。 案例 2.1.a.事件 E.a 发生并且存在一个诚实的验证者 i′ \(\in\)HSV r,s 谁应该 也停止不传播任何东西。 在这种情况下，我们有 s−2 ≡0 mod 3 并且步骤 s 是一个 Coin-Fixed-To-0 步骤。 由 定义，玩家 i′ 已收到至少 tH 条有效的 (r, s−1) 消息，其形式为 (ESIGj(0), ESIGj(v), \(\sigma\)r,s−1 j ）。由于 HSV r,s−1 中的所有验证者都签署了 H(Br \(\ell\)) 和 |MSV r,s−1| < tH，我们有 v = H(Br \(\ell\)）。 因为至少 tH −|MSV r,s−1| i′ 收到的 0 和 v 的 (r, s−1) 消息中的 \(\geq\)1 条 由 HSV r,s−1 中的验证者在时间 T r +ts−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 后发送 \(\ell\) +Λ, 玩家 i′ 已收到 mr,1 \(\ell\) 当他收到那些 (r, s−1) 消息时。因此玩家 i′ 停止而不传播任何东西；设 Br = Br \(\ell\);并将他自己的 CERT r 设置为 他收到的 0 和 v 的有效 (r, s−1) 消息集。 接下来，我们证明，任何其他验证器 i \(\in\) HSV r,s 要么以 Br = Br 停止 \(\ell\)，或 已设置 bi = 0 并传播 (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s 我）。确实，因为步骤 s 这是第一次一些验证者应该停止而不传播任何东西，不存在 存在一个步骤 s′ < s 且 s′ −2 ≡1 mod 3 使得 tH (r, s′ −1) 验证者签名为 1。 因此，HSV r,s 中没有验证器以 Br = Br 停止 ǫ。此外，正如步骤 {4, 5, ... 中的所有诚实验证者一样。 。 。 , s−1} 有符号 H(Br \(\ell\)), 确实有 不存在步骤 s′ \(\leq\) s * 且 s′ −2 ≡0 mod 3 使得 tH (r, s′ −1) 验证者已签名 一些 v′′ ̸= H(Br \(\ell\)) —确实，|MSV r,s′−1| < tH。因此，HSV r,s 中没有验证者停止 与 Br ̸= Br ϫ 和 Br ̸= Br \(\ell\)。也就是说，如果一个玩家 i \(\in\) HSV r,s 已经停止而没有 传播任何东西，他一定设置了 Br = Br \(\ell\)。 如果玩家 i \(\in\) HSV r,s 已等待时间 ts 并在时间传播消息 \(\beta\)r,s 我 = \(\alpha\)r,s 我 + ts，他已经收到了来自 HSV r,s−1 的所有消息，至少包括 tH -|MSV r,s−1|其中 0 和 v。 如果我看到 1 的票数超过 2/3，那么他 已经看到超过 2(tH −|MSV r,s−1|) 条有效 (r, s−1)-消息 1，还有更多 比 2tH -3|MSV r,s−1|其中来自诚实的 (r, s−1) 验证者。然而，这意味着 |HSV r,s−1| \(\geq\)tH−|MSV r,s−1|+2tH−3|MSV r,s−1| > 2n−4|MSV r,s−1|，矛盾 事实是 |HSV r,s−1| + 4|MSV r,s−1| < 2n, 它来自参数的关系。因此，我没有看到> 2/3 大多数人支持 1，并且他设置 bi = 0，因为步骤 s 是一个 Coin-Fixed-To-0 步骤。正如我们所拥有的 可见，vi = H(Br \(\ell\)）。因此 i 传播 (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i ) 如我们所愿 显示。 对于步骤 s+ 1，由于玩家 i′ 已帮助在其 CERT r 中传播消息 在时间 \(\alpha\)r,s 或之前 我′ + ts，HSV r,s+1 中的所有诚实验证者至少收到 tH 位 0 和值 H(Br \(\ell\)) 完成后或之前 等待。此外，HSV r,s+1 中的验证器在收到这些 (r,s−1)- 之前不会停止 消息，因为对于位 1 不存在任何其他有效的 (r, s′ -1) 消息 s′ −2 ≡1 mod 3 且 6 \(\leq\)s′ \(\leq\)s+ 1，根据步骤 s 的定义。特别是，步骤 s+ 1 本身是一个 Coin-Fixed-To-1 步骤，但 HSV r,s 中没有诚实的验证者传播 1 的消息，以及 |MSV r,s| < tH。 因此，HSV r,s+1 中的所有诚实验证者都会停止而不传播任何内容，并设置 Br = 溴 \(\ell\)：和以前一样，他们收到了 mr,1 \(\ell\) 在他们收到所需的 (r, s−1)-消息之前。20 对于未来步骤中的所有诚实验证者和一般的所有诚实用户来说，也可以这样说。 特别是，他们都知道 Br = Br \(\ell\)在时间间隔 Ir+1 内并且 T r+1 \(\leq\) \(\alpha\)r,s 我′ + ts\(\leq\)T r + \(\lambda\) + ts。 案例2.1.b。事件 E.b 发生并且存在一个诚实的验证者 i′ \(\in\)HSV r,s 谁应该 也停止不传播任何东西。 在这种情况下，我们有 s−2 ≡1 mod 3 并且步骤 s 是一个 Coin-Fixed-To-1 步骤。分析 与案例2.1.a类似，省略了很多细节。 20如果\(\ell\)是恶意的，他可能会派出mr,1 \(\ell\) 迟到了，希望一些诚实的用户/验证者还没有收到 mr,1 \(\ell\) 还 当他们收到所需的证书时。然而，由于验证者 ˆi \(\in\)HSV r,4 已设置 bˆi = 0 且 vˆi = H(Br \(\ell\)), 如 在我们有超过一半的诚实验证者 i \(\in\)HSV r,3 已经设置 vi = H(Br \(\ell\)）。这进一步意味着更多 超过一半的诚实验证者 i \(\in\)HSV r,2 设置 vi = H(Br \(\ell\))，那些 (r, 2)-验证者都收到了 mr,1 \(\ell\)。作为 对手无法区分验证者和非验证者，他无法瞄准 mr,1 的传播 \(\ell\) 至 (r, 2)-验证者 而不让非验证者看到它。事实上，很有可能超过一半（或一个很好的常数分数） 所有诚实用户都见过 mr,1 \(\ell\) 等待t2后从自己的回合r开始。从现在开始， mr,1 所需时间 \(\lambda\)′ \(\ell\) 到达剩余的诚实用户比 Λ 小得多，为了简单起见，我们不 在分析中写出来。如果 4\(\lambda\) \(\geq\) \(\lambda\)′ 则分析继续进行，没有任何变化：在步骤 4 结束时，所有 诚实的用户会收到 mr,1 \(\ell\)。如果块的大小变得巨大且 4\(\lambda\) < \(\lambda\)′，则在步骤 3 和 4 中， 协议可以要求每个验证者等待 \(\lambda\)′/2 而不是 2\(\lambda\)，并且分析继续成立。和之前一样，玩家 i′ 必须至少收到 tH 条有效的 (r, s−1) 消息，其形式为 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ）。再次根据 s 的定义，不存在步骤 5 \(\leq\)s′ < s，其中 s′ −2 ≡0 mod 3，其中至少 tH (r, s′ −1) 验证者已签署 0 且 相同的 v。因此玩家 i′ 停止而不传播任何东西；设 Br = Br ǫ;和集 他自己的 CERT r 是他收到的第 1 位的有效 (r, s−1) 消息集。 此外，任何其他验证器 i \(\in\) HSV r,s 要么以 Br = Br 停止 \(\varepsilon\) ，或已设定 bi = 1 并传播 (ESIGi(1), ESIGi(vi), \(\sigma\)r,s 我 ）。由于玩家 i′ 帮助传播了 在时间 \(\alpha\)r,s 之前，他的 CERT r 中的 (r, s−1) 消息 我′ + ts，再次是所有诚实的验证者 HSV r,s+1 停止而不传播任何东西并设置 Br = Br ǫ .同样，所有诚实的人 用户知道 Br = Br ϫ 在时间间隔 Ir+1 内并且 T r+1 \(\leq\) \(\alpha\)r,s 我′ + ts\(\leq\)T r + \(\lambda\) + ts。 案例 2.2.a.事件 E.a 发生并且不存在诚实的验证者 i′ \(\in\)HSV r,swho 也应该停止而不传播任何东西。 在这种情况下，请注意玩家 i 可能拥有有效的 CERT r i由所需的 tH 组成 (r, s−1) - 对手能够收集或生成的消息。然而，恶意 验证者可能无助于传播这些消息，因此我们不能得出结论说诚实的人 用户将在 \(\lambda\) 时间内收到它们。事实上，|MSV r,s−1|这些消息可能来自 恶意（r，s−1）验证者，他们根本不传播他们的消息，只发送 在步骤 s 中将它们发送给恶意验证者。 与情况 2.1.a 类似，这里我们有 s−2 ≡0 mod 3，步骤 s 是一个 Coin-Fixed-To-0 步骤， 以及 CERT r 中的 (r, s−1) 消息 i 代表位 0 且 v = H(Br \(\ell\)）。确实，大家都诚实 (r, s−1)-验证者对 v 进行签名，因此对手无法生成 tH 条有效的 (r, s−1)-消息 对于不同的 v′。 此外，所有诚实的 (r, s) 验证者都等待了 ts 时间，并且没有看到 > 2/3 的多数 对于位 1，同样是因为 |HSV r,s−1| + 4|MSV r,s−1| < 2n。因此，每一个诚实的验证者 i \(\in\)HSV r,s设 bi = 0, vi = H(Br \(\ell\)) 以多数票通过，并传播 mr,s 我 = (ESIGi(0)、ESIGi(H(Br \(\ell\))), \(\sigma\)r,s 我 ) 在时间 \(\alpha\)r,s 我 + ts。 现在考虑步骤 s+ 1 中的诚实验证者（这是一个 Coin-Fixed-To-1 步骤）。如果 攻击者实际上在 CERT r 中发送消息 i对其中一些并导致他们 停止，然后类似于情况2.1.a，所有诚实的用户都知道Br = Br \(\ell\)在时间间隔内 Ir+1 和 T r+1 \(\leq\)T r + \(\lambda\) + ts+1。 否则，步骤 s+1 中的所有诚实验证者都已收到 0 和 的所有 (r, s) 消息 H(溴 \(\ell\)) 来自 HSV r,s 在等待时间 ts+1 后，这导致 > 2/3 多数，因为 |HSV r,s| > 2|MSV r,s|。因此，HSV r,s+1 中的所有验证者将其消息传播为 0 和 H(Br \(\ell\)）相应地。请注意，HSV r,s+1 中的验证器不会以 Br = Br 停止 \(\ell\), 因为步骤 s+ 1 不是一个 Coin-Fixed-To-0 步骤。 现在考虑步骤 s+2 中的诚实验证者（这是一个真正翻转硬币的步骤）。 如果攻击者在 CERT r 中发送消息 i对其中一些人并导致他们停止， 那么所有诚实的用户都知道 Br = Br \(\ell\)在时间间隔 Ir+1 内并且 T r+1 \(\leq\)T r + \(\lambda\) + ts+2。否则，步骤 s+ 2 中的所有诚实验证者都已收到所有 (r, s+ 1) 消息 0 和 H(Br \(\ell\)) 在等待时间 ts+2 后从 HSV r,s+1 中生成，这导致 > 2/3 多数。 因此，它们都传播 0 和 H(Br \(\ell\)) 相应地：他们就是这么做的 在这种情况下，不是“抛硬币”。再次注意，它们不会停止传播， 因为步骤 s+ 2 不是一个 Coin-Fixed-To-0 步骤。 最后，对于步骤 s+3 中的诚实验证者（这是另一个 Coin-Fixed-To-0 步骤），所有 他们中的至少 tH 人会收到 0 和 H(Br \(\ell\)) 来自 HSV s+2， 如果他们真的等待时间ts+3。因此，无论对手是否发送消息 在 CERT 中 i对于其中任何一个，HSV r,s+3 中的所有验证器都以 Br = Br 停止 \(\ell\)，无 传播任何东西。根据对手的行为方式，其中一些人可能会 他们自己的 CERT r 由 CERT r 中的 (r, s−1) 消息组成 i，其他有 他们自己的 CERT r 由那些 (r, s+ 2) 消息组成。无论如何，所有诚实的用户 知道 Br = Br \(\ell\)在时间间隔 Ir+1 内并且 T r+1 \(\leq\)T r + \(\lambda\) + ts+3。 案例 2.2.b。事件 E.b 发生并且不存在诚实验证者 i′ \(\in\)HSV r,swho 也应该停止而不传播任何东西。 本案例的分析与案例2.1.b和案例2.2.a类似，因此有很多细节 已被省略。特别是，CERT i 由 tH 个所需的 (r, s−1) 消息组成 对于对手能够收集或生成的位 1，s−2 ≡1 mod 3，步骤 s 是 a Coin-Fixed-To-1 步骤，并且任何诚实的 (r, s) 验证者都无法看到 0 的多数票超过 2/3。 因此，每个验证者 i \(\in\) HSV r,s 设置 bi = 1 并传播 mr,s 我 = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s 我 ) 在时间 \(\alpha\)r,s 我 + ts。与案例 2.2.a 类似，最多多 3 个步骤（即协议 到达步骤 s+3，这是另一个 Coin-Fixed-To-1 步骤），所有诚实的用户都知道 Br = Br に 在时间间隔Ir+1内。而且，T r+1 可以\(\leq\)T r+\(\lambda\)+ts+1，或者\(\leq\)T r+\(\lambda\)+ts+2， 或 \(\leq\)T r + \(\lambda\) + ts+3，取决于诚实验证者第一次能够停止的时间 无需传播。 结合四个子情况，我们可以得到在时间间隔内所有诚实用户都知道 Br Ir+1，与 在情况 2.1.a 和 2.1.b 中，T r+1 \(\leq\)T r + \(\lambda\) + ts，并且 在情况 2.2.a 和 2.2.b 中，T r+1 \(\leq\)T r + \(\lambda\) + ts+3。 对于情况 2，它仍然是上限 s，因此 T r+1，我们通过考虑如何做到这一点 很多时候，Coin-Genuinely-Flipped 步骤实际上是在协议中执行的：也就是说， 一些诚实的验证者实际上已经掷硬币了。 特别是，任意固定一个硬币真实翻转步骤 s′（即 7 \(\leq\) s′ \(\leq\) m + 2 且 s′ −2 ≡2 mod 3)，令 \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ）。现在让我们假设 s′ < s， 因为否则的话，根据之前的说法，没有诚实的验证者会在步骤 s' 中实际掷硬币 讨论。 根据 SV r,s′−1 的定义，\(\ell\)′ 凭证的 hash 值也是其中最小的 PKr−k 中的所有用户。由于 hash 函数是随机的 oracle，理想情况下玩家 \(\ell\)′ 是诚实的 概率至少为 h。正如我们稍后将展示的，即使对手尽力预测 随机 oracle 的输出并倾斜概率，玩家 \(\ell\)′ 仍然对概率诚实至少 ph = h2(1 + h −h2)。下面我们考虑确实发生这种情况的情况：也就是说， \(\ell\)′ \(\varepsilon\) HSV r,s′−1。 请注意，每个诚实的验证者 i \(\in\) HSV r,s′ 已收到来自 HSV r,s′−1 的所有消息 时间\(\alpha\)r,s′ 我 + ts′。 如果玩家 i 需要掷硬币（即，他没有看到超过 2/3 的多数票） 相同的位 b \(\in\){0, 1})，那么他设置 bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ ））。如果存在另一个诚实的人 验证者 i′ \(\in\)HSV r,s′ 已经看到 b \(\in\){0, 1} 位的超过 2/3 多数，然后通过属性 引理 5.5 的 (d)，HSV r,s' 中没有诚实的验证者会暂时看到 > 2/3 多数 b′ ̸= b。由于 lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b 以 1/2 的概率，HSV r,s′ 中所有诚实的验证者都达到 以 1/2 的概率就 b 达成一致。当然，如果这样的验证器 i′ 不存在，那么所有 HSV r,s′ 中的诚实验证者同意 lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) 概率为 1。 结合 \(\ell\)′ \(\in\)HSV r,s′−1 的概率，我们得到 HSV r,s′ 中的诚实验证者 就比特 b \(\in\){0, 1} 达成一致，概率至少为 ph 2 = h2(1+h−h2) 2 。而且， 通过像以前一样的多数投票归纳，HSV r,s' 中所有诚实的验证者都有他们的 vi 集 为 H(Br \(\ell\)）。因此，一旦在步骤 s' 中就 b 达成一致，则 T r+1 为 \(\leq\)T r + \(\lambda\) + ts′+1 或 \(\leq\)T r + \(\lambda\) + ts′+2， 取决于 b = 0 还是 b = 1，根据案例 2.1.a 和 2.1.b 进行分析。在 特别是，不会执行进一步的 Coin-Genuinely-Flipped 步骤：也就是说，验证者 这些步骤仍然会检查它们是否是验证者并因此等待，但它们都会停止而不需要 传播任何东西。因此，在步骤s之前，执行Coin-GenuinelyFlipped步骤的次数根据随机变量Lr进行分配。令步骤 s′ 是根据 Lr 的最后一个硬币真实翻转步骤，通过协议的构建 我们有 s′ = 4 + 3Lr。 如果对手想要延迟 T r+1 尽可能多，他应该什么时候进行步骤 s 可能吗？我们甚至可以假设对手提前知道 Lr 的实现。如果 s> s′ 那么它就没用了，因为诚实的验证者已经在 步骤s′。可以肯定的是，在这种情况下 s 将是 s′ +1 或 s′ +2，同样取决于 b = 0 是否 或 b = 1。然而，这实际上是情况 2.1.a 和 2.1.b，所得的 T r+1 正是 与那种情况相同。更准确地说， T r+1 \(\leq\)T r + \(\lambda\) + ts\(\leq\)T r + \(\lambda\) + ts′+2。 如果 s< s′ -3 —即 s 在倒数第二个硬币真实翻转步骤之前 — 则通过 案例2.2.a和2.2.b的分析， T r+1 \(\leq\)T r + \(\lambda\) + ts+3 < T r + \(\lambda\) + ts′。 也就是说，对手实际上正在使 Br 的协议更快地达成。 如果 s= s′ −2 或 s′ −1 — 即 Coin-Fixed-To-0 步骤或 Coin-Fixed-To-1 步骤 紧接在步骤 s' 之前——然后通过对四个子案例的分析，诚实验证者 步骤 s' 不再能够抛硬币，因为它们要么停止而没有传播， 或已经看到 > 2/3 大多数相同位 b．因此我们有 T r+1 \(\leq\)T r + \(\lambda\) + ts+3 \(\leq\)T r + \(\lambda\) + ts′+2。总而言之，无论 s 是什么，我们都有 T r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = Tr + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = T r + (6Lr + 10)\(\lambda\) + Λ, 正如我们想要展示的那样。最坏的情况是当 s*= s′ −1 且情况 2.2.b 发生时。 结合二进制 BA 协议的情况 1 和情况 2，引理 5.3 成立。 ■ 5.9 种子 Qr 的安全性和诚实领导者的概率 引理 5.4 仍有待证明。回想一下，第 r 轮中的验证者取自 PKr−k 并且 根据数量 Qr−1 选择。引入回顾参数k的原因 是为了确保，回到 r −k 轮时，对手能够添加新的恶意用户 对于 PKr−k，他无法预测数量 Qr−1，除非概率可以忽略不计。请注意， hash 函数是一个随机 oracle 函数，Qr−1 是在为 r 轮选择验证器时的输入之一。 因此，无论恶意用户如何添加到 PKr−k，从对手的角度来看，每个 其中一个仍然在第 r 轮的步骤中以所需的概率 p（或 p1 代表步骤 1)。更准确地说，我们有以下引理。 引理 5.6。 k = O(log1/2 F)，对于每一轮 r，对手以压倒性的概率获胜 没有在 r −k 轮时向随机 oracle 查询 Qr−1。 证明。我们通过归纳法进行。假设对于每一轮 \(\gamma\) < r，对手没有查询 Q\(\gamma\)−1 到第 \(\gamma\) -k.21 轮的随机 oracle 考虑以下心理游戏 对手在 r −k 轮尝试预测 Qr−1。 在每轮的第 1 步中 \(\gamma\) = r −k, 。 。 。 , r −1, 给定一个特定的 Q\(\gamma\)−1，未查询到随机数 oracle，根据 hash 值 H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) 对玩家 i \(\in\)PK\(\gamma\)−k 进行排序 我们越来越多地获得 PK\(\gamma\)−k 上的随机排列。根据定义，领导者 \(\ell\) \(\gamma\) 是 排列中的第一个用户并且对概率 h 是诚实的。此外，当 PK\(\gamma\)−k 较大时 足够了，对于任何整数 x \(\geq\)1，排列中前 x 个用户都是的概率 恶意的，但第 (x + 1)st 是诚实的，是 (1 −h)xh。 如果 \(\ell\) \(\gamma\) 是诚实的，则 Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\))。由于对手无法伪造签名 从对手的角度来看，Q\(\gamma\) 的 \(\ell\) \(\gamma\) 是随机均匀分布的，并且，除了 以指数小概率，22 在 r −k 轮没有被查询到 H。 由于每个 Q\(\gamma\)+1，Q\(\gamma\)+2，. 。 。 、Qr−1 分别是 H 与 Q\(\gamma\)、Q\(\gamma\)+1、... 的输出。 。 。 , Qr−2 作为输入之一， 它们对对手来说都是随机的，并且对手无法在以下时间查询 Qr−1 到 H 轮 r −k。 因此，对手可以在回合中以良好概率预测 Qr−1 的唯一情况 r−k 是当所有领导者 \(\ell\)r−k, . 。 。 , \(\ell\)r−1 是恶意的。再次考虑一轮 \(\gamma\) \(\in\){r−k 。 。 。 , r−1} 以及由相应的 hash 值引起的 PK\(\gamma\)−k 上的随机排列。如果对于某些 x \(\geq\)2，排列中的前 x −1 个用户都是恶意的，第 x 个是诚实的，那么 对手对 Q\(\gamma\) 有 x 种可能的选择：H(SIGi(Q\(\gamma\)−1, \(\gamma\))) 形式之一，其中 i 是以下之一 21由于 k 是一个小整数，不失一般性，我们可以假设协议的前 k 轮已经运行 在安全的环境下，归纳假设对于这些轮次成立。 22 也就是说，H 的输出长度呈指数增长。请注意，这个概率远小于 F。第一个 x−1 恶意用户，通过让玩家 i 成为第 轮 \(\gamma\) 的实际领导者；或 H(Q\(\gamma\)−1, \(\gamma\))，由 迫使 B\(\gamma\) = B\(\gamma\) ǫ .否则，第 \(\gamma\) 轮的领导者将是排列中的第一个诚实用户 Qr−1 对于对手来说变得不可预测。 对手应该采用 Q\(\gamma\) 的上述 x 个选项中的哪一个？去帮助对手 回答这个问题，在心理游戏中我们实际上让他比实际更强大 是，如下。首先，实际上，对手无法计算诚实用户的 hash 签名，因此无法确定对于每个Q\(\gamma\)，一开始的恶意用户数x(Q\(\gamma\)) 由 Q\(\gamma\) 引起的第 \(\gamma\) + 1 轮中的随机排列。在心理游戏中，我们给他 免费计算 x(Q\(\gamma\))。其次，实际上，排列中的前 x 个用户都是 恶意并不一定意味着他们都可以成为领导者，因为 hash 它们的签名值也必须小于 p1。我们忽略了这种精神上的束缚 比赛中，给对手更多的优势。 很容易看出，在心理博弈中，对手的最优选择用 ˆQ\(\gamma\) 表示， 是在随机开始时产生最长的恶意用户序列的一个 第 \(\gamma\) + 1 轮的排列。事实上，给定一个特定的 Q\(\gamma\)，该协议不依赖于 Q\(\gamma\)−1 对手只能专注于第 \(\gamma\) + 1 轮中的新排列，其中有 开始时恶意用户数量的分布相同。相应地，在每一轮中 \(\gamma\)，上面提到的^Q\(\gamma\)给了他最大数量的Q\(\gamma\)+1的选项，从而最大化 连续领导者都是恶意的概率。 因此，在心理游戏中，对手遵循来自 r −k 轮的马尔可夫链 将 r −1 舍入，状态空间为 {0} \(\cup\){x : x \(\geq\)2}。状态 0 表示以下事实： 当前轮 \(\gamma\) 中随机排列中的第一个用户是诚实的，因此对手失败了 预测 Qr−1 的游戏；每个状态 x \(\geq\)2 都表示该状态中的第一个 x −1 个用户 排列是恶意的，第 x 个是诚实的，因此对手有 x 个 Q\(\gamma\) 选项。的 转移概率 P(x, y) 如下。 • 对于任何y \(\geq\)2，P(0, 0) = 1 且P(0, y) = 0。也就是说，对手一旦第一次失败，游戏就失败了。 排列中的用户变得诚实。 • 对于任何x \(\geq\)2，P(x, 0) = hx。也就是说，以概率 hx，所有 x 随机排列都有 他们的第一个用户是诚实的，因此对手在下一轮游戏中失败。 • 对于任何 x \(\geq\)2 且 y \(\geq\)2，P(x, y) 是 x 随机排列中的概率 由 Q\(\gamma\) 的 x 个选项引发，开始时的最长恶意用户序列 其中一些是 y −1，因此对手在下一轮中对于 Q\(\gamma\)+1 有 y 个选项。也就是说， P(x, y) = y−1 X 我=0 (1−h)ih !x - y−2 X 我=0 (1−h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x。 请注意，状态 0 是过渡矩阵 P 中唯一的吸收状态，其他所有状态 x 具有变为 0 的正概率。我们感兴趣的是确定 k 的上限 马尔可夫链以压倒性的概率收敛到 0 所需的轮数：也就是说，没有 无论链从哪个状态开始，对手都以压倒性的概率输掉比赛 并且无法在 r −k 轮预测 Qr−1。 考虑两轮后的转移矩阵 P (2) \(\triangleq\)P \(\cdot\) P。容易看出 P (2)(0, 0) = 1 对于任何 x \(\geq\)2，P (2)(0, x) = 0。对于任何 x \(\geq\)2 且 y \(\geq\)2，当 P(0, y) = 0 时，我们有 P (2)(x, y) = P(x, 0)P(0, y) + X z\(\geq\)2 P(x, z)P(z, y) = X z\(\geq\)2 P(x,z)P(z,y)。令 ¯h \(\triangleq\)1 −h，我们有 P(x, y) = (1 −́hy)x −(1 −́hy−1)x 和 P (2)(x, y) = X z\(\geq\)2 [(1−́hz)x−(1−́hz−1)x][(1−́hy)z−(1−́hy−1)z]。 下面我们计算 P (2)(x,y) 的极限 P(x,y) 当 h 变为 1 时，即 ¯h 变为 0。请注意，最高 P(x, y) 中 ̅h 的阶为 ̅hy−1，系数为 x。据此， 林 小时→1 P (2)(x,y) P(x,y) = 林 ́h \(\to\) 0 P (2)(x,y) P(x,y) = 林 ́h \(\to\) 0 P (2)(x,y) x́hy−1 + O(́hy) = 林 ́h \(\to\) 0 磷 z\(\geq\)2[xˆhz−1 + O(ˆhz)][zˆhy−1 + O(ˆhy)] x́hy−1 + O(́hy) = 林 ́h \(\to\) 0 2x́hy + O(́hy+1) x́hy−1 + O(́hy) = 林 ́h \(\to\) 0 2x￣hy x́hy−1 = lim h \(\to\) 0 2h = 0。 当 h 足够接近 1,23 时，我们有 P (2)(x,y) P(x,y) \(\leq\)1 2 对于任意 x \(\geq\)2 且 y \(\geq\)2。通过归纳法，对于任何 k > 2，P (k) \(\triangleq\)P k 使得 • P (k)(0, 0) = 1，对于任何 x \(\geq\)2，P (k)(0, x) = 0，并且 • 对于任意 x \(\geq\)2 且 y \(\geq\)2， P (k)(x, y) = P (k−1)(x, 0)P(0, y) + X z\(\geq\)2 P (k−1)(x, z)P(z, y) = X z\(\geq\)2 P (k−1)(x, z)P(z, y) \(\leq\) X z\(\geq\)2 P(x,z) 2k−2 \(\cdot\) P(z, y) = P(2)(x, y) 2k−2 \(\leq\)P(x,y) 2k−1 。 由于 P(x, y) \(\leq\)1，经过 1−log2 F 轮后，进入任何状态 y \(\geq\)2 的转移概率可以忽略不计， 从任何状态 x \(\geq\) 2 开始。虽然这样的状态 y 有很多，但很容易看出 林 y→+∞ P(x,y) P(x, y + 1) = 林 y→+∞ (1−́hy)x−(1−́hy−1)x (1−́hy+1)x−(1−́hy)x= 林 y→+∞ ́hy−1 -́hy ́hy -́hy+1 = 1 h = 1 1 小时。 因此，转移矩阵 P 的每一行 x 作为几何序列以速率减小 1 1−h > 2 当y足够大时，P(k)也是如此。因此，当 k 足够大但仍然 log1/2 F, P 量级 对于任何 x \(\geq\)2，y\(\geq\)2 P (k)(x, y) < F。也就是说，以压倒性的概率 对手输掉了比赛并且未能在 r −k 轮预测 Qr−1。对于 h \(\in\)(2/3, 1]，更多 复分析表明存在一个略大于 1/2 的常数 C，因此满足 取 k = O(logC F)。因此引理 5.6 成立。 ■ 引理 5.4。 （重述）给定 r 之前每轮的属性 1-3，Lr 的 ph = h2(1 + h −h2)， 并且领导者 \(\ell\)r 是诚实的，概率至少为 ph。 23例如，根据参数的具体选择，h = 80%。
证明。遵循引理 5.6，对手无法在 r −k 轮预测 Qr−1，除非 概率可以忽略不计。请注意，这并不意味着诚实领导者的概率为 h 每轮。事实上，给定 Qr−1，取决于在开始时有多少恶意用户 PKr−k 的随机排列，对手对于 Qr 和 Qr 可能有多个选项 因此可以增加第 r + 1 轮中恶意领导者的概率——我们再次给他 引理5.6中一些不切实际的优点，以简化分析。 然而，对于每个 Qr−1 ，对手在 r −k 轮时没有向 H 查询，对于 任何 x \(\geq\)1，第一个诚实用户出现在结果中的位置 x 的概率为 (1 −h)x−1h PKr−k 的随机排列。当 x = 1 时，第 r + 1 轮中诚实领导者的概率为 确实是h；而当 x = 2 时，对手有两个 Qr 选项，结果概率为 h2。仅通过考虑这两种情况，我们就可以得到回合中诚实领导者的概率 根据需要，r+1至少为h \(\cdot\) h+(1-h)h \(\cdot\) h2=h2(1+h-h2)。 请注意，上述概率仅考虑第 r -k 轮协议中的随机性 到圆河当考虑第 0 轮到第 r 轮的所有随机性时，Qr−1 为 对于对手来说更不可预测，并且第 r + 1 轮中诚实领导者的概率为 至少 h2(1 + h −h2)。将 r + 1 替换为 r 并将所有内容向后移动一轮，即领导者 \(\ell\)r 根据需要，至少有 h2(1 + h −h2) 的概率是诚实的。 类似地，在每个硬币真实翻转步骤 s 中，该步骤的“领导者”——即验证者 在 SV r,s 中，其凭证具有最小 hash 值，其诚实概率至少为 h2(1 + h−h2)。因此 Lr 的 ph = h2(1 + h −h2) 且引理 5.4 成立。 ■
Algorand ′
2 在本节中，我们构建了在以下假设下工作的 Algorand ' 版本。 诚实的大多数用户假设：每个 PKr 中超过 2/3 的用户是诚实的。 在第 8 节中，我们展示了如何用所需的诚实多数来替换上述假设 金钱假设。 6.1 Algorand ′ 的附加符号和参数 2 符号 \(\mu\) \(\varepsilon\)Z+：步数的实用上限，以压倒性的概率， 实际上将在一轮中进行。 （正如我们将看到的，参数 \(\mu\) 控制有多少个短暂的 用户为每轮提前准备的密钥。） • Lr：随机变量，代表看到 1 所需的伯努利试验次数，当每次试验 试验次数为 1，概率为 ph 2. Lr 将用于确定生成所需时间的上限 块 Br。 • tH：第 r 轮步骤 s > 1 中诚实验证者数量的下界，使得 压倒性概率（给定 n 和 p），SV r,s 中有 > tH 个诚实验证者。 参数 • 各种参数之间的关系。 — 对于第 r 轮的每一步 s > 1，选择 n 使得以压倒性的概率，
|HSV r,s| > tH 和 |HSV r,s| + 2|MSV r,s| <2tH。 请注意，上面的两个不等式一起意味着 |HSV r,s| > 2|MSV r,s|：即有 是选定验证者中 2/3 的诚实多数。 h的值越接近1，n需要越小。特别是，我们使用（变体 of) Chernoffbounds 以确保所需条件以压倒性概率成立。 • 重要参数的选择示例。 — F = 10−18。 — n 约 4000，tH 约 0.69n，k = 70。 6.2 在 Algorand ' 中实现临时密钥 2 回想一下，验证者 i \(\in\)SV r,s 对他的消息 mr,s 进行了数字签名 我 r 轮中步骤 s 的数量，相对于 临时公钥 pkr,s i ，使用临时秘密密钥 skr,s 我 他立即摧毁 使用后。 当一轮可能采取的步数受到给定的限制时 整数 \(\mu\)，我们已经了解了如何实际处理临时密钥。例如，当我们 已在 Algorand ' 中解释 1（其中 \(\mu\) = m + 3），处理所有可能的临时密钥，从 一轮 r′ 到一轮 r′ + 106，i 生成一对 (PMK, SMK)，其中 PMK 公共主控 基于身份的签名方案的密钥，SMK 其相应的秘密主密钥。用户我 公开 PMK 并使用 SMK 生成每个可能的临时公钥的秘密密钥 （并在这样做后销毁 SMK）。相关的 i 的临时公钥集 轮次为 S = {i} \(\times\) {r′, . 。 。 , r′ + 106} \(\times\) {1, . 。 。 ，μ}。 （正如所讨论的，随着 r' + 106 轮的临近， 我“刷新”了他的配对（PMK、SMK）。） 实际上，如果 \(\mu\) 足够大，则一轮 Algorand ′ 2 不会采取超过 \(\mu\) 步。在 然而，原则上，存在一种极小的可能性，即对于某一轮 r 的步数 实际取值将超过μ。当这种情况发生时，我将无法签署他的信息，先生 我 为了 任何步骤 s > \(\mu\)，因为他提前为 r 轮准备了 \(\mu\) 个密钥。而且，他 正如之前所讨论的，无法准备和公开新的临时密钥存储。事实上，要做 因此，他需要在新块中插入新的公共主密钥 PMK'。但是，应该舍入 r 采取越来越多的步骤，不会生成新的块。 然而，解决方案是存在的。例如，我可以使用 r 轮的最后一个临时密钥，pkr，μ 我 , 如下。他为 r 轮生成另一个密钥对存储 — 例如，通过 (1) 生成另一个 主密钥对（PMK、SMK）； (2) 使用这对生成另一个，例如 106 个临时密钥， 斯克 r,μ+1 我 , . 。 。 , sk r,μ+106 我 ，对应第r轮的步骤μ+1，...，μ+106； (3) 使用 skr,μ 我 以数字方式 符号 PMK（以及任何 (r, \(\mu\)) 消息，如果 i \(\in\)SV r,\(\mu\)），相对于 pkr,\(\mu\) 我 ; (4) 擦除 SMK 和 skr,μ 我 。 我是否应该成为步骤 \(\mu\) + s 中的验证者，其中 s \(\in\){1, . 。 。 , 106}，然后我对他的 (r, \(\mu\) + s)- 进行数字签名 消息 mr,μ+s 我 相对于他的新关键PK r,μ+s 我 = (i, r, \(\mu\) + s)。当然，要验证这个签名 对于 i，其他人需要确定该公钥对应于 i 的新公共主密钥 PMK。 因此，除了这个签名之外，i 还传输他相对于 pkr,μ 的 PMK 数字签名 我 。 当然，如果 r 轮继续，这种方法可以根据需要重复多次 越来越多的步骤！最后一个临时密钥用于验证新的主公钥 密钥，因此也是 r 轮的临时密钥的另一个存储。等等。6.3 实际协议 Algorand ′ 2 再次回想一下，在 r 轮的每一步 s 中，验证者 i \(\in\)SV r,s 使用他的长期公开秘密 生成其凭证的密钥对 \(\sigma\)r,s 我 \(\triangleq\)SIGi(r, s, Qr−1)，以及 SIGi Qr−1 如果 s = 1。 验证者 i 使用他的临时密钥对，(pkr,s 我,skr,s i ), 签署任何其他可能的消息 m 需要。为了简单起见，我们写 esigi(m)，而不是 sigpkr,s i (m)，表示 i 的固有短暂性 这一步中m的签名，并写ESIGi(m)而不是SIGpkr,s i (m) \(\triangleq\)(i, m, esigi(m))。 第 1 步：区块提案 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦完成，就开始自己的第 r 轮步骤 1 CERT r−1，它允许 i 明确计算 H(Br−1) 和 Qr−1。 • 用户i 使用Qr−1 来检查i 是否属于SV r,1。如果 i /\(\varepsilon\)SV r,1，他对步骤 1 不执行任何操作。 • 如果i \(\in\)SV r,1，也就是说，如果i 是潜在的领导者，那么他会执行以下操作。 (a) 如果我见过 B0，. 。 。 , Br−1 本身（任何 Bj = Bj ϫ 可以很容易地从它的 hash 值中推导出来 在 CERT j 中，因此被假定为“已看到”），然后他收集 R 轮付款 到目前为止已传播给他并计算最大支付集 PAY r 我来自他们。 (b) 如果我还没有看到所有 B0，. 。 。 , Br−1 还没有，那么他设置 PAY r 我=\(\emptyset\)。 (c) 接下来，我计算他的“候选块”Br 我 = (r, 支付 r i , SIGi(Qr−1), H(Br−1))。 (c) 最后，我计算消息 mr,1 我 = (Br i , esigi(H(Br i )), \(\sigma\)r,1 i ), 毁掉了他短暂的 密钥 skr,1 i ，然后传播两条消息 mr,1 我 和 (SIGi(Qr−1), \(\sigma\)r,1 我), 分别但同时.a a当 i 是领导者时，SIGi(Qr−1) 允许其他人计算 Qr = H(SIGi(Qr−1), r)。
选择性传播 为了缩短步骤 1 和整个回合的全局执行时间，重要的是 (r, 1)- 消息是有选择地传播的。也就是说，对于系统中的每个用户 j， • 对于他收到并成功验证的第一条 (r, 1) 消息，a 是否包含 一个区块 or 只是一个凭证和 Qr−1 的签名，玩家 j 像往常一样传播它。 • 对于玩家 j 收到并成功验证的所有其他 (r, 1) 消息，他传播 仅当它包含的凭证的 hash 值是 hash 值中最小的时候才使用它 他已收到并成功验证的所有 (r, 1) 消息中包含的凭据 远。 • 然而，如果j 收到两个不同的消息，其形式为mr,1 我 来自同一个玩家 i,b he 无论 i 凭证的 hash 值是多少，都会丢弃第二个。 请注意，在选择性传播下，每个潜在领导者 i 传播他的信息是有用的 凭证 \(\sigma\)r,1 我 与 mr,1 分开 i :c 这些小消息的传输速度比块快，确保 及时传播 mr,1 i 所包含的凭据具有较小的 hash 值，而 使 hash 值较大的那些快速消失。 a 也就是说，所有签名都是正确的，如果是 mr,1 的形式 i ，该块及其 hash 均有效 —尽管 j 不检查包含的支付集对于 i 是否是最大的。 b这意味着我是恶意的。 c我们感谢 Georgios Vlachos 的建议。第二步：分级共识协议GC的第一步 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦完成，就开始自己的第 r 轮步骤 2 CERT r−1。 • 用户i 等待的最长时间为t2 \(\triangleq\) \(\lambda\) + Λ。在等待期间，我的行为如下。 1. 等待时间 2\(\lambda\) 后，他找到用户 \(\ell\)，使得 H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j) 对于所有人 凭证 \(\sigma\)r,1 j 这是他收到的已成功验证的 (r, 1) 消息的一部分 到目前为止.a 2.如果 他 有 收到 一个 块 Br−1, 其中 比赛 的 hash 值 H(Br−1) H(Br−1) 包含在 CERT r−1,b 中，并且如果他已从 \(\ell\) 收到有效消息 mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c 然后 i 停止等待并设置 v′ 我 \(\triangleq\)(H(Br \(\ell\))，\(\ell\))。 3. 否则，当时间t2用完时，i设置v′ 我\(\triangleq\) \(\bot\)。 4. 当v′的值 i 已设置，i 根据 CERT r−1 计算 Qr−1 并检查是否 i \(\in\)SV r,2 与否。 5. 如果 i \(\in\)SV r,2，则 i 计算消息 mr,2 我 \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),d 摧毁了他的短暂 密钥 skr,2 i ，然后传播 mr,2 我。 否则，我会停止而不传播 任何东西。 a本质上，用户i私下决定r轮的领导者是用户\(\ell\)。 b当然，如果CERT r−1 表明 Br−1 = Br−1 に ，那么当他收到时，我就已经“收到”了 Br−1 CERT r−1。 c再次，玩家\(\ell\)的签名和hashes都已成功验证，并且PAY r \(\ell\) 溴 \(\ell\) 是有效的支付集 回合 r — 尽管我不检查是否 PAY r \(\ell\) 是否为 \(\ell\) 的最大值。如果溴 \(\ell\)包含一个空的支付集，那么 实际上，在验证 Br 是否存在之前，i 不需要看到 Br−1 \(\ell\) 是否有效。 d消息 mr,2 我 表示玩家 i 考虑 v′ 的第一个分量 i 是下一个块的 hash ，或者 认为下一个块是空的。
步骤3：GC第二步 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦完成，就开始自己的第 r 轮步骤 3 CERT r−1。 • 用户i 等待的最长时间为t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ。在等待时，我充当 接下来。 1.如果存在一个值v使得他至少收到了tH条有效消息mr,2 j 的 形式 (ESIGj(v), \(\sigma\)r,2 j ), 没有任何矛盾, a 然后他停止等待并设置 v′ = v。 2. 否则，当时间 t3 结束时，他设置 v′ = \(\bot\)。 3. 设置 v′ 的值后，i 根据 CERT r−1 计算 Qr−1 并检查是否 i \(\in\)SV r,3 与否。 4. 如果 i \(\in\)SV r,3，则 i 计算消息 mr,3 我 \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 i ), 毁掉他的 临时密钥 skr,3 i ，然后传播 mr,3 我。 否则，我就停止了 传播任何东西。 a即他没有收到两条分别包含ESIGj(v)和不同ESIGj(ˆv)的有效消息， 来自玩家 j。从现在开始，除了稍后定义的结束条件外，每当诚实的玩家 想要给定形式的消息，相互矛盾的消息永远不会被计算或被认为是有效的。
步骤4：GC的输出和BBA的第一步⋆ 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始他自己的第 r 轮步骤 4 完成他自己的第3步。 • 用户i 等待的最长时间为2\(\lambda\).a 在等待期间，i 的操作如下。 1. 他计算 GC 的输出 vi 和 gi，如下所示。 (a) 如果存在一个值 v′ ̸= \(\bot\) 使得他至少收到了 tH 条有效消息 先生,3 j = (ESIGj(v′), \(\sigma\)r,3 j )，然后他停止等待并设置 vi \(\triangleq\)v′ 和 gi \(\triangleq\)2。 (b) 如果他至少收到了 tH 条有效消息 mr,3 j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j )，然后他停下来 等待并设置 vi \(\triangleq\) \(\bot\) 和 gi \(\triangleq\)0.b (c) 否则，当时间 2\(\lambda\) 耗尽时，如果存在值 v′ ̸= \(\bot\)，则有 至少收到 ⌈tH 2 ⌉有效消息 mr,j j = (ESIGj(v′), \(\sigma\)r,3 j ), 然后他设置 vi \(\triangleq\)v′ 和 gi \(\triangleq\)1.c (d) 否则，当时间 2\(\lambda\) 耗尽时，他设置 vi \(\triangleq\) \(\bot\) 和 gi \(\triangleq\)0。 2. 当vi和gi的值设置完毕后，i计算BBA⋆的输入bi，如下： 如果 gi = 2，则 bi \(\triangleq\)0，否则 bi \(\triangleq\)1。 3. i 根据 CERT r−1 计算 Qr−1 并检查 i 是否 \(\in\)SV r,4 。 4. 如果 i \(\in\)SV r,4，他计算消息 mr,4 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), 毁掉他的 临时密钥 skr,4 i ，并传播 mr,4 我。否则，我会停止而不传播 任何东西。 因此，自 i 开始第 r 轮步骤 1 以来的最大总时间可能是 t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ。 b 步骤(b)是否在协议中并不影响其正确性。然而，步骤(b)的存在 如果有足够多的第 3 步验证者“签名\(\bot\)”，则第 4 步可以在不到 2\(\lambda\) 的时间内结束。 c可以证明，这种情况下的v′，如果存在的话，一定是唯一的。步骤 s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3：BBA⋆的硬币固定至 0 步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 完成他自己的步骤 s -1。 • 用户i 等待的最长时间为2\(\lambda\).a 在等待期间，i 的操作如下。 – 结束条件 0：如果在任意点存在字符串 v ̸= \(\bot\) 和步骤 s′，使得 (a) 5 \(\leq\) s′ \(\leq\) s, s′ −2 eq 0 mod 3 — 也就是说，步骤 s′ 是一个 Coin-Fixed-To-0 步骤， (b) i 已收到至少 tH 条有效消息 mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b 和 (c) i 已收到有效消息 (SIGj(Qr−1), \(\sigma\)r,1 j ) 其中 j 是第二个 v 的分量， 然后，i 停止等待并结束自己对步骤 s 的执行（实际上是 r 轮） 立即作为 (r, s) 验证者传播任何内容；将 H(Br) 设为第一个 v 的分量；并将自己的 CERT r 设置为消息集 mr,s′−1 j 步骤(b)的 与 (SIGj(Qr−1), \(\sigma\)r,1 j).c – 结束条件 1：如果在任意点存在步骤 s′，使得 (a’) 6 \(\leq\)s′ \(\leq\)s, s′ -2 eq 1 mod 3 — 即，步骤 s′ 是 Coin-Fixed-To-1 步骤，并且 (b’) i 已收到至少 tH 条有效消息 mr,s’−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d 然后，i 停止等待并结束自己对步骤 s 的执行（实际上是第 r 轮） 不作为 (r, s) 验证者传播任何内容；设 Br = Br \(\varepsilon\) ;并设定了自己的 CERT r 是消息集 mr,s′−1 j 子步骤(b’)的。 – 如果 在 任何 点 他 有 收到 在 至少 tH 有效 先生,s−1 j 的 的 的 形式 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他停止等待并设置 bi \(\triangleq\)1。 – 如果 在 任何 点 他 有 收到 在 至少 tH 有效 先生,s−1 j 的 的 的 形式 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ），但他们在同一个 v 上不一致，然后他停下来 等待并设置 bi \(\triangleq\)0。 – 否则，当时间 2\(\lambda\) 耗尽时，i 设置 bi \(\triangleq\)0。 – 设置值 bi 后，i 根据 CERT r−1 计算 Qr−1 并检查是否 i \(\in\)SV r,s。 – 如果 i \(\in\)SV r,s，i 计算消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) 与 vi 是 他在步骤 4 中计算出的值会破坏他的临时密钥 skr,s 我，然后 传播先生，s 我。否则，我会停止而不传播任何内容。 因此，自 i 开始第 r 轮第 1 步以来的最大总时间可以是 ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s -3)\(\lambda\) + Λ。 b 即使玩家 i 也收到了来自 j 的签名为 1 的消息，来自玩家 j 的此类消息也会被计数。 结束条件1类似。如分析所示，这是为了确保所有诚实的用户都知道 CERT r 彼此之间的时间间隔为 \(\lambda\)。 cUser i 现在知道 H(Br) 并且他自己的 r 轮结束。他只需要等到实际的区块 Br 出现 传播给他，这可能需要一些额外的时间。他仍然以普通用户的身份帮助传播消息， 但不会作为 (r, s) 验证者启动任何传播。特别是，他帮助传播了所有信息 他的 CERT r，这对于我们的协议来说已经足够了。注意，他还应该为二进制 BA 协议设置 bi \(\triangleq\)0，但是 无论如何，在这种情况下不需要 bi。类似的事情适用于所有未来的指示。 d在这种情况下，vj 是什么并不重要。 65步骤 s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3：BBA⋆的硬币固定到 1 步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 完成他自己的步骤 s -1。 • 用户i 等待的最长时间为2\(\lambda\)。在等待期间，我的行为如下。 – 结束条件 0：与 Coin-Fixed-To-0 步骤中的指令相同。 – 结束条件 1：与 Coin-Fixed-To-0 步骤中的指令相同。 – 如果 在 任何 点 他 有 收到 在 至少 tH 有效 先生,s−1 j 的 的 的 形式 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他停止等待并设置 bi \(\triangleq\)0.a – 否则，当时间 2\(\lambda\) 耗尽时，i 设置 bi \(\triangleq\)1。 – 设置值 bi 后，i 根据 CERT r−1 计算 Qr−1 并检查是否 i \(\in\)SV r,s。 – 如果 i \(\in\)SV r,s，i 计算消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) 与 vi 是 他在步骤 4 中计算出的值会破坏他的临时密钥 skr,s 我，然后 传播先生，s 我。否则，我会停止而不传播任何内容。 a注意，接收到签名为 1 的 tH 个有效 (r, s −1) 消息意味着结束条件 1。 步骤 s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3：BBA⋆的硬币真实翻转步骤 对每个用户 i \(\in\)PKr−k 的说明：用户 i 一旦他开始，就开始他自己的第 r 轮步骤 s 完成自己的步骤 s −1。 • 用户i 等待的最长时间为2\(\lambda\)。在等待期间，我的行为如下。 – 结束条件 0：与 Coin-Fixed-To-0 步骤中的指令相同。 – 结束条件 1：与 Coin-Fixed-To-0 步骤中的指令相同。 – 如果 在 任何 点 他 有 收到 在 至少 tH 有效 先生,s−1 j 的 的 的 形式 (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他停止等待并设置 bi \(\triangleq\)0。 – 如果 在 任何 点 他 有 收到 在 至少 tH 有效 先生,s−1 j 的 的 的 形式 (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j )，然后他停止等待并设置 bi \(\triangleq\)1。 – 否则，当时间 2\(\lambda\) 耗尽时，令 SV r,s−1 我 是 (r, s −1) 验证者的集合 他已收到有效消息 mr,s−1 j , i 设 bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 我 H(\(\sigma\)r,s−1 j ））。 – 设置值 bi 后，i 根据 CERT r−1 计算 Qr−1 并检查是否 i \(\in\)SV r,s。 – 如果 i \(\in\)SV r,s，i 计算消息 mr,s 我 \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) 与 vi 是 他在步骤 4 中计算出的值会破坏他的临时密钥 skr,s 我，然后 传播先生，s 我。否则，我会停止而不传播任何内容。 评论。 原则上，正如第 6.2 小节所考虑的，协议可以采用任意多个 某轮中的步骤。如果发生这种情况，正如所讨论的，用户 i \(\in\)SV r,s 且 s > \(\mu\) 已耗尽
他储存了预先生成的临时密钥，并且必须验证他的 (r, s) 消息 mr,s 我 由一个 临时密钥的“级联”。因此我的消息变得有点长并且传输的时间更长 消息将需要更多时间。因此，在给定回合的这么多步骤之后， 参数 \(\lambda\) 会自动稍微增加。 （但是一旦新的 \(\lambda\) 它就会恢复到原来的 \(\lambda\) 区块生成并开始新一轮。） 非验证者重建 Round-r 区块 系统中每个用户 i 的说明： 用户 i 一旦完成，就开始自己的回合 r CERT r−1。 • i遵循协议每一步的指示，参与所有的传播 消息，但如果他不是步骤中的验证者，则不会在步骤中发起任何传播。 • i 通过在某些情况下输入结束条件 0 或结束条件 1 来结束自己的回合 r 步骤，使用相应的 CERT r。 • 从那时起，他在等待接收实际区块 Br 的同时开始他的回合 r + 1（除非 他已经收到了），其 hash H(Br) 已被 CERT r 确定。再说一遍，如果 CERT r 表示 Br = Br ϫ，i 在获得 CERT r 后就知道 Br。 6.4 Algorand ' 的分析 2 Algorand ' 的分析 2 很容易从 Algorand ' 导出 1. 本质上，在 Algorand ′ 2、与 压倒性概率，(a) 所有诚实用户都同意同一个区块 Br；新的领导者 块是诚实的，概率至少为 ph = h2(1 + h −h2)。
处理线下诚实用户
正如我们所说，诚实的用户会遵循所有规定的指示，其中包括在线指示 并运行协议。这在 Algorand 中并不是一个主要负担，因为计算和 诚实用户所需的带宽相当适中。然而，让我们指出 Algorand 可以 可以轻松修改，以便在两种模型中工作，其中允许诚实的用户离线 数量巨大。 在讨论这两个模型之前，让我们指出，如果诚实玩家的百分比 是 95%，Algorand 仍然可以运行，设置所有参数，假设 h = 80%。 因此，即使最多一半的诚实玩家，Algorand也会继续正常工作 选择了离线（确实是“旷工”的一个重大案例）。事实上，在任何时候，至少 80%的在线玩家都是诚实的。 从持续参与到懒惰诚实 正如我们所见，Algorand ′ 1 和 Algorand ′ 2 选择 回顾参数k。现在让我们证明，选择适当大的 k 可以使我们删除 持续参与要求。这个要求确保了一个关键的属性：即 底层 BA 协议 BBA⋆拥有适当的诚实多数。现在让我们解释一下如何偷懒 诚实提供了一种替代且有吸引力的方式来满足这一特性。
回想一下，用户 i 是懒惰但诚实的，如果 (1) 他遵循所有规定的指示，当 他被要求参加该协议，并且 (2) 他被要求仅参加该协议 很少——例如每周一次——并有适当的提前通知，并且可能会收到重大的 当他参与时奖励。 为了允许 Algorand 与此类玩家合作，只需“选择 本轮中的用户已在更早一轮的系统中。”确实，请记住 r 轮的验证者是从 r −k 轮的用户中选出的，并且选择是基于 关于数量 Qr−1。请注意，一周大约包含 10,000 分钟，并假设 一轮大约需要（例如，平均）5 分钟，所以一周大约有 2,000 轮。假设 在某个时间点，用户希望计划他的时间并知道他是否会 下周将进行验证。该协议现在从以下用户中选择第 r 轮的验证者 轮 r −k −2, 000，选择基于 Qr−2,001。在 r 轮，我已经认识的玩家 值 Qr−2,000, . 。 。 ，Qr−1，因为它们实际上是 blockchain 的一部分。然后，对于每个M 在 1 到 2,000 之间，i 是第 r + M 轮步骤 s 中的验证者当且仅当 .H 西吉 r + M, s, Qr+M−2,001 \(\leq\)p。 因此，为了检查他是否会在接下来的 2,000 轮中被要求充当验证者，我必须 计算 \(\sigma\)M,s 我 = SIGi r + M, s, Qr+M−2,001 对于 M = 1 到 2, 000 以及对于每个步骤 s，并检查 是否.H(\(\sigma\)M,s 我 ) \(\leq\)p 对于其中一些。如果计算数字签名需要一毫秒，那么 整个操作将花费他大约 1 分钟的计算时间。如果他没有被选为验证者 在任何一轮中，他都可以带着“诚实的良心”下线。如果他不断地 参加的话，接下来的2000回合他基本上就走0步了！相反，如果 他被选为其中一轮的验证者，然后他做好准备（例如，通过获得所有 必要的信息）在适当的回合中充当诚实的验证者。 通过这样的行为，一个懒惰但诚实的潜在验证者 i 只会错过参与传播的机会 的消息。但消息传播通常是稳健的。此外，付款人和收款人 最近传播的支付预计将在线观察他们的支付发生了什么， 因此，如果他们是诚实的，他们就会参与消息传播。
诚实多数资金协议 Algorand ′
最后，我们现在展示如何用更多的假设来取代“诚实的大多数用户”假设 有意义的诚实多数资金假设。基本思想是（以 proof-of-stake 风格） “选择一个用户 i \(\in\)PKr−k 属于 SV r,s，其权重（即决策能力）与 我拥有的金钱数额。”24 根据我们的 HMM 假设，我们可以选择是否应该在 r −k 轮拥有该金额 或在 r 轮（开始）时。假设我们不介意持续参与，我们选择 后者的选择。 （为了消除持续参与，我们会选择前一种选择。 更好的说法是，在 r −k −2, 000 轮拥有的资金量。） 有很多方法可以实现这个想法。最简单的方法是按住每个键 最多 1 个货币单位，然后从 PKr−k 中随机选择 n 个用户 i，使得 a(r) 我 = 1。 24我们应该说 PKr−k−2,000 来代替持续参与。为简单起见，因为人们可能希望要求 不管怎样继续参与，我们还是像以前一样使用PKr−k，这样可以少带一个参数。
下一个最简单的实现 下一个最简单的实现可能是要求每个公钥拥有最大数量 货币 M，对于某个固定的 M。与货币总量相比，M 的值足够小 系统中的货币，这样一个密钥属于多个验证者集合的概率 比如说，k 轮中的步骤可以忽略不计。那么，一个密钥 i \(\in\) PKr−k，拥有一定数量的货币 a(r) 我 在第 r 轮中，被选择属于 SV r,s 如果 .H 西吉 r, s, Qr−1 \(\leq\)p \(\cdot\) a(r) 我 中号 。 一切都像以前一样进行。 更复杂的实现 最后的实现“迫使系统中的富有参与者拥有许多密钥”。 下面描述的另一种实现概括了状态的概念并考虑 每个用户 i 由 K + 1 个副本 (i, v) 组成，每个副本被独立选择为验证者， 并将拥有自己的临时密钥（pkr，s i,v,skr,s i,v) 在 r 轮的步骤 s 中。 K 值取决于 关于金额 a(r) 我 由 i 在 r 轮中拥有。 现在让我们更详细地看看这样的系统是如何工作的。 份数 令 n 为每个验证器集的目标预期基数，并令 a(r) 我 是用户 i 在第 r 轮拥有的资金量。令 Ar 为拥有的货币总量 由 r 轮 PKr−k 中的用户，即 氩气= X i\(\in\)P Kr−k 一个(r) 我。 如果 i 是 PKr−k 中的用户，则 i 的副本为 (i, 1),…。 。 。 , (i, K + 1)，其中 K = $ n \(\cdot\) a(r) 我 氩气 % 。 例子。设 n = 1, 000，Ar = 109，a(r) 我 = 370 万。然后， K = 103 \(\cdot\) （3.7 \(\cdot\) 106） 109 = ⌊3.7⌋= 3 。 验证者和凭证 令 i 为 PKr−k 中的用户，拥有 K + 1 个副本。 对于每个 v = 1，. 。 。 ,K,copy(i,v)自动属于SV r,s。也就是说，我的凭证是 \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1)，但对应的条件变为.H(\(\sigma\)r,s i,v) \(\leq\)1，即 永远正确。 对于副本 (i, K + 1)，对于第 r 轮的每个步骤 s，i 检查是否 .H 西吉 (i, K + 1), r, s, Qr−1 \(\leq\)a(r) 我 n Ar-K。
如果是，则副本 (i, K + 1) 属于 SV r,s。为了证明这一点，我传播了凭证 \(\sigma\)r,1 i,K+1 = SIGi (i, K + 1), r, s, Qr−1 。 例子。 与前面的示例一样，令 n = 1K, a(r) 我 = 3.7M，Ar = 1B，i 有 4 副本：(i, 1), . 。 。 ，（一世，4）。那么，前 3 个副本自动属于 SV r,s。对于第四个来说， 从概念上讲，Algorand ′ 独立地掷出一枚有偏差的硬币，正面朝上的概率为 0.7。复制 当且仅当抛硬币是正面时才选择 (i, 4)。 （当然，这种有偏见的抛硬币是通过hashing、签名和比较来实现的——正如我们 在这篇论文中我一直在做——以便让我能够证明他的结果。） 一切如常 解释了如何选择验证者及其凭证 在一轮 r 的每个步骤中计算，一轮的执行与已经解释的类似。
处理分叉
将分叉概率降低到 10−12 或 10−18 后，实际上没有必要处理 它们发生的可能性很小。 然而，Algorand 也可以使用各种分叉 解决程序，有或没有工作证明。 指导用户解决分叉的一种可能方法如下： • 如果用户看到多个链，则遵循最长的链。 • 如果有多个最长的链，则在该链的末尾添加一个非空块。如果 它们的末尾都有空块，考虑它们的倒数第二个块。 • 如果有多个最长的链末尾有非空块，则称这些链是 长度为 r，跟随块 r 的领导者拥有最小凭证的那个。如果有联系， 遵循块 r 本身具有最小 hash 值的块。如果仍然存在联系，请按照 其块 r 按字典顺序排列在第一个。
处理网络分区
如前所述，我们假设网络中所有用户之间的消息传播时间的上限为 \(\lambda\) 和 Λ。这不是一个强有力的假设，因为当今的互联网快速且强大，并且 这些参数的实际值是相当合理的。在此，我们指出 Algorand ′ 2 即使互联网偶尔被分成两部分，它仍然可以继续工作。情况当 互联网被分为两个以上的部分也是类似的。 10.1 物理分区 首先，分区可能是物理原因造成的。例如，一场大地震可能会 最终彻底切断了欧洲和美洲之间的联系。在这种情况下， 恶意用户也被分区，并且两部分之间没有通信。因此
将有两个对手，一个用于第 1 部分，另一个用于第 2 部分。每个对手仍然试图 破坏协议本身的一部分。 假设分区发生在 r 轮的中间。那么每个用户仍然被选为 基于 PKr−k 的验证器，概率与之前相同。设 HSV r,s 我 和 MSV r,s 我 分别 是第 i 部分 \(\in\){1, 2} 中步骤 s 中诚实和恶意验证者的集合。我们有 |HSV r,s 1 | + |MSV r,s 1 | + |HSV r,s 2 | + |MSV r,s 2 | = |HSV r,s| + |MSV r,s|。 请注意 |HSV r,s| + |MSV r,s| < |HSV r,s| + 2|MSV r,s| < 2tH 以压倒性的概率。 如果 i 的某个部分有 |HSV r,s 我 | + |MSV r,s 我 | \(\geq\)tH 以不可忽略的概率，例如 1%，则 |HSV r,s 的概率 3−i| + |MSV r,s 3−i| \(\geq\)tH 非常低，例如，当 F = 10−18 时，为 10−16。在这种情况下， 我们不妨将较小的部分视为离线，因为没有足够的验证者 这部分生成签名来证明一个块。 让我们考虑较大的部分，即不失一般性的第一部分。虽然 |HSV r,s| < tH 在每个步骤 s 中的概率可忽略不计，当网络分区时，|HSV r,s 1 |可能是 小于 tH 的概率不可忽略。 在这种情况下，对手可能会用一些 其他不可忽略的概率，迫使二进制 BA 协议在 r 轮中进入分叉，其中包含非空块 Br 和空块 Br ϫ 都具有 TH 有效签名。25 例如，在 Coin-Fixed-To-0 步骤 s，HSV r,s 中的所有验证器 1 对位 0 和 H(Br) 进行签名，并传播它们 消息。 MSV r,s 中的所有验证者 1 还签署了 0 和 H(Br)，但保留了他们的信息。因为 |HSV r,s 1 | + |MSV r,s 1 | \(\geq\)tH，系统有足够的签名来证明Br。然而，自从 恶意验证者隐瞒签名，用户输入步骤 s + 1，这是 Coin-Fixed-To1 步骤。因为 |HSV r,s 1 | < tH 由于分区，HSV 中的验证器 r,s+1 1 没看到tH 位 0 的签名，并且它们都为位 1 签名。 MSV r,s+1 中的所有验证者 1 也做了同样的事。因为 |HSV r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH，系统有足够的签名来证明 Br ǫ。对手 然后通过释放 MSV r,s 的签名来创建分叉 1 对于 0 和 H(Br)。 因此，将有两个 Qr，由 r 轮的相应块定义。然而， 分叉不会继续，并且在第 r + 1 轮中只有两个分支之一可以生长。 Algorand 的附加说明 2. 当看到非空块 Br 和空块时 嵌段Br \(\varepsilon\) ，跟随非空的（以及由它定义的 Qr）。 事实上，通过指示用户使用协议中的非空块，如果一个大的块 PKr+1−k 中的诚实用户数量意识到在第 r+1 轮开始时有一个分叉，然后 空块将没有足够的追随者并且不会增长。假设对手设法 对诚实用户进行分区，以便一些诚实用户看到 Br（也许 Br ϫ)，有的只看到 溴 ǫ。因为对手无法判断其中哪一个将成为 Br 之后的验证者，哪一个将成为 Br 的验证者 将成为以下 Br 的验证者 \(\varepsilon\) , 诚实用户被随机划分并且每一个仍然 成为验证者（无论是关于 Br 还是关于 Br \(\varepsilon\)) 在步骤 s > 1 的概率 p。对于恶意用户来说，他们每个人可能有两次成为验证者的机会，一次是 Br 和另一个带有 Br 的 \(\varepsilon\)，每个都有概率 p 独立。 设 HSV r+1,s 1;溴 是 Br 之后的第 r+1 轮步骤 s 中的诚实验证者集合。其他符号 例如HSV r+1,s 1;Brǫ , MSV r+1,s 1;溴 和 MSV r+1,s 1;Brǫ 也有类似的定义。通过 Chernoffbound，这很容易 25无论有或没有分区，都不可能有一个带有两个非空块的分叉，除非可以忽略不计。 概率。以压倒性的概率看到， |HSV r+1,s 1;Br | + |HSV r+1,s 1;Brǫ | + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Brǫ | <2tH。 因此，两个分支不能同时拥有证明一个区块的正确签名。 r + 1 在同一步骤 s 中。此外，由于两个步骤 s 和 s' 的选择概率是 相同并且选择是独立的，也具有压倒性的概率 |HSV r+1,s 1;Br | + |MSV r+1,s 1;Br | + |HSV r+1,s′ 1;Brǫ | + |MSV r+1,s′ 1;Brǫ | <2tH， 对于任意两个步骤 s 和 s'。当 F = 10−18 时，根据并集界限，只要对手不能 对诚实用户进行长时间分区（例如 104 步，超过 55 小时，且 \(\lambda\) = 10 秒26），最多有一个分支具有高概率（例如 1−10−10）具有 tH 个正确的签名 验证第 r + 1 轮中的区块。 最后，如果物理分区创建了两个大小大致相同的部分，则 |HSV r,s 的概率 我 | + |MSV r,s 我 | \(\geq\)tH 对于每个部分 i 都很小。经过类似的分析， 即使对手设法以每个部分都有不可忽略的概率创建一个分叉 对于第 r 轮，在第 r + 1 轮中最多可以生长四个分支之一。 10.2 对抗性划分 其次，分区可能是由Adversary造成的，从而导致消息传播 一部分的诚实用户不会直接到达另一部分的诚实用户，但是 对手能够在两个部分之间转发消息。尽管如此，一旦有人发来一条消息 一部分到达另一部分的诚实用户，它将像往常一样在后者中传播。如果 对手愿意花很多钱，可以想象他可能能够破解 像这样上网并分区一段时间。 分析与上面物理分区中较大部分的分析类似（较小的部分） 部分可以被视为人口为 0）：对手也许能够创建一个分叉并 每个诚实的用户只能看到其中一个分支，但最多只能生长一个分支。 10.3 网络分区总和 虽然网络分区可能会发生，并且分区下可能会发生一轮分叉，但是 没有任何挥之不去的歧义：分叉的寿命非常短暂，实际上最多只能持续一轮。在 分区的所有部分除了最多一个之外，用户无法生成新块，因此 (a) 认识到网络中存在分区，并且 (b) 永远不要依赖会“消失”的区块。 致谢 我们首先要感谢谢尔盖 \(\cdot\) 戈尔布诺夫 (Sergey Gorbunov)，他是所引用的 Democoin 系统的合著者。 最诚挚的感谢莫里斯 \(\cdot\) 赫利希 (Maurice Herlihy)，他进行了许多富有启发性的讨论，指出了 指出流水线将提高 Algorand 的吞吐量性能，并大大提高 26请注意，只有当用户至少看到了 tH 个签名时，他才无需等待 2\(\lambda\) 时间即可完成步骤 s。 同一条消息。当没有足够的签名时，每一步将持续2\(\lambda\)时间。
对本文早期版本的阐述。非常感谢 Sergio Rajsbaum 的评论 本文的早期版本。非常感谢 Vinod Vaikuntanathan 的多次深入讨论 和见解。非常感谢 Yossi Gilad、Rotem Hamo、Georgios Vlachos 和 Nickolai Zeldovich 感谢您开始测试这些想法，并获得许多有用的评论和讨论。 Silvio Micali 谨亲自感谢 Ron Rivest 的无数讨论和指导 从事密码学研究超过 30 年，共同创作了所引用的小额支付系统 这启发了 Algorand 的验证者选择机制之一。 我们希望将这项技术提升到一个新的水平。同时，旅行和陪伴 非常有趣，我们对此非常感激。
常见问题
- Algorand 白皮书是什么？
- Algorand 白皮书题为《Algorand：为加密货币扩展拜占庭协议》，由 Jing Chen 和 Silvio Micali 于2017年发布。它提出了一种纯权益证明协议，实现即时最终确定性且不存在分叉。
- Algorand 白皮书由谁撰写，发布于何时？
- Algorand 白皮书由麻省理工学院图灵奖得主密码学家 Silvio Micali 和 Jing Chen 共同撰写，于2017年首次作为研究论文发表。
- Algorand 的核心技术创新是什么？
- Algorand 的核心创新在于使用可验证随机函数（VRF）进行秘密、随机的委员会选举。每个区块的提议者和投票委员会均通过密码学抽签选出，使得提前锁定攻击目标变得不可能。
- Algorand 的共识机制如何运作？
- Algorand 使用纯权益证明（PPoS）结合密码学抽签。对于每个区块，提议者和投票委员会根据质押权重通过 VRF 秘密选出。委员会成员在本地验证，防止针对性攻击。最终确定性约在3.3秒内实现。
- Algorand 与其他 PoS 链有何不同？
- Algorand 实现即时最终确定性——区块不可能发生分叉。与以太坊的 PoS（存在 epoch 且可能重组）不同，Algorand 的共识机制保证一旦区块被确认即为最终确定。参与无需最低质押要求。
- Algorand 的供应模型是什么？
- Algorand 的 ALGO 固定供应量为100亿枚，均在创世时铸造完毕。分发遵循加速归属时间表。参与奖励和治理奖励激励 ALGO 持有者保障网络安全并参与治理。
- Algorand 的主要使用场景有哪些？
- Algorand 用于数字资产发行、DeFi、现实世界资产代币化、央行数字货币（CBDC，如马绍尔群岛 SOV）、碳信用市场，以及需要即时最终确定性和合规性的企业应用。
- Algorand 解决了什么问题？
- Algorand 通过同时实现安全性、可扩展性和去中心化，解决了区块链不可能三角问题。其基于 VRF 的委员会选举确保去中心化，即时最终确定性提供安全保障，并行处理实现可扩展性。
- Algorand 的安全模型如何运作？
- Algorand 的安全性基于三分之二的质押由诚实参与者持有这一假设。基于 VRF 的委员会选举在投票提交之前保持秘密，使针对性攻击在计算上不可行。
- Algorand 生态系统目前的状态如何？
- Algorand 的生态系统包括 DeFi 协议（Folks Finance、Tinyman）、NFT 平台和企业合作伙伴关系。AVM（Algorand 虚拟机）支持智能合约，而状态证明（State Proofs）功能则实现了无需信任的跨链通信。