Develop with pleasure!

福岡でCloudとかBlockchainとか。

秘密分散ベースのMPCプロトコルSPDZ

秘密分散 MPC

最近のECDSAの閾値署名のペーパー読んでたら、まずSPDZ（スピーズ）について理解しておく必要がありそうだったので、秘密分散ベースのMPCプロトコルであるSPDZの仕組みについてまとめてみる。

秘密分散とは？

ある要素aを持っていた場合、それをa = a1 + a2という関係を満たすようランダムに分割する。そしてa1をAさんに、a2をBさんに与える。AさんもBさんもaの値自体については知らないが、協力して値を合算すればaが分かる。この時分割された断片a1やa2をシェアと呼び、シェアを集めると元の秘密の値が分かる仕組みを秘密分散と呼ぶ。

シークレット値をシェアに変換する方法はいくつかあって、↑のようにa = a1 + a2と加算する方法もあれば、a = a1 * a2となるような乗算的な方法や、シャミアの秘密分散法のように多項式を利用して予め指定した閾値分だけシェアを集めればシークレット値を復元できるような方法もある。

※ 上記のようにあるシークレット値aが全ての参加者間で秘密分散されていることを示すのに＜a＞という表記を使用する。

秘密分散法を使った秘密計算

この秘密分散を利用して秘密計算を行うプロトコルの１つがSPDZで、演算回路の共同計算を可能にするMPCプロトコルになる。

といっても分かりづらいので、もう少しかいつまんで言うと、↑のように秘密分散のシェアを入力として使って、そのシェアに対して加算や乗算を行うことで、情報を秘匿したまま演算を行い、その結果を集めて復元すると秘密の値に対して演算したのと同じ結果を復元することができる。つまり秘密計算ができる。さらに加算と乗算ができるということは、計算したい内容を加算と乗算の組み合わせによる（ANDゲート、XORゲート、NOTゲートなどの任意の論理ゲートで構成される）回路として表現できる、つまり任意の関数を計算することができる。

ちなみに秘密計算を実現する方法としては、秘密分散法以外にも↓の方法などがある。

  • Garbled circuitを使う方法
    二者間でプライベート入力を介してトラストレスに機能を共同評価可能な暗号プロトコル。評価する関数はBoolean circuitとして記述する。
  • 準同型暗号を使う方法
  • 完全準同型暗号を使う方法

SPDZは加法型の秘密分散方式（↑のa = a1 + a2パターン）を採用しており、この方式でどのように加算、乗算がサポートされるのか見ていこう。

加算

加算は簡単だ。シークレット値a, bがあり、そのシェアをそれぞれ {a_i, b_i}とし各参加者が保持していると仮定する。

各参加者はローカル環境で {a_i + b_i}を計算できる。 {a = \sum_i a_i , b = \sum_i b_i}かつ {\sum_i a_i + \sum_i b_i = \sum_i (a_i + b_i)}であるため、各参加者が計算した値 {a_i + b_i}はa + bの秘密分散値とも言える。

そのため各参加者からそれぞれ {a_i + b_i}を集めるとa + bの値が分かる。

またこの他、ある値αをシェア {a_i}に乗算すると、 {\sum_i αa_i = α\sum_i a_i}であるため、各参加者はαaのシェアを持つという性質もある。

上記のように加法型の秘密分散値は線形特性があるので、こういった演算を通信を必要せずに行えるのがメリットになる。

乗算

乗算は加算より複雑になる。シークレット値x, yがあり、そのシェアをそれぞれ {x_i, y_i}とし各参加者が保持していると仮定すると、乗算のゴールはシェア {x_i, y_i}を入力としてx * yを計算すること。

乗算を行うには {x_i, y_i}以外に、c = a * bの関係を満たす３つの要素a, b, cを用意し各参加者はそのシェア {(a_i, b_i, c_i)}を持つ。

  1. 各参加者は、上記のシェアを使って、 {x_i - a_i}と {y_i - b_i}をブロードキャストする。
  2. 全員の１が揃うと(x - a), (y - b)が分かる。
  3. 参加者は２のデータを使って、 {z_i = c_i + (x - a)b_i + (y - b)a_i}を計算することができる。
  4. 3のシェアを集めると {\sum_i z_i = c + (x - a)b + (y - b)a}が計算できる。
  5. ４に対して (x - a) * (y - b)を加算すると {\sum_i z_i + (x - a) * (y - b) = c + (x - a)b + (y - b)a + (x - a) * (y - b) = xy}

となり、x * yが得られる。つまり、 {z_i}はx * yのシェアであると考えることができ各参加者はそれを持っていることになる。

↑のようにc = a * bの関係を満たす要素（トリプル）を使えば、秘密分散データの乗算が可能になる。つまり、多数のトリプルを用意すれば、秘密分散データに対して多数の乗算を行うことができ、どんな算術回路も計算できるということ（※ただしトリプルは再利用できず、乗算毎にそれぞれ異なるトリプルを用意する必要がある。再利用すると秘密に関する情報が明らかになるため）。

トリプルは秘密分散データとの依存性は無く、評価する回路（関数）とも無関係なので、回路を評価する前に事前に準備しておくことができる。

SPDZプロトコルの概要

SPDZは↑の加算型の秘密分散法を利用して入力が共有されるプロトコルで、オフラインフェーズ（前処理フェーズとも呼ぶ）とオンラインフェーズの２段階のフェーズで構成される。

オフライン（前処理）フェーズ

オフラインフェーズでは↓を行う（オフラインとあるけど、厳密にオフラインではなく参加者間の通信は行われる）。

  • 入力や評価対象の関数とは無関係に、↑の乗算に使用するc = abの関係を満たす乗算トリプルを生成する。オリジナルのペーパーでは準同型暗号を使用。
  • 回路に入力を提供する際に各参加者が使用するランダム値rの生成。

各参加者は生成した以下の値を保持する。

  • 多数のトリプルのシェア
  • {r = \sum_i r_i}となるランダム値rのシェア {r_i}

※ 上記に加えて、出力値が正しく計算されているか最後に検証するために使用するMAC鍵に同意し、そのシェアを各参加者は保持する。この段階でMACの鍵のデータを知るユーザーはおらず（いたら値の偽造ができるので）、各参加者はそのシェアを持つのみ。

オンラインフェーズ

オンラインフェーズは、オフラインフェーズで用意したトリプルを使って、実際に回路を評価する。

入力値を秘密分散

回路を評価する前に、最初に回路への入力を用意する。入力を提供するのがPiでその入力値を {X_i}とすると、そのまま提供すると秘密計算にならないので、以下の計算を行って {X_i}のシェアを作る。

  1. Piはオフラインフェーズで生成されたランダム値ｒをオープンする（最初からPiが入力を提供すると分かっている場合、オフラインフェーズで実行可能）。これはオフラインフェーズでシェア {r_i}を持つ参加者がそれをPiに送ることで、全部集まればPiがそれを合計してrを計算できる。
  2. Piは {ε = X_i - r}を計算してブロードキャストする。
  3. 各参加者は自身が持つrのシェア {r_i}とεを使って {X_i}のシェア {x_i = r_i + ε}を計算する。

SPDZでは↑のようにして入力値のシェアを作成する。

回路の評価

入力値のシェアが作成できたら↑の加算や、オフラインフェーズで生成したトリプルを使って乗算の操作ができるようになるので、入力シェアを使って回路を評価する。実際の計算は↑の加算・乗算の組み合わせ。

各参加者による計算が終わったら、各参加者が持っている出力値のシェアを集めれば最終的な出力値を入手できる。

MACを利用したデータの正しさの検証

出力値が正しいのは各参加者が正しく計算した場合のみで、悪意ある参加者が意図しない計算をしていた場合、出力値は意図する値ではなくなる。このため、最終的な出力値を計算した際に、それが正しく計算されたものかどうか検証する仕組みが必要になる。この検証のためにMACを使用する。詳しくは追ってないけど、各参加者は結果をオープし、MAC鍵のシェアの組み合わせに対して線形なコミットメントを作成し、共有する。その後MACの鍵をオープンして、結果の整合性を検証するっぽい。

以上がSPDZの概要。SPDZが発表されて以降、オフラインフェーズを中心にさまざまな最適化や改善の提案があり、いろんなバージョンのSPDZが存在する。

参考

Bitcoin Scriptの分岐処理の実装とオーバーヘッド

Bitcoin

最近Bitcoin Coreにマージされた↓の改善について

github.com

Bitcoin Core PR Review Clubで取り上げられていたので↓、内容について見ておく。

bitcoincore.reviews

Bitcoin Scriptの分岐処理

Bitcoinはスタック型のスクリプト言語を使ってコントラクトを実行できるようになっている。スクリプトはスタックにプッシュされたデータ要素と、スタック要素を操作するためのopcodeで構成される。このopcodeの内、以下のopcodeを使用するとif文を使ってスクリプトの制御フローを分岐することができる。

  • OP_IF
  • OP_NOTIF
  • OP_ELSE
  • OP_ENDIF

例えばスクリプト実行中にOP_IFが現れると、その時のスタックの１番上の要素を評価して、OP_IF分岐を実行するかどうかが決まる。もし要素がtrueを表すものであればOP_IF分岐は実行されるが、falseを表す場合、OP_IF分岐は実行されず、その後出てくるOP_ELSE分岐の方が実行される。尚、これらの分岐は複数の階層にネスト可能だ。

インタプリタの実装

スクリプトの評価は、スタック上の要素を切り替えながらループ処理される。↑の分岐処理がBitcoin Coreでどのように実装されているかだが、これまでの実装では、bool値のvectorであるvfExecという変数で制御されてきた。

  • 実行中にOP_IFもしくはOP_NOTIFが検出されると、bool値がvector vfExecにプッシュされる。
  • OP_ELSEが検出されると、vectorの最上位bool値が反転する。
  • OP_ENDIFが検出されるとvectorの最上位bool値がポップされる。
  • ループ処理ではbool値が全てtrueの場合のみ（bool fExec = !count(vfExec.begin(), vfExec.end(), false);）、実行すべきブランチと判断して処理が継続する。

そのため、例えばOP_IFを検出して、結果がfalseの場合では、スクリプトは次のOP_ELSEまでジャンプするようなことはなく（Bitcoin Scriptにジャンプ処理はない）、OP_IF分岐の中に入って現在のvfExecの値を確認して処理をするかどうか判断し、falseであれば次のループ処理を継続する。OP_IFが実行されない分岐であって、その中にOP_CATなどの無効なopcodeが含まれていた場合、実行されないのに無効なopcodeがあるとSCRIPT_ERR_DISABLED_OPCODEエラーが出るはそのためだ。

問題点

↑の処理方法の問題点を指摘しているのがSergio Demian Lernerのブログ↓

bitslog.com

これまでの実装を悪用する以下のようなスクリプトを用意した場合、

0
OP_IF { 100 times }

0 { 9798 times }

OP_ENDIF { 100 times }
1

vector vfExecに100個の要素がプッシュされ、各要素が9799回スキャン（カウント）される。つまり合計979900回スキャンされる。ブロックを全てこのスクリプトで埋めた場合ブロックの評価に2.5秒かかるようになると。

最悪のケースではチェック処理の時間が二次的に増加していくことが懸念されるが、現状スクリプト内のopcodeの最大数は201という制限があるため、大きな問題はない。

Taproot導入による問題

ただ、今後Taprootの導入（正確にはTapscript）により問題が顕在化する可能性がある。

techmedia-think.hatenablog.com

Taprootで実行可能なTapscriptではopcodeの最大数201という制限が外れる。このため検証に時間がかかるブロックを作成するのに↑が悪用される可能性がある。

修正内容

↑のPRでは、vfExecをbool値のvectorではなく、整数のペアにすることでO(n)だったチェックをO(1)で出来るように修正している。

具体的には以下の２つのプロパティを持つConditionStackというクラスに置き換わる。

  • m_stack_size： 分岐スタックのレベル
  • m_first_false_pos： ↑のスタック中に最初にfalseが出る位置

これまではvector内にfalseが無いか全要素のチェックが必要だったのに対して、↑では、m_first_false_posの値をチェックするだけ（O(1)）で済むようにしたと。具体的なコードは↓

https://github.com/bitcoin/bitcoin/blob/67dfd18f4401986063e22c79d4d7da61f15b5cd4/src/script/interpreter.cpp#L281-L343

TaprootやTapscriptでは細かい適用ルールが変わってるので、その影響を調査するのも結構大変だと思う。

Bulletproofのrange proofに任意のデータを埋め込む方法と復元する（rewind）方法

Bulletproof Mimblewimble Grin Cryptography

先日、Grinがウォレットリストアの際に自身のUTXOを識別するのにBulletproofsのrange proofにヒントを隠している記事を書いたけど、↓

techmedia-think.hatenablog.com

今回の記事では、リストアという限定的な利用方法だけでなく任意のデータをrange proofに埋め込む方法としてまとめてみる。

range proof生成時のメッセージの埋め込み

Grin自体はRustで実装されているが、range proofの生成や検証はlibsecp256k1にBulletproofの拡張を加えたsecp256k1-zkpを使っている。range proofの生成処理はこちら。

埋め込み可能なメッセージは今のところ20バイトなので、RIPEMD160とかのハッシュ値とかが向いてる。

関係するところだけ抜き出すと、

  1. 生成者はnonceを生成する。
  2. chacha20ストリーム暗号を使ってnonceから、シークレット値alpha、rhoを生成する。
  3. コミットメントのvalue値を32バイトのバイト列に変換する。ここでvalue値が取る範囲は8バイトなので、上位24バイトは空いている状態になる。
  4. 3のバイト列の[4〜23]バイト列に20バイトのメッセージを埋め込む。
  5. 4のバイト列をスカラー値に変換する。この値をvalsとする。
  6. mu = alpha - vals + rho * x を計算する。
  7. -mu を計算し、range proofにセットする。

上記のように、muを計算する要素の中にメッセージを組み込んでいる。実は↑のウォレットのリストアの際に使っている付加情報（flags|path）は、このメッセージとして埋め込まれている。

proofからメッセージの復元

↑の生成時に使われたnonceを知っていれば、proofからメッセージを復元できる。この復元処理の実装はこちら。

  1. nonceからchacha20ストリーム暗号を使ってnonceから、シークレット値alpha、rhoを生成する。
  2. proofには-muがセットされているので、-mu + alpha + rho * x = valsを計算する。
  3. vals[4-23]がメッセージとなる。

とメッセージが復元できる。これはproof生成時に使用したalpha、rhoの知識があるため復元できるが、その知識がない場合、メッセージは復元できない。

ウォレットのリストアの記事↑も基本的にはこの仕組みを利用したもの。

非対話型トランザクション作成

ウォレットのリストア以外にもrange proofにデータを埋め込むことで可能になるプロトコルもある。Grinで提案されているMimblewimbleで非対話でトランザクションを作成するためのプロトコル案もそのうちの１つだ。

Mimblewimbleで送金トランザクションを作成する際は、トランザクションカーネルに有効な署名をセットするため、送信者と受信者が協力する必要がある。具体的な仕組みについてはGBECでの解説動画参照↓

goblockchain.network

有効なSchnorr署名を作成するには送信者と受信者両方のブラインドファクターの知識が必要となるため、Mimblewimbleでは非対話型のトランザクションを作るのは難しいとされてきたが、これをDiffie-Hellmanの鍵共有を活用して非対話型にしようという提案が最近出てきた↓

https://gist.github.com/DavidBurkett/32e33835b03f9101666690b7d6185203

仕組みは簡単で、

  1. 送信者が一時鍵ペアを生成する。
  2. 送信者は自身の秘密鍵と受信者の公開鍵とでECDHを実行し共有シークレットを生成する。この共有シークレットは受信者が受け取るコイン＝コミットメントのブラインドファクターを暗号化/復号化するために使用する。
  3. 送信者は送信トランザクションを作成し、受信者のアウトプットをセットし、有効な署名を生成しトランザクションカーネルにセットする。

これで有効なトランザクションができるので後はブロードキャストするだけ。ベースの仕組みはステルスアドレスなんかでも使われているよくある仕組みだ。

この手順で問題になるのが、

  • 受信者がブラインドファクターを知るためには、送信者がECDHを実行する際に使用した鍵ペアの公開鍵を知る必要がある。
  • 送信者が受信者のコミットメントのブラインドファクターを知ってしまっている。

という２点。

前者はともかく、後者はコインを送ってもらってもブラインドファクターを送信者が知ってしまっている状態では、そのコインを元の送信者も利用可能な状態になってしまうのでまずい。

コンセンサスルールの変更

↑の２つの問題に対応するため、以下のコンセンサスルールを追加する。

  • 各アウトプットはコミットメントの他にoutput_dataを含むようになる。このoutput_dataには以下が含まれる。
    • 送信者の一時公開鍵（送信者の公開鍵を含めることで受信者はECDHにより共有鍵を生成でき暗号化されたデータを復号することができる）
    • 受信者の公開鍵
    • 暗号化されたデータ。以下の２つのデータがECDHの共有鍵で暗号化されている。
      • アウトプットのコインの量
      • アウトプットのブラインドファクター
  • 各ノードはコミットメントと一緒にoutput_dataを保存する。
  • output_dataを持つコミットメントを使用する場合、トランザクションのインプットにはそのコミットメントと一緒に、output_dataの受信者の公開鍵に対して有効な署名がセットされなければならない。このルールにより送信者と受信者の両者がコインの所有権を持つことを回避する。

range proofの利用

↑ルールにより、２つの問題は解消する。ただ、このルールだけではまだ十分ではない。各アウトプットには現状Commitmentとrange proofがあるが、これにoutput_dataを単純に加えただけでは、このデータはどこにもコミットされていないので、output_dataだけ改竄して別のデータにしてしまうことができてしまう（Bitcoinの場合と違って、Grinの場合、署名対象のメッセージはトランザクションカーネルのデータから作られるため）。

この問題に対処するために、追加のデータ（output_data）にコミットするのに↑のrange proofを使う。このユースケースでは、nonceは既知のデータとして扱われる。

プルーフの生成者は、

  • nonceをblake2b(Commitment)として計算し、
  • output_dataのハッシュ値をripemd160(blake2b(output_data))として計算し、これをメッセージとして↑のnonceを使ってrange proofに埋め込む。

その上で、以下のルールをコンセンサスルールにさらに追加する。

  • Commitmentからnonce = blake2b(Commitment)を計算する。
  • 計算したnonceを元にrange proof内のメッセージを復元し、その20バイトの値が、アウトプットのripemd160(blake2b(output_data))と一致するか検証する。

上記の仕組みを追加することで、output_dataを変更できなくすることができる。ただ↑の計算ができると取引量も計算できるようになるので、muの計算にvalue値は含めずにoutput_data内のもののみとする必要があるんじゃないかと思う。

↑はあくまでまだ提案の段階なので実際にどうなるかはまだ不明。特定のrange proofの実装に依存しない方が良いのでトランザクションカーネルを利用する提案もある。個人的には量がCommitment以外に暗号化された状態でセットされるようになるので、将来AESの暗号仮定が崩れた場合にCommitmentだけであれば過去含め取引量は不明なままだったのに、暗号化されたデータであれば復号化されてしまうと過去の取引量も分かってしまうのが微妙に思う。

Bulletproofsを利用したGrinのウォレットのリストア

Grin Mimblewimble Bulletproof

BitcoinのウォレットであればほぼBIP-32のHDウォレットをサポートしているため、マスターシードさえバックアップしておけば、いつでもウォレットをリストアすることができる。Bitcoinの受け取りに使用するアドレスは全てマスターシードから導出した鍵から作られるためだ。

一方、MimblewimbleのようにPedersen Commitmentにコインをロックしている通貨の場合、ウォレットのリストアはBitcoinほど単純ではない。

基本的にMimblewimbleをサポートしている場合、UTXOは以下のような形式のPedersen Commitmentになる。

Commitment = rG + vH

ここで、ブラインドファクターrが秘密鍵に該当し、vがコインの量になる。

rはBitcoinと同様マスターシードから導出可能だが、Commitmentはコインの量vを含んでいるため、vの情報が無いとCommitmentを見ただけでは自分が所有するUTXOなのかどうか判断ができない。このCommitmentで使われているブラインドファクターとコインの量、両方分かって初めて判断ができるが、そのためrとvの組み合わせを全てバックアップしておくというのは効率がよくない。それだとシードの意味がなく、BIP-32登場以前の全ての秘密鍵をバックアップしておくのと変わらない。

そこでMimblewimbleをサポートしているGrinでは、Commitmentで使用されているrをマスターシードから導出するための導出パスと、コインの量をCommitmentに対応するBulletproofsのrange proofに隠し、ウォレットのリストア時にその情報を復元することでウォレットが自身のUTXOをスキャンできるようにしている。

Bulletproofのrange proofのパラメータ

以前↓でrange proofの生成と証明について書いたけど、

techmedia-think.hatenablog.com

range proofを生成する際、証明者は以下の４つのシークレット値を生成している。

  • alpha：コインの量vのバイナリ表現である {a_L}へのコミットメントAを作成する際に選択するシークレット値（↑ブログ内のα）。
  • rho：range proofでコインの量を秘匿するためのブラインドファクター {s_L, s_R}へのコミットメントSを作成するために選択するシークレット値（↑ブログ内のp）。
  • tau_1：range proof作成時の多項式の次数１の係数 {t_1}へのコミットメント {T_1}を作成する際に選択するシークレット値（↑ブログ内の {\tilde{t_1}}）。
  • tau_2：range proof作成時の多項式の次数2の係数 {t_2}へのコミットメント {T_2}を作成する際に選択するシークレット値（↑ブログ内の {\tilde{t_2}}）。

そして、これらの値を使ってrange proofを生成する際に、以下のパラメータの計算が行われる。

  • {mu = alpha + rho*x}（xはランダムチャレンジの値）
  • {tau_x = tau_2 * x^{2} + tau_1 * x + z^{2}*gamma}（gammaはコミットの秘密鍵で、zはランダムチャレンジ）

このmuは以下のようにmu'置き換えられる。

mu' = mu + flags|path|v

ここで

  • flags： 0|type|switch_commitment_scheme|derivation_depthで構成される4バイトのデータ。
    • 0: 予約データで、今後の拡張の際にインクリメントして使われる。
    • type：ウォレットのタイプを指定（通常、子ウォレット、マルチシグ）
    • switch_commitment_scheme：Switch Commitmentのタイプを指定（0:なし、1:現状のSwitch Commitmentタイプ）
    • derivation_depth：導出パスのレベル
  • path：コインのBFをを導出するための導出パス
  • v：コインの量

そしてmu'と {tau_x}はrange proofに含まれるデータとなる。

Grinでのシークレット値の導出

Grinでは↑の４つのシークレット値（alpha, rho, tau_1, tau_2）を以下の2つのnonceから決定論的に導出している。

  • rewind_nonce = H(H(pub_root_key), commit)
    このrewind_nonceからalphaとrhoを導出する。
  • private_nonce = H(H(root_key), commit)
    private_nonceからtau_1、tau_2を導出する。

つまり、range proofを作成する際のシークレット値を、マスターシードから導出したルート公開鍵、ルート秘密鍵と各UTXOのコミットメントから導出している。

ウォレットのリストア

↑のようにrange proof生成時のシークレット値が決定論的に導出されるため、ウォレットをリストアする際に、マスターシードを復元後、ウォレットはチェーン上の有効なUTXOに対して以下のスキャンを行うことで、そのUTXOが自分が所有するUTXOかどうか識別する。

  1. UTXOのCommitmentに対して、rewind_nonceとprivate_nonceを計算する。
  2. mu = alpha + rho*xを計算する。
  3. proof内のmu'からmuを引いて、flags|path|vの値を導出する。
  4. pathを使って、このCommitmentに使われているブラインドファクターを導出する。
  5. vをこのCommitmenのコインの量とする。
  6. 4,5の値を使ってCommitmentを計算し、それがUTXOの元のCommitmentと一致するか検証する。
    • 一致すればそのUTXOはこのウォレットが所有するUTXO
    • 一致しない場合、そのUTXOは自分とは関係ないUTXO

※ watch-onlyなウォレットを作りたい場合は、拡張公開鍵（pub_root_key）のみを共有すればいい。この場合４でブラインドファクター自体は導出できないが、ブラインドファクターを秘密鍵とした公開鍵rGはpathを使って導出できるので、その点とvHを加算して、Commitmentを計算すればいい。

というように、Grinではrange proof内にブラインドファクターの導出パスとコインの量を隠すことで、Bitcoinと同じようにマスターシードのみのバックアップでウォレットのリストアができるという仕組みが実装されている。

参考

このあたりの仕様はちゃんとドキュメントに記載されていないので、以下の情報を参考にした。

Verifiable Delay Function

Cryptography

最近ブロックチェーン関連のペーパーでよく話題に上がる新しい暗号プリミティブVerifiable Delay Function（VDF）について調べてみた。

VDFに関する研究は、以下のサイトでまとめられている。

https://vdfresearch.org/

今回はVDF Day 2019のDan Bonehのセッションを見てみる↓

http://diyhpl.us/wiki/transcripts/verifiable-delay-functions/vdf-day-2019/dan-boneh/

VDFとは？

VDFは参加者が並行多項性を持っている場合でも、評価にTステップかかることになっている関数（並列処理してもスピードアップしない）で、分散環境において難しいとされる偏りの無いランダム性や時間経過のプロキシなどの機能を提供する。

VDFには

  • セットアップ
    セキュリティパラメータλと時間制限Tを入力にとり、公開パラメータpを生成する。
  • 評価
    評価関数は(p, x)を入力として、出力yとプルーフを生成する。並列コンピュータを使用したとしてもこれにはTステップかかり、並列処理によって計算が高速化することはない。
  • 検証
    検証アルゴリズムは(p, x, y, proof)を入力として、yがVDFの正しい評価かどうか迅速に示す。

の３つのアルゴリズムがある。

安全性

VDFには２つの安全性要件がある。

  • 一意性
    任意の値xが与えられた場合、検証者を納得させる値yは１つだけ存在する。同じyに対して異なるプルーフを持つことができるが、yは１つだけ。
  • シーケンシャル性
    敵対者が並列マシン、特に多項式個数のプロセッサを使っている場合でも、時間Tを費やさない限り、VDFの出力が完全にランダムに見える。

分散環境においてランダム値を生成しようとした場合、参加者はそれぞれランダム値を計算し、それを掲示板に貼り、ランダム値はその全てのXORで生成される。この場合、最後の参加者が最終的な生成値を制御できてしまう。これを防ぐために事前にランダム値のハッシュ値をコミットメントとして提出させる方法が考えられるが、コミットメントが提供された後ランダム値が提供されなかった場合、プロトコルは停止する。公開されなかったコミットメントは無視するというのは安全ではないからだ。

そこで分散環境におけるランダム値の生成にVDFを導入し、VDFの出力値をランダム値とする。なぜこれが可能で偏りのないランダム性になるのか？というと

全員が正午までにランダム値を送信し、特定の時間になるとそれがプロトコルの参加者になる。VDFは送信時間帯よりも長くなる。VDFのシーケンシャル特性は、VDFを計算するためには送信時間よりも時間がかかるため、最後の送信者がプロトコルへ多くの入力と試行できないこと保証する。 gallium-arcinide ASICなどの最新技術を持っていたとしても、時間がかかることを確実にする必要がある。

シーケンシャル特性により最後の参加者は出力にバイアスをかけられなくなる。バイアスをかけるためには多くの時間を必要とするため。また、一意性により出力に曖昧さがないことが保証される。シーケンシャル特性と一意性によってVDFは困難になる。

VDFの構築方法

VDFを構築するにあたっては以下のような構築方法がいくつか挙げられている。

ハードウェアEnclave

VDFを構築するのにとても簡単なのはハードウェアEnclaveを使う方法。Enclave内に暗号鍵を保存し、その鍵を使ってVDFを生成する。この場合、公開パラメータは公開鍵暗号の署名、つまり公開鍵は公開される。入力が入るとEnclaveは時間遅延を強制し、入力XのHMACもしくはPRFを生成し、出力に署名してVDFがハードウェアによって正しく計算されたことを証明する。ハードウェアEnclaveがあればVDFの構築は非常に簡単になる。しかしHMACを生成する際の秘密鍵が盗まれると、VDFの時間外で誰もが即座に結果を計算することができてしまう。

そのため、Enclaveの保護が重要だが、十分な資金があればこのハードウェアEnclaveを破ることは可能と思われ、プライバシーやデータ保護には問題がないが、コンセンサスを破ることが資金の損失に繋がるコンセンサスに採用するのは危険になる。

ハッシュ関数

ハッシュ関数を利用してもVDFを構築することはできる。この場合、公開パラメータはSNARKのパラメータで、VDFはSHA256を繰り返し評価するのに時間Tかかるハッシュチェーンとして定義される。しかし、出力が正しく計算されたかどうか検証するためにSNARKが登場する。しかしこれを正しく動作させることは難しい。プルーフはハッシュチェーンが正しく計算されたことのSNARKだが、SNAKRの計算にはチェーンの計算よりも時間がかかるため、それに対処する必要がある。

その対処として考えられているのが検証をSNARKのプルーフの検証にするというもので、最近、Recursive SNARKs（= SNARK内でSNARKのプルーフの検証を行う仕組み）として研究が行われている。SBC20の「Fractal: Post-Quantum and Transparent Recursive Proofs from Holography」のセッションでは、Recursive SNARKsを効率的に実現するための量子耐性を持つ新しい方法としてFractalというプロトコルが提案されている。

置換多項式

置換多項式からVDFを構築するというアイディアもあるっぽい。置換多項式は、有限体の元との置換多項式で、有限体内の２点x, yについて多項式f(x)がf(y)と等しくならないもの。この構造で使用する特性は、多項式の根*1を見つけること。VDFの入力は値xで、xと等しくなるようなf(y)の値yを求める。そのようなf(y)を見つけたい場合、多項式f - xの根を見つけることになる。この根を見つけるための実用的な方法は、シーケンシャルに行われるGCP（Generalized Characteristic Polynomial）計算となり、VDFに使えるのでは？とされている。

課題はショートカットがなくGCP計算が最良の計算方法である置換多項式があるかどうで、まだ研究がされてないっぽい？

代数的構成

代数的な構成では、有限巡回群Gから始まり、群Gの位数は不明、つまり群に含まれる要素の数を誰も知らないという仮定を持つ。公開パラメータは群へのハッシュ関数。VDFはxを入力として受け取り、群にハッシュし、出力yを以下のようにT回の平方演算を求める。

{y = H(x)^{2^{T}}}

これは時間の証明やtimelock puzzlesなどで使われており、この種の関数はよく使われる。

こうやって生成された出力が正しいかどうかの検証proofs of exponentiationを行う必要がある。これについてはサーベイ論文で解説されてるっぽい。

↑で群の位数が不明と書いたが、群の位数がもし分かっていると、例えばDとすると、 {2^{T} \mod D}を計算でき小さな冪乗になり評価は簡単になる。VDFとしては、群の位数が分かればTは対数時間まで加速するため、群の位数は不明でなければならない。

未知の位数の群をどうやって生成するか？

既知の位数の群でVDFを構成した場合、安全はなくなるため、未知の位数を持つ群を生成する必要があるが、まずこれをどうやって生成するのか？

１番最初に思いつくのがRSA。２つの整数pとqを選択し、それらを乗算する（n = p * q）と因数分解出来ない限り群の位数は不明になる。この因数分解を知っていれば群の位数を知っていることになるので、誰も因数分解を知らない方法でこれを構築する必要があり、そのためにTrusted Setupが必要になる。また十分大きなnにする必要があり、30,000-40,000ビットほどの大きさである必要がある。

RSAの問題はこのTrusted Setupが必要なことで、RSAモジュラスが２つの巨大な素数の因子からなり、その因数分解を誰も知らないことを誰もが確信するように生成するプロトコルが必要になる。

この辺りの研究は、SBC20でも「Scalable RSA Modulus Generation with Dishonest Majority」として取り上げられている。

Class Group

未知の位数を持つ群のもう１つの候補で注目されているClass Groupだ。Class Groupというのは1990年代に提案された暗号プリミティブだが、まだ実際に展開されたことは無い。Class Groupは素数で指定された群を持ち、その素数が1000ビットのように大きな値の場合、その群の位数を計算する方法を誰も知らないという特徴がある（なぜそうなるのか、どういうものなのか詳しくは知らない）。

これにより素数を選択することで未知の位数の群を入手し、VDFに使用できるということらしい。利点としてRSAで必要だったTrusted Setupを必要としない。ネックになるのはRSAよりClass Groupの演算の方が遅いのと、Class Groupの演算がどれくらい並列化できるものなのかがはっきり分かっていない点にある。

尚、現状代数学的なアプローチは量子耐性はなく、量子耐性を持つのはハッシュベースの構成だが、これはRecursive SNARKsを必要とする。

といずれも現在進行系でそれぞれに一長一短があり、さまざまな研究が進んでいる。

*1:p(x) = 0となるようなx