准备知识

Commitment

Commitment Scheme
1. 举例：Merkle tree
  1. 流程
    1. commit：P（Prover）构建tree，发布root
    2. reveal：P展现一个leaf及其branch
    3. check：V（Verifier）验证branch
  2. 特性
    1. binding：commit之后，所有可以reveal的leaf就已确定
    2. hiding：reveal时只展示了其中的一个
2. 一些Commitment
  1. 各种hash：SHA256、Pedersen、MiMC
  2. 各种tree：Merkle、MPT
  3. ZKP系列：KZG、FRI、IPA
Commit一段计算
1. 流程
  1. commit：P发布计算f(x)=35，承诺知道其解x
```
# 计算f(x) = x^3 + x + 5 = 35
# 解x = 3
def f(x):
  y = x**3
  assert y + x + 5 == 35
```
  2. reveal：P公布解x
  3. check：V将解x代入计算f(x)=35进行验证
  4. 解的变量x又称作计算的input，中间变量y又称作witness
2. 实现
  1. 链上运行的时候要减少发布的尺寸和验证的计算量
  2. ZK Rollup
    1. 发布：将计算编译为电路，发布电路的commitment（逻辑和变量在ZKP电路中又称作gate constraints和copy constraints）
      
      https://vitalik.ca/general/2019/09/22/plonk.html
    2. 验证：用一个基于ZKP的validity proof做简洁的验证
  3. Optimistic Rollup
    1. 发布：将计算编译为合约内虚拟机（AVM、OVM）的字节码，发布字节码的commitment
    2. 验证：fraud proof & interactive proving，V要求P在链上重新执行部分计算直至发现错误
      
       https://zerocap.com/insights/research-lab/arbitrum-arb-deep-dive/
BitVM提出了在比特币上Commit一段计算的方法，其过程完全借鉴Optimistic Rollup
1. 发布：计算→Binary Circuit→opcode script→taproot commitment，编译结果是链上可执行的
2. 验证：pre-sign几种类型的交易（challenge、response等），需要interactive proving的时候将他们上链来进行

Pre-sign Off-chain Transactions

由P和V pre-sign一些链下交易
1. 交易的input包含P和V的联合签名，确保交易的inputs和outputs符合各个场景下（challenge、response等）的格式要求
2. 交易的output使用Taproot，即满足多个条件中的任意一个即可unlock这个output
  
  https://blog.bitmex.com/the-schnorr-signature-taproot-softfork-proposal/
  1. output只展示树根，input展示任一叶子（locking script）及其对应的unlocking script，执行成功则解锁output
  2. 既能将复杂计算上链（可以包含很多并行的解锁条件），又节省链上空间和保护隐私（只展示其中的一个解锁条件）
  3. Taproot也是一种Commitment Scheme
这些交易在interactive proving的时候上链，以保证interactive proving按照既定流程进行。

BitVM

Binary Circuit Commitment

计算→Binary Circuit→opcode script→taproot commitment，重点提出了
1. 用Bit Value Commitment实现电路中的copy constraints
2. 用Logic Gate Commitment实现电路中的gate constraints
Bit Value Commitment
1. 一段Bitcoin script，可简记为<hash_0> <hash_1> OP_BITCOMMITMENT
  1. unlock的时候，输入preimage0则返回0，输入preimage1则返回1
2. Commitment Scheme
  1. commit：P发布<hash_0> <hash_1> OP_BITCOMMITMENT
  2. reveal：P展现<preimage>
  3. check：V验证<preimage> <hash_0> <hash_1> OP_BITCOMMITMENT
3. 特性
  1. binding：commit之后，所有可以reveal的preimage就已确定
  2. hiding：reveal时只展示了其中的一个preimage
4. 在电路中多处使用同一个Bit Value Commitment，实现copy constraints
  1. 如果P把两个preimage都reveal了，则破坏了copy constraints，这种情况称做Equivocation，允许V立刻punish P
Logic Gate Commitment
1. 将Bit Value Commitment作为输入和输出组装成logic gate，实现gate constraints
2. 可简记为<hash_c0> <hash_c1> <hash_b0> <hash_b1> <hash_a0> <hash_a1> OP_GATECOMMITMENT，对应的unlocking script是<preimage_a> <preimage_b> <preimage_c>
3. P发布一个Logic Gate Commitment表示其承诺3个Bit Value Commitment打开后符合gate的逻辑约束
组合成Binary Circuit Commitment
1. A, B, C, D是input，E, F, G, H, I, J, L是witness
2. P发布一个Binary Circuit Commitment
  1. 即发布电路中所有的Logic Gate Commitment<hash_c0> <hash_c1> <hash_b0> <hash_b1> <hash_a0> <hash_a1> OP_GATECOMMITMENT；其中一些包含相同的<hash_0> <hash_1>则表示电路相连
  2. 表示其承诺电路中所有Bit Value Commitment打开后符合电路的逻辑约束
最终发布Circuit Taproot，减小发布的尺寸

准备知识

Commitment

Pre-sign Off-chain Transactions

BitVM

Binary Circuit Commitment

Challenges and Responses