Upgrade to Pro — share decks privately, control downloads, hide ads and more …

BitVM

 BitVM

GBECの解説動画のスライドです。
https://goblockchain.network/2024/05/bitvm/

shigeyuki azuchi

May 28, 2024
Tweet

More Decks by shigeyuki azuchi

Other Decks in Technology

Transcript

  1. 2 任意のロジックを回路にコンパイル
 【一般的なプログラム】
 1. 高級言語を使ってコードを記述する
 2. コンパイラが最終的に機械語(0 or 1)に変換
 3.

    専用回路(CPUなど)でそれが実行される
 
 
 あらゆる計算はなんらかの回路の形で表現できる
 
 
 
 
 BitVMではNANDゲートのみを使用↑ 
 (NANDゲートの組み合わせで他の論理ゲートは構築可能) 
 OR
 
 AND
 XOR
 NOR
 NAND

  2. 3 Bitcoin ScriptでNANDゲートを実現
 Bitcoin Scriptの2つのopcodeを使えばNANDゲートを実現できる:
 
 • OP_BOOLAND
 スタックから2つの要素を取得して、両方とも非0であれば1を、
 それ以外であれば0をスタックにプッシュする


    
 • OP_NOT
 スタックから1つ要素を取得して、要素が0 or 1の場合それを反転して
 スタックにプッシュ
 
 記述を簡素化するため↑の組み合わせをOP_NAND opcodeとする。

  3. 4 Bit Value Commitment
 NANDゲートの入力値、出力値に対するコミットメント
 OP_IF
 OP_HASH160
 <hash1>
 OP_EUALVERIFY
 <1>


    OP_ELSE
 OP_HASH160
 <hash0>
 OP_EUALVERIFY
 <0>
 OP_ENDIF
 入力値に対して0 or 1の値を出力するスクリプト 
 • 2つのハッシュ値(hash0、hash1)を使ったハッシュロック 
 • hash0のプリイメージが提供されると0が 
 • hash1のプリイメージ提供されると1が出力される 
 
 記述を簡素化するためこの機能を OP_BITCOMMITMENT opocdeとする
 

  4. 入力A、B、出力YのNANDゲートのコミットメント 
 
 
 
 
 各A, B, Yのhash0, hash1のプリイメージが提供されると

    
 スクリプトにより、
 
 A NAND B == Y
 
 が評価される。これが成立する場合のみアンロック可能 
 
 5 Logic Gate Commitment
 Bit Value Commitmentを組み合わせたゲートへのコミットメント
 # 出力Yの提供 
 <Yのhash0 or hash1のプリイメージ> 
 OP_BITCOMMITMENT 
 OP_TOALTSTACK # 出力値をアルトスタックに移動 
 
 # 入力Bの提供 
 <Bのhash0 or hash1のプリイメージ> 
 OP_BITCOMMITMENT 
 OP_TOALTSTACK # 入力値となる結果をアルトスタックに移動  
 
 # 入力Aの提供 
 <Aのhash0 or hash1のプリイメージ> 
 OP_BITCOMMITMENT 
 
 # 入力Bの値をメインスタックに移動 
 OP_FROMALTSTACK 
 
 OP_NAND
 # A NAND Bの結果がスタックにプッシュされる 
 
 # アルトスタックからYを読み込み 
 OP_FROMALTSTACK 
 # A NAND B = Yかどうかチェックする 
 OP_EQUALVERIFY 

  5. Logic Gate Commitmentを組み合わせると任意の回路を構成できる
 
 
 
 
 
 
 


    
 例:4つの入力(A, B, C, D)と8つのゲートを持つ回路
 
 ※ ただし、任意の計算をする場合、数十億個の巨大な回路になる
 6 Binary Circuit Commitment

  6. 7 Taptreeへのエンコード
 回路を構成したら、回路内の 
 各Logic Gate Commitmentをリーフノードとした 
 Taptreeを構成する
 


    
 
 各ゲートに対する入力値と出力値を提供すればツリー内の任意のゲートを実行できる 

  7. 8 チャレンジ&レスポンス
 【ここまで】
 1. 任意のロジックを回路にコンパイル 
 2. 回路に対するBinary Circuit Commitmentを作成

    
 3. 回路内の各Gate CommitmentをリーフとしたTaprootスクリプトを構成 
 
 → 任意のロジックの検証が可能なBitcoin Scriptを実現 
 
 【検証】
 基本的に証明者がコミットしたロジックの計算結果をオフチェーンで提供 
 その結果に誤りがある場合、ペナルティを課せる。 
 
 • 検証者は証明者に特定のゲートの実行を要求 
 • 証明者は指定されたゲートの実行結果で応答 

  8. 証明者と検証者はセットアップ時にチャレンジ&レスポンス用の事前署名済みTxチェーンを用意 
 9 チャレンジ&レスポンス
 • 検証者がチャレンジを開始 
 • 検証者がFraud Proofを提示

    
 • 証明者が1週間待機 
 • 証明者が結果を返答 
 • 検証者が1週間待機 
 検証者がプリイメージを 
 提供して実行ゲートを指定 
 証明者は指定された 
 ゲートを実行

  9. 証明者が誤った計算結果を提供した場合、検証者が資金を没収できる 
 10 チャレンジ&レスポンス
 証明者のレスポンスでは、2つの入力と出力値について、 
 0 or 1を返すために各値について、hash0とhash1のいずれかのプリメージを公開する 


    preimage A0 or A1 preimage B0 or B1 preimage E0 or E1 不正な計算結果を提供する場合、 
 同じ入力/出力値に対して異なる値が提示されることになり 
 その値の0と1を表す2つのプリイメージが公開される。 
 その場合、2つのプリイメージの提供により 
 検証者はコインを没収できる。 

  10. 11 BitVMの制限
 • プロトコルの参加者は2名に限定される 
 • 任意の計算をBitVM用の回路にコンパイルする高級言語はまだない 
 • 任意の計算の回路を作成する場合、ゲートの数は膨大になり、

    
 保持するデータ量も膨大になる(数百MB〜数GB) 
 • Fraud Proofベースの仕組みで、基本的に任意の計算をオンチェーンで実行する仕組みではない 
 • チャレンジの際、どのゲートを実行すれば効率的に証明できるのか判断するのは難しい 
 
 
 
 BitVM 2へ