本文主要是介绍以比特币脚本来实现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 , ⋯ f_1,f_2,f_3,\cdots f1,f2,f3,⋯ 无需按顺序排列。其输入输出可形成任何类型的DAG。因此不需要在每一步中发送全局信息。
- commitment脚本可以使用条件。如,“若 z 3 = = 1 z_3 == 1 z3==1,则承诺 z 11 z_{11} z11,否则承诺 z 17 z_{17} z17”
- 可使用 f i f_i fi 的提示/辅助输入,如提供某inverse倒数,然后使用乘法来验证。
- 可将脚本输入预先解析为正确的格式。如,将某value以bits在stack上表示,而不是30-bit limbs。
将 STARK 包裹进 SNARK。一次性设置可实现快速、紧凑的通用计算。- 如,RISC0:Bonsai 和 Local
- disproveTx 可非常大,因为只有不诚实的Prover才需要为此付费。
- 可对中间结果进行哈希处理,压缩assertTx,但代价是必须在 disproveTx 中计算哈希函数。
参考资料
[1] SNARK Verifier in Bitcoin Script
这篇关于以比特币脚本来实现SNARK Verifier的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!