読者です 読者をやめる 読者になる 読者になる

Develop with pleasure!

福岡でCloudとかBlockchainとか。

Strong Federationsの概要

Blockstreamが今年に入って公開したStrong Federationsのホワイトペーパーに記載されている技術仕様についてを読んでみた↓

https://arxiv.org/pdf/1612.05491v2.pdf

もともとBlockstreamのサイドチェーンのホワイトペーパーのFederated Pegでは、信頼できる連合の職員がメインチェーンとサイドチェーン間のコインのロック/アンロックをする構成になっている↓

techmedia-think.hatenablog.com

Strong Federationというのは、このFederated Pegに加えて、Federated Blocksigningという仕組みを追加で定義した内容みたい。

Federated Pegの流れ

Federated Pegの基本的な流れが↓

  1. ユーザーは自分のアセットをメインチェーン上で特殊なアドレス宛に送付する。このアドレスはサイドチェーンがアセットが返却されたと通知されるまでアセットをロックしておくよう設計されている。
  2. ユーザーはFederated Pegのinチャネルを使って、メインチェーンでアセットが凍結されていることを示す情報をサイドチェーンに埋め込み、サイドチェーン上でそのアセットを利用できるよう要求する。
  3. ユーザーがメインチェーンでロックしたアセットと等価なサイドチェーン上のアセットがアンロックもしくは新規作成され、ユーザーはそのアセットを持ってサイドチェーンに参加できるようになる。
  4. ユーザーがサイドチェーン上のアセットもしくはアセットの一部をoutチャネルを介してメインチェーン上に戻したい場合は、メインチェーン上の出力情報をサイドチェーンに埋め込む。
  5. Strong Federationが合意すると、Federated Pegはサイドチェーンで示された数量分、メインチェーン上のアセットの凍結を解除する。

Strong Federationを使ったサイドチェーンの改善

Bitcoinにおいては、ブロックへの署名=マイナーと呼ばれる署名者のセットを使った動的メンバーシップマルチパーティ署名と捉えることができる。ただBitcoinの場合(10分という)レイテンシーの問題があり、Federated Pegのモデルでは、この動的メンバーシップマルチパーティ署名の部分を、固定メンバーによるマルチシグで代替してサイドチェーン側のブロックの署名(ブロックの作成)をしている。

Strong Federationというのは、連合のメンバーがメインチェーンとサイドチェーンの間のプロトコルアダプタとして機能するようフェデレーションされたサイドチェーンで、以下の特徴がある。

  • 第三者の許可を必要とせずにチェーン間の資金移動が可能
  • フェデレーションが失敗した場合にはメインチェーン上に資金を戻す仕組みがある

連合のメンバーも、ユーザーの資金を直接コントロールすることはできない。

Strong Federationのネットワークオペレーターは、2種類の職員から構成されている。職員というのは、特定の条件が満たされた場合に定義された操作を機会的に実行するエンティティのこと。セキュリティ強化のため、特定の操作は複数のエンティティ間で分担され、あるエンティティが攻撃されてもその損害を限定的にできるように設計されている。Strong Federationでは、職員がブロックチェーン間のアセットの移動のコントロールとサイドチェーン側のコンセンサスルールの実行権限を持っている。この職員は以下の2種類に分けられる。

この2つのコンポーネントは独立していてもいい。Blocksignerはブロックチェーンのコンセンサスを生成し、サイドチェーンの台帳を作っていく。Watchmenはブロックチェーン間でアセットを移動するときだけオンラインになればいい。(極端な例では1日1回オンラインになって、溜まったアセットの移動要求を処理するのでも良い)

Strong Federationsの技術要素

Strong Federationをサポートするには、Federated PegとFederated Blocksigningの2つのタイプのフェデレーションを開発する必要がある。

Federated Peg

サイドチェーンのホワイトペーパーでは、Bitcoinのコンセンサスルールを変更することなく、サイドチェーンを展開する方法について提案されている。ホワイトペーパーでは、サイドチェーンは5人のうち3人の職員が同意してブロックへの署名・検証、ペグを行うモデルになっていた。

Federated Pegは職員を使って2つのチェーン間でアセットを移動する仕組み。職員は少なくとも2つのチェーンを監視し、チェーン間のアセットの転送を検証する。Strong Federationの基準を満たすため、地理的及び管轄的に分散されたサーバを使用して職員のネットワークは作られる。

Federated Pegのメンバーは、Bitcoinとサイドチェーンのノードを実行するセキュアなサーバーと、クロスチェーンのトランザクションを作成、管理するソフトウェアを操作する。各サーバは暗号鍵とその署名を管理するハードウェアセキュリティモジュールを持つ。モジュールの仕事は、主にネットワークのセキュリティを守ることで、compromiseを検知すると全ての鍵を削除し、設計通りネットワークをフリーズさせる。1人もしくは少数の職員が攻撃された場合でも、その耐タンパー性のあるハードウェアに侵入されていても、他の職員に影響が無ければシステムは影響を受けない。federated pegのシステムを改竄するためには、主要なBlocksignerWatchmenのcompromiseが必要になる。それでもブロックチェーンのデータはノード間で常に共有されているため、すぐに改竄は発覚する。不適合なブロックが公開されるとすぐにBlocksignerの過半数がcompromiseであることが分かる。過半数Watchmen が安全であれば、サイドチェーン上のアセットがありながらメインチェーン上でアンロックされれることはない。

ビザンチン耐性

Bitcoinのマイニングスキームの最も重要な点の1つとしてビザンチン耐性が挙げられる。悪意あるマイナーが過半数を超えない限り、履歴の改竄やトランザクションの削除などは行えない。

Bitcoinは、全てのマイナーが平等な立場で参加でき、大多数のハッシュパワーに裏付けされたチェーンの有効性によってこれを実現している。過半数のハッシュパワーを持たない攻撃者は履歴を書き換えることはできず、計算リソースを投入しても無駄になる。これによりマイナーに正直な多数派に加わることを促し、攻撃者の負担を大きくしている。しかしこの仕組みでも、10分に1度のブロック生成でネットワークの遅延によりチェーンの一時的なフォークが発生し、チェーンの再編成リスクは残る。

Strong Federationsにおけるコンセンサス

職員の経済的な利益と連合の正しい機能と一致させることが重要で、重要な価値を持つ商業的なサイドチェーンをサポートするのにボランティアの無作為な組み合わせに頼るのは明らかに間違いだろう。フェデレーションは各参加者がフェデレーションによって保持されているのと同程度の価値を持つ場合に最も安全になる。これはビジネスでよく見られるパターンで、インセンティブはエスクロー、機能的な配分または保証債権や保険証券などの外部の法的構成物を通じて調整できる。

Strong FederationsにおけるBlocksigning

Strong Federationsでは、低レイテンシーの実現と、特定の敵対する少数派によるチェーンの再編成リスクを回避するためBitcoinにおける動的なマイナーセットを固定の署名者のセットに置き換える。プライベートチェーンと同様PoWは、スクリプトの検証に置き換えられる。連合ではこのスクリプトk-of-n のマルチシグネチャスキームで実装する。このスキームでは、ブロックの署名に個の鍵の内のk個の署名を必要とする。このようにしてBitcoinビザンチン耐性をエミュレートすることができ、悪意ある署名者が少数の内はシステムに影響を与えることはない。

以下のFig4が、Strong Federationsにおけるコンセンサスの流れ

f:id:techmedia-think:20170523125858p:plain

で、以下のフェーズで構成される。

  1. ブロック候補を作成するBlocksignerはラウンドロビンで決まる。ラウンドロビンでマスターとなったBlocksignerは候補ブロックを作成して他のBlocksignerに提案する。
  2. マスターではないBlocksignerは、受信した候補ブロックに賛成する意思表示を行う。
  3. 閾値Xを満たす場合、各Blocksignerはブロックに署名する。
  4. 閾値Yを満たす場合、ブロックは受け入れられ、ネットワークにブロードキャストされる。
  5. 次のブロックは、ラウンドロビンで次のBlocksignerにより提案される。
セキュリティの改善

Bitcoinではブロックの生成は確率的に行われるため、最近のブロックではチェーンの再編成の傾向がある。Strong Federationのブロックの生成は確率的ではなく、固定された一連の署名者によって行われるため、決して再編成されることはない。これによりトランザクションの確認に要する時間はだいぶ短縮される。

ビザンチン耐性は、2つの一般的なケースの攻撃に対する保護になる。1つはノードのクリティカルな部分がネットワークから分離され可用性が失われるケース。もう1つは攻撃者による多数のノードが操作され、完全性が失われるケース。

Strong FederationのBlocksigningは、最大2k − n − 1の攻撃者に対して堅牢である。つまり2k − nビザンチン攻撃者だけが競合する同じブロック高のブロックに署名し、ネットワークをフォークすることができる。例えば、5-of-8閾値の場合は1人の攻撃者に対するビザンチン耐性があり、6-of-8の場合は3人の攻撃者に対するビザンチン耐性がある。

一方、n − k + 1の署名者が署名に失敗すると、ブロックは生成されない。従って閾値kを増やすとフォークに対する保護は強化されるが、署名者が署名できない場合のネットワークの復元力は低下する。

所感

  • PoWを固定した署名者のセットを使ったマルチシグに置き換えて、悪意ある署名者が少数であればビザンチン耐性があるみたいな解釈は成り立つの?固定してる時点permittedなんじゃないの?と思ってしまう。
  • LiquidがこのStrong Federationsを最初に採用したプロダクトになるみたいね。
    blockstream.com

リプレイ攻撃を防ぐOP_CHECKBLOCKATHEIGHTを定義したBIP-115

EthereumがETHとETCにハードフォークした際に問題となったリプレイ攻撃

ブロックチェーンでハードフォークが発生すると、ハードフォークの前に持っていた通貨は、分岐した両方のチェーンで有効な状態になる。仮にAコインがハードフォークしてAコイン(元のコイン)とBコイン(フォークしてできたチェーンのコイン)になったとする。
ハードフォークした直後は、ハードフォーク前にAコインを持っていたユーザーは、同量のBコインも持っている状態になる。その後Aコインを使って買い物をする場合、ユーザーはECサイトにAコインを支払うトランザクションをAのネットワークにブロードキャストする。このトランザクションはBのネットワークでも有効なトランザクションなので、ユーザーとは別に悪意ある誰かがこのトランザクションをBのネットワークにブロードキャストするとユーザーがもっていたBコインもBのチェーンのECサイトのアドレス宛に送られてしまう。これをリプレイ攻撃という。

BIP-115ではこのリプレイ攻撃を防止する仕組みとして、新しいopcode = OP_CHECKBLOCKATHEIGHTを導入し、特定のブロックチェーンでのみ有効なトランザクションを構築する方法を提案している↓

bips/bip-0115.mediawiki at master · bitcoin/bips · GitHub

仕様

OP_CHECKBLOCKATHEIGHTは既存のOP_NOP5opcodeを再定義する。

このopcodeは以下のように動作する。

  1. スタック上の要素数が2未満の場合、スクリプトは失敗する。
  2. スタックの一番上の要素が32bitのCScriptNumとして解釈できない場合、スクリプトは失敗する。
  3. スタックの一番上の要素はブロック高(ParamHeight)として解釈される。
  4. このスクリプトを実行しているブロックチェーンに、ParamHeightで指定したブロック高のブロックが存在しない場合、スクリプトは失敗する。
  5. ParamHeightがチェーン内の52596ブロックより深い(マイナスを含む)を指定していた場合、opcodeは正常に完了し、スクリプトは続きの処理を実行する。
  6. スタックの上から2つめの要素は、ブロックハッシュ(ParamBlockHash)として解釈される。
  7. ParamBlockHashが28バイトより大きい場合、スクリプトは失敗する。
  8. ParamBlockHashがParamBlockHashで指定したブロックのブロックハッシュの後半部分と一致しない場合、スクリプトは失敗する。

上記でスクリプトが失敗しなければ、そのまま残りのスクリプトが実行される。

デプロイ

このBIPは、cbahという名称で、BIP-9のversion bitsを使ってデプロイされる。

使用するbitやデプロイの開始時間、タイムアウトはまだ定義されていない。

動機

二重使用からの安全な復元

状況によっては、ユーザーが受け取ったビットコインについて、ブロックに格納される前に使いたい(Tx B1)ケースがある。ただこの場合、ビットコインを送信したトランザクション(Tx A1)が二重使用されているものであれば、ウォレットは必要に応じてTx A1を使用するトランザクションを再発行する(Tx B2)必要がある。二重使用のトランザクション(Tx A2)がウォレットが受信した場合、Tx A1を入力にするTx B1でなく、新しいOutpoint(Tx A2)を使うTx B2を作り署名する必要がある。しかし二重使用がそのウォレットに送られないケースであれば、現状はこの二重使用をリカバリする方法は無い。

OP_CHECKBLOCKATHEIGHTを追加することで、ウォレットはTX A2が含まれたブロックを検知した場合、Tx B2を作成しこのリスクを排除できる。

ブロックチェーンが分岐した際のリプレイ攻撃への対処

ハードフォーク等によりブロックチェーンが分岐した場合、どちらかのチェーンで有効なUTXOを送金するトランザクションをブロードキャストした際、別のチェーンでも同じ内容の送金するトランザクションが発生する(リプレイ攻撃)ようなことが無い仕組みが望ましい。

こういったリプレイ攻撃が起きないことは、分岐したチェーンのどちらかにしか存在しないブロック(ブロックハッシュ)を選択し、OP_CHECKBLOCKATHEIGHTを使ってそのブロックがあるチェーンでしか使用できないようUTXOを固定することで保証できる。

ウォレットのベストプラクティス

チェーンが再編成された際に不要なコンフリクトが発生しないよう、ウォレットはラスト100ブロックを指定しないこと。やむを得ず直近のブロックを使う場合は、ネットワークを注意深く監視し、フォークが発生しブロックハッシュが異なるブロックが正になったら、新しいブロックハッシュを使ってトランザクションを再作成する必要がある。そのためセキュリティポリシーに競合しない限り、ウォレットは固定したブロックのconfirmationが少なくとも100になるまで、トランザクションの再作成に必要な秘密鍵をメモリ上に保持する必要がある。

通常の使用では、ウォレットはParamBlockHashを16バイトで指定する必要がる。

論拠

トランザクションのロックタイムとどう違うの?

  • ロックタイムはトランザクションが有効になるまでの時間orブロック高を指定する。一方OP_CHECKBLOCKATHEIGHTは特定のブロックのブロックハッシュを指定する。

なぜブロック高は相対的なものでなく絶対的な値なの?

  • 相対的なブロック高は、N+1ではなくNで有効なトランザクションを作成することができる。これは、Bitcoinで慎重に回避され、指定したブロックが再編成されると、悪意の無いトランザクションは後のブロックを簡単に再確認できる。

どうして52596より前のブロックが検証されないの?

  • 全てのブロックヘッダを永遠に保持し続けないといけないような状況を回避するため。52596ブロックのブロックヘッダのサイズは4MB。
  • より深いブロックを指定したい場合は、そのブロックに依存するより最近のブロックを指定すればいい。
  • 関心のある全てのブロックチェーンで共通のUTXOを二重使用する時間は1年あれば充分。
  • より深くチェックするようにするのはソフトフォークでできるけど、より浅くしたい場合はハードフォークになる。

ParamBlockHashが完全なブロックハッシュでなくブロックハッシュの一部なのはなぜ?

  • チェーンの分割で、リプレイ攻撃を避けるためには数バイトチェックするので充分。
  • 完全なブロックハッシュを使うのに比べてブロックチェーンのディスクスペースの節約になる。
  • OP_LESSTHAN)のようなopcodeと1バイトと組み合わせて使用することで、オンチェーンの gambling logicを有効にできる。

ParamBlockHashの先頭が0の場合はどうなる?

  • 先頭が0の場合は、実際のブロックハッシュと比較する必要がある。
  • 余分なスペースが問題にならないよう、先頭の0が充分な精度で必要になることはない。
  • 全てのブロックハッシュは29バイトより小さいので、ParamBlockHashは28バイトより大きくなることはない。

前のブロックと同じように最近のブロックをチェックするのはなぜ安全なのか?

  • ブロックチェーンが再編成された場合に必要に応じて行うこと。
  • これにより再編成によって無効になるトランザクションを作成できるが、同じことは二重使用トランザクションを作成する際に行われている。

後方互換

OP_NOP5はこのような将来の拡張のため、全てのマイナー、ポリシーによって禁止されなければならず、そのため古いマイナーは新しいルールの下で無効なブロックを作ることはない。しかし攻撃の一部としてそのような無効ブロックを受け入れることがないよう、アップグレードする必要がある。

古いノードは、同じ拡張性の理由からこのopcodeを使用したトランザクションをリレーしない可能性もあるが、ルールをブロックの外側のコンテキストで検証できないため重要なことではない。

参照実装

https://github.com/bitcoin/bitcoin/compare/master…luke-jr:cbah

まとめ&所感

  • 新しくOP_CHECKBLOCKATHEIGHTというopcodeが追加される。
  • OP_CHECKBLOCKATHEIGHTはスタック上にブロック高(ParamHeight)とブロックハッシュの一部(ParamBlockHash)という2つ要素を引数として取る。
  • OP_CHECKBLOCKATHEIGHTは、指定されたブロック高(ParamHeight)のブロックハッシュの後半がParamBlockHashと一致するか評価し、一致しない場合、スクリプトの評価は失敗する。
  • チェーンが分岐すると分岐以降、2つのチェーンで同じブロック高のブロックハッシュが全く同じになることは基本的にないので、OP_CHECKBLOCKATHEIGHTでブロックハッシュを評価することで、必ずどちらかのチェーンでしか利用できないUTXOを作ることができるようになると。
  • スクリプトの評価の際に過去のブロックのデータ参照にいくようなスクリプト組むのありなのかー。
  • SPVノードもブロックヘッダはダウンロードしてるから、フルノードと同様チェックは可能か。
  • 二重使用からの復元が回避できてる理由と、後方互換性のリレーしない問題の大丈夫な根拠がイマイチよく分からない。

Segwitのアドレスフォーマットを定義したBIP-173

取り下げられたSegwitのアドレスフォーマットを定義したBIP-142↓

techmedia-think.hatenablog.com

に変わって、新しい仕様でSegwitのアドレスフォーマットを定義したBIP-173が登録されてたので見てみる↓

bips/bip-0173.mediawiki at master · bitcoin/bips · GitHub

イントロダクション

概要

このBIPでは、チェックサムが付与されたBase32フォーマットBech32と、Bech32を使ったsegwitのネイティブ出力(P2WPKHとP2WSH)のアドレスの標準について定義している。

Copyright

このBIPは二条項BSDライセンス下にある。

動機

これまでBitcoinは、ダブルSHA-256をトランケートしたチェックサムを付与したBase58アドレスを使ってきた。BIP-13で定義されたPay-to-script-hash (P2SH)も同様の仕組みを採用している。しかし文字セットとチェックサムアルゴリズムには以下のような制限がある。

  • Base58は英数字モードが使えないため、QRコードで多くのスペースを必要とする。
  • Base58では大文字小文字が混ざってるので、確実に書き留めたり、モバイルキーボードで入力したり、大きな声で読み上げるのには不向き。
  • ダブルSHA-256のチェックサムは遅く、エラー検出の保証はない。
  • エラー検出に関する研究のほとんどは、character-setのサイズに対してのみ行われており、Base58は対象ではない。
  • Base58のデコードは煩雑で比較的遅い。

Segregated Witness(Segwit)の提案には、新しい種類の出力(BIP-141参照)と、その2つの例(P2WPKHP2WSHなどBIP-143参照)が含まれている。この2つの機能はP2SHでネストすることで、Segwitに対応していない古いクライアントでも間接的に利用することができるが、セキュリティやトランザクションサイズの最適化を考慮するとネストせずに直接使用したほうがいい。このBIPではネイティブのwitness出力(P2WPKHとP2WSH)のための新しいアドレスフォーマットを提案する。

このBIPは以前議論されたBIP-142を置き換えるものである。

サンプル

公開鍵 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798を使用したアドレスの例が↓P2WSHはkey OP_CHECKSIGというスクリプトを使用した場合の例。

  • MainnetのP2WPKH
    bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4
  • TestnetのP2WPKH
    tb1qw508d6qejxtdg4y5r3zarvary0c5xw7kxpjzsx
  • MainnetのP2WSH
    bc1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3qccfmv3
  • TestnetのP2WSH
    tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7

仕様

まず最初にBech32と呼ばれるBase32フォーマットのチェックサムのについて説明し、続いてそれを使用したSegregated Witnessアドレスについて定義する。

Bech32

Bech32の文字列は最大90文字で、以下の要素で構成される↓

  • human-readable part
    読み手に関連するデータの種類やその他の情報を伝えることを意図した要素。有効性はアプリケーションによるが、33〜126の値の範囲のASCII文字に制限されている。
  • sepalator
    常に"1"。human-readable partに1が含まれている場合は、文字列の最後の1がセパレーター。
  • data
    少なくとも6文字で、"1"、"b"、"i"と “o"を除く英数字で構成される。

以下の表はdata部のデータを文字列から数値に変換するための変換表

0 1 2 3 4 5 6 7
+0 q p z r y 9 x 8
+8 g f 2 t v d w 0
+16 s 3 j n 5 4 k h
+24 c e 6 m u a 7 l

(表示幅の関係で折りたたんであるだけで、0〜31までの32個データ)

チェックサム

data部分の最後の6文字はチェックサムで、情報を含まない。有効な文字列は、以下のPython3のコードスニペットで指定された有効性の検証をパスする必要がある。以下の引数が与えられたbech32_verify_checksum関数がtrueを返せば有効。

  • hrp
    human-readable partの文字列
  • data
    data部の文字列を上記の変換表で変換した後の整数のリスト
def bech32_polymod(values):
  GEN = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
  chk = 1
  for v in values:
    b = (chk >> 25)
    chk = (chk & 0x1ffffff) << 5 ^ v
    for i in range(5):
      chk ^= GEN[i] if ((b >> i) & 1) else 0
  return chk

def bech32_hrp_expand(s):
  return [ord(x) >> 5 for x in s] + [0] + [ord(x) & 31 for x in s]

def bech32_verify_checksum(hrp, data):
  return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1

これは最大4文字に影響を与えるエラーの検出とエラー検出できない確率は1/109未満であることを保証するBCH符号*1の実装になる。より詳細な特性はAppendixを参照。human-readable partは、まず最初に各文字のASCII値の上位bitをチェックサムの計算に送り、続いて0と各下位bitが処理される。

human-readable partチェックサムが付与されていないdata部の値が与えられた際、その有効なチェックサムは以下のコードで計算できる。

def bech32_create_checksum(hrp, data):
  values = bech32_hrp_expand(hrp) + data
  polymod = bech32_polymod(values + [0,0,0,0,0,0]) ^ 1
  return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]
エラー訂正

BCH符号の特性の1つとして、エラー訂正に使える点が挙げられる。ただ、エラー訂正にはエラー検出を蝕む副作用がある。訂正により無効な入力を有効な入力に変更することができるが、訂正により有効と判定した入力は、実は本当は正しい入力ではない可能性がある。間違っているけど有効な入力を使うと、資金を使用不能にしてしまう危険性がある。このため実装では、文字列中にエラーが見つかった場合、ユーザーに修正を提案することなく勝手にエラー訂正をすべきではない。

大文字/小文字

デコーダーは大文字と小文字、両方の文字列受け入れなければならないが、両方を混在させないこと。小文字の書式はチェックサム用の文字を決める際に使われる。表示する際は(通常小文字が望ましいが)、大文字の英数字モードだと、通常のバイトモードより45%コンパクトになるので、QRコード内では大文字を使用するのが望ましい。

Segwitのアドレスフォーマット

Segwitアドレスは次のBech32エンコーディングとなる。

  • human-readable partは、mainnetがbc、testnetがtb
  • data-partの値は
    • 1文字がwitness version
    • (BIP-141で定義されている)2〜40バイトのwitness programを以下の手順でbase32に変換
      • witness programのbitから処理する
      • これらのビットを5つのグループに再配置し、必要に応じて末尾にゼロをパディングする
      • 上記の変換表を使ってこれらのbitを文字に変換する
デコード

ソフトウェアは以下の手順でSegwitのアドレスを解釈する。

  • human-readable partがmainnetではbc、testnetではtbである
  • デコードされたデータ最初のデータが0〜16の間(witness version)である
  • 残りのデータをバイトに変換する
    • データの値をそれぞれ5 bitシフトする。
    • それらのbitを8 bitのグループに再配置し、最後の不完全なグループは4 bit以下で、値は全て0で、破棄される。
    • これらは2〜40のグループで、witness programのバイトとして解釈される。

デコーダーはwitness programの既知の長さの制限を適用する必要がある。例えばBIP-141では、version byteが0で、witness programが20バイトか30バイトでなければならず、それ以外の場合そのスクリプトは失敗する。

この規則の結果、アドレスは常に14〜74文字の長さとなり、8を法とする長さは0もしくは3,5にはならない。version 0のwitnessアドレスは常に42文字か62文字だが、実装では任意のバージョンの使用を許可しなければならない。

互換性

Segwitに対応した新しいソフトウェアのみがこのアドレスを使用できる。それ以外の場合は、今まで通りP2SHもしくはP2PKHを使用する。

論拠

  • なぜBase32を使うのか?
    大文字と小文字が混在しないので、音声での読み上げやQRコードの読み込みが効率的になる。既存のアドレスに比べ、15%ほどデータは長くなるがコピペするアドレスにとっては重要な問題ではない。
  • Bech32と呼ぶ理由は?
    Bechには(エラー検出アルゴリズムが使われている)BCHの文字が含まれ、Baseのように聞こえるから。
  • なぜアドレスの中にセパレーターを含めるの?
    そうすることでhuman-readable partdata partが明確に分離され、プレフィックを共有する他のhuman-readable partとの潜在的な衝突をさけることができる。またhuman-readable partに文字セットの制限を設けるのを避けることもできる。英数字以外の文字を使うとアドレスのコピーがしにくくなるため(いくつかのアプリケーションではダブルクリックで選択できない)、セパレーターは1にしている。これらの理由により通常の文字セットではない英数字が選択された。
  • なぜ既存のRFC3548z-base-32といった文字セットを使わななかったの?
    文字セットはこの視覚的類似性データに従って曖昧さを最小限抑えるよう選択され、順序付けは類似した文字のペアを最小にするように選択される。少数のbitの誤りの検出能力をを最大にするためにチェックサムが選択されるが、この選択によりいくつかのエラーモデルの下で性能が改善する。
  • human-readable partの上位bitが最初に処理されるのはなぜ?
    これにより実際にチェックサムされたデータは[high] 0 [low] [data]というデータになる。これはhuman-readable partのエラーが(アルファベットの文字を別のものに変えるような)5 bitのみの変更によるエラーを前提にすると、エラーは[low] [data]部に制限され、このデータは最大89文字になるため、(appendixに記載している)エラー検出のプロパティが適用できる。
  • Segwitに限らず全てのscriptPubkeyの汎用アドレスフォーマットを定義しては?
    それをすると既存のscriptPubKeyタイプのアドレスに混乱をきたす。さらに複数のscriptPubKeyからなるアドレスのようにscriptPubKeyとアドレスが1対1にマッピングされないアドレスが導入された場合、それを古い汎用アドレスフォーマットとして解釈でき、Bitcoinを喪失するかもしれない。
  • human-readable partに指定するのかbtcじゃなくbcなのはどうして?
    bcの方が短いから。
  • testnetのhuman-readable partの指定がtbなのはどうして?
    mainnetのbcと同じ長さにしたかったのと、視覚的にも区別されてる。

参照実装

Appendix

Test vectors

以下の文字列は有効なBech32チェックサムを持つ。

  • A12UEL5L
  • an83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgs
  • abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw
  • 11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247j
  • split1checkupstagehandshakeupstreamerranterredcaperred2y9e3w

以下のリストは有効なSegwitアドレスとその16進数のscriptPubkeyを示す。

  • BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T4: 0014751e76e8199196d454941c45d1b3a323f1433bd6
  • tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7: 00201863143c14c5166804bd19203356da136c985678cd4d27a1b8c6329604903262
  • bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7k7grplx: 8128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
  • BC1SW50QA3JX3S: 9002751e
  • bc1zw508d6qejxtdg4y5r3zarvaryvg6kdaj: 8210751e76e8199196d454941c45d1b3a323
  • tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy: 0020000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433

以下のリストは無効なSegwitアドレスと、その無効な理由

  • tc1qw508d6qejxtdg4y5r3zarvary0c5xw7kg3g4ty: human-readable partが無効
  • bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5: チェックサムが無効
  • BC13W508D6QEJXTDG4Y5R3ZARVARY0C5XW7KN40WF2: witness versionが無効
  • bc1rw5uspcuh: witness programの長さが無効
  • bc10w508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kw5rljs90: witness programの長さが無効
  • BC1QR508D6QEJXTDG4Y5R3ZARVARYV98GJ9P: version 0のwitness programの長さとして無効
  • tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sL5k7: 大文字/小文字の混在
  • tb1pw508d6qejxtdg4y5r3zarqfsj6c3: 4 bitより多いの0パディング
  • tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3pjxtptv: ゼロパディングされていない

チェックサムの設計

設計の選択肢

BCH符号は、任意のアルファベットで構成でき、サイズとエラー検出機能において良いトレードオフの関係がある。BCH符号はほぼバイナリのアルファベットに対して使用するが、これは必須要件ではない。このためCRC符号より我々のユースケースに適している。リード・ソロモン符号と違い、アルファベットのサイズより1つ小さい長さの制限もない。効率的なエラー訂正もサポートしており、エラー検出の実装は非常に簡単である。

アドレスの長さとエラー検出のレベルはトレードオフにあり、6つのチェックサム文字列を採用した。6文字ではランダムな障害の可能性が1/100,000,000という充分低い数になる。witness programのデータにセットできる最大長は40バイトで、その保護データを含めると最大71バイトになり、BCH符号ではこれで最大4つのエラーを検出できる。

選択されたプロパティ

これらのコードの多くは検出した数より多くのエラーを処理すると悪い結果になる。3つのエラー検出と4つのエラー検出で実際にどの程度のパフォーマンスの影響があるか分析する。

選択した符号は以下の通り↓

  • 93, 151, 165, 341, 1023, 1057までの長さのデータに対し、3つもしくは4つのエラーを検出するよう設計された159605のBCH符号の網羅的なリストを用意する。
  • 長さ71までで4つのエラー検出をし、結果残り28825個の符号が残る。
  • それから5文字エラーに対してワーストケースのウィンドウを持つ符号を選択すると310個の符号が残る。
  • 続いて、少数のビットエラーを検出しない可能性が最も低い符号を選択する。

単純計算で6.5 * 1019チェックサムの評価が必要なので、分析のため衝突検索のアプローチを使う。コードはここにある。

プロパティ

以下の表は検出失敗の可能性についてまとめたもの↓

f:id:techmedia-think:20170509112919p:plain

これは、P2WPKHのアドレス39文字に対し、ランダムにその5文字を変更した場合、エラー検出できなくなる確率は0.756/100,000,000であることを意味している。 この5文字の変更の範囲が19文字の範囲内の場合、確率はさらに0.093/100,000,000に減少する。エラーの数が増えるにつれ、確率は1 in 230 = 0.931 / 100,000,000に収束する。

選択された符号は1023文字までは合理的にうまく実行されるが、他の設計では、上記の89文字の長さ(セパレーターを除く)が適している。

まとめ&所感

  • BIP-142を置換するBIPで、Segwitのアドレスフォーマットを定義する。
  • P2PKHやP2SHではアドレスを算出する際にBase58エンコーディングされていたけど、今回はそれとは別のBase32ベースのエンコーディングを提案してる。
  • Base32では大文字/小文字の区別が無い。
  • QRコードでは大文字の英数字の場合は英数字モードが利用でき、同じスペースに付与できるデータ量が増え、読み込みも効率的に行われる。
  • Base58と違って、エラー訂正が可能。ただ訂正結果が実はホントのデータではなかった場合、資金を失うことになるので、自動訂正は推奨しないと。
  • Segwitのアドレスではhuman-readable part部にmainnet: bc、testnet: tbという人が見分けるためのコードを、data-part部をwitness versionとwitness programで構成する。
  • このBIPはInformational BIPというガイドライン的な位置付けのBIPなので、version bitsを使ったデプロイなどは行われず、ウォレットや各ノード実装がこれに従うかどうかの判断は各実装者に委ねられるけど、参照実装があるのでCoreには取り込まれるんだろう。
  • 符号化のアルゴリズムもいろいろあって、面白そうね。

参照実装でRubyの実装が無かったのでPython版を参考に移植してみた↓

github.com

*1:誤り訂正符号の一種。考案者のAlexis HocquenghemとRaj Chandra BoseとD. K. Ray-Chaudhuriの名前からBCHと名付けられた。

Standards Track BIPのレイヤーの分類を定義したBIP-123

Standards Track BIPのヘッダの項目の1つにLayerがあるが、このLayerについて定義したのがBIP-123↓

bips/bip-0123.mediawiki at master · bitcoin/bips · GitHub

動機

Bitcoinはさまざまな標準を含むシステムで、そのいくつかは相互運用性を担保するのに必須の要件だが、それ以外のものはオプションとみなすことができサポートするかどうかは実装者に委ねられる。この相互運用の要件をより厳密に反映するBIPプロセスを実現するためには、要件に応じたBIPの分類が必要になる。低レイヤーのプロポーザルは標準として受け入れられデプロイするまでに多くの課題があるだろう。

仕様

Standards BIPsは以下の4つのレイヤーに分類する。(上から低レベル層 >> 高レベル層)

  • Consensus
  • Peer Services
  • API/RPC
  • Applications

Standards Track BIP以外のBIPはこれらのレイヤー分類をしてもいいし、しなくてもいい。

Consensusレイヤー

Consensusレイヤーでは、暗号コミットメント構造を定義する。このレイヤーの機能の目的は、誰もがローカル環境で特定の状態や履歴が有効か、セトルメントが保証されているか評価できるようにすることである。

Consensusレイヤーはメッセージがネットワーク上でどのように伝搬するかについては関与しない。

Consensusレイヤーに関する意見の不一致は、異なるノードが互換性のない異なる履歴を受け入れることになりネットワークの分断やフォークを招く可能性がある。

さらにConsensusレイヤーの変更をSoftforkとHardforkに細分化する↓

Softfork

Softforkでは、古いルールで有効だったいくつかの構造は新しいルールの下では有効でなくなる。古いルールで無効だった構造は新しい構造でも引き続き無効である。

Hardfork

Hardforkでは古いルールの下で無効だった構造が、新しいルールの下では有効になる。

Peer Servicesレイヤー

Peer Servicesレイヤーでは、ノードがどうやってメッセージを伝播するか定義する。

基本的なノードの相互運用性には、指定された全てのピアサービスのサブセットのみがあればよく、ノードは将来のオプション拡張をサポートする。

既存サービスとの互換性を損なうことなく新しいサービスを追加したり、古いサービスを段階的に廃止することは可能で、サービス中断の重大なリスクなくネットワーク全体をアップグレードすることができる。

API/RPCレイヤー

API/RPCレイヤーは、アプリケーションからアクセス可能な高レベルの呼び出しを定義する。このレイヤーのBIPのサポートは基本的なネットワークの相互運用には必要ないものだが、特定のアプリケーションによっては求められる場合もある。

このレイヤーでは、基本的なネットワークの相互運用性を損なうことなく、競合する標準を設ける余地がある。

Applicationsレイヤー

Applicationsレイヤーは、異なるアプリケーションが同様の機能のサポートやデータの共有をするための高レベルの構造、抽象化及びルールを定義する。

既存のBIPの分類

BIPのREADMEの表のLayer欄でまとめられてる↓

bips/README.mediawiki at master · bitcoin/bips · GitHub

メッセージが拒否された理由を明確にするBIP-061

2014年4月にリリースされたBitcoin Core 0.9.0、ネットワークのプロトコルバージョン70002でサポートされたrejectメッセージのBIP↓

bips/bip-0061.mediawiki at master · bitcoin/bips · GitHub

リモートピアとメッセージを交換する際、意図する動作にならないケースにおいて、その原因が何なのかリモートピアに通知するためにrejectメッセージが追加された。

動機

ピアに対しなぜトランザクションやブロックが受け入れられなかったのか、フィードバックすることは異なる実装間の相互運用性を助けることになる。また、SPVクライアントにとっても、優先度や手数料が不十分でトランザクションがリジェクトされた際に、何が悪かったのか判断する助けになる。

仕様

この仕様のデータタイプは以下のWikiで記載されている通り。

Protocol documentation - Bitcoin Wiki

reject

このBIPで新しいメッセージタイプrejectを導入する。
このメッセージはversiontxblockメッセージのレスポンスとしてピアに送信される。

例えば、2つのピア間の通信で、なんらかの理由でリジェクトされたトランザクションのメッセージフローは以下のようになる。

--> inv
<-- getdata
--> tx
<-- reject

P2Pプロトコルバージョンが70002以降の実装では、このrejectメッセージをサポートする必要がる。

共通のペイロード

rejectメッセージは、以下のフィールドで始まる。
(一部のメッセージは、メッセージ固有のデータが追加される。)

サイズ 名称 データタイプ 内容
可変 response-to-msg var-str リジェクトの原因となったメッセージ
1 reject-code uint8_t 0x01から0x4fまでのリジェクトコード(後述)
可変 reason var_string デバッグのための人が認識できるリジェクトメッセージ

reasonデバッグのためのだけに用意されており、特に実装が異なる場合は異なる文字列が使用されることがある。この文字列は問題を診断するためにだけ使い、決してユーザに表示したりしないこと。

reject-codeには以下のカテゴリに分類される。(以下に記述するserverrejectメッセージを生成するピアで、clientrejectメッセージを受信するピア)

範囲 カテゴリ
0x01-0x0f プロトコルシンタックスエラー
0x10-0x1f プロトコルのセマンティックエラー
0x40-0x4f serverのポリシールール

全メッセージタイプ共通のreject code

code 定義
0x01 メッセージがデコード出来ませんでした

reject version code

versionメッセージへのレスポンスとして、初期コネクションを確立する際に生成されるコード

code 定義
0x11 clientでは廃止されサポートされていないバージョンです。
0x12 重複したversionメッセージを受け取りました。

reject tx payload, codes

トランザクションのリジェクトメッセージには、既存のメッセージに加え以下のTXIDが付与される。

サイズ 名称 データタイプ 内容
32 hash char[32] リジェクトされたトランザクションのハッシュ

以下のコードが使用される。

code 定義
0x10 トランザクションが何らかの理由(無効な署名、出力のコインの量が入力のコインの量を超えているなど)で無効です。
0x12 入力は既に使用されています。
0x40 (serverにとって)非標準なトランザクションなのでマイニング/リレーされません。
0x41 1つ以上の出力の量がdust閾値以下です。
0x42 マイニングやリレーをするのい充分なトランザクション手数料/優先度がありません。

payload, reject block

ブロックのリジェクトメッセージは、既存のメッセージに加え以下のブロックヘッダのハッシュが付与される。

サイズ 名称 データタイプ 内容
32 hash char[32] リジェクトされたブロックヘッダのハッシュ

以下のコードが使用される。

code 定義
0x10 ブロックが何らかの理由(無効なProof-of-Work、無効な署名など)で無効です。
0x11 サポートされなくなったブロックのバージョンです。
0x43 コンパイルされたチェックポイントが異なるブロックチェーンのブロックです。

注意:serverのベストチェーンには含まれていないが、そのブロックが有効なブロックである場合は、rejectメッセージを作成してはいけない。

互換性

rejectメッセージを認識しない古いピアでは、rejectメッセージは無視されるるため、下位互換性がある。

実装上の注意事項

実装者は、攻撃者が有効なトランザクションやブロックに対しrejectメッセージを送信したり、ランダムにrejectメッセージを送信するような攻撃や、DoS攻撃が行われた際に何が起きるか考慮する必要がある。例えば、rejectメッセージを受信した際に全てそれをユーザーに通知するようにしていたら、攻撃者がユーザーへの嫌がらせをする攻撃が可能になる。また、全てのrejectメッセージをログに書き込むだけでも、ユーザーのディスクを溢れさせるような攻撃に繋がる。