CAMPFIRE で暗号通貨技術を担当しているジョーです。

前回の続きとして、 F# で Miniscript のコンパイラを作っていきます。

Miniscript は Bitcoin 上でスマートコントラクトを行うためのハイレベル言語、およびそのコンパイル規格です。

今回作成しているソースコードは独立のレポジトリからNBitcoin のプルリクエストに移りました。

前回は左の「パース」の部分を実装したので、今回は真ん中の 「狭義のコンパイル」の部分を行っていこうと思います。

一番複雑でかつ重要な部分です。

前回の記事では、文字列表現から Policy (AbstractPolicy) へと変換する処理をF# の Active Pattern を使って実装しましたが、今回は F# 特有の機能は使いません。

コンパイルの手順

ビットコインスクリプトでは、同じことを表現するのに複数のやり方があります。

例えば、A または B ならば

- Parallel ... A or B
- Cascade ... if A then 1 else B
- Switching ... if x then A else B
- Cond, Switch ... if x then if y then A else B else 0

があり、1.検証が通るようなアイテムのバイト数 (Satisfication cost) 、2. そのアイテムを取り除くことにより増えるバイト数 (Dissatisficationn cost) 3. スクリプトそのものバイト数

でのトレードオフが存在します。

ここでいうアイテムとは、 SegWit における Witness Item 、つまりスクリプトへの入力のことです。

ビットコインスクリプトは「何らかのバイト配列を引数にとって、成功/失敗を返す関数」とみなすことができ、アイテムはその関数に対するインプットを表します。通常は ECDSA の署名データですが、HTLCなどの場合は、単なる秘密の値 (preimage) などもありえます。

「A または B 」の条件を表したい場合、実際にブロックチェーン上で実行される際には片方のインプットしか必要ないので、もし A の条件が満たされる確率の方が高いような場合「 A に対応するインプットが与えられた際にできる限り全体が小さくなる(が、 Bのインプット が与えられた時はそれほど小さくなくても良い)」という意図をコンパイルのプロセスに反映させることができます。ビットコインの場合、このように非対称な or の方が通常の or よりもむしろありがちなので (例えば Lightning Network では、相手が古い Commitment TX をブロードキャストした際に対応するケースを考慮に入れなくてはならないですが、そのケースはあくまで不誠実な振る舞いに対する抑止力として存在するだけなので、実際に行使されることは稀)、この機能の重要性は高いと言えます。

標準の Miniscript では AsymmetricOr (Aor) で、1: 127 の確率を表現することができますが、必要ならばより細かく確率を表現することもできます。

コンパイル自体は、「ありうる全てのコンパイル結果を探索して、予想されるアイテム + スクリプトのサイズが最小のものを選ぶ」というだけです。

複雑すぎるスクリプトは 1. 予想される用途が少ない & 2. そもそも Mempool またはコンセンサスルールで弾かれる

という理由から、十分計算可能なサイズに収まるので変なヒューリスティックスは必要ありません。

F# で実装

まず、ありうる中間表現を全て判別共用体 (Discriminated Union) として書き下していきます。

      /// "E"xpression. takes more than one inputs from the stack, if it satisfies the condition,
      /// It will leave 1 onto the stack, otherwise leave 0
      /// E and W are the only type which is able to dissatisfy without failing the whole script.
   	 type E =
           | CheckSig of PubKey
           | CheckMultiSig of uint32 * PubKey []
           | Time of LockTime
           | Threshold of (uint32 * E * W [])
           | ParallelAnd of (E * W)
           | CascadeAnd of (E * F)
           | ParallelOr of (E * W)
           | CascadeOr of (E * E)
           | SwitchOrLeft of (E * F)
           | SwitchOrRight of (E * F)
           | Likely of F
           | Unlikely of F
   
       /// "W"rapped. say top level element is `X`, then consume items from the next element.
       /// and leave one of [1,X] [X,1] if it satisfied the condition. otherwise
       /// leave [0,X] or [X,0] onto the stack.
       and W =
           | CheckSig of PubKey
           | HashEqual of uint256
           | Time of LockTime
           | CastE of E
   
       /// "Q"ueue. Similar to F, but leaves public key buffer on the stack instead of 1
       and Q =
           | Pubkey of PubKey
           | And of (V * Q)
           | Or of (Q * Q)
   
   
       /// "F"orced. Similar to T, but always leaves 1 on the stack.
       and F =
           | CheckSig of PubKey
           | CheckMultiSig of uint32 * PubKey []
           | Time of LockTime
           | HashEqual of uint256
           | Threshold of (uint32 * E * W [])
           | And of (V * F)
           | CascadeOr of (E * V)
           | SwitchOr of (F * F)
           | SwitchOrV of (V * V)
           | DelayedOr of (Q * Q)
   
       /// "V"erify. Similar to the T, but does not leave anything on the stack
       and V =
           | CheckSig of PubKey
           | CheckMultiSig of uint32 * PubKey []
           | Time of LockTime
           | HashEqual of uint256
           | Threshold of (uint32 * E * W [])
           | And of (V * V)
           | CascadeOr of (E * V)
           | SwitchOr of (V * V)
           | SwitchOrT of (T * T)
           | DelayedOr of (Q * Q)
   
       /// "T"opLevel representation. Must be satisfied, and leave zero (or non-zero) value onto the stack
       and T =
           | Time of LockTime
           | HashEqual of uint256
           | And of (V * T)
           | ParallelOr of (E * W)
           | CascadeOr of (E * T)
           | CascadeOrV of (E * V)
           | SwitchOr of (T * T)
           | SwitchOrV of (V * V)
           | DelayedOr of (Q * Q)
           | CastE of Ef
   
   // 全部をまとめた型
   type AST =
           | ETree of E
           | QTree of Q
           | WTree of W
           | FTree of F
           | VTree of V
           | TTree of T

再帰的に参照しあう型なので、 and キーワードを使って書いていきます。F# は通常、ソースコードの読みやすさを保つため上にあるオブジェクトから下にあるオブジェクトを参照することができませんが、再帰構造を持つような型の場合はこの制限を緩める必要があるので and という特殊な構文を使用します。

さらに、対応するスクリプトへとシリアライズするメソッドも定義します。

   type E with
       // 自分自身の型に応じて、対応するビットコインスクリプトの文字列表現に変換
       member this.Serialize(sb : StringBuilder) : StringBuilder =
               match this with
               | CheckSig pk -> sb.AppendFormat(" {0} OP_CHECKSIG", pk)
               | // ... 長いので省略

このメソッドを全ての型について実装します。ビットコインスクリプトのオブジェクトではなく、StringBuilder をアップデートして返しているのは単なる実装上の都合です。(NBitcoin がもともと文字列を受け取る API であったため)最終的には文字列から NBitcoin.Script というクラスに変換します。

あまり記事が長くなると読んでもらえなくなるので今日はこの辺りにします。

次回は実際のコンパイルのプロセスを見ていきます。