Skip to content

Instantly share code, notes, and snippets.

@yangby-cryptape
Last active March 27, 2024 04:26
Show Gist options
  • Save yangby-cryptape/0d59a7c48b2e414fced9261a3290ba16 to your computer and use it in GitHub Desktop.
Save yangby-cryptape/0d59a7c48b2e414fced9261a3290ba16 to your computer and use it in GitHub Desktop.
[2024-02-21] BTC SPV on CKB

BTC Simplified Payment Verification (SPV) on CKB

Requirements

BTC SPV on CKB 需要的需求有:

  1. 更新必须进行合法性验证。
  2. 所有权和使用权分离。
  3. 尽量避免读写竞争问题。
  4. 可以用来验证 BTC TX 。
  5. 支持一定高度的 Revert (or Reorg)。

Refs:

SPV Client contracts 需要 4 个 Operations:

  • Initialiaze
  • Append
  • Revert (or Reorg)
  • Destory (only owner)

SPV Client 还需要提供 library,包含 1 个 function:

  • Prove if a TXID in SPV Client.

Detailed Design

SPV Cell

⚠️ 我看目前设计选了 MMR ,我先这么写了,看后续有无别的想法,因为我还没看完别的 SPV clients 实现。

一个 SPV Cell 的 Data 包含:

- index (用来做 Multi SPV Cells )
- min height
- max height
- hash of the max height header
- MMR root digest
- total diff from 0 to max height

A SPV Client Contains Multi SPV Cells

使用 Multi SPV Cells 的设计,是为了解决上面需求中的 "3. 避免读写竞争" 和 "5. 支持 Revert" 。

将一个 BTC SPV Client 设计成 $N+1$ 个 Cells ,其中:

  • $N$ 个 SPV Cells

    • 所有 SPV Cells 的 min height 都是相同的,这里记做 $H_{min}$

    • 所有 SPV Cells 的 max height 都是不同的,分别是:

      • $H_{min} + a_{0}$
      • $H_{min} + a_{0} + a_{1}$
      • $\cdots$
      • $H_{min} + a_{0} + a_{1} + \cdots + a_{n-2}$
      • $H_{min} + a_{0} + a_{1} + \cdots + a_{n-2} + a_{n-1}$

      其中 $a_{i} \gt 0$ ,代表每次更新 SPV 对应的 BTC height interval 。
      如果每个 BTC block 都立刻更新,就是 $a_{i} = 1$

      如果同步服务出现了异常中断,再恢复时可以设置 $a_{i} \gt 1$ 来提速同步。
      或者 reorg 的时候,不可能再去一个一个补,肯定也是一次多个 heights 快速同步,即 $a_{i} \gt 1$

  • $1$ 个 Index Cell

    由于有 Multi SPV Cells ,循环更新,所以需要:

    • 每个 SPV Cells 里记录自己的 Index Number ,
    • 有一个 Index Cell 来保存当前最新的一个 SPV Cell 的 Index Number 。

Update 操作

假设 Index Cell 里记录 Latest SPV Cell 的 index 为 $t$ 时,更新 SPV Client 更新:

  • CellDep 包含:
    • index 为 $t$ 的 SPV Cell
  • Inputs 包含:
    • index 为 $t+1$ (如果 $t+1 = N$ 则取 index 为 $0$) 的 SPV Cell
    • Index Cell
  • Outputs 包含:
    • index 为 $t+1$ (如果 $t+1 = N$ 则取 index 为 $0$) 的 SPV Cell 更新 Cell Data
    • Index Cell 将 index 修改为 $t+1$(如果 $t+1 = N$ 则为 $0$
  • Witnesses 包含:
    • 从 index 为 $t$ 的 SPV Cell 的 max height 开始的新的 headers 。

验证逻辑:

  • 检查 Index Cell 里 index 为 $t$
  • 检查 Witnesses 包含的 tip headers 是连续的,且验证 POW
  • 检查 Witnesses 包含的 tip headers 可以和 index 为 $t$ 的 SPV Cell 连上
  • 检查 将要更新的 SPV Cell 的 index 为 $t+1$

总结下,每次更新的时候需要检查 Input,CellDep 和 Output 的 index :

  • $i_{\mathrm{Output}} = i_{\mathrm{Input}}$
  • $i_{\mathrm{Output}} \equiv i_{\mathrm{CellDep}} + 1 \pmod{N}$
  • $i \in {0, 1, \dots, N-1}$

Users 使用

用户如果要验证一笔高度在 $h$ 的 TX ,那么选择任何包含这个高度的 SPV Cell 都可以。

但建议选择 Index Cell 里记录的 Latest SPV Cell ,因为这个 Cell 的下一次更新时刻,距离当前时间最长。

这样可以 "3. 避免读写竞争" 。


Reorg 操作

$C_{i}$ 来表示 max height 为 $H_{min} + a_{0} + a_{1} + \cdots + a_{i-1} + a_{i}$ 的 SPV Cell 。

假设目前要从 $C_{r}$ 处进行 reorg (即 $C_{r}$ 是合法的,之后的全要 revert ),那么:

  • CellDep 包含:
    • $C_{r}$ 的 SPV Cell
  • Inputs 包含:
    • $C_{r+1}$ 的 SPV Cell
    • $C_{r+2}$ 的 SPV Cell
    • $\cdots$
    • $C_{N-1}$ 的 SPV Cell
    • 指向 $C_{N-1}$ 的 Index Cell
  • Outputs 包含:
    • $C_{r+1}$ 的 SPV Cell 更新 Cell Data 为最新 tip 对应的数据
    • $C_{r+2}$$C_{N-1}$ 的 SPV Cells 清空数据,等待后面 turns 再写入新数据
    • Index Cell 修改为 指向 $C_{r+1}$
  • Witnesses 包含:
    • $C_{r}$ 开始的,到要 reorg 到的最新 tip 之间的所有的 headers 。

验证逻辑:

  • 检查 Index Cell 指向的是 $C_{N-1}$
  • 检查 Witnesses 包含的 tip headers 是连续的,且验证 POW
  • 检查 Witnesses 包含的 tip headers 可以和 $C_{r}$ 连上
  • 检查 Witnesses 包含的 tip headers 比当前 $C_{N-1}$ 拥有 better total diff 。

Revert 操作

如果 Reorg 操作受到 CKB Block Size Limit 或 Cycles Limit 影响无法做到,那么只能先强行进行 Revert 操作,然后重新同步。

考虑到单纯的 revert 意味没有验证 better total diff ,所以这个操作应该是需要 Owenrship 的。

我理解这个操作不可以有,因为违背了需求 "2. 所有权和使用权分离。" 。

所以对于 reorg 不了的,无论是

  • 计算或数据 超出 CKB 的 limit ,无法验证;
  • 还是预先 Multi SPV Cells 个数设置太少了, reorg 不到。

我的建议是用户应该另部署一套 SPV Client 。


Usecase: How to verify a TX or TXID in BTC chain?

用户如果需要在一个 script 里校验 TX 或 TXID 在 BTC chain 上(仅限于 SPV Cell 的 min height 和 max height 之间的 TX),则:

  • CellDeps 包含:
    • 包含 有该 TX 的 Block 的 SPV Cell
  • Witnesses 包含:
    • TX data (如果不需要验证 data ,可以直接用 TXID )
    • TX 的 Merkle Proof
    • TX 所在 Header
    • TX 所在 Header 的 MMR Proof

验证逻辑:

  • [Optional] 用 TX data 计算出 TXID 。
  • 用 TX 的 Merkle Proof,TXID 和 Header 里的 merkle root 进行校验:TX 在 Header 里。
  • 用 TX 所在 Header 的 MMR Proof, TX 的 Header 和 SPV Cell 里的 MMR root digest 进行校验:header 在 SPV Cell 里。

References:

SPV Testnet Deployment Information

Contracts

SPV Instances

@yangby-cryptape
Copy link
Author

yangby-cryptape commented Mar 10, 2024

Reply @xcshuan:

然后使用 output_data (里面保存了某次更新后的MMR root)验证 MMR proof

抛开可行性先不谈

先不谈可行性,在于,我们是否推行这么实践。

我觉得你这个想法,甚至可以推广一下,我一个 code 部署上去,就可以销毁了。
通过 load_code 去 load 历史 data 就好了。

还要部署什么 lock 、type 啊,中间转发一次就好了。

一旦这么搞了:

  • 现在没 prune 但以后做 prune 感觉也很麻烦,明明 deleted 的 data 还要留一份;
  • light client 也是;
  • indexer 给 spent cell 做 index 吗(我没用过,不清楚)。

你这个观点应该先在更 General 的层面讨论一下,不绑定具体 功能:能不能利用 load_tx 或 load_block 去读取 dead cell data 。

可以在 Nervos Talk 上讨论下,让大佬们来定设计(游戏规则),我只负责遵循设计(在游戏规则下玩游戏)。

我说我的想法吧:你这个违背了(我理解的) CKB 设计的初衷了,你想存数据还不费 CKBytes ,看着,还能再存 DAO 赚利息。

谈谈可行性

另外,我没试,看 CKB 代码应该不可行:

  • 目前 load_cell_data 应该不能 load dead cell ,resolve 环节就报错了。

  • 目前貌似没有 load_block,单纯 load_header 的话,拿不到 cell data 。

    有个 load_transaction 只能 load 当前 transaction 。

@xcshuan
Copy link

xcshuan commented Mar 10, 2024

你这个违背了(我理解的) CKB 设计的初衷了,你想存数据还不费 CKBytes ,看着,还能再存 DAO 赚利息。

@yangby-cryptape 这个当然不违背 CKB 设计的初衷,在 CKB 脚本里读取链自身的历史,一开始就是 CKB 脚本具有的功能之一,使用这个功能并没有占用状态,也就不存在存数据还不占用CKB的问题。

看 CKB 代码应该不可行

这个方案当然是可行的,因为 cell_data 是由构建交易的链下模块自己检索,然后放在 witness 里的,而不是通过 load_dead_cell 这种目前不存在并且也不应该存在的 syscall。

以BTC的SPV来作为切入点方便理解,在CKB上实现BTC SPV Cell 验证某个BTC交易的存在性,是通过使用 BTC Header 里的 Transaction_root + Merkle Proof 实现的。

由于 CKB 使用和 BTC 类似的设计,那么使用 CKB SPV 为什么不行呢?如果这个方案不能用的话,那 BTC SPV on CKB 也同样不可行了。

由于 load_header 的存在,相当于 CKB 脚本内置了 CKB 自身的SPV节点,那么使用 CKB header 中的 transaction_root 自然可以验证某笔交易的存在性,从而获取在某个区块高度里交易对应的output,其lock,type,data分别是什么,于是脚本就获得了某个历史状态的 SPV Cell 的状态,由于这是在读取 CKB 的历史,所以并不会存在读的冲突,然后这个 SPV Cell 对应的 Live Cell 则持续根据 BTC 的状态持续更新,从而实现了读写分离。

使用这个方案时,历史 BTC SPV Cell 可能包含一些已被重组的BTC Header,但是我已经在之前的评论中对这种情况进行了安全性分析,结论是安全性与多SPV Cell是一样的。

这个设计,并不会对全节点和轻节点造成额外负担,以及影响交易历史的裁剪,因为验证一笔交易的合法性,依然只需要存储以下两项:

  1. 当前的Live Cell集合;
  2. 所有的CKB 区块头。

上面的论述应该已经表述清楚:

  1. 只使用一个 SPV MMR Cell 可以解决读写冲突问题,并且其合约实现上应该是会更简洁,只需要维护和更新一个Cell,无需维护 Multi SPV Cell的链接。
  2. 该设计不需要 CKB 本身新增任何功能,并且不违背 CKB 的设计理念。
  3. 其本质上是一种,使用 Witnesses 的空间,从而节省链上状态占用的tradeoff,正如在BTC某些应用的设计中,使用 Witnesses 会比交易的其他部分要便宜一样。

@yangby-cryptape
Copy link
Author

Reply @xcshuan:

我这次应该是真的完全理解你的意思了 😅 :就是 Cell Data 放 Witness 里。


理论上可以的,但 Witness 里至少要放:

  • 一个完整 CKB raw transaction (算 tx hash,用来保证 cell data )
    table RawTransaction {
        version:        Uint32,
        cell_deps:      CellDepVec,
        header_deps:    Byte32Vec,
        inputs:         CellInputVec,
        outputs:        CellOutputVec,
        outputs_data:   BytesVec,
    }
    
  • CKB Transaction Merkle Proof (和 tx hash 一起,用来和 header 里的 transaction root 做校验)
  • 以及原本的 BTC 相关的 Proof

这里我不清楚这样会不会导致更容易触发什么 limit :

  • Witnesses 是算 tx size 的。
  • Load witnesses 到 CKB-VM 是按照大小算 cycles 。
  • 算 Hash 的函数也是数据越大越费 cycles 的。

由于 CKB 使用和 BTC 类似的设计,那么使用 CKB SPV 为什么不行呢?

那边 Header 走额外提交的 我的想法也是为了节省:

  • 可以预计的,并非所有 BTC headers 都是要用到的,而且就算用到,一次才 80 bytes ;
  • 避免了滚动更新数据(header append 到 cell data)。
  • 再者, BTC 的 TxOut Proof 的格式上,本身就包含了 Header 。
    综上,那边设计上,提交的数据可以理解为:就是随用随提交,不和以往 数据 重合,所以没有冗余性。

我直觉感觉:你这个方案,成本高,贵!

  • 每个 tx 提交, witness 里还要再多一个 tx (而且本身还是 chain 上存在过的 tx )。

而且大部分数据还是无用的:

  • 只提交 Cell Data 证明不了 Tx Hash 的;
  • 你这个要多好多其他 Raw Tx 结构上的数据,比如就算 1 in 1 out ,就都有 lock script 和 type script。

然后放在 witness 里的,...,如果这个方案不能用的话,那 BTC SPV on CKB 也同样不可行了。

在 witness 里放 Proof 不是必须的,SPV 就提供函数而已,Proof 想放哪里随便,只要能调用到函数;我没试过,但我也想过会不会触发什么 limit 导致 witness 不够用,实在不行就放一个 Proof Cell 。

你这个方案,先放个 Proof Cell 我更嫌贵~~ (:woozy_face: 大概我小气惯了,哈哈~~)

@xcshuan
Copy link

xcshuan commented Mar 11, 2024

你这个方案,成本高,贵!
@yangby-cryptape 相比之前确实多占了一点 Witnesses 的空间,但是Witnesses的使用成本比 Cell Data便宜得多。可以进行简单的成本核算。

一个 Header 的 CellData 大致需要,80Bytes+lock(假定53Bytes)+type(假定53Bytes)+4Bytes=190Bytes,事实上不可能只存80Bytes,最终可能会占用到200Bytes。

而假定用Witnesses方案,假定SPV Cell交易都是 2 in 2 out的。

  • 两个 Outpoint+Since,其中一个付手续费,就是 74Bytes,两个output 加 cell_data,假定为 300 Bytes,2个Cell_deps,66Bytes,由此可以假定交易总占用500字节。
  • 由于CKB一个区块最多1000笔交易左右,树高度为11,则 Proof 约为12*32Bytes=384Bytes。

所以相比使用Cell存Header,每笔调用SPV Cell的交易,最终在Witnesses部分多出来的大小小于1KB,按2000shannons/KB的FeeRate,190Bytes的链上状态占用成本,够覆盖多出来的CKB花费成本执行 950 万次,考虑到一个BTC 区块最多四五千笔交易,这个方案的成本不可能更贵,反而便宜得多。

至于 Cycle 的问题,1KB的额外数据加一个哈希计算,可能顶多花100w Cycle吧,而Lockscript验证一个签名就几百万Cycle了,但是这还是远小于 Cycle上限。

并且这个方案是把额外成本分摊给了使用SPV Cell的用户,从经济模型上更合理,不然每次都创建新Cell,到后面谁来出资,过期的SPV Cell谁有权力回收?这就变成公地问题了。

@yangby-cryptape
Copy link
Author

yangby-cryptape commented Mar 11, 2024

@xcshuan

  • 现在的 Multi Cell 方案也暂时不需要在 Cell Data 里放 Headers 。

    我说的也可以把数据放 Cell Data 里,是一个通用讨论,无论什么方案, Witnesses 如果不够用都可以走 Cell Data 。
    强调下,目前的设计 Multi Cell 设计下,SPV 只提供 API 和一个 Cell :通过 Cell Dep 引用 Cell Data,然后调用 API , Proof 想放哪儿都可以。

    总之,用于 Prove ,用户需要的是:

    • Header MMR Proof
    • TxOutProof (Header 在里面了,不需要额外提供)
    • 如果用户需要相信 BTC Tx 里的数据,肯定还要完整 BTC Tx 来算 Hash 的。
  • 你的方案下,

    用户需要,除了上面的 Proof 用的,还需要:

    • 一个完整的 CKB Raw Tx (就是 Tx without witnesses)
    • CKB Tx Proof

    按照你说的:

    由此可以假定交易总占用500字节。

    不包含 Type Script ,没有 Cell Data ,总之,最简化的一个 2-in-2-out 的 secp256k1-blake160 交易的 size 是 597 (含了 witnesses )

    去掉 witnesses 也还有 560 ,假设 Client Data 本身还要 100 bytes ,就是 660 了 ,再加一个 type ,算 700 好了。

    假设引用它的 tx 也是一个 2-in-2-out 的,那么不考虑用户业务占用的 witnesses ,就已经是一个大约 1300 bytes 的 Transaction (含了 witnesses , 其中 witnesses 算 700 ,比本身 tx 还大)。

    一个怂人听闻的说法可以这么说:你这个设计使得 交易 尺寸 翻倍,使得 链 性能减半了。

  • 用户随着自己的设计,Witnesses 里大概还要放自己的业务相关数据。

    上面的 witnesses 算 700 还没考虑用户自己的数据呢。

  • Multi Cells 方案里,需要用户提供的数据,都是 CKB 确实没有的数据;你的方案的数据,对于 Chain 来说就是冗余数据。

    而且以上 Proof 都是用一次,就要提交一次的(除非使用 Cell Data 先存 Chain 上)。

    现在 mainnet 是 40Gib 的 DB, testnet 已经 128 GiB 。

    不是和 BTC 比价格,也是资源浪费。

  • 你的经济模型问题,我就不能理解了,现在是 N 个 SPV Cells 循环的模式,怎么会有公地问题?

    假设用户的 各种 Proof 合起来过大了,在 Witnesses 里提交不了,放一个 Cell Data 提交 Proof,验证完 BTC Tx 自己回收掉就好了。


Summary

我觉得我和你的分歧,类比一下,就是,我相对更认同 Luke Dashjr ,我觉得这样利用 Witnesses 塞 冗余数据 ,是不好的。

同时我还觉得你的方案,点儿当年 ETH 的 io 指令 price 设置低了,被钻空子了的感觉,感觉 CKB 目前对 witness 太宽松了。


Update:

  • 我的想法是:看了你的设计,我觉得应该提高 witness 的成本。

  • 于是,我在 CKB Core 里问了下,有人说,“这个模式已经泛滥了,我记得很久之前提过,说是不处理,不知道现在有没有态度上的变化” ;有待进一步讨论。

@xcshuan
Copy link

xcshuan commented Mar 11, 2024

@yangby-cryptape

去掉 witnesses 也还有 560

input * 2 = (32(tx_hash) + 4(index) + 8(since)) * 2 = 44, output * 2 = lock (32 + 1 + 20) + capacity(4) + lock (32 + 1 + 20) + capacity(4) + type(32+1+32) + output_data(100) = 279, cell_deps * 2 = 33 * 2 = 66, version = 4.

total = 393.

现在是 N 个 SPV Cells 循环的模式

如果是MMR Cell进行循环队列的模式,那我觉得是OK的。

看了你的设计,我觉得应该提高 witness 的成本

我相对更认同 Luke Dashjr ,我觉得这样利用 Witnesses 塞 冗余数据 ,是不好的。

在整个CKB交易中,Witness, output_data 以及script args 是用户可以自由写入的区域,如果攻击者想要恶意占用网络带宽和大幅度增大历史存储,在这三项里写,攻击者付出的成本是相差无几的。因为即便 args 和 output_data 需要占用CKB,也因可随时解锁无限复用失去约束效果,所以不存在提高 Witness 成本的问题,如果要提高攻击成本,就应该抬高整个 1000 Shannon/KB 的 基础 feeRate,而不只是Witnesses的定价。

身份不明的攻击者正尝试对 Zcash 网络进行垃圾交易攻击,相比 Zcash,至少 CKB 拥有动态的费率调整,以及根据交易大小定价的机制。但CKB目前经济模型过度依赖于状态占用,而将 FeeRate 设置为一个极低的值,可能也不是一个合理的设计,其对于网络带宽,历史存储,全节点同步速度都有影响。

在进行历史裁剪时,由于隔离见证的设计,所有的Witness数据可以首先被裁剪,并且影响最小,从这个角度考虑,Witnesses 的 定价理应比 outputs_data 的 feeRate 便宜一些。

@yangby-cryptape
Copy link
Author

input * 2 = (32(tx_hash) + 4(index) + 8(since)) * 2 = 44, output * 2 = lock (32 + 1 + 20) + capacity(4) + lock (32 + 1 + 20) + capacity(4) + type(32+1+32) + output_data(100) = 279, cell_deps * 2 = 33 * 2 = 66, version = 4.

不是你这么算的,还有结构上的部分,比如记录 input len ,记录 output len 等。
我算得是,我是写代码跑了一个出来的。

use ckb_types::{core, packed, prelude::*};

fn main() {
    let lock = packed::Script::new_builder().args([0u8; 20].pack()).build();
    let in1 = packed::CellInput::new_builder().build();
    let in2 = in1.clone();
    let cd1 = packed::CellDep::new_builder().build();
    let cd2 = cd1.clone();
    let cd3 = cd1.clone();
    let out1 = packed::CellOutput::new_builder().lock(lock.clone()).build();
    let out1 = packed::CellOutput::new_builder().lock(lock.clone()).build();
    let out2 = packed::CellOutput::new_builder()
        .lock(lock.clone())
        .type_(Some(lock).pack())
        .build();
    let empty: Vec<u8> = vec![];
    let raw = packed::RawTransaction::new_builder()
        .cell_deps(vec![cd1, cd2, cd3].pack())
        .inputs(vec![in1, in2].pack())
        .outputs(vec![out1, out2].pack())
        .outputs_data(vec![empty.pack(), [0u8; 1].pack()].pack())
        .build();
    let tx = packed::Transaction::new_builder().raw(raw).build();
    let sz = tx.serialized_size_in_block();
    println!("Size {sz}");
}

@yangby-cryptape
Copy link
Author

在这个项目之前,我还没写过最终 生产 部署的 合约项目,在 ckb-core 写合约多,但大部分都是写 tests 。

这个设计模式我确实觉得不是很认同。
但讨论后,貌似现在普遍都是这么做的,那我也不好说什么了。

按照当前 10s 才 1 个 Block , Block limit 是 597×1000 ,一年极限才 4 GiB 原始数据(不算存下来实际磁盘会放大的部分,比如 索引 之类)。


但我还是觉得这个方案是在制造不必要的冗余数据。

@xcshuan
Copy link

xcshuan commented Mar 11, 2024

反正要限制,只限制Witness定价肯定是不够的。

一年极限才 4 GiB 原始数据

@yangby-cryptape 这是一天的极限数据吧。。

做一个简单的运算,一个block最大597*1000 Bytes= 583 KB,按照 1000 feeRate来计算,假设出块时间 12s,则一天出块个数为 86400/12 = 7200,一年出块个数为 2628000,总大小为 2628000 * 583 KB = 1461 GB,那么攻击者需要的成本是多少呢?
攻击成本 = 2628000 * 583 * 1000 * 10^-8 = 15321.16 CKB,可以说,即便CKB涨到 10 美金,这个成本也算不上多高,所以目前的 feeRate 设置是极不合理的,之前就是没人用,如果有人想要恶意攻击的,完全可以在协议允许的情况下攻击。
如果将最低 feeRate 提高 100 倍,一笔普通转账交易的手续费从 0.00001 变成 0.001,对普通用户应该体感相差不大。

@matt-nervos
Copy link

matt-nervos commented Mar 12, 2024

regarding spam through witness data- Signature verification is the heaviest part of syncing a UTXO chain. In the case of recent zcash and monero spam attacks, though the transaction fee is priced in bytes, the verification burden is calculated in cycles. Downloading data is much faster than verifying signatures.

though CKB fees are calculated based on bytes, there is a limit to the number of cycles per block. I hope the market can find some equilibrium that discourages spam (because those spam transactions will reduce the # of cycles available to other transactions). Overall, an important distinction is that CKB does limit the verification burden explicitly, while other UTXO chains do not.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment