smart
ブロックチェーンの数理と実装



DaiLambda, Inc.
Jun FURUSE/古瀨 淳
応用数理I,社会数理概論I, Nagoya university, 2023-04-26

スマートコントラクト概論

アカウントが保持する状態

最小限のものは、

公開鍵
アカウントからの送金命令を検証するため
バランス
アカウントにあるトークン残高
カウンター
リプレイ攻撃を防ぐ整数

余談: カウンターとリプレイ攻撃について

アカウント \(a\) の送金命令 \(O_a\) には \(a\) の署名がある。

リプレイ攻撃

\(a\) 以外の者が \(a\) の送金命令 \(O_a\) を偽造することは出来ないが、
過去 \(a\) が実行した \(O_a\) のデータは公開されているので、
再度実行させること狙ってブロックチェーンに送りつける。

悪意ある攻撃でなくとも、ウォレットの不調などで、 \(a\) 自身が同じ命令 \(O_a\) を複数回送ってしまうことはある。

再度実行をどう防ぐか → カウンター

カウンター

\(a\) のアカウント状態にカウンター \(c \in \mathbb{N}\) を置く。

\(O_a\) を作る際、現在の \(a\) のカウンター値 \(c\) を記載する: \(O_a[c]\)

ブロックチェーンプロトコルが \(O_a[c]\) を受け取ったら:

\(a\) のカウンタの値が \(c\) と同じ時
\(O_a[c]\) を正当とみなす。\(O_a[c]\) がブロックに取り込まれ、
実行された場合は、 \(a\) のカウンタは \(c+1\) になる
\(a\) カウンタの値が \(c\) ではない時
\(O_a[c]\) は不正とみなされ、ブロックに取り込まれない

このようにして同一命令の再度実行を防ぐ。

アカウントが保持する状態

  • 公開鍵
  • バランス(残高)
  • カウンター

これらのフィールドもデータだが、変更は強い制限がある:
公開鍵: 変更不可, バランス: 総量の保持, カウンター: 増加のみ

これだけでは汎用データベースにはならない…

汎用データベースに向けて

各アカウントに追加:

ストレージ
汎用データ保存域
コード
ストレージの変更権の認証や変更ロジックを記述。
アカウントごとに独自の動作を設定可能

スマートコントラクト

実行トリガー
アカウントへの送金によってコードが起動。
(送金額0 = コード起動のためだけのメッセージ)
コード実行の連鎖
コードから他のアカウントへの送金が可能。
送金先にコードがあればコード実行が連鎖する

単なるプログラムの実行だけでなく、自動送金も(したければ)できる。 契約の自動執行。

スマートコントラクト実行の安全性

スマートコントラクトとして任意のプログラムが実行できると、
ブロックチェーンは安全性を保つことができない:

  • ストレージ以外の記憶域、例えば自分のバランスを書きかえる
  • 許可されない情報を読み込みネットワークを介して漏洩させる
  • 無限ループなどで分散型サービス拒否攻撃を発生させる
  • etc. etc… まあ、なんでもできる

実行できる命令を大幅に制限する必要がある。

仮想機械によるスマートコントラクト実行

スマートコントラクトのコードを

  • Virtual Machine の命令列に制限
  • 実行を VM インタプリタを使って管理
    • 制限されたデータ読み込み (ストレージ + バランス + etc)
    • コントラクトのストレージ以外への書き込みを禁止
    • I/O の禁止
    • 無限ループの禁止

仮想機械によるスマートコントラクト実行

ブロックチェーンごとの独自 VM。 高級言語からの独自コンパイラを必要とする。主にスタックマシン:

最近の流行: 汎用VMを使えば、既存のコンパイラを利用可能:

VM を使っても危険が残る

スマートコントラクトにバグや脆弱性があると…
意図せぬ誤動作(送金)をしてしまう。
(コントラクトは書かれたバグをそのまま実行するだけだが)
無制限にコンピューターリソースを使いだすと…
各ノードが同じコードを実行、それぞれのリソースを使い尽くす。
DDoS によりブロックチェーンが停止する。

前者は、バグのないスマートコントラクトを書いてとしか言えない。 (バグが発生しにくい VM や言語のデザインはあるが)

後者は VM 命令の実行時にリソース管理をすれば回避できる
→ ガス管理

ガス管理

ガスによる計算量制限

ガス: 各種操作の実行時間の見積もり

\[実行時間 ∝ 消費ガス量\]

になるように各操作のガス値を設計

ガスによる送金命令 \(O\) の計算量制限

送金命令の作成
仮に \(O\) を実行してガス消費見積もり \(g_O\) を宣言
送金命令の実行
スマートコントラクト実行などの各操作がガスを消費していく
ガス欠
\(O\) の実行中、総ガス消費量が見積もり \(g_O\) を超えたら、ガス欠。
実行を中断。罰金として手数料だけ取られる。
正常終了
見積もり \(g_O\) を上回るガス消費なく \(O\) が完了できれば成功。

ブロック \(B\) のガス制限

ガスリミット定数 \(G\): 各ブロック \(B\) での総ガス消費量上限

\(B\) の条件として、

\[G \geq \sum_{O\in B} g_O\]

を追加。

ブロック処理の最大時間を \(G\) で制限できる。

\(G\) を消費する時間 < ブロック更新間隔(Tezos は 15秒)

スマートコントラクトのガス消費

ガス消費
各VM命令実行前に、その命令分のガス量を消費。
ガス欠
今までの総消費量が \(O\) の見積もり \(g_O\) を超えたらガス欠。

各VM命令のガス消費量計測

ベンチマークによる実行時間計測と推論

ベンチマーク
各命令に対し、様々な入力を与え、実行時間を計測
ガスモデル
入力に対する実行時間変化のモデル
(ex. \(実行時間 = 入力データサイズの和 * x\))
ガスパラメータ推論
線形回帰による、ベンチマークの計測データのモデルへの適合。
モデルの変数の値を推論。
VM 実行系への反映
VM命令の実行部で求めたパラメータを使ったガス消費を行う

ガス推論例: 文字列の連結 CONCAT

ベンチマーク

CONCAT に対し、様々長さの文字列2つを与え、実行時間を計測

{ "workload":
    [ [ "N_IConcat_string_pair",
        [ [ "str1", "1201" ], [ "str2", "54391" ] ] ],
        // 1201 bytes と 54391 bytes の連結
      [ "N_IHalt", [] ] ],
  "measures":
    [ 3215, 3329, 3693, 3315, 3371, 3810, 3523, 3625, ..
      // 繰り返し実行し実行時間 nano secs のサンプルを取る
{ "workload":
    [ [ "N_IConcat_string_pair",
        [ [ "str1", "38036" ], [ "str2", "14145" ] ] ],
      [ "N_IHalt", [] ] ],
  "measures":
    [ 3587, 3141, 3197, 3398, 3156, 3202, 3433, 3074, ..

ガス推論例: 文字列の連結 CONCAT

モデル

\(a\) と \(b\) を連結する文字列のそれぞれのバイト数とすると、
おそらく実行時間の増加はその合計に比例するだろう:

\[\mathrm{model}(a, b) = \mathit{intercept} + \mathit{coeff} ~× (a+b)\]

パラメータ

\(\mathit{coeff}\) : 増加率の傾き

\(\mathit{intercept}\) : 切片。 CONCAT 自体の起動に必要な時間

ガス推論例: 文字列の連結 CONCAT

線形回帰による推論

Scikit-learn の LASSO回帰を使って、ベンチマークデータからモデルパラメータを推論:

free_variables:
  builtin/Timer_latency = 13
  interpreter/N_IConcat_string_pair_coeff = 0.0612222900743
  interpreter/N_IConcat_string_pair_intercept = 37.3123382529
  ...

解

\(\mathit{coeff} = 0.06122229\),
\(\mathit{intercept} = 37.3123382\)

ガス推論例: 文字列の連結 CONCAT

\(\mathit{coeff} = 0.06122229\),　　\(\mathit{intercept} = 37.3123382\)