(57)【要約】  取引がブロックに編成されている取引システムにおいて、主体に先行ブロックから量Ｑを決定させ、主体にＱ及び主体に一意に関連付けられたストリングＳを計算すべく秘密鍵を使用させ、主体にＳ自身、Ｓの機能、及び／又はＳのハッシュ値で量ＴをＳから計算させ、主体にＴが所与の特性を有しているか否かを判定させ、Ｔが所与の特性を有している場合、主体にＢrにデジタル署名させてＳ及びＢrのデジタル署名されたバージョンを利用可能にさせることにより、一連の先行ブロックＢ0，Ｂ1，．．．，Ｂr-1に対して、有効な取引の新規ブロックＢrが構築され、主体はＢrのデジタル署名に応じて変化する乱数値に基づいて選択されている。【選択図】図２
2020536473.tif 000002
【特許請求の範囲】
【請求項１】
取引がブロックに編成されている取引システムにおいて、一連の先行ブロックＢ0，Ｂ1，．．．，Ｂr-1に対して主体に有効な取引の新規ブロックＢrを構築させる方法であって、
前記主体に、前記先行ブロックから量Ｑを決定させるステップと、
前記主体に、Ｑ及び前記主体に一意に関連付けられたストリングＳを計算すべく秘密鍵を使用させるステップと、
前記主体に、Ｓ自身、Ｓの機能、及び／又はＳのハッシュ値のうち少なくとも１つで量ＴをＳから計算させるステップと、
前記主体に、Ｔが所与の特性を有しているか否かを判定させるステップと、
Ｔが所与の特性を有している場合、前記主体にＢrにデジタル署名させてＳ及びＢrのデジタル署名されたバージョンを利用可能にさせるステップとを含み、前記主体はＢrのデジタル署名に応じて変化する乱数値に基づいて選択されている方法。
【請求項２】
前記秘密鍵は、前記主体の公開鍵に対応する秘密署名鍵であって、Ｓは前記主体によるＱのデジタル署名である、請求項１に記載の方法。
【請求項３】
Ｔは数であって、Ｔが所与の数ｐより小さければ前記特性を満たす、請求項１に記載の方法。
【請求項４】
ＳはＳをＢrから導出可能にすることにより利用可能になる、請求項２に記載の方法。
【請求項５】
各ユーザーは前記取引システムに残高を有し、ｐは各ユーザーの前記残高に応じてユーザー毎に異なっている、請求項２に記載の方法。
【請求項６】
前記乱数値は前記主体のデジタル署名のハッシュである、請求項１に記載の方法。
【請求項７】
前記主体は前記取引システムの最小数の主体がＢrにデジタル署名できるように選択された閾値を前記乱数値が下回る場合に選択される、請求項６に記載の方法。
【請求項８】
一連の先行ブロックＢ0，Ｂ1，．．．，Ｂr-1に関して新規ブロックＢrを検証すべくブロックチェーンシステムのユーザーの部分集合を選択する方法であって、
前記ユーザーの少なくとも一部に、他の情報と共に前記新規ブロックＢrにデジタル署名させてデジタル署名を生成させるステップと、
前記ユーザーの少なくとも一部に、前記デジタル署名のハッシュ値を決定させるステップと、
前記ユーザーの少なくとも一部に、前記ハッシュ値を所定の閾値と比較させるステップと、
前記ユーザーの部分集合に、前記ユーザーの部分集合毎に、所定の閾値を下回る前記ハッシュ値に応答して前記新規ブロックＢrを検証すべく前記デジタル署名を利用可能にさせるステップとを含む方法。
【請求項９】
前記ユーザーのうち特定の１人が前記新規ブロックＢrにデジタル署名するのは、前記ユーザーの前記特定の１人が前記新規ブロックＢrに設定された情報を検証する場合のみである、請求項８に記載の方法。
【請求項１０】
前記所定の値は前記ユーザーの部分集合が前記ユーザーの最少人数を含むように選択されている、請求項８に記載の方法。
【請求項１１】
前記ブロックチェーンシステムは取引がブロックに編成された取引システムで用いられる、請求項８に記載の方法。
【請求項１２】
ブロックチェーンにおいて、少なくとも１個のデータストリングｍの証明を行う方法であって、
ユーザーの集合Ｓに、ｍが所与の少なくとも何らかの特性を有しているか否かを検証させるステップと、
ユーザーに、前記ユーザーによるｍの検証に応答してｍにデジタル署名させるステップと、
前記ユーザーにｍの信任された署名であるｍの前記デジタル署名を利用可能にさせるステップとを含む方法。
【請求項１３】
ｍの前記デジタル署名が信任されるのは前記デジタル署名が所与の追加的な特性を満たす場合である、請求項１２に記載の方法。
【請求項１４】
ｍの前記デジタル署名が前記所与の追加的な特性を満たすのは、前記デジタル署名のハッシュが所与の目標数よりも小さい場合である、請求項１３に記載の方法。
【請求項１５】
前記データストリングｍはｍの少なくとも所与の数の信任された署名により証明される、請求項１２に記載の方法。
【請求項１６】
請求項１〜１５のいずれか一項に記載の方法を実装する実行可能コードを含む、非一時的コンピュータ可読媒体で提供されるコンピュータソフトウェア。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、電子取引の分野、特に電子取引用の取引ブロックのシーケンスの内容の安全確保の分野に関する。
【背景技術】
【０００２】
ブロックチェーンは、ブロックの拡張可能なシーケンス１、２，．．．，を含み、各ブロックは多くの取引、１つ前のブロックのハッシュ、及び他のデータ、例えばブロックの数、時間情報等からなる。ブロックチェーンの有用な特性として、システムの全ユーザーが最終的に全ブロックの内容を知り、誰もブロックの内容又は順序を変更することができず、有効な取引は全て最終的にチェーン内のあるブロックに入れられる。
【０００３】
ユーザーはデジタル署名することができ、従って各ユーザーは少なくとも１個の公開鍵及び対応する秘密鍵を所有している。ブロックチェーンでは一般に、公開鍵は知られているが、所有するユーザーは必ずしも知られていない。従って、公開鍵と所有者を同一視することができる。
【０００４】
ブロックチェーンは、メッセージ（例：ブロック、取引等）を拡散することで機能する。典型的に、但し非排他的に、メッセージはピアツーピア方式で、又はリレーを介して雑談することにより拡散される。
【０００５】
いくつかのブロックチェーンシステムでは、システム内の充分多数のユーザーのデジタル署名によりブロックを証明する必要がある。いくつかのシステムにおいて、このような証明するユーザーは固定されたユーザーの集合に属する。他のいくつかのシステムにおいて、ユーザーは動的に変化する集合に属する。これが好適であるのは、特に集合が動的であるだけでなく予測不可能である場合、動的に変化する集合を敵対者が唆すのがより困難になるからである。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
検証可能だが予測不可能な方法でユーザーの集合を選択する特に効果的な仕方は、Ａｌｇｏｒａｎｄが採用している暗号抽選である。ここで、ユーザーｉは、入力ｓ及びｒ、並びに他の入力その他データ（例：ある整数ｋが与えられて、ユーザーがブロックｒの少なくともｋブロック前でシステムに関与した事実）を用いて、自身の秘密鍵を介して、ｉが実行する計算の結果に基づいて、ブロック番号ｒを生成する間に、あるステップｓで行動する権限を与えられたユーザーの集合に属している。例えば、ｉの計算は、そのような入力にｉのデジタル署名
【数１】
2020536473.tif 000003
を行い、
【数２】
2020536473.tif 000004
をハッシングし、及びハッシュが所与の目標値ｔより小さいか否かを調べることが必要であろう。（実際、他の任意のストリングと同様に、ハッシュされた値は、何らかの標準的な方法で数値として解釈することができる。）そうであれば、
【数３】
2020536473.tif 000005
はブロックｒに関するステップ５に対するｉの信任値であると定義される。このような信任値は、ｉが実際に（好適には署名付き）メッセージ
【数４】
2020536473.tif 000006
すなわちラウンドｒのステップｓ、すなわちブロックｒの生成を意図した処理で本人のメッセージを生成する権限があることを誰に対しても証明する。実際、ｉのデジタル署名は誰でも確認することができ、且つ誰でも所与の値をハッシュすることができ、次いで、結果が実際に所与の数よりも小さい（又は等しい）か否かを確認することができる。従って、ｉは
【数５】
2020536473.tif 000007
と
【数６】
2020536473.tif 000008
の両方を拡散することができる。Ａｌｇｏｒａｎｄでは、信任値
【数７】
2020536473.tif 000009
は長期鍵に対して計算されるのに対し、
【数８】
2020536473.tif 000010
の署名は、ｉがメッセージ
【数９】
2020536473.tif 000011
１個だけを認証するのに用いる短期キーを用いて計算する。実際、正直なｉは、
【数１０】
2020536473.tif 000012
の署名に用いたならば直ちにそのような短期秘密鍵を消去する。
【０００７】
使用後に消去される短期キーを用いることで、
【数１１】
2020536473.tif 000013
を拡散させた後で、ｉを唆す敵対者がラウンドｒのステップｓに関する異なるメッセージに署名することをｉに強制するのを防止する。本システムは、しかし、他人への保証に適したプロシージャ、すなわちユーザーｉのラウンドｒのステップｓへの自身のメッセージ認証専用の短期キーに依存している。このような保証には追加的なデータの保存及び／又は送信が必要な場合がある。従って、この要件が軽減できれば好ましい。特に、ブロックチェーンのブロックの証明に好ましい。
【０００８】
従って中央当局を信用する必要がなく、且つ公知の分散型アプローチの非効率性及び危険性から免れた公開台帳及び電子資金システムを提供することが望まれる。
【課題を解決するための手段】
【０００９】
本明細書に記述するシステムによれば、取引がブロックに編成されている取引システムにおいて、主体に先行ブロックから量Ｑを決定させ、主体にＱ及び主体に一意に関連付けられたストリングＳを計算すべく秘密鍵を使用させ、主体にＳ自身、Ｓの機能、及び／又はＳのハッシュ値で量ＴをＳから計算させ、主体にＴが所与の特性を有しているか否かを判定させ、Ｔが所与の特性を有している場合、主体にＢrにデジタル署名させてＳ及びＢrのデジタル署名されたバージョンを利用可能にさせることにより、一連の先行ブロックＢ0，Ｂ1，．．．，Ｂr-1に対して、有効な取引の新規ブロックＢrが構築され、主体はＢrのデジタル署名に応じて変化する乱数値に基づいて選択されている。秘密鍵は、主体の公開鍵に対応する秘密署名鍵であってよく、Ｓは主体によるＱのデジタル署名である。Ｔは数であってよく、Ｔが所与の数ｐより小さければ特性を満たす。Ｓは、ＳをＢrから導出可能にすることにより利用可能になり得る。各ユーザーは取引システムに残高を有していてよく、ｐは各ユーザーの残高に応じてユーザー毎に異なっていてよい。乱数値は、主体のデジタル署名のハッシュであってよい。主体は、取引システムの最小数の主体がＢrにデジタル署名できるように選択された閾値を乱数値が下回る場合に選択されていてよい。
【００１０】
本明細書に記述するシステムによれば更に、一連の先行ブロックＢ0，Ｂ1，．．．，Ｂr-1に関して新規ブロックＢrを検証すべくブロックチェーンシステムのユーザーの部分集合を選択するステップは、ユーザーの少なくとも一部に他の情報と共に新規ブロックＢrにデジタル署名させてデジタル署名を生成させるステップと、ユーザーの少なくとも一部にデジタル署名のハッシュ値を決定させるステップと、ユーザーの少なくとも一部にハッシュ値を所定の閾値と比較させるステップと、ユーザーの部分集合に、ユーザーの部分集合毎に、所定の閾値を下回るハッシュ値に応答して新規ブロックＢrを検証すべくデジタル署名を利用可能にさせるステップとを含んでいる。ユーザーの特定の１人が新規ブロックＢrにデジタル署名できるのは、ユーザーの特定の１人が新規ブロックＢrに設定された情報を検証する場合のみである。所定の値は、ユーザーの部分集合がユーザーの最少人数を含むように選択されてよい。ブロックチェーンシステムは、取引がブロックに編成された取引システムで用いることができる。
【００１１】
本明細書に記述するシステムによれば更に、ブロックチェーンは、ユーザーの集合Ｓに、ｍが所与の少なくとも何らかの特性を有しているか否かを検証させ、ユーザーに、ユーザーによるｍの検証に応答して、ｍにデジタル署名させ、ユーザーに、ｍの信任された署名であるｍのデジタル署名を利用可能にさせることにより、少なくとも１個のデータストリングｍの証明を行う。ｍのデジタル署名が信任できるのは、デジタル署名が所与の追加的な特性を満たす場合である。ｍのデジタル署名が所与の追加的な特性を満たすことができるのは、デジタル署名のハッシュが所与の目標数よりも小さい場合である。データストリングｍは、ｍの少なくとも所与の数の信任された署名により証明されてよい。
【００１２】
本明細書に記述するシステムによれば更に、非一時的コンピュータ可読媒体で提供されるコンピュータソフトウェアは、本明細書に記述する任意のステップを実行する実行可能コードを含んでいる。
【００１３】
本発明は、ブロックを証明するための短期鍵を省略する。典型的に、最初に新規ブロックが用意され（例：少なくとも一部のユーザーにより提案又は賛同される）、次いで証明される。ブロックＢがどのように用意されるかは不可知であり、１個又は複数のステップで用意されても、短期鍵を用いてもよい。しかし、短期鍵に依存することなく証明したい。ブロックＢの証明は、特定の有益な特性がブロックに当てはまることを証明する。典型的な主特性は、ブロックＢの用意に関与していないか又は視認しなかったユーザーであっても、ユーザーが、Ｂがブロックチェーンに追加されたこと、又はＢがブロックチェーンのｒ番目のブロックであることをも証明できるようにすることである。別の有益な特性（往々にして仕上げと称する）は、ソフト分岐に起因して、たとえブロックチェーンプロトコルが実行される通信ネットワークが分割されていたとしても、Ｂがブロックチェーンから消失しないことを証明する。
【００１４】
ブロックＢが任意の仕方で、且つ任意のステップ数で用意されていると仮定する。ブロックが適切に用意されていることを認識するには時間及び労力、並びに様々な断片的証拠の検証を要する。Ｂの証明は、有効な信任値を有する所与の数のユーザーのデジタル署名を含んでいる。このようなＢの証明は、そのような署名を行ったユーザーがＢの用意に関与又は視認したことを証明する。少なくとも、証明のデジタル署名の１個が正直なユーザーによりなされていれば、ユーザーは、Ｂが適切に用意されていることを確認している。
【００１５】
本発明のシステムにおいて、Ｂが適切に用意された証拠を見た複数のユーザーｉ（全ユーザーでもよい）がデジタル的にＢに署名する。（脚注１：量Ｑにデジタル署名することは、Ｑのハッシュされたバージョンにデジタル署名すること、他のデータでＱにデジタル署名することを含んでいる。本明細書において、デジタル署名とは、各メッセージｍに対して、各ユーザーが、公開鍵の選択の仕方に依らずｍの単一の署名を有していると仮定する。）これらの署名は（短期とは逆に）長期鍵に関連するものであってよい。このような署名は、しかし、所与の特性Ｐを満たすならばＢの証明に役立つ。好適な実施形態において、Ｂに対するｉのデジタル署名ＳＩＧi（Ｂ）は、（ａ）自身のハッシュ（数と解釈された）が所与の目標ｔよりも小さく、好適にはｉがＢの少なくともｋブロック前でブロックチェーンに関与したならば所与の特性を有している。全員がｉのＢに対するデジタル署名を検証して、そのハッシュを計算し、その結果が実際にｔより大きくないことを検証できる点に注意されたい。また、ｉがブロックチェーンに関与したこと、従って当人が少なくともｋブロック前にブロックチェーンに関与したことを誰でも検証することができる。このようなＳＩＧi（Ｂ）は、Ｂに対するｉの信任された署名と同様に、専用の信任値であると考えられる。従って、本明のシステムにおいて、信任値は、ｒ番目のブロックの生成における所与のステップｓではなく、特定のブロックに紐付けられる。従って、ユーザーｉは所与のブロックＢに対する信任値を有している、別のブロックＢ’に対しては有していない場合がある。対照的に、例えばＡｌｇｏｒａｎｄでは、ラウンドｒのステップｓへの適当な信任値を有するユーザーは、ステップ及びラウンドで自身が望むあらゆるものに署名できる。ブロック証明は従って、Ｂに対する所与の数ｎの信任された署名を含んでいる。ｎより多くの信任された署名が存在する場合、ブロックＢは１個よりも多くの証明を有していてよい点に注意されたい。
【００１６】
本発明のシステムの効率性は、適当なＳＩＧi（Ｂ）が、ｉがＢを証明し、且つｉがＢを証明する資格を有していることを証明する事実から導かれる。従来のシステムにおいて、ｉは最初に、自身がＢを証明することに同意するラウンドｒのステップｓへの信任値を取得し、次いで別個の署名によりＢを証明する必要がある。従って１個ではなく、少なくとも２個の署名が必要であり、Ｂの信任値の一部として保存及び／又は送信することも必要であろう。また、Ｂに対するｉの署名が短期であれば、使用した短期鍵が、ｉがステップｓ及びラウンドｒのためだけに必要とした鍵であったことの何らかの証明も必要であろう。
【００１７】
システムのセキュリティは、目標ｔ及びブロックの証明に充分な数ｎの署名の適切な選択から導かれる。例えば、ｐをシステム内で悪意のあるユーザーの最大割合とする。典型的に、悪意のあるユーザーは極めて少数、例えばｐ＜１／３である。次いで、ｔ及びｎを、充分に高い確率で、（ａ）任意の可能なブロック値Ｂ’に対して、Ｂ’の証明を形成するために正直なユーザーのｎ個以上の信任された署名が存在し、（ｂ）Ｂ’の任意の証明において少なくとも１個の信任された署名が正直なユーザーに属しているように選択することができる。
【００１８】
また、ブロックＢを証明すべく信任される正直なユーザーの集合は、敵対者には相手が誰であるかを予測できず、且つ相手がブロックを証明する前に相手を唆すことが不可能な程度に充分無作為である。一方、正直なユーザーｉがブロックＢを証明して、ＳＩＧi（Ｂ）を拡散した後では、敵対者はｉを唆す利点がない。実際、ＳＩＧi（Ｂ）は既にネットワーク全体にわたりウイルス的に拡散されていて、敵対者はこの拡散過程を止めることができない。第２に、ｉを唆した後で、敵対者が異なるブロックＢ’にデジタル署名することをｉに強制したならば、ＳＩＧi（Ｂ’）はｔよりも小さいハッシュを有しておらず、敵対者は、かなりの確率でＢ’のｎ個のデジタル署名を見つけるために、ある割合ｐ以上のユーザーを唆す必要があろう。
【００１９】
本発明のシステムの一部として、ユーザーｉは、Ｂに対する１個（又はゼロ個の）の信任値だけでなく、重み付きの信任値（本質的に多くの票に紐付けられた信任値）を有していてよい。実際、Ｂに対するｉの信任値の重みは、ｉがシステムに保有する金額に依存してよい。実際、全てのユーザーに対して１個のｔを有するのではなく、各ユーザーｉは、ｉの金額が多いほど高い自身の目標ｔiを有していてよい。Ｂに対するｉの信任値の重みは、ｔiに関するＳＩＧi（Ｂ）のハッシュがどの程度小さいかに依存していてよい。簡潔のため、但し非限定的に、Ｂに対する重みｍの信任値を有するユーザーｉを、各々がＢに対する（重み−１）信任値を有するｍ人のユーザーとして扱う本システムの説明を続けることにする。
【００２０】
以上、充分な数の信任されたＢの署名を介してブロックＢを証明することを議論してきた。しかしより一般的には、本発明のシステムは、少なくとも所与のメッセージｍが、充分な数の信任されたｍのデジタル署名により証明されているブロックチェーンに適用できる。そのようなメッセージｍは、ブロックではなく、より一般的なデータストリングであってよい。従って、ｍのこのような証明は、ブロックに適用可能であるか又は望ましいものとは異なる特性がｍに適用できることを保証することができる。例えば、但し一切の限定を意図することなく、システム内のユーザーの集合Ｓの充分な割合のユーザーにより、又はＳの少なくとも１人の正直なユーザーによりｍが承認されたという特性である。実際、ｍの信任された署名を有するＳ内のユーザーが、Ｓ内のユーザーの充分に無作為に選択されたサンプルを形成していてよい。従って、ｍの充分な数の信任された署名が生成されたという事実は、充分な高い確率で、Ｓ内のユーザーの所与の割合、又はＳ内の少なくとも１人の正直なユーザーがｍを承認することを示している。
【００２１】
以下に、従来のＡｌｇｏｒａｎｄシステムを手短に想起した後で、Ａｌｇｏｒａｎｄに基づいて、一切の限定無しに、好適な実施形態の一例を示す。
【００２２】
本明細書に記述するシステムの実施形態について、各図面内の描画を参照しながらより詳細に説明する。
【図面の簡単な説明】
【００２３】
【図１】本明細書に記述するシステムの一実施形態によるネットワーク及びコンピューティングステーションの模式図である。
【図２】Ａｌｇｏｒａｎｄシステムの第１ステップの模式的及び概念的要約であり、取引の新規ブロックを提案している。
【図３】Ａｌｇｏｒａｎｄシステム内の新規ブロックの合意書及び証明の模式的且つ概念的要約である。
【図４】マークル木及びそのノードの１個に含まれる値への認証経路を示す模式図である。
【図５】ブロック木に構築された第１ブロックに対応するマークル木を示す模式図である。
【発明を実施するための形態】
【００２４】
本明細書に記述するシステムは、取引情報を検証及び／又は拡散する計算の実行に単独で責任を負う主体が存在しないように取引の検証及び拡散を配信する機構を提供する。逆に、関与する各々の主体が、検証可能且つ信頼できる仕方で取引を拡散すべく計算の実行を分担する。
【実施例】
【００２５】
図１を参照するに、インターネット等のデータネットワーク２４に接続されたコンピューティングワークステーション２２ａ〜２２ｃを図示している。ワークステーション２２ａ〜２２ｃは、本明細書の他の箇所でより詳細に記述しているように、分散取引拡散及び検証を提供すべくネットワーク２４を介して互いに通信する。本システムは、ワークステーション２２ａ〜２２ｃが互いに通信可能である前提で、本明細書に記述する機能を適用可能な任意の数のワークステーションを収容することができる。ワークステーション２２ａ〜２２ｃは各々、本明細書の他の箇所でより詳細に記述しているように、本システムの他のワークステーションの全てに取引を拡散し、且つ取引を検証すべく独立して処理を実行することができる。
【００２６】
図２に、Ａｌｇｏｒａｎｄシステムにおけるラウンドｒの第１ステップを模式的且つ概念的に要約しており、選択された数人のユーザーの各々が、ｒ番目のブロックに対して自身の候補を提案する。具体的には、ステップはシステム内のユーザーａ，．．．，ｚが独立に秘密の暗号抽選処理を受けることから始まり、処理はどのユーザーがブロックを提案すべく選択されたかを決定し、各々の選択されたユーザーが、ブロックを生成する資格が自身に与えられたことを証明する信任値を非公開に計算する。図２の例において、ユーザーｂ、ｄ、及びｈだけがブロックを提案すべく選択されており、各人の計算された信任値は
【数１２】
2020536473.tif 000014
である。各々の選択されたユーザーｉは、自身の提案されたブロック
【数１３】
2020536473.tif 000015
をアセンブルし、これに短期署名（すなわち、後述するように短期鍵を用いてデジタル署名）して、自身の信任値と共にネットワークに拡散する。ラウンドのリーダーは、信任値が最も小さいハッシュを有する選択されたユーザーである。図は、リーダーがユーザーｄであることを示す。従って、自身の提案されたブロック
【数１４】
2020536473.tif 000016
は、バイナリ合意プロトコルへの入力として与えられるものである。
【００２７】
図３に、提案されたブロックを公式なｒ番目のブロック（Ｂr）として合意及び証明するＡｌｇｏｒａｎｄの方法を模式的且つ概念的に要約している。Ａｌｇｏｒａｎｄの第１ステップが新規ブロックの提案を含んでいるため、処理は第２ステップから始まる。ステップは実際、Ａｌｇｏｒａｎｄの好適なビザンチン合意プロトコル（ＢＡ*）の第１ステップに一致している。プロトコルの各ステップは、秘密の暗号抽選（図に示さず）により無作為に選択されたプレーヤーの異なる「委員会」により実行される。従って、各ステップを実行すべく選択されたユーザーは完全に異なっていてよい。ＢＡ*のステップ数は変化し得る。図３は、７ステップすなわちＡｌｇｏｒａｎｄのステップ２〜Ａｌｇｏｒａｎｄのステップ８を含むＢＡ*の実行を示している。図３の例において、ステップ２を実行すべく選択されたユーザーはａ、ｅ、及びｑである。各ユーザーｉε文字∈｛ａ，ｅ，ｑ｝は、ｉが実際にＡｌｇｏｒａｎｄのラウンドｒのステップ２でメッセージを送る資格を有していることを証明する自身の信任値
【数１５】
2020536473.tif 000017
及びステップに適した自身のメッセージ
【数１６】
2020536473.tif 000018
をネットワークに拡散する。ステップ３〜７は図示していない。最後のステップ８において、図は、対応する選択されたユーザーｂ、ｆ、及びｘがラウンドｒの公式ブロックとしてＢrの合意に達しており、ブロックＢrの自身の短期署名（これらの署名は共にＢrを証明する）及びステップ８で行動する資格を有していることを証明する自身の信任値を拡散する様子を示す。
【００２８】
図４に、マークル木及びその認証経路の１個を模式的に示す。具体的には、図４Ａは、深さ３の完全マークル木を示す。各ノードｘは値ｖxを保存し、ｘは長さが３以下のバイナリストリングで表される。ｘの長さが２以下ならばｖx＝Ｈ（ｖx0，ｖx1）である。図４ａのマークル木に対して、図４Ｂは値ｖ010の認証経路を示す。
【００２９】
図５に、深さ３の完全２進木内に構築されたブロック木に構築された最初の８ブロックに対応するマークル木を模式的に示す。図５ｉにおいて、整数で印が付けられたノードがマークル木Ｔiに属する。ｉ（又は太字のｉ）と印が付けられたノードの内容は一時的（又は永続的）である。
【００３０】
本明細書における記述は支払い取引に注目しており、且つ本明細書におけるシステムを資金プラットフォームとして記述している。当業者には、本明細書に記述するシステムがあらゆる種類の取引を同様に扱うことができることが理解されよう。
【００３１】
本明細書に記述するシステムは、極めて柔軟な設計がなされており、各種の、但し関連した仕方で実装することができる。本システムの柔軟性をその一般的な設計で可能な２つの実施形態を詳述することにより示す。当業者にはそこから他のあらゆる種類の実装を導く仕方が理解できよう。
【００３２】
本発明の理解を容易にすべく、且つ様々な部分の内部相互参照に可能にすべく、本発明を、番号と見出しを付けた節に編成して提示する。第１節は、詳細な実施形態の両方に共通である。
【００３３】
１．序
資金は益々仮想化されている。今日米ドルの約８０％が台帳エントリとしてのみ存在すると推定されている。他の金融ツールもこれに追随している。
【００３４】
起こり得るあらゆるサイバー攻撃に耐性を有していて普遍的に信用できる中心的主体を頼ることができる理想的な世界において、資金及び他の金融取引は専ら電子的に行われ得る。残念ながら、発明者らはこのような世界に住んでいない。従って、ビットコイン等の分散化された暗号通貨、及びイーサリアム等の「スマート契約」システムが提案されている。これらのシステムの中心に、支払い及び契約等の広範な一連の取引を改ざん防止された仕方で確実に記録する共有台帳がある。このような改ざん防止を保証するために選択される技術としてブロックチェーンがある。ブロックチェーンは、暗号通貨、金融アプリケーション、及びモノのインターネット等のアプリケーションの背後にある。ブロックチェーンに基づいて台帳を管理するいくつかの技術、すなわちプルーフオブワーク、プルーフオブステーク、実用的ビザンチンフォールトトレランス、又はこれらの何らかの組み合わせが提案されている。
【００３５】
しかし現時点では、台帳は管理が非効率的な場合がある。例えば、ビットコインのプルーフオブワークアプローチは膨大な量の計算を必要とし、無駄が多く、且つスケーリング性に欠ける。また、実際に極めて少数の者の権力を集中させてしまう。
【００３６】
従って、現在の分散された実装の非効率性及び弱点を排除した、信用でき且つ不可侵な権威者により実行される集中化されたシステムの利便性及び効率を実現する公開台帳を実装する新たな方法を推奨したい。発明者のアプローチをＡｌｇｏｒａｎｄと称するが、その理由は、これまで構築された台帳に基づいて、アルゴリズム的無作為性を利用して有効な取引の次のブロックの構築を担当する検証者の集合を選択するからである。当然ながら、このような選択が不正操作に耐性を有し、且つ最後の瞬間まで予測不可能であることが証明されているだけでなく、究極的に普遍的に透明性を有していることを保証する。
【００３７】
Ａｌｇｏｒａｎｄのアプローチは、原理的にも実態的にも（ビットコインにおける「採掘者」と「一般ユーザー」のような）異なる階級のユーザーを設定しない、という意味で完全に民主的である。Ａｌｇｏｒａｎｄでは「全ての権力は全てのユーザーの集合に存在する」。
【００３８】
Ａｌｇｏｒａｎｄの顕著な特性の１つは、取引履歴が極めて小さい確率（例：１兆分の１、すなわち１０-18程度）で分岐し得ることである。Ａｌｇｏｒａｎｄはまた、何らかの法的及び政治的な懸念に対応することができる。
【００３９】
Ａｌｇｏｒａｎｄアプローチは、ブロックチェーンに、より一般的にはブロックの改ざん防止シーケンスを生成する任意の方法に適用できる。実際、我々は別途注目されてよいブロックチェーンの代替策として、より効率的な新たな方法を提案した。
【００４０】
１．１  ビットコインの仮定及び技術的課題
ビットコインは、極めて巧妙なシステムであって、後続する膨大な研究を惹起した。それにもかかわらず問題を含んでいる。ビットコインと同様にプルーフオブワークに基づく全ての暗号通貨が基本的に実際に共有している、基礎をなす仮定及び技術的課題を以下に要約する。
【００４１】
この要約に際して、ビットコインではユーザーがデジタル署名スキームの複数の公開鍵を有していること、資金が公開鍵に紐付けられていること、及び支払いがある公開鍵から別の公開鍵へある金額を送金するデジタル署名であることを想起すれば充分である。本質的に、ビットコインは、各々が複数の支払いを含むブロックの連鎖Ｂ1，Ｂ2，．．．における全ての処理対象の支払いが、任意の順序でなされるＢ1の全ての支払い、続いて任意の順序でなされるＢ2の支払い等が一連の有効な支払いを構成するように編成する。各ブロックは平均１０分毎に生成される。
【００４２】
上述のブロックシーケンスがチェーンをなしている理由は、何らかの変化が、たとえ単一ブロックで生じても、全ての後続ブロックに拡散して、支払い履歴に何らかの変更が加えられたならば認識し易くするために構築されるためである。（これは以下で述べるように、各ブロックに１つ前のブロックの暗号ハッシュを含めることにより実現される。）このようなブロック構造をブロックチェーンと称する。
【００４３】
仮定：計算能力の正直な多数派  ビットコインでは、いかなる悪意のある主体（又は協調した悪意のある主体の連合）もブロック生成に割かれた大部分の計算能力を制御することはないと仮定している。このような主体は実際、ブロックチェーンを改ざんし、従って望みのままに支払い履歴を書き直すことできる。特に、支払い
【数１７】
2020536473.tif 000019
に、支払いの対価を得させ、次いで
【数１８】
2020536473.tif 000020
の痕跡を全て「消去」させることができる。
【００４４】
技術的課題１：計算の無駄  ブロック生成へのビットコインのプルーフオブワークアプローチは格別な計算量を必要とする。現在、システム内には数十万個の公開鍵しかない状況で、上位５００の最も強力なスーパーコンピュータは、ビットコインプレーヤーが必要とするトータルの計算能力の僅か１２．８％パーセントしか集中することができない。より多くのユーザーがシステムに参加したならば、この計算量は大幅に増大しよう。
【００４５】
技術的課題２：権力の集中  今日、必要とされる計算量が過大であるため、ユーザーが通常のデスクトップ（携帯電話は論外）を用いて新規ブロックの生成を試みたならば資金を失うと予想される。実際、通常のコンピュータで新規ブロックを計算する場合、計算への電力供給に必要な電気の予想コストは期待される報酬を上回る。（「新規ブロックのマイニング」以外は何もしない）特別に構築されたコンピュータのプールを用いるだけで、新規ブロックを生成することにより利益が得られると期待する人もいよう。従って今日、事実上、２つの分断されたユーザーのクラス、すなわち支払いだけを行う通常のユーザー、及び新規ブロックの探索だけに特化したマイニングプールがある。
【００４６】
従って、最近、ブロック生成用の全計算能力がたった５つのプールに割かれているのは驚くべきことではない。このような状況において、大部分の計算能力が正直であるという仮定は信用できなくなる。
【００４７】
技術的課題３：曖昧さ  ビットコインにおいて、ブロックチェーンは必ずしも一意ではない。実際、ビットコインの最後の部分はしばしば分岐する。すなわちブロックチェーンは、例えば、あるユーザーによれば
【数１９】
2020536473.tif 000021
、また別のユーザーによれば
【数２０】
2020536473.tif 000022
であってよい。数ブロックがチェーンに追加された後にのみ、最初のｋ＋３ブロックが全てのユーザーにとって同じであると、合理的に確信することができる。従って、チェーンの最終ブロックに含まれる支払いを直ちに信頼することはできない。ブロックチェーン内でブロックが充分に深く、従って充分に安定しているか否かを待機及び確認することがより賢明であろう。
【００４８】
これとは別に、ビットコインに関して司法及び通貨政策面での懸念も持ち上がっている。
（脚注２：ビットコイン支払いが提供する（疑似）匿名性が資金洗浄及び／又は犯罪者或いはテロリスト組織への融資に悪用され得る。原理的に完全な匿名性を提供する従来の紙幣又は金の延べ棒も同じ問題を生起するが、これらの通貨は物理的に資金の送金が遅くなるため、司法当局によりある程度の監視が可能になる。
「現金を印刷する」能力は国家の極めて基本的な権力の１つである。従って原理的に、独立に流通する通貨を大量に使用することでこの権力が削減され得る。しかし現在、ビットコインは政府の金融政策を脅かすものからは程遠く、スケーラビリティ問題のため永久にそうならないであろう。）
【００４９】
１．２  Ａｌｇｏｒａｎｄの簡潔な説明
設定  Ａｌｇｏｒａｎｄは極めて厳しい設定で機能する。要するに、
（ａ）許可不要及び許可が必要な環境。Ａｌｇｏｒａｎｄは全く許可不要な環境でも効率的に機能し、任意の多くのユーザーが一切審査や許可を受けることなく随時システムに参加することができる。無論、Ａｌｇｏｒａｎｄは許可が必要な環境では更によく機能する。
（ｂ）極めて敵対的な環境。Ａｌｇｏｒａｎｄは、以下を行い得る極めて強力な敵対者に対抗できる。
（１）許可不要な環境においてシステムの資金の２／３が正直なユーザーのものである前提で、狙ったユーザーを好きなときに唆すことができる。（許可が必要な環境において、資金に依らず、ユーザーの２／３が正直であれば充分である。）
（２）唆したユーザー全員を完全に支配して完璧に協調させ、
（３）全てのメッセージの発信をスケジューリングする
正直なユーザーが送った各メッセージｍが、ｍの大きさだけに依存する時間λm内に全ての（又は、充分に多くの）正直なユーザーに届く。
【００５０】
主要な特性  強力な敵対者が存在するにもかかわらず、Ａｌｇｏｒａｎｄでは、
・必要な計算量が最小である。本質的に、システム内にユーザーが何人いたとしても、１５００人のユーザーの各々は、最大でも数秒の計算を実行すれば済む。
・新規ブロックが素早く生成され、事実上ブロックチェーンから決して消滅しない。すなわち、Ａｌｇｏｒａｎｄのブロックチェーンは、無視できる（すなわち、１兆分の１すなわち１０-18未満の）確率でしか分岐しないであろう。従ってユーザーは、ブロックが出現したならば直ちに、新規ブロックに含まれる支払いを信頼することができる。
・全ての権限はユーザー自身にある。Ａｌｇｏｒａｎｄは真に分散取引システムである。特に、どの処理が認識されるかを支配できる（ビットコインの「マイナー」のような）外部の主体が存在しない。
【００５１】
Ａｌｇｏｒａｎｄの技術
１．新規且つ高速なビザンチン合意プロトコル。Ａｌｇｏｒａｎｄは、本発明の暗号、メッセージ通過、バイナリビザンチン合意（ＢΑ）プロトコル（ＢＡ*）を介して新規ブロックを生成する。プロトコルＢＡ*は、（以下に述べる）いくつかの追加的な特性を満たすだけでなく、極めて高速でもある。要約すれば、そのバイナリ入力バージョンは、プレーヤーｉが他の全てのプレーヤーに単一のメッセージｍiを送る３ステップのループを含んでいる。完全且つ同期化されたネットワークで実行され、プレーヤーの２／３以上が正直であり、各ループの後で１／３超の確率でプロトコルは合意に達する。（プロトコルＢＡ*が一切弱められることなくビザンチン合意本来の定義を満たすことを強調する。）
【００５２】
Ａｌｇｏｒａｎｄは、異なる通信モデルにおいて、バイナリＢＡプロトコルを利用して各新規ブロックで合意に達する。合意されたブロックは次いで、所定数の適当な検証者のデジタル署名を介して証明され、ネットワークを介して拡散される。
【００５３】
２．秘密暗号抽選。極めて高速ではあるが、プロトコルＢＡ*は数百万ユーザーにより実行されたならば更に速度が向上する。従って、Ａｌｇｏｒａｎｄは、ＢＡ*のプレーヤーを全ユーザーの集合よりもはるかに小さい部分集合となるように選択する。異なる種類の権力の集中課題を避けるため、各新規ブロックＢrは、選択された検証者ＳＶrの別の集合によるＢＡ*の新たな実行を介して構築されて合意に達する。原則として、このような集合の選択は、直接Ｂrを選択するのと同程度に難しいかもしれない。秘密の暗号抽選と称する新たなアプローチによりこの潜在的な問題に対処する。抽選は、資格のある個人の大きい集合から無作為に役員を選択する仕方である。（抽選は、例えばアテネ、フィレンツェ、及びベニス共和国により数世紀にわたり実施されてきた。現代の司法制度において、しばしば無作為な選択を用いて陪審員を選択している。ランダムサンプリングは選挙においても提唱されてきた。）分散システムでは無論、各々の検証者集合ＳＶrのメンバーを無作為に選択するのに必要な無作為なコインを選択することは問題を含んでいる。従って、全ユーザーの母集団から、自動的（すなわち、メッセージ交換を一切必要としない）且つ無作為であることが保証された仕方で、各々の検証者集合を選択するために暗号を利用する。同様に、新規ブロックＢrを提案する役割を担うユーザーすなわちリーダー、及びリーダーが提案したブロックで合意に達する役割を担う検証者集合ＳＶrを選択する。本発明のシステムは、１つ前のブロックの内容から導出可能であって、たとえ極めて強い敵対者が存在しても不正操作が不可能な何らかの情報Ｑr-1を利用する。
【００５４】
３．量（シード）Ｑr。次の検証者集合及び新規ブロックＢrを構築する役割を担うリーダーを自動的に決定するためにブロックチェーンの最終ブロックＢr-1を用いる。このアプローチの問題は、前のラウンドで僅かに異なる支払いを選択するだけで、強力な敵対者が次のリーダーを相当程度支配可能になることである。敵対者がシステム内のプレーヤー／資金の１／１０００を制御するだけで、確実に全てのリーダーを悪意のある者にすることができる。（直観的説明の節４．１参照）この問題は、全てのプルーフオブステークアプローチの中心にあり、知られる限り、現時点まで満足に解決されていない。
【００５５】
この問題に対処すべく、強力な敵対者にとって予測不可能なだけでなく、影響を及ぼし得ないことが確実な、注意深く定義された別々の量Ｑrを意図的に構築して常に更新する。ｒ番目のブロックの生成に特別の役割を果たす全てのユーザーをＡｌｇｏｒａｎｄが秘密の暗号抽選を介して選択するＱrから来ているため、Ｑrをｒ番目のシードと称することにする。シードＱrはブロックＢr-1から導出可能である。
【００５６】
４．秘密の信任値。検証者集合及び新規ブロック（Ｂr）を構築する役割を担うリーダーを選択するには、現在の最終ブロックＢr-1を無作為且つ曖昧さ無しに用いることは充分でない。Ｂrを生成する前にＢr-1が既知でなければならないため、Ｂr-1から導出可能な影響を及ぼさない最後の量Ｑr-1もまた既知でなければならない。従って、検証者及びブロックＢｒを計算する役割を担うリーダーもそうである。従って、強力な敵対者は直ちに、検証者及びリーダーが証明するブロックを完全に制御すべくＢrに関する何らかの議論に加わる前に全員を唆す恐れがある。
【００５７】
この問題を防止すべく、リーダーは（実際は検証者も）自身の役割に非公開に知るが、実際にその役割を担う誰に対しても証明力を有する適切な信任値を計算することができる。ユーザーが、自分が次ブロックのリーダーであることを非公開に理解したならば最初に、自身の提案された新規ブロックを非公開にアセンブルし、次いで自身の信任値と共に（証明可能なように）拡散する。このように、敵対者は次ブロックのリーダーが誰であるかが直ちに分かり、且つ敵対者が直ちにリーダーを唆すことができるが、敵対者が新規ブロックの選択に影響を及ぼすには遅すぎる。実際、敵対者は、強力な政府であってもウィキリークスがウイルス的に拡散したメッセージを瓶に戻すことができないのと同様に、リーダーのメッセージを「呼び戻す」ことができない。
【００５８】
以下で分かるように、リーダー自身を含め、リーダーが１人であることも、誰がリーダーであるかを皆が確実に知っていることも保証できない。しかしＡｌｇｏｒａｎｄでは曖昧ではない進展が保証される。
【００５９】
５．プレーヤーの代替可能性。リーダーは、新規ブロックを提案した後は仕事が終わったので、「退場」した方がよい（さもなければ敵対者に唆される。）しかしＳＶrの検証者にとって、ものごとはさほど単純でない。実際、充分に多くの署名を有する新規ブロックＢrを証明する役割を担う検証者は最初に、リーダーが提案したビザンチン合意を実行しなければならない。問題は、如何に効率的であってもＢＡ*は複数のステップを要し、且つ２／３を超えるプレーヤーが正直であることを要することである。これが問題である理由は、効率性のため、ＢＡ*のプレーヤー集合は、全ユーザーの集合から無作為に選択した小さい集合ＳＶrを含んでいるからである。従って、強力な敵対者は、全ユーザーの１／３を唆すことはできないものの、ＳＶrの全メンバーを確実に唆すことができる！
【００６０】
幸い、ピアツーピア方式でメッセージを拡散することにより実行されるプロトコルＢＡ*がプレーヤーを代替可能である。この新たな要件は、たとえ各々のステップが全く新たな、無作為且つ独立に選択されたプレーヤーの集合により実行されるとしても、プロトコルが正当且つ効率的にコンセンサスに達することを意味する。従って、数百万ユーザーがいる状況で、ＢＡ*のステップに関連付けられたプレーヤーの各々の小さい集合と次の集合との共通集合は空である。
【００６１】
加えて、ＢＡ*の異なるステップのプレーヤーの集合は恐らく、全く異なる基数を有していよう。更に、各集合のメンバーは次のプレーヤー集合が誰であるかを知らず、内部状態を非公開に渡すことはない。
【００６２】
代替可能プレーヤー特性は実際、想像し得る能動的且つ極めて強力な敵対者を打ち負かすために必須である。代替可能プレーヤープロトコルが、多くのコンテキスト及びアプリケーションで必須であることが分かるものと考える。特に、代替可能プレーヤーは、全プレーヤーの小さい割合でさえ唆すことができ、より小さいサブプロトコルで全プレーヤーを唆すことが困難でない能動的な敵対者と共にプレーヤーのより大きな世界に埋め込まれた小さいサブプロトコルを安全に実行するために必須である。
【００６３】
追加的特性／技術：怠慢な正直さ  正直なユーザーは、オンラインであってプロトコルを実行することを含む自身への所定の指示に従う。Ａｌｇｏｒａｎｄは控えめな計算及び通信要件しか有していないため、オンラインであってプロトコルを「バックグラウンド」で実行することはさほどの負荷ではない。無論、突然接続が切断されたか又はリブートが必要になったことに起因して生じたような、正直なプレーヤーのうち少数の「不在者」は自動的に許容される（そのような少数のプレーヤーが一時的に悪意者であると常に考えることができるため。）しかし、Ａｌｇｏｒａｎｄは、正直なユーザーが通常はオフラインである新たなモデルで機能すべく簡単に適合できることを指摘しておく。新たなモデルは以下のように非公式に導入することができる。
【００６４】
怠慢な正直さ。大雑把に言えば、ユーザーｉは、（１）プロトコルに参加するよう求められたときに自身の全ての所定の指示に従う場合、及び（２）ごく稀に、且つ適当な事前通告を以てプロトコルに参加するよう頼まれた場合に、怠慢だが正直である。
【００６５】
そのような正直さの緩和された概念により、正直な人々は必要とされた際に近くにいると確信してよく、そのような場合Ａｌｇｏｒａｎｄは次のことを証明する、
所与の時点で、関与しているプレーヤーの大多数が悪意があったとしても、システムは安全に動作する。
【００６６】
２  緒言
２．１  暗号プリミティブ
理想的ハッシング。任意の長さのストリングを固定長のバイナリストリングに写像する効率的に計算可能な暗号ハッシュ関数Ｈを信頼しよう。長年の慣習に従い、本質的に各々の可能なストリングｓを無作為且つ独立に選択（次いで固定）されたバイナリストリングＨ（ｓ）に写像する関数である無作為なオラクルとしてＨをモデル化する。
【００６７】
記述する実施形態において、Ｈは長さが２５６ビットの出力を有している。実際、このような長さは、システムを効率的にするのに充分短く、且つシステムを安全にするのに充分長い。例えば、Ｈに衝突耐性を持たせたい。すなわち、Ｈ（ｘ）＝Ｈ（ｙ）となる２個の異なるストリングｘ及びｙを見つけるのが困難でなければならない。Ｈが長さ２５６ビットの出力を有する無作為なオラクルである場合、そのようなストリングのペアを見つけることは実際に困難である。（無作為に試行すれば、誕生日のパラドックスに従い２256/2＝２128回の試行が必要である。）
【００６８】
デジタル署名。  デジタル署名は、ユーザーが秘密鍵を一切共有することなく互いに情報を認証できるようにする。デジタル署名スキームは３個の高速アルゴリズム、すなわち確率的鍵生成器Ｇ、署名アルゴリズムＳ、及び検証アルゴリズムＶを含んでいる。
【００６９】
充分に大きい整数であるセキュリティパラメータｋを与えられれば、ユーザーｉはＧを用いてｋビット鍵（すなわちストリング）のペア、すなわち「公開」鍵ｐｋi及び該当する「秘密」署名鍵ｓｋiを生成する。公開鍵は対応する秘密鍵を決して「裏切らない」。すなわち、ｐｋiに関する知識が与えられても、ｉ以外は誰もｓｋiを天文学的時間より短い時間で計算することはできない。
【００７０】
ユーザーｉはｓｋiを用いてメッセージにデジタル署名を行う。各々の可能なメッセージ（バイナリストリング）ｍに対して、ｉは最初にｍをハッシュし、次いで入力Ｈ（ｍ）及びｓｋiに対してアルゴリズムＳを実行して、ｋビットストリングを生成する。
【数２１】
2020536473.tif 000023
（脚注３：Ｈは衝突弾性を有しているため、ｍに署名することにより、ある者が異なるメッセージｍ’に「偶然署名する」ことは実際には不可能である。）
【００７１】
バイナリストリング
【数２２】
2020536473.tif 000024
は（ｐｋiに対する）ｍへのｉのデジタル署名と称され、公開鍵ｐｋiがコンテキストから明らかな場合、単にｓｉｇi（ｍ）と表記する。
【００７２】
ｐｋiを知る者は誰でもこれを用いて、ｉにより生成されたデジタル署名を確認することができる。具体的には、（ａ）プレーヤーｉの公開鍵ｐｋi、（ｂ）メッセージｍ、及び（ｃ）ストリングｓ、すなわちメッセージｍへのｉの推定されたデジタル署名が入力されたならば、検証アルゴリズムＶはＹＥＳ又はＮＯを出力する。
【００７３】
デジタル署名スキームから必要とする特性は以下の通りである。
１．合法的署名が常に検証される：ｓ＝ｓｉｇi（ｍ）ならばＶ（ｐｋi，ｍ，ｓ）＝ＹＥＳ、及び
２．デジタル署名は偽造が困難：ｓｋiに関する知識がなければ、ｉが決して署名していないメッセージｍに対してＶ（ｐｋi、ｍ、ｓ）＝ＹＥＳであるストリングｓを見つけるには天文学的に長い時間を要する。
（強いセキュリティ要件に従い、たとえ他の任意のメッセージの署名が得られてもこれは真である。）
【００７４】
従って、プレーヤーｉは、自身の代理で他の誰かがメッセージに署名するのを防止すべく、自身の署名鍵ｓｋiを秘密（用語「秘密鍵」の所以）にし続けなければならず、自身が署名するメッセージを誰でも検証できるように、ｉは自身の鍵ｐｋiを公開する（用語「公開鍵」の所以）ことに関心がある。
【００７５】
メッセージ検索可能な署名  一般に、メッセージｍは自身の署名ｓｉｇi（ｍ）から検索できない。概念的に便利な「メッセージ検索可能性」特性を満たすデジタル署名を実質的に扱うため（すなわち、署名者とメッセージが署名から容易に計算可能であることを保証すべく、以下を定義する。
ｐｋiが明らかならば、
【数２３】
2020536473.tif 000025
【００７６】
一意なデジタル署名  また、以下の追加的な特性を満たすデジタル署名スキーム（Ｇ，Ｓ，Ｖ）を考える。
【００７７】
３．一意性。以下のようなストリングｐｋ’ 、ｍ、ｓ、及びｓ’を見つけるのは困難である。
ｓ≠ｓ’且つＶ（ｐｋ’，ｍ，ｓ）＝Ｖ（ｐｋ’，ｍ，ｓ’）＝１
（一意性特性は合法的に生成された公開鍵ではないストリングｐｋ’の場合も成立する点に注意されたい。しかし特に、一意性特性が示唆するのは、指定された鍵生成器Ｇを用いて公開鍵ｐｋを合致する秘密鍵ｓｋと共に計算し、従ってｓｋを知ったならば、ｐｋに対して同じメッセージになされた２個の異なるデジタル署名を見つけるのは本質的に不可能な点である。）
【００７８】
注記
・一意な署名から検証可能なランダム関数へ。一意性特性を有するデジタル署名スキームに関して、写像ｍ→Ｈ（ｓｉｇi（ｍ））は各々の可能なストリングｍに、一意且つ無作為に選択された２５６ビットのストリングを関連付け、写像の正しさは署名ｓｉｇi（ｍ）が与えられたならば証明可能である。
【００７９】
すなわち、一意性特性を満たしている理想的なハッシング及びデジタル署名スキームは本質的に、検証可能なランダム関数（ＶＲＦ）の基本的実装を行う。
【００８０】
ＶＲＦは特別の種類のデジタル署名である。メッセージｍへのｉのこのような特別の署名をＶＲＦi（ｍ）と表記できる。一意性特性を満たすことに加え、検証可能なランダム関数は、充分に無作為であることが保証された出力を生成する。すなわち、ＶＲＦi（ｍ）は本質的に無作為であって、生成されるまで予測不可能である。対照的に、ＳＩＧi（ｍ）は充分に無作為である必要はない。例えば、ユーザーｉは、ＳＩＧi（ｍ）が常にｋビットストリングであるように、すなわち（辞書編成順に）小さくなる（すなわち冒頭の数ビットが常に０であり得る）ように自身の公開鍵を選択することができる。しかし、Ｈが理想的なハッシュ関数であるため、Ｈ（ＳＩＧi（ｍ））は常に無作為な２５６ビットストリングになる点に注意されたい。好適な実施形態において、各メッセージｍ及び各ユーザーｉに一意な乱数を正確に関連付けることが可能であるように一意性特性を満たすハッシングデジタル署名を拡張的に用いる。ＶＲＦと共にＡｌｇｏｒａｎｄを実装したならば、Ｈ（ＳＩＧi（ｍ））をＶＲＦi（ｍ）で代替することができる。特に、ユーザーｉは、最初にＳＩＧi（ｍ）、次いでＨ（ＳＩＧi（ｍ））を（順に、例えばＨ（ＳＩＧi（ｍ））を数ｐと比較するために）を計算する必要がない。ユーザーは直接ＶＲＦi（ｍ）を計算してもよい。要するに、Ｈ（ＳＩＧi（ｍ））をＶＲＦｉ（ｍ）、又はプレーヤーｉにより容易に計算されるが、他の誰にも予測不可能であって、ｉ及びｍに明確に関連付けられた充分に無作為な数であると解釈できる点を理解されたい。
【００８１】
・デジタル署名に対する３つの異なるニーズ。Ａｌｇｏｒａｎｄでは、ユーザーｉは以下を行うべくデジタル署名を信頼する。
（１）ｉ自身の支払いの認証。本アプリケーションにおいて、鍵は「長期」（すなわち、長期間にわたり多くのメッセージに署名するために用いる）であって、通常の署名スキームによるものであってよい。
（２）ｉがラウンドｒのいずれかのステップｓで行動する資格を有していることを証明する信任値の生成。ここで、鍵は長期であってよいが、一意性特性を満たすスキームによるものでなければならない。
（３）ｉが行動する各ステップで送るメッセージの認証。ここで、鍵は短期的で（すなわち、最初に使用された後で破壊され）なければならないが、通常の署名スキームによるものであってよい。
【００８２】
・低コストの簡素化。簡潔のため、各ユーザーｉが単一の長期鍵を有しているものと仮定する。従って、このような鍵は一意性特性を有する署名スキームによるものでなければならない。このような簡素性は計算コストが小さい。典型的に、一意なデジタル署名は実際、通常の署名よりも生成及び検証が僅かに高価である。
【００８３】
２．２  理想化された公開台帳
Ａｌｇｏｒａｎｄは、理想化された公開台帳に基づいて以下の支払いシステムを模倣しようとする。
【００８４】
１．初期状態。資金は、個別公開鍵（秘密裡生成されてユーザーにより所有）に紐付けられている。ｐｋ1，．．．ｐｋjを初期公開鍵、及びａ1，．．．ａjをそれら各々の初期資金単位金額とすれば、初期状態は、
Ｓ0＝（ｐｋ1，ａ1），．．．，（ｐｋj，ａj）
であり、システムで共通の知識とする。
【００８５】
２．支払い。ｐｋを現在ａ≧０の資金単位を有する公開鍵、ｐｋ’を別の公開鍵、ａ’をａ以下の非負数とする。このとき、（有効な）支払い
【数２４】
2020536473.tif 000026
はｐｋに対するデジタル署名であって、何らかの追加的な情報と共に、ｐｋからｐｋ’へのａ’資金単位の送金を指定している。次式、
【数２５】
2020536473.tif 000027
において、Ｉは、有用であるが感度は高くないと考えられる任意の追加的な情報（例：時間情報及び支払い識別子）を表し、Ｉは感度が高いと考えられる任意の追加的な情報（例：支払い理由、恐らくはｐｋ及びｐｋ’の所有者の属性等）である。
【００８６】
ｐｋ（又はその所有者）を支払人、各ｐｋ’（又はその所有者）を受取人、ａ’を支払い
【数２６】
2020536473.tif 000028
の金額と称する。
【００８７】
支払いを介した自由参加。ユーザーは自身の公開／秘密鍵ペアを生成することにより、いつでも好きなときにシステムに参加できることに注意されたい。従って、上述の支払い
【数２７】
2020536473.tif 000029
に出現する公開鍵ｐｋ’は、これまで一切資金を「所有していない」新たに生成された公開鍵であってよい。
【００８８】
３．マジック台帳。理想化されたシステムにおいて、全ての支払いは有効であって、誰でも見られるように「一般公開された」支払いの集合の改ざん防止されたリストＬに出現する。
Ｌ＝ＰＡＹ1，ＰＡＹ2，．．．，
【００８９】
各ブロックＰＡＹr+1は、ブロックＰＡＹrの出現以来なされた全ての支払いの集合を含んでいる。理想的なシステムにおいて、新規ブロックは、一定の（又は有限の）時間経過後に出現する。
【００９０】
議論
・より一般的な支払い及び未使用取引出力。より一般的に、公開鍵ｐｋがある金額ａを有していれば、ｐｋの有効な支払い
【数２８】
2020536473.tif 000030
は、
【数２９】
2020536473.tif 000031
である限り、金額
【数３０】
2020536473.tif 000032
の各々を鍵
【数３１】
2020536473.tif 000033
へ送金することができる。
【００９１】
ビットコイン及び同様のシステムにおいて、公開鍵ｐｋが所有する資金は別々の金額に分離され、ｐｋによりなされた支払い
【数３２】
2020536473.tif 000034
は、このように分離された金額ａの全額を送金しなければならない。ｐｋがａの一部ａ’＜ａだけを別の鍵に送金したい場合、残高すなわち未使用取引出力も別の鍵、恐らくｐｋ自身に送金しなければならない。
【００９２】
Ａｌｇｏｒａｎｄはまた、分割された金額を有する鍵により機能する。しかし、Ａｌｇｏｒａｎｄの新規態様に着目するには、より単純な支払い形式及び単一の金額が紐付けられた鍵に専念する方が概念的に簡単である。
【００９３】
・現状。理想化されたスキームは、システムの現状に関する情報（すなわち、各公開鍵がどれくらいの資金単位を有しているか）を直接提供しない。この情報は、マジック台帳から導出可能である。
【００９４】
理想的なシステムにおいて、能動的なユーザーは常に最新の状態情報を保存及び更新するが、さもなければ情報を一から、又は最後に計算したときから再構築しなければならない。（しかし、以下でユーザーが効率的に現状を再構築できるようにすべくＡｌｇｏｒａｎｄを拡張する仕方を示す。）
【００９５】
・セキュリティ及び「プライバシー」。デジタル署名は、誰も他のユーザーの支払いを偽造できないことを保証する。支払い
【数３３】
2020536473.tif 000035
において、公開鍵と金額は隠されないが、機微情報Ｉは隠される。実際、Ｈ（Ｉ）だけが
【数３４】
2020536473.tif 000036
に出現し、Ｈは理想的なハッシュ関数であるため、Ｈ（Ｉ）は無作為な２５６ビット値であり、従って、Ｉが何であったかについて推測する以外に分かる方法がない。しかし、Ｉが何であったかを証明する（例：支払いの理由を証明するため）には支払人はＩを明かすだけでよい。明かされたＩの正確さは、Ｈ（Ｉ）を計算して、結果的に得られた値を
【数３５】
2020536473.tif 000037
の最後の項目と比較することにより検証できる。実際、Ｈは衝突耐性を有しているため、Ｈ（Ｉ）＝Ｈ（Ｉ’）となる第２の値Ｉ’を見つけるのは難しい。
【００９６】
２．３  基本概念及び表記
鍵、ユーザー、及び所有者  別途指定しない限り、各公開鍵（略して「鍵」）は長期且つ一意性特性を有するデジタル署名スキームに関係している。公開鍵ｉは、既にシステムに存在する別の公開鍵ｊがｉに支払いを行う際にシステムに参加する。
【００９７】
個性のため、鍵を擬人化する。鍵ｉを「彼」と称し、ｉは正直であり、ｉがメッセージ等を送受信するものとする。ユーザーは鍵と同義語である。鍵と、それが属する人を区別したい場合、各々用語「デジタル鍵」及び「所有者」を用いる。
【００９８】
許可不要及び許可が必要なシステム。デジタル鍵がいつでも参加でき、且つ所有者が複数のデジタル鍵を所有できる場合、システムは許可不要であり、逆の場合は許可が必要である。
【００９９】
一意な表現  Ａｌｇｏｒａｎｄの各オブジェクトは一意な表現を有している。特に、各集合｛（ｘ，ｙ，ｚ，．．．）：ｘ∈Ｘ，ｙ∈Ｙ，ｚ∈Ｚ．．．｝は指定された仕方で、例えば、辞書編成順に先頭がｘ、次いでｙのように順序付けられている。
【０１００】
同速度の時計  世界共通の時計は存在しない。むしろ、各ユーザーは自身の時計を有している。ユーザーの時計は一切同期化される必要がない。しかし、全員が同じ速度であると仮定する。
【０１０１】
例えば、ユーザーｉの時計で午後１２時のとき、別のユーザーｊの時計では午後２：３０であってよいが、ｉの時計で１２：０１のとき、ｊの時計では２：３１である。すなわち、「全てのユーザーにとって１分は同じ（充分に、本質的に同じ）である」。
【０１０２】
ラウンド  Ａｌｇｏｒａｎｄは、ラウンドと呼ばれる論理ユニットｒ＝０，１，．．．に編成されている。
【０１０３】
ラウンドを示すために常に上付き文字を用いる。非数値量Ｑ（例：ストリング、公開鍵、集合、デジタル署名等）がラウンドｒを指すことを示すために、単にＱrを書く。Ｑが（数として解釈可能なバイナリストリングではなく）真に数である場合のみＱ(r)と書くことで記号ｒがＱの指数と解釈されないようにする。
【０１０４】
ラウンドｒ＞０（の開始時点）で、全ての公開鍵の集合がＰＫrであり、システム状態は
【数３６】
2020536473.tif 000038
であり、
【数３７】
2020536473.tif 000039
は公開鍵ｉが使える資金の量である。ＰＫrがＳrから導出可能であってＳrはまた各公開鍵ｉの他の要素を指定する場合があることに注意されたい。
【０１０５】
ラウンド０において、ＰＫ0は初期公開鍵の集合であり、Ｓ0は初期状態である。ＰＫ0及びＳ0はシステムで共通の知識とする。説明を簡単にするため、ラウンドｒの開始時点で、ＰＫ1，．．．，ＰＫr及びＳ1，．．Ｓrも同様である。
【０１０６】
ラウンドｒにおいて、システム状態はＳrからＳr+1に遷移する。数式的には以下の通りである。
Ｒｏｕｎｄ  ｒ：Ｓr→Ｓr+1
【０１０７】
支払い  Ａｌｇｏｒａｎｄでは、ユーザーは常に支払いを行う（及び分節２．７に記述するように拡散する。）ユーザーｉ∈ＰＫrの支払い
【数３８】
2020536473.tif 000040
は、理想的なシステムと同じ形式及び意味を有している。すなわち
【数３９】
2020536473.tif 000041
。
【０１０８】
支払い
【数４０】
2020536473.tif 000042
は、（１）金額ａが
【数４１】
2020536473.tif 000043
以下であり、且つ（２）いかなる公式の支払集合ＰＡＹr’（ｒ’＜ｒ）にも出現しない場合に、（ラウンドｒ支払いを縮めた）ラウンドｒで個々に有効である。（後述するように、第２の条件は
【数４２】
2020536473.tif 000044
が既に有効になっていないことを意味する。
【０１０９】
金額の合計が最大でも
【数４３】
2020536473.tif 000045
である場合、ラウンドｒ支払いの集合は包括的に有効である。
【０１１０】
支払集合  ラウンドｒ支払集合Ｐは、各ユーザーｉに対して、Ｐにおけるｉの支払い（恐らく皆無）が包括的に有効であるようなラウンドｒ支払いの集合である。全てのラウンドｒ支払集合の集合は
【数４４】
2020536473.tif 000046
である。Ｐの全ての上位集合がラウンドｒ支払集合でない場合、ラウンドｒ支払集合Ｐは最大である。
【０１１１】
実際、支払い
【数４５】
2020536473.tif 000047
はラウンドρも指定し、
【数４６】
2020536473.tif 000048
、ある一定の非負整数ｋに対して［ρ，ρ＋ｋ］の外側のラウンドでは有効になり得ないことを示唆する。
（脚注４：これにより
【数４７】
2020536473.tif 000049
が「有効」になったか否かの確認が簡素化される（すなわち、ある支払集合ＰＡＹrが
【数４８】
2020536473.tif 000050
を含むか否かの判定が簡素化される。ｋ＝０のとき、
【数４９】
2020536473.tif 000051
及び
【数５０】
2020536473.tif 000052
ならば、ｉは
【数５１】
2020536473.tif 000053
を再送信しなければならない。）
【０１１２】
公式支払集合  ラウンドｒ毎に、Ａｌｇｏｒａｎｄは、単一の（恐らく空の）支払集合ＰＡＹr、すなわちラウンドの公式支払集合を（以下に記述する仕方で）公けに選択する。（本質的に、ＰＡＹrは「実際に」生じたラウンドｒ支払いを表す。）
【０１１３】
理想的なシステム（及びビットコイン）と同様に、（１）新規ユーザーｊがシステムに参加する唯一の方法は、所与のラウンドｒの公式支払集合ＰＡＹrに属している支払いの受取人になることであり、（２）ＰＡＹrは、現在のラウンドＳrの状態から次のラウンドＳr+1の状態を判定する。数式的には次式の通りである。
ＰＡＹr：Ｓr→Ｓr+1
【０１１４】
具体的には、
１．ラウンドｒ＋１の公開鍵の集合ＰＫr+1は、ＰＫrと、ＰＡＹrの支払いに初めて出現した全ての受取人鍵の集合との和集合であり、
２．ユーザーｉがラウンドｒ＋１で所有している資金量
【数５２】
2020536473.tif 000054
は、ａi（ｒ）すなわちｉが前のラウンドで所有していた資金量（ｉ
2020536473.tif 000055
ＰＫrならば０）と、ＰＡＹrの支払いに従いｉに支払われた金額の合計である。
【０１１５】
要するに、理想的なシステムと同様に、各状態Ｓr+1は以前の支払い履歴から導出可能である：
ＰＡＹ0，．．．，ＰＡＹr
【０１１６】
２．４  ブロック及び確認されたブロック
Ａｌｇｏｒａｎｄ0において、ラウンドｒに対応するブロックＢrは、ｒ自体、ラウンドｒの支払いの集合ＰＡＹr、以下に説明する量
【数５３】
2020536473.tif 000056
、及び１つ前のブロックＨ（Ｂr-1）のハッシュを指定する。従って、固定されたあるブロックＢ0から始めて、従来のブロックチェーンが得られる。
【数５４】
2020536473.tif 000057
【０１１７】
Ａｌｇｏｒａｎｄでは、ブロックの真正性は、Ｂrを証明済みブロック
【数５５】
2020536473.tif 000058
に変換する別の情報「ブロック証明」ＣＥＲＴrにより実際に保証される。マジック台帳は従って、以下のような証明済みブロックのシーケンスにより実装される。
【数５６】
2020536473.tif 000059
【０１１８】
議論  以下で分かるように、ＣＥＲＴrは、これらのメンバーの各々が実際にＳＶrに属する旨の証明と共に、Ｈ（Ｂr）、ＳＶrの大部分のメンバーへのデジタル署名の集合から構成される。無論、証明ＣＥＲＴrをブロック自体に含めることができるが、別々にしておいた方が概念的に明瞭であることが分かる。）
【０１１９】
ビットコインでは各ブロックは特別の特性を満たす、すなわち「暗号パズルの解を含んでいる」必要があるため、ブロック生成の計算負荷が高くなると共に、分岐は避けられず稀でなくなる。対照的に、Ａｌｇｏｒａｎｄのブロックチェーンは、主な利点が２つある。すなわち最小限の計算で生成され、且つ極端に高い確率では分岐しない。各ブロックＢiは、ブロックチェーンに参加したならば直ちに安全に最終である。
【０１２０】
２．５  受容可能な失敗確率
Ａｌｇｏｒａｎｄのセキュリティを解析すべく、何かがおかしい（例：検証者集合ＳＶrの大多数が正直でない）ことを受け入れようとする確率Ｆを指定する。暗号ハッシュ関数Ｈの出力長の場合と同様に、Ｆもパラメータである。しかし、その場合と同様に、Ａｌｇｏｒａｎｄでは充分なセキュリティで充分な効率を同時に得ることが実際に可能であるという事実をより直観的に把握できるように、Ｆを具体的な値に設定することが有用であると考える。Ｆが望み通りに設定できるパラメータであることを強調すべく、第１及び第２の実施形態で各々以下のように設定することができる。
Ｆ＝１０-12且つＦ＝１０-18
【０１２１】
議論  １０-12が実際に１兆分の１未満であることに注意すれば、このようなＦの選択は発明者らのアプリケーションに充分であると考えられる。１０-12は、敵対者が正直なユーザーの支払いを偽造できる確率ではないことを強調しよう。全ての支払いはデジタル署名され、従って適切なデジタル署名を用いた場合、支払いを偽造する確率は１０-12よりもはるかに小さく、実際にはほぼ０である。確率Ｆならば許容し得る悪い事象はＡｌｇｏｒａｎｄのブロックチェーン分岐である。発明者らによるＦの設定及び１分間にわたるラウンドにおいて、Ａｌｇｏｒａｎｄのブロックチェーンに分岐が生じるのは（概ね）１９０万年に一度程度の稀さであることに注意されたい。対照的に、ビットコインでは分岐は極めて頻繁に生じる。
【０１２２】
より欲張りな人はＦをより低い値に設定することができる。このため、第２の実施形態でＦを１０-18に設定することを考える。ブロックが毎秒生成されると仮定すれば、１０18はビッグバンから現在まで宇宙が存在した推定秒数であることに注意されたい。従って、Ｆ＝１０-18として、ブロックが１秒で生成される場合、分岐を観測するために宇宙の年齢ほど待たねばならない。
【０１２３】
２．６  敵対的モデル
Ａｌｇｏｒａｎｄは、極めて敵対的なモデルで安全であるように設計されている。以下に説明する。
【０１２４】
正直な及び悪意のあるユーザー  あるユーザーが正直であるのは、自身の全てのプロトコル命令に従い、メッセージの送受信を完全に行える場合である。ユーザーに悪意（すなわち、分散コンピューティングの用語でビザンチン）があるのは、自身の所定の命令から自在に逸脱できる場合である。
【０１２５】
敵対者  敵対者とは、望みのユーザーをいつでも（唆せるユーザーの数の上限だけに制約される）悪意のある者にする、分かり易く擬人化された効率的（技術的に多項式時間）なアルゴリズムである。
【０１２６】
敵対者は、全ての悪意のあるユーザーを完全に支配して完璧に協調させる。敵対者は、ユーザーの全てのメッセージの送受信を含む全ての行動をユーザーになり代わって行い、任意の仕方でユーザーを所定の命令から逸脱させることができる。又は、敵対者は単にメッセージを送受信している唆されたユーザーを孤立させることができる。敵対者がユーザーｉにさせた行動によりｉの悪意が露見する場合があるものの、ユーザーｉに悪意のあることは他の誰にも自動的には分からないことを明言しよう。
【０１２７】
しかしこの強力な敵対者は、
・無限の計算能力を有しておらず、無視できる確率でしか正直なユーザーのデジタル署名を偽造することができず、
・正直なユーザー同士のメッセージ交換にいかなる仕方でも干渉することができない。
【０１２８】
更に、正直なユーザーを攻撃する能力は、以下の仮定の１つにより制約される。
【０１２９】
資金の正直な多数派  資金の正直な多数派（ＨＭＭ）仮定の連続体を考える。すなわち、各々の非負整数ｋ及び実数ｈ＞１／２に対して次式が成り立つ。
ＨＨＭk＞ｈ：毎ラウンドｒにおける正直なユーザーが、ラウンドｒ−ｋでシステムにあった全資金のｈより大きい割合を所有していた。
【０１３０】
議論。全ての悪意のあるユーザーが行動を完全に協調（あたかも単一の主体すなわち敵対者により支配されているかの如く）させるものと仮定するのは却って悲観的な仮説である。余りにも大勢を完全に協調させるのは困難である。恐らく、悪意のあるプレーヤーの別々のグループ内でしか協調は生じない。しかし、悪意のあるユーザーが享受できる協調のレベルについて確信が持てないため、後悔するよりも安全な方がよいであろう。
【０１３１】
敵対者が非公開に、動的に、及び直ちにユーザーを唆せると仮定することもまた悲観的である。つまり、現実的にはユーザーの行動を完全に支配するには、ある程度の時間を要する。
【０１３２】
ＨＭＭk＞ｈという仮定は、１ラウンドが（平均）１分で実行されたならば、所与のラウンドで、ｋ＝１２０ならば少なくとも２時間、ｋ＝１００００ならば少なくとも１週間は資金の大部分が正直なユーザーの手元に残るであろうことを示唆する。
【０１３３】
ＨＭＭ仮定及び先の計算能力の正直な多数派は、計算能力は金で買えるので、悪意のあるユーザーは資金の大部分を所有していれば大部分の計算能力を得ることができるという意味で関連していることに注意されたい。
【０１３４】
２．７  通信モデル
メッセージ拡散、すなわち「ピアツーピアゴシップ」を通信の唯一の手段と考え、全ての拡散されたメッセージが適時にほぼ全ての正直なユーザーに届くと仮定する。（脚注５：本質的に、ビットコインと同様に、ユーザーがメッセージｍを拡散した際に、最初にｍを受信している全ての能動的なユーザーｉが、適当な少ない数の能動的なユーザー、すなわちｍの転送先である自身の「隣人」を、恐らくユーザーから承認を受信するまで無作為且つ独立に選択する。ｍの拡散が終了するのは、初めてどのユーザーもｍを受信しなかったときである。）本質的に、正直なユーザーにより拡散された各メッセージｍは、ｍの長さに依存する所与の時間内に全ての正直なユーザーに届くものと仮定する。（実際にはｍは正直なユーザーの充分に高い割合に達すれば充分である。）
【０１３５】
３  従来の設定におけるＢＡプロトコルＢＡ*
既に強調したように、ビザンチン合意はＡｌｇｏｒａｎｄの主要な要素である。実際、Ａｌｇｏｒａｎｄが分岐に影響を受けないのは、そのようなＢＡプロトコルを用いるからである。しかし、強力な敵対者から保護するために、Ａｌｇｏｒａｎｄは新規プレーヤーの代替可能制約を満たすＢＡプロトコルに依存しなければならない。また、Ａｌｇｏｒａｎｄが効率的であるためには、このようなＢＡプロトコルは極めて効率的でなければならない。
【０１３６】
ＢＡプロトコルは当初、理想化された通信モデル、すなわち完全同期ネットワーク（ＳＣネットワーク）に対して定義された。このようなモデルにより、ＢＡプロトコルの設計及び解析を簡素化することができる。従って、本節では、ＳＣネットワーク用に新たなＢＡプロトコル、すなわちＢＡ*を導入し、プレーヤー代替可能性の問題を完全に無視する。プロトコルＢＡ*は、別々の値の寄与である。実際、これまで知られている最も効率的なＳＣネットワーク用の暗号ＢＡプロトコルである。
【０１３７】
Ａｌｇｏｒａｎｄプロトコル内で用いるため、異なる通信モデル及びコンテキストを考慮すべくＢＡ*を変更する。
【０１３８】
ＢＡ*が動作するモデル及びビザンチン合意の概念を想起することから始める。
【０１３９】
３．１  完全同期ネットワーク及び該当敵対者
ＳＣネットワークにおいて、各積分時刻ｒ＝１、２，．．．で刻時する共通のクロックがある。
【０１４０】
各々の偶数時刻クリックｒにおいて、各プレーヤーｉは即時且つ同時に、自身を含む各プレーヤーｊに単一のメッセージ
【数５７】
2020536473.tif 000060
（恐らく空メッセージ）を送る。各メッセージ
【数５８】
2020536473.tif 000061
は、プレーヤーｊが時刻ｒ＋１で送信者ｉの属性と共に正しく受信される。
【０１４１】
再び、通信プロトコルにおいて、プレーヤーは、所定の指示の全てに従うならば正直であり、さもなければ全ての悪意のあるプレーヤーは完全に支配されていて、特に、悪意のあるプレーヤー宛の全てのメッセージを直ちに受信して、送るメッセージを選択する敵対者により完全に協調させられる。
【０１４２】
敵対者は、望みの奇数時刻で、狙った正直なユーザーを直ちに悪意のある者に変えることができ、悪意のあるプレーヤー数の可能な上限ｔにしか制約されない。すなわち、敵対者は、通常通り配信されるであろう「正直なユーザーｉにより既に送られたメッセージに干渉することはできない」。
【０１４３】
敵対者はまた、各偶数ラウンドにおいて、正直なプレーヤーが現在送っているメッセージを即時に見て、その情報を即時に用いて悪意のあるプレーヤーが同時刻に送るメッセージを選択する追加的な能力を有している。
【０１４４】
３．２  ビザンチン合意の概念
ビザンチン合意の概念は当初、バイナリの場合、すなわち全ての初期値がビットからなる場合について導入されたかもしれない。しかし、間もなく任意の初期値まで拡張された。ＢＡプロトコルを、任意の値の場合を意味するものとする。
【０１４５】
定義３．１．同期ネットワークにおいて、Ｐを、プレーヤー集合をプレーヤー同士が共通に知っているｎプレーヤープロトコルとし、ｔをｎ≧２ｔ＋１であるような正整数とする。Ｐを、健全性σ∈（０，１）を有する任意の値（又はバイナリ）（ｎ，ｆ）ビザンチン合意プロトコルと呼ぶのは、特別の記号⊥を含んでいない値Ｖの全ての集合に対して（又はＶ＝｛０，１｝に対して）、プレーヤーのうち最大でもｔ人が悪意を有し、且つ全てのプレーヤーｉが初期値ｖi∈Ｖから始まる実行において、全ての正直なプレーヤーｊが確率１で停止し、少なくとも確率σで、以下の２つの条件を満たすように値ｏｕｔi∈Ｖ∪｛⊥｝を出力する場合である。
１．合意：ｏｕｔ∈Ｖ∪｛⊥｝が存在し、全ての正直なプレーヤーｉに対してｏｕｔi＝ｏｕｔとなる。
２．整合性：ある値ｖ∈Ｖに対して、全てのプレーヤーｉについてｖi＝ｖならば、ｏｕｔ＝ｖである。
【０１４６】
ｏｕｔをＰの出力と称し、各ｏｕｔiをプレーヤーｉの出力と称する。
【０１４７】
３．３  ＢＡ表記＃
ＢＡプロトコルにおいて、プレーヤーは、所与のステップで何人のプレーヤーが自身にメッセージを送ったか数えることを求められる。従って、送られるかもしれない各々の可能な値ｖに対して、
【数５９】
2020536473.tif 000062
（又はｓが明らかな場合は単に＃i（ｖ））が、ｉがステップｓでｖを受信したプレーヤーｊの数である。
【０１４８】
プレーヤーｉが各プレーヤーｊからちょうど１個のメッセージを受信することを想起して、プレーヤー数がｎである場合、全てのｉ及びｓに対して
【数６０】
2020536473.tif 000063
である。
【０１４９】
３．４  新規バイナリＢＡプロトコルＢＢＡ*
本節において、３分の２以上のプレーヤーの正直さに依存して、極めて高速である新たなバイナリＢＡプロトコル（ＢＢＡ*）を提示する。悪意のあるプレーヤーが何をしようと、主ループの各々の実行は、機械的に実行されるだけでなく、プレーヤーを確率１／３で合意に達せさせる。
【０１５０】
ＢＢＡ*において、各プレーヤーは、一意な署名特性を満たすデジタル署名スキームの自身の公開鍵を有している。本プロトコルは完全同期ネットワークで動作すべく意図されているため、プレーヤーｉが自身の各メッセージに署名する必要はない。
【０１５１】
デジタル署名を用いて、ステップ３で充分に一般的なランダムビットを生成する。（Ａｌｇｏｒａｎｄでは、デジタル署名を用いて他の全てのメッセージも認証する。）
【０１５２】
プロトコルは最小限の設定、すなわちプレーヤーの鍵から独立した一般的な無作為なストリングｒを要する。（Ａｌｇｏｒａｎｄでは、ｒは実際には量Ｑrで代替される。）
【０１５３】
プロトコルＢＢＡ*は３ステップループであり、プレーヤーは繰り返しブール値を交換し、異なるプレーヤーが異なる時点でループを出ることができる。プレーヤーｉは、あるステップで、特別の値０*又は特別の値１*を拡散して、全てのプレーヤーに、将来の全てステップで各々がｉから０及び１を受信する「振りをする」ように指示することによりループを出る。（換言すれば、プレーヤーｊが別のプレーヤーｉから受信した最後のメッセージがビットｂであったと仮定する。すると、ｉから一切メッセージを受信しない任意のステップで、ｊはあたかもｉが自身にビットｂを送ったかのように振る舞う。）
【０１５４】
プロトコルは、３ステップループが何回実行されたか表すカウンタγを用いる。ＢＢＡ*の開始時点でγ＝０である。（γを大域的カウンタとみなすこともできるが、実際にはループが実行される都度個々のプレーヤーにより増分される。）
【０１５５】
ｎ≧３ｔ＋１が存在し、ｔは悪意のあるプレーヤーの可能な最大数である。バイナリストリングｘを、（先頭が０であり得る）バイナリ表現がｘである整数とし、ｌｓｂ（ｘ）はｘの最下位ビットを表す。
【０１５６】
プロトコルＢＢＡ*
（通信）ステップ１．［コインが０に固定されたステップ］各プレーヤーｉはｂiを送る。
１．１
【数６１】
2020536473.tif 000064
ならばｉはｂi＝０を設定、０*を送信、ｏｕｔi＝０を出力、次いで停止する。
１．２
【数６２】
2020536473.tif 000065
ならばｉはｂi＝１を設定する。
１．３  さもなければ、ｉはｂi＝０を設定する。
【０１５７】
（通信）ステップ２．［コインが１に固定されたステップ］各プレーヤーｉはｂiを送る。
２．１
【数６３】
2020536473.tif 000066
ならばｉはｂi＝１を設定、１*を送信、ｏｕｔi＝１を出力、次いで停止する。
２．２
【数６４】
2020536473.tif 000067
ならばｉはｂi＝０を設定する。
２．３  さもなければ、ｉはｂi＝１を設定する。
【０１５８】
（通信）ステップ３．［コインを本当に投げたステップ］各プレーヤーｉはｂi及びＳＩＧi（ｒ，γ）を送信する。
３．１
【数６５】
2020536473.tif 000068
ならばｉはｂi＝０を設定する。
３．２
【数６６】
2020536473.tif 000069
ならばｉはｂi＝１を設定する。
３．３  さもなければ、Ｓi＝｛ｊ∈Ｎ（ステップ３で正当なメッセージをｉに送った者）｝として、ｉは
【数６７】
2020536473.tif 000070
を設定し、γiを１増分して、ステップ１に戻る。
【０１５９】
定理３．１．  ｎ≧３ｔ＋１である都度、ＢＢＡ*は健全性１を有するバイナリ（ｎ，ｔ）ＢＡプロトコルである。
【０１６０】
定理３．１の証明は、ｈｔｔｐｓ：／／ｐｅｏｐｌｅ．ｃｓａｉｌ．ｍｉｔ．ｅｄｕ／ｓｉｌｖｉｏ／Ｓｅｌｅｃｔｅｄ−ＳｃｉｅｎｔｉｆｉｃＰａｐｅｒｓ／ＤｉｓｔｒｉｂｕｔｅｄＣｏｍｐｕｔａｔｉｏｎ／ＢＹＺＡＮＴＩＮＥＡＧＲＥＥＭＥＮＴＭＡＤＥＴＲＩＶＩＡＬ．１５ｐｄｆで見ることができる。
【０１６１】
３．５  等級化コンセンサス及びプロトコルＧＣ
任意の値に対して、ビザンチン合意よりもはるかに弱いコンセンサスの概念を想起しよう。
【０１６２】
定義３．２．  Ｐを、全てのプレーヤーの集合が共通知識であって、各プレーヤーｉが任意の初期値
【数６８】
2020536473.tif 000071
を非公開に知っているプロトコルとする。
【０１６３】
Ｐを（ｎ，ｔ）等級化コンセンサスプロトコルであると言うのは、ｎ人のうち最大でもｔ人が悪意を有しているプレーヤーによる全ての実行において、全ての正直なプレーヤーｉが、以下の３つの条件を満たすべく値の序列のペア（ｖi，ｇi）の出力を停止する場合であり、ここで（ｇi∈｛０，１，２｝）であり、
１．全ての正直なプレーヤーｉ及びｊに対して、｜ｇi−ｇj｜≦１
２．全ての正直なプレーヤーｉ及びｊに対して、ｇi−ｇj＞０⇒ｖi＝ｖj
３．ある値ｖに対して
【数６９】
2020536473.tif 000072
ならば、全ての正直なプレーヤーｉに対してｖi＝ｖ且つｇi＝２である。
【０１６４】
以下のツーステッププロトコルＧＣは、文献で公知の等級化コンセンサスプロトコルである。４．１節のプロトコル
【数７０】
2020536473.tif 000073
のステップに合致させるべく、ＧＣのステップを各々２及び３と呼ぶ。（実際、
【数７１】
2020536473.tif 000074
の第１ステップは、他の事項、すなわち新たなブロックの提案に関する。）
【０１６５】
プロトコルＧＣ
ステップ２．各プレーヤーｉは全てのプレーヤーに
【数７２】
2020536473.tif 000075
を送る。
ステップ３．
【数７３】
2020536473.tif 000076
のときのみ各プレーヤーｉは全てのプレーヤーにストリングｘを送る。
出力判定。各プレーヤーｉは、次式のように計算されるペア（ｖi、ｇi）を出力する：
・あるｘに対して、
【数７４】
2020536473.tif 000077
ならば、ｖi＝ｘ且つｇi＝２
・あるｘに対して、
【数７５】
2020536473.tif 000078
ならば、ｖi＝ｘ且つｇi＝１
・さもなければ、ｖi＝⊥且つｇi＝０
【０１６６】
プロトコルＧＣが文献で公知のプロトコルであるため、以下の定理が保持することは既知である。
【０１６７】
定理３．２．  ｎ≧３ｔ＋１ならば、ＧＣは（ｎ，ｔ）等級化ブロードキャストプロトコルである。
【０１６８】
３．６  プロトコルＢＡ*
ここでバイナリＢＡプロトコルＢＢＡ*及び等級化コンセンサスプロトコルＧＣを介した任意値ＢＡプロトコルＢＡ*を説明する。以下、各プレーヤーｉの初期値は
【数７６】
2020536473.tif 000079
である。
【０１６９】
プロトコルＢＡ*
ステップ１及び２．  各プレーヤーｉは、
【数７７】
2020536473.tif 000080
が入力されたならばＧＣを実行してペア（ｖi，ｇi）を計算する。
ステップ３，．．．  各プレーヤーｉは、ｇi＝２ならば初期入力を０として、さもなければ初期入力を１としてＢＢＡ*を実行してビットｏｕｔiを計算する。
【０１７０】
出力判定。各プレーヤーｉは、ｏｕｔi＝０ならばｖiを、さもなければ⊥を出力する。
【０１７１】
定理３．３．  ｎ≧３ｔ＋１である都度、ＢＡ*は健全性１を有する（ｎ，ｔ）ＢＡプロトコルである。
【０１７２】
証明。最初に整合性、次いで合意を証明する。
【０１７３】
整合性の証明。ある値ｖ∈Ｖに対して、
【数７８】
2020536473.tif 000081
と仮定する。次いで、等級化コンセンサスの特性３により、ＧＣの実行後、全ての正直なプレーヤーが（ｖ，２）を出力する。従って、ＢＢＡ*の実行の終了時点で全ての正直なプレーヤーの初期ビットは０である。従って、ＢＡ*の実行終了時点で、バイナリビザンチン合意の合意特性により、全ての正直なプレーヤーに対してｏｕｔi＝０である。これはＢＡ*における各々の正直なプレーヤーｉの出力がｖi＝ｖであることを意味する。□
【０１７４】
合意の証明。ＢＢＡ*がバイナリＢＡプロトコルであるため、
（Ａ）全ての正直なプレーヤーｉに対してｏｕｔi＝１、又は
（Ｂ）全ての正直なプレーヤーｉに対してｏｕｔi＝０である。
【０１７５】
ケースＡにおいて、ＢＡ*で全ての正直なプレーヤーは⊥を出力し、従って合意が成立する。ここでケースＢを考える。この場合、ＢＢＡ*の実行において、少なくとも１人の正直なプレーヤーｉの初期ビットは０である。（実際、全ての正直なプレーヤーの初期ビットが１であったならば、ＢＢＡ*の整合性特性により、全ての正直なｊに対してｏｕｔj＝１が得られよう。）従って、ＧＣの実行後、ｉはある値ｖに対してペア（ｖ、２）を出力する。従って、等級化コンセンサスの特性１により、全ての正直なプレーヤーｊに対してｇj＞０である。従って、等級化コンセンサスの特性２により、全ての正直なプレーヤーｊに対してｖj＝ｖである。これは、ＢＡ*の終了時点で全ての正直なプレーヤーｊがｖを出力することを示唆する。従ってＢのケースでも合意が成立する。□
【０１７６】
整合性と合意が共に成立するため、ＢＡ*は任意値ＢＡプロトコルである。■
【０１７７】
プロトコルＢＡ*は、ゴシッピングネットワークでも動作し、実際、認識された極めて敵対的なモデルでＡｌｇｏｒａｎｄが安全であるために必須のプレーヤー代替可能性特性を満たしている。
【０１７８】
ＢＢＡ*及びＢＡ*のプレーヤー代替可能性  ここでプロトコルＢＡ*及びＢＢＡ*が、通信がプレーヤー代替可能性を満たすピアツーピアゴシップを介して行われるネットワークでの実行に適合可能である理由を若干直観的に説明しよう。具体性を持たせるべく、ネットワークが１０Ｍ人のユーザーを有し、ＢＢＡ*（又はＢＡ*）の各ステップｘが、秘密の暗号抽選を介して無作為に選択され、ステップｘでメッセージを送る資格を有していることを証明する証明を有する１０，０００人のプレーヤーの集団により実行されるものと仮定する。所与のステップで送られた各メッセージがステップ番号を特定し、送信者によりデジタル署名されていて、自身の送信者がそのステップで話す資格を有していることを証明する証明を含むものと仮定する。
【０１７９】
最初に、正直なプレーヤーの割合ｈが２／３よりも充分に大きい（例：７５％）場合、圧倒的な確率で、各ステップで選択された委員会が、必要な２／３の正直者の多数派を有している。
【０１８０】
また、１０，０００人強の無作為に選択された委員会が各ステップで変化するという事実はＢＢＡ*又はＢＡ*のいずれの正当な動作も妨げない。実際、いずれのプロトコルにおいても、プレーヤーｉはステップｓで、ステップｓ−１において所与のメッセージｍを受信した回数に反応するだけである。ゴシップネットワークにいるため、ステップｓ−１で送られた、ステップｓで動作すべく選択されたものを含む、全てのメッセージが（直観的であるために直ちに）全てのユーザーに届く。更に、ステップｓ−１で送られた全てのメッセージがステップ番号を指定しており、送信者がステップｓ−１で話す権限が実際に与えられた旨の信任値を含んでいる。従って、送信者がステップｓ−１でも選択されたか否かに依らず、ステップｓで行動すべく選択されたユーザーｉは、自身が正当なステップｓ−１のメッセージを受信した回数を完全に正しく数えることができる。ユーザーｉがそれまで全てのステップを実行していたか否かは全く重要でない。全てのユーザーは「同じ船に乗って」おり、従って簡単に他のユーザーで代替できる。
【０１８１】
４  Ａｌｇｏｒａｎｄの２つの実施形態
極めて高いレベルで議論したように、Ａｌｇｏｒａｎｄの１ラウンドは以下のように理想的に進行する。第１に、無作為に選択されたユーザー、すなわちリーダーが新規ブロックを提案して循環させる。（この処理は最初に数人の潜在的リーダーを選択し、次いで、少なくともある程度の時間にわたり、単一の共通リーダーが出現することを保証するステップを含む。）第２に、無作為に選択されたユーザーの委員会が選択され、リーダーが提案したブロックに対してビザンチン合意に達する。（処理は、ＢＡプロトコルの各ステップが別途選択された委員会により実行されることを含んでいる。）同意に達したブロックは次いで、委員会メンバーの所与の閾値（ＴH）によりデジタル署名される。これらのデジタル署名は、どれが新規ブロックであるかを誰でも確信できるように拡散される。（これは、署名者の信任値を循環させて、新規ブロックのハッシュだけを認証して、そのハッシュが明らかになれば全員がブロックを学習できることを保証するステップを含む。）
【０１８２】
次の２個の節において、適切な「正直なユーザーの多数派」仮定の下で各々機能する基本Ａｌｇｏｒａｎｄ設計の２つの実施形態
【数７９】
2020536473.tif 000082
及び
【数８０】
2020536473.tif 000083
を提示する。節？？において、これらの実施形態が「正直な資金の多数派」仮定の下で採用する仕方を示す。
【０１８３】
【数８１】
2020536473.tif 000084
は委員の２／３超が正直であることを認識するだけである。また、
【数８２】
2020536473.tif 000085
において、ビザンチン合意に達するまでのステップ数は、適切に大きい数を上限としているため、一定数のステップ内で合意に達することが圧倒的な確率で保証されている（しかし、
【数８３】
2020536473.tif 000086
のステップよりも潜在的に長い時間を要する。）最後のステップまで未だ合意に達していない遠隔ケースにおいて、委員会は常に有効である空ブロックについて合意する。
【０１８４】
【数８４】
2020536473.tif 000087
は、委員会の正直なメンバーの人数が常に一定の閾値ｔH以上である（圧倒的な確率で、委員会メンバーの少なくとも２／３が正直であることを保証する）ことを想定している。また、
【数８５】
2020536473.tif 000088
は任意のステップ数で（しかし潜在的に
【数８６】
2020536473.tif 000089
よりも短い時間で）ビザンチン合意に達することができる。
【０１８５】
当業者には、これらの基本的実施形態の多くの変型例を導出できることが理解されよう。特に、
【数８７】
2020536473.tif 000090
を前提として、任意のステップ数でビザンチン合意に到達できるように
【数８８】
2020536473.tif 000091
を変更することは容易である。
【０１８６】
両方の実施形態は、以下の共通核、表記、概念、及びパラメータを共有している。
【０１８７】
４．１  共通核
目的  理想的には、各ラウンドｒに対して、Ａｌｇｏｒａｎｄは以下の特性に満たす必要がある。
１．完全な正しさ。全ての正直なユーザーが同一ブロックＢrについて同意する。
２．完全性１。確率１で、正直なユーザーによりブロックＢrが選択されている。
（実際、悪意のあるユーザーは常に、自身の「友人」の支払いだけを含む支払集合を有するブロックを選択することができる。）
【０１８８】
無論、完全な正しさだけを保証するのはたやすい。全員が常に公式支払集合ＰＡＹrが空になるように選択する。しかしこの場合、システムの完全性は０である。残念ながら、悪意のあるユーザーが存在する場合に完全な正しさと完全性１の両方を保証することは容易でない。従ってＡｌｇｏｒａｎｄはより現実的な目的を採用する。非公式に、正直なユーザーの割合をｈ、但しｈ＞２／３、と表記すれば、Ａｌｇｏｒａｎｄの目標は、
圧倒的な確率で、完全な正しさ及びｈに近い完全性を保証することである。
【０１８９】
完全性よりも正しさを優先させることは合理的な選択に思える。１ラウンドで処理されなかった支払いは次のラウンドで処理できるが、可能ならば分岐を避けるべきである。
【０１９０】
導かれたビザンチン合意  過剰な時間及び通信を一時的に無視すれば、完全な正しさを以下のように保証することができる。ラウンドｒの開始時点で、各ユーザーｉは自身の候補ブロック
【数８９】
2020536473.tif 000092
を提案する。次いで、全てのユーザーが、候補ブロックのうち１個だけについてビザンチン合意に達する。発明者らの導入から、採用したＢＡプロトコルは２／３の正直な多数派を必要とし、プレーヤーは代替可能である。各々ステップは無作為に選択された、内部変数を一切共有しない検証者の小さい集合により実行することができる。
【０１９１】
残念ながら、上述のアプローチは全くうまくいかない。その理由は、正直なユーザーが提案する候補ブロックは互いに全く異なる可能性が極めて高いからである。実際、各々の正直なユーザーは異なる支払いを見る。従って、異なる正直なユーザーが見た支払いの集合の多くが重なり合っているにもかかわらず、全ての正直なユーザーが同じブロックを提案する可能性は低い。従って、ＢＡプロトコルの整合性に関する合意は決して強制ではなく、合意１だけであり、従って、合意に達するのは良いブロックではなく、常に⊥に関してである。
【０１９２】
Ａｌｇｏｒａｎｄ’はこの問題を以下のように回避する。最初に、ラウンドｒのリーダーｌrが選択される。次いで、ｌrは自身の候補ブロック
【数９０】
2020536473.tif 000093
を拡散する。最後に、ユーザーはｌrから実際に受信するブロックに関して合意に達する。ｌrが正直であるときは常に完全な正しさと完全性１の両方が成立するため、Ａｌｇｏｒａｎｄ’はｌrがｈに近い確率で正直であることを保証する。
【０１９３】
リーダー選択  Ａｌｇｏｒａｎｄにおいて、ｒ番目のブロックは以下の形式である。
【数９１】
2020536473.tif 000094
【０１９４】
序で既に述べたように、量Ｑr-1は、極めて強力な敵対者により本質的に不正操作が不可能なように注意深く構築されている。（本節の後半でその理由について直観的に説明する。）ラウンドｒの開始時点で、全てのユーザーはそれまでのブロックチェーンＢ0，．．．，Ｂr-1を知っており、そこから全ての先行ラウンドのユーザーの集合、すなわちＰＫ1，．．．，ＰＫr-1を導出する。ラウンドｒの潜在的リーダーは下記を満たすユーザーｉである。
．Ｈ（ＳＩＧi（ｒ，１，Ｑr-1））≦ｐ
【０１９５】
以下に説明する。基礎となるデジタル署名スキームのメッセージ検索可能性特性により、量Ｑr-1はブロックＢr-1から導出可能であるため、ことに注意されたい。更に、基礎となる署名スキームは一意性特性を満たす。従って、ＳＩＧi（ｒ，１，Ｑr-1）はｉ及びｒに一意に関連付けられたバイナリストリングである。従って、Ｈは無作為オラクルであるため、Ｈ（ＳＩＧi（ｒ，１，Ｑr-1））はｉ及びｒに一意に関連付けられた無作為な長さ２５６ビットのストリングである。Ｈ（ＳＩＧi（ｒ，１，Ｑr-1））の前の記号「．」は（このケースではバイナリの）小数点であるため、
【数９２】
2020536473.tif 000095
は、ｉ及びｒに一意に関連付けられた０〜１の間の無作為な２５６ビットの数のバイナリ拡張である。従って、ｒiがｐ以下である確率は本質的にｐである。
【０１９６】
確率ｐは、少なくとも１個の潜在的検証者が圧倒的な（すなわち１−Ｆ）確率で正直であるように選択される。（実際、ｐはそのような最小確率となるように選択される。）
【０１９７】
ｉが自身の署名を計算できる唯一のユーザーであるため、自身がラウンド１の潜在的検証者である否かを判定できるのはｉだけであることに注意されたい。しかし、自身の信任値
【数９３】
2020536473.tif 000096
を明かすことにより、ｉはラウンドｒの潜在的検証者であることを誰に対しても証明することができる。
【０１９８】
リーダーｌrは、自身のハッシュされた信任値が、他の全ての潜在的リーダーｊのハッシュされた信任値よりも小さい潜在的リーダーであると定義される。すなわち
【数９４】
2020536473.tif 000097
が成り立つ。
【０１９９】
悪意のあるｌrは自身の信任値を明かさないかもしれないため、ラウンドｒの正当なリーダーが知られることは決してなく、且つ極めて稀な同点を禁止しているので、ｌrが実際にラウンドｒの唯一のリーダーである。
【０２００】
最後に、最後だが重要な詳細について述べる。ユーザーｉがラウンドｒの潜在的リーダー（従ってリーダー）であり得るのは、少なくともｋラウンドにわたりシステムに属した場合だけである。これにより、Ｑrの不正操作防止及び全ての将来のＱ量が保証される。実際、潜在的リーダーのうち１人が実際にＱrを決定することになる。
【０２０１】
検証者選択  ラウンドｒの各ステップｓ＞１が検証者の小さい集合ＳＶr,sにより実行される。再び、各々の検証者はｉ∈ＳＶr,sはｒ以前のラウンドでシステムｋに既に存在していたユーザーの中から、再び特別の量Ｑr-1を介して無作為に選択される。具体的には次式が成立すればｉ∈ＰＶr,sがＳＶr,sの検証者である。
．Ｈ（ＳＩＧi（ｒ，ｓ，Ｑr-1））≦ｐ’
【０２０２】
再び、自身がＳＶr,sに属しているか否かを知っているのはｉだけであるが、これが事実ならば、ｉは自身の信任値
【数９５】
2020536473.tif 000098
を示すことにより証明することができた。検証者ｉ∈ＳＶr,sはラウンドｒのステップｓでメッセージ
【数９６】
2020536473.tif 000099
を送り、メッセージは、次ステップでの検証者ｆが
【数９７】
2020536473.tif 000100
が合法的なステップｓのメッセージであると認識できるようにすべく自身の信任値
【数９８】
2020536473.tif 000101
を含んでいる。
【０２０３】
確率ｐ’は、ＳＶr,sにおいて、＃ｇｏｏｄを正直なユーザーの数、＃ｂａｄを悪意のあるユーザーの数とすれば、圧倒的確率で以下の２つの条件が成立することを保証すべく選択されている。
【０２０４】
【数９９】
2020536473.tif 000102
の実施形態の場合、
（１）＃ｇｏｏｄ＞２・＃ｂａｄ、及び
（２）＃ｇｏｏｄ＋４・＃ｂａｄ＜２ｎ、但しｎはＳＶr,sの期待濃度である。
【０２０５】
【数１００】
2020536473.tif 000103
の実施形態の場合、
（１）＃ｇｏｏｄ＞ｔH、及び
（２）＃ｇｏｏｄ＋２＃ｂａｄ＜２ｔH、但しｔHは指定された閾値である。
【０２０６】
これらの条件は、充分に高い確率で、（ａ）ＢＡプロトコルの最後のステップにおいて、少なくとも所与の数の正直なプレーヤーが新規ブロックＢrにデジタル署名し、（ｂ）１ラウンド毎に１個のブロックだけが必要な数の署名を有していてよく、（ｃ）使用したＢＡプロトコルが（各ステップで）必要とされる２／３の正直な多数派を有していることを意味する。
【０２０７】
ブロック生成の明確化  ラウンドｒのリーダーｌrが正直ならば、対応するブロックは以下の形式であり、
【数１０１】
2020536473.tif 000104
ここに、支払集合ＰＡＹrは最大である。（全ての支払集合が定義から全体として有効であることを想起されたい。）
【０２０８】
さもなければ（すなわちｌrに悪意があれば）、Ｂrは以下の２つの可能な形式のうち１つを有している。
【数１０２】
2020536473.tif 000105
【０２０９】
第１の形式において、ＰＡＹrは（必ずしも最大限ではない）支払集合であり、ＰＡＹr＝φであってよく、ｉはラウンドｒの潜在的リーダーである。（しかし、ｉはリーダーｌrでないことがある。これは実際にｌrが自身の信任値を秘匿したまま自身を明かさない場合に起きる。）
【０２１０】
第２の形式が生じるのは、ＢＡプロトコルのラウンドｒの実行に際して、全ての正直なプレーヤーが、アプリケーションで空ブロック
【数１０３】
2020536473.tif 000106
である既定値を出力するときである。（定義から、ＢＡプロトコルの可能な出力は、一般に⊥と表記される既定値を含んでいる。節３．２を参照されたい。）
【０２１１】
両方のケースで支払集合が空であるにもかかわらず、Ｂr＝（ｒ，φ，ＳＩＧi（Ｑr-1），Ｈ（Ｂr-1））と
【数１０４】
2020536473.tif 000107
は構文的に異なるブロックであって、２つの異なる状況で生じることに注意されたい。すなわち各々、「全てがＢＡプロトコルの実行で充分にスムーズに進行した」、及び「ＢＡプロトコルで何かまずいことが起きて既定値が出力された」。
【０２１２】
ここでブロックＢrの生成がＡｌｇｏｒａｎｄ’のラウンドｒでどのように進むかを直観的に説明する。最初の１ステップにおいて、各々の資格のあるプレーヤー、すなわち各プレーヤーｉ∈ＰＫr-kは自身が潜在的リーダーであるか否かを確認する。そうであれば、ｉは、自身がこれまで行った全ての支払いと現在のブロックチェーンＢ0，．．．，Ｂr-1を用いて最大限の支払集合
【数１０５】
2020536473.tif 000108
を非公開に用意するよう求められ、非公開に自身の候補ブロック
【数１０６】
2020536473.tif 000109
を構築する。すなわち、プレーヤーｉは
【数１０７】
2020536473.tif 000110
に第２の要素としてちょうど用意された支払集合を含めるだけでなく、第３の要素として自身の署名Ｑr-1、すなわち最終ブロックＢr-1の第３の要素も含める。最後に、プレーヤーｉは、自身のラウンドｒのステップ１のメッセージ
【数１０８】
2020536473.tif 000111
を拡散し、メッセージには（ａ）自身の候補ブロック
【数１０９】
2020536473.tif 000112
、（ｂ）自身の候補ブロックの自身の適当な署名（すなわち、
【数１１０】
2020536473.tif 000113
のハッシュの自身の署名、及び（ｃ）自身が実際にラウンドｒの潜在的検証者であることを証明する自身の信任値
【数１１１】
2020536473.tif 000114
が含まれる。
【０２１３】
（正直なｉが自身のメッセージ
【数１１２】
2020536473.tif 000115
を生成するまで、敵対者はｉが潜在的検証者であるとの手掛かりを有していない点に注意されたい。敵対者は、正直な潜在的リーダーを唆そうと欲したならば、正直なプレーヤーを無作為に唆す必要があろう。しかし、敵対者が
【数１１３】
2020536473.tif 000116
を見たならば、ｉの信任値を含んでいるため、ｉを知って唆すことができるものの、ウイルス的に拡散された
【数１１４】
2020536473.tif 000117
がシステム内の全てのユーザーに届くのを防ぐことはできない。）
【０２１４】
第２ステップにおいて、各々の選択された検証者ｊ∈ＳＶr,2はラウンドのリーダーを識別しようとする。具体的には、ｊは、自身が受信した正当なステップ１のメッセージに
【数１１５】
2020536473.tif 000118
に含まれるステップ１の信任値
【数１１６】
2020536473.tif 000119
を取り、それらの全てをハッシュ、すなわち
【数１１７】
2020536473.tif 000120
を計算し、ハッシュが辞書編成順に最小である信任値
【数１１８】
2020536473.tif 000121
を見つけて、
【数１１９】
2020536473.tif 000122
がラウンドｒのリーダーであるとみなす。
【０２１５】
考慮する各信任値がＱr-1のデジタル署名であること、ＳＩＧi（ｒ，１，Ｑr-1）がｉ及びＱr-1により一意に決定され、Ｈは無作為なオラクルである、従って各Ｈ（ＳＩＧi（ｒ，１，Ｑr-1）はラウンドｒの各潜在的リーダーｉに一意な無作為の長さ２５６ビットのストリングであることを想起されたい。
【０２１６】
上記から、２５６ビットストリングＱr-1自体が無作為且つ独立に選択されていれば、ラウンドｒの全ての潜在的リーダーのハッシュされた信任値も同様であろう。実際、全ての潜在的リーダーは明確であり、それらの信任値（実際に計算されているか否かに依らず）も同様である。更に、ラウンドｒの潜在的リーダーの集合は、ラウンドｒ−ｋのユーザーの無作為な部分集合であり、正直な潜在的リーダーｉは、ｉの信任値を含む自身のメッセージ
【数１２０】
2020536473.tif 000123
を常に適切に構築して拡散する。従って、正直なユーザーの割合はｈであるため、悪意のある潜在的リーダーが何をしようと（例：自身の信任値を明かすか又は隠す）、最小のハッシュされた潜在的リーダーの信任値は、ラウンドｒのリーダーｌrであることが必然的に全員に識別されている正直なユーザーのものである。従って、２５６ビットストリングＱr-1自体が無作為且つ独立に選択されていれば、正確に確率ｈで（ａ）リーダーｌrは正直であり、（ｂ）全ての正直なステップ２での検証者ｊに対してｌj＝ｌrである。
【０２１７】
実際には、ハッシュされた信任値は確かに無作為に選択されているが、無作為且つ独立に選択されなかったＱr-1に依存する。しかし、注意深い解析により、Ｑr-1が、あるラウンドのリーダーが、ｈに充分近い確率ｈ’すなわちｈ’＞ｈ2（１＋ｈ−ｈ2）で正直であることを保証できる程度に充分に不正操作ができないことが保証される。例えば、ｈ＝８０％ならばｈ’＝．７４２４である。
【０２１８】
ラウンドのリーダーを識別（リーダーｌrが正直な場合は正しく行われる）したならば、ステップ２検証者のタスクは、リーダーのブロックであると信じる初期値を用いてＢＡ*の実行を開始することである。実際、必要な通信量を最小化すべく、検証者ｊ∈ＳＶr,2は、ビザンチンプロトコルへの自身の入力値
【数１２１】
2020536473.tif 000124
として、しかしリーダー以外、及びブロックのハッシュすなわち
【数１２２】
2020536473.tif 000125
以外、ｌj（リーダーと見なされるユーザーｊ）から実際に受信したブロックＢjを使用しない。従って、ＢＡプロトコルの終了時点で、最後のステップの検証者は、所望のラウンドｒブロックＢrを計算せず、Ｈ（Ｂr）を計算（認証及び拡散）する。従って、Ｈ（Ｂr）はＢＡプロトコルの最後のステップの充分に多くの検証者によりデジタル署名されているため、システムのユーザーはＨ（Ｂr）が新規ブロックのハッシュであることが分かる。しかし、システムのユーザーはまた、敵対者が何をしようとも、実際に使用可能であることをプロトコルが保証するブロックＢr自体を検索（又は、実行は全く非同期であるため待機）しなければならない。
【０２１９】
非同期性及びタイミング
【数１２３】
2020536473.tif 000126
及び
【数１２４】
2020536473.tif 000127
は顕著な非同時性を有している。その理由は、拡散されているメッセージの配信を敵対者がスケジューリングする大きな自由度を有しているためである。また、１ラウンドにおけるステップの総数に上限が設定されているか否かに依らず、実際に行われたステップの数により寄与に分散がある。
【０２２０】
Ｂ0，．．．，Ｂr-1の証明を知ったならば直ちに、ユーザーｉはＱr-1を計算してラウンドｒで行動を開始し、ラウンドｒのあるステップｓで自身が潜在的リーダーであるか、又は検証者であるかを確認する。
【０２２１】
ｉがステップｓで行動しなければならないと仮定すれば、上述の非同時性の観点から、ｉは行動する前に充分な情報を有していることを確信すべく各種の戦略に依存する。
【０２２２】
例えば、ｉは、（
【数１２５】
2020536473.tif 000128
のように）前のステップの検証者から少なくとも所与の数のメッセージを受信するまで待つか、又は（
【数１２６】
2020536473.tif 000129
のように）前のステップの充分に多くの検証者のメッセージを受信することを確信すべく充分な時間待つことができる。
【０２２３】
シードＱr及び見直しパラメータｋ  理想的には、量Ｑrは、敵対者による不正操作が充分に防止されているだけで充分であるにもかかわらず、無作為且つ独立しているべきであることを想起されたい。
【０２２４】
一見したところ、Ｑr-1をＨ（ＰＡＹr-1）と一致するように選択することができる。しかし、基本的な解析により、悪意のあるユーザーはこの選択機構を悪用できることが分かる。（脚注６：発明者らはラウンドｒ−１の開始時点にいる。従って、Ｑr-2＝ＰＡＹr-2は公知であり、敵対者は、誰が自身の支配する潜在的リーダーであるかを非公開に知っている。敵対者がユーザーの１０％を支配し、且つ極めて高い確率で悪意のあるユーザーｗがラウンドｒ−１の潜在的リーダーであると仮定する。すなわち、Ｈ（ＳＩＧw（ｒ−２，１，Ｑr-2））が小さいため、正直な潜在的リーダーが実際にラウンドｒ−１のリーダーである可能性は極めて低いと仮定する。（秘密の暗号抽選機構を介して潜在的リーダーを選択するため、敵対者は誰が正直な潜在的リーダーであるかを知らないことを想起されたい。）敵対者は従って、所望の支払集合ＰＡＹ’を選択してラウンドｒ−１の公式支払集合にできる羨望的立場にある。しかし、敵対者はさらに多くのことができる。敵対者はまた、高い確率で、（＊）敵対者がどのようなＰＡＹrでも自由に選択できるように、悪意のあるユーザーの１人がラウンドｒのリーダーにもなることを保証できる。（以下同様。少なくとも長期間、すなわち、これらの高確率事象が実際に生起する限り。）これを保証すべく（＊）、敵対者は以下のように行動する。ＰＡＹ’を敵対者がラウンドｒ−１で好む支払集合とする。次いで、敵対者はＨ（ＰＡＹ’）を計算して、既に悪意のあるプレーヤーｚにとってＳＩＧz（ｒ，１，Ｈ（ＰＡＹ’））が特に小さいか否か、すなわち極めて高い確率でｚがラウンドｒのリーダーになるのに充分小さいか否かを確認する。これが当てはまるならば、敵対者はｗに、候補ブロックが
【数１２７】
2020536473.tif 000130
になるような選択をするように命令する。さもなければ、敵対者は、悪意のあるユーザーｚ（又はある固定されたユーザーｚでもよい）にとって
【数１２８】
2020536473.tif 000131
も特に小さくなるまで、他の２人の悪意のあるユーザーｘ及びｙに、互いに新規の支払い
【数１２９】
2020536473.tif 000132
を生成させ続ける。この実験は、極めて突然に停止する。停止したならば、敵対者はｗに候補ブロック
【数１３０】
2020536473.tif 000133
を提案するように頼む。）ある追加的な成果は、悪意のあるリーダーが極めて頻繁に現れることを保証すべく従来のブロック量に基づく他の多くの代替策が敵対者により容易に利用できることを示している。発明者らはその代わりに、敵対者による不正操作が不可能であることを証明できるように全く新たな量Ｑrを具体的且つ誘導的に定義する。すなわち、次式が成り立つ。
Ｂrが空ブロックでなければ
【数１３１】
2020536473.tif 000134
、空ブロックであれば
【数１３２】
2020536473.tif 000135
【０２２５】
Ｑrの上述の構造が機能する理由を以下に直観的に説明する。Ｑr-1が真に無作為且つ独立に選択されたものと一時的に仮定する。Ｑrもそうであろうか？ｌrが正直であれば答えは（大まかに言うと）ＹＥＳである。その理由は、
【数１３３】
2020536473.tif 000136
がランダム関数であるからである。しかしｌrに悪意のある場合、ＱrはＱr-1とｌrから一意に定義されない。Ｑrには少なくとも２個の別々の値がある。一方は
【数１３４】
2020536473.tif 000137
であり続け、他方はＨ（Ｑr-1，ｒ）である。第２の選択が多少任意であっても、第２の選択は絶対的に必須であることを最初に論じよう。その理由は、悪意のあるｌrは常に、全く異なる候補ブロックを第２ステップの正直な検証者に受信させることができるからである。（脚注７：例えば、説明を簡潔（しかし極端に）保つべく、「第２ステップの時間が満了しそうなときに」ｌrは各ユーザーｉに異なる候補ブロックＢiを直接電子メールで送ることができる。こうすれば、誰がステップ２の検証者であろうと、全く異なるブロックを受信するであろう。）一旦そうなれば、ラウンドｒのＢＡプロトコルを介して最終的に合意に達したブロックが既定のものとなり、従ってＱr-1の誰のデジタル署名も含まないようにすることを保証するのは容易である。しかし、システムは継続せねばならず、このためラウンドｒのリーダーが必要である。リーダーが自動的且つ公開された仕方で選択されたならば、敵対者は言うまでもなくリーダーを唆す。同じ処理を介して前のＱr-1で選択されたならば、ｌrは再びラウンドｒ＋１でリーダーとなる。具体的に同じであるが新たなＱ量、すなわちＨ（Ｑr-1，ｒ）に適用する秘密暗号抽選機構の使用を提案する。量をＨの出力とすることで出力が無作為であることが保証され、ｒをＨの第２の入力として含めることで、Ｈの他の全ての使用が単一入力又は少なくとも３入力を有している状態で、そのようなＱrが独立に選択されたことを「保証」する。再び、代替的なＱrの特定の選択は重要でなく、重要なのはｌrがＱrについて２つの選択肢を有し、従って悪意のある別のユーザーを次のリーダーにできるチャンスを２倍にできることである。
【０２２６】
Ｑrに対する任意選択は、悪意のあるｌrを支配する敵対者にとってより多いであろう。例えば、ｘ、ｙ及びｚを、
【数１３５】
2020536473.tif 000138
であるようなラウンドｒの３人の悪意のある潜在的リーダーとし、
【数１３６】
2020536473.tif 000139
が特に小さいとする。すなわち、
【数１３７】
2020536473.tif 000140
は全ての正直な潜在的リーダーのハッシュされた信任値よりも小さくなる好機がある。次いで、ｘに自身の信任値を隠すよう求めることにより、敵対者にはｙをラウンドｒ−１のリーダーにする好機がある。これは、敵対者にはＱrに対して別の任意選択肢すなわちＨ（ＳＩＧy（Ｑr-1），ｒ）があることを示唆する。同様に、敵対者は、ｚがラウンドｒ−１のリーダーになり、Ｑrに対して別の任意選択肢すなわちＨ（ＳＩＧz（Ｑr-1），ｒ）が得られるように、ｘとｙに信任値を明かさないよう求めることができる。
【０２２７】
しかしながら、言うまでもなく敵対者は正直な潜在的ユーザーのデジタル署名のハッシュを予測できないため、これら及び他の任意選択肢の各々が失敗する可能性はゼロではない。
【０２２８】
注意深い、マルコフ連鎖的解析により、敵対者がラウンドｒ−１でどのような任意選択を行っても、敵対者は、システムに新規ユーザーを投入できない限り、正直なユーザーがラウンドｒ＋４０のリーダーになる確率をｈよりも大幅に低下させることはできない。これが、ラウンドｒの潜在的リーダーがラウンドｒ−ｋで既に存在しているユーザーであることを要求する理由である。これは、ラウンドｒ−ｋで敵対者が、正直なユーザーがラウンドｒのリーダーになる確率を大幅に変えられないようにする１つの方法である。実際、敵対者がラウンドｒ−ｋからｒの間にシステムにどのようなユーザーを加えたとしても、ラウンドｒの潜在的リーダーに（より強い理由からリーダーに）なるには不適格である。従って、見直しパラメータｋは最終的にセキュリティパラメータである。（但し、節？？で見られるように、一種の「便利なパラメータ」でもあり得る。）
【０２２９】
短期鍵  発明者らのプロトコルの実行は無視できる確率を除いて分岐を生成できないが、敵対者は合法的ブロックｒが生成された後のｒ番目のブロックで分岐を生成することができた。
【０２３０】
大まかに言えば、Ｂrが生成されたならば、敵対者はラウンドｒの各ステップの検証者が誰であるか知っている。敵対者は従って、検証者全員を唆して新規ブロック
【数１３８】
2020536473.tif 000141
の証明を強いることができる。偽造ブロックは合法的ブロックの後でしか拡散できないため、注意を払っていたユーザーは騙されないであろう。（脚注８：主要なテレビネットワークのニュースアンカーを唆して、クリントン国務長官が直近の大統領選挙に勝利した様子を示すニュース映像を今日作成及び放送したとしよう。大多数の人はこれをデタラメと認識するであろう。だが昏睡から覚めた誰かが騙されるかもしれない。）にもかかわらず、
【数１３９】
2020536473.tif 000142
は構文的には正しく、その生成の防止が望まれる。
【０２３１】
新たな規則をその手段とする。本質的に、ラウンドｒのステップｓの検証者集合ＳＶr,sのメンバーは、短期公開鍵
【数１４０】
2020536473.tif 000143
を用いて自身のメッセージにデジタル署名する。これらの鍵は、使い捨てであり、対応する秘密鍵
【数１４１】
2020536473.tif 000144
は１回使えば破壊される。このようにして、後で検証者が唆された場合、敵対者は検証者が当初署名しなかったものには一切署名を強制することができない。
【０２３２】
当然、敵対者が新たな鍵
【数１４２】
2020536473.tif 000145
の計算が不可能であることを保証して、これがステップｓで使用する検証者ｉ∈ＳＶr,sの正当な短期鍵であることを正直なユーザーに納得させなければならない。
【０２３３】
４．２  表記、概念、及びパラメータの一般的概要
表記
・ｒ≧０：現在のラウンド番号。
・ｓ≧１：ラウンドｒの現在のステップ番号。
・Ｂr：ラウンドｒで生成されたブロック。
・ＰＫr：ラウンドｒ−１の終了までの、及びラウンドｒの開始時点での公開鍵の集合。
・Ｓr：ラウンドｒ−１の終了までの、及びラウンドｒの開始時点でのシステム状態。（脚注９：同期的でないシステムにおいて、「ラウンドｒ−１の終了」及び「ラウンドｒの開始」の表記は注意深く定義する必要がある。数学的には、ＰＫr及びＳrは、初期状態Ｓ0及びブロックＢ1，．．．，Ｂr-1から計算される。）
・ＰＡＹr：Ｂrに含まれる支払集合。
・ｌr：ラウンドｒのリーダー。ｌrはラウンドｒの支払集合ＰＡＹrを選択（及び次のＱrを決定）する。
・Ｑr：ラウンドｒのシード、すなわちラウンドｒの終了時に生成されてラウンドｒ＋１の検証者の選択に用いられる量（すなわちバイナリストリング）。Ｑrはブロック内支払集合からは独立していて、ｌrにより不正操作することはできない。
・ＳＶr,s：ラウンドｒのステップｓのために選択される検証者の集合。
・ＳＶr：ラウンドｒのために選択される検証者の集合であり、ＳＶr＝∪s≧1ＳＶr,s。
・ＭＳＶr,s及びＨＳＶr,s：各々ＳＶr,sで悪意のある検証者の集合及び正直な検証者の集合。ＭＳＶr,s∪ＨＳＶr,s＝ＳＶr,s且つＭＳＶr,s∩ＨＳＶr,s＝φ。
・
【数１４３】
2020536473.tif 000146
及び
【数１４４】
2020536473.tif 000147
：各々ＳＶr,1の潜在的リーダーの人数の期待値、及びＳＶr,sの検証者の人数の期待値、但しｓ＞１。
ｎ１＜＜ｎでことに注意されたい。その理由は、ＳＶr,1で少なくとも１個の正直なメンバー、但しｓ＞１に対して各ＳＶr,sの正直なメンバーの少なくとも多数を必要とするからである。
・ｈ∈（０，１）：２／３よりも大きい定数。ｈはシステムの正直さの比である。すなわち、用いる仮定に依存するが、各ＰＫrにおける正直なユーザー又は正直な資金の割合は少なくともｈである。
・Ｈ：無作為オラクルとしてモデル化された暗号ハッシュ関数。
・⊥：Ｈの出力と同じ長さの特別のストリング。
・Ｆ∈（０，１）：許容されるエラー確率を指定するパラメータ。確率≦Ｆは「無視できる」とみなされ、確率≧１−Ｆは「圧倒的」とみなされる。
・ｐh∈（０，１）：ラウンドｒのリーダーｌrが正直である確率。理想的にはＰh＝ｈ。敵対者が存在する場合、ｐhの値は解析で決定される。
・
【数１４５】
2020536473.tif 000148
：見直しパラメータ。すなわち、ラウンドｒ−ｋは、ラウンドｒの検証者を選択するラウンドであり、ＳＶr⊆ＰＫr-k。（脚注１０：厳密には、「ｒ−ｋ」は「ｍａｘ｛０，ｒ−ｋ｝」の筈である。）
・ｐ１∈（０，１）：ラウンドｒの第１ステップに対して、ラウンドｒ−ｋのユーザーが確率
【数１４６】
2020536473.tif 000149
でＳＶr,1に存在するように選択される。
・ｐ∈（０，１）：ラウンドｒの各ステップｓ＞１に対して、ラウンドｒ−ｋのユーザーが確率
【数１４７】
2020536473.tif 000150
でＳＶr,sに存在するように選択される。
・ＣＥＲＴr：Ｂrへの証明。ラウンドｒにおける適切な検証者からのＨ（Ｂr）のｔH署名の集合である。
・
【数１４８】
2020536473.tif 000151
は証明されたブロックである。
ユーザーｉがＢrを知るのは、証明されたブロックの両方の部分を有した（且つ検証に成功し）た場合である。異なるユーザーが見るＣＥＲＴrは異なり得る点に注意されたい。
・
【数１４９】
2020536473.tif 000152
：ユーザーｉがＢrを知る（ローカル）時間。Ａｌｇｏｒａｎｄプロトコルでは各ユーザーは自身の時計を有している。異なるユーザーの時計は同期している必要はないが、同じ速度を有していなければならない。解析目的のためのみ、基準クロックを考え、これに関するプレーヤーの時間を測定する。
・
【数１５０】
2020536473.tif 000153
及び
【数１５１】
2020536473.tif 000154
：各々ユーザーｉがラウンドｒのステップｓの実行を開始及び終了する（ローカル）時刻。
・Λ及びλ：本質的に、それぞれ、Ａｌｇｏｒａｎｄプロトコルのステップ１の実行に要する時間及び他の任意のステップの実行に要する時間の上限。
パラメータΛは単一の１ＭＢのブロックを拡散する時間の上限。
パラメータλはステップｓ＞１の検証者毎に１個の小さいメッセージを拡散する時間の上限。
Λ≦４λと仮定する。
【０２３４】
概念
・検証者選択。
各ラウンドｒ及びステップｓ＞１に対して
【数１５２】
2020536473.tif 000155
である。各ユーザーｉ∈ＰＫr-kは自身の長期の鍵を用いて非公開に自身の署名を計算してｉ∈ＳＶr,sであるか否かを判定する。ｉ∈ＳＶr,sならばＳＩＧi（ｒ，ｓ，Ｑr-1）はｉの（ｒ，ｓ，）信任値であり、簡潔に
【数１５３】
2020536473.tif 000156
と表記する。
ラウンドｒの第１ステップにおいて、ＳＶr,1と
【数１５４】
2020536473.tif 000157
は、ｐをｐ1で置換して同様に定義される。ＳＶr,1の検証者が潜在的リーダーである。
【０２３５】
・リーダー選択。
ユーザーｉ∈ＳＶr,1は、全ての潜在的リーダーｊ∈ＳＶr,1に対して
【数１５５】
2020536473.tif 000158
ならばラウンドｒのリーダーであり、ｌrと表記する。２人のプレーヤーの信任値のハッシュが、極めて稀な同点の場合、比較される都度、プロトコルは常に、潜在的リーダーの（長期公開鍵）に従い辞書編成順にタイブレークする。
定義により、プレーヤーｌrの信任値のハッシュ値もまた、ＰＫr-kの全てのユーザーの中で最も小さい。潜在的リーダーは、他の潜在的リーダーの信任値を見ることなく、自身がリーダーであるか否かを非公開に決めることができない点に注意されたい。
ハッシュ値は無作為に一様であるため、ＳＶr,1が空でなければ、ｌrは常に存在し、少なくとも確率ｈで正直である。パラメータｎ1は、各ＳＶr,1が圧倒的確率で非空であることを保証すべく充分に大きい。
【０２３６】
・ブロック構造。
非空ブロックは
【数１５６】
2020536473.tif 000159
の形式であり、空ブロックは
【数１５７】
2020536473.tif 000160
の形式である。
ラウンドで支払いが生じなければ、又はリーダーに悪意があれば、非空ブロックは依然として空の支払集合ＰＡＹrを含んでいてよい。しかし、非空ブロックとは、ｌrの属性、信任値
【数１５８】
2020536473.tif 000161
、及び
【数１５９】
2020536473.tif 000162
が全て適時に明かされていることを示唆する。プロトコルは、リーダーが正直ならば圧倒的確率でブロックが非空であることを保証する。
【０２３７】
・シードＱr。
Ｂrが非空ならば
【数１６０】
2020536473.tif 000163
、さもなければ
【数１６１】
2020536473.tif 000164
である。
【０２３８】
パラメータ
・各種パラメータ同士の関係。
−  ラウンドｒの検証者及び潜在的リーダーがＰＫr-kのユーザーから選択され、ｋは、敵対者がＦより高い確率でラウンドｒ−ｋ−１に戻ってｑr-1を予測できないように選択される。さもなければ、敵対者はラウンドｒ−ｋに悪意のあるユーザーを招き入れることができ、その全員がラウンドｒの潜在的リーダー／検証者になって、敵対者が望むステップｓでＳＶr,sに悪意のあるリーダー又は悪意のある多数派を有することに成功する。
−  各ラウンドｒのステップ１において、ｎ1は、圧倒的確率でＳＶr、1≠φであるように選択される。
・重要なパラメータの選択例。
−  Ｈの出力は長さ２５６ビットである。
−  ｈ＝８０％、ｎ1＝３５。
−  Λ＝１分及びλ＝１５秒。
・プロトコルの初期化。
プロトコルは、時刻０でｒ＝０を以て始まる。「Ｂ-1」又は、「ＣＥＲＴ-1」が存在しないため、構文的にＢ-1は第３の要素がＱ-1を指定する公開パラメータであり、全てのユーザーは時刻０におけるＢ-1を知っている。
【０２３９】
５
【数１６２】
2020536473.tif 000165
本節では、以下の仮定の下で機能する、Ａｌｇｏｒａｎｄ’のバージョンを構築する。
【０２４０】
ユーザーの大多数は正直という仮定：各ＰＫrのユーザーの２／３以上は正直である。
【０２４１】
節？？において、上述の仮定を、望ましい大部分の資金は正直という仮定で置換する仕方を示す。
【０２４２】
５．１  追加的な表記及びパラメータ
表記
・
【数１６３】
2020536473.tif 000166
：バイナリＢＡプロトコルにおけるステップの最大数であって３の倍数。
・Ｌr≦ｍ／３：各々の試行が確率
【数１６４】
2020536473.tif 000167
で１であって最大ｍ／３回の試行がある場合に１を得るまでに要するベルヌーイ試行の回数を表す確率変数。全ての試行が失敗したならば
【数１６５】
2020536473.tif 000168
である。ＬrはブロックＢrの生成に要する時間に上限を設けるために用いられる。
・
【数１６６】
2020536473.tif 000169
：プロトコルの終了条件で必要とされ署名の数。
・ＣＥＲＴr：Ｂrへの証明。ラウンドｒにおける正当な検証者からのＨ（Ｂr）のｔH個の署名の集合である。
【０２４３】
パラメータ
・各種のパラメータ同士の関係。
−  ラウンドｒの各ステップｓ＞１に対して、ｎは圧倒的確率で下記のように選択される。
｜ＨＳＶr,s｜＞２｜ＭＳＶr,s｜且つ｜ＨＳＶr,s｜＋４｜ＭＳＶr,s｜＜２ｎ
ｈの値が１に近いほど、ｎは小さくなければならない。特に、圧倒的確率で所望の状態が保たれることを保証すべくチャーノフ境界（の変型例）を用いる。
−  ｍは、圧倒的確率でＬr＜ｍ／３であるように選択される。
・重要なパラメータの選択例。
−  Ｆ＝１０-12。
−  ｎ≒１５００、ｋ＝４０且つｍ＝１８０。
【０２４４】
５．２
【数１６７】
2020536473.tif 000170
における短期鍵の実装
既に述べたように、検証者ｉ∈ＳＶrが、使用後直ちに破壊する短期秘密鍵
【数１６８】
2020536473.tif 000171
を用いて、短期公開鍵
【数１６９】
2020536473.tif 000172
に関して、ラウンドｒでステップｓの自身のメッセージ
【数１７０】
2020536473.tif 000173
にデジタル署名することが望ましい。従って、
【数１７１】
2020536473.tif 000174
が実際に
【数１７２】
2020536473.tif 000175
に対するｉの署名の検証に用いられる鍵であることを全てのユーザーが検証できることを保証する効率的な方法が必要である。属性に基づく署名スキームを（知識の及ぶ限りで）新たに用いることでこれを行う。
【０２４５】
高いレベルでは、このようなスキームにおいて、中央当局Ａは公開マスター鍵ＰＭＫ、及び対応する秘密マスター鍵ＳＭＫを生成する。プレーヤーＵの属性Ｕが与えられると、ＡはＳＭＫを介して公開鍵Ｕに対する秘密署名鍵ｓｋUを計算して、ＵにｓｋUを非公開に与える（実際、属性に基づくデジタル署名スキームにおいて、ユーザーＵの公開鍵はＵ自身である！）このため、Ａが、デジタル署名を生成可能にしたいが、計算された秘密鍵を一切保持したくないユーザーの秘密鍵を計算した後でＳＭＫを破壊したならば、Ｕは公開鍵Ｕに関してメッセージにデジタル署名することができる唯一のユーザーとなる。従って、「Ｕの名前」を知る者は誰でも自動的にＵの公開鍵を知り、従ってＵの署名を検証することができる（恐らく、公開マスター鍵ＰＭＫも使用して）。
【０２４６】
発明者のアプリケーションにおいて、当局Ａはユーザーｉであり、全ての可能なユーザーＵの集合は、例えばＳ＝｛ｉ｝×｛ｒ’，．．．，ｒ’＋１０6｝×｛１，．．．，ｍ＋３｝におけるラウンドステップペア（ｒ，ｓ）と一致し、ｒ’は所与のラウンド、ｍ＋３は１ラウンド内に生起し得るステップ数の上限である。これにより、
【数１７３】
2020536473.tif 000176
であるため、ｉの署名
【数１７４】
2020536473.tif 000177
を見ている全員が、ｒ’に続く最初の１００万ラウンドｒについて、圧倒的確率で直ちにこれを検証することができる。
【０２４７】
換言すれば、ｉは最初にＰＭＫ及びＳＭＫを生成する。次いでｉは、ＰＭＫが任意のラウンドｒ∈［ｒ’，ｒ’＋１０6］のｉのマスター公開鍵であることを公表し、ＳＭＫを用いて各３つ組（ｉ、ｒ、ｓ）∈Ｓに対する秘密鍵
【数１７５】
2020536473.tif 000178
を非公開に生成して保存する。これが行われたならばＳＭＫを破壊する。自身がＳＶr,sの一部でないと判定したならば、ｉは（プロトコルがラウンドｒのステップｓのいかなるメッセージの認証を求めないため）
【数１７６】
2020536473.tif 000179
を放置する。さもなければ、ｉは最初に
【数１７７】
2020536473.tif 000180
を用いて自身のメッセージ
【数１７８】
2020536473.tif 000181
にデジタル署名を行い、次いで
【数１７９】
2020536473.tif 000182
を破壊する。
【０２４８】
ｉが最初にシステムに参加した際に自身の最初の公開マスター鍵を公表できることに注意されたい。すなわち、（ラウンドｒ’又はｒ’に近いラウンドで）ｉをシステムに参加させる同じ支払い
【数１８０】
2020536473.tif 000183
はまた、ｉの求めに従い、例えば（ＰＭＫ，［ｒ’，ｒ’＋１０6］）の形式のペアを含めることにより、任意のラウンドｒ∈［ｒ’，ｒ’＋１０6］用のｉの公開マスター鍵がＰＭＫであることを指定し得る。
【０２４９】
また、１ラウンドに１分かかると仮定すれば、ｍ＋３が１ラウンドにおけるステップの最大数であるため、そのように生成されたｉの短期鍵の退避場所が約２年間保持されることに注意されたい。同時に、これらの短期秘密鍵をｉが生成するのにさほど長い時間かからない。３２Ｂ鍵を有する楕円曲線に基づくシステムを用いて、各々の秘密鍵は数マイクロ秒で計算される。従って、ｍ＋３＝１８０であれば、全ての１８０Ｍ秘密鍵を１時間未満で計算することができる。
【０２５０】
現在のラウンドがｒ’＋１０6に近づいている場合、ｉは次の１００万ラウンドを扱うために新規ペア（ＰＭＫ’，ＳＭＫ’）を生成して、例えば、ＳＩＧi（ＰＭＫ’，［ｒ’＋１０6+１，ｒ’＋２・１０6＋１］）を別々の「取引」として又は支払いの一部である何らかの追加的な情報として新規ブロックに入力させることにより、自身の短期鍵の次の退避場所がどこであるかを通知する。こうすることで、ｉは次の１００万ラウンドにおけるｉの短期署名を検証するためにＰＭＫ’を用いる必要があることを全員に通知する。以下同様。
（上述の基本的アプローチに従い、属性に基づく署名を用いることなく短期鍵を実装する他の方法が確かに可能であることに注意されたい。例えばマークル木を介して可能である。）（脚注１１：本方法において、ｉは、例えば｛ｒ’，．．．，ｒ’＋１０6｝×｛１，．．．，ｍ＋３｝における各ラウンドステップペア（ｒ，ｓ）の公開秘密鍵ペア
【数１８１】
2020536473.tif 000184
を生成する。次いでこれらの公開鍵を正準的に順序付けて、ｊ番目の公開鍵をマークル木のｊ番目の葉に保存し、ルート値Ｒiを計算して公表する。鍵
【数１８２】
2020536473.tif 000185
に対するメッセージに署名したい場合、ｉは実際の署名だけでなく、Ｒiに対する
【数１８３】
2020536473.tif 000186
の認証経路を提供する。この認証経路もまた、
【数１８４】
2020536473.tif 000187
がｊ番目の葉に保存されていることを証明することに注意されたい。この考えから、他の詳細事項も容易に想到されよう。）
【０２５１】
短期鍵を実装する他の方法も、例えばマークル木を介して、もちろん可能である。
【０２５２】
５．３
【数１８５】
2020536473.tif 000188
のステップとＢＡ*のステップのマッチング
上述のように、
【数１８６】
2020536473.tif 000189
の１ラウンドは最大ｍ＋３ステップを有している。
【０２５３】
ステップ１。本ステップにおいて、各々の潜在的リーダーｉは自身の候補ブロック
【数１８７】
2020536473.tif 000190
を自身の信任値
【数１８８】
2020536473.tif 000191
と共に計算して拡散する。
この信任値が明示的にｉを識別することを想起されたい。その理由は
【数１８９】
2020536473.tif 000192
だからである。
【０２５４】
潜在的検証者ｉはまた、自身のメッセージの一部として、
【数１９０】
2020536473.tif 000193
の自身の適当なデジタル署名も拡散する。支払い又は信任値を扱わないため、ｉのこの署名は自身の短期公開鍵
【数１９１】
2020536473.tif 000194
と関連している。すなわち
【数１９２】
2020536473.tif 000195
を拡散する。
【０２５５】
慣例を前提として、
【数１９３】
2020536473.tif 000196
及び
【数１９４】
2020536473.tif 000197
を拡散するのではなく、ｉは
【数１９５】
2020536473.tif 000198
を拡散することができた。しかし、発明者らの解析では
【数１９６】
2020536473.tif 000199
への明示的なアクセスを有する必要がある。
【０２５６】
ステップ２。本ステップにおいて、各検証者ｉは、ハッシュされた信任値が最も小さい潜在的リーダーとして
【数１９７】
2020536473.tif 000200
を、及び
【数１９８】
2020536473.tif 000201
が提案するブロックとして
【数１９９】
2020536473.tif 000202
を設定する。効率の観点から、直接Ｂrにではなく、Ｈ（Ｂr）に同意したいため、ｉは、初期値を
【数２００】
2020536473.tif 000203
としてＢＡ*の第１ステップで拡散したであろうメッセージを拡散する。すなわち、
【数２０１】
2020536473.tif 000204
を、無論それに短期署名した後で、拡散する。（すなわち、この場合は
【数２０２】
2020536473.tif 000205
である正当な短期公開鍵に関して署名した後で。）
無論、ｉは自身の信任値も送信する。
【０２５７】
ＢＡ*の第１ステップが、等級化コンセンサスプロトコルＧＣの第１ステップを含んでいるため、Ａｌｇｏｒａｎｄ’のステップ２はＧＣの第１ステップに対応している。
【０２５８】
ステップ３。本ステップにおいて、各検証者ｉ∈ＳＶr,2はＢＡ*の第２ステップを実行する。すなわち、ＧＣの第２ステップで送ったであろうものと同じメッセージを送る。再び、ｉのメッセージは短期署名されており、ｉの信任値が伴っている。（以後、検証者が短期的に自身のメッセージに署名すると共に自身の信任値を拡散するとの表現を割愛する。）
【０２５９】
ステップ４。本ステップにおいて、全ての検証者ｉ∈ＳＶr,4は、ＧＣ（vi，ｇi）の出力を計算し、ＢＡ*の第３ステップで、すなわちＢＢＡ*の第１ステップで、ｇi＝２ならば初期ビットを０、さもなければ１として送ったであろうものと同じメッセージに短期署名して送る。
【０２６０】
ステップｓ＝５，．．．，ｍ＋２。このようなステップは、仮に到達したならば、ＢＡ*のステップｓ−１に、従ってＢＢＡ*のステップｓ−３に対応している。
【０２６１】
発明者らの拡散モデルは充分に非同期であるため、このようなステップｓの途中で、ブロックＢrが既に選択されていることを証明する情報が検証者ｉ∈ＳＶr,sに到達している可能性を考慮しなければならない。この場合、ｉはＡｌｇｏｒａｎｄ’のラウンドｒの自身の実行を停止して、自身のラウンド（ｒ＋１）命令の実行を開始する。
【０２６２】
従って、ＢＢＡ*のステップｓ−３に対応する命令に加えて、検証者ｉ∈ＳＶr,sの命令は、ＢＢＡ*の実行が前のステップｓ’で停止されたか否かの確認を含んでいる。ＢＢＡ*が停止できるのはコインが０に固定されたステップ又はコインが１に固定されたステップだけであるため、命令は以下を区別する。
Ａ（終了条件０）：ｓ’−２≡０ｍｏｄ３、又は
Ｂ（終了条件１）：ｓ’−２≡１ｍｏｄ３。
【０２６３】
実際に、ケースＡにおいて、ブロックＢrは非空であり、従って、ｉが適切な証明ＣＥＲＴrと共にＢrを適切に再構築することを保証するには追加的な命令が必要である。ケースＢにおいて、ブロックＢrは空であり、従ってｉは
【数２０３】
2020536473.tif 000206
を設定して、ＣＥＲＴrを計算するよう命令される。
【０２６４】
ステップｓを実行する間、ブロックＢrが既に生成されたいかなる証拠もｉが認識しなければ、ｉはＢＢＡ*のステップｓ−３で送ったであろうものと同じメッセージを送る。
【０２６５】
ステップｍ＋３。ステップｍ＋３の実行中に、ブロックＢrが前のステップｓ’で既に生成されていたことをｉ∈ＳＶr,m+3が認識したならば、正に上で述べたように進行する。
【０２６６】
さもなければ、ＢＢＡ*のステップｍで送っていたであろうものと同じメッセージを送るのではなく、ｉは、自身が有する情報に基づいて、Ｂr及び対応する証明ＣＥＲＴrを計算するよう命令される。
【０２６７】
実際、１ラウンドの合計ステップ数の上限をｍ＋３としたことを想起されたい。
【０２６８】
５．４  実際のプロトコル
ラウンドｒの各ステップｓで、検証者ｉ∈ＳＶr,sが自身の長期公開鍵及び秘密鍵のペアを用いて、ケースｓ＝１でのＳＩＧi（Ｑr-1）と共に自身の信任値
【数２０４】
2020536473.tif 000207
を生成することを想起されたい。検証者ｉは、自身の短期秘密鍵
【数２０５】
2020536473.tif 000208
を用いて自身の（ｒ，ｓ）メッセージ
【数２０６】
2020536473.tif 000209
に署名する。簡潔のため、ｒとｓが明らかな場合、ラウンドｒのステップｓにおける値ｘのｉの適切な短期署名を表記するのに
【数２０７】
2020536473.tif 000210
ではなくｅｓｉｇi（ｘ）と書き、（ｉ，ｘ，ｅｓｉｇi（ｘ））を表記するのに
【数２０８】
2020536473.tif 000211
ではなくＥＳＩＧi（ｘ）と書く。
【０２６９】
ステップ１：ブロック提案
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉは、Ｂr-1を知ったならば直ちにラウンドｒの自身のステップ１を開始する。
・ユーザーｉはＢr-lの第３の要素からＱr-1を計算してｉ∈ＳＶr,1であるか否かを確認する。
・ｉ
2020536473.tif 000212
ＳＶr,1ならば、直ちにステップ１の自身の実行を停止する。
・ｉ∈ＳＶr,1、すなわちｉが潜在的リーダーならば、それまで自身に拡散してきたラウンドｒの支払いを回収し、それらから最大限の支払集合
【数２０９】
2020536473.tif 000213
を計算する。次に、自身の「候補ブロック」
【数２１０】
2020536473.tif 000214
を計算する。最後に、メッセージ
【数２１１】
2020536473.tif 000215
を計算して、自身の短期秘密鍵
【数２１２】
2020536473.tif 000216
を破壊し、次いで
【数２１３】
2020536473.tif 000217
を拡散する。
【０２７０】
注記。実際には、ステップ１の大域的実行を短縮するには、（ｒ−１）メッセージを選択的に拡散することが重要である。すなわち、システム内の全てのユーザーｉ毎に、プレーヤーｉは最初に受信して検証に成功した（脚注１２：すなわち、全ての署名は正当であって、ブロックとそのハッシュは両方とも有効であるが、ｉは含まれた支払集合が提案者にとって最大であるか否かを確認しない。）（ｒ−１）メッセージを通常の通りに拡散する。プレーヤーｉが受信して検証に成功した他の全ての（ｒ−１）メッセージの場合、含まれる信任値のハッシュ値が、それまで受信して検証に成功した全ての（ｒ−１）メッセージに含まれる信任値のハッシュ値の最も小さいものである場合にだけ拡散する。更に、Ｇｅｏｒｇｉｏｓ  Ｖｌａｃｈｏｓが提言するように、各々の潜在的リーダーｉは、自身の信任値
【数２１４】
2020536473.tif 000218
もまた別個に拡散することが有用である。これらの小さいメッセージはブロックより速く移動し、含まれる信任値が小さいハッシュ値を有している
【数２１５】
2020536473.tif 000219
の適時な拡散を保証する一方、大きいハッシュ値を有するものを素早く消失させる。
【０２７１】
ステップ２：等級化コンセンサスプロトコルＧＣの第１ステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップ２を開始する。
・ユーザーｉはＢr-1の第３の要素からＱr-1を計算してｉ∈ＳＶr,2であるか否かを確認する。
・ｉ
2020536473.tif 000220
ＳＶr,2ならば、ｉは直ちにステップ２の自身の実行を停止する。
・ｉ∈ＳＶr,2ならば、ある長さの時間
【数２１６】
2020536473.tif 000221
待機した後でｉは以下のように行動する。
１．検証に成功した（ｒ，ｌ）メッセージの一部である全ての信任値
【数２１７】
2020536473.tif 000222
に対して
【数２１８】
2020536473.tif 000223
であるようなユーザーｌを見つける。（脚注１３：本質的に、ユーザーｉは、ラウンドｒのリーダーがユーザーｌであると非公開に決定する。）
２．ｉがｌから有効なメッセージ
【数２１９】
2020536473.tif 000224
（脚注１４）を受信していれば、ｉは
【数２２０】
2020536473.tif 000225
を、さもなければ
【数２２１】
2020536473.tif 000226
を設定する。（脚注１４：再び、プレーヤーｌの署名及びハッシュは全て検証に成功しており、
【数２２２】
2020536473.tif 000227
における
【数２２３】
2020536473.tif 000228
はラウンドｒの有効な支払集合であるが、ｉは
【数２２４】
2020536473.tif 000229
がｌに対して最大であるか否かを確認しない。）
３．ｉは、メッセージ
【数２２５】
2020536473.tif 000230
を計算して、自身の短期秘密鍵
【数２２６】
2020536473.tif 000231
を破壊し、次いで
【数２２７】
2020536473.tif 000232
を拡散する。（脚注１５：メッセージ
【数２２８】
2020536473.tif 000233
は、プレーヤーｉが
【数２２９】
2020536473.tif 000234
を次ブロックのハッシュであるとみなすか、又は次ブロックが空であるとみなすかを通知する。）
【０２７２】
ステップ３：ＧＣの第２ステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップ３を開始する。
・ユーザーｉはＢr-1の第３の要素からＱr-1を計算してｉ∈ＳＶr,3であるか否かを確認する。
・ｉ
2020536473.tif 000235
ＳＶr,3ならば、ｉは直ちにステップ３の自身の実行を停止する。
・ｉ∈ＳＶr,3ならば、ある長さの時間
【数２３０】
2020536473.tif 000236
待機した後でｉは以下のように行動する。
１．値ｖ’≠⊥が存在して、受信した全ての有効なメッセージ
【数２３１】
2020536473.tif 000237
のうち、２／３よりも多くが
【数２３２】
2020536473.tif 000238
の形式で一切矛盾しない（脚注１６）ならば、メッセージ
【数２３３】
2020536473.tif 000239
を計算する。さもなければ
【数２３４】
2020536473.tif 000240
を計算する（脚注１６：すなわち、プレーヤーｊから、ＥＳＩＧj（ｖ’）及び異なるＥＳＩＧj（ｖ”）を各々含む２個の有効なメッセージを受信していない。これ以降、後で定義する終了条件を除き、正直なプレーヤーが所与の形式のメッセージを望む都度、互いに矛盾するメッセージは決してカウントされず、有効であるともみなされない。）
２．ｉは自身の短期秘密鍵
【数２３５】
2020536473.tif 000241
を破壊し、次いで
【数２３６】
2020536473.tif 000242
を拡散する。
【０２７３】
ステップ４：ＧＣの出力及びＢＢＡ*の第１ステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップ４を開始する。
・ユーザーｉはＢr-1の第３の要素からＱr-1を計算してｉ∈ＳＶr,4であるか否かを確認する。
・ｉ
2020536473.tif 000243
ＳＶr,4ならば、ｉは直ちにステップ４の自身の実行を停止する。
・ｉ∈ＳＶr,4ならば、ある長さの時間
【数２３７】
2020536473.tif 000244
待機した後でｉは以下のように行動する。
１．ｖi及びｇi、すなわちＧＣの出力を以下のように計算する。
（ａ）値ｖ’≠⊥が存在して、受信した全ての有効なメッセージ
【数２３８】
2020536473.tif 000245
のうち、２／３よりも多くが
【数２３９】
2020536473.tif 000246
の形式であるならば
【数２４０】
2020536473.tif 000247
及び
【数２４１】
2020536473.tif 000248
を設定する。
（ｂ）さもなければ、値ｖ’≠⊥が存在して、受信した全ての有効なメッセージ
【数２４２】
2020536473.tif 000249
のうち、１／３よりも多くが
【数２４３】
2020536473.tif 000250
の形式であるならば
【数２４４】
2020536473.tif 000251
及び
【数２４５】
2020536473.tif 000252
を設定する。（脚注１７：ケース（ｂ）のｖ’が存在するならば、一意でなければならないことを証明できる。）
（ｃ）さもなければ、
【数２４６】
2020536473.tif 000253
及び
【数２４７】
2020536473.tif 000254
を設定する。
２．ｂiすなわちＢＢＡ*の入力を以下のように計算する。
ｇi＝２ならば
【数２４８】
2020536473.tif 000255
、さもなければ
【数２４９】
2020536473.tif 000256
３．メッセージ
【数２５０】
2020536473.tif 000257
を計算して、自身の短期秘密鍵
【数２５１】
2020536473.tif 000258
を破壊し、次いで
【数２５２】
2020536473.tif 000259
を拡散する。
【０２７４】
ステップｓ，５≦ｓ≦ｍ＋２，ｓ−２≡０ｍｏｄ３：ＢＢＡ*のコインが０に固定されたステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップｓを開始する。
・ユーザーｉはＢr-1の第３の要素からのＱr-1を計算してｉ∈ＳＶr,sであるか否かを確認する。
・ｉ
2020536473.tif 000260
ＳＶr,sならば、ｉは直ちにステップｓの自身の実行を停止する。
・ｉ∈ＳＶr,sならば、ｉは以下のように行動する。
−  ある長さの時間
【数２５３】
2020536473.tif 000261
が経過するまで待機する。
−  終了条件０：このように待機する間の任意の時点で、ストリングｖ≠⊥が存在し、及び以下のようなステップｓ’すなわち、
（ａ）５≦ｓ’≦ｓ，ｓ’−２≡０ｍｏｄ３、すなわちステップｓ’はコインが０に固定されたステップであり、
（ｂ）ｉは少なくとも
【数２５４】
2020536473.tif 000262
個の有効なメッセージ
【数２５５】
2020536473.tif 000263
を受信しており（脚注１８：プレーヤーｊからのそのようなメッセージは、たとえプレーヤーｉがｌに署名しているｊからもメッセージを受信していた場合であっても数えられる。終了条件１と同様の事項。解析に示すように、これは時間λ内に全ての正直なユーザーが互いからＢrを区別することを保証するために行われる。）、
（ｃ）ｉは１個の有効なメッセージ
【数２５６】
2020536473.tif 000264
但し
【数２５７】
2020536473.tif 000265
を受信している
が存在する場合、ｉは何も拡散することなく直ちにステップｓ（及び実際にはラウンドｒ）の自身の実行を停止して、
【数２５８】
2020536473.tif 000266
を設定し、自身のＣＥＲＴrをサブステップ（ｂ）のメッセージ
【数２５９】
2020536473.tif 000267
の集合となるように設定する（脚注１９：ユーザーｉは現在Ｂrを知っており、自身のラウンドｒは終了する。ユーザーｉは依然として一般ユーザーとしてメッセージの拡散を支援するが、（ｒ，ｓ）検証者としては一切拡散を開始しない。特に、自身のＣＥＲＴrで全てのメッセージの拡散を支援しており、これはプロトコルにとって充分である。ユーザーｉはバイナリＢＡプロトコルに対して
【数２６０】
2020536473.tif 000268
も設定しなければならないが、いずれにせよｂiはこの場合必要とされないことに注意されたい。全ての将来的な命令についても同様である。）
−  終了条件１：このように待機する間の任意の時点で、以下のようなステップｓ’すなわち、
（ａ’）６≦ｓ’≦ｓ，ｓ’−２≡１ｍｏｄ３、すなわちステップｓ’はコインが１に固定されたステップであり、
（ｂ’）ｉは少なくともｔH個の有効なメッセージ
【数２６１】
2020536473.tif 000269
を受信している（脚注２０：この場合、ｖjが何であろうとかまわない。）
が存在する場合、ｉは何も拡散することなく直ちにステップｓ（及び実際にはラウンドｒ）の自身の実行を停止して、
【数２６２】
2020536473.tif 000270
を設定し、自身のＣＥＲＴrをサブステップ（ｂ’）のメッセージ
【数２６３】
2020536473.tif 000271
の集合となるように設定する。
−  さもなければ、待機終了時点でユーザーｉは以下を実行する。
受信した全ての有効な
【数２６４】
2020536473.tif 000272
の第２の要素におけるｖ’jの多数票になるようにｖiを設定する。
【０２７５】
以下のようにｂｉを計算する。
受信した全ての有効な
【数２６５】
2020536473.tif 000273
の２／３より多くが
【数２６６】
2020536473.tif 000274
の形式であれば、
【数２６７】
2020536473.tif 000275
を設定する。
さもなければ、受信した全ての有効な
【数２６８】
2020536473.tif 000276
の２／３より多くが
【数２６９】
2020536473.tif 000277
の形式であれば、
【数２７０】
2020536473.tif 000278
を設定する。
さもなければ
【数２７１】
2020536473.tif 000279
を設定する。
【０２７６】
メッセージ
【数２７２】
2020536473.tif 000280
を計算して、自身の短期秘密鍵
【数２７３】
2020536473.tif 000281
を破壊し、次いで
【数２７４】
2020536473.tif 000282
を拡散する。
【０２７７】
ステップｓ、６≦ｓ≦ｍ＋２，ｓ−２≡１ｍｏｄ３：ＢＢＡ*のコインが１に固定されたステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップｓを開始する。
・ユーザーｉはＢr-1の第３の要素からのＱr-1を計算してｉ∈ＳＶr,sであるか否かを確認する。
・ｉ
2020536473.tif 000283
ＳＶr,sならば、ｉは直ちにステップｓの自身の実行を停止する。
・ｉ∈ＳＶr,sならば、ｉは以下を実行する。
−  ある長さの時間
【数２７５】
2020536473.tif 000284
が経過するまで待機する。
−  終了条件０：コインが０に固定されたステップと同じ命令。
−  終了条件１：コインが０に固定されたステップと同じ命令。
−  さもなければ、待機終了時点でユーザーｉは以下を実行する。
受信した全ての有効な
【数２７６】
2020536473.tif 000285
の第２の要素におけるｖ’jの多数票になるようにｖiを設定する。
【０２７８】
以下のようにｂｉを計算する。
受信した全ての有効な
【数２７７】
2020536473.tif 000286
の２／３より多くが
【数２７８】
2020536473.tif 000287
の形式であれば、
【数２７９】
2020536473.tif 000288
を設定する。
さもなければ、受信した全ての有効な
【数２８０】
2020536473.tif 000289
の２／３より多くが
【数２８１】
2020536473.tif 000290
の形式であれば、
【数２８２】
2020536473.tif 000291
を設定する。
さもなければ
【数２８３】
2020536473.tif 000292
を設定する。
【０２７９】
メッセージ
【数２８４】
2020536473.tif 000293
を計算して、自身の短期秘密鍵
【数２８５】
2020536473.tif 000294
を破壊し、次いで
【数２８６】
2020536473.tif 000295
を拡散する。
【０２８０】
ステップｓ，７≦ｓ≦ｍ＋２，ｓ−２≡２ｍｏｄ３：ＢＢＡ*のコインを本当に投げたステップ
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップｓを開始する。
・ユーザーｉはＢr-1の第３の要素からのＱr-1を計算してｉ∈ＳＶr,sであるか否かを確認する。
・ｉ
2020536473.tif 000296
ＳＶr,sならば、ｉは直ちにステップｓの自身の実行を停止する。
・ｉ∈ＳＶr,sならば、ｉは以下を実行する。
−  ある長さの時間
【数２８７】
2020536473.tif 000297
が経過するまで待機する。
−  終了条件０：コインが０に固定されたステップと同じ命令。
−  終了条件１：コインが０に固定されたステップと同じ命令。
−  さもなければ、待機終了時点でユーザーｉは以下を実行する。
受信した全ての有効な
【数２８８】
2020536473.tif 000298
の第２の要素におけるｖ’jの多数票になるようにｖiを設定する。
【０２８１】
以下のようにｂｉを計算する。
受信した全ての有効な
【数２８９】
2020536473.tif 000299
の２／３より多くが
【数２９０】
2020536473.tif 000300
の形式であれば、
【数２９１】
2020536473.tif 000301
を設定する。
さもなければ、受信した全ての有効な
【数２９２】
2020536473.tif 000302
の２／３より多くが
【数２９３】
2020536473.tif 000303
の形式であれば、
【数２９４】
2020536473.tif 000304
を設定する。
さもなければ、
【数２９５】
2020536473.tif 000305
を、有効なメッセージ
【数２９６】
2020536473.tif 000306
を受信した送信元である（ｒ，ｓ−１）検証者の集合とする。
【数２９７】
2020536473.tif 000307
を設定する。
【０２８２】
メッセージ
【数２９８】
2020536473.tif 000308
を計算して、自身の短期秘密鍵
【数２９９】
2020536473.tif 000309
を破壊し、次いで
【数３００】
2020536473.tif 000310
を拡散する。
【０２８３】
ステップｍ＋３：ＢＢＡ*の最後のステップ
（脚注２１：圧倒的な確率でＢＢＡ*が本ステップの前に終了しているが、完全性を求めて本ステップを指定する。）
全てのユーザーｉ∈ＰＫr-kへの命令：ユーザーｉはＢr-1を知ったならば直ちにラウンドｒの自身のステップｍ＋３を開始する。
・ユーザーｉはＢr-1の第３の要素からのＱr-1を計算してｉ∈ＳＶr,m+3であるか否かを確認する。
・ｉ
2020536473.tif 000311
ＳＶr,m+3ならば、ｉは直ちにステップｍ＋３の自身の実行を停止する。
・ｉ∈ＳＶr,m+3ならば、ｉは以下を実行する。
−  ある長さの時間
【数３０１】
2020536473.tif 000312
が経過するまで待機する。
−  終了条件０：コインが０に固定されたステップと同じ命令。
−  終了条件１：コインが０に固定されたステップと同じ命令。
−  さもなければ、待機終了時点でユーザーｉは、以下を実行する。
【数３０２】
2020536473.tif 000313
及び
【数３０３】
2020536473.tif 000314
を設定する。
メッセージ
【数３０４】
2020536473.tif 000315
を計算して、自身の短期秘密鍵
【数３０５】
2020536473.tif 000316
を破壊し、次いで
【数３０６】
2020536473.tif 000317
を拡散してＢrを証明する。（脚注２２：ステップｍ＋３からの証明はＥＳＩＧi（ｏｕｔi）を含んでいなくてもよい。これを含めるのは均一性のためだけである。証明は現在、どのステップで生成されたかに依らず均一な形式を有している。）
【０２８４】
非検証者によるラウンドｒブロックの再構築
システム内の全てのユーザーｉへの命令：ユーザーｉはＢr-1を知ったならば直ちに自身のラウンドｒを開始し、以下のようなブロック情報を待つ。
−  このように待機する間の任意の時点で、ストリングｖ、及び以下のようなステップｓ’すなわち
（ａ）５≦ｓ’≦ｍ＋３但しｓ’−２≡０ｍｏｄ３
（ｂ）ｉは、少なくともｔH個の有効なメッセージ
【数３０７】
2020536473.tif 000318
を受信しており、
（ｃ）ｉは１個の有効なメッセージ
【数３０８】
2020536473.tif 000319
但し
【数３０９】
2020536473.tif 000320
を受信している
が存在する場合、ｉは直ちにラウンドｒの自身の実行を停止して、
【数３１０】
2020536473.tif 000321
を設定し、自身のＣＥＲＴrをサブステップ（ｂ）のメッセージ
【数３１１】
2020536473.tif 000322
の集合となるように設定する。
【０２８５】
−  このように待機する間の任意の時点で、以下のようなステップｓ’すなわち、
（ａ’）６≦ｓ’≦ｍ＋３但しｓ’−２≡１ｍｏｄ３
（ｂ’）ｉは少なくともｔH個の有効なメッセージ
【数３１２】
2020536473.tif 000323
を受信している
が存在する場合、ｉは直ちにラウンドｒの自身の実行を停止して、
【数３１３】
2020536473.tif 000324
を設定し、自身のＣＥＲＴrをサブステップ（ｂ’）のメッセージ
【数３１４】
2020536473.tif 000325
の集合となるように設定する。
【０２８６】
−  このように待機する間の任意の時点で、ｉが少なくともｔH個の有効なメッセージ
【数３１５】
2020536473.tif 000326
を受信していれば、ｉは直ちにラウンドｒの自身の実行を停止して、
【数３１６】
2020536473.tif 000327
を設定し、自身のＣＥＲＴrを１及び
【数３１７】
2020536473.tif 000328
へのメッセージ
【数３１８】
2020536473.tif 000329
の集合となるように設定する。
【０２８７】
６  短期鍵を有するＡｌｇｏｒａｎｄ
本質的に、Ａｌｇｏｒａｎｄではブロックはラウンドで生成される。ラウンドｒにおいて
（１）適切に信任されたリーダーが新規ブロックを提案し、次いで、
（２）信任されたユーザーは適切に、いくつかのステップにわたり、提案されたブロックで適切なビザンチン合意（ＢＡ）プロトコルを実行する。
【０２８８】
好適なＢＡプロトコルはＢＡ*である。ブロック提案ステップはステップ１と考えられるため、ＢＡ*のステップは２，３，．．．である。
【０２８９】
システムのユーザーの中から無作為に選択された適切なユーザーｉだけが、ラウンドｒのステップｓでメッセージ
【数３１９】
2020536473.tif 000330
を送る資格を有している。Ａｌｇｏｒａｎｄが極めて高速且つ安全である理由は、そのようなユーザーｉは自身が話す資格を有しているか否かを調べるためである。そうである場合、ユーザーｉは実際に証明すなわち信任値を取得する。ラウンドｒのステップｓで自分が話す順番である場合、ｉは自身の信任値
【数３２０】
2020536473.tif 000331
及び自身のデジタル署名されたメッセージ
【数３２１】
2020536473.tif 000332
の両方をネットワークに拡散させる。信任値は他のユーザーに、メッセージ
【数３２２】
2020536473.tif 000333
を考慮に入れるべきであることを証明する。
【０２９０】
ユーザーｉがラウンドｒのステップｓで話す資格を有するのに必要な条件は、数ラウンド前に既にシステムに存在していた。具体的には、ラウンドｒのｋラウンド前であり、ｋは「見直し」パラメータと称されるパラメータである。すなわち、ラウンドｒで話す資格を有するには、ｉはＰＫr-k、すなわちラウンドｒ−ｋで既にシステムに存在する全ての公開鍵／ユーザーの集合に属していなければならない。（ユーザーは自身の公開鍵により識別できる。）この条件は、ブロックチェーンから導出可能であるという意味で検証が容易である。
【０２９１】
他の条件は、
Ｈ（ＳＩＧi（ｒ，ｓ，Ｑr-1））＜ｐ
であり、ｐはＳＶr,sの検証者の人数の期待値を制御する所与の確率、すなわちラウンドｒのステップｓで話す資格を有しているユーザーの集合である。この条件が満たされたならば、ｉの信任値は次式で定義される。
【数３２３】
2020536473.tif 000334
【０２９２】
無論、自身がＳＶr,sに属するか否かを推測できるのはｉだけであり、他の全てのユーザーはｉの秘密署名鍵に関する知識がないため、これに関して全く分からない。しかし、ｉ∈ＳＶr,sならば、ｉは自身の信任値
【数３２４】
2020536473.tif 000335
を拡散することにより、これまでのブロックチェーンを与えられたならば誰にでも当てはまることを示すことができる。実際、（１）Ｑr-1は１つ前のブロックＢr-1から容易に計算可能であるが、充分に多くのブロックを遡れば本質的に予測不可能であり、（２）誰でもｉのデジタル署名を（システムにおけるｉの長期鍵に関して）確認することができることを想起されたい。
【０２９３】
また、これまでのＡｌｇｏｒａｎｄのバージョンにおいて、検証者ｉ∈ＳＶr、sが短期公開鍵
【数３２５】
2020536473.tif 000336
に関して自身のステップｓラウンドｒメッセージ
【数３２６】
2020536473.tif 000337
にデジタル署名し、ブロックチェーンが与えられれば、ｉ及びラウンドｒのステップｓに実際に対応していることは誰でも分かることを想起されたい。この「短期署名」を小文字で
【数３２７】
2020536473.tif 000338
と表記し、大文字で表記する「長期」鍵によるｉの署名と区別する。
【０２９４】
要するに、ＳＶr,sのユーザーは、ラウンドｒのステップｓで２つの別々のメッセージすなわち、（ａ）自身の信任値
【数３２８】
2020536473.tif 000339
及び（ｂ）自身の（短期的に）デジタル署名されたステップｓラウンドｒメッセージ
【数３２９】
2020536473.tif 000340
を拡散する。これを実行した後で、ｉは
【数３３０】
2020536473.tif 000341
に対応する自身の秘密短期鍵を削除する。
【０２９５】
短期鍵をこのように用いることで、ブロックＢrが生成された後で敵対者がラウンドｒの充分に多くの検証者を唆して異なるラウンドｒブロックを生成できるようになることを防止する。
【０２９６】
実際に、ステップ１の検証者が潜在的リーダーであり、且つ検証者のステップｌラウンドｒのメッセージが検証者の提案するブロックであることを想起されたい。（ラウンドｒのリーダーｌrは、最小の信任値がハッシュされた潜在的リーダーであると定義される。極めて稀な同点の場合、辞書編成順に先頭である潜在的リーダーを選択してよい。）任意のステップｓ＞１に対して、ｉ∈ＳＶr,sのメッセージ
【数３３１】
2020536473.tif 000342
が自身の「支配メッセージ」、すなわちＢＡプロトコルＢＡ*における自身のメッセージである。
【０２９７】
検証者ｉの信任値を自身の（デジタル署名された）メッセージ
【数３３２】
2020536473.tif 000343
から分離することには、次の２つの主な利点がある。
Ａ1  数人の潜在的リーダーが提案された新規ブロックを拡散する第１ステップにおいて、ユーザーはラウンドリーダーｌrが正直ならば素早く識別することができる。実際、全ての信任値、特にステップ１における信任値は極めて小さいのに対し、提案されたブロックは大きい場合がある。（ｌrが提案する実際のブロックは直後に識別することができる。）
Ａ2  怠慢な正直さを実装可能にする。すなわち、ユーザーｉが行動しなければならないラウンド及びステップを事前に非公開に認識できるようにする。
【０２９８】
７  メッセージ信任されたブロックチェーンを用いるＡｌｇｏｒａｎｄ
最初に、最終的にブロックを証明するために短期鍵を用いる必要はないが、他の全てのステップでは短期鍵を用いるＡｌｇｏｒａｎｄの新たな実施形態について述べる。
【０２９９】
次いで、第１のブロック提案ステップを除く全てのステップでＡｌｇｏｒａｎｄにより短期鍵をなくす方法について述べる。
【０３００】
ブロック提案  新たな実施形態は以前と同じステップ１を用いる。従って、ラウンドｒの潜在的リーダーｉは、自身の対応する短期鍵に関して自身の提案されたブロック
【数３３３】
2020536473.tif 000344
に署名して、対応する秘密の短期鍵を消去し、次いで
【数３３４】
2020536473.tif 000345
の自身の信任値及び署名を拡散する。
【０３０１】
ビザンチン合意  ラウンドｒにおいて、ＢＡプロトコルＢＡ*の全てのステップｓは以前と同じままである。従って、特に、検証者ｉ∈ＳＶr,sは自身の信任値及び自身のｒ−ｓ短期公開鍵に関してデジタル署名された自身のステップｓラウンドｒメッセージ
【数３３５】
2020536473.tif 000346
を拡散して、対応する秘密短期鍵を消去する。しかし、第１のコインが１に固定されたステップの終了条件及びＢＢＡ*の全ての後続ステップに以下の変更が加えられる。
【０３０２】
このようなステップｓでユーザーｉが初めて終了条件に達したと仮定する。その場合、
・あるビットｂに対して、ｉは少なくともｔH個の有効なメッセージ
【数３３６】
2020536473.tif 000347
但し同じｖ≠⊥、を受信しており、
・ｉは１個の有効なメッセージ
【数３３７】
2020536473.tif 000348
但し
【数３３８】
2020536473.tif 000349
を受信している。
【０３０３】
従って、ｉがＳＶr,sにおける検証者であれば、Ａｌｇｏｒａｎｄの従来技術の実施形態では、直ちに実行を停止して、ＣＥＲＴrを所有していると思われるブロックＢrを知っていたであろう。ＣＥＲＴrが所与の数の短期デジタル署名を含んでいることを想起されたい。ここではそのようなＣＥＲＴrをＢrの「短期証明」と呼ぶ。
【０３０４】
Ａｌｇｏｒａｎｄの新たな実施形態において、ユーザーｉはＳＶr,s（必然的にＰＫr-kに属する）の検証者ではなく、ＰＫr-kの任意のユーザーであってよく、ｋは見直しパラメータである。そのような任意のユーザーｉはもはや、ラウンドｒ実行（のシミュレーション）を停止しない。むしろ、自身の長期の秘密鍵を用いて、ブロックＢが最後であると考えることを示すデータの署名を生成し、署名が正当に考慮される適切な機会があることを保証している。例えば、一切の限定を意図することなく、ｉは、
ｓi＝ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，Ｈ（Ｂ））
を計算し、ここでＢはブロックチェーンで構築されたばかりの最新ブロックである。Ｈ（ｓi）＜ｐならば、ｉはｓiを拡散し、ｓiを信任された証明署名と呼ぶ。（ここに、ｐは［０，１］の範囲にある所与のパラメータである。）
【０３０５】
そのような署名の所与の閾値ＴがＢの非短期証明を構成する。
【０３０６】
ここで、非短期証明だけが重要である。短期証明は、真の非短期証明に向かう「踏み石」に過ぎないと考えてよい。
【０３０７】
正直なユーザーは、ブロックＢrの最後の証明を見て、ラウンドｒのブロックの最後の証明の生成にはもはや関与しない。
【０３０８】
解析  たとえ非短期証明が長期署名を含んでいたとしても、本実施形態は依然として安全である。本質的に、その理由は、ｐ及びＴの適切な選択のために、敵対者は以下の形式のＴ個の署名Ｓjを生成できるストリングＸを一切見つけることができないからである。
ｓj＝ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，Ｘ）
ここに、全てのｊは唆されたユーザーであってＨ（ｓj）≦ｐである。
【０３０９】
（本出願において、Ｔは極めて小さくても、例えば約５００であってもよい。その理由は、Ｔ個の署名のうち少なくとも１個が正直なユーザーのものであればよいからである。実際、Ｔははるかに小さくてよく、その理由は、非短期証明を頻繁に生成すれば充分であり、必ずしも全てのブロックについて生成しなくてもよいからである。）
【０３１０】
また、新たな実施形態では、敵対者が唆されたユーザーが計算した「任意の信任された証明署名」を正直なユーザーに拡散させることによりネットワークをオーバーフローさせることができない点にも注意されたい。実際、悪意のあるｊ∈ＰＫr-kは誰でも、Ｈ（ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，ｘj））＜ｐであるような任意のストリングｘjを見つけられるが、拡散規則を適正に用いることにより、署名ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，ｘj）は決して正直なユーザーにより中継されないであろう。実際、ユーザーｕが署名ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，Ｈ（Ｂ））を転送するのは、（１）ｊ∈ＰＫr-k且つ（２）Ｈ（ＳＩＧi（ＦＩＮＡＬ，ｒ，ｓ，Ｑr-1，Ｈ（Ｂ）））＜ｐの場合だけでなく、（３）Ｈ（Ｂ）が、ｕ自身が非短期証明を見たブロックＢのハッシュである場合も転送する。
【０３１１】
実は、上の条件３は、以下のより弱いもので代替することができる。
３’．Ｈ（Ｂ）は、可能な短期証明の充分大きい部分集合をｕ自身が見たブロックＢのハッシュである。
【０３１２】
実際、正直なユーザーｉがＢの完全な短期証明を見たならば、（分割がない状態で）他の正直なユーザーはＢが適切なステップの多数の検証者が承認したＢを見ていた筈である。この数は、実際に非短期的に証明される可能性があるブロックだけを識別するのに充分である。
【０３１３】
他のステップにおける短期鍵の除去  上の実施形態は、元のＡｌｇｏｒａｎｄプロトコルに最小限の変更を必要とする。以下に、第１ステップ以外の全てのステップで短期鍵を回避する仕方を説明しよう。概念は、全てのステップｓ＞１に対して、ステップｓ検証者が存在しないというものである。むしろ、全てのラウンドｒに対して、全てのユーザーがあたかもＳＶr,sの検証者であるかのようにステップｓを内部的に実行することにより、自身のステップｓラウンドｒメッセージ
【数３３９】
2020536473.tif 000350
を内部的に計算する。この時点で、ｉは自身の短期鍵
【数３４０】
2020536473.tif 000351
で
【数３４１】
2020536473.tif 000352
にデジタル署名するのではなく、自身が以下のようにメッセージ
【数３４２】
2020536473.tif 000353
を拡散する資格を有しているか否かを、次のように確認する。最初に、ｉはｋラウンド前にシステムにいたか否か、すなわち、ｊ∈ＰＫr-kか否かを確認する。そうであれば、ｉは量Ｑr-1と共に、自身の長期鍵で
【数３４３】
2020536473.tif 000354
にデジタル署名する。例えば、
【数３４４】
2020536473.tif 000355
を計算して、所与の確率ｐでこの署名のハッシュが≦ｐであるか否かを確認する。そうであれば、ｉは
【数３４５】
2020536473.tif 000356
を拡散する資格を有しており、実際に
【数３４６】
2020536473.tif 000357
を拡散する。
【数３４７】
2020536473.tif 000358
が与えられたならば、ｉが
【数３４８】
2020536473.tif 000359
を拡散する資格を有していることを誰でも確かめることができる点に注意されたい。ステップｓ＋１において、ユーザーは、資格を有するユーザーが拡散したステップｓのメッセージだけを考慮する。
【０３１４】
ラウンドｒのステップｓを（少なくとも内部的に）実行した正直なユーザーは、もはやそのようなステップを実行することも、実行に関与することもない。
【０３１５】
８  範囲
本明細書に記述する機構が、検証等の特定の目的でユーザーの部分集合を一般に検証可能な仕方で無作為に選択することが望ましい他のブロックチェーンシステムに適用できる点に注意されたい。従って、本明細書に記述するシステムは他のブロックチェーンスキーム、例えばイーサリアム又はライトコイン或いは通貨とは直接関係がないブロックチェーンスキームにも適合させることができる。
【０３１６】
本明細書に記述するシステムは、全文を本明細書に引用している２０１７年５月４日出願のＰＣＴ／ＵＳ２０１７／第０３１０３７号、２０１７年８月１７日出願の第１５／５５１，６７８号、２０１７年９月２８日出願の第６２／５６４，６７０号、２０１７年１０月４日出願の第６２／５６７，８６４号、２０１７年１０月１０日出願の第６２／５７０，２５６号、２０１７年１１月２日出願の第６２／５８０，７５７号、２０１７年１２月１９日出願の第６２／６０７，５５８号、２０１８年２月２０日出願の第６２／６３２，９４４号、及び２０１８年３月１５日出願の第６２／６４３，３３１号のいずれか又は全てに開示された機構に適用すべく、及びこれらと組み合わせるべく適合させることができる。
【０３１７】
本明細書に記述するシステムのソフトウェア実装は、計算機可読媒体に保存され、１つ以上のプロセッサにより実行される実行可能コードを含んでいてよい。計算機可読媒体は非一時的でよく、コンピュータハードドライブ、ＲＯＭ、ＲＡＭ、フラッシュメモリ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、フラッシュドライブ、ＳＤカード等の可搬コンピュータ記憶媒体及び／又は例えばユニバーサルシリアルバス（ＵＳＢ）インターフェースを備えた他のドライブ、及び／又は実行コードが保存されてプロセッサにより実行可能な有形又は非一時的計算機可読媒体或いはコンピュータメモリであってよい。本明細書に記述するシステムは任意の適当なオペレーティングシステムと組み合わせて用いられてよい。
【０３１８】
本発明の他の実施形態は、本明細書に開示する本発明の仕様の実施を考慮することにより当業者に明らかになろう。仕様及び実施例は例示目的に過ぎず、本発明の真の範囲及び趣旨は以下の請求項により示されるものとする。
【図１】
2020536473.tif 000360
【図２】
2020536473.tif 000361
【図３】
2020536473.tif 000362
【図４．Ａ】
2020536473.tif 000363
【図４．Ｂ】
2020536473.tif 000364
【図５】
2020536473.tif 000365
【国際調査報告】
2020536473.tif 000366