MASTを実現するMERKLEBRANCHVERIFYを定義したBIP-116

MAST（マークル化抽象構文木）を実現する新しいアプローチとしてMERKLEBRANCHVERIFY opcodeの導入を提案するBIP-116が公開された↓

https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki

MAST（Merkelized Abstract Syntax Tree）とは？

Bitcoinのスクリプトでは IF/ELSEの分岐を使って以下のように複数のアンロック条件を定義することができる。

IF
  2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFY
ENDIF

このスクリプトにロックされたコインは、

• アリスとボブが協力してマルチシグをアンロックする署名の作成が必要
• ボブがハッシュのプリイメージを知っていればそのプリイメージとボブの署名が必要

のどちらかの条件を満たせばアンロックできる。つまりアンロックのパスは２つある。

こういったスクリプトはそのハッシュがP2SHの形式でscriptPubkeyに指定され、そのコインを使用する際のインプットのscriptSigに↑のスクリプトと↑のアンロック条件を満たす要素がセットされるようになる。

この一般的な手法には↓の２つの問題がある。

1. scriptSigにプッシュできる要素数には制限があるので巨大なスクリプトは組み込めないし、スクリプトのアンロック条件が多くスクリプトが大きくなるほどトランザクションサイズも増えるので手数料も増える。
2. 実際にコインを入手する際に使用するパスは１つだけなのに、使用しないパス（条件）も公開され誰もが参照可能な状態になってしまう（ケースによっては使用されない条件は秘匿したいということも考えられる）。

そこでスクリプトのパスについてマークルツリーを利用して↑の問題を解消しようというのがMASTを使ったアプローチになる。各アンロック条件のパスをそれぞリーフノードとしてマークルツリーを構成し、そのマークルートに資金をロックする。資金を使用する際は、実際にアンロックに使用する実行パスのスクリプトと、それ以外の条件のマークルブランチのハッシュと、使用する実行パスへのマークルパスをscriptSigのスタックに入れる。

こうすると実際にアンロックに使用するスクリプト部分のみが公開され、それ以外のスクリプトは秘匿されたまま、しかし与えられたマークルパスとハッシュから計算したマークルルートとロック時に使われたマークルルートを比較することで、スクリプト全体に対するコミットはされる。また全スクリプトを公開する必要がないことから、どんなに巨大なスクリプトでも構築することができ、scriptSig自体はコンパクトになることから手数料も大きくなることはない。

MASTの提案自体は、Johnson Lauが2016年4月にBIP-114として提案している↓

techmedia-think.hatenablog.com

BIP-114はSegwitによって導入されるwitness programに新バージョンを定義することで使用できるような提案になっており、segwitが導入されるのに時間がかかったこともありデプロイ計画はまだない。

今回のBIP-116は、BIP-114がwitness programの新しいバージョンでMASTをサポートするのに対し、まだ残りがある将来の拡張用のNOP opcodeを使って新しいopcode MERKLEBRANCHVERIFYを導入する仕様になっている。既存のスクリプト内で使用可能になるので非Segwitなトランザクションでも利用可能になる。個人的にはBIP-116の方がシンプルで既存のクライアントとも互換があるので、BIP-116によるMASTの導入に期待したい。

また、デプロイ方法にBIP-8を挙げてるのも興味深い。

techmedia-think.hatenablog.com

具体的なBIP-116の具体的な仕様については、BIPの内容を見てみよう↓

概要

Bitcoinのコントラクトの一般的な手法では、アンロック条件を全て列挙し、これらの条件の検証を１つのスクリプトにプログラムする。ロックされているコインを償還する際は、例えばif/elseのような条件が構成された場合、使用する条件を明示的に選択し、選択した条件を満たす要素をwitnessスタックにプッシュする。

この手法には、検証に使われないパスも含め全てのプログラムのパスをscriptPubkeyもしくはredeem scriptを含めなければならないという大きな欠点がある。これはブロックチェーンのスペースを無駄に消費し、プッシュ制限のためスクリプトのサイズを制限することなる。また特定のユーザーに向けたコントラクトであるケースも多く、その内容が全て公開されてしまうためプライバシーやファンジビリティの影響もある。

このBIPでは、スクリプトの作成者が償還時にスクリプトの全体を明かすことなく、償還に使用するスクリプトの１要素もしくは複数の要素のみを明らかにすれば済むように、ソフトフォークでアップグレード可能な新しいopcode MERKLEBRANCHVERIFYを提案する。公開鍵や検証サブスクリプトなどの要素をこれらのポリシーでエンコードし、MERKLEBRANCHVERIFYopcodeを使えば既存のBitcoinスクリプトの制限を克服できる。

仕様

MERKLEBRANCHVERIFYは既存のOP_NOP4 opcodeを再定義して使用する。実行した際、以下の条件のいずれかに当てはまるとスクリプトインタプリタはエラーで終了する。

1. スタックの要素が３つより少ない
2. スタックの最初の要素が2バイトより大きい
3. スタックの最初の要素は整数Nとして解釈され、Nが負の値であるか最小限のエンコードでない場合
4. スタックの２つめの要素が32バイトでない場合
5. スタックの３つめの要素がBIP-98で指定されているfloor(N/2) のVERIFYハッシュであるシリアライズされたマークルツリーのinclusion proofではない場合
6. 残りのスタックの要素にはfloor(N/2)未満の追加要素が含まれており、これらをあわせてインプットスタック要素となる。

Nの下位ビットがクリアな場合N&1 == 0、各インプットスタック要素はdouble-SHA256でハッシュされている。それ以外の場合は、各要素は正確に32バイトの長さである必要がありシリアライズされたハッシュとして解釈される（これらはVERIFYハッシュ）。

スタックの３つめの要素のマークルツリーのinclusion proofのVERIFYハッシュを使ってスタックに示されている順に上から下に計算して算出したfast マークルルートが、スタックの２つめの要素と一致しない場合、スクリプトインタプリタはエラーで終了する。

上記以外の場合は、NOPが実行されたかのようにスクリプトの実行が継続される。

動機

BIP16 (Pay to Script Hash)やBIP141 (Segregated Witness)では両方ともredeem scriptをscriptPubKey外につまりUTXO外に保持することができようにしたが、コインを使用する際にそのコインの全使用条件（redeem script全て）を明らかにしなければならない。これには償還に必要な条件のパスやポリシーが含まれる。この不必要な情報がブロックチェーン上に存在することは非効率なだけでなく、使用されていないスクリプトポリシーが識別される可能性があるためプライバシーやファンジビリティにも影響する。マークルハッシュツリーを使ってポリシーオプションにコミットし、償還時に使用するポリシーのみを明らかにすることで、この情報漏洩は最小限に抑えられる。

マークルハッシュツリーを使ってポリシーにコミットすることで、今までは組み込みのスクリプトサイズや実行時の制限のため不可能だったより複雑なコントラクトの構築が可能になる。ポリシーに対するマークルコミットメントにより、サイズや実行時の制限は全ポリシーの合計ではなく使用するポリシーのみに制限される。

論拠

Satoshiがブロックヘッダのマークルルートの計算に使用したマークルルートの構成には下位プロトコルにmalleabilityを導入する要因となる重複エントリーの脆弱性があるため、MERKLEBRANCHVERIFY opcodeはBIP-98で定義されたfast マークルハッシュを使用する。マークルプルーフにおけるmalleabilityは、MERKLEBRANCHVERIFYを使用するプロトコルに脆弱性をもたらす可能性がる。例えばコンパクトな2-of-Nのポリシーでは、MERKLEBRANCHVERIFYを使って同じツリーから２つの鍵が一度に抽出されたことを証明し、続いて同じエントリーが２回使用されなかったことを確認するためビット単位の等価性の証明をチェックする。脆弱なマークルツリーの実装では、バランスの取れていないマークルツリー内に特別なポジションがあり、１つのエントリーに対し複数のプルーフを構築できてしまう。

BIP141 (Segregated Witness)は、スクリプトバージョニングと呼ばれる強力なスクリプトアップグレードの仕組みサポートしており、以前であればハードフォークが必要だったアップグレードをソフトフォークで可能にした。スクリプトバージョニングをこの仕組みを導入すると、MERKLEBRANCHVERIFYはそのインプットを使用するように書くことができ、多くの予想されるユースケースに対して２バイトの節約が可能だ。しかし、スクリプトバージョニングではなく BIP65 (CHECKLOCKTIMEVERIFY)やBIP112 (CHECKSEQUENCEVERIFY)の導入の際に使われたより使い慣れたNOPを使った拡張ソフトフォークの仕組みが以下の２つの理由から採用された。

1. インフラストラクチャの互換性
   NOP拡張のソフトフォークにすることで、カスタムスクリプトを使用できる既存のソフトウェアでMERKLEBRANCHVERIFYを利用できるようになり、結果BIP143の署名コードを必要とせずP2SHやP2SHでネストされたP2WSHアドレスが使える。これによりMERKLEBRANCHVERIFYはスクリプトバージョニングやBIP-143の署名をライブラリやツールがサポートするのを待つことなく、必要なサービスですぐに使用することができる。
2. スクリプトアップグレードプロトコルの決定の遅れ
   今後のスクリプトのアップグレードに関して、スクリプトバージョニングをどのように使用すべきか未解決の問題がある。将来の拡張用に確保されているスクリプトバージョンは16種類しかないため、希少なリソースとして扱う必要がある。さらに、スクリプト機能のバージョニングはおそらくwitnessに対して定義されるべきで、BIP141のスクリプトバージョニングはwitnessの構造を定義するのにのみ使用されるが、まだそのようなプロトコルは無い。NOP拡張スペースを使用することで（既に利用可能な拡張スペースを利用しているので）、スクリプトのアップグレード手続きが完了するまでMERKLEBRANCHVERIFYが停滞するのを防ぐことができる。

MERKLEBRANCHVERIFY opcodeではVERIFYハッシュを直接提示するか、リーフの値をdouble-SHA256して計算する。ほとんどの場合、後者のアプローチはリーフの値を前処理なくブランチの検証と他の目的の両方に使用できることが期待される。しかし既に計算済みのハッシュをインプットとすることで、チェーンされたMERKLEBRANCHVERIFYopcodeを使って520バイトのプッシュ制限を超えるほど大きなプルーフを持つツリーのブランチを検証することができる。定義されているように、リーフから15番めの内部ノードをルートとして証明し、そのノードのハッシュが実際のマークルツリーのルートハッシュの子であることを証明することで30ブランチパスを検証できる。（ハッシュ値をキーとするバイナリプレフィックスツリーのような）250ブランチパスの検証は、18の連鎖検証が必要だが現在のスクリプトの制限内に収まる。

アプリケーション

1-of-N（Nが巨大な場合）

スクリプトサイズによる線形スケーリングなく、巨大なセット内の任意の鍵でコインを使用するredeem scriptは以下のようになる。

redeemScript: <root> 2 MERKLEBRANCHVERIFY 2DROP DROP CHECKSIG
witness: <sig> <pubkey> <proof>

redeem scriptは標準のpay-to-pubkey-hashにとても似てるが、P2PKHにおいてpubkeyのハッシュがP2PKHのハッシュ（コミットメント）と同じであることを示す代わりに、pubkeyはredeem scriptでコミットされているマークルツリーに含まれる多くの公開鍵の１つであることを示している。最初のパラメータ2の下位ビットは((2>>1) == 1)でインプットが１つある（シリアライズされた公開鍵）ことを指し、そのVERIFYハッシュはdouble-SHA256を使ってMERKLEBRANCHVERIFYで計算する必要がある。

ハニーポット

Pieter Wuilleによって説明されているように*1、1-of-Nのスキームはハニーポットの構築に特に有用だ。サーバー自体の価値よりも大きな特典をつけるのが大事で、サーバーに侵入された場合ハッカーはそのサーバより価値のあるビットコインを入手する＝サーバーへの侵入が明らかになる。しかしサーバの数が多い場合（1,000台とか）、各サーバ毎に別々の賞金を確保するととても高額になる。同じ賞金が複数のサーバで共有され、どのサーバが侵入されたか明らかになるのが望ましいだろう。

これには1000個の別々の鍵を生成し、これらの公開鍵のハッシュツリーを構築し、各鍵と関連するマークルパスをそれぞれのサーバに配置することで実現できる。ハニーポットが請求されたとき、前のコインのオーナーは資金の請求に使われた鍵とパスからどのサーバが侵入されたのか知ることができる。

実装

このBIPの実装はコンセンサスコードの更新とテストの両方を含み、以下のリポジトリで公開されている。

https://github.com/maaku/bitcoin/tree/merkle-branch-verify

デプロイ

このBIPはBIP-8を使ってデプロイされ、merklebranchverifyという名前でbit 2を使用する。

Bitcoinのmainnetでは、BIP8のstartheightがM（未決定）で、timeoutはM+50,400ブロック後。

Bitcoinのtestnetでは、BIP8のstartheightがT（未決定）で、timeoutはT+50,400ブロック後。

DISCOURAGE_UPGRADABLE_NOPSは、この機能を使用するトランザクションが既にネットワークルールで非標準とみなされているため、例えばBIP68の時よりデプロイは容易になる。

互換性

古いクライアントはOP_MERKLEBRANCHVERIFYをNOPとみなして無視する。プルーフは検証されないがトランザクションは承認される。

*1:https://blockstream.com/2015/08/24/treesignatures.html

Merkle Treeの重複エントリー問題の解消とパフォーマンスを向上するFast Merkle Treeについて定義したBIP-98

Bitcoinのブロックヘッダにはブロックに入っているトランザクションのリストにコミットするため、各トランザクションのTXIDをリーフノードにしたマークルツリーを構築し、そのマークルルートの値が入れられるようになっている。ブロックにどれだけたくさんのトランザクションが含まれていても、それらから計算されるマークルルートは32バイトの固定値で、その固定値が全てのデータセットのコミットメントになる、とても空間効率の良いデータ構造で、ブロックヘッダのマークルルート以外にも様々な使い方が提案されている。

このマークルツリーの構造の改良について、Fast Merkle Treeという新しい提案（BIP-98）が公開され↓

https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki

↓のような特徴がある。

パフォーマンスの向上

リーフノードからマークルツリーを構築する際、親ノードの値は２つの子ノードの値を結合し、それをdouble-SHA256ハッシュした値になる。この提案では必ずしもここでdouble-SHA256である必要はなく、これをfast-SHA256という新しく定義する暗号学的ハッシュ関数に置き換えることでパフォーマンスを向上させる。ただこのハッシュ関数はインプットとして2つの32バイトのハッシュ値を持つデータに対してのみ有効なハッシュ関数となる。

脆弱性への対応

マークルツリーの構築アルゴリズムでは、マークルツリーのリーフ要素が奇数の場合、奇数の最後の要素を複製して偶数個にするが、ここに重複エントリーの問題がある。奇数個のリストのアイテムを持つマークルツリーと、奇数個の最後の要素と全く同じ要素を加えて偶数個にしたリストのマークルツリーは、リーフノードの要素数は異なるが、それら計算したマークルルートは同じ値になる。Fast Merkle Treeの場合、要素数が奇数個の場合にその要素をコピーして偶数個にすることをしないことで、この脆弱性を回避する。

データがマークルツリーに含まれていることを証明するInclusion Proofのエンコード方法

マークルツリーにあるデータが含まれていることを示すプルーフ提供の仕組みは、SPVノードなどが受け取るmerkleblockメッセージなどで利用されている。このメッセージには

• トランザクション数（リーフノードの数）
• 1つ以上のトランザクションのハッシュと内部ノードのハッシュ
• マークルツリーの特定のノードに↑のハッシュを割り当てるために使うフラグリスト

が含まれており、これをベースにマークルツリーの部分的な復元や検証をしている。この内、フラグリストには1バイト中に8個のフラグビットがセットされ、そのフラグビットの0 or 1でマークツリー内のノードにハッシュを割り当てるかどうか判断している。

一方このFast Merkle Treeでは、ツリーの内部ノードの数を可変長整数でシリアライズし、その後に内部ノードが持つ２つの子ノードが{SKIP,VERIFY,DESCEND}のどの構成であるか示す3 bitのデータをルートノードから順番にバイト列にパックしシリアライズしたデータでツリー構造を表現するようになっている。

用途

↑のような特徴があるFast Merkle Treeだが、既存のブロックヘッダのマークルルートの計算方法をこれに変えようという提案ではなく（変更するとHFになる）、別で提案されているBIP-116のMERKLEBRANCHVERIFYの実装でこのアルゴリズムを使用するようだ。

詳細についてはBIPの内容を見てみる↓

概要

多くのアプリケーションでは、あるデータがデータセット内のデータであることを証明するのに、データセットの全データを明らかにする必要はない。インナー/内部ノードのラベルがその子ノードのハッシュから生成されるマークルハッシュツリーは、それを実現する暗号化ツールだ。Bitcoinではブロック内のトランザクションをブロックヘッダにコミットするのにマークルハッシュツリーを利用している。Satoshiによって作られたこの設計は、National Vulnerability DatabaseのCVE-2012-2459*1に記載されているように重複したエントリーに関連する深刻な欠陥に悩まされており、また不必要なダブルハッシュにより最適なパフォーマンスとは言えない。

このBIPでは、CVE-2012-2459の脆弱性がなく、最適化したSatoshiのマークルハッシュツリー構造の実装に比べてハッシュツリーの構築および検証時間が55%減少する、より効率的なマークルハッシュツリー構造について説明する。

動機

マークルハッシュツリーは、全ての非末端ノードはそのノードに接続されているノードの値もしくはラベルを結合した値のハッシュ値でラベルされる非循環有向グラフのデータ構造である。BitcoinはSatoshiが考案したユニークなマークルハッシュツリー構造を利用して、ブロック内のトランザクションのリストに対するブロックヘッダのコミットメントを計算している。新しいアプリケーションではこれと同じデータ構造を利用することで、実装の共有やメンテナンスコストの削減が見込まれるが、再利用には３つの欠陥がある。

最初に、Satoshiのマークルハッシュツリー構造は重複したエントリーについて深刻な欠陥があり、そのまま使用するとプロトコルにバグをまねく可能性がある。この欠陥の悪用からプロトコルと実装を保護することは可能だが、この脆弱性を回避する安全なプロトコルを設計するには洞察といくつかの注意が必要だ。新しいプロトコルの設計者はネイティブな実装による下流のバグの可能性を確実に減らすため、可能な限りSatoshiのマークルツリーハッシュ構造の使用を避けなければならない。

第二に、Satoshiのマークルツリーハッシュは不要な数の暗号学的ハッシュ関数の圧縮ラウンドを実行する必要があり、本来の用途として必要な数に比べて、簡単な実装では約3倍の計算時間と検証時間がかかり、目的に特化した実装でも2.32倍以上の計算量が必要になる*2。後方互換性を必要としない新しい実装では、不必要な負荷を実行しないハッシュツリーの実装を検討する必要がある。

第三に、Satoshiのアルゴリズムは順序付きリストからツリーインデックスを構築することを前提としているため、ツリー内の全ての要素についてルートからリーフまで均一のパス長をもつバランスの取れたツリーをサポートするよう設計されている。一方、多くのアプリケーションでは不均衡なパス長を持つツリーを活かしている。特に短いパスが使用される可能性が高い場合により効果的だ。Satoshiのハッシュツリーのいくつかの要素を他の要素より短いパスにすることも可能だが、そのためのトリックはツリーのサイズに依存しあまり柔軟ではない。

これら３つの理由は、これらの問題を解決する新しいプロトコルで使用する標準的なマークルハッシュツリー構造を指定する際の正当性を提供する。このBIPではその構造について記述し、実装例を示す。

仕様

このBIPで定義されているマークルハッシュツリーは任意のバランスのバイナリツリーで、その末端のリーフノードはデータのdouble-SHA256ハッシュでラベル付けされ（そのフォーマットは本BIPの範囲外）、内部ノードはその子ノードのラベルのfast-SHA256 から生成された値でラベル付けされる。以下の図はアンバランスなハッシュツリーの例を示している。

AおよびB、Cはリーフラベルで、リーフに関連付けられたデータの32バイトのdouble-SHA256ハッシュである。NodeとRootは内部ノードで、そのラベルはそれぞれの子ノードのラベルのfast-SHA256ハッシュである。NodeはBとCを連結したfast-SHA256ハッシュでラベル付けされる。RootはAとNodeを連結したfast-SHA256ハッシュでラベル付けされ、このツリーのマークルルートである。子ノードが１つだけのノードは許可されない。

double-SHA256暗号学的ハッシュ関数は、任意の長さのデータをインプットとし、FIPS 180-4*3で指定されたSHA256ハッシュ関数を介してデータを実行し、length-extension attack（伸長攻撃）から保護するため同じハッシュを再度実行して32バイトのハッシュを生成する。

fast-SHA256暗号学的ハッシュ関数は２つのハッシュ値を取り、これらを連結して64バイトのバッファを生成し、 カスタム初期化ベクトル (IV)と、メッセージパディング無しでSHA256ハッシュ関数を1回実行する。結果は結合されたハッシュ値と内部ノードのラベルである32バイトのmidstate*4である。変更されたIVは、パス拡張攻撃に対する保護になる。fast-SHA256は2つの32バイトのハッシュに対してのみ有効な定義である。カスタムIVは、以下の16進エンコードされたバイト列について標準のSHA256を実行したmidstateを展開した後に生成される中間ハッシュ値である。

cbbb9d5dc1059ed8 e7730eaff25e24a3 f367f2fc266a0373 fe7a4d34486d08ae
d41670a136851f32 663914b66b4b3c23 1b9e3d7740a60887 63c11d86d446cb1c

このデータは9番目の素数である23の平方根の最初の512小数bitであり、結果得られるmidstateはfast-SHA256暗号学的ハッシュ関数のIVとして使われる。

static unsigned char _MidstateIV[32] =
        { 0x89, 0xcc, 0x59, 0xc6, 0xf7, 0xce, 0x43, 0xfc,
          0xf6, 0x12, 0x67, 0x0e, 0x78, 0xe9, 0x36, 0x2e,
          0x76, 0x8f, 0xd2, 0xc9, 0x18, 0xbd, 0x42, 0xed,
          0x0e, 0x0b, 0x9f, 0x79, 0xee, 0xf6, 0x8a, 0x24 };

fast-SHA256は2つの32バイトハッシュのインプットに対してのみ定義されているので、2つの特殊なケースがある。空のマークルツリーは許可されず、そういったツリーに対してはルートハッシュも定義されない。データが１つだけのマークルツリーの場合、そのルートハッシュはツリーの唯一のリーフノード自身の値と同じになる（パススルー操作でハッシュ計算が行われない）。

論拠

64バイトのデータをFIPS 180-4で指定されているSHA256でハッシュすると（メッセージパディングのため）2回の圧縮が実行され、double-SHA256を計算するのに3回の圧縮が実行される。このためfast-SHA256ハッシュ関数は、用途を特化したdouble-SHA256の実装より2.32倍高速に、通常のSHA256プリミティブを2回適用する実装より3倍高速に計算できる。同様にfast-SHA256のマークルルートの検証は、SatoshiがBitcoinで使用するdouble-SHA256より2倍以上高速に行える。さらにfast-SHA256の実装は一般的なSHA256の実装であり、パフォーマンスコストをかけずに汎用回路やコードへの再利用が可能だ。

fast-SHA256はインプットがハッシュ値で数値と長さが固定されているので、メッセージのパディングやダブルハッシュによる攻撃の影響を受けることはなく、安全に内部ノードのラベル付けを行うことができる。

fast-SHA256の初期化ベクトル（IV）はリーフハッシュや内部ノードのコミットメントが別のリーフハッシュと部分的に衝突するような上位レベルのプロトコルに対する攻撃を防ぐために変更されている。IVはカスタムIVをサポートしていない暗号ライブラリインタフェースとの互換性を保つため、カスタムIVやmidstateからのレジュームをサポートしていない場合、↑の2倍のパフォーマンスを犠牲にして標準のSHA256とmidstateの抽出を行い計算される。ハッシュされたデータは、ハッシュプリイメージが知られていないnothing-up-my-sleeve numberである。2〜19までの最初の8個の素数の先頭bitが既にSHA256自体の設定に使われている定数であるため、その次の9個めの素数23を選択した。次の素数を順番に使うことで一定の因子の再利用による弱点が導入される可能性を減らすことができる。

データ要素が１つしかないツリーのマークルルートハッシュは、何の変更もないリーフハッシュへの単純にパススルーで、スプリットプルーフの連鎖検証を可能にする。これは、Bitcoinスクリプトのプッシュ制限のような検証サイズに制限があるような検証環境において便利だ。連鎖検証により検証者は１つのプルーフを2つ以上に分割することができ、リーフは内部ノードの下に示され、内部ノードがルートの下に示される。データ要素が１つのみツリーにおいてパススルーハッシングでない場合だと、連鎖検証を使うのにチェーンのリンクの数と同じ最小パス数の要件が余計に必要になる。単一要素のパススルーハッシングは１つ以上の連鎖検証の代わりにゼロ長パスからなるNOPプルーフを使うことができ、それにより例えば固定された一連の４つの連鎖検証が長さ３以下のパスを検証できる。

Inclusion Proofs

マークルルートハッシュの使い方で重要なのは、オーダーlog（サイズ）のプルーフで、任意のデータが含まれていることをコンパクトに証明できることだ。このセクションでは、ある複数の要素がツリーに含まれていることを証明するプルーフの標準的なエンコード方法を定義する。

特定のルートを持つマークルツリーにあるハッシュのセットが含まれていることを証明するには次の４つの情報が必要になる。（この要素は既存のマークルツリーの場合と同じ）

1. マークルツリーのルートハッシュ
2. 検証されるハッシュ値。通常データ要素のdouble-SHA256で構成されるが、それか内部ノードのラベルかその両方。
3. ルートから対象のハッシュがあるノードへのパス（シリアライズされたバイナリツリー構造として表現される）。
4. それらのパスに含まれないブランチ（ノード）のハッシュ値

通常↑の最後の２つの要素（パスとパスを辿らないブランチのハッシュ）をまとめてプルーフと呼んでいる。

シリアライズする際は、まずプルーフ内の内部ノードの数Nを可変長整数（Varint）としてエンコードする。次にツリーの構造を、深さ優先で左から右、前順・先行順・前置順・行きがけ順で各内部ノードを走査する前提で、各ノードの構成をパックした3bit表現でエンコードする（ノード数Nに応じて(3*N + 7) / 8バイト消費する）。続いてスキップするハッシュの数（プルーフの中に含まれるハッシュ、プルーフで検証しないもの）は、可変長整数（Varint）でシリアライズされ、その後にプルーフで明かされるハッシュ自体が順番に続く。

以下の図のように８個の内部ノードの構成が可能だ。

この図では、DESCENDは"..."とラベル付けされた子グラフ要素で表されている別の内部ノードへの分岐リンクを意味する。SKIPはそのブランチに省略されたサブツリーのハッシュか要素のハッシュが含まれていることを意味し、このブランチのサブツリーのfast-SHA256ルートハッシュかデータ要素のdouble-SHA256ハッシュのどちらかがプルーフデータの中に含まれている。VERIFYはそのブランチにプルーフの検証に必要なwintessとして外部から提供されたハッシュが含まれていることを意味する。表形式にするとこれらのコード値は以下の通り。

コード	Left	Right
000	VERIFY	SKIP
001	VERIFY	VERIFY
010	VERIFY	DESCEND
011	DESCEND	SKIP
100	DESCEND	VERIFY
101	DESCEND	DESCEND
110	SKIP	VERIFY
111	SKIP	DESCEND

この３つのbitコードは3バイト毎に8つのコードが収まるようバイト列にパックされる。バイトを埋めていく順序は最上位bit0x80で始まり、最下位bit0x01で終わる。内部ノードの数が8の倍数でない限り、シリアライズした最終バイトは下位bitが余ることになり、この余りのbitには全てゼロがセットされなければならない。

ツリーのシリアライゼーションは自己分割であることに注意すること。ツリー構造を追跡することで、プルーフの校正者はパーサーがいつ最後の内部ノードに到達したかを知ることができる。プルーフ内にシリアライズされた内部ノードの数は、ツリー構造自体から推論されるノード数と等しくなければならない。同様に、SKIPハッシュの数はシリアライズされたツリー構造から推論することもでき、プルーフ内のハッシュの数と等しくなければならない。

（内部ノードが無い）シングルハッシュプルーフはN=0で、（内部ノードが無いので）ツリー構造もシリアライズされずSKIPハッシュの数は0または1のいずれか。

例

次のマークルツリー構造を考えてみよう。

この構造では6個の内部ノードがある。深さ優先で左から右、前順・先行順・前置順・行きがけ順で探索するとA→B→→D→F→C→Eの順に回る。３つのSKIPハッシュがあり、0x00... → 0x66... → 0x22...の順に回る。残りの４つのハッシュは実行時に提供されプルーフにより検証される。

	Byte 1	Byte 2	Byte3
Bits	76543210	76543210	76543210
Nodes	AAABBBDD	DFFFCCCE	EE------
Code	10111101	10000100	01000000

シリアライゼーションは内部ノードの数の可変長整数（Varint）で始まるので↑だと0x06、次にツリーのシリアライゼーション自体（↑だと0xbd8440）が続く。次のSKIPハッシュの数も可変長整数としてエンコードされ↑だと0x03、その後に３つのハッシュが順番に続く。結果101バイトのプルーフBase64で以下のようにエンコードされた値となる。

Br2EQAMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmREREREREREREREREREREREREREREREREREREREREREQ=

論拠

内部ノードの3 bitエンコードは、左右のブランチがそれぞれ｛DESCEND, SKIP, VERIFY｝のいずれかであるかを示す構成をエンコードすることができる。この他、除外された第９のパターンとして、左右のブランチが両方共SKIPであるパターンがある。

このパターンは検証のため許可されていない（そのブランチ自体へのSKIPと同じことであるため）。この２つのSKIPブランチを持つノードを不許可にすることで、プルーフのmalleabitiyの原因を排除している。

プルーフを検証するために必要なハッシュ計算の回数は、ハッシュの数（SKIPとVERIFYを合わせた数）より１つ少なく、内部ノードの数Nと等しい。可変長整数エンコーディングにはシリアライズされた数値も辞書順にソートされたものも数値順にソートされるという性質がある。最初にシリアライズされるのは内部ノードの数であるため、プルーフを辞書順にソートすることはプルーフの検証に必要な作業量でプルーフをソートする効果がある。

プルーフの検証のためのインプットとして必要なハッシュの数は、N+1からSKIPハッシュの数を引いたもので、ツリー構造を解析することなく素早く計算することができる。

シリアライズされたツリー構造のコーディングルールとパッキングルールは辞書比較を有効にするため選択された。もし完全に拡張されたツリー（SKIPが無く全てVERIFYの）を左から右に深さ優先で要素のリストをエンコードするとみなした場合、欠損している値のハッシュをSKIPし、SKIP,SKIPノードを再帰的にプルーニングすることでリストのサブセットのプルーフ抽出することができる。結果得られるシリアライズされたツリー構造を辞書順に比較することは、派生したプルーフによって検証されたオリジナルのリストからインデックスのリストを比較するのと同じことである。

内部ノードの数とSKIPハッシュの数はツリー構造から抽出可能であるため、プルーフ内の可変長整数は両方とも冗長で省略可能だ。しかし、そうするとシリアライゼーションと検証の両方で、デシリアライズの際にメモリ上に明示的にツリーを構築・保持する必要があるか、比較的複雑なツリー解析コードの複製が必要になる。そのため（単一ハッシュのエッジケースの場合も同様）、冗長だが内部ノードの数とSKIPハッシュの数を明示的にシリアライゼーションし、プルーフが有効であるためにはその２つの値がツリー構造から推測される値と一致しなければならない。これによりデシリアライズが簡単になり、検証のタイミングまでツリーの構築を遅らせることができる。これには対数時間の検証アルゴリズムが有効になるという追加のメリットがある。

Fast Merkle Lists

多くのアプリケーションではマークルツリーを使用してリスト内の要素についてのインデックス化やコンパクトなメンバーシップ証明を提供する。この仕組はいろんな長さのリストのための標準的な平衡木構造を構築するアルゴリズムを指定する。このアルゴリズムには、重複エントリーに関連する脆弱性を構造的に防止するため、Satoshiのアルゴリズムとは微細だが重要な点で違いがある。

1. まず任意のデータ文字列のリストがある。
2. リストの各要素をそれぞれdouble-SHA256ハッシュした値に置き換える前処理を行う。
3. リストが空の場合は、ゼロハッシュを返す。
4. リストに２つ以上の要素がある場合は
   • リストの隣接するエントリーを結合し、fast-SHA256ハッシュに渡す。リストの要素が奇数の場合、最後の要素をそのまま残す（これにより脆弱性を修正する）。このステップでN個のリストの要素をceil(N/2) 個のエントリーに減らす。
5. リストに残った最後のアイテムがマークルルートである。

このアルゴリズムはBitcoinで使われているマークルリストと２つの点で異なる。１つめは、内部ノードのラベル付けにdouble-SHA256でなくfast-SHA256が使われる。２つめは、奇数長のリストの最終エントリーは重複してハッシュされない。これはCVE-2012-2459につながった間違いだ。

実装

このBIPのマークルブランチの抽出と高速なマークルブランチの検証は以下のGithubのリポジトリで利用可能だ。

https://github.com/maaku/bitcoin/tree/fast-merkle-tree

このリポジトリにはこのBIPのアルゴリズムを使用してルート値の計算と任意ツリーのinclusion proofsの抽出および値のリストからツリーを構築するmerklebranch RPCと、２つ以上のマークルinclusion proofsを統合する（SKIPハッシュを別のproofから抽出したサブツリーに置き換える）ためのmergemerklebranch RPCが含まれる。

デプロイ

このBIPは、BIP-116（MERKLEBRANCHVERIFY）がソフトフォーク用のNOP拡張opcodeを使用してMerkle inclusion proof の検証をスクリプトに追加するために使用される。MERKLEBRANCHVERIFYのデプロイはこのBIPの内容を決定的にするだろう。BIP-116のデプロイ計画はそのBIPの本文に記載されている。

*1:bitcoind及びBitcoin-QTの0.6.2より前のバージョンにあったDoS攻撃の脆弱性で、マークルツリーのリーフに重複したトランザクションを配置してブロックハッシュを衝突させ、同じハッシュを持つ正当なブロックを受け入れられないようにする。

*2:2017年9月にPieter Wuilleとの個人的なコミュニケーションの結果、ハッシュ関数の各ステージのインプットが固定長であるという知識を利用することで、Satoshiのマークルツリー構造ハッシュ集約関数について、Wuille氏は64バイトデータのdouble-SHA256ハッシュの計算にかかる時間を22.7%短縮することができた

*3:Federal Information Processing Standard（FIPS） PUB 180-4

*4:SHA256はデータを64バイト毎のチャンクに分割し処理を行う。チャンク毎に、データを分割→拡張→圧縮という工程を経るが、この時の圧縮してできたデータがmidstateで、次のチャンクで圧縮処理をする際に使用される。

SIGHASH_FORKIDとfork idを使ったリプレイプロテクションの仕組み

8/1にBitcoin Cashが分岐した際、BTCとの間のリプレイアタックに対する保護の仕組みを組み込む必要があり、この時SIGHASHを利用する仕組みが導入された。

spec/replay-protected-sighash.md at master · Bitcoin-UAHF/spec · GitHub

最近分岐したBitcoin Gold（BTG）も同じ仕組みを採用したようだ。

SIGHASH_FORKID

通常トランザクションに署名する際には、トランザクションのどのスコープまで署名するか決めるのにSIGHASH TYPEと呼ばれるものをセットするようになっている↓

techmedia-think.hatenablog.com

基本となるSIGHASH_ALL、SIGHASH_NONE、SIGHASH_SINGLEの３つタイプにSIGHASH_ANYONECANPAYというフラグを組み合わせることで計6通りの署名スコープをセットできるようになっている。
（ほとんどのトランザクションはSIGHASH_ALLを使っている。）

フォークを識別するため、SIGHASH_ANYONECANPAYのように追加されたフラグがSIGHASH_FORKIDで以下の値がフラグとして決められている。

SIGHASH_FORKID = 0x40

HF後、このフラグがセットされていないトランザクションはBCHやBTGのブロックチェーン上では無効なトランザクションと判断される。尚、BTCのチェーンでは、セットされているSIGHASH_TYPEからSIGHASH_ANYONECANPAYを除去した結果、その値がSIGHASH_ALL(0x01) 〜 SIGHASH_SINGLE(0x03)の間でなければ署名のエンコードチェックでエラーになる。つまり、 SIGHASH_FORKID（0x40）フラグがセットされていればエラーになる。

署名スコープがSIGHASH_ALLでBCHやBTGのトランザクションの署名を作る際、そのSIGHASH TYPEは

SIGHASH_ALL(0x01) | SIGHASH_FORKID（0x40） = 0x41

になる。

実際にBitcoin Cashのトランザクション↓

https://www.blocktrail.com/BCC/tx/50c22f9cb1fbeec34fb9a77fdd54bcfa65c6ae65deebc6e06655867d0d659b3d

のインプットのscriptSigを見てみると↓

304502210085b726543e566fe2921f801f548e18bfb67662de920f0264bee6086e610af553022011103703f8cbc19c33c213e546da169434f3334c20f456fdf36fd2ea33fe4e1b41 
033489bdf777f135fa9ab0f31bd795a60a56d7daddc0ae18c6c1ad4d8589d2c72e

１つめの要素が署名で2つめの要素が公開鍵。署名の最後にはSIGHASH TYPEをセットする決まりなので、上記から41 = SIGHASH_ALL | SIGHASH_FORKIDになっていることが分かる。

Bitcoin Goldのトランザクションも↓

https://btgexp.com/api/getrawtransaction?txid=6673dd19df842c2777201718d95edca600f72de6bf508727604ddb0834212323&decrypt=1

41 = [ALL|FORKID]が適用されていることが分かる。

fork id

BCHもBTGもどちらもSIGHASH_FORKIDフラグが付与されているのは分かったが、これだけだとBTC⇔BCH,BTGのリプレイ保護にはなるけどBCH⇔BTG間のリプレイ保護にはならない。そのため共通のSIGHASH_FORKIDフラグとは別に各チェーンを識別するためのfork idが存在する。各チェーンのfork idの値は以下の通り。

チェーン	fork id
BCH	0
BTG	79（金の原子番号）

このfork idは、署名対象のトランザクションのダイジェストデータであるSIGHASHを生成する際に加味される。BCHもBTGもトランザクションのダイジェストデータを生成する仕様は、BTCのsegwitで導入されたBIP-143のルールに従う↓（BCHはsegwit導入はしていないけどこの仕様だけは導入している）

techmedia-think.hatenablog.com

オリジナルのBIP-143と唯一違うのは、このSIGHASHを生成する際に使用するSIGHASH TYPEの最上位bitにfork idを含める点だ。BCHのfork idは0なので実質何もする必要はないが、BTGの場合は79なので↓のようにSIGHASH TYPEにfork idのビット和を適用する必要がある。

hash_type = hash_type | (79 << 8)

これにより、BTGのトランザクションをBCHのチェーンで署名検証すると、署名対象データであるSIGHASHを生成する際に使用する値（fork id）が違っているので署名検証に失敗し、リプレイ攻撃から保護できるという仕組みだ。

以上のSIGHASH_FORKIDとfork idがリプレイプロテクションの仕組みなので、この仕組みを採用しているBTC派生チェーンで有効なトランザクションを作成する際は、

1. トランザクション署名時のSIGHASH TYPEにSIGHASH_FORKIDフラグを適用
2. SIGHASH生成時に使用するSIGHASH TYPEの最上位bitにfork_idを適用（BCHのみ省略可）

すれば、それぞれのチェーンで有効なトランザクションが生成できる。トランザクションについては他はBTCと変わらないみたいなので、各チェーンのコインを送金したい場合は↑のルールに則って署名すればいいだけ。

気になる点

• この仕組みはSIGHASHを使った仕組みなので、当然ながらOP_CHECKSIGやOP_CHECKMULTISIGを使用せず署名検証が必要のないスクリプトの場合、リプレイ保護は提供されない（まぁほとんどは署名検証をするスクリプトになっているということだろう）。
• SIGHASH_FORKIDは署名の最後のSIGHASH TYPEを確認すれば簡単に分かるが、fork idはSIGHASH生成時の１要素なだけなので署名データから明示的に確認する方法はなく、そのチェーンで有効なfork idなのかは署名検証するまで分からない。
• 署名検証のコストも考慮すると、ネットワークのservice bitsなんかで互いを識別して接続しないようにするとかした方が、各ノードが無駄なコストを負担しなくて済むように思うけどどうなんだろう？

Scriptless Scriptで実現するAtomic Swap

Atomic Swapといえば同じハッシュ関数とタイムロックの仕組みを持つブロックチェーンであれば、それぞれのチェーンの通貨をトラストレスに交換することができるプロトコルで、最近だとBitcoinやLitecoin、BitcoinとEthereumでAtomic Swapの事例が出てきている。

ハッシュのプリイメージとタイムロックの仕組みを使ったこのプロトコルの詳細は↓

techmedia-think.hatenablog.com

このプロトコルでは、各チェーンで以下のようなスクリプトにコインをロックしている。

IF
  2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFY
ENDIF

↑はBitconのスクリプト言語だが、Ethereumでは同様の機能を持つContractを実装することになる。

ハッシュのプリイメージとタイムロックを使うこのプロトコルには、２つのチェーンにおいて同じプリイメージ及びそのハッシュを使用しているのでチェーン間のトランザクションがリンクできるというプライバシーの課題がある。MASTが利用可能になれば取引の当事者が協調することでこの課題を解消する方法もあるが、こういったハッシュのプリイメージを使用するスクリプトを使わずに暗号技術を使ってAtomic Swapを実現するScriptless Scriptというアプローチがある。

スクリプト無しでどうやってAtomic Swapを行うかは、Scaling Bitcoin 2017でもScriptless Scriptsについて話をしたBlockstreamのAndrew Poelstraが、以下のドキュメントに書いている。

github.com

内容についてざっと見てみる。

Schnorr署名とAdaptor Signature

楕円曲線のジェネレータをGとし、Hをビット文字列の空間から（Gの位数を法とする整数である）スカラーグループにマッピングするハッシュ関数としたとき、公開鍵Pを有するメッセージmのSchnorr署名は以下の式を満たす(s, R)のペアになる。

sG = R + H(P || R || m)P

これに関連するAdaptor Signatureは以下の式を満たす(s', R, T)として定義される。

s'G = T + R + H(P || R || m)P

Schnorr署名(s, R)とAdaptor Signature(s', R, T)から（それぞれRが同じであることに注意）、Tの離散対数をs' - sで計算することができる。上記の式を減算すると(s' - s)G = Tになるため。

同様に、Adaptor Signature(s', R, T)とT = tGとなるtが与えられると、s = s' - tでSchnorr署名(s, R)を計算することができる。

公開鍵Pを有するAdaptor Signature(s', R, T)が与えられると、同じP及びRを有するSchnorr署名の知識はTの離散対数の知識と等しいと結論付けることができる。

このAdaptor SignatureがAtomic Swapのハッシュのプリイメージの代わりに使われる。

Schnorr署名のマルチシグ

Schnorr署名には複数の署名を集約することができる特性がある。公開鍵PとQを持つ２人の当事者が対話的にPとQのマルチシグを作成することが可能だ。署名のコンポーネント(s, R)は、両当事者の提出した署名鍵の合計になる。まず最初に両当事者は署名で使用するRの値について同意し、続くステップで各当事者がそれぞれの署名鍵を提供しsを作る。

スクリプトレスなAtomic Swapのプロトコル

スクリプトレスなAtomic Swapは↑のSchnorr署名のマルチシグとAdopter Signatureを組み合わせたプロトコルになる。

アリスはAチェーンに、ボブはBチェーンにコインをそれぞれ持っており、それぞれのチェーンのコインをアトミックに交換したい場合、以下の手順でAtomic Swapを行う。

1. まずアリスとボブはそれぞれコインを持っているチェーンで、使用するには両者の署名が必要なマルチシグのアウトプットにコインを入れる。またこの時、最終的にコインを償還する際の署名に使用するRの値についてお互いに合意する。
2. 続いてアリスはランダムな値tを生成し、T = tGを算出する。続いてマルチシグの署名値のsを作成するためのアリスの署名鍵を渡す代わりにAdaptor Signature(s', R, T)を生成して、ボブに送る。（T + R + H(P || R || m)PのPの部分はマルチシグなので、おそらくアリスの公開鍵とボブの公開鍵を結合したものになる）
3. ボブは受け取ったAdaptor Signatureを検証し問題なければ（各チェーンのAdaptor Signatureで同じTが使われている＝離散対数が同じことをを確認する）、マルチシグの署名データsに必要な自分の署名鍵を明らかにする。
4. アリスはボブから受け取った署名鍵と自分の署名鍵を組み合わせてsを導出し、マルチシグの署名(s, R)を完成させる。それをパブリッシュしてコインを入手する。
5. ボブは手順2でアリスから受け取ったAdaptor Signatureと手順4でアリスが公開した署名からシークレットtを計算する（Schnorr署名とAdaptor SignatureからTの離散対数tを計算できる）。算出したtを使ってアリスの署名鍵を計算する。
6. ボブは計算したアリスの署名鍵に自分の署名鍵を加えて署名を完成させ、その署名でコインを入手する。

※ 手順2でアリスからAdaptor Signatureが送られてこなかったり、2つのAdaptor SignatureのTが違っていたり、手順4でアリスがトランザクションをブロードキャストしない場合、予めlocktimeを設けていた払い戻し用のトランザクションをブロードキャストして自分のコインを取り戻す。

という手順でSchnorr署名のマルチシグとAdaptor Signatureを利用することで、スクリプトを書くことなくクロスチェーンのAtomic Swapを行うことができる。

この時ブロックチェーンに記載されるのはSchnorr署名のデータのみであるため、アリスとボブの間でAtomic Swapが行われたことを他のユーザーが検知することはできず、プライバシーに優れている。

↑のプロトコルはAtomic Swapを行う各チェーンで同じ楕円曲線を使用する前提になっているが、Scaling Bitcoin 2017でのAndrew Poelstraのセッションでは今後異なる楕円曲線間（Bitcoinのsecp256k1とMoneroのed25519など）のスワップのサポートを追加していくとのこと。

Andrew Poelstraの記事を読むことで、Scriptless Scriptの仕組みがふんわりと分かった気がする。Schnorr署名は単純に署名を集約してサイズ削減するだけでなく、こういった暗号学的なトリックに使うことができるのは面白い。バックボーンの原理についてはよく分かってないので勉強しないとなー。

OpenSCでマイナンバーの登録情報を確認してみた

OpenSCにマイナンバーカード（JPKI）の対応がマージされていたので、OpenSCを使ってマイナンバーカードの登録情報を確認してみる。

github.com

使用したカードリーダーは↓でMacでも認識できた。

amzn.to

カードに登録されているオブジェクトのリスト確認

まずカードに登録されているオブジェクトを確認してみる。

$ pkcs15-tool --dump
Using reader with a card: Gemalto PC Twin Reader
PKCS#15 Card [JPKI]:
    Version        : 0
    Serial number  : 00000000
    Manufacturer ID: JPKI
    Flags          : 
PIN [User Authentication PIN]
    Object Flags   : [0x12], modifiable
    ID             : 01
    Flags          : [0x12], local, initialized
    Length         : min_len:4, max_len:4, stored_len:0
    Pad char       : 0x00
    Reference      : 1 (0x01)
    Type           : ascii-numeric
    Tries left     : 3

PIN [Digital Signature PIN]
    Object Flags   : [0x12], modifiable
    ID             : 02
    Flags          : [0x12], local, initialized
    Length         : min_len:6, max_len:16, stored_len:0
    Pad char       : 0x00
    Reference      : 2 (0x02)
    Type           : ascii-numeric
    Tries left     : 5

Private RSA Key [User Authentication Key]
    Object Flags   : [0x1], private
    Usage          : [0x4], sign
    Access Flags   : [0x1D], sensitive, alwaysSensitive, neverExtract, local
    ModLength      : 2048
    Key ref        : 1 (0x1)
    Native         : yes
    Auth ID        : 01
    ID             : 01
    MD:guid        : c5a0a252-9d2d-eb60-fec0-41b4fbd722a2

Private RSA Key [Digital Signature Key]
    Object Flags   : [0x1], private
    Usage          : [0x204], sign, nonRepudiation
    Access Flags   : [0x1D], sensitive, alwaysSensitive, neverExtract, local
    ModLength      : 2048
    Key ref        : 2 (0x2)
    Native         : yes
    Auth ID        : 02
    ID             : 02
    MD:guid        : e1bc1dae-59f1-16ab-b43f-9dafbb2acc9b

Public RSA Key [User Authentication Public Key]
    Object Flags   : [0x0]
    Usage          : [0x0]
    Access Flags   : [0x2], extract
    Key ref        : 1 (0x1)
    Native         : yes
    Path           : 000a
    ID             : 01

Public RSA Key [Digital Signature Public Key]
    Object Flags   : [0x0]
    Usage          : [0x0]
    Access Flags   : [0x2], extract
    Key ref        : 2 (0x2)
    Native         : yes
    Path           : 0001
    ID             : 02

X.509 Certificate [User Authentication Certificate]
    Object Flags   : [0x0]
    Authority      : no
    Path           : 000a
    ID             : 01
    Encoded serial : 02 03 1C3301

X.509 Certificate [Digital Signature Certificate]
    Object Flags   : [0x1], private
    Authority      : no
    Path           : 0001
    ID             : 02

X.509 Certificate [User Authentication Certificate CA]
    Object Flags   : [0x0]
    Authority      : yes
    Path           : 000b
    ID             : 03
    Encoded serial : 02 01 01

X.509 Certificate [Digital Signature Certificate CA]
    Object Flags   : [0x0]
    Authority      : yes
    Path           : 0002
    ID             : 04
    Encoded serial : 02 01 01

• JPKIのカードオブジェクト
• 認証用のPIN
• 署名用のPIN
• 認証用のRSA秘密鍵
• 署名用のRSA秘密鍵
• 認証用のRSA公開鍵
• 署名用のRSA公開鍵
• 認証用のX.509証明書
• 署名用のX.509証明書
• 認証用の認証局のX.509証明書
• 署名用の認証局のX.509証明書

が登録されていることが分かる。

証明書の確認

↑のうち、ユーザーの証明書は認証用のX.509証明書と署名用のX.509証明書。

まずユーザー認証用のX.509証明書の内容を確認してみる。

$ pkcs15-tool --read-certificate 1 > user-auth.pem
Using reader with a card: Gemalto PC Twin Reader
$ openssl x509 -text -noout -in user-auth.pem

opensslコマンドで証明書の内容を確認できる。

X509v3 Issuer Alternative Name: 
   DirName:/C=JP/O=\xE5\x85\xAC\xE7\x9A\x84\xE5\x80\x8B\xE4\xBA\xBA\xE8\xAA\x8D\xE8\xA8\xBC\xE3\x82\xB5\xE3\x83\xBC\xE3\x83\x93\xE3\x82\xB9
X509v3 CRL Distribution Points: 
   DirName:/C=JP/O=JPKI/OU=JPKI for user authentication/OU=CRL Distribution Points/OU=Fukuoka-ken/CN=Iizuka-shi CRLDP

発行者は"公的個人認証サービス"で、CRLのDistribution Pointsは福岡県飯塚市になってる。各市町村が証明書の失効リストを管理していることになる？

この認証用の証明書には個人情報は掲載されていない。

個人情報が含まれているのは、署名用のX.509証明書で、個人の氏名、生年月日、性別、住所といった本人確認に必要な情報が含まれている。続いてこの証明書の内容を確認してみる。

先程と同様にpkcs15-toolで確認しようとすると

$ pkcs15-tool --read-certificate 2 > user-signature.pem
Certificate read failed: Security status not satisfied

とエラーになる。どうやらこっちはPINでロックされてるみたい。

なので--verify-pinオプションでPINの検証をする。この時、署名用のPINのIDは02なので--auth-idオプションでそのPINを指定して実行する。すると署名用のPINの入力を求められるので入力すると署名用のX.509証明書が表示される。

$ pkcs15-tool --read-certificate 2 --verify-pin --auth-id 02
Using reader with a card: Gemalto PC Twin Reader
Please enter PIN [Digital Signature PIN]: 
-----BEGIN CERTIFICATE-----
...
-----END CERTIFICATE-----

証明書のX509v3 Subject Alternative Nameに個人情報が記載されているが、UTF-8で記載されているこのデータはopensslコマンドで確認しても

othername:<unsupported>, othername:<unsupported>, othername:<unsupported>, othername:<unsupported>, othername:<unsupported>, othername:<unsupported>

となるだけなので、別途OpenSSL::ASN1などでパースする必要がある。

rubyでパースするサンプル↓

require 'openssl'

cert = OpenSSL::X509::Certificate.new File.read('証明書のパス')
subject_alt_name = cert.extensions.find {|e| e.oid == 'subjectAltName'}

asn_san = OpenSSL::ASN1.decode(subject_alt_name)
asn_san_sequence = OpenSSL::ASN1.decode(asn_san.value[1].value)

asn_san_sequence.each do |asn_data|
  key = asn_data.value[0].value
  value = asn_data.value[1].value[0].value
  puts "#{key}: #{value}"
end

証明書に記載されている個人情報が確認できる。

最後に

公的認証された証明書やキーペアを日本国民であれば誰でも手に入れられ、それらを利用すれば各サービス毎の煩わしい本人確認のプロセスは簡略化できると思うので、今後そういったサービスが充実していくのに期待したい。まぁカードの場合リーダーとセットで不便なので、スマホなどへのインポートができるとさらに便利になると思う。

まぁ、本当に秘密鍵を知ってるは本人だけなのか？という疑念はあるけどなー。マイナンバー登録時に鍵にアクセスする際のPINの登録はするけど、その際に秘密鍵作ってるわけではないし。