論文翻訳: Constant Latency in Sleepy Consensus

Abstract

動的な参加のサポートはビットコインの最長チェーンプロトコルとその亜種の重要な特徴である。しかしこれらのプロトコルは基本的なトレードオフとして長いレイテンシーに悩まされている。具体的にはレイテンシーは少なくとも以下の 2 つの要因に依存する: 1) プロトコルに求められるセキュリティレベル、および 2) ネットワークの実際の参加レベル。一方、古典的な BFT プロトコルは一定のレイテンシーを達成することができるが、動的な参加の下では進歩することができない。この研究では、静的クォーラムの重要な特性を維持しつつ、古典的な BFT アプローチを静的クォーラムサイズから動的クォーラムサイズに拡張する、つまり現在の参加レベルに応じて拡張する技術を紹介する。また通信とストレージの両面で効率的な再接続ノードの回復メカニズムも提示する。我々の実験的評価では特に参加者が急激に減少した場合に、我々のプロトコルは最長チェーンプロトコルよりもはるかに低遅延であることが示された。

CCS CONCEPTS: セキュリティとプライバシー → 文選システムセキュリティ:

KEYWORDS: BFT プロトコル; ブロックチェーン; 動的参加; Sleepy モデル

Table of Contents

1. Abstract
2. 1 導入
3. 2 関連研究
4. 3 MODEL AND DEFINITIONS
   1. 3.1 Sleepy Model with Recovery
   2. 3.2 Additional Remark on the Sleepy Model
5. 4 段階的合意
   1. 4.1 ウォームアップ: ロックステップ GA
   2. 4.2 緩く同期されたクロックでの GA プロトコル
   3. 4.3 Correctness of the Protocol
6. 5 Sleepy モデルにおけるアトミックブロードキャスト
   1. 5.1 Correctness of the protocol
7. 6 ATOMIC BROADCAST WITH PRACTICAL RECOVERY
   1. 6.1 Correctness of the Protocol
8. 7 EXPERIMENTAL EVALUATION
9. 8 DISCUSSION
10. 9 CONCLUSION AND FUTURE DIRECTIONS
11. ACKNOWLEDGEMENTS
12. REFERENCES
13. 翻訳抄

1 導入

ブロックチェーン [28] の技術基盤であるビザンチン障害耐性 (Byzantine fault-tolerant) (BFT) コンセンサス [24] は恣意的に行動をする悪意のある当事者が存在しても合意に達することを可能にする。古典的な BFT コンセンサスプロトコル [10, 24, 32] は静的かつ既知の参加モデル、つまりすべての参加者が事前に知られており、すべての参加者が常にプロトコル内でアクティブであることを想定している。Nakamoto の Bitcoin プロトコル [28] の革新の中心は動的参加のサポートである。つまり参加者は事前に知られておらず、いつでも自由にシステムを離れたり参加したりできる。

Bitcoin プロトコルはランダムな proof-of-work 抽選の当選者が自分の見解で最も長いブロックのチェーンを延長するという洗練された "最長チェーン" パラダイムを発明した。その後の研究では高価な proof-of-work を回避するために Bitcoin の最長チェーンパラダイムを proof-of-stake に拡張している [4, 13, 14, 31]。当然のことながらこれらのプロトコルは Bitcoin の動的参加へのサポートも受け継いでいるが、同時に長い遅延という根本的な欠点も受け継いでいる。より具体的には遅延は少なくとも \(\Omega(\frac{\kappa \Delta}{\gamma})\) である。ここで \(\kappa\) はセキュリティパラメータ、\(\Delta\) はネットワーク遅延限界、\(\gamma \le 1\) は実際の参加者の割合 (予想される参加者のレベルと比較して) である。セキュリティパラメータへの依存は \(\kappa\)-確認規則 (\(\kappa\)-confirmation rule) によるものである。あるブロックが決定されるのは、後続のブロックが \(k\) 個生成された後である。ここで \(k\) はのく敵のセキュリティレベルに線形に依存する。最長チェーンプロトコルのブロック間隔は \(\Delta\) より著しく大きくなければならない [14, 30]。実際の参加レベルが突然低下し、合計ハッシュレートやアクティブなステークホルダーが減少するとブロック間隔はさらに長くなる (これが遅延が \(\gamma\) に反比例する理由である)。

一方、古典的な BFT プロトコルは \(O(\Delta)\) の (期待または償却された) 遅延を達成することができる [1, 19]。これにより次のような自然な疑問が生じる。

動的参加をサポートし、同時に \(O(\Delta)\) の遅延を達成する BFT コンセンサスプロトコルを設計することは可能か?

この疑問に答えるためには、コンセンサス問題と動的参加のモデルを定式化する必要がある。我々は、当事者が台帳 (線形か可能なログ) に合意する BFT アトミックブロードキャスト問題 [8, 12] に着目する。モデルに関しては Pass と Shi の Sleepy モデル [31] を出発点とする (後にモデルをさらに緩和する)。Sleepy モデルは、誠実な (honest) 参加者の数が敵対者の制御で変動しうることを仮定しており、誠実な当事者が常にビザンチン当事者よりも多いという制約がある。

最近、上記の問題は研究され 2 つの異なる角度から部分的に検討されている。Goyal ら [20] は Algorand [11, 19] に基づいて構築することで \(O(\kappa \Delta)\) 遅延を実現している。つまり彼らのプロトコルの遅延はもはや参加レベルには依存していないが、依然としてセキュリティパラメータには依存する。別の角度から見ると Prism [5]、Parallel Chains [18]、TaiJi [25] はセキュリティパラメータ \(\kappa\) への依存を取り除いたが、参加者レベルへの依存、つまり \(O(\frac{\Delta}{\gamma})\) 遅延は残っている。

この研究では、これらのトレードオフの両方を解決することによって上記の疑問に肯定的に答える。具体的には次の結果を示す:

定理 1.1 (非公式) 検証可能なランダム関数 (VRF) と公開鍵基盤 (PKI) を仮定すると、Sleepy モデルには少数の呼称を許容して安定した参加期間中に期待値 \(O(\Delta)\) の遅延を持つ BFT アトミックブロードキャストプロトコルが存在する。

以下、我々の結果と主要な技術課題について詳しく説明する。

古典的な BFT アプローチの採用. 我々のプロトコルは古典的な BFT アプローチにしたがっている。我々はまず定足数ベースの段階的合意 (GA; graded agreement) プロトコル [1, 17, 22, 27] を設計し、GA を使用してアトミックブロードキャストプロトコルを構築する。Sleepy モデルに定足数に基づくアプローチを採用することはいくつかの課題をもたらしている。第一に、古典的なプロトコルにおける定足数しきい値は当事者の総数に基づいて設定されている。参加レベルは未知であり、実行中に変動する可能性があるため、このような静的クォーラムしきい値は Sleepy モデルでは機能しない。この問題は Pass と Shi [31] も指摘している: "… プロトコルは実際にいくつのプレーヤーが目覚めているかを認識していないため、(クォーラム) しきい値をどのように設定するかが問題となる。" この技術的な問題もあって、彼らやほとんどの先行研究では最長チェーンパラダイムに従わなければならず、その長い遅延を引き継ぐ必要があった。

これは、この論文が取り組もうとしている技術的な問題でもある。我々は古典的なクォーラムベースのアプローチを Sleepy モデルに適用したいと考えている。我々の最初の自然なアイディアは、クォーラムのサイズが各当事者の "認識された" (perceived) 参加レベルに基づいて定義される動的クォーラム (dynamic quorum) を使用することである。詳しく説明すると、参加者は自身がアクティブであることを表明する。ある当事者が、現在プロトコルに参加している参加者が \(m\) と認識したとき、そのローカルのクォーラムサイズは \(\lfloor m/2 \rfloor + 1\)、つまり認識された参加者の過半数とみなす。

しかしこれには別の問題がある。古典的な BFT プロトコルでは、ある値に対する (電子署名付き) 定足数票はしばしばクォーラム証明書 (quorum certificate) と呼ばれ、これは転送可能 (transferable) である。つまりある当事者が認識したクォーラム証明書は他のすべての当事者からも常にクォーラム証明書として認識される。静的クォーラムでのこの些細な事実が動的クォーラムでは成り立たない。なぜなら認識されている参加レベルが当事者間で異なる可能性があるためである。これは、悪意のある当事者が一部の誠実な当事者に自分自身を表明するが、他の当事者には表明しないために起こりうることである。さらに悪いことに、すべての参加者が現在のクォーラム証明書を認識していたとしても、後から悪意のある参加者が自分自身を表明して認識される参加レベルを上げて必要な定足数の大きさをさらに引き上げると、参加者はクォーラム証明書を認識しなくなる可能性がある。特に、新しく参加した当事者はクォーラム証明書が過去に有効であったかを判断できない。この論文の主な技術的貢献は、動的クォーラムを用いてこの転送可能性を復元させることである。

効率的な回復. オリジナルの Sleepy モデルでは当事者がプロトコルに再参加するとスリープ中に送信されたすべてのメッセージをただちに受信することを前提としている。理論的には簡単だが、これは非現実的な仮定である。なぜなら各当事者はこれまでに送受信したすべてのメッセージを記録し再送信する必要があるためである。この問題を回避するために、再接続するノードに対して台帳の内容と最近のプロトコルメッセージ (スリープの長さに関係なく) だけを再送信する必要のある効率的な回復メカニズムを設計した。より具体的には、我々のプロトコルは当事者が古いメッセージを "忘れる" (forget) ことができる実行中のポイントを定期的に特定する。これはまたオリジナルの Sleepy モデルにおける過去のメッセージの非現実的な保存要件を回避するものである。

実験的評価. 我々のプロトコル改良を実証するために、基本的なプロトコルを実装して最長チェーンプロトコル [31] と比較評価した。我々の実験は期待される結果を示している。具体的には、最長チェーンプロトコルはセキュリティパラメータ \(\kappa\) に依存するためすべての関係者がアクティブな場合でも長い遅延にさいなまれる。また \(\gamma\) に依存するため参加レベルが急激に低下するとその遅延がさらに悪化する。これに対して我々のプロトコルは激しい変動の期間を除いて低遅延である。

利点と仮定. 我々のプロトコルのもう一つの利点と (合理的な) 追加の仮定について言及する。

我々のプロトコルは少数の故障を許容する。これは Sleepy モデルにおいて悪意のある当事者の数 \(f\) が最大 \(n/2\) であることを意味する。ここで \(n\) はプロトコル実行中のアクティブな参加者の最小数である。この \(f \lt n/2\) 条件は Sleepy モデルで必要であることが示されている [31]。これは既存の動的参加型プロトコルに対する我々のプロトコルのもう一つの利点である。それらはすべて \(\epsilon\) を正の定数としたとき \(f \le (1/2-\epsilon)n\) だけを許容している。我々のプロトコルは "安定した参加" の期間、つまり参加者があまり劇的に変換しない期間においてのみ進行する (セクション 3 で定式化する)。参加レベルが常に大きく変動する可能性は非常に低いと思われるため、これは実際には妥当な仮定であると考えている。なお、我々のプロトコルでは恣意的に乱降下する期間でも安全性を維持し、参加が安定するたびに再び進行を開始することに注意。

結果の要約. この研究の成果を要約すると以下のとおりである。

1. 期待値 \(O(\Delta)\) の遅延時間を持つ Sleepy モデルにおける BFT アトミックブロードキャストプロトコルを提示する (セクション 5)。我々のプロトコルはクォーラムベースの設計を使用して段階的合意 (GA) プロトコル (セクション 4) から構築されている。

2. Sleepy モデルを緩和し、我々のプロトコルの効率的な回復メカニズムを提示する ( セクション 6)。

3. 我々のプロトコルを実験的に評価し、最長チェーンプロトコルと比較した (セクション 7)。

2 関連研究

古典的な BFT プロトコルはすべての当事者が常に参加する静的参加を前提としている。Nakamoto の最長チェーン proof-of-work パラダイムは動的参加に対応した最初の BFT プロトコルである。最近の研究では最長チェーンパラダイムを proof-of-stake に拡張し、長い遅延の欠点を引き継いでいる [4, 13, 14, 31]。

マルチチェーンプロトコル. セキュリティパラメター \(\kappa\) への依存を取り除くためにマルチチェーンアプローチ [5, 18, 25] が研究されている。これは複数の最長チェーンを並行して実行することで、ブロック (またはトランザクション) の確定を高速化するものである。各最長チェーンのブロック間隔は総ハッシュレート (またはアクティブなステークホルダー) に依存するため、その遅延は依然としてアクティブな参加レベル \(\gamma\) に依存する。Prism と TaiJi は依然としてエネルギー効率の悪い proof-of-work アプローチを使用している。

Goyal ら. Goyal ら [20] もまた古典的なクォーラムベースのアプローチを採用し、Sleepy モデルで \(O(\kappa\Delta)\) 遅延を達成している。これは各ステップでサイズ \(\Omega(\kappa)\) の委員会をサンプリングする Algorand のアプローチを採用する [11, 19]。委員会サイズは事前に固定されているため、彼らのプロトコルでは少なくとも \(n=\Omega(\kappa)\) の参加者が常に存在する必要がある。一方、我々のプロトコルは任意の \(n \gt 0\) の参加者で動作する。具体的な遅延については、彼らのプロトコルは \(18\kappa\Delta\) であり、我々のプロトコル \(32\Delta\) と比較して (例えば低いセキュリティレベル、\(\kappa=10\) であっても) はるかに悪いものである。

未知数参加モデル. 別の最近の研究 [23] は、参加者数 \(n\) が参加者にとって未知であるが時間の経過とともに固定する未知数参加 (unknown participation) モデルにおけるビザンチン合意を研究している。彼らは認証されていない設定を考慮し、\(f \lt n/3\) 故障のみを許容する。彼らはまた動的な参加をサポートするプロトコルも提示している。しかし、彼らのモデルは依然として Sleepy モデルよりも強力である。彼らのモデルでは、誠実な当事者がオフラインになったとき、ネットワークにその不在を表明することができる。一方 Sleepy モデルでは誠実な当事者は事前に通知することなくオフラインになる。

クラッシュ障害耐性. クラッシュ障害のみが存在しビザンチン障害が存在しないなら動的参加のサポートは非常に容易になる。この場合、当事者は自分自身をネットワークに正直に表明するため、プロトコルは現在の参加レベルを正しく観測することができ、転送可能性の問題には遭遇しない。クラッシュ障害耐性を持つ動的アトミックブロードキャストに関する先行研究 [6, 7] が存在する。これらのプロトコルもクォーラムベースのアプローチを取っている。

非同期フォールバック. Sleepy モデルでは同期通信が必要である [31]。この問題を解決するために ebb-and-flow [29] と checkpointed longest-chain [33] は動的参加と分断耐性のバランスを取る方法を研究している。これらのプロトコルは最長チェーン台帳と BFT 台帳の 2 つの台帳を出力する。最長チェーン台帳は動的参加をサポートし、BFT 台帳は非同期を許容するが動的参加はサポートしない。我々のプロトコルは最長チェーン台帳を置き換えることで彼らのプロトコルの遅延を改善することができる。

3 MODEL AND DEFINITIONS

3.1 Sleepy Model with Recovery

3.2 Additional Remark on the Sleepy Model

4 段階的合意

このセクションでは、後述するアトミックブロードキャストプロトコルの重要な構成要素となる段階的合意のサブルーチンを導入する。

段階的合意 (GA). 我々の段階的合意では、各当事者はある時間 \(T\) に対して以下の保証を提供する値 \(b\) と段階ビット \(g \in \{0,1\}\) のペア \((b,g)\) の入力値 (おそらく空 \(\perp\)) と出力値 (おそらく複数¹) を持っている。

1. 一貫性 (consistency). 誠実な当事者が \((b,1)\) を出力するなら、時間 \(t \gt T\) に目覚めているすべての誠実な当事者は \((b,*)\) を出力する。

2. 完全性 (integrity). 誠実な当事者が値 \(b\) を入力しなければ、誠実な当事者は \((b,*)\) を出力しない。

3. 有効性 (validity). 最初 (時刻 0) に目覚めているすべての誠実な当事者が同じ入力値 \(b\) を持っているなら、ずっと目覚めているすべての誠実な当事者は \((b,1)\) を出力する。

我々のプロトコルが達成する有効性の特性は上記のものより少し複雑になるが、説明を簡単にするために当面は上記の単純なバージョンを使用することにしよう。

古典的なモデルでは. 古典的な静的参加モデルでは誠実な過半数、すなはち \(N=n=2f+1\) のクォーラムベースのプロトコルを次のように簡単に考え出すことができる: ラウンド 1 (時刻 0) において、各当事者は自身の入力に対してマルチキャストで票を投じる。同じ値に対する \(f+1\) 票はしばしばその値に対するクォーラム証明書 (または単純に証明書) と呼ばれる。ある当事者がラウンド 1 の終わり (時刻 \(\Delta)\) に \(b\) に対する証明を受け取った場合、その当事者は値 \(b\) を段階 (grade) 1 で出力し、他のすべての当事者にその証明書を転送する。ラウンド 2 以降 (時刻 \(t \gt \Delta\)) にその証明書を受け取った場合、段階 0 の値 \(b\) を出力する。証明書の転送可能性 (transferability) は一貫性のために重要であることに注意。\((b,1)\) を出力する誠実な当事者は証明書を転送し、すべての誠実な当事者も証明書を認識して \((b,0)\) を出力することになる。

• ¹我々の GA は複数の出力を許可しているため古典的な段階的合意よりも弱い。

4.1 ウォームアップ: ロックステップ GA

理解を助けるためにまず当事者が共通の時計にアクセスできるロックステップラウンドモデル (lockstep round model) で GA を構築する。これはすべての当事者のローカル時計がグローバル時計と等しい。ロックステッププロトコルは Figure 1 に示す通りであり、主な課題とその手法について以下で説明する。

動的クォーラム. 我々の最初の自然なアイディアはクォーラムのしきい値を "認知された" 参加レベル、つまりネットワークに自分自身を公表した当事者の数に基づいて行うことである。これにより投票ラウンドで目を覚ましている誠実な当事者の数がクォーラムのしきい値を満たすことができるようになる。具体的には、我々のプロトコルでは各当事者はラウンド 3 (すなわち投票ラウンド) において \(\langle{\sf awake},3\rangle\) をマルチキャストし、クォーラムのしきい値はこれまでに受信した \(\langle{\sf awake},3\rangle\) の数 (\(\mathcal{M}_3\) と表記) に基づくものである。

ただし、前述のとおり動的クォーラムは転送可能性を自動的には提供しない。言い換えると、一方の当事者が認識した証明書が他方の当事者からは証明書として認識されていない可能性がある。これは Sleepy モデルにおいてビザンチン当事者が特定の当事者には自分を公表するが他の当事者には公表しない、あるいは公表を保留して後から新たに参加した当事者として公表してクォーラムのしきい値を変更したときに、認識される参加レベル、ひいてはクォーラムのしきい値が当事者間で異なる可能性があるためである。

動的クォーラム証明書の転送可能性. 証明書の転送可能性を回復するには、当事者が認知した参加レベルではなく、実際の参加レベル (すはわち投票ラウンドにおいて目を覚ましている当事者の数) の過半数から票を集めることが必要である。どの当事者が認知する参加レベルも実際の参加レベルを超えることはないため、実際の参加レベルの過半数から得た票からなる証明書は、後から参加した当事者も含めて常にすべての当事者によって認識される。そこで我々の考えは、次のような手法で誠実で目覚めている当事者 (実際の参加者の過半数) 全員が投票するようにすることである。

タイムシフトクォーラム. タイムシフトクォーラム (time-shifted quorum) と呼ぶ新しい手法を導入する。ラウンド 1 では、各当事者はその入力値に対する echo メッセージと、ラウンド 1 に対する awake メッセージを送信する。各当事者は \(\mathcal{E}(b)\) で示される任意の値 \(b\) の echo 数と、\(\mathcal{M}_1\) で示されるラウンド 1 の認知している参加者レベルを追跡する。この 2 つの変数は時間とともに変化する可能性があることに注意。ラウンド 3 においてある当事者が値 \(b\) に対する過半数の echo、つまり \(\mathcal{E}(b) \gt \mathcal{M}_1/2\) を観測した場合は \(b\) に投票する。最後に、ラウンド 3 の後、時刻 \(\Delta\) までに受信した echo の数がまだ過半数に達している、つまり \(\bar{\mathcal{E}}(b) \gt \mathcal{M}_1/2\) の場合、当事者はラウンド 3 で目を覚ましていたすべての誠実な当事者が \(b\) に投票したことを確信でき (これを次で証明する) \((b,1)\) を出力することができる。

誠実な当事者 \(p\) がラウンド 3 の後 (ラウンド \(i\) とする) に \((b,1)\) を出力したとする。このとき \(p\) はラウンド 2 で目を覚ましていて、それまでに \(e_p := \bar{\mathcal{E}}(b)\) に \(\langle{\sf echo},b\rangle\) を受信した当事者数を固定したはずである。\(q\) をラウンド 3 で目を覚ましている任意の誠実な当事者とし、\(e_q := \mathcal{E}(b)\) をこれまでに \(\langle{\sf echo},b\rangle\) を受信した当事者の数とする。\(p\) はすべてのメッセージを転送し、(ラウンド 3 で目が覚めていた) \(q\) はそれらを受信するため \(e_p \le e_q\) である。ラウンド 3 までに \(q\) が \(\langle{\sf awake},1\rangle\) を受信した当事者数を \(m_q\) とし、ラウンド \(i\) までに \(p\) が \(\langle{\sf awake},1\rangle\) を受信した当事者数を \(m_p\) する。\(q\) はすべてのメッセージを転送し、(ラウンド \(i\) で目を覚ましていた) \(p\) はそれらを受信するので \(m_q \le m_p\) である。\(p\) は \((b,1)\) を出力することから \(e_p \gt m_p/2\) が成り立つ。\(e_p \le e_q\) と \(m_q \le m_p\) より \(e_q \gt m_q/2\) である。したがって、ラウンド 3 で目を覚ましているすべての誠実な当事者は \(\langle{\sf vote},2\rangle\) と \(\langle{\sf awake},3\rangle\) をマルチキャストしている。目を覚ましている誠実な当事者は故障している当事者より常に多いため、ラウンド 3 の後に目を覚ましたすべての誠実な当事者は \(\mathcal{V}(b) \gt \mathcal{M}_3/2\) (つまり証明書は転送可能) を観測し、\((b,*)\) (一貫性を保証) を出力する。

4.2 緩く同期されたクロックでの GA プロトコル

ここで Algorithm 1 の GA プロトコルの非ロックステップ版を提示する。この場合、各当事者のクロックは最大 \(\Delta\) の差で緩く同期している。

基本的な考え方はラウンドごとに \(2\Delta\) の時間を確保することである。そうすることで 2 者のローカルクロックが \(\Delta\) だけ異なっていても、ラウンド \(r\) で送信されたメッセージは受信者の認識するラウンド \(r\) の終わりまでに必ず受信者に到着する。この単純なトリックは従来のモデルでロックステッププロトコルを緩やかに同期されたクロックに変換するのに十分である。

しかし Sleepy モデルでは新たな課題が待っている。このプロトコルは特定の (ローカル) 時間 \(t\) にメッセージを送信するよう当事者に指示することに注意。もしある当事者がそのローカル時間 \(t\) で眠っているとこのメッセージは送信されないだろう。特に、これによって過半数の echo が観測されても当事者が vote の送信をスキップする可能性がある。この場合、我々のタイムシフトクォーラムの論議は破綻するだろう。

この問題は次の単純な修正で解決する: メッセージを送信するために \(\Delta\) 時間ウィンドウを当事者に与える。ロックステッププロトコルが当事者にローカル時刻 \(t\) でメッセージを送信するよう指示したとする。このとき修正後のプロトコルでは、当事者は \([t,t+\Delta]\) の間のいつでもメッセージを送信する。つまり、ある当事者がローカル時刻 \(t\) に眠っていて \(t+\Delta\) より前に目覚めると、その当事者は目が覚めたときにメッセージを送信する。この方法では、グローバル時間 \(t+\Delta\) に目を覚ましているすべての正直な当事者は、その時間にローカルクロックが \([t,t+\Delta]\) の中にあるはずなのでメッセージを送信するだろう。

1 行目と 8 行目は上記のトリックを適用している。例えば投票ステップではある当事者はそのローカル時間 \([4\Delta,5\Delta]\) の間に投票する。したがってグローバル時刻 \(5\Delta\) に目を覚ましているすべての誠実な当事者は (条件を満たせば) 投票することになり、これだけで転送可能な証明書を形成するのに十分である。

一般的な変換のポテンシャル. Pass と Shi [31] は、Sleepy モデルにおけるロックステップから緩く同期したクロックへの汎用的な変換について非常に簡単に (証明なしで) 言及したことに注目する。しかしかられ羅上記の問題をどのように扱うかについて記述していないため、彼らの変換を我々のプロトコルに適用する方法は不明である。また仮に彼らの返還を適用する方法があったとしても、彼らの返還ではすべてのラウンドが \(3\Delta\) となるため我々の解決方法のほうがより効率的である。我々の技術が一般的な変換を構成するかは独立した関心ごとである。現時点では我々の特定のプロトコルで機能することを証明しているだけである。

メッセージの競合. Figure 1 では各当事者にすべての echo メッセージを転送するようにした。これは故障した当事者が無限に異なる値の echo を送信できるため、無制限の通信が発生する可能性がある。この問題を回避するために、メッセージ間の競合 (conflict) を定義する。具体的には \(\langle{\sf echo},b\rangle_p\) は任意の \(b' \ne b\) に対して \(\langle{\sf echo},b'\rangle_p\) と競合する。同様に \(\langle{\sf vote},b\rangle_p\) は \(\langle{\sf vote},b'\rangle\) と競合する。我々のプロトコルは他のメッセージと競合しない場合にのみメッセージを送信する (24 行目)。また他のメッセージと競合しない場合にのみ当事者は \(\langle{\sf vote},b'\rangle\) を \(\bar{\mathcal{E}}(b)\) にカウントすることに注意 (7 行目)。これにより、カウントされたすべての echo が常にほかのすべての当事者に転送されるようになり、これはタイムシフトクォーラムにとって重要である。

4.3 Correctness of the Protocol

5 Sleepy モデルにおけるアトミックブロードキャスト

このセクションでは、前節で紹介した段階的合意プロトコルに基づくアトミックブロードキャストプロトコル (Algorithm 2) の構築を紹介する。

ビューベースの構築. 我々のプロトコルは標準的な view-by-view パラダイムに従っている。各ビューは \(37\Delta\) 時間続く。つまり、ビュー \(v\) はローカル時刻 \(37(v-1)\Delta\) に開始しローカル時刻 \(37v\Delta\) に終了する。(最初のビューは view 1 である。) 簡略化のためビューに対する相対時間を使用する。つまりビュー \(v\) のローカル時刻 \(\tau\) とはローカル時刻 \(37(v-1)\Delta+\tau\) を意味する。各ビューはおおよそ 2 つのフェーズで構成される。第一フェーズ (1-4 行目) では各当事者が VRF 抽選とともに提案する。第二フェーズ (5-23 行目) では選出されたリーダーからの提案が一連の段階的合意 (GA) インスタンスを通じて決定される。

ブロックと連鎖. 値の集合 (当事者の入力) はブロック \(b\) にまとめられる (ブロック内の値は全順序付けされている)。ログはブロックのリスト \(\Lambda = [b_1,b_2,\ldots]\) で自然に表現される。各ログ \(\Lambda\) は次のように定義されるハッシュ \(\bar{H}(\Lambda)\) によって一意に識別される。空のログ \([]\) はハッシュ値 \(\perp\) を持つと定義される。ログ \(\Lambda' = \Lambda \ || \ b\) のハッシュは \(\bar{H}(\Lambda') = H(\bar{H}(\Lambda) \ || \ b)\) と再帰的に定義される。

提案とリーダー選出. 提案 (4 行目) は新しいブロック \(b\) と (前のビューですでに拡散されている) ログ \(\Lambda=[b_1,b_2,\ldots]\) のハッシュ \(h\) で構成される。これは新しいログ \(\Lambda \ || \ b\) を提案する。この提案には現在のビュー番号での VRF 評価も含まれており、これはリーダー選出のくじの役割を果たす。第二フェーズの開始時 (6 行目)、各当事者はこのビューのリーダーを最大の VRF を持つ (現在のビューの) 提案を受け取った当事者であると見なす。ここで敵対者は提案を送信する前に誠実な当事者の VRF 評価を推測することはできない。したがって、敵対者は選出されたリーダーに対して標的型攻撃を開始することはできない (つまりリーダーを破損させたりスリープ状態にすることはできない)。少なくとも 1/2 の確率で故障している当事者より目を覚ましている誠実な当事者の方が多いため、すべての誠実な当事者は同じ誠実な当事者をリーダーと認識する。

決定フェーズ. しかし一定の確率でリーダー選挙は失敗することがある。つまり誠実な当事者が異なるリーダーと提案を選出することがある。そこで第二フェーズ (5-23 行目) ではローカルで選出されたリーダーの提案を決定できるかどうかを判断する。選出されたリーダー \(L\) の提案は \(1 \le i \le 5\) の \({\rm GA}_{v,i}\) で表される一連の 5 つの段階的合意を通じて処理される。ペア \((b,h)\) で表される提案されたログはハッシュ \(H(h||b)\) を持ち、これが最初の GA (つまり 10 行目の \({\rm GA}_{v,1}\)）に入力される。その後、段階 1 の (\(1 \le i \le 4\) に対する) \({\rm GA}_{v,i}\) の出力が入力として \({\rm GA}_{v,i+1}\) に渡される (14-15 行目)。直感的には、決定フェーズをさらに 4 つのサブフェーズ "公証 (notary) - 立候補 (candidate) - ロック (lock) - 決定 (decide)" に分離することでこのプロトコルの安全性と活性性を維持することができる。この構造は HotStuff [34] の ("key-lock-commit" [2, 3] とも呼ばれる) 3 つのフェーズにヒントを得たものである。後者の 3 つのフェーズは HotStuff の3 つのフェーズと本質的に同じ役割を持つ。我々は、古典的なプロトコルでは簡単だが Sleepy モデルでは非自明となる "公証" という別のフェーズを持っている。以下、各フェーズについて詳しく説明する。

公証. ログ (またはそのハッシュ \(h\)) は \({\rm GA}_{v,2}\) がそのハッシュ (段階 0 または 1) を出力するときに初めて提案されたビュー \(v\) で公証される (notarized)。これは、公証された値 \(h\) とそのビュー \(v\) のペアの notarized セットによって維持される (24-25 行目)。直感的には、あるログの公証は、そのログがビュー内で一意であること、すなわちビュー内で公証された他のログが存在しないことを確認し、ビュー内の安全性を保障している。このため、段階 0 または 1 の出力 \(h' \ne h\) が他にない場合にのみ、最初の \({\rm GA}_{v,1}\) の出力 \(h\) が次の \({\rm GA}_{v,2}\) に渡される (14 行目)。我々の GA の定義では複数の出力を許可していることは以前に述べた。しかし、\({\rm GA}_{v,1}\) の一貫性により誠実な当事者は一貫性のない出力を検出し、同じビューで生成された福栖の公証を防ぐことができる。

5.1 Correctness of the protocol

6 ATOMIC BROADCAST WITH PRACTICAL RECOVERY

6.1 Correctness of the Protocol

7 EXPERIMENTAL EVALUATION

8 DISCUSSION

9 CONCLUSION AND FUTURE DIRECTIONS

ACKNOWLEDGEMENTS

We thank our shepherd Qiang Tang and the anonymous reviewers at ACM CCS 2022 for their helpful feedback.We also thank Joachim Neu, Ertem Nusret Tas, and David Tse, for valuable discussions. We also thank Keisuke Hasegawa and Masashi Sato for helping us with the experiment. This work is supported in part by an NSF CAREER award.

REFERENCES

1. Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren. 2019. Synchronous Byzantine Agreement wit h Expected \(O(1)\) Rounds, Expected \(O(n^2)\) Communication, and Optimal Resilience. In Financial Cryptography and Data Security (FC). Springer, 320–334.
2. Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. 2021. Reaching consensus for asynchronous distributed key generation. arXiv preprint arXiv:2102.09041 (2021).
3. Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. 2019. Asymptotically optimal validated asynchronous byzantine agreement. In ACM Symposium on Principles of Distributed Computing (PODC). 337–346.
4. Christian Badertscher, Peter Gaži, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas. 2018. Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. In ACM SIGSAC Conference on Computer and Communications Security (CCS). 913–930.
5. Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019. Prism: Deconstructing the blockchain to approach physical limits. In ACM SIGSAC Conference on Computer and Communications Security (CCS). 585–602.
6. Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch. 2002. Early-delivery dynamic atomic broadcast. In International Symposium on Distributed Computing (DISC). Springer, 1–16.
7. Kenneth PBirmanandRobbert Van Renesse. 1993. Reliable distributed computing with the Isis toolkit. IEEE Computer Society Press.
8. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to reliable and secure distributed programming. Springer Science & Business Media.
9. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference (CRYPTO). Springer, 524–541.
10. Miguel Castro, Barbara Liskov, et al. 1999. Practical Byzantine fault tolerance. In 3rd Symposium on Operating Systems Design and Implementation (OSDI). USENIX, 173–186.
11. Jing Chen and Silvio Micali. 2016. Algorand. arXiv preprint arXiv:1607.01341 (2016).
12. Flaviu Cristian, Houtan Aghili, Ray Strong, and Danny Dolev. 1995. Atomic broadcast: From simple message diffusion to Byzantine agreement. Information and Computation 118, 1 (1995), 158–179.
13. Phil Daian, Rafael Pass, and Elaine Shi. 2019. Snow white: Robustly reconfigurable consensus and applications to provably secure proof of stake. In Financial Cryptography and Data Security (FC). Springer, 23–41.
14. Bernardo David, Peter Gaži, Aggelos Kiayias, and Alexander Russell. 2018. Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Springer, 66–98.
15. Danny Dolev and H. Raymond Strong. 1983. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12, 4 (1983), 656–666.
16. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (1988), 288–323.
17. Paul Feldman and Silvio Micali. 1988. Optimal algorithms for Byzantine agreement. In 20th Annual ACM Symposium on Theory of Computing (STOC). 148–161.
18. Matthias Fitzi, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2018. Parallel Chains: Improving Throughput and Latency of Blockchain Protocols via Parallel Composition. IACR Cryptology ePrint Archive, Report 2018/1119 (2018).
19. Yossi Gilad,Rotem Hemo,Silvio Micali,Georgios Vlachos,and Nickolai Zeldovich. 2017. Algorand: Scaling byzantine agreements for cryptocurrencies. In 26th Symposium on Operating Systems Principles (SOSP). 51–68.
20. Vipul Goyal, Hanjun Li, and Justin Raizes. 2021. Instant Block Confirmation in the Sleepy Model. In Financial Cryptography and Data Security (FC).
21. Yue Guo, Rafael Pass, and Elaine Shi. 2019. Synchronous, with a chance of partition tolerance. In Annual International Cryptology Conference (CRYPTO). Springer, 499–529.
22. Jonathan Katz and Chiu-Yuen Koo. 2009. On expected constant-round protocols for byzantine agreement. J. Comput. System Sci. 75, 2 (2009), 91–112.
23. Pankaj Khanchandani and Roger Wattenhofer. 2021. Byzantine Agreement with Unknown Participants and Failures. arXiv preprint arXiv:2102.10442 (2021).
24. Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4, 3 (1982), 382–401.
25. Songze Li and David Tse. 2020. TaiJi: Longest Chain Availability with BFT Fast Confirmation. arXiv preprint arXiv:2011.11097 (2020).
26. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016. The honey badger of BFT protocols. In ACM SIGSAC Conference on Computer and Communications Security (CCS). 31–42.
27. Atsuki Momose and Ling Ren. 2021. Optimal Communication Complexity of Authenticated Byzantine Agreement. In International Symposium on Distributed Computing (DISC).
28. Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008).
29. Joachim Neu, Ertem Nusret Tas, and David Tse. 2021. Ebb-and-flow protocols: A resolution of the availability-finality dilemma. In IEEE Symposium on Security and Privacy (S&P). IEEE, 446–465.
30. Rafael Pass, Lior Seeman, and Abhi Shelat. 2017. Analysis of the blockchain protocol in asynchronous networks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Springer, 643–673.
31. Rafael Pass and Elaine Shi. 2017. The sleepy model of consensus. In Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Springer, 380–409.
32. Marshall Pease, Robert Shostak, and Leslie Lamport. 1980. Reaching agreement in the presence of faults. Journal of the ACM (JACM) 27, 2 (1980), 228–234.
33. Suryanarayana Sankagiri, Xuechao Wang, Sreeram Kannan, and Pramod Viswanath. 2020. The Checkpointed Longest Chain: User-dependent Adaptivity and Finality. arXiv preprint arXiv:2010.13711 (2020).
34. Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. Hotstuff: Bft consensus with linearity and responsiveness. In ACM Symposium on Principles of Distributed Computing (PODC). ACM, 347–356.

翻訳抄

検証可能な乱数を用いて委員会選出を行う Sleepy コンセンサスで動的な参加を可能にする 2022 年の論文。

1. Atuki Momose and Ling Ren. 2022. Constant Latency in Sleepy Consensus, Cryptology ePrint Archive, Paper 2022/404