BitVM及其优化思考-3. BitVM优化

3.1 基于ZK降低OP交互次数

当前有2大主流Rollups：ZK Rollups和OP Rollups。其中，ZK Rollups依赖于ZK Proof的有效性验证，即正确执行的密码学证明，其安全性依赖于计算复杂度假设；OP Rollups依赖于Fraud Proof，假设所提交的状态均是正确的，设定挑战周期通常为7天，其安全性假定系统内至少有一个诚实方能探测到不正确的状态，并提交欺诈证明。假设BitVM挑战程序最大步数为$2^{32}$，需要内存为$2^{32}\ast 4$字节，约17GB。在最坏情况下，需要约40轮挑战和响应，约半年时间，总脚本约150KB。该情况下激励严重不足，但实际情况下几乎不发生。
考虑使用零知识证明降低BitVM的挑战次数，从而提高BitVM的效率。根据零知识证明理论，如果数据$Data$满足算法$F$，则证明proof满足验证算法$Verify$，即验证算法输出True；如果数据$Data$不满足算法$F$，则证明proof也不满足验证算法$Verify$，即验证算法输出False。在BitVM系统中，如果挑战者不认可证明方提交的数据，则发起挑战。
对于算法$F$，使用二分法拆开，假设需要$2^n$次，则能找到错误点；如果算法复杂度太高，则n较大，需要很久才能完成。但是，零知识证明的验证算法$Verify$的复杂度是固定的，公开证明proof和验证算法$Verify$全过程，发现输出为False。零知识证明的优势在于打开验证算法$Verify$所需的计算复杂度，相比于二分法打开原始算法$F$，要低得多。因此，借助零知识证明，让BitVM挑战的不再是原始算法$F$，而是验证算法$Verify$，降低挑战轮数，缩短挑战周期。
最后，虽然零知识证明有效性和欺诈证明依赖于不同的安全假设，但是可将二者结合，可构建ZK Fraud Proof，实现On-Demand ZK Proof。不同于full ZK Rollup，不再需要为每个单个状态变换生成ZK proof，On-Demand模型使得，仅在有挑战时才需要ZK Proof，而整个Rollup设计仍是乐观的。因此，仍默认所生成的状态是有效的，直到有人挑战该状态。如果某个状态无挑战，则无需生成任何ZK Proof。但是，如果参与方发起挑战，则需为挑战区块内所有交易的正确性生成ZK Proof。未来，可探索为单个有争议指令生成ZK Fraud Proof，避免一直生成ZK Proof的计算成本。

3.2 比特币友好的一次性签名

比特币网络中，遵循共识规则的交易是有效交易，但除共识规则之外，还额外引入了standardness规则。比特币节点仅转发广播标准交易，有效但非标准的交易被打包的唯一方法直接是与矿工合作。
根据共识规则，legacy（即non-Segwit）交易的最大size为1MB，即占满整个区块。但legacy交易的standardness上限为100kB。根据共识规则，Segwit交易的最大size为4MB，即weight limit。但Segwit交易的standardness上限为400kB。
Lamport签名是BitVM的基础组件，降低签名和公钥长度，有助于降低交易数据，从而降低手续费。Lamport一次性签名需使用哈希函数（如one way permutation函数f）。Lamport一次性签名方案中，消息长度为v比特，公钥长度为2v比特，签名长度也为2v比特。签名和公钥较长，需要消耗大量的存储gas。因此，需要寻找类似功能的签名方案，以降低签名和公钥长度。相比Lamport一次性签名，Winternitz一次性签名的签名和公钥长度大幅降低，但是增加了签名和验签的计算复杂度。
在Winternitz一次性签名方案中，使用特殊函数$P$将$v$比特的消息映射为长度为$n$的向量$s$。$s$中每个元素的取值为 { 0 , ⋯   , d } \{0,\cdots,d\} {0,⋯,d}。Lamport一次性签名方案是$d=1$特殊情况下的Winternitz一次性签名方案。在Winternitz一次性签名方案中，$n,d,v$之间的关系满足：$n\approx v/{\log }_2(d+1)$。当$d=15$时，有$n\approx (v/4)+1$。对于包含$n$个元素的Winternitz签名而言，比Lamport一次性签名方案中的公钥长度和签名长度短4倍。但是，验签的复杂度提高了4倍。在BitVM中使用$d=15,v=160,f=ripemd160(x)$实现Winternitz一次性签名，可将bit commitment size降低50%，从而将BitVM的交易费降低至少50%。未来，在对现有Winternitz比特币脚本实现进行优化的同时，可探索以比特币脚本表达的更紧凑的一次性签名方案。

3.3 比特币友好的哈希函数

根据共识规则，P2TR script的最大size为10kB，P2TR script witness的最大size与最大Segwit交易size一样，为4MB。但P2TR script witness的standradness上限为400kB。
当前比特币网络还不支持OP_CAT，无法拼接字符串做Merkle path验证。因此，需用现有比特币脚本，以script size和script witness size最优的方式，实现一种比特币友好的哈希函数，从而支持merkle inclusion proof验证功能。
BLAKE3为BLAKE2哈希函数的优化版，并引入了Bao tree模式。相比于BLAKE2s-based，其压缩函数的轮数由10降至7。BLAKE3哈希函数会将其输入切分为1024字节大小的连续chunks，最后一个chunk可能更短但不为空。当只有一个chunk时，则该chunk为root node，且为该树的唯一节点。将这些chunks排布为二进制树的叶子节点，然后对每个chunk独立压缩。
当将BitVM用于验证Merkle inclusion proof场景时，哈希运算的输入由2个256-bit哈希值拼接而成，即哈希运算的输入为64字节。使用BLAKE3哈希函数时，这64字节可分配于单个chunk内，整个BLAKE3哈希运算仅需要对单个chunk应用一次压缩函数。BLAKE3的压缩函数中，需要运行7次轮函数和6次置换函数。
目前BitVM中已完成基于u32值的XOR、模加、位右移等基础运算，可以很容易组装出比特币脚本实现的BLAKE3哈希函数。使用stack中4个分开的字节来表示u32 words，来实现BLAKE3所需的u32 addition、u32 bitwise XOR 和 u32 bitwise rotations。目前BLAKE3哈希函数比特币脚本共约100kB，足以用于构建一个toy版本的BitVM。
此外，可拆分这些BLAKE3代码，使得Verifier和Prover可通过将挑战-响应游戏中的执行一分为二而不是完全执行来显著降低所需的链上数据。最后，使用比特币脚本实现Keccak-256、Grøstl等哈希函数，从中选出最比特币友好的哈希函数，并探索其它新的比特币友好哈希函数。

3.4 Scriptless Scripts BitVM

Scriptless Scripts是一种通过使用Schnorr签名，在链下执行智能合约的方法。Scripless Scripts概念诞生自Mimblewimble，除了kernel及其签名之外，不存储永久数据。
Scriptless Scripts的优点是功能、隐私和效率。

• 功能：Scriptless Scripts可增加智能合约的范围和复杂性。比特币脚本能力受限于网络中已启用的OP_CODES数量，而Scriptless Scripts将智能合约的规范和执行从链上转移到仅设计合约参与方的讨论，无需等待比特币网络的分叉来启用新的操作码。
• 隐私：将智能合约的规范和执行从链上转移到链下，可增加隐私。在链上，合约的很多细节都会共享到整个网络，这些详细信息包括参与者的数量和地址以及转账金额等。通过将智能合约移至链下，网络只知道参与者同意其合约条款已得到满足且相关交易有效。
• 效率：Scriptless Scripts最大限度地降低链上验证和存储的数据量。通过将智能合约移至链下，全节点的管理费用会减少，用户的交易费用也会降低。

Scriptless scripts是一种在比特币上设计密码学协议的方法，可避免执行显式智能合约。核心思想是使用密码算法实现期望功能，而不是使用脚本实现功能。适配器签名和多重签名，是Scriptless scripts的原始构建基石。使用Scriptless scripts，可实现比常规交易更小的交易，降低交易手续费。
可借助Scriptless Scripts，使用Schnorr多重签名和适配器签名，不再像BitVM方案那样提供哈希值和哈希原像，也可实现BitVM电路中的逻辑门承诺，从而可节约BitVM脚本空间，提高BitVM效率。虽然现有的Scriptless Scripts方案能降低BitVM脚本空间，但是需要证明者和挑战者有大量交互来组合公钥。未来将对该方案进行改进，同时尝试将Scripless Scripts引入到具体BitVM功能模块内。

3.5 无需许可的多方挑战

当前BitVM挑战默认需要许可的原因在于：Bitcoin的UTXO仅能执行一次，导致恶意的verifier可通过挑战诚实prover来“浪费”该合约。当前BitVM限定为两方挑战模式。试图作恶的prover，可同时用自己控制的verifier发起挑战，从而“浪费”该合约，使得作恶成功，而其它verifier无法阻止该行为。因此，在Bitcoin基础之上，需要研究无需许可的多方OP挑战协议，可将BitVM的现有1-of-n信任模型，扩展至1-of-N。其中，N远大于n。此外，需要研究解决挑战者与prover串谋或恶意挑战“浪费”合约的问题。最终实现信任更小的BitVM协议。
无需许可的多方挑战，允许任何人在没有许可名单的情况下参与。这就意味着，用户可在没有任何可信第三方参与的情况下，从L2提币。此外，任何想要参与OP挑战协议的用户均可质疑和删除无效提款。
将BitVM扩展为无需许可多方挑战模型，需解决如下攻击：

• 女巫攻击：即使攻击者伪造多个身份参与争议挑战，单个诚实参与方仍能够赢得争议。如果诚实参与方捍卫正确结果的成本，与对攻击者的数量呈线性关系时，则当涉及大量攻击者时，诚实参与方为赢得争议所需付出的成本将变得不切实际，且容易受到女巫攻击。论文 Permissionless Refereed Tournaments 中，提出一种改变游戏规则的争议解决算法，单个诚实参与方赢得争议的成本随着对手的数量呈对数增长，而不是线性增长。
• 延迟攻击：某个或一群恶意方，遵循某种策略来阻止或延迟正确结果（如将资产提取到L1）在L1上的确认，并迫使诚实的prover花费L1手续费。可要求挑战者需提前质押来缓解该问题。如果挑战者发起延迟攻击，则没收其质押。但是，如果攻击者愿意在一定限度内牺牲质押来追求延迟攻击，则应该有应对策略来降低延迟攻击的影响。论文 BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol提出的算法，使得无论攻击者愿意失去多少质押，最坏情况下的攻击只能导致一定上限的延迟。
  未来，将探索适用于比特币特性的，可抵抗以上攻击问题的BitVM无需许可多方挑战模型。