拜占庭协议：从相关工作到最优协议解析

### 拜占庭协议：从相关工作到最优协议解析 在分布式系统中，拜占庭协议是保障系统一致性和可靠性的关键技术。本文将深入探讨拜占庭协议的相关工作、模型定义、核心范式以及具体协议实现，为你揭示其背后的技术原理和应用价值。 #### 1. 相关工作概述 拜占庭协议的轮复杂度研究领域成果丰硕，不同协议在效率上因多种因素而异，如设置假设、腐败阈值和输入域等。下面聚焦于二进制拜占庭协议（Binary BA）的轮复杂度，这类协议可通过标准技术扩展到多值拜占庭协议（Multivalued BA），不过在不同腐败阈值下会增加额外的轮数。 部分协议还借助理想的一轮抛硬币协议，该协议无误差和偏差，可通过可信的唯一阈值签名设置来实现。以下是一些重要的相关工作： - **Feldman 和 Micali（1997）**：针对 t < n/3 情况给出无条件协议，期望轮数为常数。在 O(r) 轮内达成协议，失败概率为 2^(-r)。假设使用理想硬币，对于二进制输入，在 2r 轮内以相同概率达成协议。 - **Fitzi 和 Garay（2003）**：在特定数论假设和公钥基础设施（PKI）下，为 t < n/2 情况给出首个期望常数轮协议。 - **Katz 和 Koo（2006）**：改进上述结果，协议仅依赖 PKI。 - **Abraham 等人（2019）**：在阈值签名假设下，扩展上述成果，实现首个期望常数轮 BA，通信复杂度为 O(n^2)，线性提升了通信效率。这些协议可在 O(r) 轮内以 2^(-r) 的失败概率达成协议。 - **Micali 和 Vaikuntanathan（2017）**：假设使用理想硬币，对于二进制输入，在 2r 轮内以 2^(-r) 的失败概率达成协议，提升了具体效率。 - **Fitzi、Liu - Zhang 和 Loss（2021）**：推广 Feldman 和 Micali 的迭代范式，在假设使用理想硬币的情况下，改进了固定轮协议的具体效率。对于二进制输入，t < n/3 时需 r + 1 轮，t < n/2 时需 3/2r 轮，失败概率为 2^(-r)。 此外，还有一些工作专注于在不诚实多数情况下实现广播的轮高效解决方案。同时，Karlin 和 Yao 以及 Chor、Merritt 和 Shmoys 证明了在腐败数量 t 与参与方数量 n 呈线性关系时，任何 r 轮随机协议的失败概率至少为 (c·r)^(-r)，Attiya 和 Censor - Hillel 将此界限扩展到异步模型。 协议的组合问题也备受关注，包括并行组合、顺序组合和通用组合等方面的分析。Cohen 等人给出了具有概率终止的拜占庭协议的下界。 #### 2. 模型和定义 考虑一个包含 n 个参与方 P = {P1, P2, ..., Pn} 的系统，下面详细介绍其通信和对手模型、密码学原语以及协议相关的基本定义。 ##### 2.1 通信和对手模型 参与方通过点对点认证信道组成的完整网络进行通信，网络是同步的，诚实方发送的消息能在已知时间内送达。协议通常以轮为单位描述。 存在一个自适应对手，可在协议执行的任何时刻腐败最多 t 个参与方，使其任意偏离协议。对手是强抢先的，能在每轮观察诚实方发送的消息后再选择自己的消息，甚至在诚实方发送消息时立即腐败该方并替换消息。 ##### 2.2 密码学原语 - **公钥基础设施（PKI）**：所有参与方都可访问 PKI，持有相同的公钥向量 (pk1, pk2, ..., pkn)，每个诚实方 Pi 持有与 pki 对应的私钥 ski。使用私钥 sk 对值 v 进行签名计算为 σ ← Signsk(v)，使用公钥 pk 验证签名为 Verpk(v, σ)。为简化证明，假设签名是完美不可伪造的，在实际应用中，结果除可忽略的失败概率外仍然成立。 - **抛硬币协议（Coin - Flip）**：参与方可以使用理想的抛硬币协议 CoinFlip，该协议能为参与方提供一个共同的均匀随机值（范围取决于具体协议）。在首个诚实方查询 CoinFlip 之前，该值对对手而言是均匀分布的。此原语可通过可信的唯一阈值签名设置实现。 ##### 2.3 协议基本定义 - **拜占庭协议（Byzantine Agreement）**：协议 Π 中，每个参与方 Pi 初始持有输入值 xi ∈ {0, 1}，并在生成输出 yi 时终止。若满足以下属性，则该协议是抗 t 腐败的拜占庭协议： - **有效性（Validity）**：若所有诚实方输入为 x，则每个诚实方输出 yi = x。 - **一致性（Consistency）**：任意两个诚实方 Pi 和 Pj 输出相同的值 yi = yj。 - **近似普查协议（Proxcensus）**：作为拜占庭协议的一种松弛形式，输出值通常带有一个等级，指示协议达成的一致程度。这里考虑输入为二进制的简化版本： - **定义**：设 ℓ ≥ 2 为自然数，协议 Π 中每个参与方 Pi 初始持有输入位 xi ∈ {0, 1}，并在生成输出 yi ∈ {0, 1, ..., ℓ - 1} 时终止。若满足以下属性，则该协议是具有 ℓ 个槽的二进制近似普查协议，抗 t 腐败： - **有效性**：若所有诚实方输入 xi = 0（或 xi = 1），则每个诚实方输出 yi = 0（或 yi = ℓ - 1）。 - **一致性**：任意两个诚实方 Pi 和 Pj 的输出位于两个连续的槽内，即存在一个值 v ∈ {0, 1, ..., ℓ - 2}，使得每个诚实方 Pi 输出 yi ∈ {v, v + 1}。 - **条件分级广播协议（Conditional Graded Broadcast）**：是广播的一种松弛版本，允许发送方将值分发给 n 个接收方，每个接收方带有一个置信等级。在协议中使用了一种稍作修改的版本，每个参与方 Pi 有一个额外的位 bi，直观地表示 Pi 是否会在协议期间发送消息。 - **定义**：协议 Π 中，指定的发送方 Ps 初始持有值 x，每个参与方 Pi 持有位 bi，每个参与方 Pi 在生成输出对 (yi, gi) 且 gi ∈ {0, 1, 2} 时终止。若满足以下属性，则该协议是抗 t 腐败的条件分级广播协议： - **条件有效性（Conditional Validity）**：若发送方 Ps 诚实且每个诚实方的 bi = 1，则每个诚实方输出 (x, 2)。 - **条件分级一致性（Conditional Graded Consistency）**：对于任意两个诚实方 Pi 和 Pj，|gi - gj| ≤ 1；若 gi > 0 且 gj > 0，则 yi = yj。 - **无诚实方参与（No Honest Participation）**：若所有诚实方输入 bi = 0，则每个诚实方输出 (⊥, 0)。 假设存在公钥基础设施，条件分级广播协议在 t < n/2 腐败情况下可在 3 轮内实现。 #### 3. 扩展 - 提取范式 由 Fitzi、Liu - Zhang 和 Loss 引入的扩展 - 提取范式包含三个步骤，下面详细介绍其具体内容和协议实现。 ##### 3.1 范式步骤 - **扩展步骤**：参与方共同执行一个 ℓ 槽的二进制近似普查协议 Proxℓ，每个参与方 Pi 以输入位 xi 运行该协议，得到输出 zi = Proxℓ(xi) ∈ {0, 1, ..., ℓ - 1}，此时诚实方的输出满足近似普查协议的有效性和一致性。 - **多值抛硬币步骤**：参与方获得一个硬币值 ci ∈ {0, 1, ..., ℓ - 2}。 - **切割步骤**：根据硬币值 ci 和近似普查协议的输出 zi 计算最终输出位 yi，若 zi ≤ ci，则 yi = 0，否则 yi = 1。 假设硬币是理想的（无误差和偏差），即返回一个在 {0, 1, ..., ℓ - 2} 范围内的共同均匀随机值，那么参与方达成一致的概率为 1 - 1/(ℓ - 1)。具体分析如下： - 若所有诚实方输入 xi = 0，经过第一步后近似普查协议的输出 zi = 0，无论硬币值是多少，最终输出 yi = 0。同理，若输入 xi = 1，则 zi = ℓ - 1，由于硬币的最大值为 ℓ - 2，所以最终输出 yi = 1。 - 由于诚实方在调用 Proxℓ 后位于两个相邻的槽内，所以只有一个可能的硬币值（在 ℓ - 1 个值中）会导致参与方有不同的输入。 ##### 3.2 协议描述 ```plaintext Protoc ```