Develop with pleasure!

福岡でCloudとかBlockchainとか。

OP_CODESEPARATORは廃止の流れか？

Bitcoin

Bitcoin開発者の１人であるMatt Coralloが提案するコンセンサスルールのクリーンナップ↓

https://github.com/TheBlueMatt/bips/blob/cleanup-softfork/bip-XXXX.mediawiki

まだBIPにはなってないが、このクリーンナップの内容の１つがOP_CODESEPARATORの廃止だ。

OP_CODESEPARATORとは？

OP_CODESEPARATORはあまり見かけることがないopcodeの１つだが、これはOP_CHECKSIGで署名検証する際にscriptPubKeyの一部だけをチェックするために使われる。

署名検証の手順

例えば通常OP_CHECKSIGの署名検証は以下の手順で実行される。

  1. 公開鍵と署名データがスタックからポップされる。
  2. この時署名のフォーマットはDER形式で、署名データの最後にはSIGHASH_TYPEの値が付与されている。
  3. 署名からSIGHASH_TYPEを取り除き、保持する。
  4. 現在のトランザクションをコピーしたtxCopyを作成する。
  5. コピーしたtxCopyの全インプットのscriptSigを空にする。
  6. 署名検証対象のtxCopyのインプットに、subScript（後述）をセットする。
  7. SIGHASH_TYPEの値によってtxCopyの内容を調整する。
  8. txCopyをシリアライズし、double-SHA256する。
  9. 生成したハッシュ値とスタックからポップした公開鍵を使って署名の検証を行う。

subScriptとscriptCode

OP_CODESEPARATORが関連してくるのは、↑の手順6で出てくる該当インプットにセットするsubScriptの部分。subScriptは実際に実行されたコード = scriptCodeから作成される。

scriptCodeは、

  • 非Segwitの場合
    • P2SH以外はscriptPubkeyそのもの
    • P2SHの場合はそのredeem script
  • Segwitの場合
    • P2WPKHの場合は、witness programをP2PKHスクリプトに変換した0x1976a914{20-byte-pubkey-hash}88ac
    • P2WSHのの場合は、witness script = Segwitにおけるredeem script

となる。ほとんどの場合、scriptCodeがそのままsubScriptになるわけだが、scriptCodeのスクリプト内にOP_CODESEPARATORが含まれている場合だけ勝手が違ってくる。

OP_CODESEPARATORの作用

スクリプトにOP_CODESEPARATORが含まれる場合、最後にパースされたOP_CODESEPARATORからスクリプトの最後までがsubScriptになる。

例えば次のようなOP_CODESEPARATORを３つ含むscriptCodeがあった場合、

[スクリプトパート１] OP_CODESEPARATOR [スクリプトパート２] OP_CODESEPARATOR OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG OP_CODESEPARATOR [スクリプトパート4]

スクリプトインタプリタがOP_CHECKSIGを評価する際、最後にパースしたOP_CODESEPARATORは２つめのOP_CODESEPARATORになるため、それ以降のスクリプト↓がsubScriptになる。

OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG OP_CODESEPARATOR [スクリプトパート4]

そして、subScript内のOP_CODESEPARATORは全て除去されるため、最終的なsubScriptは

OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG [スクリプトパート4]

となり、これが署名対象のSignature Hashを生成する際のトランザクションのインプットにセットされることになる。

※ 但し、BIP-143が適用されるSegwitスクリプトでは、subScript内の全OP_CODESEPARATORの削除は行われない。

OP_CODESEPARATORの用途は？

OP_CODESEPARATORの動作は分かったとして、この複雑な機能はいったい何のためにあるのか？という疑問が湧き、2011年にbitcointalkでスレッドが立つも有用なユースケースは見つかっていない。

bitcointalk.org

コメント頂きました。

アリスが、ボブが支払い条件を満たすトランザクションを公開しBOB_HASHのプリイメージを取得したい以下のようなスクリプトを考える。

OP_DEPTH 3 EQUAL
OP_IF
    2 <ALICE_KEY_PAYMENT> <BOB_KEY_PAYMENT> MULTICHECKSIGVERIFY HASH160 <BOB_HASH> EQUAL
OP_ELSE
    <ALICE_KEY_REDEEM> CHECKSIG CLTV DROP
OP_END

ただ、<ALICE_KEY_PAYMENT>と<ALICE_KEY_REDEEM>の鍵が同じであった場合、ボブはBOB_HASHのプリイメージを公開することなくアリスの署名を使ってコインを入手できるためよろしくない。

↑のスクリプトをOP_CODESEPARATORを使うことで以下のように変更することができる。

<ALICE_KEY>
OP_DEPTH 3 EQUAL
OP_IF
    OP_SWAP <BOB_KEY_PAYMENT> CHECKSIGVERIFY HASH160 <BOB_HASH> EQUAL OP_CODESEPARATOR
OP_ELSE
     CLTV DROP
OP_END
CHECKSIG

↑のスクリプトでは<ALICE_KEY_PAYMENT>と<ALICE_KEY_REDEEM>が同じ<ALICE_KEY>として扱われるが、OP_IFの分岐とOP_ELSEの分岐でアリスが提供する署名は、OP_CODESEPARATORにより署名対象のトランザクションダイジェストの値が変わるため、最初のスクリプトのようにボブが不正をできなくなる。

結果、アリスがOP_IFとOP_ELSE分岐で同じ公開鍵を使用することで公開鍵1つ分（＝33バイト分）スクリプトデータを削減することができる。というのがOP_CODESEPARATORの用途として提案されている。

実際、上記の提案では、SegwitのスクリプトでOP_CODESEPARATORが利用できれば問題ないということで↓の非標準化は実現された。また、このユースケース自体はスクリプト全体を公開することなく、スクリプトの実行ブランチのみを公開する）MASTが利用可能になれば代替可能になる。

Bitcoin Core 0.16.1以降は非標準に

Bitcoin Core 0.16.1では以下のプルリクにより、非Segiwtなスクリプトにおいて、スクリプト内にOP_CODESEPARATORが含まれている場合、非標準トランザクションとみなし、リレーされなくなる。

github.com

そのため、現在標準トランザクションとしてOP_CODESEPARATORが利用できるのは、SegwitのP2WSHもしくは、PS2SH-P2WSHのみ。

OP_CODESEPARATORの弊害

↑のようにOP_CODESEPARATORを使うと署名対象のSignature Hashのデータを変更することができるため、大量の署名操作と共に悪用すると署名検証にえらい時間がかかるトランザクションを作成することが出来てしまう恐れがある（最悪３０分とか）。

Bitcoin Core 0.16.1によりリレーされにくくなったとは言え、有用な用途もなく悪用される可能性のあるopcodeは廃止しようという流れだ。

本当に廃止される？

Bitcoin Core 0.16.1以降では非標準トランザクションとして判定されるものの、コンセンサスルールでは許可されてるため、廃止するにはソフトフォークが必要になる。OP_CODESEPARATORに限らず、Matt Coralloのクリーンナップの提案には無効なSIGHASH_TYPEを無効判定にするなどの提案もある。これらを有効化した場合、まだブロードキャストされていないが、それらの条件を使用した署名済みのトランザクションが保持されていて、かつその署名を作成した秘密鍵にアクセスすることができなくなってしまっている場合にコインを喪失する懸念がある。このようなユーザーがいる場合、ソフトフォークがアクティベートした後はそれらのトランザクションがブロックに取り込まれなくなるため、資金は永遠に失わえる。

そういった懸念から、OP_CODESEPARATORの数をトランザクションweightに加味するようなソフトフォークにした方がいいのでは？という提案もあるが、これをどう判断しBIPとするか課題は残る。

Grinで作るAtomic Swapとアウトプットへのタイムロック条件の適用

Grin Mimblewimble

techmedia-think.hatenablog.com

について整理したので、今回は応用編ということでAtomic Swapや、タイムロックの仕組みをアウトプットと組み合わせた（BitcoinのOP_CLTV使うようなイメージ）条件付きのタイムロック支払いのコントラクトの構成方法についてまとめる。

Atomic Swap

異なるチェーン間でコインをトラストレスに交換するAtomic Swapプロトコルには、よくHTLCｓが使われるが、Mimblewimbleにはスクリプトは無いので、Adaptor Signatureを利用して以下のように実現する。

アリスがgrinを持ってて、ボブがbitcoinを持ってて、それぞれを交換するケースを考える。まずボブはBitcoinのトランザクションを作成し以下のいずれかの条件でコインをアンロックできるロックスクリプト宛にコインを送る。

  • アリスがハッシュのプリイメージxを知っていれば、アリスの署名でアンロック可能
  • 時間がTb経過したらボブの署名でアンロック可能

ただこの時、ハッシュ関数を使うのではなく、代わりにx*Gを使う。つまりスクリプトは以下のような形式になる。

OP_IF
  2 <アリスの公開鍵> <x*G> 2 OP_CHECKMULTISIG
OP_ELSE
  <有効期間> OP_CLTV OP_DROP <ボブの公開鍵> OP_CHECKSIG
OP_ENDIF

続いてアリスは、ボブがxを明らかにしたらgrinをボブが入手できるようGrinのブロックチェーン上でセットアップする。

  1. アリスは最初に自分が持っているgrinを、↑のマルチパーティ＋タイムロック付きトランザクションを作成しそこに送る。この時払い戻しトランザクションはアリス宛で、その時にセットするタイムロックはTa < TbとなるようなTa。
  2. アリスはこのトランザクションをブロードキャストし、コインを2-of-2のマルチシグにロックする。

続いて、交換プロセス。

  1. アリスはランダムなnonce ksを選択し、アリスのランダムファクターの合計rsを計算し、ks*Gとrs*Gをボブに送る。
  2. ボブはコインを受け取るのに使うランダムなブラインディングファクターrrとランダムなnonce krを選択する。ここで単純にsr = kr + e*rrを計算するのではなく、sr' = kr + x + e * rrを計算しsr``とkrG、rrG、x*G`をアリスに送る。
  3. アリスはsr'*G = kr*G + x*G + e*rr*Gが成立するか検証する。そしてボブがBitcoinのチェーンでコインをx*Gにロックしているか検証する。
  4. 検証が成功したらアリスは自身の署名値ss = ks + e*rsを計算し、ボブに送る。
  5. ボブは署名を完成させるため、sr = kr + e*rrを計算し、最終的な署名(sr + ss, kr*G + ks*G)を完成させる。
  6. ボブはトランザクションをブロードキャストしgrinを手に入れる。アリスはそのトランザクションの署名値sr + ssからsrを入手し、前にボブから受け取ったsr'を使って、sr' - sr = xを導出する。
  7. アリスはxを使ってBitcoinのブロックチェーン上でコインを入手する。

という感じ。BitcoinにもSchnorrが導入されると、Bitcoinサイドも↓みたいにスクリプトレスにできるようになる。

www.youtube.com

アウトプットへのタイムロック条件の適用

前回の記事でトランザクションカーネルのlock_heightにブロック高を指定することで絶対的、相対的なタイムロックをトランザクションに施せることは分かった。こういった何の条件もついていないタイムロックの機能に対し、BitcoinではOP_CLTVやOP_CSVといったopcodeを使ってトランザクションアウトプットにタイムロック条件を付けることができる。

Mimblewimbleにはそういったスクリプトは無いので、前回の記事に書いた条件の無いタイムロックトランザクションにちょっと変わった仕掛けを組み合わせる。

まず2つの秘密鍵Key1とKey2を用意する。そして、２つの秘密鍵を合算して新しい秘密鍵を作る。

Key3 = Key1 + Key2

そして２つのトランザクションTx1とTx2のアウトプットをOut1とOut2とし、

  • Out1のブラインドファクターはKey1
  • Out2のブラインドファクターはKey2
  • Tx2にだけロックタイムが付いている

という状況を作る。これは、

  • Tx1はすぐにでもブロードキャストでき、ブロックチェーンに格納される。
  • Tx2はロックタイムが設定されているため、それを経過するまでブロードキャストできない。
  • Key3を使う場合、Out1とOut2を同じトランザクションで同時に使用する場合、Tx2のロックタイムを待たなければならない。

という状況が作られることを意味する。

そのため、Key1とKey2の情報を知り得ない形でKey3を構成すれば、Out1とOut2を個別に使用できないため、タイムロックの期間を過ぎるまで待つしか無い。つまりこういう鍵の公開スコープをハンドリングすることで、アウトプットにタイムロック条件を適用させることができる。

どうやってスクリプトレスなアウトプットにタイムロックのような条件を付与するのかと不思議だったけど、↑みたいに秘密鍵のスコープ調整と組み合わせて実現するのね。スクリプトと比べて手間ではあるけど、よく考えるなー。

Grinでコントラクトを作る際の基本要素

Grin Mimblewimble

MimblewimbleとGrinのトランザクション構成が把握できたので↓

techmedia-think.hatenablog.com

今回は↓を参考にGrinでどんなコントラクトを作る際に使える基本要素についてまとめる。

https://github.com/mimblewimble/grin/blob/master/doc/contracts.md

Mimblewimbleでは基本的にコインはPedersen Commitmentで管理されるため、Bitcoinのようなスクリプトは存在しないが、トランザクションにタイムロックの仕組みは用意されている。それに↑の記事で説明したように、署名は送信者と受信者それぞれのSchnorr署名を集約して構築することから、Schnorrもコントラクトを構成する上で利用可能だ。

タイムロック

トランザクションをある一定の時間（ブロック高）までブロックに入れられないようロックする機能で、Bitcoinではさまざまなコントラクトを実現する上で欠かせない機能の１つである。

Grinでは以下の2種類のロックをサポートしている。

絶対時間によるタイムロック

クロスチェーンのアトミックスワップや、Lightning Networkのマルチホップ決済で使われるHTLCs（Hashed Time-Locked Contract）で必要となる要素の１つが絶対時間によるタイムロック。

Grinではトランザクションのトランザクションカーネルに、手数料と一緒にlock_heightというフィールドがセットできるようになっており、このフィールドには任意のブロック高を指定することができる。そして、指定されたlock_heightまでトランザクションをブロックに入れることはできないようになっている。

通常Grinのトランザクションに署名をする際、署名対象のメッセージはM = fee | lock_heightと手数料とこのlock_heightで構成される。Grinでは送信者と受信者が協力して署名を構成するため、このlock_heightは当然両者が合意した値になり、署名のメッセージに含まれているので第三者が変更することもできない。

Bitcoinにも同様のnLockTimeというフィールドがトランザクションのプロパティにあるが基本的にはそれと同じ機能になる。

相対時間によるタイムロック

Lightning Networkで不正を働いたユーザーに対するペナルティを設ける際などに使われているのが、あるトランザクションがブロックに入ってからタイマーがスタートする相対時間によるタイムロック。

Grinではトランザクションカーネルのlock_heightを相対的に解釈するよう拡張する。Tx1とTx2があるとして、Tx1がブロックに格納されてからlock_heightで指定したブロック経過した後、Tx2がブロックに入れられるよう制御する。

このような相対的なタイムロックを持つトランザクションTx2を作成する際は、絶対的なタイムロックと以下が異なる。

  • lock_timeは絶対的なブロック高ではなく相対的なブロック高を指定する。
  • トランザクションに署名する際のメッセージは、手数料とlock_heightに加えて、タイムロックの起点となるトランザクションのカーネルコミットメントから構成される。
    M = fee | lock_height | Tx1のカーネルコミットメント

マルチシグ

コインを使用するのにアリスとボブの両者の署名が必要なマルチシグをGrinでどう作るか。基本的にGrinはスクリプト言語が無いので、Scriptlessで実現する必要がある。そもそもGrinではトランザクションに署名する際に、送信者と受信者がそれぞれ作成した署名を集約するSchnorrの集約署名を利用してるので、マルチシグも基本的にSchnorrの集約署名で実現する。

通常のSchnorr署名であれば、アリスとボブがマルチシグにコインをロックする場合は、アリスの公開鍵をPA = xaG、ボブの公開鍵をPB = xbGとするとP = PA + PBとなる公開鍵にコインをロックし、そのコインを使用する際はお互い署名用のランダムnonce RA = kaG、RB = kbGを選択し、R ＝ RA + RB、sa = ka + H(P, R, M)xa, sb = kb + H(P, R, M)xbを計算し、集約した署名（R, sa + sb = ka + kb + H(P, R, m)(xa + xb)）を作れば良い。

Grinの場合も基本的に仕組みは同じで、マルチシグは両者がそれぞれ知る秘密の情報が無いと署名を作成することができないコミットメント宛にコインを送る。つまり1つのコミットメントに対してそのブランディングファクターはアリスとボブがそれぞれ知るブランディングファクターを足し合わせたものになる。

具体的には以下の手順でコインをロックする。

  • ボブがブラインディングファクターrbを選択し、rb*Gをアリスに送る。
  • アリスも同様にブラインディングファクターraを選択し、コミットメントC = ra*G + rb*G + v*Hを計算する。このコミットメントをボブに送る。
  • ボブはrbとCを使ってvに対する範囲証明を作成し、それをアリスに送る。
  • アリスは自身の範囲証明を生成し、ボブの範囲証明に集約する。最終的なマルチシグのアウトプットを {O_{AB}}とする。

あとはトランザクションを作成し、そのアウトプットに {O_{AB}}を含めれば良い。また {O_{AB}}のコミットメントを使用する時は、インプットのブランディングファクターの集約署名を作成する際に、アリスとボブが協力してそれぞれのブランディングファクターを加味したSchnorr署名を作成し集約すればいい。

マルチパーティ＋タイムロック付きトランザクション

ペイメントチャネルを構成する際によく使われるのが、マルチシグ宛にコインをロックしてペイメントチャネルをオープンするけど、オープンする前にタイムロック付きの払い戻しトランザクションを作成しておくというパターン。

Grinでも上述したマルチシグとトランザクションカーネルのタイムロック機能を利用すると、以下の手順で同様の事ができる。

  1. 上記のようにアリスはボブとの2-of-2のマルチシグトランザクションを作成し、それをボブに共有する。ただしこの段階ではアリスはトランザクションカーネルにセットする署名は作っていない。
  2. ボブは↑のタイムロックを使って、24時間（1440ブロック）経過したらアリスにマルチシグのコインを返金する払い戻しトランザクションを作成し、ボブの署名を付与しアリスに送る。
  3. アリスは払い戻しトランザクションのボブの署名の有効性を検証し、問題なければボブと一緒に2-of-2のマルチシグトランザクションを完成させ（トランザクションカーネルに署名をセットし）ブロードキャストする。

これで、アリスとボブは2-of-2のマルチシグにロックされた資金を元に単方向のオフチェーン決済が可能になる。もしボブから応答がなくなったとしても、タイムロック期間が経過したらアリスは自分の資金を取り戻すことができる（ただ上記だけではまだペイメントチャネルを双方向にしたり、チャネルの有効期間を無期限にするといったことはできない）。また、他のチェーンのコインとgrinを交換する際のAtomic Swapなんかにも利用できる。

と、マルチシグの仕組みとタイムロックの機能についてははっきりしたので、次は上記の基本要素を使って複雑なコントラクトをどう実装するか見ていきたい。キーはタイムロック部分をBitcoinでいうOP_CLTVやOP_CSVみたいにどうコントロールするのかという部分。

MimblewimbleとGrinのトランザクションフロー

Mimblewimble Grin

Grinのトランザクションのトランザクションフローを見てたら、オリジナルのMimblewimbleと署名プロセスが少し変わってたのでまとめてみた。

Mimblewimbleの基本機能

Pedersen Commitment

Gregory Maxwellが提案したConfidential Transactionで導入されたコインの量を秘匿する機能。コインの量をBitcoinのような整数値ではなく、以下のような準同型性のコミットメントとして管理することで取引の当事者以外はコインの量を知り得なくする仕組み。

Commitment = r * G + v * H

GとHは同じ楕円曲線上の異なる生成点。rはブランディングファクターで、vがコインの量。トランザクションのアウトプットは全てこのコミットメント持つ。MimblewimbleではConfidential Transactionを単純に量の秘匿に使うだけでなく、scriptPubkeyも無くしこのコミットメントに集約している（ブランディングファクターが秘密鍵の役割を果たす。後述）。

Confidential Transactionの仕組みの詳細については先日GBECで解説したスライド参照↓

www.youtube.com

Mimblewimbleのトランザクション

Mimblewimbleでは、Bitcoinのように各インプット毎にそれぞれ署名があるわけではなく、トランザクション毎に1つの署名が作られる。その際、署名に使用する秘密鍵は↑のPedersen Commitmentのブラインディングファクターの総計から作られる。

この辺が躓きがちなポイントなんだけど、Bitcoinの場合、アウトプットはコインの量を持つvalueとそのコインのロックスクリプトであるscriptPubkeyとセットで管理されているが、Mimblewimbleの場合は上述したようにscriptPubkeyのようなロックスクリプトはなく、上記のPedersen Commitmentのみが存在する。それ以外に、コインをロックするような公開鍵の情報などがセットされているわけではない。その状態でどうやってコインを取引するための署名を作るのか疑問に思うが、以下の手順で署名は作られる。

例えば、アリスが以下の２つのコミットメントを持っているとする。

  • c1 = 35G + 4H
  • c2 = 93G + 6H

それぞれブラインディングファクターが35と93、コインの量が4と6で２つ合わせて10コイン持ってることになる。

この状態で、上記2つのコミットメントを使ってアリスからボブに７コイン送る場合、以下のような手順でトランザクションを構成することになる。手数料は１コインとする。

  1. アリスはお釣り用のコミットメントで使用するブラインディングファクターをランラムに選択する。これを47とする（※実際のブラインディングファクターはもっと巨大な値）。
  2. アリスはお釣り用のコミットメント c3 = 47G + 2H を作成する。
  3. アリスは自身が管理するブラインディングファクターの差分（インプットの全ブラインディングファクターからアウトプットの全ブラインディングファクターを差し引いたもの）を計算する。
    47 - (35 + 93) = −81
  4. アリスはトランザクションの雛形とブランディングファクターの総計（-81）をボブに送る。
  5. ボブはブラインディングファクターをランダムに選択する。これを153とする。
  6. ボブは選択したブラインディングファクターを使って、7コンを受け取るコミットメント c4 = 153G + 7H を作成する。
  7. ボブはアリスから受け取ったブランディングファクターの総計に自身のブランディングファクターを加味し、ブランディングファクターの超過値（excess）を算出する。
    153 - 81 = 72
  8. ボブは超過値（72）を秘密鍵として署名を生成しブロードキャストする。
  9. ネットワークのノードはトランザクションの全インプットとアウトプットのコミットメントを相殺して残った楕円曲線上の点＝公開鍵（今回の場合は72 * G）に対して有効な署名があるか検証する。
    この時、有効な署名が作成できるということは、コミットメントの内、ブラインディングファクターについてはexcessが存在するが、コインの量についてはアウトプット−インプットで0Hになるということの証明にもなる。

というように、送信者のブラインディングファクターの総計を受け取った受信者が、自身が選択したブラインディングファクターを加味して受信者のみが知りうるexcessを秘密鍵としてしている。Bitcoinの場合はインプットの所有者＝送信者が署名を作成するが、Mimblewimbleの場合は受信者が署名を作成することになる。

Mimblewimbleのトランザクションはインプットとアウトプットの他にトランザクションカーネルと呼ばれるデータを持ち、トランザクションカーネルは、

  • 手数料
  • 超過値（excess）
  • excessを使って作成した署名
  • lock_height

を持つ。署名は個々のCommitmentに対して存在するのではなく、トランザクション単位で有効になる。

Grinのトランザクション

GrinはMimblewimbleを実装したブロックチェーンだが、署名手順はMimblewimbleとは多少異なる。オリジナルのMimblewimbleの投稿では、送信者が自身に関連するブラインディングファクターの総計をそのまま受信者に渡すことで、受信者のみがexcess値を知り、それを使って署名を作成していたが、Grinの場合送信者はブラインディングファクターの総計をそのまま渡すのではなく、楕円曲線のベースポイントGに乗算して公開鍵として渡すようになっている。この場合、受信者は自身の受け取り用のアウトプットのコミットメントを作成し、そのブラインディングファクターを加味することで、excess * Gを算出することはできるが、その秘密鍵であるexcessの値を知ることはできない。そのため送信者と受信者は協力し、お互いが知るブラインディングファクターの情報から署名をそれぞれ作り、その署名を集約することでexcess * Gに対して有効な署名を完成させるというアプローチを採っている。

この時作成される署名は、集約特性のあるSchnorr署名が使われる。

Schnorr署名

秘密鍵をx、秘密鍵に対応する公開鍵をP = x * G、メッセージをMとする。尚、Bitcoinではトランザクションに署名をする際、署名対象のメッセージMはトランザクションの各データ（バージョン、locktime、インプット、アウトプットなど）から生成されるが、Grin場合はトランザクションの手数料とlock heightの2つの要素で構成される。

GrinのSchnorr署名の作成手順は以下のとおり。

  1. ランダムにnonce値kを選択する。
  2. R = k * Gを計算する。
  3. e = SHA256(M | R | P)を計算する。
  4. s = k + e * xを計算する。
  5. 算出した（R, s）のペアが署名データ

そして署名の検証は、s * Gがs * G = R + ePを満たすか検証する。

Grinの署名手順

Grinの詳細なトランザクションフローは↓にまとめられている。

https://raw.githubusercontent.com/mimblewimble/grin-wallet/master/doc/transaction/basic-transaction-wf.png

送信者は送金にあたって以下の作業をする（内部的な実装の手順は省略）。

  1. トランザクションカーネルに現在のチェーンの高さでlock_heightをセットする。
  2. インプットにするコミットメントを選択する。
  3. インプットのブラインディングファクターの合計x1を計算する。
  4. お釣り用のアウトプット用のブラインディングファクターxCを選択し、お釣り用のアウトプット（コミットメント）を作成する。
  5. トランザクション手数料を計算する。
  6. 全インプットとアウトプットから超過合計xS1 = xC - x1を計算する。
  7. ランダムなnonce値kSを選択する。
  8. xS1からランダムなカーネルオフセットoSを減算した、xS = xS1 - oSを計算する。
  9. 送信者側のブラインディングファクターの総計xSと署名に必要なnonceの値kSをGに乗算して、曲線上の点xS * GとkS * Gを計算する。
  10. 相手インプット、アウトプットのコミット、手数料、lock_height、xS * G、kS * Gを送る。

受信者は、送信者から受け取った情報を元に以下の作業をする。

  1. 受信用のブラインディングファクターxRを選択し、 受信用のアウトプット（コミットメント）を作成する。。
  2. 署名に用いるメッセージM= fee | lock_heightを作成する。
  3. 署名に使用するランダムなnonce値kRを選択する。
  4. xRとkRをそれぞれGに乗算して、曲線上の点xR * GとkR * Gを計算。
  5. Schnorr署名用のチャレンジ e = SHA256(kR * G + kS * G | xR * G + xS * G | M)を計算
  6. 受信者側のSchnorr署名 sR = kR + e*xRを計算する。
  7. 送信者に受信者が計算した部分署名値sRと、xR * G, kR * Gを送る。

送信者は、受信者から受け取った情報を元に署名を完成させトランザクションをブロードキャストする。

  1. 署名に用いるメッセージM= fee | lock_heightを作成する。
  2. Schnorr署名用のチャレンジ e = SHA256(kR * G + kS * G | xR * G + xS * G | M)を計算
  3. 受信者から送られた部分署名であるsRについて、sR * G = kR * G + e * xR * Gが成立するか検証する。
  4. 送信者側のSchnorr署名 sS = kS + e * xS を計算する。
  5. Schnorr署名を完成させる。Schnorr署名のRの値はkS * G + kR * G、sの値はsR + sS。
  6. sの値が公開鍵x*G = xS * G + xR * Gに対して有効な署名か検証する。

トランザクションに署名する際の秘密鍵は基本的にMimblewimbleのexcessの値であり、上記のケースであればexcess = xR + xS。このexcess値をお互い知ること無く、協力してSchnorr署名のsの値sR + sS = kR + kS + e * (xR + xS)を計算している。

↑のようにGrinの場合は、Mimblewimbleのオジリナルの投稿とは異なり、送信者と受信者が協力して署名を作成するようになってる。単純にexcess値をそのまま渡すより安全であるというのと、署名のメッセージにlock_heightが含まれることから送信者と受信者の両者がロックタイムに合意するという意味もあるのかもしれない。

自称サトシになる方法

Bitcoin ECDSA Cryptography

最近また自称サトシが登場してるみたいだったので、自称サトシになるために必要なことを調べてみた。

ecdsa - If someone wanted to pretend to be Satoshi by posting a fake signature to defraud people how could they? - Bitcoin Stack Exchange

自称サトシになるには？

BitcoinのGenesis Block↓のコインを移動することができれば、それは自称ではなく間違いなく本物のサトシだが、

https://en.bitcoin.it/wiki/Genesis_block

自称サトシが証明として提供しているのは、Genesis Blockのコインの送金先である公開鍵

04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f

に対して有効な署名。この有効な署名を作ることができるのは、対応する秘密鍵を知るサトシ本人であるというもの。

一見正しい論理に思えるが提供しているデータにトリックがある。まず、正しいECDSA署名についておさらいしておこう。

ECDSA署名の作成と検証

定義にあたって、以下の表記を使用する。

署名の作成

秘密鍵xとメッセージmを使って署名を作成する場合、手順をざっくり書くと以下のようになる。（他にも諸々細かい注意点はあるので詳細はRFCなど参照）

  1. ランダムな値kを選択する。
  2. R = kGを計算し、Rのx座標をrとする。
  3. {s = \frac{H(m) + r \cdot x}{k}}を計算する。
  4. 計算してできた(r, s)が有効なECDSA署名。

署名の検証

検証者は署名(r, s)、メッセージm、公開鍵Pが与えられた状況で、以下を検証する。

  1. H(m)を計算する。
  2. {\frac{H(m)}{s}G + \frac{r}{s}P}を計算し、算出した点のx座標がRと等しいか検証する。

自称サトシの証明の作り方

自称サトシも上記ECDSA署名(r, s)を提供しているわけだが、ここにトリックがあり上記のようなプロセスを経て作られたデータではないと思われる。どういうことかというと(r, s)とH(m)は提供しているが、m自体は提供していない。

メッセージのハッシュ値を計算する部分は、ECDSAのアルゴリズム上、必要不可欠な重要なパートであり、署名を検証する検証者は、署名対象のメッセージのハッシュを必ず自身で計算しなければならない。そうでない場合、ECDSAの安全性は保持されず、偽造が可能になる。

具体的にどういう不正ができるかとというと、以下のようにして(r, s)を計算できる。

  1. ランダムな値aとbを選択する。
  2. R = aG + bPとなるRを計算し、Rのx座標をrとする。
  3. メッセージのハッシュをH(m)を {r \cdot \frac{a}{b}}とする。
  4. {s = \frac{r}{b}}とする。
  5. 上記（r, s）を署名とする。

これを検証するととうなるかというと、

{\frac{H(m)}{s}G + \frac{r}{s}P = \frac{r \cdot \frac{a}{b}}{s}G + \frac{r}{s}P = r \cdot \frac{a}{b} \cdot \frac{b}{r}G + r \cdot \frac{b}{r}P = aG + bP}

となり、R = aG + bPと等しくなり有効な署名として検証される。

このようなことで偽の署名を有効と認識しないためにも、検証者は必ずメッセージmからハッシュ値を計算し、その値を持って署名の検証をする必要がある。

今回の自称サトシが提供したのはあくまで、(r, s)とH(m)なので、これは上記のようにサトシの証明にはならない。また、ハッシュ値が {r \cdot \frac{a}{b}}となるようなプリイメージを見つけることができないかぎり、ECDSAの安全性自体を破るものでもない。

一応、しばらくしたら内容（プリイメージ）を明かすと発言しているので楽しみにしておきたい。