前に、XYM を EVM に持っていくブリッジを作った。その記事の最後で、「ちゃんとやるなら、鍵を配るディーラーをなくして DKG にしたい」「Symbol のチェーンの上で DKG することになる」と書いた。
で、後回しにして、後回しにして、後回しにして、結局やった。Symbol を掲示板にして、誰も鍵の全体を一度も知らないまま、5 人で鍵を分けて作った。参加者のやりとりは、全部 Symbol のメッセージに載せた。Symbol のハードフォークはいらない。いつものやつである✨
さらに、その鍵で誰も秘密鍵を知らない預かり口座を作り、委員会の入れ替えまでやった。入れ替えはトランザクション 1 つで、預かった XYM は 1 ミリも動かしていない。いいじゃなぁい🎉
試作なので、参加者は全員 1 つのプロセスの中にいて、分け前もメモリにしかない。今回も、5 人のふりをした 1 人、そう私と Claude Code である。主に Claude Code である。相変わらずさみしい🥲 一応本物の資産は預けないであげてね💦 預けるためにやってるのは違いないんだけど……。
DKG ってなに
閾値署名では、鍵をたくさんの分け前に分けて配り、決まった数が集まったときだけ署名できるようにする。前の記事までは、この「分けて配る」をディーラーがやっていた。ディーラーは配る前の一瞬だけ、鍵の全体を知っている。ディーラーを信頼するくらいなら、最初からカストディアンを信頼すれば済む。それでは分散型とは言いにくい。だってディーラーが裏切ったらそこで試合終了なんだもん。
DKG（分散鍵生成）は、ディーラーなしで、参加者どうしのやりとりだけで鍵を分けて作る。ざっくり言うとこうだ。
- 参加者はそれぞれ、自分だけの秘密を作る
- その秘密を分け前にして、ほかの参加者全員に 1 つずつこっそり渡す
- 同時に、「私が配った分け前は、ちゃんと 1 つの秘密から作ったものです」と後から確かめられる約束を、全員に見える場所に出す
- 最後に、自分がもらった分け前を全部足すと、それが自分の鍵の分け前になる
グループの秘密は、全員の秘密を足したものになる。でも、誰も全員の秘密を知らないので、誰もグループの秘密を知らない。グループの公開鍵のほうは、みんなの約束から誰でも計算できる。
……と書くと簡単そうだが、例によって私は中身の高度な数学はよくわかっていない。例によって足し算の気配だけ感じる✨ 今回も計算は Zcash Foundation の frost-core に丸投げしている。依存ライブラリの責務なので許してほしい💦
DKG に要るもの：全員に同じものが見える掲示板
DKG で本当にむずかしいのは、計算ではなく、「誰の配ったものを採用するか」を全員で一致させるところだ。
ネットワークは、メッセージが届く順番を保証してくれない。A さんには届いたけど B さんには届いていない、が普通に起きる。人によって見えているものが違うと、人によって違う鍵ができてしまう。非同期の DKG は、これを解くために、中に合意の仕組みを抱えている。重いのやだ。
ここで Symbol である。前のロールアップの記事でも書いたが、Symbol はあとから間に差し込めない掲示板だ。ファイナライズされたブロックを読めば、全員が同じものを同じ順番で見る。
なので、教科書に載っている「全員に同じものが届くチャネルがある前提の DKG」が、そのまま使える。
- 締め切りは、ブロックの高さで決める。「高さ h までに載ったもの」は、誰が読んでも同じ
- 同じ人が同じことを何度載せても、最初の正しいものだけを使う
- 何を採用するかは、掲示板だけで決まる。参加者の手元の状態には頼らない
ブリッジの記事で「珍しく Symbol がああいう仕様でよかった、という回になりそう」と書いたが、本当にそうなった。ファイナライズがあって、誰でも書けて、あとから変えられない。DKG のためにあるような掲示板である。いつもニコニコすんぼる払い✨
載せるもの
1 回の DKG（セッション）の掲示板は、セッションの ID のハッシュを公開鍵の代わりにして作ったアドレス（受け箱）だ。誰も秘密鍵を持っていない。ここに転送のメッセージで、次のものを順に貼っていく。
- 始める：しきい値と、参加者の公開鍵の並び。中身のハッシュがセッションの ID なので、ID を知っている人は、中身が本物か確かめられる
- 約束する：さっきの「約束」と、自分宛ての分け前を暗号化してもらうための公開鍵
- 配る：ほかの参加者それぞれに宛てた分け前。宛先の公開鍵で暗号化して、全部まとめて 1 つに載せる
- 苦情を言う：届いた分け前が約束と合わなかったら、その配り手に苦情を言う
- 明かす：苦情を受けた配り手は、その人宛ての分け前を平文で出す
始める以外は、参加者が自分の鍵で署名する。なので、掲示板に載せるのは誰でもいい。この例では、手数料を払う中継役がまとめて載せている。中継役が意地悪して載せてくれなくても、参加者は自分で手数料を払って載せればいい。
分け前の暗号化には、Symbol の暗号化メッセージは使わなかった。あれは送り主と宛先の 2 人の間の暗号なので、「中継役が、5 人分の宛先の分け前を 1 つにまとめて載せる」には合わない。代わりに、試すたびに使い捨ての X25519 の鍵を作り、組ごとに別の鍵で ChaCha20-Poly1305 をかけている。ふつうの組み立てである。
苦情と明かし
分け前は暗号化して載せるので、正しいかどうかは受け取った本人にしかわからない。じゃあ、壊れた分け前を配る不届き者がいたらどう成敗致すのか。
答えは、苦情を受けたら、平文で明かしてもらう。
- 明かした分け前は、誰でも約束と照らし合わせられる。合わなければ、配り手が悪い。外す
- 合っていれば、配り手は外さない。苦情を言った人は、明かされた分け前を使う
- 明かさなかったら、外す
暗号文が壊れていたのか、苦情が嘘なのかは区別しない。どっちでも、明かされた分け前で先に進める。嘘の苦情で明かさせられるのは、苦情を言った本人宛ての分け前だけなので、困るのは本人だけだ。
それと、しきい値以上の人から苦情を受けた配り手は、明かさせずに外す。不正をする人がしきい値より少ない限り、それだけの人が苦情を言っているなら中に必ず正直な人がいるので、配り手が悪いのは確定だ。それに、しきい値の数だけ分け前を明かすと、その配り手の秘密が丸見えになってしまう。
誰かを外したら、残った人で最初からやり直す。正直な人は外されないので、やり直すのは不正をした人の数までで済む。
確立された手法はいじりたくない
ここまでの手順は、自分で考えたものではない。Gennaro たちの DKG（Joint-Feldman と呼ばれる形）そのままである。……と言い切るために、ちゃんと読んだ、Claude Code が🫠 原本はペイウォールの向こうだったので、分散乱数ビーコンの SoK（eprint 2023/728）の付録にある説明で確かめた。「t 件より多い苦情を受けたら失格。そうでなければ、苦情を出した人宛ての分け前を明かす」と、そのまま書いてあった（ここの t は不正をする人の上限で、しきい値より 1 少ない数なので、「しきい値以上」と同じ規則だ）。よかった。
暗号のプロトコルは、ちょっと変えただけで安全性の証明が効かなくなることがある。なので、変えたところは README にはっきり書いた。
- 誰かを外したら、最初からやり直す。元の手順は、外した人の分を除いて、そのまま進む
- 全員が載せたら、締め切りを待たずに段階を閉じる
どちらも「いつ、誰の分で計算するか」の話で、計算の中身には触っていない。計算は全部 frost-core のままだ。
預かり口座：DKG を 2 回、片方でもう片方を 1-of-1
ブリッジの記事では、預かり口座を「使い捨ての鍵で作って、グループ鍵だけを連署者にしたマルチシグにして、使い捨ての鍵は捨てる」で作った。でも、使い捨ての鍵も、捨てるまでは誰かが知っている。
今回は、その使い捨ての鍵も DKG で作った。
- DKG ①：預かり口座の鍵を作る
- DKG ②：委員会の鍵を作る
- 預かり口座を、②だけを連署者にした 1-of-1 のマルチシグにする。①は預かり口座として、②は加わる側の同意として連署する
- これで①の鍵は、もう何にも使えない
4 がポイントで、catapult は、連署者のいるアカウントが自分で署名したトランザクションを弾く（MultisigPermittedOperationValidator）。なので、①の分け前があとで全部漏れても、預かり口座は動かせない。誰も秘密鍵を知らないまま生まれて、一度だけ署名して、そのまま役目を終える鍵である。もののあはれである。
委員会の入れ替えは、トランザクション 1 つ
委員会が入れ替わるときは、新しい委員会の鍵（③）を DKG で作り、連署者を②から③に差し替える。
ここで気になったのが、「足すのと外すのを、1 つのトランザクションでできるのか」だ。catapult のソースを読んだら、なんかできた。
- 足す人と外す人は、同じトランザクションの別のリストに書ける。足すのと外すのを同時にすること自体は止められていない。1 つのトランザクションで外せるのは 1 人までだが、入れ替えには 1 人で足りる
- 外すのを含むと、連署の数は「削除の最小数」で数える。1-of-1 なら②の連署 1 つで足りて、外される側の同意はいらない
- 足す③は、加わる側の同意として連署する
FROST にも、公開鍵を変えずに分け前を配り直す仕組み（resharing）はある。でも、古いメンバーが古い分け前を捨てずに持っていたら、しきい値の人数が集まれば今でも署名できてしまう。「ちゃんと消した」と信じるしかない。連署者の差し替えなら、古い委員会はチェーンのルールで締め出される。代わりに、入れ替えのたびにトランザクションが 1 つ要るし、入れ替えたことはチェーンから見える。
ちなみに、作っている途中で「DKG なのに、自分の分け前を公明正大に一般公開する不届き者は考慮するの？」という疑問が浮かんだ。DKG では防げない。その人は「不正をした 1 人」に数えるしかない。ただ、漏れた値が誰の分け前かは、掲示板から計算できる参加者ごとの公開鍵と照らせば一発でわかる。言い逃れはできない。あとは、その人を抜いた委員会を作り直して、漏れがしきい値に届く前に差し替えればいい。公明正大の代償は大きいのである😇
動かしてみた
heika（自作の Symbol の Rust のツールキット。試験的にノードも動く）4 台のプライベートネットで、DKG を 3 回して、預かり口座を回した。参加者は各 5 人で、署名に要るのは 3 人だ。それぞれに 1 人ずつ、わざと悪いことをする人を入れた。
- ①：1 人が壊れた分け前を配る。苦情を受けて、正しいものを明かす
- ②：1 人が壊れた分け前を配る。苦情を受けても、明かさない
- ③：1 人がずっと黙っている
[① 預かり口座] 試み 0: 参加者 2 が、参加者 4 からの分け前に苦情を言いました
[② 委員会] 試み 0: 参加者 1 が、参加者 2 からの分け前に苦情を言いました
[① 預かり口座] 試み 0: 参加者 4 が、参加者 2 宛ての分け前を明かしました（コミットメントと合っています）
[① 預かり口座] 高さ 21448 で鍵ができました: T…
[② 委員会] 試み 0: 参加者 2 を外します（苦情を受けて、正しい分け前を明かしませんでした）
[② 委員会] 高さ 21459 の次から、残った人でやり直します（試み 1）
[② 委員会] 高さ 21492 で鍵ができました: T…
高さ 21502 で、預かり口座 T… を、②だけを連署者にしたマルチシグにしました（2.000000 XYM を入れました）
①の鍵で預かり口座から送ろうとすると、弾かれました: Failure_Heika_Rejected_When_Harvesting
[③ 新しい委員会] 試み 0: 参加者 5 を外します（締め切りまでに約束しませんでした）
[③ 新しい委員会] 高さ 21524 の次から、残った人でやり直します（試み 1）
[③ 新しい委員会] 高さ 21564 で鍵ができました: T…
高さ 21575 で、預かり口座の連署者を②から③に差し替えました（預かった XYM は動かしていません）
②で預かり口座から送ろうとすると、弾かれました: Failure_Heika_Rejected_When_Harvesting
高さ 21577 で、③が預かり口座から 1.000000 XYM を送りました
全部ねらいどおりに動いた🎉 ①は誰も外れずに、②と③は悪い人を外してやり直して、鍵ができた。差し替えたあとは、②では動かせず、③では動かせる。
それと、参加者でない人が、セッションの ID だけを手がかりに掲示板を読んで、同じ鍵にたどり着けることも確かめた。掲示板を読めば、誰が苦情を言って、誰が外されて、どの鍵ができたかまで、全部同じように再現できる。外から検算できる DKG である✨
最初は差し替えで弾かれた
……と、すんなりいったように書いたが、最初に流したときは、最後の差し替えで弾かれた。ノードのログには「アグリゲートの連署者 T… は要りません」。
原因はこうだ。catapult は、アグリゲートの署名者も、連署者の 1 人に数える。そして連署者はみな、中のどれかのトランザクションに要る人でないといけない（MultisigAggregateEligibleCosignatoriesValidator）。手数料を払う中継役がアグリゲートに署名していたのに、中では何もしていなかったので、「要らない子」になっていた。
直し方は、Symbol をよく触っている人ならおなじみの名物、何も transfer しない transfer である。中継役から中継役への、モザイクもメッセージもない転送を 1 つ入れて、中継役も「大事な要る子」にした。ちゃんと規則どおりに弾いてくれた heika、えらい。弾かれた理由が、catapult みたいな細かい名前ではなく Failure_Heika_Rejected_When_Harvesting という雑な名前なのは、また今度気が向いたら直す🫠 かもしれない。
締め切りまで待つと遅い
もう 1 つ。最初の版は、どの段階も締め切りまで待っていた。このプライベートネットは、ファイナライズが先端から 10 ブロックほど遅れる。参加者はファイナライズされたものを見てから動くので、1 段階に 20 ブロック取っていた。①だけで 80 ブロック、②は 140 ブロックかかった。そんなにかかるんだ……😇
なので、全員が載せたら、締め切りを待たずに次の段階に進むようにした。「全員が載せた」も掲示板から読めるので、誰が読んでも同じ結論になる。苦情の段階だけは、「苦情がない」ことが掲示板に出ないので、苦情がなくても「苦情なし」を載せてもらうことにした。
これで、①は 45 ブロック、②は 89 ブロックになった。全員が正直な段階は、ほぼファイナライズの遅れの分だけで進む。締め切りまで待つのは、黙っている人がいる段階だけだ。
気をつけるところ
- 締め切りに間に合わないと外される。チェーンが混んで、正直な人の載せたものが締め切りに入らないと、その人は外される。1 段階の長さは、ファイナライズの遅れと混み具合を見込んで決める
- 変な点は入口で弾く。Ed25519 の曲線の点には、小さいおまけの成分が混ざったものがある。約束にこれを混ぜられると、グループ鍵にずっと残って、catapult ではたまにしか署名が通らない委員会になる。直すには DKG をやり直すしかない。なので、掲示板から読む点は、frost-ed25519 の読み方で、おまけの混ざっていないものだけを受け付ける
- 誰を参加者にするかは決めていない。参加者は、始めるものを載せた人が決める。勝手に入ってくる人を防ぐ仕組みはない
- 耐量子にはしていない。DKG でできる鍵がどうせ Ed25519 なので、量子計算機があれば、公開されているグループ鍵から秘密鍵のスカラーを計算できる。分け前の暗号化だけ耐量子にしても、余分なロマン案件でしかない
おわりに
DKG に要るのは、「全員に同じものが見える掲示板」と「1 人ずつに秘密を届ける手段」だった。掲示板は Symbol のファイナライズがそのままくれた。秘密を届けるのは、掲示板の上でも暗号化すれば済んだ。新しく持ち込んだのは、DKG と、分け前のふつうの暗号化くらいである。
そして、DKG を 2 回して片方でもう片方を 1-of-1 にすると、誰も秘密鍵を知らない預かり口座ができて、委員会の入れ替えもトランザクション 1 つで済む。ROAST の記事で「マルチシグは 25 人まで」とさんざん言ったのに、今回もマルチシグに助けられた。今日も手のひらくるくる旋盤の如しである🤑
これで、ロールアップのブリッジの引き出し側に要る委員会が、ディーラーなしで作れるようになった。入金はロールアップの規則で数えればいいので、委員会がいるのは引き出しだけだ。あとはつなぐだけ……と言うのは簡単である😇 そう、ただでさえぼっちが DKG しても何も分散型にならないのである。めでたしめでたし（めでたいとは言っていない）。