以比特币脚本来实现SNARK Verifier

1. 引言

前序博客有：

• 基于BitVM的乐观 BTC bridge
• BitVM：Bitcoin的链下合约
• Bitcoin Bridge：治愈还是诅咒？
• BitVM2：比特币上的无需许可验证

比特币脚本的基础限制有：

• 最大脚本size为：4MB
• 最大stack size为：altstack + stack，一共小于1000个元素
• 单个stack元素最大size为：520字节
• 算术opcodes的最大输入size为：32-bit words

比特币脚本的实际限制为：

• 以32-bit words的最大脚本输入：1000 items * 32-bit/item = 32 kB
• 脚本之间传输状态的开销为：
  • 使用Winternitz签名：31 bytes per bit
  • 1 stack item for every 4bits（每个item 20字节）
  • 每个Script的最大输入状态size：1000 items * 4 bit/item = 4000 bits = 500 bytes（需要20kB签名数据）
  • 单个full block可承诺数据量约为：4 MB / block * 31 bytes / bit = 16 kB

2. 可能的证明系统

可 以比特币脚本实现的，可能的证明系统有：

• Groth16 ( 22000 Fq multiplications )
• FFlonk ( 14000 Fq multiplications + hash function )
• FFlonk + slonk

这3个证明系统均基于BN254曲线。

这些证明系统的示例实现有：

• Arkworks的 https://github.com/arkworks-rs/groth16
• Iden3的 https://github.com/iden3/snarkjs

3. 以比特币脚本来实现SNARK Verifier

以比特币脚本来实现SNARK Verifier，对应的代码模块有：

• Lamport signatures / Winternitz signatures
• u256 arithmetic
  • addition, multiplication, Karatsuba multiplication
• bn254 field arithmetic
  • addition, multiplication, inversion
  • Montgomery reduction
• bn254 curve operations
  • point addition, inversion, scalar multiplication
• bn254 degree-2, degree-6, and degree-12 extensions
• bn254 pairings
  • constant vs variable inputs

4. 复杂度分析

以比特币脚本来实现SNARK Verifier，对应的复杂度分析为：

• Groth16 Proof size约为300个字节。其public inputs还另需约100个字节。
• 当前，占满比特币整个区块空间的手续费小于0.3BTC，约2万美金。
• assertTx可能需承诺多达16KB的trace数据。
• 单个degree-12 extension field element 约为3 KB。因此assertTx可能需承诺多达5个中间结果。
• 因此，Verifiers可能需从多达6个disproveTx Tapscripts中选择，且所有Tapscripts的组合size将多达 6 x 4 MB = 24 MB。

5. 优化思路

以比特币脚本来实现SNARK Verifier，当前的优化思路有：

• Prover可在其kickoffTx中做另一large commitment。
• 可使用一系列的commit交易，高效将该commitment分散至多个区块。
• $f_1,f_2,f_3,\cdots$ 无需按顺序排列。其输入输出可形成任何类型的DAG。因此不需要在每一步中发送全局信息。
• commitment脚本可以使用条件。如，“若 $z_3==1$，则承诺 $z_{11}$，否则承诺 $z_{17}$”
• 可使用 $f_i$ 的提示/辅助输入，如提供某inverse倒数，然后使用乘法来验证。
• 可将脚本输入预先解析为正确的格式。如，将某value以bits在stack上表示，而不是30-bit limbs。
  将 STARK 包裹进 SNARK。一次性设置可实现快速、紧凑的通用计算。
  • 如，RISC0：Bonsai 和 Local
• disproveTx 可非常大，因为只有不诚实的Prover才需要为此付费。
• 可对中间结果进行哈希处理，压缩assertTx，但代价是必须在 disproveTx 中计算哈希函数。

参考资料

[1] SNARK Verifier in Bitcoin Script