F# でスマートコントラクト
Part1: パーサ編
CAMPFIRE で暗号通貨技術を担当しているジョーです。
この度弊社の取り組んでいる技術に関連する記事を書いて行こうということになりました。
一発目の記事は誰でも興味を持てるような内容にしようと思い、「ビットコイン決済の未来」というタイトルにしようと思ったのですが、ポエム力の欠如により断念しました。
というわけで、ビットコインスマートコントラクトスクリプトの DSL の一種である Miniscript のコンパイラを作ろうと思います。かなりニッチな内容になってしまいましたが、気にしないことにします。
Miniscript とは？
Miniscript の概要については以前別のところに書いたので、こちらを参照してください。
> 日本語 URL の関係で埋め込みがうまく行かなかったので以下に直接 URL 貼りました。
https://medium.com/blockchain-engineer-blog/miniscript-bitcoin%E3%81%AE%E3%82%B9%E3%83%9E%E3%83%BC%E3%83%88%E3%82%B3%E3%83%B3%E3%83%88%E3%83%A9%E3%82%AF%E3%83%88%E3%81%AE%E3%81%93%E3%82%8C%E3%81%BE%E3%81%A7%E3%81%A8%E3%81%93%E3%82%8C%E3%81%8B%E3%82%89-b5c0c838ccec前書き
初めに断っておくと、ここで作成しているものを本番で利用するのはやめた方が良いです。異常なスマートコントラクトができてしまう可能性があります。(そもそも完成しないかも)
また、 Miniscript 自体かなり新しい仕組みであり、細かい点で変更が加えられる可能性が大いにあるのでその点にも注意。
理想を言うと、参照実装をそのまま使った方が安全です。ffi で呼び出すとか、あとは最近は wasm が流行っているので、 wasm にコンパイルして load するなどの方法が現実的です。
じゃあなんで作るねんと言う声が聞こえてきそうですが、以下の理由のためです。
1. Miniscript の詳細な動作を知るため
2. F# の勉強のため
3. 一般的なコンパイラの仕組みを学ぶため
F# の知識は仮定しませんが、そこまで詳しく説明はしないつもりなので、必要に応じて調べてください。
今回は、 Andrew Poelstra 氏の rust-miniscript というリポジトリを参考に作成しています。
その１: 全体の構成を把握する
一番大事な工程です。何を作りたいのか把握しないまま書き出すと大抵ろくなことになりません。
rust-miniscript のコードを読むと、大まかに以下の手順に分けられるようです。
1. DSLの文字列表現をパースして AST に変換
2. AST の部分木それぞれについて、可能な表現形式を全て考慮し、コストが最小になるような表現形式を選ぶ
ただし、「表現形式」とはコンパイル後のビットコインスクリプトの実態を指し、「コスト」とは、「見込まれるスクリプト全体の大きさ」を指します。詳しくは次回以降書きます。
3. ビットコインスクリプトを、文字列またはオブジェクトとして生成する。
一番複雑で、Bitcoin 特有の概念が関与してくるのが 2 です。
今回は 1 だけを行います。
その2: データの構造を決める
Miniscript では DSL を使って解除条件を記述します。この解除条件から実体となるスクリプトを生成する (あるいはその逆を行う) のが最終目標です。
Miniscript 開発者の作成したデモサイトを見ると、この DSL には以下の関数が存在するようです。
- `pk(HEX)` // 署名対象となる公開鍵。対応する署名が必要であることを示す。
- `multi(m, HEX, HEX, HEX...)` // マルチシグ管理を行う公開鍵。m 個の署名が必要であることを示す。
- `time(NUMBER)` // いわゆるTimelock。output の作成から相対時間で NUMBER だけ経つ必要があることを示す。(時間なのかブロック数なのか現時点ではよくわかりません)
- `hash(hex)` // HEX の SHA256 ハッシュが必要であることを示す。
- `and(EXPR, EXPR)` // EXPR は、別の Miniscript の Sub Expression 。二つの EXPR が両方とも真の時のみ解除できることを示す。
- `or(EXPR, EXPR)` // 同様に少なくとも片方が真の時のみ解除できることを示す。
- `aor(EXPR, EXPR)` // or と同じだが、一つ目の解除条件が履行される可能性が非常に高いことを示す。ちょっと独特。
- `thres(NUM, EXPR, EXPR...)` // Sub Expression のうち、真となるものが NUM 以上になった際に解除できることを示す。thres は threshold
`aor` の存在が不思議に思えるかもしれませんが、これは、「多分最初の EXPR が実行されるので、そちらを実行する場合に (署名を含む) 全体のデータ量が小さくなるようなスクリプトを生成してほしい」と言うことをコンパイラに伝えるために存在します。
これらを表現するために、判別共用体を使います。判別共用体は Union や直和型とも呼ばれるもので、「以下の値のうちのいずれか」を意味します。
type Policy<'P> =
| Key of NBitcoin.PubKey // of の左は判別共用体の identifier, 右は内部にもつ値の型
| Multi of uint32 * PubKey[] // (a * b) は、 「型aと型bのタプル」
| Hash of NBitcoin.uint256
| Time of uint32
| Threshold of uint32 * Policy<'P>[]
| And of Policy<'P> * Policy<'P>
| Or of Policy<'P> * Policy<'P>
| AsymmetricOr of Policy<'P> * Policy<'P>`AST` などではなく `Policy` と言う名前になっているのは、次回以降のステップで別の AST 表現を使うためです。 Miniscript が表現するのは解除条件の "ポリシー" であるため、この名前になっています。
Policy は内部にサブ Policy を含むので、自分自身を参照する再帰的データ構造になっています。
ここで嬉しいのが、 F# では再帰的なデータ構造を Rust よりも綺麗に扱うことができる点です。 Rust では再帰的データ構造で `Box<T>` や `Rc<T>` などのスマートポインタを使う必要があります。これは単に読み辛いだけでなく、うっかりライフタイム地獄にはまる可能性があります。もちろん Rust の方がコンパイラのパフォーマンスの面で有利なのですが、パフォーマンスはここでは重要ではありません。
では、文字列を受け取ってこの `Policy` を返す関数 (パーサ) を書いていくわけですが、その前に、逆の関数、すなわちこの Policy を文字列に返す関数を書きましょう。空白文字の扱いなどを考えなくて良いぶん、こちらの方が簡単です。
その３: Policy<'a> → string の変換
「Policy を受け取り、それぞれの場合についてパターンマッチを行い、必要に応じて再帰し、最終的に文字列を返す」関数なので、以下のような形式になるはずです。
let rec printPolicy (input: Policy<'a>): string =
match input with
| Key pk -> // それぞれの場合の処理F# は関数型言語なので、その他の変数と同じように関数を宣言します。
`=` の左に関数名や引数が、右に関数の実体がきます。
`rec` は再帰関数であることを示します。 `input` が引数で、 `Policy<'a>` というジェネリクス型であることを明示しています。
返り値が `string` であることも明示しています。
引数と返り値の型は明示しなくてもコンパイラが自動推論してくれるので、以下のようにもかけます。
let rec printPolicy p =
match p with
| Key k1 -> ...マッチ式の → の右側で、文字列を返せば OK です。
let rec printPolicy p =
match p with
| Key k1 -> sprintf "pk(%s)" (k1.ToHex())ここでは、 Key にマッチした時に、中身が k1 に格納されるようになっています。
上の Policy で定義した、NBitcoin.PubKey が k1 に入ります。この公開鍵を hex に変換した後、 `pk()` の中に埋め込んでいます。
同様に全パターンについて書いていき、以下のような関数になりました。
let rec printPolicy p =
match p with
| Key k1 -> sprintf "pk(%s)" (string (k1.ToHex()))
| Multi (m, klist) -> klist
|> Seq.map(fun k -> string (k.ToHex()))
|> Seq.reduce(fun a b -> sprintf "%s,%s" a b)
|> sprintf "multi(%d,%s)" m
| Hash h -> sprintf "hash(%s)" (string (h.ToString()))
| Time t -> sprintf "time(%s)" (string (t.ToString()))
| Threshold (m, plist) -> plist
|> Array.map(printPolicy)
|> Array.reduce(fun a b -> sprintf "%s,%s" a b)
|> sprintf "thres(%d,%s)" m
| And (p1, p2) -> sprintf "and(%s,%s)" (printPolicy p1) (printPolicy p2)
| Or (p1, p2) -> sprintf "or(%s,%s)" (printPolicy p1) (printPolicy p2)
| AsymmetricOr (p1, p2) -> sprintf "aor(%s,%s)" (printPolicy p1) (printPolicy p2)その4: string → Policy<'a> の変換
ではパーサを書きます。大きく以下の方針があり得ます。下にいくほど複雑なパターンの解析に向いています。相互排他的ではなく、混ぜて使うことも可能です。
1. 正規表現を使う。
2. Active Pattern を使う。
これは F# の特殊な機能の一つで、任意の値に対してパターンマッチできるような関数を生成する方法。
3. FParsec を使う。
Haskell の老舗の構文解析ライブラリである Parsec の F# バージョン。
今回は、以下の理由から1, 2 で行うことにしました。
1. 解析対象がそこまで複雑ではない。
2. セキュリティ上外部ライブラリに依存したくない。
3. F# 特有の機能を勉強したい。
アクティブパターンとは、一言で言うと任意の条件をパターンマッチで扱えるようにするための関数です。
大枠は、以下のような関数になります。
let rec (|Policy|_|) (s: string) =
match s with
| (* pk() 関数にマッチするパターン *) pk -> Some(Key pk) // Key は Policy の一種であることを思い出してほしい。
| (* multi() にマッチするパターン *) <multiの中身> -> (* 中身を Multi に与えて返す *)
// ...
| _ -> None // いずれにもマッチしなければ、None を返す。Some, None は Option 型として知られる判別共用体で、大抵の関数型言語に存在します。( `Maybe` という名前だったりします。)
関数名に (|Hoge|_|) を使っているのがアクティブパターンの目印です。この関数のおかげで、任意の文字列に対して「この文字列は Miniscript DSL としてパース可能か？」をパターンマッチで調べることができます。つまり以下のような使い方ができます。
let data1 = "pk(0225629523a16986d3bf575e1163f7dff024d734ad1e656b55ba94e41ede2fdfb6)"
match data1 with
| Policy p -> printfn "パースに成功しました！Policy は %A です" p
| _ -> failwith "パースに失敗したのでエラーを投げます :("ただマッチしているだけなのに、パースが行われているのが面白いですね。
4.1: 再帰的でないパターンのパース
まずは、再帰的でないパターンのパースを実装します。
このままだと、上記の「pk() 関数にマッチするパターン」の構築ができなくて困るので、 pk() にマッチする独立のアクティブパターンを作ってあげましょう
let (|PKExpression|_|) (s: string) =
let s = s.TrimStart()
if s.StartsWith("pk") then
Some (s.Substring(2)) // "pk" 部分以外を一緒のデータとして返す
else
Noneこれで、マッチ側では以下のようにして使用できます。
let rec (|Policy|_|) (s: string) =
match s with
| PKExpression pkHex -> Some(Key new NBitcoin.PubKey(pkHex))
このままだと、pkHex には公開鍵の hex 表現に加えて "(", ")" が含まれているため、 `PubKey` のコンストラクタが受け付けずエラーになってしまいます。PKExpression 側で、トリミングしても良いのですが、より応用が利くように、再利用可能な形で別のパターンマッチとして定義してみましょう。
let quoted = Regex(@"\((.*)\)")
let rec (|SurroundedByBrackets|_|) (s: string) =
let s2 = s.TrimStart()
let matchC = quoted.Matches(s2)
if matchC.Count <> 0 then
let last = matchC.Count
let lastMatch = matchC.[last - 1]
let contentStr = lastMatch.Value.TrimStart('(', ' ').TrimEnd(')', ' ')
let contents = contentStr.Split(',')
Some (contents)
else
Noneここでは正規表現によるアクティブパターンの例を示すため、dotnet の Regex モジュールを使って `()` の中身のデータを取得しています。
- この程度のパターンでは正規表現は必須ではないですが、好きなようにかけるのがアクティブパターンの良いところです。
- 空白の扱いなどは現時点で適当です。テストを書いて詰めていきましょう。
`,`で中身を分割し、string の配列として返しています。
これを使って、マッチ側を以下のように変更します。
let rec (|Policy|_|) (s: string) =
match s with
| PKExpression (SurroundedByBrackets pkHex) ->
Some(Key new NBitcoin.PubKey(pkHex.[0]))コンパイルエラーがなくなったので、次は `Multi` へのマッチを書いていきましょう。
`PKExpression` と同じように、 `MatchExpression` を定義しても良いですが、 `pk()` も `multi()` も、他の関数も全て、同様の構造をしているので、PKExpression を以下のように更新して再利用可能にしてあげましょう。
let (|Expression|_|) (prefix: string) (s: string) =
let s = s.TrimStart()
if s.StartsWith(prefix) then
Some (s.Substring(prefix.Length))
else
Noneこれで、 `MatchExpression` を定義することなく、以下のようにかけます。
let rec (|Policy|_|) (s: string) =
match s with
| Expression "pk" (SurroundedByBrackets pk) ->
Some(Key new NBitcoin.PubKey(pkHex.[0]))
| Expression "multi" (SurroundedByBrackets pks) -> Some(Multi((* pks を、Multi が受け付ける形に変換して返す。 *)))Multi が受け付ける形は何でしょう？最初に定義した `Policy<'T>` の定義を思い出しましょう。uint32 * PubKey[] でした。pks は `string[]` なので適当に変換します。(面倒なので省略)
ただ、ここにはもう一つ問題があります。公開鍵の値が不正だった場合に、PubKey のコンストラクタが例外を投げることです。API を使う側は純粋関数のつもりで使うので、今回は単に None を返すように変更します。
// 単一の PubKey の hex にマッチし、PubKey 型にパースして返す。
let (|PubKeyPattern|_|) (s: string[]) =
if 1 < s.Length then
None
else
let s = s.[0]
try
Some(PubKey(s))
with
| :? FormatException as ex -> None
// 同様に PubKeysPattern も定義する(中略)
// ...
let rec (|Policy|_|) s =
match s with
| Expression "pk" (SurroundedByBrackets (PubKeyPattern pk)) -> Some (Key pk)
| Expression "multi" (SurroundedByBrackets (PubKeysPattern pks)) -> Some(Multi((fst pks), (snd pks)))4.2: 再帰的パターンに対するマッチングのケース
同様に、`"threshold"` という単語にマッチして、後続の() の中身をThreshold 型の中身に変換して返します。
let (|Threshold|_|) (s: string[]) =
if s.Length < 2 then // 最初に数字と、その後に一つ以上の subexpression が必要なので
None
else
let thresholdStr = s.[0]
match UInt32.TryParse(thresholdStr) with
| (true, threshold) ->
let subPolicy = s.[1..s.Length] |> Array.choose((|Policy|_|))
if subPolicy.Length <> s.Length then
None
else
Some (threshold, subPolicy)
| (false, _) -> None
let rec (|Policy|_|) s =
match s with
| Expression "pk" (SurroundedByBrackets (PubKeyPattern pk)) -> Some (Key pk)
| Expression "multi" (SurroundedByBrackets (PubKeysPattern pks)) -> Multi((fst pks), (snd pks)) |> Some
| Expression "thres" (SurroundedByBrackets (Threshold thres)) -> Some(Threshold(thres))残念ながら、これはコンパイルしません。なぜかというと、 `(|Threshold|_)` パターンマッチの中で
`(|Policy|_|)` パターンマッチを使用しているためです。
F# では、ファイル中の定義の順番が重要なので、上で定義した値を下で使うことはできますが、その逆はできません。一見不便な仕様ですが、依存関係が常に上から下に流れるため、コードを読むのが容易になります。
では、逆に `(|Threshold_|)` を `(|Policy|_|)` の下に持ってきたら良いでしょうか？残念ながらこれもダメです。同じ理由で `(|Poiicy|_|)` 中で Threshold を使うことができなくなります。
このように循環参照している関数の場合、 `and` キーワードでまとめて定義します。
let rec (|Policy|_|) s =
match s with
| Expression "pk" (SurroundedByBrackets (PubKeyPattern pk)) -> Some (Key pk)
| Expression "multi" (SurroundedByBrackets (PubKeysPattern pks)) -> Multi((fst pks), (snd pks)) |> Some
| Expression "thres" (SurroundedByBrackets (Threshold thres)) -> Some(Threshold(thres))
| _ -> None
and (|Threshold|_|) (s: string[]) =
if s.Length < 2 then
None
else
let thresholdStr = s.[0]
match UInt32.TryParse(thresholdStr) with
| (true, threshold) ->
let subPolicy = s.[1..s.Length] |> Array.choose((|Policy|_|))
if subPolicy.Length <> s.Length then
None
else
Some (threshold, subPolicy)
| (false, _) -> Noneこれで、全てのパターンを定義できるようになったので、あとはひたすら書いていき、テストを用意 → デバッグしたら完成です。
テストは Expecto というフレームワークを使っています。次回解説するかも
結語
パーサを作るのは初めてだったので四苦八苦しました。 F# は良質なドキュメントが多くて助かります。
note.mu は現時点でコードを書くのに向いていないなあと思いました。インラインコードがないのは辛いです。
今回作成したものはこちらにあります。
次回以降はこの Policy をコンパイルする処理を書いていこうと思います(気力があれば)