区块广播:

“BCH技术升级争论”之Ctor 现状分析

Rawpool.com水手发布在 BCH/比特币现金
 2064  0

近期,Bitcoin Cash社区的开发团队Bitcoin ABC和nChain就11月的BCH升级产生了分歧,大体上分为两派:

  • Bitcoin ABC为代表的一派主推Ctor排序替换Ttor排序,并且引入OPDSV;
  • nChain为代表的一派主张扩大区块上限,并且锁死协议。
对本次“BCH技术升级争论”,Rawpool.com作为Bitcoin Cash社区的一员,秉持“对矿工负责,为社区贡献“的原则,将对Bitcoin ABC和nChain的新版本进行研究分析,并将及时的对外公布中肯的分析报告,以供大家参考。

接下来由来自Rawpool.com的炮哥为大家重点分析下Ctor是不是真的像宣传的那么神奇,性能秒杀Ttor,尤其在大区块的情况下。

技术普及
1. Ttor: Topological Transaction ordering,交易按拓扑排序,什么是拓扑呢?即交易之间的依赖关系网,通常我们说如果一个A交易的输入如果用到了交易B的输出,那显而易见A交易是依赖B交易的,所有还未打包的交易中,他们之间存在着错综复杂的交易依赖关系,在计算机中用专业的数据结构:有向无环图来表示,通俗地讲也就是拓扑图,比如下面这幅图:

图中的A交易叫做祖先交易,BCD都是他的子孙交易,因为BCD的输入都用到了A交易的输出,同时可以看到C也是D的祖先交易,因为D的输入也同时会用到C的输出。这就是一个有向无环图,对他进行排序的话,一个合理的输出可能是ABCD,但是绝对不可能是ABDC,也就是说不能发生子孙在祖先之前出现的情况。

2. Ctor: Canonical Transaction ordering: 交易规范排序,这种排序就比较直观了,直接按照交易的ID来排序,也就是字母表顺序。

技术分析
在Ctor 的仅有的一些论文以及其他技术文献中,几乎都提到了他的性能要好,尤其在大块的情况,这几乎成为了他90%的卖点,其他的优势比如排除了一些攻击方法等,都是附带优势,毕竟之前的实现方法也没有出现安全问题, 那接下来就聊一聊性能是否真的变好,是不是真的有那么大收益。
在这里炮君不会拿出时间复杂度来说事,因为《Canonical Transaction Ordering for Bitcoin》这篇文章中已经对时间复杂度给出了足够清晰的分析,并且结果显而易见是Ctor要好,从事过软件工程或者熟悉计算机算法的工程师都知道,在代码实现层面为了追求更快的计算速度,往往会做很多优化,其中比较常见的一种就是用存储换取时间,比如说字典就是典型的用存储换取时间,把每一个结果都存起来,再次计算的时候就只需要查字典,而不需要重新计算,这种方式的缺点就是存储占用会比较多。
具体到拓扑排序,排序的实体是每一个交易,那么交易在内存中的存储方式就至关重要,直接决定了排序的过程耗时多久可以完成。下面我们来看一下bitcoind是如何实现排序的,以及他的交易是如何存储的,首先定位到区块打包功能相关代码,看到了如下代码:


其中排序功能,只有这一句代码,很简单,调用了std::sort 。这个模板方法的最后一个参数是一个比较操作符,谁排在前面是这个操作符决定的,跟踪到这个函数可以看到:

用到了CtxMemPool::GetCountWithAncestors方法:



此方法只是一个属性读取符,返回了一个成员变量。

简单总结一下,被论述为性能开销很大的Ttor排序,在代码层面只是根据“祖先个数” 这个非常普通的字面常量进行排序,这很容易理解,谁的祖先多,谁就被认为辈分非常低,也就是越要往后排。

而被论述为性能比较好的Ctor排序,又是怎么做的呢?


如图所示,Ctor排序,依然是一样的套路,只不过用的不是“祖先个数”,而是“交易ID”,依然是一个普通字面常量。所以说这两种排序在排序本身上,性能开销是完全一样的,都是基于一个字面常量进行排序,唯一的区别是一个依赖“祖先个数”, 而另一个依赖“交易ID”。

那么至此,问题就转变成了这两个数值的维护工作,究竟谁的成本更高,谁更轻量化?

“交易ID”本身就是一个随机值,没什么工作量,让我们深度看一看“祖先个数”这个值的来龙去脉,这里面涉及2个核心数据结构,一个是mapTx,是真正用来存储交易的字典,字典的Value是CtxMempoolEntry,Key有四个,分别是ID、fee、time和score。

具体声明如下:


接下来便于更好的找到交易的祖先以及子孙,引入了另一个变量:mapLinks

这也是一个字典,Key是交易ID,Value是一个结构体,其中包含了两个成员,parents和children,这两个成员是集合类型,其中存放的是交易的迭代器即0号索引。这样的话,当我们知道一个交易的ID,第一时间就可以把此交易的祖先和子孙全部找出来,可谓非常高效,时间复杂度是O(1)。
那么什么时候用来更新这些信息呢,当然是有新的交易到来,或者有已存在的交易离开内存池的时候:

总结一下:当有交易到来,有交易离去,系统需要非常及时的遍历当前交易的祖先交易、子孙交易,以及进一步更新这些交易的信息的时候,这一套非常优雅的数据结构设计就显得尤为重要, 他非常好的使用存储空间节省了时间开销。

结论
至此大家可以看出,整个的Ttor机制是扎根到了Bitcoind的骨髓里的,从算法到数据结构,并非只是一个排序功能那么简单。
举个例子,打掉一个贪官可能并不难,但是难度在于这个贪官背后的层层关系网,种种后台组织,对这样的大规模违法组织进行清剿,一定是劳民伤财,伤筋动骨的。
而另一个层面,这种排序方法真的是性能老旧,不堪入目么?
炮哥认为倒也未必,良好的算法设计使得这部分代码非常高效,用非常理论的度量方法来套用有向无环图的时间复杂度是没有意义的,重要的是在真实的工程中他的表现是什么样的。
当然,炮哥不否认随着块越来越大,交易越来越多,传统Ttor的内存开销必然会上涨,而且运算时间也会急剧变大。

根据上述分析,炮哥总结出来的结论给大家分享下:


  • 通过对Bitcoin ABC 0.18.0 的研究发现,新版本中同时存在两种排序的代码,也就是说Ttor排序的逻辑并没有被去除掉,所以我们放弃了对这个版本进行性能测试的计划,答案可想而知,额外增加了一次排序绝对比以前要慢的,性能测试没有意义。我们也于第一时间和ABC的工程师进行了沟通,询问其依然保留了老代码的用意,他们给出的答案是:为了兼容分叉前的逻辑,如果现在去除掉老的排序代码,那么现有主链上的块将无法校验,这个回答显然是合理的。
  • 通过跟ABC工程师的讨论,ABC 也认为对这样的数据结构进行大规模整改,是要花费很大力气的,而且这部分代码除了排序,目前依然有别的作用,所以不可能简单去除掉。
  • 敲黑板,重点来了,如果这部分数据结构不做修改,那么单纯讨论Ctor还是Ttor没有任何意义,举个例子,哪个人当总统可能不重要,更重要的是其背后的党派不变,那么社会现状就不会进行大的改变。而ABC也确实坦言近期不会大规模更改代码,所以在一段时间内,Ctor只是听起来更好听罢了。



Rawpool.com简介
Rawpool.com(www.rawpool.com)2018年2月成立于北京,是一家专注于数字货币领域的创新性技术服务公司,是全球领先的比特币数据服务商与矿池解决方案提供商。
Rawpool.com是BCH私有矿池,目前自有算力超500Phash/s。现由私矿转公矿,面向全球用户招募矿工,目前已通过技术手段实现100% 防御DDOS 攻击,支持一键切换BTC/BCH,同时对区块链研究院、矿机、芯片、钱包、交易所等全产业链产品布局,以软硬件结合的方式为用户和合作伙伴提供全球顶级的区块链产品和服务。

官方网站:www.rawpool.com

微信:Rawpool矿池 | 微博:Rawpool矿池

联系邮箱:hi@rawpool.com



本主题由 等一轮残月 于 2018-09-10 17:54:48 审核通过
  • 正序
  • 最新
帖子暂无回复,回帖抢沙发
登录 账号发表你的看法,还没有账号?立即免费 注册
推荐节点 更多
热帖榜 本周最热本月最热