# 書誌情報 - **タイトル**: Secure and Efficient Asynchronous Broadcast Protocols - **著者**: [[Christian Cachin]], [[Klaus Kursawe]], [[Frank Petzold]], [[Victor Shoup]] - **出版年**: 2001 - **ジャーナル・カンファレンス**: 本体は[[CRYPTO]] 2001 - **Abstract**: Reliable broadcast protocols are a fundamental building block for implementing replication in fault-tolerant distributed systems. This paper addresses secure service replication in an asynchronous environment with a static set of servers, where a malicious adversary may corrupt up to a threshold of servers and controls the network. We develop a formal model using concepts from modern cryptography, present modular definitions for several broadcast problems, including reliable, atomic, and secure causal broadcast, and present protocols implementing them. Reliable broadcast is a basic primitive, also known as the Byzantine generals problem, providing agreement on a delivered message. Atomic broadcast imposes additionally a total order on all delivered messages. We present a randomized atomic broadcast protocol based on a new, efficient multi-valued asynchronous Byzantine agreement primitive with an external validity condition. Apparently, no such efficient asynchronous atomic broadcast protocol maintaining liveness and safety in the Byzantine model has appeared previously in the literature. Secure causal broadcast extends atomic broadcast by encryption to guarantee a causal order among the delivered messages. Thresholdcryptographic protocols for signatures, encryption, and coin-tossing also play an important role. # 1. Introduction - [[Bracha's Reliable Broadcast Algorithm]]は、全ての正直なノードが同じメッセージをdeliverするという性質を保証する[[Reliable Broadcast]]だが、これは[[Verifiability]]を保証していない。 - [[Verifiability]]: すでにメッセージをdeliverしたノードが、そのdeliverの証明（配信された事実と内容）を他のノードに1回の追加メッセージで証明できるという性質 ![[Pasted image 20250731175320.png]] - 段階的に、[[Multi Valued Byzantine Agreement]]、[[Total Order Broadcast|Atomic Broadcast]], [[Secure Causal Atomic Broadcast]]を提供する - このペーパーでは、external validityを保証する[[Multi Valued Byzantine Agreement]]を提案する。また、それを用いて[[Total Order Broadcast|Atomic Broadcast]]を構築する方法も示す。 - [[External Validity]]: 不正な値を決定しないようにして、決定値がアプリケーションにとって受け入れ可能な性質 - デジタル署名と追加の暗号技術を用いる - [[Multi Valued Byzantine Agreement]]を実現する方法 - 一定数の[[Binary Byzantine Agreement]]の呼び出す - cryptographic common coin protocolを使用 - $N \geq 3f + 1$ - メッセージ複雑性は$O(n^2)$ - Atomic Broadcastを用いて[[Secure Causal Atomic Broadcast]]を実装する - メッセージが配送されるまでの機密性を保証する。[[HoneyBadgerBFT]]みたい - [[Total Order Broadcast|Atomic Broadcast]]と[[Threshold Encryption]]を用いる それぞれ性質を整理すると以下のようになる |プロトコル名|合意 (Agreement)|正当性 (Validity)|全順序 (Total Order)|因果順序 (Causal Order)|メッセージの機密性 (Secrecy)|決定範囲|特徴| |---|---|---|---|---|---|---|---| |Byzantine Agreement|◯|◯（全員同じ値提案の場合）|×|×|×|単一値|単発の合意| |Multi-valued Byzantine Agreement|◯|◯（外部検証も考慮）|×|×|×|値の集合・多数値|アプリ検証付き| |Atomic Broadcast|◯|◯|◯|△（orderだがcausalではない）|×|メッセージ列全体|順序も重視| |Secure Causal Atomic Broadcast|◯|◯|◯|◯|◯|メッセージ列全体|順序＋因果＋秘匿| # 2. Model ## 2.1 Basic System Model ### Adversary model - [[Adversary model]]を整理している - 全てのパーティー（敵対者含む）は多項式時間の計算のみを実行可能。[[Bounded adversary]] - ネットワークについての仮定は設けない（[[Asynchronous Network]]）。敵の完全なコントロール下にあるとする。（正しいノード間の通信内容は書き換えられない. authenticated links. ←暗号で保証?） - メッセージを好きなだけ遅延させられるが、プロトコルの進行のためにeventual deriveryは必要 - セキュリティパラメータ$k$があり、任意の正の数$c$について、すべての$k > k_0$に対して$\epsilon(k) < \frac{1}{k^c}$となるような$k_0$が存在するとき、 $\epsilon(k)$は無視できる（[[negligible function]]）といわれる。 - $k$が大きくなれば（ここで大きさのしきい値は$k_0$）、どんなべき乗$1/k^c$よりも速くゼロに近づく関数、ということ - つまり、多項式関数よりも速くゼロに近づくということ。例えば指数関数的減衰がこれにあたる。 - t個のパーティーをcorruptさせられる - [[Static adversary]]を仮定している（[[Adaptive adversary]]にも拡張できるはず、とは書かれている） - しきい値暗号とかの仮定がそうなのでそう、ということらしい? ### Parties and Protocols - $n$個のパーティー$P_1, ..., P_n$から構成される - それぞれのパーティーは[[Probabilistic Interactive Turing Machine]]であり、多項式時間（$k$がパラメータとなる）のアルゴリズムを実行できる - メッセージを読むインターフェース、書くインターフェースがある - 初期化時に、別のエンティティであるdealerが実行するinitialization algorithmがある - 入力$k, n, t$に対して、各パーティーの初期状態を生成する - 各パーティーの初期状態には、パーティーの秘密鍵と全パーティーの公開鍵が含まれる - n-partyプロトコルに関連する公開情報を作成することもできる。Clientがうれしい - たとえば、各パーティーのアドレス、とか? - root protocolが下層のプロトコルを呼び出していく - 同時にいくつものプロトコルインスタンスが並行で呼び出される - 各インスタンスにはtag IDが付与されている - rootは敵対者・普通のアプリケーションそれぞれに呼び出される ### Communication #### Message - メッセージには、input actions, output actions, protocol messagesの3種類ある - input actions, output actions: ローカル入力・ローカルの出力をプロトコルインスタンスに突っ込む・プロトコルインスタンスの出力をローカル入力に突っ込む - 上層・下層のプロトコルに入力していくイメージ。垂直方向。 - `(ID, in, action, ...)`, `(ID, out, action, ...)` - protocol messages: 同じ層のプロトコルを実行するパーティー間でのメッセージ - `(ID, type)` (typeはin, out以外) - input action - `(ID, in, open, type)`: 一番最初のaction. $P_i$はこれを受け取ったら、インスタンスを初期化する。typeでどのようなプロトコルを初期化するか指定する。 - output action - `(ID, out, halt)`: プロトコルが終了し、呼び出し元への出力を含む。$P_i$がこのメッセージを生成したら、$P_i$がインスタンス`ID`を停止したという - すべてのメッセージは認証されている。この論文では対称鍵暗号を仮定している。 ### Quantitive Aspects #### Defining Termination - 普通、分散システムのプロトコルではLivenessの性質として[[Eventual Termination]]を置くが、今回は多項式時間でしか動作しない[[Probabilistic Interactive Turing Machine]]を仮定しているので、Eventual Terminationは保証できない。非同期ネットワークを仮定しているので、遅延も無限に大きくなるかもしれない。 - **Honestなパーティーがどれだけ通信・計算をしたのかというefficiencyを測る統計量であるProtocol Staticsを定義して、それが多項式の範囲に収まることを持って終了とするという定義に置き換える** - Protocol Statics $X(k)$: セキュリティパラメータ$K$によって決まる確率変数。正直な参加者、敵対者、ディーラーのコイントス（[[Non-deterministic Turing Machine|NTM]]なので）に依存 - 敵対者$A$, パラメータ$k$ごと定まる$\{X_A(k)\}$ - 注意: $X_A(k)$は敵対者の仕事量ではなくて、敵対者$A$（とパラメータ$k$）の場合の正直なパーティーたちの仕事量 - Uniformly Bounded: 多項式$T(k)$が存在し、敵対者$A$によらず$\Pr[X_A(k)>T(k)] \leq \epsilon(k)$ - $X_A(k)$（敵対者の仕事量）が多項式を超える確率が無視できるほど小さい - Probabilistically uniformly bounded: 全ての敵対者$A$に対して、全ての$l \geq 0$, $k \geq 0$に対して、$\Pr[X(k) > lT(k)] \leq \delta(l) + \epsilon_A(k)$ - $\delta(l)$: $l$に依存する[[negligible function]] - $l$を増やせば、$X(k) > lT(k)$となる確率が減少していく、ということっぽい - **Lemma 1**: $X$が、$T$によってProbabilistically uniformly boundedとなるマルチパーティープロトコルの統計量であるとする。全ての敵対者$A$に対して、$X_A(k)$の期待値が$cT(k)+{\epsilon'}_A$で束縛されるような定数$c$が存在する - Probabilistically uniformly boundedな統計量があれば、その期待値も多項式オーダーで押さえられる（無視できる誤差で）ということ - 証明はよくわからなかった。。。数弱ですみません - **Lemma 2**: 敵対者に依存しない任意の多項式関数$F(x_1, ..., x_f)$を固定する。$X_1, ..., X_f$がprobabilistically uniformly boundedな統計量であるとするとき、$F(X_1, ..., X_f)$もまたprobabilistically uniformly boundedな統計量となる - これによって、**probabilistically uniformly boundedな統計量をもつプロトコル同士を合成しても、同じ性質が保証される!** - 直感的には、Fが多項式演算だからそうかもな? とは思うけど、Lemma 1の証明を理解しないとこっちもわからなさそう #### Communication and Message Complexity - 任意のHonestパーティの全てのinput/outputメッセージの長さは固定の多項式で表現される上限があると仮定する - メッセージ複雑性$X_A, X_B$を持つプロトコル$A, B$があるとして、それぞれProbabilistically uniform boundedであるとする - Lemma 2より、$A$がオラクルとして$B$を呼び出すとすると、合成されたプロトコル$AB$のメッセージ複雑性$X_{AB}$もまたProbabilistically uniformly boundedとなる - Lemma 3: Probabilistically uniformly boundedなメッセージ複雑性は、プロトコルの合成のもとで閉じている ## 2.2 Byzantine Agreement - [[Total Order Broadcast|Atomic Broadcast]]を実現するための[[Byzantine Agreement]]の定義 - プロトコルは`(ID, in, propose, v)`で開始し、`(ID, out, decide, v)`で終了する - $v \in \{0, 1\}$ - Definition 2: プロトコルは、無視できる確率を除いて以下の条件を満たす場合、Byzantine Agreementを解く - **Validity**: `ID`で開始した全ての正直なパーティーが$v$をproposeした場合、`ID`で終了した正直なパーティーは`v`を決定する - **Agreement**: 1つのHonestなノードが`ID`で$v$を決定した場合、全てのHonestなパーティーは$v$を決定して終了する - **Liveness**: 全てのHonestなパーティーが`ID`を開始し、全ての関連するメッセージが届けられたら、全てのHonestなパーティーは値を決定する - **Efficiency** (Termination): 全ての`ID`について、`ID`の通信複雑性はprobabilistically uniformly boundedとなる ## 2.3 Cryptographic Primitives - デジタル署名 - private keyとmessage $m$を入力として、署名$\sigma$を生成する - [[Non-Interactive Threshold Signature]]（[[しきい値署名]]]） - に耐えられるスキームを利用する - [[Dual Threshold Signatures]]を使う - $n$個のパーティーのうち、$t$個はcorruptする可能性がある - 各パーティーは、署名に用いる秘密鍵のシェアを保有する - $t < \kappa \leq n-t$となる$\kappa$個の署名で、有効な署名が生成される - 構成 - Key Generation: セットアップ - パラメータ: $k, n, \kappa, t$ - アウトプット: 公開鍵、各パーティーの秘密鍵のシェア、ローカルverification key - Verification Keyは、署名のシェアが正当な秘密鍵シェアから生成されたものかを検証するために用いられる - Signing: 自身がもつ秘密鍵のシェアで署名のシェアを生成 - パラメータ: メッセージ、公開鍵、秘密鍵のシェア - アウトプット: 署名のシェア - Share Verification: シェアの検証 - パラメータ: メッセージ、$P_i$による署名のシェア、公開鍵、$P_i$のverification key - アウトプット: valid or not - Share Combining algorithm: 有効な署名のシェアから合成された署名を生成 - パラメータ: メッセージ、$\kappa$個の有効な署名のシェ - アウトプット: メッセージに対して有効な（合成された）署名 - Signature Verification Algorithm: 署名検証 - パラメータ: メッセージ、Share combining algorithmで生成された署名、公開鍵 - アウトプット: valid or not - $(n, t+1)$-[[Non-Interactive Threshold Cryptosystems]] - t+1個で復号できる - $(n, t+1)$-[[Threshold Coin-Tossing]] - $t+1$人の協力で構成なランダム値を生成できる（$t$人が裏切ってもOK） - $t+1$個のシェアでランダム値が決まる # 3. Broadcast Primitives ## 3.1 Reliable Broadcast ### 3.1.1 Definition - [[Reliable Broadcast]]の紹介 - `(ID.j.s, in, r-broadcast, m)`で開始し、`(ID.j.s, out, r-deliver, m)`で終了 - `ID.j`は送信者のID、`s`はシーケンス番号 - Definition 3: Reliable Broadcast: Reliable Broadcastプロトコルは、無視できる確率を除いて以下の要件を満たす - **Validity**: もし正直な参加者がメッセージ m を ID.j.s というタグ付きで r-broadcast したなら、（すべての正直な参加者がID.j.sでアクティベートされ、関連メッセージがすべて配信された場合）、全ての正直な参加者が m を r-deliver する。 - **Consistency**: ある正直な参加者が m を r-deliver し、別の正直な参加者が m′ を r-deliver した場合、 m = m′ でなければならない（同じメッセージしかデリバリーされない）。 - **Totality**: もし誰か正直な参加者が何らかのメッセージを r-deliver した場合、 （すべての正直な参加者が適切に起動され関連メッセージが配信されたなら） 全ての正直な参加者も何かしらのメッセージを r-deliver する。 - **Integrity**: すべてのID, 送信者j, シーケンス番号sについて、正直な参加者は**高々1つのメッセージしか r-deliver しない**。 また、もし全員がプロトコルに従っていれば、そのメッセージは Pj が r-broadcast したものである。 - **Efficiency**: 任意のID, 送信者j, シーケンス番号sに対し、そのインスタンスに必要な通信複雑度は一様な上限がある。 ## 3.1.2 A Protocol for Reliable Broadcast - [[Bracha's Reliable Broadcast Algorithm]]を改変したもの?紹介されていた - ハッシュを使うように最適化 ## 3.2 Verifiable Broadcast - - 通常の**reliable broadcast**では、あるノードが配信したメッセージmを他のノードがまだ配信していない場合、"このmを配信せよ"とアドバイスしても、それを「検証可能な形」で伝える処理は標準仕様には含まれていません。 - そこで、「検証可能（verifiable）」という性質を追加します。具体的には、ある正直なノードがmを配信したなら、そのノードは**1つのメッセージM**を他のノードに送るだけで、他の正直なノードが確実にmを配信できることを保証する、というものです。 - RBCのr-readyにに署名を加えるだけでOK # 3.3 Consistent Broadcast - Reliable Broadcastから、Totality（全員に配信すること）を除いたもの - 同じメッセージが配信されることは保証するけど、みんなに配信されることは保証しない - Verifiable Consistent Broadcast (VCBC) - echo broadcastベースのプロトコル+threshold signatureで実現 # 4. Validated Byzantine Agreement - Validated Byzantine Agreement: アプリケーションから与えられる外部のValidity条件を満たすByzantine Agreement - 条件 1. **External Validity**: 合意された値(v, π)は、必ずQ(v, π)を満たす。 2. **Agreement**: ある正直なノードが合意した値は他の全ての正直なノードも合意する。 3. **Liveness（活性）**: 全ての正直なノードが提案・メッセージを受信すれば合意に至る。 4. **Integrity（完全性）**: 合意された値(v, π)は、必ず誰かが提案したものである。 5. **Efficiency**: 通信量が多項式時間で抑えられる。 - **MVBA**: Multi valued byzantine agreementの流れ - VCBC（Verifiable Consistent Broadcast）で全員に配信 - n-tの検証OKな提案地を受信したらラウンドを開始 - BAする（ここでみんな合意する。これにはTotalityがある） # 5. Atomic Broadcast - 条件 - **Validity（妥当性）** t+1個以上の正直ノードのinput queueに未配信メッセージが存在すれば、そのメッセージは必ず配信される。 - **Agreement（合意性）** ある正直なノードがメッセージmを配信したなら、すべての正直ノードも同じmを配信する。 - **Total Order（全順序性）** すべての正直ノードは「受信したメッセージ列の順序」が完全に一致する。 - **Integrity（完全性）** どのメッセージも一度しか配信・受信されず、配信されたメッセージは実際に誰かが送信したもの。 - **Fairness（公平性）** t+1個の正直ノードがqueueに持つ“古いメッセージ”集合Mに対し、そのいずれか1つは多項式回数以内に配信される。 - 流れ - 各ラウンドごと、各自がキューの先頭メッセージを提案 - メッセージベクタと証明ベクタに**MVBA**で合意する（検証条件付き） # 6. Secure Causal Atomic Broadcast - Causalityを満たすメッセージ配信 - 暗号文のまま配送 - - メッセージはまず、**その内容を知られないままAtomic Broadcastされる（しっかり全会一致の順序性を担保）**。 - その後、**Atomic Broadcastによる「配信タイミング」をもって初めて、復号処理が各メンバーで開始**。 - 復号にはt+1人以上のdecryption shareが必要（閾値暗号の仕組み）。つまり、**honest majorityが「このCiphertextはいま配るべき」と合意した段階でのみ、中身が明かされる**。 - この仕組みによって「まだ前件メッセージが配信されていない段階で、それに依存する後続メッセージ内容だけが先に露呈する」という因果違反が起きません。 a fixed permutation: 組み合わせの中で決まったら越