(57)【要約】  ブロックチェーンを介してエンティティにより提供されるデータの通信、保存、及び処理のためのシステム及び方法が提供される。ブロックチェーンにおける決定を行うコンピュータ実行方法が提供される。方法は、選択（A,B）に関連する第1署名（σ（Am），σ（Bm））と選択に関連する第2署名（σ（A），σ（B））とにより履行することが可能なブロックチェーン投票コミットメント・トランザクション（2）を提供するステップと、少なくとも1つの各自のシークレット値（kA,kB）の少なくとも1つのシェア（kA,i,kB,i）を複数の参加者（Ui）の各々に提供するステップと、ブロックチェーン投票コミットメント・トランザクション（2）をブロックチェーンにサブミットするステップとを含む。
2020532221.tif 000002
【特許請求の範囲】
【請求項１】
ブロックチェーンで決定を行うコンピュータ実行方法であって：
選択に関連する第１署名と前記選択に関連する第２署名とを利用することにより履行することが可能な第１ブロックチェーン・トランザクションを提供するステップ；
少なくとも1つの各自のシークレット値の少なくとも1つのシェアを複数の参加者の各々に提供するステップ；及び
前記第１ブロックチェーン・トランザクションを前記ブロックチェーンにサブミットするステップ；
を含む方法。
【請求項２】
少なくとも１人の参加者が、暗号資産を表す少なくとも１つの署名された入力を前記第１ブロックチェーン・トランザクションに追加する、請求項１に記載の方法。
【請求項３】
ロックタイム条件が充足されると前記暗号資産のうちの少なくとも一部を少なくとも１人の参加者に戻すように履行することが可能な第２ブロックチェーン・トランザクションを提供するステップを更に含む請求項２に記載の方法。
【請求項４】
前記第１ブロックチェーン・トランザクションは、ｍ−ｏｆ−ｎマルチシグネチャの履行スクリプトを含み、少なくとも１つのシェアが前記履行スクリプトに追加されている、請求項１−３のうちの何れか１項に記載の方法。
【請求項５】
少なくとも１つのシェアが、少なくとも１つの決定についての第１公開鍵により暗号化される、請求項４に記載の方法。
【請求項６】
前記第１公開鍵で暗号化する前に、少なくとも１つのシェアと選択を識別する識別データとを結合するステップを更に含む請求項５に記載の方法。
【請求項７】
前記結合するステップは前記少なくとも１つのシェアと前記識別データとの連結を含む、請求項６に記載の方法。
【請求項８】
前記シェアを前記参加者に提供するステップが：
（ｉ）ディーラー・エンティティが前記シェアを前記参加者に提供するステップ；及び
（ｉｉ）前記参加者が彼らの中で前記シェアを生成するステップ；
のうちの少なくとも１つを含む、請求項１−７のうちの何れか１項に記載の方法。
【請求項９】
前記第１ブロックチェーン・トランザクションを前記ブロックチェーンにサブミットする前に、何れの参加者が何れのシェアを提供したかを秘匿するステップを含む請求項１−８のうちの何れか１項に記載の方法。
【請求項１０】
前記第１ブロックチェーン・トランザクションを履行するために構成される第３ブロックチェーン・トランザクションを提供するステップを更に含む請求項１−９のうちの何れか１項に記載の方法。
【請求項１１】
少なくとも１つの第２公開鍵を利用して少なくとも１つのシェアを検証するステップを更に含む請求項１−１０のうちの何れか１項に記載の方法。
【請求項１２】
シェアの少なくとも１つのサブセットを組み合わせて少なくとも１つの前記第２公開鍵を決定するために、前記複数の参加者が協力する、請求項１１に記載の方法。
【請求項１３】
プロセッサ；及び
実行可能命令を含むメモリ；
を有するコンピュータで実現されるシステムであって、前記実行可能命令は、前記プロセッサによる実行の結果として、請求項１−１２のうちの何れか１項に記載のコンピュータ実行方法を前記システムに実行させる、システム。
【請求項１４】
実行可能命令を格納した非一時的なコンピュータ読み取り可能な記憶媒体であって、前記実行可能命令は、コンピュータ・システムのプロセッサにより実行された結果として、請求項１−１２のうちの何れか１項に記載の方法を前記コンピュータ・システムに少なくとも実行させる、記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に暗号により実行されるデータ記録及び処理システムに関連する。特に、本発明はブロックチェーンにより又はそれを介してエンティティによりシステムに提供されるデータを通信、記録、及び／又は保存するための技術的ソリューションに関連する。データは、例えば、選択、選出、フィードバック、及び／又は決定を表し得る。本発明は、ブロックチェーン・ネットワークを介するエンティティ間でのそのようなデータの安全な保存及び通信のための技術を提供し、転送されるデータ及び転送された後に使用されるデータの完全性を保証する。また、認可された行動を妨げるようなネットワークにおけるそのようなデータのソースの識別に関する問題も軽減する。本発明は、投票、電子フィードバック・サブミッション、計数するアプリケーション、又はその他のアプリケーションに適している（ただし、それらに限定されない）。ここで、データの完全性、ソースの秘匿、使用割り当て又は制限の強制が重要なものになり得る。
【背景技術】
【０００２】
この文献において我々は「ブロックチェーン」という用語を電子的なコンピュータ・ベースの分散された台帳の総ての形態を含むように使用する。これらはコンセンサス・ベースのブロックチェーン及びトランザクション・チェーン技術、許可型及び非許可型の台帳、共有台帳、及びそれらの変形を含む。ブロックチェーン技術の最も広く知られたアプリケーションはビットコイン台帳であるが、他のブロックチェーン実装も提案され開発されている。便宜上及び説明の目的のために、ビットコインが本願で言及されるかもしれないが、本発明はビットコイン・ブロックチェーンに限定されず、代替的なブロックチェーン実装及びプロトコルが本発明の範囲内に属することに留意すべきである。本願において「ユーザー」という用語は人間又はプロセッサ・ベースのリソースを指すことができる。
【０００３】
ブロックチェーンは、ブロックにより構成されるコンピュータ・ベースの非セントラル化された分散システムとして実装されるコンセンサス・ベースの電子台帳であり、ブロックはトランザクションにより構成される。各々のトランザクションは、ブロックチェーン・システム内の参加者間でのディジタル資産のコントロールをエンコードするデータ構造であり、少なくとも1つの入力と少なくとも1つの出力とを含む。各々のブロックは先行するブロックのハッシュを含み、そのブロックに対して複数のブロックが共にチェーン状になり、その発端以来ブロックチェーンに書き込まれてきた全てのトランザクションの永続的な変更できない記録を作る。トランザクションは、トランザクションの出力が誰によってどのようにアクセスされ得るかを指定する各自の入力及び出力に埋め込まれたスクリプトとして知られる小さなプログラムを含む。ビットコイン・プラットフォームでは、これらのスクリプトはスタック・ベース・スクリプト言語を使用して書かれる。
【０００４】
トランザクションがブロックチェーンに書き込まれるために、それは「検証」されなければならない。ネットワーク・ノード（マイナー）は、各々のトランザクションが有効であることを保証するための作業を実行し、有効でないトランザクションはネットワークから拒否される。ノードにインストールされているソフトウェア・クライアントは、未使用トランザクション（UTXO）に関するこの検証作業を、そのロッキング及びアンロッキング・スクリプトを実行することによって実行する。ロッキング及びアンロッキング・スクリプトの実行が真（TRUE）に評価される場合、トランザクションは有効であり、そのトランザクションはブロックチェーンに書き込まれる。従って、トランザクションがブロックチェーンに書き込まれるために、（i）トランザクションを受信する第１ノードにより検証され−−−トランザクションが検証されると、ノードはそれをネットワーク内の他のノードへ中継し；（ii）マイニング・ノードにより構築される新たなブロックに追加され；（iii）マイニングされる、即ち過去のトランザクションの公の台帳に追加されなければならない。いったん記録されると、どのブロックにおけるデータも、総ての後続のブロックを変更することなく且つネットワークの過半数の共謀もなしに、遡って変更することはできない。
【０００５】
トランザクションはあるノードから他のノードへの1つ以上のトークンの移転を含む。トークンはネットワーク・リソースの将来的なコントロールを表現することができる。幾つかのケースにおいて、トークンは資産又は価値を表現し得るが、必須ではない。例えば、幾つかのケースにおいて、トークンは暗号通貨として理解されることが可能である。しかしながら、本願は暗号通貨の文脈での実装に限定されず、コントロール・トークンの分散移転のためのブロックチェーン・ネットワークに関連するように、より広義に理解される。
【０００６】
ブロックチェーンは、検証可能な永続的な方法で関係者間のトランザクションを記録することが可能な公の台帳として役立つ。ブロックチェーンは、チェーンに保存される情報の改変不可能性、及び非セントラル化されたコンセンサスにより確立される信用などの多くの特質を有し、これらの特質はブロックチェーンを様々なアプリケーションでの使用に相応しくする。そのような1つのアプリケーションは電子投票である。「投票システム（voting  system）」という用語は本願では政治的又は行政的な文脈に限定されず、選択、選出、決定、又はパラメータ（即ち、投票）が何らかの方法で転送、記録、保存、処理、及び／又は登録されることを可能にするシステムを単に意味するような一般的な意味で使用される点に留意すべきである。従って、本発明はエンティティ間でのデータの改善された通信、保存、及びセキュリティに関連する。
【０００７】
多くのタイプのコンピュータ実装システムは、選択／決定の指示又は他のデータが、ネットワークを介して通信されることを必要とし、その結果、データは何らかの方法で作用する又は処理されることが可能になる。多くのケースにおいて、選択が行われ得る回数について所定のルール又は基準を強制できることが望ましい。換言すれば、選択又は選出が行われ得る回数に対して割り当て又は制限が存在し得る。利便性及び参照を容易にすることのみのために、そのようなシステムを「電子投票（e-voting）」システムと言及するかもしれないが、政治的又は行政的な文脈に本発明を限定するように解釈すべきではない。代替的に、「データ記録システム」という用語は、本発明のより広い適用性を反映するように使用することができる。本発明は受信、記録、及び保存されるデータのタイプ又は性質に関して制限されない。
【０００８】
最近、安全な電子投票のためのプロトコルを設計するオンライン技術を開発することに関心が高まっている。これらの努力のゴールは、ユーザーのグループが、秘密に維持される個々人の好みに基づく共同決定を許容することである。電子投票に関連する問題は、ユーザーの投票を決定する能力を別の関係者に許可しないこと、投票の改変不可能性を保証すること、更にはプロセスで投票者の信用を獲得するためにプロセス全体を通じて必要な透明性を提供することを含む。
【０００９】
暗号通貨プロトコルの基礎としてのブロックチェーンの導入は、これらの分散台帳の変更不可能性及び透明性の特質の活用をもたらす。有用な暗号ソリューションとの組み合わせによりこれらの台帳は、典型的には電子的な（サーバー）及び非電子的な投票プロセスに信頼できる第三者についての有効な置換として、ブロックチェーンを利用する特徴的な機会をもたらす。
【００１０】
特にインターネット等の情報技術のグローバル・コミュニティによる幅広い採用は、様々な既存のサービスの利用に関し、必然的に電子投票の問題に導いた。ウェブ・ベースの世論調査（polls）はユーザーの感情を獲得する一般的な方法であるが、公職その他の状況に関連する選出に電子投票を利用することに著しい反対がある。この反対に直面して、電子投票が更なる成功を達成するために、提案されるシステムは様々な社会的・技術的なハードルを乗り越えることが課されるであろう。
【００１１】
電子投票システムが達成するように努力しなければならないと考えられる望ましい基準のうちの幾つかは以下のとおりである：
正しいこと：総ての投票は正しく考慮される：即ち、無効な又は非承認の投票は排除される一方、総ての有効な投票は最終的な結果に結びつくようにカウントされる。
プライバシー：投票は投票者自身とは異なる参加者に知られない。
二重投票禁止：投票は2回提出されない。即ち、他の投票者により既に提出された投票を攻撃者がコピーすることは不可能であるべきである。
適格性：認可された投票者のみがプロトコルの中で各自の票を投じることができる。
票が適切に考慮されていることを確認するための検証可能性。
【００１２】
暗号通貨ビットコインによるブロックチェーン技術の出現は、電子投票プロトコルの構築でブロックチェーンの特質を活用する機会を提供した。ブロックチェーンそれ自体は、トランザクションの検証において信頼できる第三者の必要性を排除する変更不可能な公の台帳である。これらの特徴は、上記の5つの基準のうちの1つ以上を適用及び／又はイネーブルにすることにより、電子投票に適用可能であると考えられる。
【００１３】
ブロックチェーンは、票及び意見が公に且つ永続的に記録され得る適切な環境を構成し、如何なる種類の票の操作も回避する。この能力にもかかわらず、ブロックチェーンで安全な票を作るために対処されるべき多くの問題が存在する。これは、複数の票の提出を防止することから、ユーザーのプライバシー及び信用検査を維持することまで多岐に及ぶ。
【００１４】
非セントラル化は、オンライン電子投票及び評価のプロトコルにとって最も大きな問題のうちの1つである：通常の既存のソリューションは不正を防止するような方法で構成されるが、それらは投票及びフィードバックを検証及び考慮するために中央の権限を当てにする。
【００１５】
中央の権限は、票の投票に秘密性及び適格性の検証を付加するために、ブラインド署名及び準同型暗号などの様々な暗号プリミティブを利用することができる。ショーン（Chaum）のプロトコル参加者は各自の票を混合当局に送付し、混合当局は、ミックス・ネット・セットアップを利用して、それらのブロードキャスト前に票をシャッフルして暗号化し、投票と投票者との結び付きを隠す。これについては次の非特許文献１で詳細に説明されている。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】Chaum,  D.  L.  (1981)-“Untraceable  electronic  mail,  return  addresses,  and  digital  pseudonyms”,  Communications  of  the  ACM,  24(2),  84-90
【発明の概要】
【００１７】
従って、ビットコイン対応の投票プロトコルを提供することが望ましく、その場合において、投票者は、ビットコイン・トランザクションを使用して、（2つの可能な選択肢の中で）好ましい候補に対して各自の票を投じ、勝利候補に対してビットコイン又はトークンの量を約束する。このプロトコルは、十分な票を勝ち取る候補者の報酬を促進するために、分散鍵共有方式を利用する。
【００１８】
このように改善されたソリューションが工夫されている。
【００１９】
かくて本発明によれば添付の特許請求の範囲に記載されるような方法が提供される。
【００２０】
本発明によれば、ブロックチェーンにおいて投票するコンピュータで実現される方法が提供されることが可能であり、本方法は：複数の投票者の各々に、シークレット値の少なくとも1つのシェアを提供するステップであって、各々のシークレット値は選択に関連している、ステップ；（i）勝利選択肢のシークレット値から確定することが可能な第１署名、及び（ii）勝利選択肢の識別子を示す第２署名の双方を提供することにより勝利選択肢を明らかにするために履行することが可能な（redeemable）コミットメント・トランザクションを提供するステップ；及びコミットメント・トランザクションをブロックチェーンにサブミットするステップであって、勝利選択肢のシークレット値は、少なくとも１人の投票者により提供される投票アイテム数を利用して確定することが可能であり、投票アイテムの各々は少なくとも1つのシェアを含み、その数は所定の値を超えている、ステップを含む。
【００２１】
このような方法を提供することにより、ブロックチェーンのユーザーは、改竄防止の小選挙区制の投票システム（a  tamper-proof  first-past-the-post  style  voting  system）で安全に票を投じることができる。
【００２２】
少なくとも１人の投票者は、暗号資産を表す少なくとも1つの署名された入力を第１コミットメント・トランザクションに追加してもよい。
【００２３】
これは、投票プロセスにおいて不正な又は悪意の参加を思いとどまらせる利点を提供する。
【００２４】
本方法は、ロックタイム条件が充足されると暗号資産のうちの少なくとも一部を少なくとも１人の投票者に戻すように履行することが可能なリターン・トランザクションを提供するステップを更に含んでもよい。
【００２５】
これは、勝利選択肢が無い場合に資産の喪失を最小化する仕組みによる利点を提供する。
【００２６】
コミットメント・トランザクションは、m-of-nマルチシグネチャの履行スクリプトを含んでもよく、少なくとも1つの投票アイテムが履行スクリプトに追加されてもよい。
【００２７】
これは、少なくとも1つの投票アイテムの格納及び公の視認性を可能にすることによる利点を提供する。
【００２８】
少なくとも投票アイテムは、少なくとも1つの選択についての第１公開鍵により暗号化されてもよい。
【００２９】
これは、選択された選択肢のみが、投票アイテムを解読し、シェアへのアクセスを得ることを可能にする利点を提供する。
【００３０】
少なくとも1つの投票アイテムは、少なくとも1つの選択肢を識別する少なくとも1つの識別アイテムを含んでもよい。
【００３１】
投票アイテムの解読に成功すると、これは、シェアが後に識別され得る容易性を増やす利点を提供する。
【００３２】
少なくとも1つの投票アイテムは、少なくとも1つのシェアと少なくとも1つの識別アイテムとの連結を含んでもよい。
【００３３】
シェアを投票者に提供するステップが：
（ｉ）ディーラー・エンティティがシェアを投票者に提供するステップ；及び
（ｉｉ）投票者がシェアを生成するステップ；
のうちの少なくとも1つを含んでもよい。
【００３４】
これは、ディーラーに基づく投票システムとディーラーのいない投票システムとの双方を可能にし、これにより投票方法の多様性を増やす。
【００３５】
本方法は、コミットメント・トランザクションをブロックチェーンにサブミットする前に、何れの投票者が何れの投票アイテムを提供したかを秘匿するステップを更に含んでもよい。
【００３６】
これは、投票者が各自の投票アイテムから識別されてしまうことを防止し、これにより投票方法のセキュリティを増進する利益を提供する。
【００３７】
本方法は、コミットメント・トランザクションを履行するように構成される履行トランザクション（a  redemption  transaction）を提供するステップを更に含んでもよい。
【００３８】
これは勝利選択肢の識別子を投票者に示す簡易な方法による利点を提供する。
【００３９】
本方法は、少なくとも1つの第2公開鍵を利用して少なくとも1つのシェアを検証するステップを更に含んでもよい。
【００４０】
これは、投票者がシェアの有効性を検査することを可能にし、これにより投票方法のロバスト性を増進する利点を提供する。
【００４１】
シェアの少なくとも1つのサブセットを組み合わせて少なくとも1つの第2公開鍵を決定するために、複数の投票者が協力してもよい。
【００４２】
これは、投票方法の少なくとも一部分を非セントラル化する手段を提供し、これにより本方法の多様性を更に増やす利点を提供する。
【００４３】
追加的又は代替的に、本発明によれば、ブロックチェーンにおいて投票の勝利選択肢を決定するコンピュータで実現される方法が提供されることが可能であり、本方法は：少なくとも1つの投票アイテムから少なくとも1つのシークレット値の少なくとも1つのシェアを決定するステップであって、各々のシークレット値は選択肢に関連付けられている、ステップ；少なくとも1つの投票アイテムにより提供されるシェアの数を利用して勝利選択肢のシークレット値を決定するステップであって、その数は所定値を超えている、ステップ；勝利選択肢のシークレット値から第1署名を決定するステップ；及び（i）第１署名、及び（ii）勝利選択肢の識別子に関連する第2署名の双方を提供することにより、勝利選択肢を明らかにするためにコミットメント・トランザクションを履行するステップを含む。
【００４４】
このような方法を提供することにより、ブロックチェーンで実行される投票方法の勝利選択肢の識別子が、安全で透明性のある方法で決定され確認されることが可能である。
【００４５】
本発明はまたシステムを提供し、システムは：
プロセッサ；及び
実行可能命令を含むメモリ；
を有し、実行可能命令は、プロセッサの実行の結果として、上記のコンピュータ実行方法の任意の実施形態をシステムに実行させる。
【００４６】
本発明はまた実行可能命令を格納した非一時的なコンピュータ読み取り可能な記憶媒体を提供し、実行可能命令は、コンピュータ・システムのプロセッサにより実行された結果として、上記のコンピュータ実行方法の実施形態をコンピュータ・システムに少なくとも実行させる。
【００４７】
本願は、ユーザーによりブロックチェーンに提出されるデータ・アイテムを暗号化、検証、及びブロードキャストする方式についての安全な、暗号的に実行される効率的な実装を支援するシステム及び方法を説明している。何らかの有用なアプリケーションにおいて、ユーザーは投票又はフィードバック・プラットフォームの参加者であってもよい。幾つかの実装において、本願は、悪意の行為者からのデータの提出を防止するように設計されるプロトコルを提供する。これは、受信したデータに基づいてシステムにより生成される結果の完全性及び信頼性を維持することができる。
【図面の簡単な説明】
【００４８】
本発明のこれら及び他の態様は、本願で説明される実施形態から明らかになり、それらを参照しながら説明される。本発明の実施形態は例示としてのみ添付図面を参照しながら説明される。
【００４９】
【図１】本発明の3つのトランザクションの相互作用の概略図を示す。
【００５０】
【図２】投票者数と、選択肢が決定されるために必要とされる閾・投票者数と、多項式の次数との間の関係を示す本発明によるテーブルである。
【００５１】
【図３】本発明を説明するフローチャートを示す。
【００５２】
【図４】投票コミットメント・トランザクションを示す。
【００５３】
【図５】2つの勝者支払トランザクションを示す。
【００５４】
【図６】リファンド・トランザクションを示す。
【００５５】
【図７】様々な実施形態が実装され得るコンピューティング環境を示す概略図である。
【発明を実施するための形態】
【００５６】
本願は、一群の投票者が候補ペアの間で選択を行うように求められるシステムである閾値シークレット共有投票（Threshold  Secret  Share  Voting：TSSV）のシステムを説明しており、勝利候補は、各投票者によりコミットされたxBTCを受け取る。勝利候補は、過半数の投票と、指定閾値を超える投票数との双方を獲得する必要がある。TSSVプロトコルは、プライベート・キー・シェアの分配を利用しており、仮に1人以上の参加者が悪意である又はプロトコルの期待に応じない場合には、コミットされた何らかのビットコインが取り戻されるように設計されている。
【００５７】
「BTC」という略語は、ビットコイン・プロトコルの任意のバリエーションに対する略称として使用されてもよい。1つの何らかの特定のビットコイン関連プロトコルに制限されるように又はそれを表すように解釈されるべきではない。
【００５８】
シークレット・シェアリング
閾値暗号システムは(t;n)-閾値により規定され、ここでnは関係者の数であり、t+1はシークレットを再構築するために必要な関係者の最小数である。シークレット共有方式は閾値暗号システムの具体例であり、シークレットkがnプレイヤ間で分割され、その結果、kを再構築するためには少なくともt+1人の参加者が協力するように要求される。シークレットkのうちの任意のt個のピースについての知識は、kを未定のまま残す。
【００５９】
シャミールのシークレット共有（Shamir’s  secret  sharing：SSS）は多項式補間に基づいており、一般性を失うことなく、シークレットは有限体Fの要素であると仮定される。本方式は、ディーラーと（ディーラーのいないバージョンも存在する）、一群のn人の参加者U1,...,Unと、アクセス構造Aとを有し、即ちプレイヤのグループはシークレットを再構築することができる。これは次の文献に詳細に説明されている。
Shamir,  A.  (1979)  “How  to  share  a  secret”,  Communications  of  the  ACM,  22(11),  612-613.
【００６０】
シャミールの解に関し、任意のランダム・シークレットがt次多項式f(x)におけるf(0)として格納され、プレイヤiはそのシェアf(xi)を計算できるだけである。n人のプレイヤのうちのt+1人が協力し合うならば、彼らは、ラグランジュ多項式補間を利用してf(x1),f(x2),...,f(xn)に対応する（キーkの）各自のシェアk1,k2,...,knを用いて、f(x)の任意の地点を再構築することができる。
【００６１】
ラグランジュ多項式補間を利用して、次数tの関数f(x)は、t+1個の地点により再構築されることが可能である。
【数１】
2020532221.tif 000003
bi,p(xi)=1及びbi,p(xj)=0であることに留意を要する。
【００６２】
ディーラーが存在する場合、ディーラーは、サイズp（pは素数）の有限体の要素であると仮定されるシークレットa0=kを単に選択し、t-1個の正の整数a1,...,at-1をランダムに取り出し、これらの整数は多項式f(x)=a0+a1x+a2x2+...の係数を表現する。次いでディーラーは多項式に属するn個の地点（xi,f(xi)）を計算し、それを関参加者に分配する。
【００６３】
ディーラーレス・シェア分配段階では：
1.  各々のプレイヤUiが、誰もが知っているxiの割り当てを受ける。各々のxiは固有であることを要する。
2.  各々のプレイヤUiが、次数tのランダム多項式fi(x)を生成する。
3.  各々のプレイヤUiが、多項式における各自の地点fi(xj)  mod  nを他のプレイヤ全員に秘密に（受信者の公開鍵で暗号化して）送信する。
4.  各々のプレイヤUiが各自受信したf1(xi),f2(xi)...,fp(xi)を総て合計し（all  mod  n，nは楕円曲線における点Gにより生成されるグループの次数である）、ki=f(xi)  mod  nを形成し、これは多項式f(x)  mod  nにおけるシェアである。
【００６４】
閾値署名計算の重要な要素はk×Gの決定であり、kはシークレット・キーであり、Gは楕円曲線上の点である。
【００６５】
f(x)がt次多項式である場合、シークレットkはk=Σi∈πbi,πkiにより補間されることが可能であり、πはシェアka,kb,...,kt,kt+1のサイズt+1のサブセットであり、bは補間因子である。πは各自のシェアkiを明らかにすることなくk×Gを計算するために協力するt+1プレイヤのグループである。kはt次多項式におけるx=0ポイントである。
・各々のプレイヤUiが一部分bi,πki×Gを計算する
・πのうちの総てのプレイヤが各自のパートを一緒に加算する（ラグランジュ補間によりシークレットkを再構築する）：
ba,πka×G+bb,πkb×G+・・・+bt+1,πkt+1×G=k×G
この計算プロセスQ=kGは、シークレット共有結合（Secret  Share  Joining）として言及される。
【００６６】
公的に検証可能なシークレット共有方式
TSSVプロトコルでは、投票者が正しいシークレット・シェアを与えられていることを確認できることが望ましい。実際、一貫性のないシェアがプレイヤ間に分配されると、投票者の正しくないシェア／票は、その投票者が好む候補に対して貢献し損なうであろう。シェアの検証に関し、我々は「公的に検証可能なシークレット共有方式（the  Publicly  Verifiable  Secret  Sharing  scheme）」を利用し、これは投票者が各自自身のシェアだけでなく他の投票者のシェアも検証することを許容する。これについては次の文献に詳細に説明されている：
Stadler,  M.  (1996,  May),  “Publicly  verifiable  secret  sharing”  -  International  Conference  on  the  Theory  and  Applications  of  Cryptographic  Techniques  (pp.  190-199),  Springer  Berlin  Heidelberg。
【００６７】
PVSS方式では、各々の参加者Uiは解読関数Diを有し、解読関数Diは対応する公開暗号関数Eiにより暗号化された情報にアクセスすることができる。このように、ディーラーは公開暗号関数を利用してシェアを分配し、それらを次の形式で公表する：
Ki=Ei(ki),  i=1,...,n
【００６８】
従って、暗号化されたシェアは、以下で詳細に説明されるように、関心のある任意の者によって公に検証されることが可能である。参加者が各自自身のシェアを検証できるだけでなく、誰もが、参加者は正しいシェアを受信したこと、即ちディーラーが正直であったか否かを検証することができる。
【００６９】
プロトコルのメイン・ステップは次のとおりである：
1−シークレット共有：シェアを算出してそれらを参加者間に分配するために、ディーラーがアルゴリズムShare(k)=(k1,...,kn)を実行する。
2−再構築：参加者は、Recover({Di(Ki)|i∈A})=kのようにアルゴリズムRecoverを実行することにより、シークレットを再構築することができる。
3−検証：暗号化されたシェアを検証するために、アルゴリズムPubVerifyが使用される。我々がアルゴリズムPubVerify({Ki|i∈A})=1→Recover({Di(Ki)|i∈A})=u及びu=kを実行するならば、ディーラーは正直であり、シェアは一貫している。
【００７０】
PVSS方式はリカバリー段階における必要性に応じてインタラクティブ又は非インタラクティブであるとすることが可能である。
【００７１】
ビットコイン・トランザクションにおいて入力から出力を分離すること
投票プロトコルの設計は、勝利候補に支払うトランザクションが、個々の投票者の票をも含むようにされる。投票プロセスの参加者、候補、又は任意の部外者が、他の任意の参加者の票（及び／又はその暗号化された値）を知ることがないように、他の任意の参加者がその暗号化された値を投票者のソースにリンクし得ることなく、各々の投票者が各自の暗号化された票を提供することを許容するソリューションを組み込むことが重要である。
【００７２】
この要件は一般的なビットコイン・コイン・ミキシング・ソリューションCoinJoinに類似するものであり、CoinJoinについては以下において詳細に説明されている：at  Maxwell,  G.  (2013,  August)  -  “CoinJoin:  Bitcoin  privacy  for  the  real  world”  -  Post  on  Bitcoin  Forum.  http://tinyurl.com/gn6kmx4。CoinJoinでは、一群の参加者の各々がビットコイン・トランザクションの入力のうちの1つに貢献して表現し；このトランザクションは複数の出力を含み、出力アドレスの各々は入力についての参加者により提供される。コイン混合プロセスの秘匿性を強化するために、入力参加者を各自の出力アドレスから切り離すことが重要である。この問題に対処するために、様々なシャッフルするソリューションが提案されており、その場合、他の任意の参加者又は外的な敵対者が参加者を特定の出力アドレスに関連付け得ることなく、参加者は各自の出力アドレスを提供することができる。
【００７３】
シャッフリング・ソリューションは、CoinShuffle（これについては次の文献に詳細に説明されている：T.,  Moreno-Sanchez,  P.,  &  Kate,  A.  (2014,  September),  “CoinShuffle:  Practical  decentralized  coin  mixing  for  Bitcoin”  -  European  Symposium  on  Research  in  Computer  Security  (pp.  345-364),  Springer  International  Publishing）、CoinShuffle++（これについては次の文献に詳細に説明されている：T.,  Moreno-Sanchez,  P.,  &  Kate,  A.  (2016)  -  “P2P  mixing  and  unlinkable  Bitcoin  transactions”  NDSS’17.  https://goo.gl/QrfMhp）、及びCircleShuffleを含む。
【００７４】
閾値シークレット共有投票
図1-6を参照すると、ブロックチェーンにおける決定を行う方法が提供されている。決定は、望ましい行動指針、選出における好ましい候補、又は他の何らかの決定の形式におけるものであってよい。多数の参加者又は投票者は、決定の1つ以上のアウトカム（one  or  more  outcomes）に関連する個々のシークレット値のシェアの提供を受ける。アウトカムは選出に立候補した候補であってもよい。参加者は、以後、各自の好むアウトカム、選択、候補のために、第1の又はコミットメント・トランザクション2を、アウトカムに関連するシェアを含む入力４に提供することによって投票する。コミットメント・トランザクション2（図4参照）は、1つのアウトカムに関連する第1署名（6a,6b）とそのアウトカムに関連する第2署名（8a,8b）との双方の提供に限って履行することが可能であるように構成される。図4-6において、公開鍵Xの署名はσ(X)と記される。シークレット値の少なくとも閾値数のシェアを提供すると、第2署名（8a,8b）を実行するために十分な情報が利用可能になり、従ってコミットメント・トランザクション2の条件を充足し、アウトカムを明らかにし及び／又は決定を制定する。
【００７５】
閾値シークレット共有投票（TSSV）プロトコルに関し、一群の参加者{Ui}が1つ以上の選択又は候補に対する投票する選択肢を有するという状況を想定する。この例では、A及びBで指定される2つの候補が存在する。各々の候補は、メイン・プライベート_パブリック・キー・ペア（(PrivAM,PubAM)及び(PrivBM,PubBM)）を有し、パブリック・キーは総ての投票者にとって利用可能にされる。各々の投票者は1つの票を有し、勝利候補（a  winning  candidate）は：
・最も多い票，
・及び、指定された閾値を超える十分な票
を有する候補である。
一例として、9人の参加者（投票者）が存在する場合、勝利候補は少なくとも5つの票を受けるように要求され得る。
【００７６】
各自の票との組み合わせにおいて、投票者は、各自の票とともに所定量のファンド（例えば、ビットコイン）をコミット（又は約束）するように求められる。総ての投票者から蓄積されコミットされたファンドは、勝利候補に与えられるであろう。これらのファンドは、勝者に対する報酬、又は投票プロセスにおける不真面目な又は悪意の参加者に対する行動阻害要因として理解され得る又はそのように動作し得る。
【００７７】
TSSVプロトコルは3つのトランザクションを利用する。これらのトランザクションは、投票コミットメント・トランザクション2（図4）、勝者支払（又は履行）トランザクション10（図5）、及びリファンド・トランザクション12（図6）のようにラベルを付されている。これらのトランザクションは以下の責務を有する。
【００７８】
投票コミットメント・トランザクション：投票コミットメント・トランザクション（VCT）2は、各投票者の投票コミットメント及びビットコイン・コミットメント双方を含むトランザクションである。提案されるTSSV設計において、トランザクション2は投票者群全体からの入力4を含むが、必ずしも総ての投票者が票を提供するようには要求されない。VCT2は総てのユーザーの投票を記録するだけでなく、1つの出力14におけるビットコイン・コミットメントをプールする。これらの票は暗号化される。
【００７９】
リファンド・トランザクション：リファンド・トランザクション（RT）12は、指定された時間の前に、候補者が、投票者の蓄積されたビットコインを収集できなかった場合に、各自が委託したファンドを投票者が取り戻すフェイルセーフ手段である。RT12は、ユーザーが投票し且つVCT2が作成された後（但し、サブミットされていない場合）に作成され署名される。
【００８０】
勝者支払トランザクション：勝者支払トランザクション（WPT）10又は履行トランザクションは、蓄積されたビットコインを勝利候補に支払うトランザクションである。勝利候補は、プールされたビットコインを収集することができる唯一の人、候補その他の者となるであろう。図5は2つの可能な履行トランザクション10a,10bを示し；（a）は候補Aが勝利した場合の履行トランザクション10aを示し、（b）は候補Bが勝利した場合の履行トランザクション10bを示す。
【００８１】
3つのトランザクション2、10、12の間の相互作用の視覚的な表現、及びプールされたビットコインが図1に示されている。
【００８２】
投票コミットメント・トランザクション（VCT）2はユーザーの票を含むトランザクションである。投票者は、2つのコミットメント（票及びビットコイン）についてのVCTを作成することを必要とし、BTCファンドを作成するプロセスは、最も理解し易いものであり且つビットコイン・プロトコルによって最も促進されるものである。
【００８３】
ビットコイン・コミットメントの場合、各々のユーザーは、彼らが制御／所有する特定のアドレスで未使用BTCを使用し、これをコミットメント・トランザクション2の入力4として含め、各自の入力4に署名する。コミットメント・トランザクション2における投票者の入力4は投票者によってのみ署名され、ただし投票者は、コミットメント・トランザクション2の他の利用可能な詳細とともに充足されるものと仮定される。リファンド・トランザクション12もまた総ての関係者によって署名されているべきである。各々のユーザーは各自の投票に対して同じ量のビットコイン（xBTC）をコミットするように期待されるが、このことは必須ではない。
【００８４】
「投票コミットメント」の場合に、TSSVプロトコルの文脈で候補Bに対する投票者Uiによる投票viは：Uiの下でのキーkBのうちのシークレット・シェアkB,i；及び候補Bに対する識別値の連結として表現される。票は、vi=kB,i||IDCandidateBのような方法で表現されてもよい。ここで、kB,iはキーkBのうちの投票者Uiにより保持されているシェアであり、||は連結を表現する。
【００８５】
viのキー・シェア成分は、候補Bが十分な票を獲得した場合に、総ての票の蓄積されコミットされたファンドを候補Bが請求することを部分的に許容する役割を果たす。票viは必ずしもそのままVCT2に埋め込まれず；好ましくは、投票者が票を投じることを望む候補（この例では、候補B）の公開鍵で先ず暗号化される。暗号化された票は、vi^=EncB(vi)のように表現されることが可能である。
【００８６】
候補Bがvi^を解読しようとする場合、成分IDCandidateBは、首尾よく解読に成功した候補Bに対するインジケータとして役立つ。IDCandidateBのビット・サイズは、不適切な解読（プライベート）キーが暗号文vi^から値・文字列||IDCandidateBを生成できそうにない程度に十分大きくあるべきである。
【００８７】
ビットコイン・トランザクションがメタデータのストレージに専用のフィールドを有しない場合、TSSVプロトコルの成功は、参加者の票を記録するために適切な場所を発見することにかかっている。プロトコルの設計が、総ての票が1つのコミットメント・トランザクション（VCT2）で表現されるようになっている場合、これは票コミットメントのセットを組み込む際に何らかの制約を追加する。
【００８８】
TSSVの提案される設計では、票は、m-of-nマルチシグネチャ・トランザクションのビットコイン・スクリプトを使用して保存される。m-of-nマルチシグネチャ・スクリプトは以下のフォーマットを採用する：
【００８９】
【数２】
2020532221.tif 000004
ここで、太字部分の内容は＜scriptPubKey＞のものであり、及び下線部の内容は＜scriptSig＞のものである。＜scriptPubKey＞はトランザクション出力が使用されることを許可するルールセットである。＜scriptSig＞は＜scriptPubKey＞を充足する要求される内容である。NumSigsは要求される署名数であり、Numkeysは可能な署名数であり、PubXは署名SigXに対応する公開鍵である。スクリプトはm-of-n署名に意図されているが、レディーム・スクリプトのPubX要素はメタデータの記憶に使用するために相応しいかもしれない。
【００９０】
一例として、2-of-4マルチシグネチャ・スクリプトが示され、公開鍵に確保された4データ要素のうちの2つがメタデータを格納するために使用される。スクリプトは以下のフォーマットを使用する：
【００９１】
【数３】
2020532221.tif 000005
我々の目的に関し、メタデータ要素はユーザーの一群の暗号化された票{vi^：i∈[1,n]}を表すことができる。
【００９２】
一例として、1-of-7マルチシグネチャ・スクリプトが示され、公開鍵のために予約されている7つのデータ要素のうちの5つが暗号化された票を保存するために使用され、真の公開鍵に2つが使用される。スクリプトは以下のフォーマットを使用する：
【００９３】
【数４】
2020532221.tif 000006
ビットコイン・プロトコルの現在のバージョンでは、マルチシグ出力で許容される公開鍵の最大数は15である。この理由により、説明されるm-of-nスクリプトが許容され得る最大投票数（投票者数）は13である（（15のうちの）2つの場所は候補A又はBの公開鍵のために確保されることに留意を要する）。少なくとも2つの公開鍵が、各々の候補（例えば、候補A）、メイン公開鍵、及びkA,iキー・シェアに基づいて協働して導出される公開鍵に取り付けられる。しかしながら、重要なことに、複数のm-of-nマルチシグ・スクリプトが1つのより長いスクリプトの中で使用されることが可能である。具体例として、何れの候補が支払を受けたかを決定するために、if-else条件がスクリプトの中で使用され得る。スクリプトの中の各々のオプションは、自身のm-of-nセグメントをスクリプト内に有することが可能であり、少なくとも26個の可能な票の包含をもたらす。より手の込んだスクリプトはより多くの票を組み込むように構成され得るが、スクリプトの最大サイズは今のところ10キロバイト（ビットコイン・スクリプト・インタープリタで更に詳細に説明されている−https://github.com/bitcoin/bitcoin/blob/fcf646c9b08e7f846d6c99314f937ace50809d7a/src/script/interpreter.cpp#L256）であること、及びトランザクション・コストはトランザクションのサイズに依存することに留意を要する。
【００９４】
m-of-nビットコイン・スクリプトの公開鍵要素の利用は、ビットコイン・プロトコルに対する公開鍵に課せられるサイズ制約に考慮がなされるべきことを要求する。これは、公開鍵はvi^を保存するために割り当てられ、vi^は同じビット長によるものであり且つvi=kB,i||IDCandidateBの暗号化であることを念頭に置いている。
【００９５】
提案されるTSSVプロトコルでは、ビットコイン楕円曲線ディジタル署名アルゴリズム（ECDSA）署名（ファンドを請求するために勝利候補にとって最終的に要求される）は、256ビット・プライベート・キー（例えば、https://en.bitcoin.it/wiki/Private_keyにおけるPrivate  keyを参照されたい）を必要とすることに留意すべきである。256ビット（32バイト）のプライベート・キーを再構築するために、キー・シェア自体も256ビットの長さであることを要する。
【００９６】
ビットコイン・プロトコルは（256ビット長の）楕円曲線（EC）暗号化を利用し、公開鍵kGは曲線上の点にあり；各座標は256ビットによるものである。この点については次の文献に詳細に説明されている：
Franco,  P.,  2014.  Understanding  Bitcoin:  Cryptography,  engineering  and  economics.  John  Wiley  &  Sons。
ビットコイン・プロトコルは、圧縮された又は圧縮されていない点としてEC公開鍵の表現を許容する。圧縮された点の場合、EC点のx値（256ビット）のみが保存されるが、非圧縮の点の場合、x及びyの値双方が保存される（それぞれが256ビットによるものである）。
【００９７】
これが意味することは、非圧縮公開鍵がm-of-nスクリプトに使用される場合、256ビット・キー・シェア及び候補IDの連結について十分なストレージ空間が存在することである。EC点のx座標の256ビットはキー・シェアkB,iに使用されることが可能であるが、yの値のために確保される他方の256ビットは候補IDを保存するために使用され得る。
【００９８】
投票システムでは、通常、ユーザーの票が投票者まで追跡されないことが望ましい。提案されるTSSVプロトコルに関し、投票者が各自のvi^を存在するvis^の集合／リストに単に追加するならば、他の投票者は自ら又は協働して投票者のvi^を決定することができる。第1投票者が各自のvi^を票のリストに追加する場合を考察する。第2投票者は、リスト中に既に存在する（暗号化された票）が第1投票者によるものであることを容易に知ることができるであろう。これはvi自体ではなく暗号文vi^を知らせるだけであるが、このことは、投票者をviにリンクさせる上で、悪意の投票者／参加者をより有利な状況に置いてしまう。
【００９９】
より重要なことに、票の暗号化が2つの候補のうちの一方の公開鍵で行われる状況において、票のシャッフルは、候補者（A又はB）が投票者を票に結び付けることから防止する。仮にシャッフルしなかった場合、候補者がvi^を解読できる状況の下で、候補者は、1人以上の投票者の協働により、投票者を票に結び付けることが可能である。TSSVプロトコルにおいて唯2人の候補者しか存在しない場合、候補者が票を解読できないことは、その票は他方の候補者に対するものであることを意味することにも留意すべきである。
【０１００】
この理由により、TSSVプロトコルに関し、ユーザーが各自の票を＜scriptPubKey＞に提供するプロセスに、シャッフル・ソリューションが組み込まれる。シャッフル・ソリューションの具体例は上記のようなものであり、それらのうちの何れがTSSVプロトコルのインスタンスで使用されてもよい。TSSVの目的で使用されるシャッフル・ソリューションの基本的な責務は、他の任意の投票者又は投票者でない者が、どの（暗号化された）票がどの投票者から由来するかを決定できることなく、各々の投票者が各自の（暗号化された）投票を提供できるようにすることである。
【０１０１】
従って、暗号化された票の集合{v1^,v2^,...,vn-1^,vn^}は、任意の投票者又は候補者（又はそれ以外の者）が、集合中の何れの要素が何れの投票者から由来しているかを知ることなく、作成されることが可能である。
【０１０２】
TSSVプロトコルは、勝利した候補のみが、プールされたビットコインを収集できるような方式で設計される。この制約は閾値シークレット方式により促進され、この方式では、{ki:i∈[1,n]}というシェアの集合中のt+1個のシェアがシークレットkを決定するために使用され得る。tはシークレット・キー・シェアを計算するために使用される多項式の次数である。
【０１０３】
2つの候補（A及びB）の各々には公開鍵が指定される。
PubA=kAG
PubB=kBG
ここで、Gは楕円曲線（EC）の基準点であり、kGはECの「スカラー倍数点（point-multiplication-by-scalar）」の一例である。GはEC上の基準点であり、kはスカラー値である。
【０１０４】
kA及びkBの値は、プロトコルの先行する段階では（誰にも、候補者、又は投票者にとって）未知である。これらのkA及びkBの値は、ユーザー達が特定の候補に対して十分な数の票を提出した場合に決定され得るだけである。これらのユーザー投票は、選択の投票者の候補に依存するkA又はkBのキー・シェアを含む。kA及びkBのキー・シェアは次のようなものである：
kA≡f(kA,1,kA,2,...,kA,n)
kB≡f(kB,1,kB,2,...,kB,n)
【０１０５】
一例として、投票者の投票コミットメントは、彼らが候補Bに投票することを選択する場合、次のようであってもよい：
vi=kB,i||IDCandidateB
値kB,iはキーkBのキー・シェアであり、投票者Uiに以前に分配されているシェアである。
【０１０６】
理論上、キー・シェアの分配はディーラーに基づくもの（ディーラー・ベース）、又はディーラーによらないもの（ディーラー・レス）であるとすることが可能である。ディーラー・ベースの分配の場合、ディーラーはkA及びkBを知っており、kA及びkB双方のキー・シェアを分配する。シェアkB,i及びシェアkA,iの所有に係わる参加者は正当な参加者と考えられてよい。このディーラーは、何れかの候補であってはならず、そうではなく第三者でなければならない。候補A又はBがディーラーであった場合、何れかの候補はTSSVの出力に署名することができ、悪意の候補者が総てのシークレット・キーを知った場合、必要な票を勝ち取ることなく、プールしたファンドを総て収集できてしまう。ディーラー・レス実装の場合、各々の投票者が各自自身のキー・シェアを構築する。投票者達は、公開鍵PubA=kAG及びPubB=kBGを計算するために、上述したようなシークレット共有結合を利用して協働する。
【０１０７】
PVSS方式は、候補者及び投票者がPubA及びPubBを考慮してキー・シェアを検証するために使用される。ディーラーにキー・シェアを配分してもらうことは、適確な投票者のリストに関して適切な権限コントロールをもたらし；これにより、キー・シェアのオーナーシップは、投票適格性の認証として理解され得る。
【０１０８】
候補Bが十分な票（kB,iシェア）を獲得できる場合、候補BはシークレットkBを構築し、投票コミットメント・トランザクション2の出力を署名する際にこのkBを使用して、プールされたコミットされたビットコインを収集することができるであろう。
【０１０９】
シャミールのシークレット共有の実装に関し、多項式の次数は、候補者が勝利するために必要な投票数と投票者数とを考慮して選択されなければならない。勝利候補は最多投票数を達成しなければならず、勝利候補が受けた投票数も指定された閾値より大きくなくてはならない。一例として、図2は、候補が勝利するために必要な票の数と、投票者数の変化に対する多項式の次数とを示す。勝利する候補に必要な最低票は、より大きな閾値が望まれる場合に高くなり得る。具体例として、政策提案が受け入れられるために、政府の国民投票は、過半数、及び少なくとも75％の票の双方を必要とし得る。
【０１１０】
票を集めて勝つために、勝利候補BはPubBに対する署名8bより多くを提供する必要がある（図4）。公開鍵PubA/PubBを割り振ることに加えて（対応するプライベート・キーは分割される）、候補者A及びB双方それぞれが各自自身の別個の（メイン）公開鍵PubAm及びPubBmを所有する。候補者AはPubAmに対するプライベート・キーを知っており、候補者BはPubBmに対するプライベート・キーを知っている。
【０１１１】
この余分な公開鍵の必要性は、t+1人の投票者の任意の集合は理論的には協働してkBを計算し、蓄積されたファンドを盗み得るという事実に起因している。これは、余分な公開鍵に基づく署名6bに関する条件は存在せず、候補者だけに知られるプライベート・キー（公開鍵に対応するもの）は更にそうであるという事実に起因する。この理由により、公開鍵pubBMの勝利候補の署名6bもまた、勝利候補（候補B）が、蓄積されたファンドを請求するために必要となる。
【０１１２】
この点に留意して、我々は、プールされたビットコインが請求され得るビットコイン・スクリプトに関して異なる方法を考察する。投票コミットメント・トランザクション2の＜scriptPubKey＞は、収集支払についての3方法の考察を含む。
【０１１３】
これらのルールのうちの第1は以下のサブスクリプトにより＜scriptPubKey＞において表現される：
【数５】
2020532221.tif 000007
ここで、サブスクリプトという用語は、より大きなスクリプトのうちのセグメントを記述するために使用される。このケースでは、より大きなスクリプトは＜scriptPubKey＞である。このスクリプトは、最も多くのビットコイン・トランザクション・アウトプットが保護される基本方法を示す；それは、包含される公開鍵に対する署名を単に必要とする。投票コミットメント・トランザクション（VCT）2に関し、このサブスクリプトは、TSSVプロトコルの実行が予定されているように進行しない場合、即ち勝利選択肢が存在しない場合、あるいは勝利選択肢が投票コミットメント・トランザクションを履行しない場合に、各自がコミットしたビットコインの払い戻しを得るようにユーザーの能力を制御する。リファンド・トランザクション12のブロックチェーンへのサブミッション成功は、公開鍵PubSに対する署名を含む＜scriptSig＞に依存する。この公開鍵は、投票者のうちの1人が署名できる公開鍵であるとすることが可能であり、あるいは分配されたキー・シェアの個々の集合に基づく公開鍵であるとすることが可能である。後者の選択肢の場合、PubSの署名を取得することは、プライベート・キーを構築し、署名を生成するために少なくともt+1人の投票者間の協働作業となる。
【０１１４】
以下の事項に留意を要する：
・署名されたリファンド・トランザクション12のコピーは、VCT2がブロックチェーンにサブミットされる前に総ての投票者に対して利用可能である。
・リファンド・トランザクション12はnLockTime値を含み、これは指定された時点（例えば、ユニックス時間又はブロック高さ）を経過しない限り、リファンド・トランザクション12のブロックチェーンへのサブミッションを妨げる。
・リファンド・トランザクション12は、ユーザーがコミットしたビットコインを各ユーザーに戻す。
【０１１５】
VCT2のプールされたファンドを請求するこれらのオプションの第2ルールセットは、2つの要求された署名6a,8a（図4）を生成する候補Aの能力に応じて、候補Aがプールされたファンドを請求できるようなものである。（以下に示される）サブスクリプトは2-of-15マルチシグであり、即ち一群の15個の公開鍵フィールドの中で発見される2つの公開鍵フィールドに対応する署名を要求する。13人より少ない投票者しかいない場合、15個より少ないフィールドしか存在しなくてもよい。
【数６】
2020532221.tif 000008
【０１１６】
このサブスクリプトは二重の目的に役立つ。これらの責務のうちの第1は暗号化された（高々13個の）票を含むことであり、第2は、候補者Aがプールされたビットコインを請求することを、彼が公開鍵PubA及びPubAm各々の署名8a,6aを生成できる場合に許容することである。PubA=kAG及びPubAの署名8aはkAを発見するためにv1^値の中で発見されたシークレット値を利用して取得される。これは当然にスクリプト内の候補Aに対する票が十分に存在することに依存する。候補Aに対する各々の票は、シェアkA,iを有し、候補Aの公開鍵（好ましくは、PubAm）で暗号化される。PubAmは候補Aにより生成される公開鍵であり、従って候補Aはこの（メイン）公開鍵に対する署名6aを生成することができるはずである。PubAmの署名6aは候補Aの責務であり、なぜならPubAmを生成したのは候補Aだったからであり、これはPubAmの対応するプライベート・キーPrivAMを所有しているからである。
【０１１７】
第3ルールセットは第2のものに類似し、少なくとも2つの署名の提供に基づいてVCTファンドを請求する能力を候補Bに対して許可又は否定するために、追加的な票を含むように意図されている。これは以下のように示される。
【数７】
2020532221.tif 000009
このケースにおいて、m-of-nサブスクリプトでは、再び投票／メタデータに相応しい高々13個のフィールドが存在する一方、2つのフィールドが正当な公開鍵として使用するために割り振られている。実際に署名を要求する公開鍵はPubB及びPubBmである。PubB=kBGは、kB,iシェアに対応する公開鍵である。候補Bに対して少なくともt+1個の票が候補Bに対するm-of-nスクリプト中に存在することは、候補Bが、kB,iキー・シェアを利用してPubBの署名8bを生成することを許容する。PubBmを生成した候補Bは従って署名8aを生成することができるはずである。これら双方の署名8a,8bを提供することは、候補Bが、投票コミットメント・トランザクション2のプールされたビットコインを集めることを許容する。
【０１１８】
以下の事項に留意すべきである：
・2つのm-of-nサブスクリプトのうちの何れにおいて暗号化投票が発見されるかは問題ではなく：総てのvi^がブロックチェーンの中で双方の候補にとって可視的であり、双方の候補は、署名が要求される各自の公開鍵の各自のキー・シェアを取り出そうとして、候補A又は候補Bのm-of-nサブスクリプトのうちの何れかからvi^を解読することを試みることが可能である。
・t+1は候補者が処理するために必要な投票の閾値であり、tは多項式ベースのシークレット共有メカニズムで使用される多項式の次数である。
・tは、t+1が過半数の票であることを保証するように選択され、この場合における票は2候補間での選択である。
【０１１９】
図3を参照すると、本発明を組み込むプロセス300を示すフローチャートが示されている。先ず、ステップ302において、投票者数nに関して決定がなされる。上述した鍵共有技術を利用して、ステップ304において、プライベート・キーkAについてn個のシェアが作成される。同様に、キーkBについてn個のシェアが作成される。これらのプライベート・キーは、公開鍵PubA及びPubBにそれぞれ対応する。
【０１２０】
各々の投票者に、kAに属する固有のシェアkA,iとkBに属する固有のシェアkB,iとがステップ306において与えられる。次いで投票者達はステップ308においてkA,iキー・シェアを利用して協働し、シークレット共有結合を利用してPubA=kAGを算出し、同様にkB,iキー・シェアを利用して協働し、PubB=kBGを算出する。次いでPubA及びPubBがステップ310において総ての投票者及び候補者に伝達され、PubA及びPubBを考慮してキー・シェアを検証するために、キー・シェア方式が利用される。次いで、候補者A及びB各々はステップ312において個々のメイン公開鍵PubAm及びPubBmをそれぞれ作成する。
【０１２１】
ステップ314において、各々の投票者は、自身のシークレット・シェアと選択する候補者のIDとを連結して（vi=kB,i||IDCandidateB）を提供することにより投票を行う。
【０１２２】
ステップ316において、各々の投票者は、自身の投票を、選択する候補者の公開鍵で暗号化する。例えば、候補者Bの場合、暗号化された投票は次のようになる：
【数８】
2020532221.tif 000010
【０１２３】
ステップ318において、各々の投票者は自身の投票をリストに拠出し、これは、ユーザーと投票との間に結び付きが無くなるように、上述したようにシャッフルする技術を利用して行われる。次いでステップ320において投票者コミットメント・トランザクション2が作成される。これは各投票者からの入力を含む。各投票者はある量のビットコインxBTCを拠出する。
【０１２４】
ステップ322において、nxBTCという値の投票者コミットメント・トランザクション2の出力は、m-of-nスクリプトにより管理され、そのスクリプトによりpubkey要素が、暗号化された票の記憶として各自使用するために割り当てられる。投票者コミットメント・トランザクション2のこの出力スクリプトは：
xBTCの各投票者への払い戻し
候補者Aが署名σ(Am)及びσ(A)を利用してxBTCを集めること
候補者Bが署名σ(Bm)及びσ(B)を利用してxBTCを集めること
を許容する。
【０１２５】
次いでステップ324においてリファンド・トランザクション12が作成され、署名され、コピーが各々の投票者に配布される。次いで投票者コミットメント・トランザクション2はブロックチェーンにサブミットされる。
【０１２６】
ステップ326において、候補者Bは総てのvi^値を解読しようと試みる。解読プロセスが、候補者BのIDを、viの後半のセグメントとして明らかにしたならば、候補者Bは、viの第1の（前半の）セグメントをシークレット・シェアkB,iとして認識する。候補者Bが十分な票（シェア）を受けている場合、彼は出力を署名することができる。候補者Aは、候補者Bで実行されたものと実質的に同じプロセスを実行する。
【０１２７】
最終的に、ステップ328において、リファンド・トランザクション12のnLockTimeの前に何れの候補者も各自の勝利を主張できない場合、リファンド・トランザクション12が任意の投票者によりサブミットされ、それぞれの投票者のコミットしたファンドが、トランザクション・コストを差し引いて投票者に返される。
【０１２８】
図7をここで参照すると、本開示の少なくとも1つの実施形態を実施するために使用され得るコンピューティング・デバイス2600の例示的な簡略化されたブロック図が提供されている。様々な実施形態において、コンピューティング・デバイス2600は上記に例示及び説明される任意のシステムを実装するために使用され得る。例えば、コンピューティング・デバイス2600は、データ・サーバー、ウェブ・サーバー、ポータブル・コンピューティング・デバイス、パーソナル・コンピュータ、又は何らかの電子コンピューティング・デバイスとして使用するために構成され得る。図7に示されるように、コンピューティング・デバイス2600は、1つ以上のレベルのキャッシュ・メモリとメモリ・コントローラとを有する1つ以上のプロセッサを含むことが可能であり、プロセッサは、メイン・メモリ2608とパーシステント・ストレージ2610とを含むストレージ・サブシステム2606と通信するように構成されることが可能である（まとめて2602というラベルが付される）。メイン・メモリ2608はダイナミック・ランダム・アクセス・メモリ（DRAM）2618とリード・オンリ・メモリ（ROM）2620とを図示のように含むことができる。ストレージ・サブシステム2606とキャッシュ・メモリ2602とは、本開示で説明されるトランザクション及びブロックに関連して詳細に説明されるような情報のストレージに使用されることが可能である。プロセッサ2602は本開示で説明される任意の実施形態のステップ又は機能を提供するために使用されることが可能である。
【０１２９】
プロセッサ2602はまた1つ以上のユーザー・インターフェース入力デバイス2612、1つ以上のユーザー・インターフェース出力デバイス2614、及びネットワーク・インターフェース・サブシステム2616と通信することも可能である。
【０１３０】
バス・サブシステム2604は、コンピューティング・デバイス2600の様々なコンポーネント及びサブシステムが、意図されるように互いに通信できるようにするメカニズムを提供することができる。バス・サブシステム2604は単独のバスとして概略的に示されているが、バス・サブシステムの代替的な実施形態は複数のバスを使用することが可能である。
【０１３１】
ネットワーク・インターフェース・サブシステム2616は他のコンピューティング・デバイス及びネットワークに対するインターフェースを提供することができる。ネットワーク・インターフェース・サブシステム2616は、コンピューティング・デバイス2600の他のシステムからデータを受信し、他のシステムへデータを送信するためのインターフェースとして機能することができる。例えば、ネットワーク・インターフェース・サブシステム2616はデータ技術者がデバイスをネットワークに接続できるようにし、その結果、データ技術者はデータ・センタ等の遠隔地にいながらにして、デバイスにデータを送信し及びデバイスからデータを受信することができる。
【０１３２】
ユーザー・インターフェース入力デバイス2612は、キーボード；統合マウス、トラックボール、タッチパッド、又はグラフィックス・タブレット等のポインティング・デバイス；スキャナ；バーコード・スキャナ；ディスプレイに組み込まれたタッチ・スクリーン；音声認識システム、マイクロフォン等のオーディオ入力デバイス；及び他のタイプの入力デバイス等の1つ以上のユーザー入力デバイスを含むことができる。一般に、「入力デバイス」という用語の使用は、コンピューティング・デバイス2600に情報を入力するための全ての可能なタイプのデバイス及びメカニズムを含むように意図される。
【０１３３】
1つ以上のユーザー・インターフェース出力デバイス2614は、ディスプレイ・サブシステム、プリンタ、又は、オーディオ出力デバイス等の非視覚的ディスプレイを含むことができる。ディスプレイ・サブシステムは陰極線管（CRT）、液晶ディスプレイ（LCD）や発光ダイオード（LED）ディスプレイ等のフラット・パネル・デバイス、又はプロジェクションその他のディスプレイ・デバイスを含むことができる。一般に、「出力デバイス」という用語の使用は、コンピューティング・デバイス2600から情報を出力するための全ての可能なタイプのデバイス及びメカニズムを含むように意図される。1つ以上のユーザー・インターフェース出力デバイス2614は、例えば、説明されたプロセス及びその変形のプロセスを実行するアプリケーションとのユーザー相互作用を、そのような相互作用が適切である場合には促進するユーザー・インターフェースを提供するために使用されることが可能である。
【０１３４】
ストレージ・サブシステム1206は、本開示の少なくとも1つの実施形態の機能を提供することが可能な基本プログラミング及びデータ構造を格納するコンピュータ読み取り可能な記憶媒体を提供することができる。アプリケーション（プログラム、コード・モジュール、命令）は、1つ以上のプロセッサにより実行されると、本開示の1つ以上の実施形態の機能を提供することができ、ストレージ・サブシステム2606に格納されることが可能である。これらのアプリケーション・モジュール又は命令は1つ以上のプロセッサ2602により実行されることが可能である。ストレージ・サブシステム2606は本開示に従って使用されるデータを格納するリポジトリを追加的に提供することができる。メイン・メモリ2608及びキャッシュ・メモリ2602は揮発性ストレージにプログラム及びデータを提供することができる。パーシステント・ストレージ2610は、プログラム及びデータをパーシステント（不揮発性）ストレージに提供することが可能であり、フラッシュ・メモリ、1つ以上のソリッド・ステート・ドライブ、1つ以上の磁気ハード・ディスク・ドライブ、関連する取り外し可能な媒体を有する1つ以上のフロッピー・ディスク・ドライブ、関連する取り外し可能な媒体を有する1つ以上の光ドライブ（例えば、CD-ROM又はDVD又はブルーレイ）ドライブ、及びその他のストレージ媒体を含むことが可能である。このようなプログラム及びデータは、本開示で説明されるような1つ以上の実施形態のステップを実行するためのプログラムだけでなく、本開示で説明されるトランザクション及びブロックに関連するデータをも含むことが可能である。
【０１３５】
コンピューティング・デバイス2600は、ポータブル・コンピュータ・デバイス、タブレット・コンピュータ、ワークステーション、又は以下に説明される何らかの他のデバイスを含む任意の様々なタイプのものであるとすることが可能である。更に、コンピューティング・デバイス2600は、1つ以上のポート（例えば、USB、ヘッドフォン・ジャック、照明コネクタ等）を通じてコンピューティング・デバイス2600に接続されることが可能な他のデバイスを含むことが可能である。コンピューティング・デバイス2600に接続され得るデバイスは、光ファイバ・コネクタを受け入れるように構成される複数のポートを含むことが可能である。従って、このデバイスは、光信号を電気信号に変換するように構成されることが可能であり、電気信号は、処理のためにデバイスをコンピューティング・デバイス2600へ接続するポートを介して伝送されることが可能である。コンピュータ及びネットワークの不断に変化する性質に起因して、図7に示されるコンピューティング・デバイス2600の説明は、デバイスの好ましい実施形態を説明する目的のための特定の例として意図されている。図7で説明されるシステムのものより多い又は少ないコンポーネントを有する他の多くの構成が可能である。
【０１３６】
上述した実施形態は本発明を限定するのではなく例示していること、及び当業者は、添付の特許請求の範囲に記載されている本発明の範囲から逸脱することなく、多くの代替的な実施形態を設計できることに留意すべきである。特許請求の範囲において、括弧内に配置される如何なる参照符号も特許請求の範囲を限定するように解釈されないこととする。「有している」及び「有する」等の言葉は、任意の請求項又は明細書全体の中で列挙されているもの以外の要素又はステップの存在を排除していない。本明細書において、「有する」は「含む又はから成る」を意味し、「有している」は「含んでいる又はから構成されている」を意味する。要素単独の参照はそのような要素複数個の参照を排除しておらず、逆もまたそうである。本発明は、幾つかの個別的な要素を有するハードウェアにより、及び適切にプログラムされたコンピュータにより実装されることが可能である。幾つかの手段を列挙するデバイス・クレームにおいて、これら幾つかの手段はハードウェアの1つの同じアイテムにより具現化されることが可能である。所定の複数の事項が相互に異なる従属請求項に記載されているという単なるその事実は、これらの事項の組み合わせが有用に利用できないことを示してはいない。
【図１】
2020532221.tif 000011
【図２】
2020532221.tif 000012
【図３】
2020532221.tif 000013
【図４】
2020532221.tif 000014
【図５】
2020532221.tif 000015
【図６】
2020532221.tif 000016
【図７】
2020532221.tif 000017
【国際調査報告】
2020532221.tif 000018
2020532221.tif 000019
2020532221.tif 000020