Develop with pleasure!

福岡でCloudとかBlockchainとか。

Confidential Transactionのcommitmentを生成してみる

Bitcoin Ruby CT Elements

以前、Confidential Transactionのホワイトペーパーを読んだ↓

techmedia-think.hatenablog.com

Confidential Transactionでは、トランザクションの出力にコインの量をセットする代わりに、Pedersen commitmentを楕円曲線に適用したコミットメント（この場合は楕円曲線上のある点）をセットすることで、トランザクションで取引されるコインの量を秘匿している。

ホワイトペーパーを読んで概要はなんとなく分かったまま放置してたので、実際にコードで検証してみる。

commitmentの生成

このコミットメントは

commitment = xG + aH

の式で定義され、xが量の秘匿のために用いられるblinding factorでいわゆるシークレットに該当する。実際に取引するコインの量はaになる。
この式はxとGからなる楕円曲線上の点と、aとHからなる楕円曲線上の点を加算した新たな点を算出し、この点をコインの量の代わりにトランザクションの出力にセットしている。

Hの算出

ここでGは楕円曲線のベースポイントで、HはGをエンコードして生成するもう１つのベースポイントである。Hは以下の式で楕円曲線上のX座標を計算し、そこからY座標を求めることで算出でき、これも楕円曲線上の点になる。

HのX座標 = SHA256(ENCODE(G))

Rubyのecdsa gemを使うとこのX座標は以下のように算出できる。

require 'ecdsa'
require 'securerandom'

G = ECDSA::Group::Secp256k1

encoded_g = ECDSA::Format::PointOctetString.encode(G.generator)
coordinate_x = Digest::SHA256.hexdigest(encoded_g).to_i(16)
=> 36444060476547731421425013472121489344383018981262552973668657287772036414144

X座標が分かれば、secp256k1の楕円曲線上のY座標は以下のように算出できる。ただ楕円曲線はX軸関して対称であるため、Y座標の候補は２つある。

P = G.field.prime

coordinate_y1 = G.field.power((coordinate_x**3 + 7) % P, (P + 1)/4)
=> 93254584761608041185240733468443117438813272608612929589951789286136240436011

coordinate_y2 = coordinate_y1 * -1 % P
=> 22537504475708154238330251540244790414456712057027634449505794721772594235652

Confidential Transactionを実装しているBlockstreamのサイドチェーンElements Alphaのソースを確認すると後者のY座標の値が使われていたので、そちらを使用して、Hの楕円曲線上の点は以下の座標になる。

  • X座標：36444060476547731421425013472121489344383018981262552973668657287772036414144
  • Y座標：22537504475708154238330251540244790414456712057027634449505794721772594235652
# ２つめのベースポイントH
H = ECDSA::Point.new(G, coordinate_x, coordinate_y2)

ちなみにこのHをGから導出する固定値でなく、アセットを表す識別子としてアセット毎に任意に生成できるようにしたのがConfidential Assets。

Hの算出方法を確認するため↑の計算をしたけど、Hは固定値なので以下のように定義してそのまま使うのでも良い。

# ECDSA::Grou::Secp256k1 = G とgenerP = G.field.primeatorのポイントが違うだけのGroupを定義
module ECDSA
  class Group
    Secp256k1H = new(
        name: 'secp256k2',
        p: 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_FFFFFC2F,
        a: 0,
        b: 7,
        g: [0x50929b74_c1a04954_b78b4b60_35e97a5e_078a5a0f_28ec96d5_47bfee9a_ce803ac0,
            0x31d3c686_3973926e_049e637c_b1b5f40a_36dac28a_f1766968_c30c2313_f3a38904],
        n: 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_BAAEDCE6_AF48A03B_BFD25E8C_D0364141,
        h: 1,
    )
  end
end

コミットメントの作成

blinding factorをx、取引するsatoshiの量をaとした時、そのコミットメントは以下のように算出できる。

# blinding factor
x = 1 + SecureRandom.random_number(G.order - 1)

# コミットするコインの量
a = 10000

# コミットメント
commitment = G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(a)

どうしてGとHの２つのベースポイントが必要かというと、もしHでなく同じGを使うと、blinding factorの値によって実際のコインの量をなんとでもコントロール出来てしまうからで、そのためblinding factorとコインの量を表現する際のベースポイントは必ず別のポイントである必要がある。

秘匿された量の検証

Confidential Transactionでは、↑のように出力にセットするのが明示的な量ではなく、コミットメント＝楕円曲線上の点になる。この場合実際にいくらの量がやりとりされているかは、blinding factorの値を知る取引の当事者しか分からず、blinding factorを知らない他の参加ノードは実際の取引量は分からない。

ただ、取引量がわからなくても、トランザクションの入力と出力でコインの量が正しくセットされているか＝入力に使われているコインの量を超えるような出力がセットされていないかについては、blinding factorを知っている・知っていないに関らず誰もが検証できる必要がある。

この検証は、トランザクションの入力に使われている全コミットメントと出力の全コミットメントに対し以下の式が成立すれば入力と出力でコインの量は等しいことが確認できる。

（入力１のコミットメント + 入力２のコミットメント... ） - （出力１のコミットメント + 出力２のコミットメント...） = 0

ただこの時、手数料が問題になる。Bitcoinのトランザクションでは入力-出力の差が手数料として使用されるが、Confidential Transactionのように量が秘匿されている状態では手数料がいくらかは分からないので、手数料は明示的にトランザクションにセットする必要がある。

実際にこの式が成立するか検証してみよう。とりあえず手数料を考えず、全入力のコミットメントを加算した点から全出力のコミットメントを加算した点を引いたものが0になれば良い。

楕円曲線上の点の減算は、減算したい点についてX軸について対称の点を計算し、その点を加算することが減算になる。(x, y)に対して(x, -y)を作れば前者の点を使った減算ができる。ちなみにこの両者を加算すると無限遠点となり、この場合、無限遠点はこの演算に関してゼロとして機能する。そのため、全入力のコミットメントから全出力のコミットメントを減算した結果、無限遠点となればイコール0と判断できる。

1500のコインをもつ1つの入力と、1000と500の2つの出力を例に計算してみる。

この場合入力のコミットメントは

# blinding factor
x = 1 + SecureRandom.random_number(G.order - 1)

input =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1500)

となる。同じxを使った出力のコミットメントは単純に考えると以下のようになる

output1 =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(500)

が、この出力は正しくない。このコミットメントを使って全入力のコミットメント-全出力コミットメントを計算するとG.generator.multiply_by_scalar(x)の分だけ余りが発生し0にはならない。

そのため、こういうケースでは計算が合うように出力のblinding factorの値を選択する必要がある。
今回は簡易的に計算するため、それぞれのflinding factorを以下のように調整した値のコミットメントを作成した。

output1 =  G.generator.multiply_by_scalar(x / 2) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x - x / 2) + H.multiply_by_scalar(500)

実際にblinding factorをどのように設定するかは、トランザクションを作成するユーザーが全入力のコミットメント-全出力コミットメント＝０になれば後は自由に決めて良い。

実際にこのコミットメントを持つトランザクションが与えられた際、当事者以外は以下の検証をすると入力と出力が同じ量であるか検証できる。

input =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1500)

output1 =  G.generator.multiply_by_scalar(x / 2) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x - x / 2) + H.multiply_by_scalar(500)

outputs = output1 + output2

result = input + outputs.negate # ECDSA::Point#negateは、その点のX軸に対して対象な点を算出するメソッド

result.infinity?
=> true

実際に入力と出力の関係が1:1になることはほとんど無いと思うので、入力のblinding factorとその入力が持つ量と出力先の数を踏まえて、新たに出力で使用するbliding factorを計算する必要がある。

ECDSAの脆弱性を利用した未承認トランザクションの二重使用を防止する仕組み

Bitcoin ECDSA

Bitcoinのトランザクションは10分に一度作成されるブロックに取り込まれる。最近のメモリプールの状況では10分後に取り込まれればラッキーな方で、まだ時間がかかることもよくあると思う。
その一方でECサイトや実店舗でのBitcoin決済の導入は進んでいる。リアルな店舗で決済する際に10分以上待たされてはBitcoinを使って決済しようとは思えないから、こういった店舗では、決済するトランザクションがブロードキャストされれば決済されたと判断しトランザクションがブロックに取り込まれるまで待たずに決済をしている。つまに未承認のトランザクションで決済している。

この場合、もし二重使用が発生すると店舗側は決済した金額を受け取れない事態が発生する。まぁその辺のリスクを考慮してBitcoin決済ができるのはある一定額までで、そういう事態が発生した場合は決済会社が保証などしているのだと思う。

そんな未承認トランザクションの二重使用を防ぐ仕組みについてバルセロナ自治大学のホワイトペーパーが公開されていたので見てみた↓

http://eprint.iacr.org/2017/394.pdf

二重使用を防ぐ基本的な仕組み

二重使用はその資金を二重使用できないようなトランザクションに送る初期化フェーズと、そのトランザクションを使って決済を行うファストペイメントフェーズの２つのフェーズからなる。

初期化フェーズ

アリスはまず自分のUTXOをFR-P2PKの出力に送るfunding transactionを作成する。このトランザクションを作るためアリスは、ランダムな整数値kと公開鍵PKa（対応する秘密鍵はSKa）を選択し（＝決済に使用するキーペアの生成）、FR-P2PKの出力（具体的なスクリプトは後述）をセットし、そこにいくらかの資金を送金するトランザクションを構成する。アリスはfunding transactionをブロードキャストし、トランザクションがブロックに格納されたら初期化フェーズが完了する。

FR-P2PKというのはfixed-r pay-to-pubkey scriptの略で、Pay-to-Pubkeyを少し変形させたスクリプトになる。Pay-to−Pubkeyの場合、そのスクリプトを使用するには署名をscript_sigにセットすればいいけど、FR-P2PKはその署名が特定の値rを使って生成される必要がある。FR-P2PKではECDSAの脆弱性を逆に利用して二重使用から保護する。

つまり、FR-P2PKを使用するトランザクションを作り、更に同じFR-P2PKを二重使用するトランザクションがブロードキャストされた場合、ネットワーク上には

  • 同じ秘密鍵
  • 同じ乱数
  • ２つ異なる署名対象のメッセージ

から生成された署名が２つ存在することになり、ネットワークに参加しているノードであれば誰でもそこから秘密鍵を計算することができる。そのため二重使用しようとしたユーザーは、ネットワーク上のノードに計算した秘密鍵からFR-P2PKの資金を奪われるというリスクを考慮するから、二重使用するインセンティブが働かなくなるという仕組み。

この脆弱性から秘密鍵を導出するのは簡単でRubyでecdsa gemを使って書くと↓のように書ける。

※ 署名値のSが-S mod Nの場合もあるので、ちゃんと計算する場合はそこも考慮する必要はある。

Fast paymentフェーズ

実際に決済する際は、アリスは初期化フェーズで作成したfunding transactionのFR-P2PK出力を使ってボブにBitcoinを送るfast-payment transactionを作成する。このトランザクションのscript_sigが有効であるということは、アリスが公開鍵PKaに対応する有効な秘密鍵SKaと初期化フェーズで生成したkの値を持っていることの証明になる。アリスは作成したfast-payment transactionをBitcoinネットワークにブロードキャストする。

ボブはメモリプール内にある受信したfast-payment transactionを確認すると、このトランザクションで使用されるUTXOがFR-P2PK出力であることを検証することができる。FR-P2PK出力であることが確認できれば、ボブはアリスが二重使用しようとすると彼女が自分の資金を失う可能性があることを認識する。

アリスがfunding transactionの資金を二重使用する場合、FR-P2PK出力を二重使用するトランザクションを新たに作成する必要がある。このトランザクションの署名はもちろん有効な署名でないといけないので、SKaと初期化フェーズで選択されたkを使った２つ目の署名を作ることになる。つまり二重使用のトランザクションを作るということは、同じ秘密鍵SKaと同じrをを使った異なる署名を作ることになる。署名されるメッセージ（トランザクションダイジェスト）も異なるので、この場合ECDSAの、同一の秘密鍵によって同じ値kで行われる２つの署名があれば、署名に使用された秘密鍵を導出するのに充分なヒントになるという脆弱性に該当する。

そのためアリスは二重使用トランザクションをブロードキャストすると、自分の資金を失う危険性がある。これはfunding transactionとfast-payment transactionの両方を受信するオブザーバーがアリスの秘密鍵SKaを導出できるため、結果 FR-P2PKの出力をオブザーバーに送金する第３のトランザクション（ペナルティトランザクション）を作成することができる。

抑止的な保護の仕組み

↑の仕組みには明らかな欠陥がある。アリスがボブの店で↑のファストペイメントを行い商品を購入するとする。ボブはトランザクションを受信すると商品をアリスに発送する。アリスは商品を受取ると二重使用を試みるかもしれない。オブザーバーがfast-payment transactionと二重使用トランザクションの両方を監視しているケースでは、ペナルティトランザクションを作成し、それが先にブロックチェーンに格納されるように調整する（手数料などで）。この場合ペナルティトランザクションがブロックに入れられるとアリスは資金を失うが、ボブも支払いを受け取れない。このようなケースであればボブは、商品を発送したが、それと交換にBitcoinを受け取ることができない。結果的にアリスはBitcoinをボブではなく第三者のオブザーバーに支払ったことになり、オブザーバーがトランザクションの総量を手に入れる。結果的にアリスが二重使用をするインセンティブは働かないので、この提案した方法は二重使用を防ぐかもしれない。

しかし、方法を少し変えるだけでアリスに二重使用を思いとどまらせる方法がある。それはfunditoin transactionのFR-P2PK出力に支払いに使う金額より一定の係数λだけ高い金額をセットすることを強制する方法だ。この場合、アリスが二重使用を試みると、支払金額より多いFR-P2PK出力分のコインをオブザーバーに全て持って行かれる可能性があり、商品をボブから入手したとしても、係数λの分だけアリスが損をすることになる。そのため自分が損する可能性があるのにアリスは二重使用を試みるはずはない。

FR-P2PKスクリプトの構成

Bitcoinのトランザクションの署名データは、以下のDERエンコーディング仕様で構成されている。

0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]

techmedia-think.hatenablog.com

この署名データのフォーマットを考慮した上で、FR-P2PKの出力は以下のように定義される。

ScriptPubKey: OP_DUP <pubKey> OP_CHECKSIGVERIFY OP_SIZE <0x47> OP_EQUALVERIFY <sigmask> OP_AND <r> OP_EQUAL
ScriptSig: <sig>
  • <pubKey>: 署名の検証に使われる公開鍵
  • <sigmask>: 71バイトのバイト列で、DERエンコーディングされた署名データ(sig)のrの位置と最後のSIGHASH_TYPEの位置に1がセットされ、その他の部分には0がセットされたビットマスクになる。
  • <r>: 71バイトのバイト列で、整数rのDER形式の値と、SIGHASH_TYPEには0x01が、それ以外の箇所は全て0がセットされている。

このスクリプトを実行すると、まず署名が<pubKey>に対応した有効な署名か検証が行われ、続いて署名のサイズを検証する。その後<sig>と<sigmask>のビット単位のANDを計算し、その結果が<r>と同じかチェックされる。このようにして署名データに固定値のrを強制している。

ただ、このOP_ANDというopcodeはBitcoinの標準仕様では無効化されているものなので、このスクリプトを現在使用することはできない。

所感

  • ECDSAの脆弱性を利用するという逆転の発想感は面白い。
  • オブザーバーの存在や、現実的に全てのノードがオブザーバーになるわけでもないのと、二重使用のトランザクションがブロードキャストされそれをオブザーバーが検知してからの対応になるという仕組みを考えると、完璧に二重使用を防げるものではないので、そういうリスクを取らせることで二重使用するインセンティブを排除していくのだろう。
  • 初期化フェーズでfunding transactionをブロードキャストする必要があるので、最終的に決済するのに２つのトランザクションのブロードキャストが必要になる。この部分の手数料や手間とか考慮すると残念ながらあまりカジュアルに使える方法ではないと思う。
  • 実現する場合は、現在無効化されているOP_ANDが再び使えるようになる必要がある。

Strong Federationsの概要

Bitcoin Sidechain

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

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

Strong Federationsの技術要素

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

Federated Peg

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

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

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

ビザンチン耐性

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

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

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つの一般的なケースの攻撃に対する保護になる。１つはノードのクリティカルな部分がネットワークから分離され可用性が失われるケース。もう１つは攻撃者による多数のノードが操作され、完全性が失われるケース。

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

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

所感

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

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

BIP Bitcoin

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. スタックの一番上の要素が32bitのCScriptNumとして解釈できない場合、スクリプトは失敗する。
  3. スタックの一番上の要素はブロック高（ParamHeight）として解釈される。
  4. このスクリプトを実行しているブロックチェーンに、ParamHeightで指定したブロック高のブロックが存在しない場合、スクリプトは失敗する。
  5. ParamHeightがチェーン内の52596ブロックより深い（マイナスを含む）を指定していた場合、opcodeは正常に完了し、スクリプトは続きの処理を実行する。
  6. スタックの上から２つめの要素は、ブロックハッシュ（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を二重使用する時間は１年あれば充分。
  • より深くチェックするようにするのはソフトフォークでできるけど、より浅くしたい場合はハードフォークになる。

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

  • チェーンの分割で、リプレイ攻撃を避けるためには数バイトチェックするので充分。
  • 完全なブロックハッシュを使うのに比べてブロックチェーンのディスクスペースの節約になる。
  • （OP_LESSTHAN）のようなopcodeと１バイトと組み合わせて使用することで、オンチェーンの 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）という２つ要素を引数として取る。
  • OP_CHECKBLOCKATHEIGHTは、指定されたブロック高（ParamHeight）のブロックハッシュの後半がParamBlockHashと一致するか評価し、一致しない場合、スクリプトの評価は失敗する。
  • チェーンが分岐すると分岐以降、２つのチェーンで同じブロック高のブロックハッシュが全く同じになることは基本的にないので、OP_CHECKBLOCKATHEIGHTでブロックハッシュを評価することで、必ずどちらかのチェーンでしか利用できないUTXOを作ることができるようになると。
  • スクリプトの評価の際に過去のブロックのデータ参照にいくようなスクリプト組むのありなのかー。
  • SPVノードもブロックヘッダはダウンロードしてるから、フルノードと同様チェックは可能か。
  • 二重使用からの復元が回避できてる理由と、後方互換性のリレーしない問題の大丈夫な根拠がイマイチよく分からない。

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

Bitcoin BIP Segwit

取り下げられた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参照）と、その２つの例（P2WPKHやP2WSHなどBIP-143参照）が含まれている。この２つの機能は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部分の最後の６文字はチェックサムで、情報を含まない。有効な文字列は、以下の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

これは最大４文字に影響を与えるエラーの検出とエラー検出できない確率は1/109未満であることを保証するBCH符号*1の実装になる。より詳細な特性はAppendixを参照。human-readable partは、まず最初に各文字のASCII値の上位bitをチェックサムの計算に送り、続いて０と各下位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符号の特性の１つとして、エラー訂正に使える点が挙げられる。ただ、エラー訂正にはエラー検出を蝕む副作用がある。訂正により無効な入力を有効な入力に変更することができるが、訂正により有効と判定した入力は、実は本当は正しい入力ではない可能性がある。間違っているけど有効な入力を使うと、資金を使用不能にしてしまう危険性がある。このため実装では、文字列中にエラーが見つかった場合、ユーザーに修正を提案することなく勝手にエラー訂正をすべきではない。

大文字/小文字

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

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

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

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

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

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

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

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

アドレスをscriptPubkeyに変換する際は実装に特に注意する必要がある。witness version nはOP_nとして保存されているため、OP_0は0x00になるがOP_1からOP_16は0x51から0x60としてエンコードされる。bech32アドレスが正しくないscriptPubkeyに変換されると、使用できないもしくは不正なものになってしまう。

互換性

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

論拠

  • なぜBase32を使うのか？
    大文字と小文字が混在しないので、音声での読み上げやQRコードの読み込みが効率的になる。既存のアドレスに比べ、15%ほどデータは長くなるがコピペするアドレスにとっては重要な問題ではない。
  • Bech32と呼ぶ理由は？
    Bechには（エラー検出アルゴリズムが使われている）BCHの文字が含まれ、Baseのように聞こえるから。
  • なぜアドレスの中にセパレーターを含めるの？
    そうすることでhuman-readable partとdata partが明確に分離され、プレフィックを共有する他のhuman-readable partとの潜在的な衝突をさけることができる。またhuman-readable partに文字セットの制限を設けるのを避けることもできる。英数字以外の文字を使うとアドレスのコピーがしにくくなるため（いくつかのアプリケーションではダブルクリックで選択できない）、セパレーターは１にしている。これらの理由により通常の文字セットではない英数字が選択された。
  • なぜ既存のRFC3548やz-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とアドレスが１対１にマッピングされないアドレスが導入された場合、それを古い汎用アドレスフォーマットとして解釈でき、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: 5128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
  • BC1SW50QA3JX3S: 6002751e
  • bc1zw508d6qejxtdg4y5r3zarvaryvg6kdaj: 5210751e76e8199196d454941c45d1b3a323
  • 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/100,000,000という充分低い数になる。witness programのデータにセットできる最大長は40バイトで、その保護データを含めると最大71バイトになり、BCH符号ではこれで最大４つのエラーを検出できる。

選択されたプロパティ

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

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

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

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

プロパティ

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

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

これは、P2WPKHのアドレス３９文字に対し、ランダムにその５文字を変更した場合、エラー検出できなくなる確率は0.756/100,000,000であることを意味している。 この５文字の変更の範囲が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と名付けられた。