FROSTを利用したマルチシグの設定変更

FROSTはSchnorrベースの閾値署名方式で、プロトコルの内容については過去の記事↓やGBEC動画参照。

techmedia-think.hatenablog.com

このFROSTを利用してBitcoinでマルチシグウォレットの開発を進めているFrostsnapというプロジェクト↓

https://frostsnap.com/introducing-frostsnap.html

の説明の中で、

With FROST you can add or remove signers after key generation while keeping the key the same. FROSTを利用すると、鍵生成後に同じ鍵のまま署名者の追加/削除ができる。

とあったので、具体的にどうやるのか調べてみた。

FROST

マルチシグの参加者数をn、閾値をtとして↑の記事に書いた分散鍵生成を実行すると、各参加者 ${P_i}$ は、秘密鍵のシェア（定数項 ${a_{i, 0}}$ ）が含まれる多項式

${f(x)_i = a_{i, t-1}x^{t-1} + a_{i, t-2}x^{t-2} + ... + a_{i, 0}}$

を保持し、各係数に対して楕円曲線上のベースポイントを乗算したコミットメント ${a_{i, j}G}$ のリストを他の参加者と共有している状態になる。

また、他の参加者向けに、各参加者のIDで多項式を評価した結果 ${(ID, f(ID)_i)}$ をシェアとして送信し、各参加者は他の全参加者の多項式のシェアを保持している状態になる。

マルチシグの公開鍵は、全参加者の秘密鍵のシェア ${a_{i, 0}G}$ を合算した点＝ ${P = \sum_{i=1}^{n}a_{i, 0}G}$ になる。

署名生成フェーズでは、↑のシェアを利用して多項式補間を実行して最終的に有効なSchnorr署名を生成する（詳細なプロトコルについては、↑の記事or動画参照）。

FROSTを利用したダイナミックなマルチシグ設定

Frostsnapのリポジトリをみたところ、それっぽいプロトコルの説明はなかったけど、FrostsnapチームのNickのGistにそれっぽい説明があった↓

https://gist.github.com/nickfarrow/64c2e65191cde6a1a47bbd4572bf8cf8

署名者の削除

n人のマルチシグ参加者から、1人削減する（t of nからt of n - 1に変更する）場合。削除されるユーザーがその後の署名プロセスに関与できないようにする必要がある。

この場合、n - 1人で再度シェアを生成し直す。この時、各参加者が保持する元のマルチシグの公開鍵Pに対して有効なシークレットシェアは変わらないようにする必要がある。これは分散鍵生成において、各参加者が再生成する多項式の定数項（ ${a_{i, 0}}$ ）については元の値を使用し、それ以外の項の係数は新たに生成しなおし、更新した多項式で生成したシェアを他の参加者に配布することで実現できる。

この場合、n - 1人の参加者が保持する各参加者のコミットメント値およびシェアの値は異なるものになるが、元の公開鍵Pに対して有効なシークレットシェアは有効なままになる。

上記のようにシェアを定期的に再生成するようなプロアクティブな秘密分散法を用いると、シェア更新後は古いシェアを攻撃に使うことはできなくなる。

閾値の削減

続いて、閾値tを削減する（t of nからt - 1 of n - 1に変更する）場合。

この場合は、削除する参加者のシークレットシェアを他の全参加者に開示する。各参加者はそのシェアを使って署名シェアを作成する。

※ nを減らさずにtだけ減らす場合、つまりt - 1 of n - 1ではなくt - 1 of nにする場合は、後述する方法で署名者を新たに追加する必要がある。

この方法の場合、削除対象の参加者のシークレットシェアが必要になるため、デバイスの紛失などでシークレットシェア自体にアクセスできないようなケースでは機能しない。

署名者の追加

署名者を追加して、n + 1にする（t of nからt of n + 1に変更する）場合は、削除より少し複雑になる。↑のGistでは、二通りの方法が説明されている：

Repairable Threshold Scheme

１つめは、シェアの修復を可能にする修復可能な閾値スキーム（Repairable Threshold Scheme＝RTS）の一種を利用するアプローチ↓

techmedia-think.hatenablog.com

フラグメントの共有

もう1つの方法は、予め決めた数（kとする）だけ後から署名者を追加するアプローチ。

鍵生成プロセスにおいて、各参加者は生成した多項式を使って、通常n個のインデックスに対してn個をシェアを作成する代わりに、n + k個のシェアを作成する。つまりk個の追加のシェアを計算する。このk個の追加シェアは後から署名者を追加するのに使用される。
各参加者はk個の追加シェアに対して、閾値tでシャミアの秘密分散法を用いて、n個のフラグメントを生成する。つまり、k × n個のフラグメントが生成される。そして生成したフラグメントを他の参加者と共有する。
新しい参加者（インデックスをn + 1とする）を追加する場合、t人の参加者が対象のインデックス（n + 1）に属するすべてのフラグメント送信する必要がる。結果、n × t個のフラグメントが集められたら、それらから新しい参加者用のシークレットシェアが作成できる。

閾値tを増やす

閾値tを増やす場合は、各参加者が生成する多項式の次数を増やし、全員が古い多項式を削除することを信頼する必要がある。次数を増やした多項式を生成するのは↑の署名者の削除と同様のアプローチでできそうだけど、後者のトラストポイントは残ってしまう。

というのが、FROSTを利用したマルチシグの設定変更の概要みたい。まだ実装や安全性の評価は行われていないようなので、利用可能になるまではまだ時間がかかると思われるけど、暗号技術だけでマルチシグの設定が変更できるというのは、おもしろい技術だ。マルチパーティでUTXOを共有するようなプロトコルでも、活用できるかも？

Develop with pleasure!

福岡でCloudとかBlockchainとか。