(57)【要約】  本発明は、ディーラーフリーのしきい値署名グループによる計算タスクに対する解法(S)の安全な決定に関する。リソース又は報酬へのアクセスは、その解法と引き換えに提供される。その方法は、そのグループの中の個人が、トラストレスの又はディーラーフリーの方式によって協調することを可能とする。このことを達成するために、個人は、自身の鍵の対を生成し、自身の公開鍵を使用して、そのグループとの間で、それらの個人のすべてが使用することが可能である初期の共有されている公開鍵を確立し、並行して、そのタスクに対する解法を発見する。検証されるとともに共有される公開鍵は、解法が発見されそして検証されるときに使用される初期の共有されている公開鍵を使用して作成されるので、それらの個人の自身の秘密鍵は、秘密のままであり、したがって、その協調は、トラストレスであり、効果的に動作する。リソース又は報酬は、その検証されるとともに共有される公開鍵によって保護されてもよい。各々の参加者の秘密鍵は、その解法につながる初期の共有されている公開鍵の決定の際に使用され、対応する共有されている秘密鍵は、すべての参加者又は参加者のあらかじめ合意されているしきい値によってのみ生成されるため、参加者は、その次に、リソース又は報酬のロックを解除するために協調する必要がある。初期の共有されている公開鍵を使用し、そして、解法を発見した後に検証されているとともに共有されている公開鍵をグループで計算することによって、効率を達成することが可能である。本発明は、シャミアの秘密共有方式を適用するときに、楕円曲線暗号の同形特性を使用することによって、そのタスクがトラストレスとなることを可能とする。本発明の概念は、グループが協調することが可能である安全でトラストレスであり且つ効率的な方法に属する。本発明は、タスクに対して不可知的であってもよい。
2021507276.tif 000002
【特許請求の範囲】
【請求項１】
複数の参加者(P)を有するグループ又はプールされているリソースによる計算タスクに対する解法(S)の安全な決定のためのコンピュータにより実装される方法であって、前記グループは、トラストレスの又はディーラーフリーのシステム又は方式によって動作し、当該コンピュータにより実装される方法は、
n個の参加者(P1…n)を有するグループ(P)を確立するか又は前記グループ(P)に参加するステップであって、n≧2である、ステップと、
初期の秘密鍵の持ち分(sn0)及び初期の公開鍵の持ち分(pk1)を生成し、そして、前記グループとの初期の共有されている公開鍵(pkO)を確立するステップと、
前記タスクを実行し、そして、前記解法(S)を探索するステップであって、前記解法(S)は、中間秘密鍵(rn0)及び前記グループの前記共有されている公開鍵(pkO)を使用して、前記タスクに対する回答(Ac)を決定する、ステップと、
前記解法(S)を発見し、そして、前記グループとの間で前記解法(S)を共有するか、又は、他の参加者から前記解法(S)を受信し、それにより、前記グループが、前記タスクに対する前記解法を検証することを可能とする、ステップと、
前記解法(S)を提供した前記中間秘密鍵(rn0)及び前記初期の共有されている公開鍵(pk0)を使用して、検証されるとともに共有される公開鍵(pkv)を前記グループで計算するステップと、
前記解法(S)を提供した前記中間秘密鍵(rn0)及び前記初期の秘密鍵(son)の総和をとることによって、検証されている秘密鍵の持ち分(sv0)を構築するステップと、
前記他の参加者のすべて又は参加者のしきい値数と協調して、検証されている秘密鍵の持ち分(sv0)を使用することによって、前記検証されるとともに共有される公開鍵(pkv)に対する検証されるとともに共有される秘密鍵(skv)を構築するステップと、を含み、前記検証されるとともに共有される秘密鍵(skv)は、前記グループが、プロセスのリソース又はステージのロック解除又はアクセスのために集合的に動作することを可能とするコードとして使用される、
コンピュータにより実装される方法。
【請求項２】
クライアント(C)又は参加者(P)から、クライアントの秘密鍵(skc)から導き出されるクライアントの公開鍵(pkc)及び前記タスクを受信するステップをさらに含み、前記クライアントの公開鍵は、前記タスクに対する前記解法の前記決定の際に使用される、請求項1に記載のコンピュータにより実装される方法。
【請求項３】
前記タスクを実行し、そして、前記解法(S)を探索するステップは、
前記中間秘密鍵(rn0)を使用して、前記初期の共有されている公開鍵(pkO)に追加される中間公開鍵(Rn0)を作成し、そして、前記中間秘密鍵(rn0)が探索された前記回答(Ac)を決定した解法であったか否かを決定するように処理される一時的な公開鍵(pknR)を作成するステップと、
前記回答(Ac)が決定されない場合に、前記中間秘密鍵(rn0)の前記値を増加させ、そして、前記解法(S)が決定され、且つ、前記回答(Ac)が証明されるまで前記処理を繰り返すステップと、を含む、請求項1及び2のうちのいずれか1項に記載のコンピュータにより実装される方法。
【請求項４】
前記初期の共有されている公開鍵(pk0)及び前記検証されるとともに共有される公開鍵(pkv)は、一度だけ生成される、請求項1乃至3のうちのいずれか1項に記載のコンピュータにより実装される方法。
【請求項５】
前記タスクは、少なくとも1つのグループメンバーが解法を発見することを必要とし、前記解法は、処理されると、特定のパターンを有する暗号通貨アドレスを生成する、請求項1乃至3のうちのいずれか1項に記載の方法。
【請求項６】
前記タスクは、セットパターン(A)の前記決定を必要とし、前記セットパターンは、第三者又は他の参加者に由来し、前記第三者は、第三者秘密鍵(skc)を生成し、そして、前記グループに、対応する第三者公開鍵(pkc)を提供し、pkc＝skc×Gであり、Gは、楕円曲線基準点であり、前記第三者公開鍵(pkc)を受信し、前記セットパターンを決定するときに、pk＝pkc＋i×Gとなるように、増加変数(i)とともに前記第三者公開鍵(pkc)を使用して前記セットパターンを決定し、前記第三者に、前記解法の決定を可能とする前記増加変数(i)を送信し、それによって、前記第三者は、楕円曲線点乗算の同形特性に起因して、前記第三者のランダムな秘密鍵(skc)を使用して、前記解法を検証することが可能であり、sk＝skc＋iであり、pk＝sk×Gである、請求項1乃至5のうちのいずれか1項に記載の方法。
【請求項７】
n個の参加者の前記グループは、安全な複数当事者の計算(MPC)によって、生成する、請求項1乃至6のうちのいずれか1項に記載の方法。
【請求項８】
前記初期の共有されている公開鍵(pkO)は、シャミアの秘密共有スキームを使用して前記グループの間で確立される、請求項1乃至7のうちのいずれか1項に記載の方法。
【請求項９】
前記共有されている秘密鍵(skv,sko)は、シャミアの秘密共有スキームを使用して前記グループの間で確立され、参加者自身のランダム次数tの多項式fi(x)を生成し、そして、その次に、各々の他の参加者Pjにfi(j)を安全に送信することによって、各々の参加者Piの間で、トラストレスの関係を確立し、各々の参加者は、前記受信したすべての点の総和f1(i)＋f2(i)＋…＋fn(i)をとって、前記共有されている多項式f(x)の前記Pi点である参加者の秘密の持ち分si＝f(i)を取得する、請求項1乃至8のうちのいずれか1項に記載の方法。
【請求項１０】
前記初期の秘密鍵の持ち分(sn0)の作成に続いて、bisn×Gであるときに、楕円曲線基準点Gを使用して前記初期の公開鍵の持ち分(pk1)を計算し、前記補間係数biは、
【数１５】
2021507276.tif 000017
であり、前記初期の公開鍵の持ち分は、その次に、すべての参加者にブロードキャストされ、前記初期の共有されている公開鍵(pko)は、その次に、
【数１６】
2021507276.tif 000018
にしたがって、いずれかのt＋1個の持ち分の前記総和として計算される、請求項1乃至9のうちのいずれか1項に記載の方法。
【請求項１１】
前記タスクは、クライアント(C)又は参加者(P)から受信されてもよく、前記タスクは、指定されたパターンを有する暗号通貨アドレスのための秘密鍵を発見することであり、
前記中間秘密鍵(rn0)は、ランダムに生成され、中間公開鍵(Rn0)は、(rn0)による前記シード番号の楕円曲線基準点(G)との倍数であり、
前記一時的な公開鍵(Rn0)は、前記共有されている公開鍵(pkO)に加算され、そして、処理されて、暗号通貨アドレスを生成する、請求項1乃至10のうちのいずれか1項に記載の方法。
【請求項１２】
前記解法(S)を提供した前記シード番号(rv0)を有するすべての参加者に対して、
【数１７】
2021507276.tif 000019
から前記検証されるとともに共有される公開鍵を計算し、
svn＝sOn＋rv0から計算される各々の参加者の検証されている秘密鍵の持ち分を計算から、検証される秘密鍵(skv)を計算する、請求項1乃至11のうちのいずれか1項に記載の方法。
【請求項１３】
当該方法は、前記グループとの間で、前記タスクに適用される前記計算リソースを実証可能である中間結果を周期的に共有するステップをさらに含む、請求項1乃至12のうちのいずれか1項に記載の方法。
【請求項１４】
前記中間結果は、前記タスクに対する前記回答(Ac)の一部に対応する、請求項13に記載の方法。
【請求項１５】
前記中間結果は、困難さに比例するレベルを有し、1つ又は複数の参加者は、提示される中間結果の前記頻度及び/又は困難さに基づいて、他の参加者が適用する前記計算リソースを評価する、請求項13又は14に記載の方法。
【請求項１６】
コンピュータ実行可能な命令を含むコンピュータ読み取り可能な記憶媒体であって、前記コンピュータ実行可能な命令が実行されるときに、請求項1乃至15のうちのいずれか1項に記載の方法を実行するようにプロセッサを構成する、コンピュータ読み取り可能な記憶媒体。
【請求項１７】
電子デバイスであって、インターフェイスデバイス、前記インターフェイスデバイスに接続される1つ又は複数のプロセッサ、及び前記1つ又は複数のプロセッサに接続されるメモリを含み、前記メモリは、コンピュータ実行可能な命令を格納し、前記コンピュータ実行可能な命令が実行されるときに、請求項1乃至15のうちのいずれか1項に記載の方法を実行するように前記1つ又は複数のプロセッサを構成する、電子デバイス。
【請求項１８】
ブロックチェーンネットワークのノードであって、当該ノードは、請求項1乃至15のうちのいずれか1項に記載の方法を実行するように構成される、ノード。
【請求項１９】
請求項18に記載のノードを有するブロックチェーンネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、一般的に、ブロックチェーンネットワークのノード等のコンピュータプロセッサ又はそのようなプロセッサのグループにおける実装に適するコンピュータ実装方法及びシステムに関する。計算のセキュリティ及び効率を向上させるために、プールの中又はグループの中で計算タスクを実行するか、或いは、プールの中でタスクを分配する改良された方法を説明する。本発明は、特に、並列的に作業して、あるタスクの解決方法を決定する複数の参加者の間でのトラストレスの(管理者による承認を必要としない)(trust-less)協調(collaboration)に適している。
【背景技術】
【０００２】
本明細書においては、すべての形態の電子的な台帳、コンピュータベースの台帳、分散型の台帳を含む"ブロックチェーン(blockchain)"という語を使用する。これらは、合意に基づくブロックチェーン技術(consensus-based  blockchain  technology)及びトランザクションチェーン技術(transaction-chain  technology)、許可された台帳(permissioned  ledger)及び許可されていない台帳(un-permissioned  ledger)、共有されている台帳(shared  ledgers)、及び、それらの変形を含む。ブロックチェーン技術の最も広く知られている用途は、ビットコイン台帳(Bitcoin  ledger)であるが、他のブロックチェーンの実装が、提案されそして開発されている。本明細書においては、利便性及び説明の目的のために、ビットコインを参照することが可能であるが、本発明は、ビットコインブロックチェーンと関連する使用には限定されず、複数の代替的なブロックチェーンの実装及びプロトコルは、本発明の範囲に属するということに留意すべきである。"ユーザ"という語は、本明細書においては、人間又はプロセッサベースのリソースを指してもよい。
【０００３】
ブロックチェーンは、ピアトゥピアの電子的な台帳であり、そのピアトゥピアの電子的な台帳は、コンピュータベースの非中心化された分散型のシステムとして実装され、そのコンピュータベースの非中心化された分散型のシステムは、複数のブロックから構成され、それらの複数のブロックは、同様に、複数のトランザクションから構成される。各々のトランザクションは、ブロックチェーンシステムの中の複数の参加者の間のディジタル資産の制御の移転を符号化するデータ構造であり、少なくとも1つの入力及び少なくとも1つの出力を含む。各々のブロックは、前のブロックのハッシュを含み、それによって、複数のブロックは、一体となってチェーン化されて、開始以降にそのブロックチェーンに書き込まれているすべてのトランザクションの永続的且つ変更不可能な記録を構成する。複数のトランザクションは、それらのトランザクションの入力及び出力の中に埋め込まれているスクリプトとして知られている複数の小規模のプログラムを含み、それらの複数の小規模のプログラムは、どのようにして及びいずれの者が、それらのトランザクションの出力にアクセスすることが可能であるかを指定する。ビットコインプラットフォームにおいては、これらの複数のスクリプトは、スタックベースのスクリプト化言語を使用して記述される。
【０００４】
ある1つのトランザクションがブロックチェーンに書き込まれるためには、(ｉ)  そのトランザクションは、そのトランザクションを受信する最初のノードによって検証される必要があり、そのトランザクションが検証される場合には、その最初のノードは、そのネットワークの中の他のノードへとそのトランザクションを中継し、(ii)  マイナー(採掘者)(miner)が構築する新しいブロックに追加される必要があり、そして、(iii)  マイニングされる(採掘される)(mined)必要がある、すなわち、過去のトランザクションの公開的な台帳に追加される必要がある。
【０００５】
ブロックチェーンをサポートすることは、大きな計算コストを必要とする。例として、あるブロックをマイニングする際の現時点での困難な点は、単独で作業をする個々のマイナーが、専門家に専用のハードウェア及びリソースを必要とするということである。計算上のタスク及びそれに伴うコストは、複数の個人又は組織の間で分配され、且つ、共有されることがよくあり、それらの複数の個人又は組織は、集合的に、"プール(pool)"と称される。ある1つの例としてブロックチェーンマイニングプール(blockchain  mining  pool)を使用すると、そのブロックチェーンに新たなブロックを追加する際に"Proof  of  Work"を決定するタスクは、個人又は企業によって管理され、その個人又は企業は、以降では、プール"オペレータ(operator)"又はプール"ディーラー(dealer)"と称され、そのプール"オペレータ"又はプール"ディーラー"は、プールサーバの管理下にある。そのディーラーは、プールの代表として行動し、ある特定のアドレスを使用して一括の報酬(block  reward)を受け取り、その報酬は、その後、個々のマイナーが提出する持ち分(shares)、すなわち、個々のマイナーの寄与に基づいて、個々のマイナーとの間で共有される。
【０００６】
残念ながら、ディーラーによる集中制御により、マイニングプールは、不正な行為の影響を受けやすくなり、サーバがクラッシュし、メンテナンスが必要となり、又は攻撃される場合があるため、単一の故障点と解釈されてもよい。ディーラーの必要性を排除しているピアトゥピアマイニングプールは、パフォーマンスに関して妥協を伴う。
【０００７】
他の知られている計算コストの高いタスクの1つの例は、ブロックチェーンに対するトランザクションのためのある特定のアドレスの決定であり、その特定のアドレスは、"バニティーアドレス(vanity  addresses)"と称されることがよくあり、その"バニティーアドレス"は、セキュリティ対策を強化し及び/又は改善するのに使用されてもよい。バニティーアドレスの決定は、楕円曲線乗算及びハッシュ化の双方を必要とする。個人は、計算を実行して、バニティーアドレスを決定することが可能であるが、より長いバニティーアドレスパターンを決定するタスクは、プール全体に分散させられる場合がある。
【０００８】
残念ながら、バニティーアドレスを決定するタスクを分散させると、データの破損と関連するリスクを伴う。バニティーアドレスを決定すると、そのバニティーアドレスの秘密鍵及び公開鍵が既知となり、システムは安全ではなくなる。知られている技術を使用してプールの中での複数の協調者の間の通信を実行する際に、知られているセキュリティ技術を使用すると、グループのパフォーマンス能力を低下させる。さらに、システムは、データの破損及び/又はフリーライディングの影響を受けやすい。
【発明の概要】
【０００９】
概して、本発明は、計算タスクに対する解法(S)の安全な決定のための新規なアプローチに属する。そのタスクは、答えを決定する必要がある。あるリソース又は報酬へのアクセスは、その解法と引き換えに提供される。そのリソース又は報酬は、ある公開鍵によって保護され、その公開鍵は、対応する秘密鍵を使用することによってロック解除可能となるか又は解放可能となる。本発明は、複数の参加者を有するプールされているリソース又はグループによってタスクを処理し又は解決することを可能とし、そのプールされたリソース又はグループは、ディーラーフリーのしきい値署名グループであってもよい。
【００１０】
その方法は、当該グループに属する個人が、トラストレス(管理者による承認を必要としない)(trust-less)方式又はディーラーフリー(dealer-free)方式によって、ともに作業することを可能とする。このことを達成するために、個人は、自身の鍵の対を生成し、そして、その個人の公開鍵を使用して、初期の共有されている公開鍵をグループで確立し、その初期の共有されている公開鍵をすべての個人が並列的に使用して、そのタスクに対する解法を発見することが可能である。検証されるとともに共有される公開鍵は、解法が発見され且つ検証されているときに使用された初期の共有されている公開鍵を使用して作成されるため、自身の秘密鍵は秘密のままであり、したがって、その協調は、トラストレスであり、効率的に動作する。その検証されるとともに共有される公開鍵によってリソース又は報酬を保護することが可能である。各々の参加者の秘密鍵は、その解法につながる初期の共有されている公開鍵の決定の際に使用されており、したがって、すべての参加者又は参加者のあらかじめ合意されているしきい値によってのみ、対応する共有されている秘密鍵(又は、対応する署名)を生成することが可能であるため、参加者は、その後、共同でリソース又は報酬のロックを解除する必要がある。効率は、初期の共有されている公開鍵を使用し、そして、その解法が発見された後に、検証されるとともに共有される公開鍵である異なる共有されている公開鍵をグループで計算することによって、達成可能である。
【００１１】
本発明は、シャミアの秘密共有方式を適用する際に楕円曲線の準同形(homomorphic)特性を使用することによって、そのタスクがトラストレスとなることを可能とする。
【００１２】
本発明の概念は、グループが協調することが可能である安全な且つトラストレスである効率的な方法に属する。本発明は、タスクに対して不可知的であってもよい。
【００１３】
このようにして、本発明にしたがって、添付の特許請求の範囲によって定義される方法及びシステムが提供される。
【００１４】
このようにして、複数の参加者を有するプールされているリソース又はグループによる計算タスクに対する解法の安全な決定のためのコンピュータ実装方法を提供することが望ましく、そのグループは、トラストレスの又はディーラーフリーのシステム又は方式によって動作し、当該方法は、n個の参加者を有するグループを確立するか又は前記グループに参加するステップであって、n≧2である、ステップと、初期の秘密鍵の持ち分及び初期の公開鍵の持ち分を生成し、そして、前記グループとの間で、初期の共有されている公開鍵を確立するステップと、前記タスクを実行し、そして、中間秘密鍵及び前記グループの前記共有されている公開鍵を使用して前記タスクに対する回答を決定する前記解法を探索するステップと、前記解法を発見し、そして、前記グループとの間で前記解法を共有するか、又は、他の参加者から前記解法を受信し、その結果として、前記グループが、前記タスクに対する前記解法を検証することを可能とするステップと、前記解法を提供した前記中間秘密鍵及び前記初期の共有されている公開鍵を使用して、検証されるとともに共有される公開鍵を前記グループで計算するステップと、前記解法を提供した前記中間秘密鍵及び前記初期の秘密鍵の総和をとることによって、検証されている秘密鍵の持ち分を構築するステップと、前記他の参加者のすべて又は参加者のしきい値数と協調して、検証されている秘密鍵の持ち分を使用することによって、前記検証されるとともに共有される公開鍵に対する検証されるとともに共有される秘密鍵を構築するステップと、を含み、前記検証されるとともに共有される秘密鍵は、前記グループが、プロセスのリソース又はステージのロック解除又はアクセスのために集合的に動作することを可能とするコードとして使用される。検証されるとともに共有される公開鍵は、その解法が発見された後に計算されるということに留意すべきである。
【００１５】
当該方法は、クライアント又は参加者から、クライアントの秘密鍵から導き出されるクライアントの公開鍵及び前記タスクを受信するステップをさらに含んでもよく、前記クライアントの公開鍵は、前記タスクに対する前記解法の前記決定の際に使用される。このようにして、クライアント又は参加者のみがその解法を決定することが可能であるように、そのタスクを暗号化することが可能である。
【００１６】
プロセスのステージへのアクセスであってもよく又は金銭的報酬であってもよいリソース又は報酬は、検証されるとともに共有される公開鍵によってロックされるか又は保護され、検証されるとともに共有される秘密鍵は、グループが、プロセスのリソース又はステージに対するロック解除又はアクセスを実行するように集合的に動作することを可能とするコードとして使用されてもよい。集合的に動作するn個の参加者のグループは、そのグループに属する参加者のすべてが協調するか、又は、参加者のあらかじめ合意されているしきい値mが協調することのいずれかを必要とし、m≦nである。
【００１７】
前記タスクを実行し、そして、前記解法を探索するステップは、前記中間秘密鍵を使用して、前記初期の共有されている公開鍵に追加される中間公開鍵を作成し、そして、前記中間秘密鍵が探索された前記回答を決定する解法であるか否かを決定するように処理される一時的な公開鍵を作成するステップと、前記回答が決定されない場合に、前記中間秘密鍵の前記値を増加させ、そして、前記解法が決定され、且つ、前記回答が証明されるまで前記プロセスを繰り返すステップと、を含んでもよい。
【００１８】
中間公開鍵を使用するステップは、解法のみを決定するために、各々のステップにおいて新たな共有されている公開鍵を生成する必要なく、参加者が並列的に作業することを可能とすることが可能である。むしろ、検証されるとともに共有される公開鍵は、その解法がすべての参加者によって知られているとともに検証されているときに作成される。初期の共有されている公開鍵及び検証されるとともに共有される公開鍵は、以前に生成されてもよい。
【００１９】
タスクは、少なくとも1つのグループメンバーが、処理されたときに、ある特定のパターンを有する暗号通貨アドレスを生成する解法を発見することを必要としてもよい。その暗号通貨アドレスは、本明細書における複数の例のように、ビットコインアドレスであってもよい。
【００２０】
タスクは、セットパターン(A)の決定を必要としてもよく、そのセットパターンは、第三者又は他の参加者に由来し、第三者は、第三者秘密鍵(skc)を生成し、そして、グループに、対応する第三者公開鍵を提供し、pkc＝skc×Gであり、Gは、楕円曲線基準点(elliptic  curve  generator)であり、×は、楕円曲線点乗算であり、第三者公開鍵を受信し、セットパターンを決定するときに、pk＝pkc＋i×Gとなるように、増加変数(i)とともに第三者公開鍵を使用してセットパターンを決定し、第三者に、解法の決定を可能とする増加変数(i)を送信し、それによって、第三者は、楕円曲線点乗算の同形特性に起因して、それらのランダムな秘密鍵(skc)を使用して、解法を検証することが可能であり、sk＝skc＋iであり、pk＝sk×Gである。
【００２１】
n個の参加者のグループは、安全な複数当事者の計算(MPC)によって、初期の共有されている公開鍵及び/又は検証されるとともに共有される公開鍵を生成してもよい。初期の共有されている公開鍵は、シャミアの秘密共有スキームを使用してグループの間で確立されてもよい。
【００２２】
初期の及び/又は共有されている秘密鍵は、シャミアの秘密共有スキームを使用してグループの間で確立されてもよく、参加者自身のランダム次数tの多項式fi(x)を生成し、そして、その次に、各々の他の参加者Pjにfi(j)を安全に送信することによって、各々の参加者Piの間で、トラストレスの関係を確立してもよく、各々の参加者は、受信したすべての点の総和f1(i)＋f2(i)＋…＋fn(i)をとって、共有されている多項式f(x)のPi点である参加者の秘密の持ち分si＝f(i)を取得する。
【００２３】
初期の秘密鍵の持ち分の作成に続いて、bisn×Gであるときに、楕円曲線基準点Gを使用して初期の公開鍵の持ち分を計算してもよく、補間係数biは、
【数１】
2021507276.tif 000003
であり、初期の公開鍵の持ち分は、その次に、すべての参加者にブロードキャストされ、初期の共有されている公開鍵は、その次に、
【数２】
2021507276.tif 000004
にしたがって、いずれかのt＋1個の持ち分の総和として計算される。
【００２４】
タスクは、クライアント又は参加者から受信されてもよく、そのタスクは、ある指定されたパターンを有する暗号通貨アドレス又はビットコインアドレスのための秘密鍵を発見することであってもよい。中間秘密鍵は、ランダムに生成されてもよく、中間公開鍵は、シード番号の楕円曲線基準点との倍数であってもよく、一時的な公開鍵は、共有されている公開鍵に加算され、そして、処理されて、ビットコインアドレス等の暗号通貨アドレスを生成する。
【００２５】
その解法を可能にするシード番号を有するすべての参加者に対して、検証されるとともに共有される公開鍵は、
【数３】
2021507276.tif 000005
から計算されてもよい。
【００２６】
各々の参加者は、svn＝sOn＋rv0から計算される各々の参加者の検証されている秘密鍵の持ち分を計算して、参加者のグループが、共有されるとともに検証される秘密鍵を構築するか又は有効なディジタル署名を生成するのを可能とする。
【００２７】
その方法は、グループとの間で、タスクに適用される計算リソースを実証可能である中間結果を周期的に共有するステップをさらに含んでもよい。それらの中間結果は、回答の一部に対応していてもよい。それらの中間結果は、困難さに比例するレベルを有してもよい。1つ又は複数の参加者は、提示される中間結果の頻度及び/又は困難さに基づいて、他の参加者が適用する計算リソースを評価してもよい。
【００２８】
他の態様において、本発明は、コンピュータ実行可能な命令を含むコンピュータ読み取り可能な記憶媒体に属し、そのコンピュータ実行可能な命令は、実行されるときに、本明細書において請求されている複数の方法のうちのいずれかを実行するようにプロセッサを構成する。
【００２９】
他の態様において、本発明は、電子デバイスに属し、その電子デバイスは、インターフェイスデバイス、そのインターフェイスデバイスに接続される1つ又は複数のプロセッサ、及びそれらの1つ又は複数のプロセッサに接続されるメモリを含み、そのメモリは、コンピュータ実行可能な命令を格納し、それらのコンピュータ実行可能な命令は、実行されるときに、請求項の方法を実行するようにそれらの1つ又は複数のプロセッサを構成する。
【００３０】
他の態様において、本発明は、ブロックチェーンネットワークのノードに属し、そのノードは、本明細書において請求されている複数の方法のうちのいずれかを実行するように構成される。
【００３１】
他の態様において、本発明は、ブロックチェーンネットワークに属し、そのブロックチェーンネットワークは、本明細書において請求されているノードを有する。
【００３２】
この明細書は、乱数の使用に言及しているということに留意すべきである。本発明は、追加的に又は代替的に擬似乱数を使用してもよい。
【００３３】
現時点で、そのような改善された解法が考案されている。
【図面の簡単な説明】
【００３４】
本発明のこれらの態様及び他の態様は、本明細書に記載されている実施形態から明らかであり、その実施形態を参照して説明されるであろう。本発明のある1つの実施形態は、以下で、単なる例として、添付の図面を参照して説明されるであろう。
【００３５】
【図１】本発明のシステム又は方法を使用してタスクを取り扱うプロセスの要素である。
【図２】その中に設定されている人間により読み取り可能であるパターン"nChain"を有するとともに、ブロックチェーンにおいて使用するためのアドレスである。
【図３】毎秒につき100万個の鍵という予想される速度を使用する標準的なコンピュータ処理ユニット(CPU)を使用して、さまざまなセットパターンを有するアドレスを決定するのに要すると予想される平均時間及び困難さのレベルをまとめた表である。
【図４】ある特定の秘密鍵の例から、ブロックチェーンにおいて使用するためのアドレスを決定するのに要するステップを示すフローチャートである。
【図５】バニティーアドレスを導き出すための計算を示すフローチャートであり、図4で実行されるステップを包含する。
【図６ａ】参加者が、どのようにして、最初に協調して、共有されている公開鍵を確立するかを示すフローチャートである。
【図６ｂ】参加者が、どのようにして、図5に示されている計算を使用してアドレスを決定するかを示すフローチャートである。
【図７】秘密共有多項式における鍵共有の更新のロジックを図示している。
【図８】さまざまな実施形態を実装することが可能である計算環境を図示している概略的な図である。
【発明を実施するための形態】
【００３６】
［概要］
本明細書において、安全であり、効率的であり、そしてディーラーフリーの又はトラストレスのシステムにおける計算タスクを共有する問題に対する解法を説明する。その方法及びその方法を実装するためのシステムは、入力を受け取り、そして、出力を決定する。
【００３７】
［計算タスクの概要］
図1は、本発明にしたがったシステムの最も簡単な説明図であり、入力又は要求が設定され、タスクを実行して、出力を提供する必要がある。
【００３８】
入力は、前のタスクからの出力であってもよく、又は、タスクを外部委託している第三者によって設定されてもよい。そのタスクは、理論的に、1つの個人又は1つのエンティティによって実行されてもよい。一方で、本発明は、タスクを共同で行って、出力を生成する複数の個人又は複数のエンティティ等の複数の当事者に関する。出力は、後に続くタスクへの入力として使用されてもよく、したがって、コード又はデータのセットとして具体化されてもよい。
【００３９】
タスクへの入力を設定し、そして、出力を受信する第三者は、公開的にそのことを行うことが可能であり、それによって、解法及び回答は、その出力又は解法を共同して決定するグループのうちの少なくとも1つ及びその第三者に知られる。
【００４０】
代替的に、第三者のクライアントがタスクを安全に割り当てることを望む場合には、それらの第三者のクライアントは、秘密鍵(skc)及び対応する公開鍵(pkc)を生成してもよい。タスクセットに対する解法及び解答を決定する際に使用するために、参加者(P)のグループ(G)にそのクライアントの公開鍵を提供してもよい。それらの参加者は、その解法の決定の際に、(秘密鍵skGから決定される)新たな公開鍵を使用し、その解法は、クライアント公開鍵(pkc)にグループ公開鍵(pkG)を追加することによって達成される。明確にするために、その解法は、グループが生成する共有されている公開鍵に追加されるクライアントの公開鍵、すなわち、pkc＋pkGを使用して決定されてもよい。
【００４１】
グループが解法及び回答を決定するときに、それらの第三者のクライアントは、協調して、コードを生成し、そのコードは、グループが、例えば、解法の決定につながるグループ公開鍵(pkG)に対応する秘密鍵(skG)をクライアントとの間で共有することを可能とする。
【００４２】
クライアントは、その次に、自身の秘密鍵(skc)にそのグループ秘密鍵(skG)を追加して、解法を決定してもよい。このようにして、クライアントのみが、そのタスクに対する解法を可能にする秘密鍵を知っている[8]。
【００４３】
簡単にするために、以下の複数の例は、(共同して解決するためのタスクを提供する)第三者のクライアントが、その共同作業を信頼し、その解法の暗号化のために、グループに"クライアント"公開鍵(pkc)を提供しないということを仮定する。
【００４４】
［計算タスクの例］
例として、ディーラーフリーのしきい値署名グループによるバニティーアドレスの決定を使用して、その方法及びその方法を実装するためのシステムを説明する。このタスクは、図1に示され、そのタスクの安全な割り当て及び第三者(又は、いずれかの他のプロセス)からの結果の配信から独立して説明される。
【００４５】
その方法は、信頼されている第三者のディーラーを使用することなく、秘密共有スキームによって、共有されている公開鍵を生成する参加者のグループと関係する。その方法は、秘密共有多項式の算術的な特性及び楕円曲線乗算の同形特性を利用して、バニティーアドレスストリングの並列的な決定を可能にする。
【００４６】
その方法は、セキュリティのいかなる損失も伴わずに、バニティーアドレスの決定等の計算タスクの分散を可能とする。ディーラー又は同様の信頼されている当事者は、必要とはされない。その方法は、追加的に、グループタスクにおいて各々の参加者が利用する計算リソースの評価又は測定を可能とすることができる。
【００４７】
図2は、ビットコイン等の暗号通貨システムにおいて使用するアドレスを示している。そのアドレスは、暗号通貨トークンの決済のための宛先を定義する識別子となっている。ビットコインプロトコルにおいて、アドレスは、決済を受信する当事者が生成する秘密鍵に対応する楕円曲線公開鍵の160ビットのハッシュとなっている。完全な公開鍵ではなくアドレスへの暗号通貨の決済の送信は、出力(未使用トランザクション  -UTXO)が(P2PKHの中のscriptSigの一部として)費やされるまで、対応する完全な公開鍵が、ブロックチェーンにおいて明らかにされないということを意味する。このことは、量子コンピューティングの急速な進歩によって生じる場合がある楕円曲線暗号化の潜在的且つ将来的な弱点に対する保護を提供する。
【００４８】
ビットコインアドレスは、通常、カスタムBase58Check符号化スキームを使用して英数字フォーマットに変換され、ビットコインアドレスのその変換は、長さが25乃至34文字のテキストストリングを生じる。Base58符号化スキームは、アドレスをコンパクト且つ人間により読み取り可能であるようにするために採用され、このフォーマットにおいては、決済アドレスは、コピー又は書き換えのために、(例えば、ウェブサイトにおいて)容易に利用可能とすることが可能である。
【００４９】
図2の人間により読み取り可能なテキストストリングは、決定論的な方法で、ランダムな秘密鍵から導き出される。したがって、繰り返し計算を実行して、Base58符号化アドレスの中で特定のあらかじめ決定されている部分ストリングを生じる秘密鍵を発見することが可能である。この種の集約的な探索は、"総当たりの(brute-force)"探索と称されることがよくある。
【００５０】
図2のアドレスは、"バニティーアドレス(vanity  address)"として知られており、アドレスをより識別可能にするとともに、不正な行為の影響を受けにくくするのに使用されてもよい。例えば、1David等の会社名又は個人名、或いは、他のあらかじめ決定されているストリングで開始するアドレスを決定してもよい。この場合には、"nChain"という語を有するアドレスは、秘密鍵から決定されている。
【００５１】
バニティーアドレスの決定は、秘密鍵空間の確率論的な探索を必要とし、したがって、必要とされる部分ストリングパターンに依存する有意な計算コストを必要とする。必要とされる部分ストリングの発見の計算コストは、困難さ(D)として定量化され、その困難さ(D)は、試行される必要がある(すなわち、アドレスに変換される必要がある)ランダムな秘密鍵の期待値(平均値)数として定義される。
【００５２】
図3は、複数の異なる長さのある特定の大文字と小文字を区別する部分ストリングで開始するアドレスの発見の困難さ及び毎秒ごとに100万個の鍵の探索速度に基づく対応する平均探索時間を列記している表を示している。グラフィック処理ユニット(GPUs)又は特定用途向け集積回路(ASICs)等の特殊なハードウェアであっても、探索は、長いストリングについては計算コストが高いままであり、並列的な探索は、より高速である。
【００５３】
図4は、個人用の鍵又は秘密鍵からアドレスを確立するのに要するステップを図示しており、その秘密鍵は、(秘密に保たれる必要があるとともに)個人用の鍵である256ビットの安全な乱数である[2]。対応する完全な公開鍵は、その次に、Secp256k1楕円曲線(×G)における点乗算によって生成され、その点乗算は、(楕円曲線点のx座標及びy座標について)2つの256ビットの数字を生じる。これらの座標は、連結され、0x04の接頭語が付けられ、520ビットの数字を生じる。公開鍵は、その次に、SHA-256関数によってハッシュされて、256ビットの数字となり、その256ビットの数字は、その次に、RIPEMD-160関数によってハッシュされて、160ビットのアドレスとなり、(メインビットコインネットワークの場合には0x00である)バージョンバイトの接頭語が付けられる。そのアドレスは、その次に、Base58check符号化を使用して、人間により読み取り可能である表現に変換されてもよい。この符号化は、数字、大文字、及び小文字(ただし、0、O、I(Iの大文字)、及びl(Lの小文字)の符号は、いくつかのフォントでは区別が困難な場合があるため、これらは、使用されない)の58個の英数字記号のセットを特徴とする。加えて、そのアドレスの終端に4バイトの誤り検査コードを追加して、誤字を自動的に検出する(そして、資金が使うことができないアドレスに送られるのを防止する)[3]。
【００５４】
図5は、特定の部分ストリング(又はパターン)を含むBase58符号化されたアドレスを決定するのに要する動作を示し、それらのBase58符号化されたアドレスは、秘密鍵空間の総当たりの探索(brute-force  search)によって決定されてもよい[1]。考慮されるパターン(Str)は、探索されているクライアントの回答(Ac)の一部である。その回答を決定するのに使用される計算において使用する値は、その回答の決定を可能とする値を含み、解法(S)の構成要素と考えられる。その解法は、図4において開示されているステップを使用して処理されるときに、望ましいストリングを有するアドレス(Ac)をもたらす秘密鍵である。
【００５５】
図5において、アドレスの最初の4つの文字が"コイン"となるように構成されるパターンを有するブロックチェーンアドレスの形態の回答(Ac)を設定する。"コイン"の語は、探索される文字のストリング(str)である。図4のステップにしたがって、秘密鍵又は個人用の鍵(sk0)を表す乱数を生成する。公開鍵(pk0)は、その秘密鍵に楕円曲線基準点(G)を乗算することによって計算される。Base58checkの中の符号化されたアドレスは、公開鍵から決定され、アドレスのパターン(str)が最初の4つの文字の中に"Coin"を有する場合には、秘密鍵(sk0)は、解法である。アドレスのパターン(str)が最初の4つの文字の中に"Coin"を有していない場合には、秘密鍵(sk0)は、1だけ、すなわち、＋1ビットだけ増加させられ、他の公開鍵の計算は確立され、プロセスは繰り返される。
【００５６】
図3において示唆されているように、探索されるパターンの長さが増加するのに伴って、解答(Ac)のこの確率論的な生成は、そのプロセスの何百万回ものサイクルを必要とすることがよくあり、困難さは増加する。ハッシュ関数の出力は、ランダムであると考えられてもよいので、ランダムなオラクルモデルを仮定すると、その探索は、確率論的となる。必要とされる試行又はサイクルの予想される数は、そのパターンの複雑さによって決まるであろう。バニティーアドレスは、検索の複雑さにかかわらず、いずれかの他のランダムな鍵から作成されるアドレスと同じ程度に安全である(破壊可能ではない)。
【００５７】
本発明は、解法(S)を決定するための計算タスクを使用して本明細書において説明され、その計算タスクは、回答(Ac)、この場合には、バニティーアドレスの決定であるが、タスク等を実行する安全且つ効率的な並列化は、ビットコインを使用するためのバニティーアドレスの決定には限定されない。その解法は、資産又はリソースへのアクセスに使用されてもよい。
【００５８】
［既知の並列探索］
グループの中の複数の参加者(P)のプールされているリソースを使用して、共同してタスクを実行することは、ブロックチェーンマイニングから知られている。マイニングプールの場合に、ディーラーは、それらの複数の参加者を調整し、秘密鍵及び公開鍵の対を確立する。秘密鍵の持ち分は、その後、ディーラーがそれらの複数の参加者に分配する。さらに、コングレス(congress)又は参加者グループは、単一の公開鍵又はアドレスによって参加者の資金が集合的に保護されるようにすることが可能である。マイニングプール及びコングレスシナリオにおいては、しきい値署名スキームによって、その共有されている公開鍵に対応する署名を生成してもよく、したがって、グループ及びそのグループの一部が、資金又は報酬に集合的にアクセスすることを可能とする。
【００５９】
一方で、コングレスが完全にトラストレスの且つ安全であるためには、信頼されている第三者("ディーラー")を使用せずに、共有されている公開鍵(及び対応するアドレス)を生成する必要がある。
【００６０】
ディーラーフリーの秘密共有プロトコルは、複数回のラウンドにおいて、複数の参加者の間の有意の通信を必要とする。このことは、ネットワークの待ち時間に依存して、通常は、秒から分といったように、完了するのに有意な長さの時間を要する。さらに、ディーラーフリーの秘密共有プロトコルの場合には、ある参加者が、共有されている公開鍵のその参加者の持ち分を使用して、あるタスクに対する解法を決定しようと試みるたびごとに、新たな共有されている公開鍵が要求されるであろう。バニティーアドレスパターンの決定の際の各々の試行に対して、新たな共有されている公開鍵が要求される。
【００６１】
ある参加者が、バニティーアドレス探索等の計算タスクにおける共同探索の間に、進行状況を検証するか、或いは、グループとの間で状態の更新又は潜在的な解法を共有することを望むたびごとに、各々のステップにおいて新たなディーラーフリーの共有されている公開鍵を必要とし、このことは、タスクを完全に実行不可能とする。言い換えると、探索等のタスクは、複数のステップを有し、そのタスクにおいて協調するグループは、各々のステップを並列的に実行する。安全であるがトラストレスの関係を維持するために、そのグループは、そのタスクの各々のステップにおいて、新たな公開鍵を集合的に生成することを要求される。例えば、共有されている公開鍵の生成時間を10秒と仮定すると、ちょうど4つの文字("1CoinXXX…")のパターンで開始するアドレスを発見するために、(個々の秘密鍵を有する単一の当事者のための数秒と比較して)1年の時間を占有するであろう。この理由により、本発明は、元の公開鍵及び解法に基づいている第2の共有されている公開鍵を確立する。
【００６２】
［改善された並列的な探索−共有されている公開鍵の生成］
本発明は、トラストレスのシステムにおける共同的な作業に関する。ディーラーを使用しない場合に、そのグループは、設定されたタスクに対する解法及び/又は回答を安全に共有するためのメカニズムを確立する必要がある。このことを達成するために、ディーラーフリーのしきい値グループを確立する。
【００６３】
グループは、数(n)の参加者(P)を有する。各々の参加者は、共有されている秘密鍵又は個人用の鍵の秘密の持ち分(son)を確立する。共有されている秘密鍵は、秘密の持ち分のしきい値(m)数から決定されてもよい(m≦n)。持ち分のしきい値から構築されるときに、共有される秘密を確立してもよいが、そのようにする必要はない。
【００６４】
共有されている秘密鍵の秘密の持ち分(son)を確立する前に、そのグループは、楕円曲線基準(G)を定義する他のパラメータ及び生成器について合意する。楕円曲線点乗算の一部としてその生成器又は点を使用して、秘密鍵を公開鍵に変換する。グループの複数当事者の計算(MPC)の場合には、楕円曲線点乗算は、個々の秘密鍵の持ち分から、その共有されている公開鍵を導き出すプロセスの一部として使用される。その生成器は、その次に、各々の参加者によって使用されて、共有されている公開鍵(pkO)を生成するのに使用される公開鍵の対応する持ち分及び秘密鍵の秘密の持ち分(pk1)を確立してもよい。そのグループは、それらの秘密の持ち分を使用して初期の共有されている公開鍵(pkO)を計算する。そのグループは、安全な複数当事者の計算(MPC)を使用して、このことを達成してもよい。
【００６５】
共有されている秘密鍵は、グループによっては使用されないため、その共有されている秘密鍵を計算する必要はないということに留意すべきである。そのプロセスの後において、共有されている秘密鍵の各々の参加者の持ち分は、資産のロックを解除するのに使用される。
【００６６】
共有されている公開鍵(pkO)は、グループが探索する解法/解答及び出力を決定するのに使用されてもよく、その出力は、アクセスされる資産であり、共有されているグループ鍵及び対応するアドレスの制御下に置かれる。参加者のしきい値が協調しているときに、その資産にアクセスするのに必要となる秘密鍵又は個人用の鍵を決定することが可能である(又は署名を生成する)にすぎないため、共有されている公開鍵(pkO)は、そのグループが完全にトラストレスの方法で協調することを可能とする。
【００６７】
共有されている秘密鍵の各々の参加者の持ち分及び共有されている公開鍵の確立は、シャミアの秘密共有スキーム(SSSS)[4]を使用し、そのシャミアの秘密共有スキーム(SSSS)は、次数tの多項式がt＋1個の点のいずれかのセットに適合することが可能であるか又は整合することが可能であるという事実を使用する。共有されている秘密鍵が定数項(a0＝f(0))として定義され、且つ、残りの係数が乱数として安全に生成される場合に、次数tの多項式f(x)は生成される。その多項式における数nの複数の異なる任意の点は、各々の参加者の秘密の持ち分である。m＝t＋1又はそれ以上の参加者が、その次に、それらの点を組み合わせる場合に、(ラグランジュ(Lagrange)の補間によって)これらの点に次数tの多項式を適合させるのに十分な情報が存在し、a0＝f(0)は、共有されている秘密として現れる。このスキームは、いずれかのしきい値を有する任意の数の当事者の間で単一の秘密鍵の共有を可能とする。
【００６８】
ディーラーを取り除くとともに、システムをトラストレスにすることが可能である[5]。ディーラーが、初期の多項式を作成し、秘密の持ち分を分配するのではなく、各々の参加者Piは、自身のランダムな次数tの多項式fi(x)を生成し、そして、その次に、他の参加者Pjの各々にfi(j)を安全に送信する。各々の参加者Piは、その次に、受信した点のすべての総和をとる、すなわち、f1(i)＋f2(i)＋…＋fn(i)を求めて、自身の秘密の持ち分si＝f(i)を取得し、その自身の秘密の持ち分si＝f(i)は、共有されている多項式f(x)におけるPiの点である。
【００６９】
秘密の持ち分を作成した後に、楕円曲線基準点(G)を使用して、共有されている秘密鍵に対応する共有されている公開鍵(pkO)を計算する。一方で、以下で明らかになるように、共有されている秘密鍵は、知られておらず、計算する必要はない。
【００７０】
参加者Piは、その次に、bisi×Gとして、自身の公開鍵の持ち分を計算し、補間係数は、
【数４】
2021507276.tif 000006
である。
【００７１】
これらの公開鍵の持ち分は、その次に、すべての参加者にブロードキャストされ、共有されている公開鍵(pkO)は、その次に、単に、いずれかのt＋1個の持ち分の総和として計算され、
【数５】
2021507276.tif 000007
である。
【００７２】
各々の参加者は、受信した公開鍵の持ち分のすべてが一致しているということを検証してもよい。
【００７３】
グループが協調するか又はそのグループの参加者のしきい値数が協調するときに、コードを生成することが可能であり、そのコードは、これらの例において秘密鍵である解法となる。そのコードの協調的な生成は、そのグループが、資産にアクセスし又は資産をロック解除することを可能とし、或いは、図1に示されているタスクの完了等のプロセスにおけるステージを終了させる機能を可能とする。その完了したタスクは、暗号化のプロセス等のあるプロセスにおける複数のタスクのうちの1つであってもよい。
【００７４】
例として、アドレスに対応する署名を使用して、資金をロック解除することが可能であり、そのグループのm個の参加者のしきい値が協調して、共有されている秘密鍵を再び作成するか、又は、より安全に、しきい値署名スキームを使用して、支出トランザクションに集合的に署名するか、のいずれかのときにのみ、それらの資金をロック解除することが可能である[6]。
【００７５】
［改善された並列的な探索−協調的な計算］
例として、処理されたときにビットコインアドレスを生成する秘密鍵の発見に関連して、トラストレスの方式で参加者のグループによる解法の決定を説明する。英数字アドレスフォーマット及び指数関数ベースの公開鍵署名によるいずれかの暗号通貨に、或いは、いずれかの計算プロセス又はタスクに、トラストレスの方式で安全な且つ効率的な協調を維持するのに要するステップを適用することが可能である。
【００７６】
例示的な計算タスクにしたがって、本発明は、バニティーアドレスの決定によって解説される。楕円曲線(EC)演算は、ビットコインにおいて使用されているSecp256k1曲線が定義するパラメータを使用して実行される[7]。この規格は、(曲線パラメータのほかに)生成点G及び次数pを指定する。他に指定されない場合には、(多項式を含む)すべての演算は、モジュロpにおいて実行され、すべての秘密鍵は、256ビットの数である。すべての公開鍵は、ECの座標である。
【００７７】
プロトコルは、参加者のグループ("しきい値グループ")の間で動作し、そして、すべての参加者が互いに認証し、安全なチャネルを介して通信することが可能であるということを仮定する。このことは、公開鍵暗号システム又はディッフィーヘルマン(Diffie-Hellman)鍵交換プロトコルを使用して達成されてもよい。そのグループの目的は、特定の用途に依存し、それらのうちの1つは、コングレスの形態となっていてもよい。
【００７８】
この方式の各々の参加者は、複数の秘密鍵を生成することを要求され、それらの複数の秘密鍵は、エントロピーの適切なソースを有する暗号的に安全な疑似乱数発生器(CSPRNG)から導き出される。
【００７９】
［グループの確立］
図6(a)は、上記のように、共有されている多項式及び関連する共有されている公開鍵を最初に生成するグループを表している。選択的な追加の検証ステップを実行して、個々の持ち分の有効性を保証してもよい。
【００８０】
そのグループは、数(n)の参加者(Pi:P1,P2,P3,…,Pn)を有し、それらの参加者(Pi:P1,P2,P3,…,Pn)は、安全な通信チャネルを確立し、それらの参加者のすべては、しきい値(m)及びアドレスパターンStr(Base58ストリング)について合意する。そのアドレスパターンは、探索される解答(Ac)である。
【００８１】
各々の参加者(Pi)は、ランダムな係数fi(x)を有する次数m−1の多項式を生成する。各々の参加者Piは、各々の他の参加者(j＝1,…,n)にfi(j)の値を送信する。各々の参加者は、その次に、自身のfi(i)の値とともに、受信した値のすべての総和を取り、自身の秘密の持ち分
【数６】
2021507276.tif 000008
を取得し、
【数７】
2021507276.tif 000009
である。
【００８２】
対応する共有されている公開鍵(pkO)は、その次に、上記のように、ラグランジュ補間を使用して、すべての参加者によって計算されそして検証される。
【００８３】
この点において、各々の参加者は、現在、自身の初期の秘密の持ち分(s0i)及び初期の共有されている公開鍵(pkO)を有する。グループが確立するその共有されている公開鍵(pkO)は、そのタスクの際に各々の参加者によって使用される。共有されている鍵(skO)は、計算されることはなく、また、使用されない。一方で、共有されている鍵(skO)は計算されないが、共有されている秘密の各々の参加者の持ち分(s0i)及び共有されている公開鍵は、解法(S)を決定するのに使用されるということに留意することは重要である。以下で、そのプロセスを説明する。
【００８４】
［並列的な探索］
実行されるタスクは、図5に示されており、上記で説明されている。グループは、その次に、図6(b)に示されている順序で、指定されたパターンの探索を並列的に実行する。
【００８５】
各々の参加者Pnは、(複数の参加者の間の探索スペースの重複を防止するための)探索シードである乱数ri0を生成する。その乱数ri0は、この例においては、秘密鍵であり、アドレスは、その秘密鍵から導き出される。
【００８６】
その次に、各々の参加者Piは、
【数８】
2021507276.tif 000010
にしたがって、探索シードから楕円曲線点番号Ri0を計算し、Gは、楕円曲線基準点(elliptic  curve  generator)であり、秘密鍵rn0によって乗算されると、一時的な公開鍵Ri0を確立する。
【００８７】
共有されている公開鍵pkOは、
【数９】
2021507276.tif 000011
にしたがって、新たな公開鍵の持ち分pkiRを決定するのに使用される。
【００８８】
新たな公開鍵の持ち分pkiRは、AiR＝Ad(pkiR)にしたがって、Base58アドレスAiRに変換される。
【００８９】
参加者は、その次に、Base58アドレスAiRが回答(Ac)と一致するか否か、すなわち、そのBase58アドレスAiRが、指定されたパターンStrを含むか否か又は指定されたパターンStrによって開始するということを検査する。言い換えると、探索されるパターンによって開始するアドレスにつながる乱数ri0を有する。
【００９０】
一致しない場合には、シード番号である乱数ri0(秘密鍵)は、例えば、1ビットだけri0を増加させるといったように、増加させられ、探索シードから(一時的な公開鍵である)他の二次的な乱数Ri0を計算し、元の公開鍵及びその一時的な公開鍵を加算することによって他の新たな公開鍵を決定し、他の新たな公開鍵をBase58アドレスに変換し、そして、そのBase58アドレスが、指定されたパターンStrと一致するか否かを検査することによって、そのプロセスを繰り返す。
【００９１】
Base58アドレスAiRが、指定されたパターンStrを含んでいるか又はその指定されたパターンStrと一致する場合に、参加者は、その解法をブロードキャストし、その解法は、回答を決定することを可能とするシード番号ri0であり、そのシード番号又は秘密鍵は、以降では、バニティーシード番号rv0と称される。
【００９２】
他の参加者が、他のグループのメンバーからブロードキャストrv0＝ri0を受信すると、それらの他の参加者は、楕円曲線基準点(×G)で秘密鍵を乗算し、そして、元の共有されている公開鍵(pkO)を加算することによって、その秘密鍵が、ターゲットテキストストリング(Str)を有するアドレスに対応するということを検証してもよい。
【００９３】
元の共有されている公開鍵を使用して、グループは、新たな共有されている公開鍵pkvを計算し、その新たな共有されている公開鍵pkvは、
【数１０】
2021507276.tif 000012
にしたがって探索されるバニティーアドレスに対応する。
【００９４】
シード番号(秘密鍵)を使用する一時的な公開鍵の持ち分の作成は、参加者が行う各々のステップにおいて新たな共有されている公開鍵を生成する必要なく、そのグループが、迅速且つ効率的に並列的に作業することを可能とし、その一時的な公開鍵は、(解答を決定することが可能である秘密鍵である)解法を発見するときに新たな公開鍵の作成につながる。各々の参加者は、制限なく自身の進行状況を他の参加者との間で共有することが可能であり、その解法を発見したときにのみ、新たな共有されている公開鍵を確立する。
【００９５】
［秘密の持ち分の更新］
各々の参加者Piは、現在、自身の初期の秘密の持ち分s0i、共有されている公開鍵pkO、及びri0を有し、ri0は、望ましいテキストストリングを含むアドレスにつながる。自身の秘密の持ち分を更新するために、各々の参加者は、
【数１１】
2021507276.tif 000013
の値にrv0を単に加算し、rv0は、回答につながる秘密鍵である。
【００９６】
更新された持ち分sviのしきい値(m)は、その次に、シャミアのスキームを使用することによって、且つ、
【数１２】
2021507276.tif 000014
にしたがって、探索されているバニティーアドレスに対応する新たな共有されている公開鍵に対応する完全な秘密鍵skvを再構築することを可能とするであろう。このことは、多項式演算から生じ、その多項式演算においては、図7に図示されているように、すべての秘密の(非ゼロx)点へのある定数の加算は、その同じ定数だけ、補間されたゼロ点(秘密)を増加させるであろう。
【００９７】
参加者のすべては、新たな共有されている公開鍵を独立して確立することが可能であるが、それらの参加者は、対応する秘密鍵を作成するか又は有効なディジタル署名を生成するのに協調する必要があり、その有効なディジタル署名は、以前の共有されている公開鍵又は新たな共有されている公開鍵が保護しているいずれかのリソースへのアクセス又はロック解除の際に必要とされる。
【００９８】
［検証］
新たな秘密鍵を確認し及び検証するために、グループは、対応する共有されている公開鍵(pkO)に関連して、上記で説明されているように、自身の新たな秘密の持ち分(svi)を使用して新たな共有されている公開鍵pkvを生成する手順を実行し、その対応する共有されている公開鍵(pkO)は、ラグランジュ補間を使用してすべての参加者によって計算され及び検証され、その公開鍵の持ち分は、すべての参加者にブロードキャストされており、その共有されている公開鍵(pkv)は、その次に、
【数１３】
2021507276.tif 000015
にしたがって、単に、いずれかのt＋1個の持ち分の総和として計算される。
【００９９】
各々の参加者は、受信した公開鍵の持ち分のすべてが一致しているということを検証してもよい。
【０１００】
［プロセスの概要］
複数の参加者は、グループ及び共有されている公開鍵(pkO)を形成し、その共有されている公開鍵(pkO)は、"元の"共有されている公開鍵である。その元の共有されている公開鍵は、対応する共有されている秘密鍵の各々の参加者の持ち分及び元の共有されている公開鍵の各々の参加者の持ち分から確立される。共有されている秘密鍵は、確立されておらず、また、確立する必要はないということに留意すべきである。
【０１０１】
グループには、タスクが設定され、そのタスクは、第三者によって設定されてもよい。そのタスクに対する解法と引き換えに、リソース又は報酬が、提供され又は利用可能になる。その解法を発見するときに、そのリソース又は報酬は、新たな共有されている公開鍵によって保護されてもよく、その鍵は、その解法を使用して確立される。リソース又は報酬へのアクセス或いはリソース又は報酬のロック解除は、グループが、対応する新たな共有されている秘密鍵を協調して生成することを必要とする。
【０１０２】
例として、そのタスクは、金銭的報酬と引き換えにするバニティーアドレスの決定である。探索されるアドレスは、あるタスクに対する回答と考えられてもよく、(クライアントによって)あらかじめ決定されているパターン又はテキストストリングである。その解法は、そのタスクの証明である。
【０１０３】
個々にそして並列的に、各々の参加者は、シードとして機能する一時的な秘密鍵を生成し、そのシードが探索されているアドレスにつながるか否かを決定する。そのシードが探索されているアドレスにつながらない場合には、そのシードは増加させられ、それらの複数の参加者のうちの1つが、望ましいテキストストリングを有するアドレスに対する一時的な秘密鍵を識別するまで、決定が繰り返される。
【０１０４】
決定の際に、一時的な秘密鍵は、各々の参加者によって、その決定のために自身で使用するために、(一時的な)公開鍵に変換され、その公開鍵は、その次に、元の共有されている公開鍵に加算され、総和をとられた公開鍵は、加算されて、結合された公開鍵を作成し、その結合された公開鍵のハッシュを求めて、生成されたアドレスが、探索されているテキストストリングを含むか否かを決定する。
【０１０５】
さらなる公開鍵の使用は、一時的に及び参加者自身の使用のために、参加者が、元の共有されている公開鍵とは独立に演算することを可能とし、したがって、各々のステップにおいて新たな共有されている公開鍵を作成する必要があることによる負担を軽減する。
【０１０６】
それらの複数の参加者のうちの1つが、望ましいテキストストリングを有するアドレスに対する一時的な秘密鍵を識別するときに、それらの複数の参加者は、他の参加者との間でその一時的な秘密鍵を共有し、それらの他の参加者は、その次に、さらなる公開鍵から導き出される秘密鍵が、探索されているアドレスにつながる解法であるということを検査する。
【０１０７】
さらなる公開鍵から導き出される秘密鍵がその解法である場合に、(検証されている鍵又は"バニティー"鍵である)新たな共有されている公開鍵は、参加者が元の共有されている公開鍵を確立したのと同じ方式で、それらの複数の参加者によって作成される。
【０１０８】
資産又は報酬は、新たな共有されている公開鍵によって保護されてもよく、解法によってロックを解除されてもよい。資産は、例えば、図1に示されているタスクの完了等のプロセスにおけるステージを終了させるための手続き的なステップ及び機能であってもよい。このようにして、グループは、協調して、資産にアクセスし又は資産をロックを解除し、或いは、報酬を取得し、参加者は、その解法を使用して、そのことを行う。
【０１０９】
この例では、資産のロック解除の説明のために、新たな共有されている公開鍵は、ビットコイン又は他の暗号通貨の支払いを受け取るための新たな共有されている公開アドレスを決定するのに使用される。
【０１１０】
対応する共有されている秘密鍵又は個人用の鍵のみを使用して、この決済にアクセスすることが可能である。参加者のすべて又は参加者のしきい値数が、共有されている秘密鍵を作成するまで、未使用トランザクション(unspent  transaction  (UTXO))のロック解除に必要とされる共有されている秘密鍵は、存在しない。
【０１１１】
新たな共有されている秘密鍵は、各々の参加者の秘密鍵の持ち分から作成され、各々の参加者の秘密鍵の持ち分は、(元の共有されている公開鍵を作成するのに使用される)参加者の元の共有されている秘密鍵及びその秘密鍵(解法)の総和であり、(新たな共有されている公開鍵を作成するのに使用される)その秘密鍵(解法)は、望ましいテキストストリングを有するアドレスを決定する。
【０１１２】
元の共有されている公開鍵の根拠となる秘密の持ち分は、解法(秘密鍵)を確立するのに使用されるのみならず、他の参加者には知られていないため、そのプロセスは、トラストレスとなる。明確にするために、いずれの時点においても、少なくとも、持ち分のしきい値、すなわち、m個の参加者の秘密の持ち分を使用することなく、共有されている秘密鍵を確立することはできない。このことは、(このプロセスにおいては決定されない)元の共有されている秘密鍵及び解法に基づいている新たな共有されている秘密鍵にも当てはまる。
【０１１３】
最初に、共有されている公開鍵は、トラストレスの協調のための基準点を確立し、開始点として、共有されている公開鍵を使用し、そして、解法を使用して新たな共有されている公開鍵を生成することによって、共有されている公開鍵を生成する秘密の持ち分も、新たな共有されている秘密鍵を提供する秘密の持ち分(解法)も、協調なしでは知られることはない。
【０１１４】
［協調の不正な行為の防止］
トラストレスの協調は、フリーライディングの形態の不正な行為の影響を受けやすく、1つ又は複数の参加者は、意図的に、タスクの解法の決定にほとんど寄与しないか又は全く寄与することなく、割り当てられる報酬の均等な配分又は公正な配分を取得することを期待する。その報酬は、金銭的な報酬であってもよく、計算処理リソース又はエネルギー供給等の以降のリソースの割り当てであってもよい。
【０１１５】
匿名の参加者によって形成されているしきい値グループの場合には、それらの参加者は、探索を実行しないように経済的に動機づけられ、タスクに対する解法の決定に積極的に参加しないか又はそのタスクにふさわしい計算のリソースに責任を持つことはない。
【０１１６】
この問題に対処するために、参加者は、報酬の持ち分を割り当てられ、そのような割り当ては、そのタスクに適用される計算リソースに比例するか又は少なくともその計算リソースを表す。それらの参加者が利用するリソースに対して各々の参加者が受け取る割り当ての実際の数又はパーセンテイジは、前もって確立されていてもよい。そのタスクに適用されるリソースを測定するためのメカニズムは、タスクに対する解法を決定しようと試みる際に各々の参加者が行う動作の困難さのレベルを評価することが可能である。適用されるリソースの測定又は指標は、ある特定の参加者がある与えられた比率でそのタスク又は探索を実行したということの証拠を提供することが可能である。困難さのレベルを示すのに、部分測定又は部分指標を使用してもよい。困難さのレベルは、そのタスクの部分的な結果又は部分的な解法から決定されてもよい。
【０１１７】
例として、バニティーアドレスの決定を使用して、参加者のグループは、割り当て又は持ち分のパーセンテイジをどのように決定するべきであるかについて合意してもよい。例えば、探索されている回答がアドレス"1Bitcoin"に対応する秘密鍵である場合には、例えば、"Bitco"等の合意されているパターンの部分ストリングを生成する公開鍵の持ち分の発見は、ある特定のレベルの計算リソースが適用されていることを示すということに合意してもよい。
【０１１８】
並列的な探索の際に、各々の参加者は、"1Bitcoin"によって開始するアドレスの探索を個々に実行し、参加者が、その部分ストリングパターンを有するアドレスに対応する一時的な公開鍵の持ち分を発見するときに、それらの参加者は、そのグループの残りの参加者に、その一時的な公開鍵の持ち分を生成するのに使用される乱数又は使い捨ての乱数(ノンス)(nonce)ri0をブロードキャストする。他の参加者は、各々の受信したノンスri0を検証してもよい、すなわち、
【数１４】
2021507276.tif 000016
から導き出されるアドレスが、その部分ストリングパターンに一致するということを検証してもよく、各々の他の参加者Piから受信した有効なノンスri0の数の記録を維持する。
【０１１９】
各々の参加者Piからの受信した有効なノンスri0の期待される頻度は、それらの参加者の計算(探索)の努力に比例し、部分ストリングパターンの困難さに反比例するであろうということに留意すべきである。例として、標準的なCPUによってアドレスパターン"1Bitcoin"(困難さ8.7×1013)を探索する20個の参加者のしきい値グループは、数時間で、ある解法を発見することが期待されるであろう。一方で、各々の参加者は、約4分毎に部分ストリングアドレスパターン"1Bitco"(困難さ2.6×108)に一致するri0の値を生成し、そして、ブロードキャストすることが期待されるであろう。概ねこの頻度で有効なri0の値を提供しないいずれかの参加者は、例えば、(ディーラーフリーの秘密の共有を再び実行することにより)コングレスの料金を課金するか又はグループからそれらの参加者を締め出すことによって、そのグループの残りの参加者によって罰を与えられもよい。
【０１２０】
［コンピューティング環境］
図8は、さまざまな実施形態を実装することが可能であるコンピューティング環境を図示している概略的な図である。コンピューティングデバイス2600の例示的な且つ簡略化されたブロック図が提供され、そのコンピューティングデバイス2600は、本開示の少なくとも1つの実施形態を実現するのに使用されてもよい。さまざまな実施形態において、コンピューティングデバイス2600は、上記で解説されているシステムのうちのいずれかを実装するのに使用されてもよい。例えば、コンピューティングデバイス2600は、データサーバ、ウェブサーバ、携帯用コンピューティングデバイス、パーソナルコンピュータ、又はいずれかの電子コンピューティングデバイスとして使用するように構成されてもよい。図8に示されているように、コンピューティングデバイス2600は、1つ又は複数のレベルのキャッシュメモリ及びメモリコントローラを有する(集合的に2602の標識を付されている)1つ又は複数のプロセッサを含んでもよく、それらの1つ又は複数のプロセッサは、メインメモリ2608及び永続的な記憶装置2610を含むストレージサブシステム2606と通信するように構成されてもよい。メインメモリ2608は、示されているように、ダイナミックランダムアクセスメモリ(DRAM)2618及び読み取り専用メモリ(ROM)2620を含んでもよい。ストレージサブシステム2606及びキャッシュメモリ2602は、本開示において説明されているトランザクション及びブロックと関連する詳細等の情報の格納のために使用されてもよい。1つ又は複数のプロセッサ2602は、本開示において説明されているいずれかの実施形態のステップ又は機能を提供するのに利用されてもよい。
【０１２１】
1つ又は複数のプロセッサ2602は、また、1つ又は複数のユーザインターフェイス入力デバイス2612、1つ又は複数のユーザインターフェイス出力デバイス2614、及びネットワークインターフェイスサブシステム2616と通信してもよい。
【０１２２】
バスサブシステム2604は、コンピューティングデバイス2600のさまざまな構成要素及びサブシステムが、意図されるように互いに通信することを可能とするメカニズムを提供してもよい。バスサブシステム2604は、単一のバスとして概略的に示されているが、バスサブシステムの代替的な実施形態は、複数のバスを利用してもよい。
【０１２３】
ネットワークインターフェイスサブシステム2616は、他のコンピューティングデバイス及びネットワークへのインターフェイスを提供してもよい。ネットワークインターフェイスサブシステム2616は、コンピューティングデバイス2600からデータを受信し、及び、コンピューティングデバイス2600から他のシステムにデータを送信するためのインターフェイスとして機能してもよい。例えば、ネットワークインターフェイスサブシステム2616は、データ技術者が、ネットワークにデバイスを接続することを可能としてもよく、それによって、そのデータ技術者は、データセンター等の遠隔の位置にある間に、そのデバイスにデータを送信し、及び、そのデバイスからデータを受信することを可能としてもよい。
【０１２４】
ユーザインターフェイス入力デバイス2612は、キーボード等の1つ又は複数のユーザ入力デバイス、一体化されたマウス、トラックボール、タッチパッド、又はグラフィックスタブレット等のポインティングデバイス、スキャナ、バーコードスキャナ、ディスプレイに組み込まれているタッチスクリーン、音声認識システム、マイクロフォン等の音声入力デバイス、及び、他のタイプの入力デバイスを含んでもよい。一般的に、"入力デバイス"の語の使用は、コンピューティングデバイス2600に情報を入力するためのすべての可能なタイプのデバイス及びメカニズムを含むことを意図している。
【０１２５】
1つ又は複数のユーザインターフェイス出力デバイス2614は、ディスプレイサブシステム、プリンター、又はオーディオ出力デバイス等の非視覚的ディスプレイ等を含んでもよい。ディスプレイサブシステムは、陰極線管(CRT)、液晶ディスプレイ(LCD)、発光ダイオード(LED)ディスプレイ等のフラットパネルデバイス、又は投影又は他のディスプレイデバイスであってもよい。一般的に、"出力デバイス"の語の使用は、コンピューティングデバイス2600から情報を出力するためのすべての可能なタイプのデバイス及びメカニズムを含むことを意図している。1つ又は複数のユーザインターフェイス出力デバイス2614は、例えば、ユーザインターフェイスを提示して、アプリケーションとの間の対話が適切であるときに、説明されているプロセス及びそれらのプロセスの変形を実行するアプリケーションとの間のそのようなユーザ対話を容易にするのに使用されてもよい。
【０１２６】
ストレージサブシステム2606は、コンピュータ読み取り可能な記憶媒体を提供してもよく、そのコンピュータ読み取り可能な記憶媒体は、本開示の少なくとも1つの実施形態の機能を提供することが可能である基本プログラミング構成及びデータ構成を格納する。(プログラム、コードモジュール、命令等の)アプリケーションは、1つ又は複数のプロセッサによって実行されるときに、本開示の1つ又は複数の実施形態の機能を提供することが可能であり、ストレージサブシステム2606の中に格納されてもよい。これらのアプリケーションモジュール又は命令は、1つ又は複数のプロセッサ2602によって実行されてもよい。ストレージサブシステム2606は、追加的に、本開示にしたがって使用されるデータを格納するためのリポジトリを提供してもよい。例えば、メインメモリ2608及びキャッシュメモリ2602は、プログラム及びデータのための揮発性記憶装置を提供してもよい。永続的な記憶装置2610は、プログラム及びデータのための永続的な(不揮発性の)記憶装置を提供してもよく、フラッシュメモリ、1つ又は複数のソリッドステートドライブ、1つ又は複数の磁気ハードディスクドライブ、関連する取り外し可能なメディアを有する1つ又は複数のフロッピーディスクドライブ、関連する取り外し可能なメディアを有する(例えば、CD-ROM又はDVD又はブルーレイ等の)1つ又は複数の光ドライブ、及び他の同様の記憶媒体を含んでもよい。そのようなプログラム及びデータは、本開示において説明されている1つ又は複数の実施形態のステップを実行するためのプログラムのみならず本開示において説明されているトランザクション及びブロックと関連するデータを含んでもよい。
【０１２７】
コンピューティングデバイス2600は、携帯用コンピュータデバイス、タブレットコンピュータ、ワークステーション、又は以下で説明されているいずれかの他のデバイスを含むさまざまなタイプのコンピューティングデバイスであってもよい。追加的に、コンピューティングデバイス2600は、他のデバイスを含んでもよく、そのような他のデバイスは、(例えば、USB、ヘッドフォンジャック、ライトニングコネクタ(Lightning  connector)等の)1つ又は複数のポートによってコンピューティングデバイス2600に接続されてもよい。コンピューティングデバイス2600に接続されることが可能であるデバイスは、光ファイバコネクタを受け入れるように構成される複数のポートを含んでもよい。したがって、このデバイスは、複数の光信号を複数の電気信号に変換するように構成されてもよく、それらの複数の電気信号は、処理のために、そのデバイスを接続するポートを介してコンピューティングデバイス2600に送信されてもよい。コンピュータ及びネットワークの絶えず変化する性質のために、図8に示されているコンピューティングデバイス2600の説明は、そのデバイスの好ましい実施形態を解説するためのある特定の例として意図されているにすぎない。図8に示されているシステムよりもより多くの構成要素又はより少ない構成要素を有する多くの他の構成が可能である。
【０１２８】
［要約］
今日のブロックチェーンは、マイニングのためであるか又はバニティーアドレスの決定のためであるかにかかわらず、計算量に大きく依存している。グループにわたってそれらの計算タスクを分散させて、グループの集合的な計算処理能力を利用することは有益である場合がある。
【０１２９】
この明細書において説明されている解決方法は、バニティーアドレスの決定を使用して、トラストレスの又はディーラーフリーのシステムにおいてより効率的な協調を可能にする改善された安全な協調技術を実証する。
【０１３０】
バニティーアドレスは、理論上は、いずれかの他のアドレスと同じ程度に安全であるが、独特のアドレスを使用すると、不正使用者が、代替のアドレスを提供し、その代替のアドレスが、他人を欺き、異なる口座に対して行われる決済につながる場合があるということがより困難になるということに留意すべきである。ユーザにとって使いやすく且つ人間によって読み取り可能なフォーマット又はパターンで、機械読み取り可能なコードを提示することによって、上記のリスクを最小化する。バニティーアドレスの中の各々の文字は、58個の異なる文字から選択可能である。あるアドレスの中のパターン"1B"の頻度は、1/58である。各々の追加的な文字は、58の倍数だけその頻度を減少させる(1/3364)。バニティーアドレスの複製は、そのストリングに追加される各々の新たな文字について、58の倍数だけより困難となり、より長いアドレスをより安全にする。
【０１３１】
本発明にしたがったディーラーフリープールにおける協調は、そのプールが、完全に並列的な方法で、安全且つ効率的に一緒に動作することを可能とし、第三者に依存することなく且つセキュリティのいかなる損失もなく、迅速な解決方法を可能とする。
【０１３２】
共有されている公開鍵のディーラーフリーの生成を一度実行する必要があるにすぎず、各々の参加者は、要求を満たすバニティーアドレスを独立して探索することが可能である。バニティーアドレスを発見すると、グループの参加者の個々の鍵の持ち分は、完全な共有されるアドレスに対応するように更新される。
【０１３３】
不正な行為又はフリーライディングは、また、その計算タスクにおける進行状況又は適用されるリソースを共有する正規の安全な且つトラストレスの手段によって禁止される。
【０１３４】
また、上記で言及されている複数の実施形態及び例は、本発明を限定するのではなく例示するものであり、当業者が、添付の特許請求の範囲が定義する本発明の範囲から離れることなく、多くの代替的な実施形態を設計することが可能であるということに留意すべきである。特許請求の範囲において、括弧の中に記載されている参照符号は、請求項に記載されている発明を限定するものと解釈されるべきではない。"含んでいる"及び"含む"等の語は、いずれかの請求項又は明細書全体の中に列挙されている要素又はステップ以外の要素又はステップの存在を除外するものではない。本明細書において、"含む"は、"含む又はから構成される"を意味し、"含んでいる"は、"含んでいる又はから構成されている"を意味する。ある要素の単数形の言及は、そのような要素の複数形の言及を除外するものではなく、その逆もまた同様である。本発明は、複数の個別の要素を含むハードウェアによって実装されてもよく、また、適切にプログラムされているコンピュータによって実装されてもよい。複数の手段を列記しているデバイスの請求項においては、これらの複数の手段のうちのいくつかは、ハードウェアの1つの同じ項目によって具体化されてもよい。ある特定の手段が相互に異なる従属請求項に記載されているという事実のみでは、これらの手段の組み合わせを有益に利用することは不可能であるということを示すものではない。
【０１３５】
［参考文献］
[1]  [Vanitygen  2016]
(URL:    https://en.bitcoin.it/wiki/Vanitygen)
[2]  [Addr  2016]
(URL:  https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses)
[3]  [Base58  2016]
(URL:  https://en.bitcoin.it/wiki/Base58Check_encoding)
[4]  [Shamir  1979]
Shamir,  Adi.  "How  to  share  a  secret."  Communications  of  the  ACM  22.11  (1979):  612-613.
[5]  [Nojourmian  2013]
Nojoumian,  Mehrdad,  and  Douglas  R.  Stinson.  "On  dealer-free  dynamic  threshold  schemes."  Adv.  in  Math.  of  Comm.  7.1  (2013):  39-56
[6]  [Goldfeder  2015]
Goldfeder,  Steven,  et  al.  "Securing  Bitcoin  wallets  via  a  new  DSA/ECDSA  threshold  signature  scheme."
[7]  [SEC  2010]
Standards  for  Efficient  Cryptography  (SEC)  -  Certicom  Research,
(URL:  http://www.secg.org/sec2-v2.pd)
[8]  [JoelKatz  2012]
(URL:  https://bitcointalk.org/index.php?topic=81865.msg901491#msg901491)
ビットコイン開発者の参考文献は、http://bitcoin.org/en/developer-reference  から取得される。
【図１】
2021507276.tif 000020
【図２】
2021507276.tif 000021
【図３】
2021507276.tif 000022
【図４】
2021507276.tif 000023
【図５】
2021507276.tif 000024
【図６ａ】
2021507276.tif 000025
【図６ｂ】
2021507276.tif 000026
【図７】
2021507276.tif 000027
【図８】
2021507276.tif 000028
【手続補正書】
【提出日】令和2年9月17日(2020.9.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の参加者(P)を有するグループ又はプールされているリソースによるタスクに対する解法(S)の安全な決定のためのコンピュータにより実装される方法であって、前記グループは、トラストレスの又はディーラーフリーのシステム又は方式によって動作し、当該コンピュータにより実装される方法は、
n個の参加者(P1…n)を有するグループ(P)を確立するか又は前記グループ(P)に参加するステップであって、n≧2である、ステップと、
初期の秘密鍵の持ち分(sn0)及び初期の公開鍵の持ち分(pk1)を生成し、そして、前記グループとの初期の共有されている公開鍵(pkO)を確立するステップと、
前記タスクを実行し、そして、前記解法(S)を探索するステップであって、前記解法(S)は、中間秘密鍵(rn0)及び前記グループの前記共有されている公開鍵(pkO)を使用して、前記タスクに対する回答(Ac)を決定する、ステップと、
前記解法(S)を発見し、そして、前記グループとの間で前記解法(S)を共有するか、又は、他の参加者から前記解法(S)を受信し、それにより、前記グループが、前記タスクに対する前記解法(S)を検証することを可能とする、ステップと、
前記解法(S)を提供した前記中間秘密鍵(rn0)及び前記初期の共有されている公開鍵(pk0)を使用して、検証されるとともに共有される公開鍵(pkv)を前記グループで計算するステップと、
前記解法(S)を提供した前記中間秘密鍵(rn0)及び前記初期の秘密鍵(son)の総和をとることによって、検証されている秘密鍵の持ち分(sv0)を構築するステップと、
前記他の参加者のすべて又は参加者のしきい値数と協調して、検証されている秘密鍵の持ち分(sv0)を使用することによって、前記検証されるとともに共有される公開鍵(pkv)に対する検証されるとともに共有される秘密鍵(skv)を構築するステップと、を含み、前記検証されるとともに共有される秘密鍵(skv)は、前記グループが、プロセスのリソース又はステージのロック解除又はアクセスのために集合的に動作することを可能とするコードとして使用される、
コンピュータにより実装される方法。
【請求項２】
クライアント(C)又は参加者(P)から、クライアントの秘密鍵(skc)から導き出されるクライアントの公開鍵(pkc)及び前記タスクを受信するステップをさらに含み、前記クライアントの公開鍵(pkc)は、前記タスクに対する前記解法の前記決定の際に使用される、請求項1に記載のコンピュータにより実装される方法。
【請求項３】
前記タスクを実行し、そして、前記解法(S)を探索するステップは、
前記中間秘密鍵(rn0)を使用して、前記初期の共有されている公開鍵(pkO)に追加される中間公開鍵(Rn0)を作成し、そして、前記中間秘密鍵(rn0)が探索された前記回答(Ac)を決定した解法であったか否かを決定するように処理される一時的な公開鍵(pknR)を作成するステップと、
前記回答(Ac)が決定されない場合に、前記中間秘密鍵(rn0)の値を増加させ、そして、前記解法(S)が決定され、且つ、前記回答(Ac)が証明されるまで前記処理を繰り返すステップと、を含む、請求項1及び2のうちのいずれか1項に記載のコンピュータにより実装される方法。
【請求項４】
前記初期の共有されている公開鍵(pk0)及び前記検証されるとともに共有される公開鍵(pkv)は、一度だけ生成される、請求項1乃至3のうちのいずれか1項に記載のコンピュータにより実装される方法。
【請求項５】
前記タスクは、少なくとも1つのグループメンバーが解法を発見することを必要とし、前記解法は、処理されると、特定のパターンを有する暗号通貨アドレスを生成する、請求項1乃至3のうちのいずれか1項に記載の方法。
【請求項６】
前記タスクは、セットパターン(A)の前記決定を必要とし、前記セットパターン(A)は、第三者又は他の参加者に由来し、前記第三者は、第三者秘密鍵(skc)を生成し、そして、前記グループに、対応する第三者公開鍵(pkc)を提供し、pkc＝skc×Gであり、Gは、楕円曲線基準点であり、前記第三者公開鍵(pkc)を受信し、前記セットパターンを決定するときに、pk＝pkc＋i×Gとなるように、増加変数(i)とともに前記第三者公開鍵(pkc)を使用して前記セットパターンを決定し、前記第三者に、前記解法の決定を可能とする前記増加変数(i)を送信し、それによって、前記第三者は、楕円曲線点乗算の同形特性に起因して、前記第三者のランダムな秘密鍵(skc)を使用して、前記解法を検証することが可能であり、sk＝skc＋iであり、pk＝sk×Gである、請求項1乃至5のうちのいずれか1項に記載の方法。
【請求項７】
n個の参加者の前記グループは、安全な複数当事者の計算(MPC)によって、前記初期の共有されている公開鍵(pkO)及び/又は前記検証されるとともに共有される公開鍵(pkv)を生成する、請求項1乃至6のうちのいずれか1項に記載の方法。
【請求項８】
前記初期の共有されている公開鍵(pkO)は、シャミアの秘密共有スキームを使用して前記グループの間で確立される、請求項1乃至7のうちのいずれか1項に記載の方法。
【請求項９】
前記共有されている秘密鍵(skv,sko)は、シャミアの秘密共有スキームを使用して前記グループの間で確立され、参加者自身のランダム次数tの多項式fi(x)を生成し、そして、その次に、各々の他の参加者Pjにfi(j)を安全に送信することによって、各々の参加者Piの間で、トラストレスの関係を確立し、各々の参加者は、前記受信したすべての点の総和f1(i)＋f2(i)＋…＋fn(i)をとって、前記共有されている多項式f(x)の前記Pi点である参加者の秘密の持ち分si＝f(i)を取得する、請求項1乃至8のうちのいずれか1項に記載の方法。
【請求項１０】
前記初期の秘密鍵の持ち分(sn0)の作成に続いて、bisn×Gであるときに、楕円曲線基準点Gを使用して前記初期の公開鍵の持ち分(pk1)を計算し、補間係数biは、
【数１５】
2021507276.tif 000029
であり、前記初期の公開鍵の持ち分(pk1)は、その次に、すべての参加者にブロードキャストされ、前記初期の共有されている公開鍵(pko)は、その次に、
【数１６】
2021507276.tif 000030
にしたがって、いずれかのt＋1個の持ち分の前記総和として計算される、請求項1乃至9のうちのいずれか1項に記載の方法。
【請求項１１】
前記タスクは、クライアント(C)又は参加者(P)から受信され、前記タスクは、指定されたパターンを有する暗号通貨アドレスのための秘密鍵を発見することであり、
前記中間秘密鍵(rn0)は、ランダムに生成され、中間公開鍵(Rn0)は、(rn0)によるシード番号の楕円曲線基準点(G)との倍数であり、
前記中間公開鍵(Rn0)は、前記共有されている公開鍵(pkO)に加算され、そして、処理されて、暗号通貨アドレスを生成する、請求項1乃至10のうちのいずれか1項に記載の方法。
【請求項１２】
前記解法(S)を提供した前記シード番号(rv0)を有するすべての参加者に対して、
【数１７】
2021507276.tif 000031
から前記検証されるとともに共有される公開鍵を計算し、
svn＝sOn＋rv0から計算される各々の参加者の検証されている秘密鍵の持ち分から、検証される秘密鍵(skv)を構築する、請求項11に記載の方法。
【請求項１３】
当該方法は、前記グループとの間で、前記タスクに適用される計算リソースを実証可能である中間結果を周期的に共有するステップをさらに含む、請求項1乃至12のうちのいずれか1項に記載の方法。
【請求項１４】
前記中間結果は、前記タスクに対する前記回答(Ac)の一部に対応する、請求項13に記載の方法。
【請求項１５】
前記中間結果は、困難さに比例するレベルを有し、1つ又は複数の参加者は、提示される中間結果の頻度及び/又は困難さに基づいて、他の参加者が適用する前記計算リソースを評価する、請求項13又は14に記載の方法。
【請求項１６】
コンピュータ実行可能な命令を含むコンピュータ読み取り可能な記憶媒体であって、前記コンピュータ実行可能な命令が実行されるときに、請求項1乃至15のうちのいずれか1項に記載の方法を実行するようにプロセッサを構成する、コンピュータ読み取り可能な記憶媒体。
【請求項１７】
電子デバイスであって、インターフェイスデバイス、前記インターフェイスデバイスに接続される1つ又は複数のプロセッサ、及び前記1つ又は複数のプロセッサに接続されるメモリを含み、前記メモリは、コンピュータ実行可能な命令を格納し、前記コンピュータ実行可能な命令が実行されるときに、請求項1乃至15のうちのいずれか1項に記載の方法を実行するように前記1つ又は複数のプロセッサを構成する、電子デバイス。
【請求項１８】
ブロックチェーンネットワークのノードであって、当該ノードは、請求項1乃至15のうちのいずれか1項に記載の方法を実行するように構成される、ノード。
【請求項１９】
請求項18に記載のノードを有するブロックチェーンネットワーク。
【国際調査報告】
2021507276.tif 000032
2021507276.tif 000033
2021507276.tif 000034