お互いを信頼していなくても、乱数を生成することは可能ですか? パート2

おい、ハブル！

В 最初の部分 この記事では、お互いを信頼していない参加者のために乱数を生成する必要がある理由、そのような乱数生成器に対してどのような要件が提示されているかについて説明し、その実装に対する XNUMX つのアプローチを検討しました。

記事のこの部分では、しきい値署名を使用する別のアプローチを詳しく見ていきます。

ちょっとした暗号化

しきい値署名がどのように機能するかを理解するには、基本的な暗号化について理解する必要があります。 スカラー、または単に数字という XNUMX つの概念を使用します。これらは小文字 (x、y) と楕円曲線上の点を大文字で示します。

しきい値署名の基本を理解するには、いくつかの基本的な事項を除いて、楕円曲線がどのように機能するかを理解する必要はありません。

1. 楕円曲線上の点を加算したり、スカラーで乗算したりすることができます (スカラーによる乗算を次のように表します)。 xGという表記ですが、 Gx 文献でもよく使われます）。 スカラーによる加算と乗算の結果は、楕円曲線上の点になります。

2. 要点だけを知ることで G とその積とスカラー xG 計算できません x.

多項式の概念も使用します p（x） 度 k-1. 特に、多項式の次のプロパティを使用します。値がわかっている場合 p（x） 誰にとっても k 異なる x (そしてそれ以上の情報はありません p（x））、計算できます p（x） 他の誰かのために x.

興味深いのは、どの多項式でも p（x） そして曲線上のどこかの点 G意味を知る p(x)G 誰にとっても k さまざまな意味 x、計算することもできます p(x)G 誰にとっても x.

これは、しきい値署名の仕組みと、しきい値署名を使用して乱数を生成する方法を詳細に調べるのに十分な情報です。

しきい値署名の乱数発生器

そう言ってみましょう n 参加者は乱数を生成したいと考えており、誰でも参加できるようにしたいと考えています。 k それらは数を生成するのに十分な数がありましたが、制御する攻撃者は k-1 人以下の参加者は、生成される数を予測したり影響を与えたりすることができませんでした。

このような多項式があるとします p（x） 度 k-1 最初の参加者が知っていること p（1）、XNUMX番目の人は知っています p(2)、 等々 （n-thは知っています p(n)）。 また、あらかじめ決められた点については、 G 誰もが知っている p(x)G すべての価値観に対して x。 電話いたします p(i) 「プライベートコンポーネント」 i番目の参加者（なぜなら i番目の参加者は彼女を知っています)、そして 豚 「パブリックコンポーネント」 i- 番目の参加者 (参加者全員が彼女を知っているため)。 覚えているとおり、知識は 豚 復元するには十分ではありません p(i)。

このような多項式を作成すると、 i-最初の参加者と他の誰も彼のプライベート コンポーネントを知りませんでした。これはプロトコルの最も複雑で興味深い部分であり、以下で分析します。 ここでは、そのような多項式があり、すべての参加者が自分のプライベートコンポーネントを知っていると仮定しましょう。

このような多項式を使用して乱数を生成するにはどうすればよいでしょうか? まず、ジェネレーターへの入力としてこれまで使用されていない文字列が必要です。 ブロックチェーンの場合、最後のブロックのハッシュ h はそのようなラインの良い候補です。 参加者が次を使用して乱数を作成できるようにします。 h 種のような。 参加者が最初に変換する h 事前定義された関数を使用して曲線上の点に移動します。

H = スカラーToPoint(h)

その後、参加者一人ひとりが i 計算して公表する Hi = p(i)H、 彼らは知っているから何ができるのか p(i) と H. 開示 H他の参加者がプライベート コンポーネントを復元することを許可しません iしたがって、プライベート コンポーネントの XNUMX セットをブロック間で使用できます。 したがって、以下で説明する高価な多項式生成アルゴリズムは、一度実行するだけで済みます。

時 k 参加者は解剖された Hi = p(i)H、 誰でも計算できる H×＝ p(x)H みんなの x 前のセクションで説明した多項式の性質のおかげで。 この時点で参加者全員が計算します H0 = p(0)H、 これが結果として得られる乱数です。 誰も知りませんのでご注意ください p(0)、 したがって、計算する唯一の方法は p(0)H – これは補間です p(x)H、 それは次の場合にのみ可能です k 価値観 p(i)H 知られています。 少量でも開封可能 p(i)H に関する情報は提供されません p(0)H。

上記のジェネレーターには、必要なプロパティがすべて含まれています。攻撃者は制御のみを行います。 k-1 人以下の参加者は結論に情報や影響力を持ちませんが、参加者は全員 k 参加者は結果の数値とそのサブセットを計算できます。 k 参加者は、同じシードに対して常に同じ結果に達します。

上記で慎重に回避した問題が XNUMX つあります。 補間が機能するには、値が次のとおりであることが重要です。 H各参加者が公開したi i 本当に同じでした p(i)H. 他には誰もいないので、 i- 番目の参加者は知りません p(i)、 以外の誰も i-番目の参加者はそれを確認できません Hi 実際には正しく計算されており、暗号による正しさの証明はありません H攻撃者は任意の値を次のように公開できます こんにちは、 乱数発生器の出力に任意に影響を与える:

最初の参加者によって送信された H_1 の値が異なると、結果の H_0 も異なります

正しさを証明するには少なくとも XNUMX つの方法がある H多項式の生成を分析した後でそれらを検討します。

多項式の生成

前のセクションでは、このような多項式があると仮定しました。 p（x） 度 k-1 参加者が i 知っている p(i)、そして他の誰もこの値についての情報を持っていません。 次のセクションでは、事前に決められた点についてもそれが必要になります。 G 誰もが知っていた p(x)G みんなの x.

このセクションでは、各参加者がローカルに秘密鍵を持っていると仮定します。 西、 誰もが対応する公開鍵を知っているように Xi.

考えられる多項式生成プロトコルの XNUMX つは次のとおりです。

1. 各参加者 i 任意の多項式をローカルに作成します pi(x) 次数 k-1。 次に、各参加者を送信します。 j значение pi(j)、公開鍵で暗号化 Xj. したがって、のみ i-よ и j-よ 参加者は知っています pi(j)。 参加者 i も公表しています pi(j)G みんなの j から 1 до k 包括的です。

2. すべての参加者が何らかの合意に基づいて選択します k 多項式が使用される参加者。 参加者の中にはオフラインの場合もあるため、全員が揃うまで待つことはできません。 n 参加者は多項式を公開します。 このステップの結果はセットです Z 少なくともからなる k ステップ (1) で作成された多項式.

3. 参加者は自分が知っている価値観を確認します pi(j)は公表されているものに相当 pi(j)G. このステップインの後、 Z プライベートに送信された多項式のみ pi(j)は公表されているものに相当 pi(j)G.

4. 各参加者 j プライベートコンポーネントを計算します p(j) 合計として pすべての i(j) i в Z。 各参加者もすべての値を計算します p(x)G 合計として すべての i に対して pi(x)G в Z.

ご了承ください p(x) – それは本当に多項式です k-1、 それは個人の合計だから pi(x)、それぞれは次数の多項式です k-1. 次に、各参加者が j 知っている p(j)、 彼らはそれについての情報を持っていません p（x） のために x ≠ j。 実際、この値を計算するには、すべてを知る必要があります。 パイ(x)、 そして参加者である限り j 選択された多項式の少なくとも XNUMX つを知りません。十分な情報がありません。 p(x)。

これは、前のセクションで必要だった多項式生成プロセス全体です。 上記のステップ 1、2、および 4 の実装は非常に明白です。 しかし、ステップ 3 はそれほど簡単ではありません。

具体的には、暗号化されていることを証明できる必要があります。 pi(j) は実際に公開されているものに対応します pi(j)G. 証明できない場合、攻撃者は i 代わりにゴミを送るかもしれない pi(j) から参加者へ jと参加者 j 本当の価値を得ることができなくなります pi(j)、 プライベートコンポーネントを計算できなくなります.

追加のメッセージを作成できる暗号化プロトコルがあります 証明i(j)、どの参加者も何らかの値を持つ e, 及び 証明(j) и pi(j)G はローカルで検証できる e - それは本当に pi(j)、 参加者のキーで暗号化される j. 残念ながら、そのような証拠のサイズは信じられないほど大きく、公開する必要があることを考えると、 O（nk） そのような証拠をこの目的に使用することはできません。

それを証明する代わりに パイ(j) 一致 pi(j)G 多項式生成プロトコルに非常に長い時間を割り当てることができ、その間にすべての参加者が受信した暗号化されたメッセージをチェックします。 pi(j)、 復号化されたメッセージが公開メッセージに対応しない場合 pi(j)G では、受信した暗号化メッセージが間違っているという暗号学的証拠を公開しています。 メッセージであることを証明してください ノー 一致 豚） 一致することを証明するよりもはるかに簡単です。 これは、各参加者がそのような証拠を作成するために割り当てられた時間内に少なくともXNUMX回オンラインに登場することを要求しており、そのような証拠を公開すれば、同じ割り当て時間内に他のすべての参加者にその情報が届くという前提に基づいていることに注意してください。

参加者がこの期間中にオンラインに現れず、少なくとも XNUMX つの間違ったコンポーネントを持っていた場合、その特定の参加者はそれ以降の番号生成に参加できなくなります。 ただし、少なくとも k 正しいコンポーネントを受け取ったばかりか、割り当てられた時間内に不正の証拠を残すことができた参加者。

H_i の正しさの証明

最後に議論すべき部分は、公開された情報の正確性をどのように証明するかです。 H私、つまりそれ Hi = p(i)H、 開けずに p(i)。

価値観を覚えておいてください H、G、p(i)G 公であり、誰にでも知られています。 受信動作 p(i) 知っている 豚 и G 離散対数と呼ばれる、または ドログ、 そして私たちは次のことを証明したいと考えています。

dlog(p(i)G, G) = dlog(Hi, H)

開示せずに p(i)。 そのような証明のための構造は存在します。たとえば、 シュノアプロトコル.

このデザインでは、参加者一人ひとりが、 Hi 設計に従って正しいことの証明を送信します。

乱数が生成されると、多くの場合、その乱数を生成した人以外の参加者がその乱数を使用する必要があります。 このような参加者は、番号とともにすべてを送信する必要があります。 Hi および関連する証拠。

好奇心旺盛な読者はこう尋ねるかもしれません。なぜなら、最終的な乱数は H0、および p(0)G – これは公開情報であるのに、なぜ個人ごとに証拠が必要なのでしょうか？ H代わりにその証拠を送ってみませんか

dlog(p(0)G, G) = dlog(H0, H)

問題は、その値を誰も知らないため、Schnorr プロトコルを使用してそのような証明を作成できないことです。 p（0）、証明を作成するために必要であり、さらに、乱数生成器全体がこの値を誰も知らないという事実に基づいています。 したがって、すべての値が必要です Hi そしてその正しさを証明するための個々の証拠 H0.

ただし、意味的に乗算に類似した楕円曲線上の点に対する演算があった場合、正しさの証明は行われません。 H0 それは些細なことであり、単にそれを確認するだけです

H0× G = p(0)G×H

選択したカーブがサポートしている場合 楕円曲線の組み合わせ、この証明は機能します。 この場合 H0 は乱数発生器の出力であるだけではなく、それを知っている参加者であれば誰でも検証できます。 G、H и p(0)G. H0 はシードとして使用されたメッセージの署名でもあり、次のことを確認します。 k и n 参加者はこのメッセージに署名しました。 したがって、もし シード – はブロックチェーンプロトコルのブロックのハッシュです。 H0 は、ブロック上の複数の署名であると同時に、非常に優れた乱数でもあります。

結論

この記事は技術ブログ シリーズの一部です NEAR。 NEAR は、開発の容易さとエンドユーザーの使いやすさに重点を置いた分散型アプリケーションを開発するためのブロックチェーン プロトコルおよびプラットフォームです。

プロトコル コードはオープンであり、実装は Rust で書かれており、次の場所で見つけることができます。 ここで.

NEAR の開発がどのようなものかを確認し、オンライン IDE で実験することができます ここで.

すべてのニュースをロシア語でフォローできます。 電報グループ と VKontakteのグループ、公式では英語で さえずり.

またね！

出所： habr.com