比特币的双花攻击问题解决

2020-01-18 14:33:05 +08:00
 blueberryman

双花攻击肯定是比特币很大的一个问题。utxo 中怎么证明这笔钱属于我,就是通过输入脚本和前一个的输出脚本匹配,如果返回 true 就能说明这笔钱属于我。不管是 p2pk 还是 p2pkh 都没有标记这笔交易是否已经被花过了,那怎么解决的双花呢?

900 次点击
所在节点    Bitcoin
29 条回复
blueberryman
2020-01-18 15:19:18 +08:00
我又有了新的进展,原来是会被标记为已用,然而是在哪个字段中标记为已用的呢?也就是说每添加一个新的区块就要修改之前区块的信息?那 merkle 树不就乱套了????
memorybox
2020-01-23 08:13:19 +08:00
1. 写入区块链的交易才被承认,双花交易只存在于内存池中,所有的双花交易只能有一笔进入区块链
2. 更改已经进入区块链的交易,只有发动 50%攻击
3. 消费 coinbase 交易需要 100 block 的成熟期,现在不少裁剪节点是以 prune 方式运行的,一般设定 prune=4096,所以说,理论上区块链重组是有可能的,但是 100 个 block,4000 个 block 级别就变成近乎不可能的事情,一般情况下,6 个 block 确认就基本上确保一切; 历史上曾发生过最多 31 个 block 的重组事件,是在 2013 年 3 月份发生的,现在几乎不可能再有这种情况发生了;

我比较仔细的研究过这些情况,写过一篇科普文章,有兴趣可以翻阅下:

https://happy123.me/blog/2019/01/21/bi-te-bi-de-blockchain-1/
acess
2020-01-26 19:36:24 +08:00
@memorybox
我想杠一下。

不足 50%的算力也有一定概率能让攻击链追上原链,然后就成功覆盖了原链。50%以上算力,只要坚持足够久,是 100%概率成功,所以才叫 51%攻击。
http [V 站] s://bitcoin. [真烦人] org/en/bitcoin-core/features/validation 下面的 chain rewrite,还给了一张图表,横轴算力占比,纵轴等效 BTC 金额。

所以说,虽然区块链和挖矿就是用来对付双花的,但是这也只能是“假共识”,每时每刻都不能完全保证是不是有人偷偷藏了一条攻击链暂时没放出来,一旦放出来,就有一段历史要被改写。

另外,51%攻击也不止能双花,还可以 DoS,也就是拒绝正常打包交易。

总之,51%攻击也可以被视作一种恶意的软分叉(在原规则的基础上新加一条恶意的规则)。
acess
2020-01-26 19:53:00 +08:00
@blueberryman 你应该这样理解:比特币区块链上只有“历史转账记录”,没有“最终余额状态”;也就是说只有“过程”,没有“结果”。“最终余额状态”,也就是 UTXO 集合,这个是每一个全节点根据区块链(也就是历史交易记录)自己推算出来的。
历史记录当然是没有必要去改动的。

我感觉中本聪本来想把“交易记录”和“最终余额”合为一体的,也就是“交易”和“币”一体两面。所以他才会在白皮书里写“利用 Merkle 树剪枝来回收磁盘空间”
但实际上,稍加思考,就会这个想法不靠谱——Merkle 树只能证明一笔交易确实在链上,无法证明一个币是不是被花掉了,所以,恶意节点(不需要挖矿算力)完全可以把已经花掉的币重新加回来,或者把本来没花掉的币“修剪”掉。

以太坊就有“世界状态”这种设定,也就是把这个“最终余额状态”也算出一个 hash,登记到链上。
比特币呢,很多年前 Pieter Wuille 等开发者就提出了 UTXO commitment,不过这个争议比较大,至今也没有实现、部署。按照一般的搞法,新节点只能是从创世区块开始同步。虽然你直接拷一个同步好的数据目录过来也没人拦得住你,但很显然开发者不鼓励这种行为。
acess
2020-01-26 20:03:01 +08:00
与这个问题相关的另一个概念是“欺诈证明”( fraud proof )。

看到我前面说“无法证明一个币是不是被花掉”,你八成会感到不服气——这怎么就不可能做到了?只要把后来花掉这个币的交易(以及对应的 Merkle 路径)给出来不就证明了么?

这个问题比直觉上复杂一些,但是也不是那么复杂,很多开发者都总结过各种可能的伪造数据方式,然后给出对策。大体上说,这需要对比特币的区块结构稍微增补一些数据,让矿工多登记一些证明数据。

其实,中本聪的白皮书里也有提到,SPV 轻钱包会盲目跟随多数算力,所以可能是需要一种警报机制,让 SPV 可以知道哪条链是违反规则的,不要去跟随这种非法链,这样即使攻击者掌控 51%的算力也无法任意地打破规则。

简单说,“欺诈证明”,就是一段非常简短的数据,任何节点(不需要有算力,甚至未必需要是全节点)都可以生成,而且其他节点收到后可以立即作出判断,如果“欺诈证明”本身没问题,那就一定是它指向的那条链有问题,所以那条链一定是非法的,不能跟随。


曾经,core 开发者认为 segwit 可以更方便地实现这一点,后来他们又否认了这一点,声明 segwit 并不会让欺诈证明更容易实现,而且后来他们还弃坑了。

弃坑的理由也很简单:即便我们可以生成这种简短的“欺诈证明”,也防不住恶意矿工把区块里非法的部分暂时藏匿起来。如果要亲自确证一条区块链是不是有被藏匿起来的部分,那只能是像全节点那样从头完整下载一遍。
acess
2020-01-26 20:12:25 +08:00
为什么说 UTXO commitment 存在争议呢?如果把最近时间点的 UTXO 集合算一个 hash,然后登记到链上,那不就可以跳过历史区块,直接从最近的时间点开始同步了么?而且检验 hash 就可以防止下载到假数据不是么?

争议点在于:这个“UTXO 集合的 hash”不具有“自证清白”的特性。
对于整条区块链数据来说,它是具有“自证清白”的特性的,因为每一个币是不是在比特币规则约束的范围内挖出来的,全节点都可以自己验证。
但是,你在链上看到“UTXO 集合的 hash”,怎么可以知道这个 hash 是不是恶意矿工伪造的呢?你只能是先验证过之前的交易数据,才能知道这个 UTXO 集合数据(以及它的 hash )对不对。

所以,就有开发者认为:如果大家都习惯了用 UTXO commitment 跳过历史区块,那比特币就丢失了“51%的算力也无法任意打破规则”这个良好的特性,变成了任由掌握了多数算力的矿工宰割的体系,这甚至可以说是丢失了去中心化。

大区块党一般都不认同这种观点,他们会强调“让矿工统治整个系统,这是中本聪本来的设计”……
acess
2020-01-26 20:15:02 +08:00
这里也可以看出“历史区块不可避免地会越攒越大”是一个问题。我记得 Meni Rosenfeld 等很多人都认为这个问题可以用零知识证明来解决,不过我也不清楚具体是怎么解决的。我只知道 MimbleWimble 协议是安全地实现了裁剪。
acess
2020-01-27 00:37:00 +08:00
@memorybox @memorybox 我还是逐条杠一下吧。

1. 写入区块链的交易才被承认,双花交易只存在于内存池中,所有的双花交易只能有一笔进入区块链

“内存池”是每一个节点自己维护的,它存放的是待打包的交易。每个节点都有自己的内存池,并不存在一个全网统一的“内存池”概念。
你愿意打包什么数据进区块,完全是你的自由,谁也管不着。你愿意的话,打包进去一笔从 0.01 个币凭空变出 1 亿个币的非法交易都不是不可以。
如果有人尝试双花,那就会产生 N 笔互相抵触的交易(因为这些交易都花掉了同一个币)。
但是,**正常的节点不会允许自己的内存池里出现多笔互相抵触的交易**,只可能保留其中的一笔。
说完了内存池,那区块链呢?
只要有算力,任何人都可以完全可以去挖一条非法链来同时把这 N 笔互相抵触的交易都给打包进去,这样其实凭空造出了币。
如果你不愿意挖这种非法链,那你也可以去挖出多条分叉链,每一条分叉链本身都只打包这 N 笔交易中的一笔,每一条分叉链都完全符合规则。
不过,**正常的节点都是先独立地从头验证一条链是否合法**,中间但凡有发现任何违反规则的数据,都会将其标记为非法,**拒收**这条分叉链自此以后的所有区块;
**如果正常的节点看到了多条合法链,则会跟随其中最长的那条链(严格来说是积累工作量最大,而不是最长)**。

但凡是理性的矿工,也就是脑子里只想着赚钱的矿工,他只要考虑到“其他矿工也会按照规则验证我挖出的区块,非法区块会被拒收”,就不会把非法的交易打包进去;
他只要考虑到“最长链规则”,就只会在最长链的末端进行挖矿,把这条最长链延长;
无论是乱七八糟的分叉链,还是虽然长但是包含非法内容的链,理性的矿工都不会去跟随,因为跟随了,就是浪费自己的算力,让矿机白白烧掉电费而拿不到奖励。

可以看出来,每个节点都只是遵照一个规则来独立进行判断,而不是交给某一个“权威服务器”来进行处理和判断。所以才说,比特币是去中心化的。

2. 更改已经进入区块链的交易,只有发动 50%攻击

51%攻击,这个我在 3 楼说过了。
至于“更改已经进入区块链的交易”,我也在上面几楼说了一下比特币社区的分歧:
目前占主流的一派认为“比特币区块链具有无需信任(可以自证清白)的能力,即使是 50%以上的算力也仍然不能主宰比特币系统,为了达到这个目的,只能劳烦用户去跑笨重的全节点软件,别无他法——这也是我们不应该随便扩大区块容量的众多理由之一”;
相对少数的“大区块党”就不认同这一点,他们认为“按照中本聪的很多发言,矿工本来就主宰着比特币系统,所以区块容量和全节点之类的东西,让矿工们去管理就可以了,一般用户不需要操心去掺和;至于什么‘欺诈证明’都是很边缘的问题,不能拿来作为阻碍扩大区块的借口”。

3. 消费 coinbase 交易需要 100 block 的成熟期,现在不少裁剪节点是以 prune 方式运行的,一般设定 prune=4096,所以说,理论上区块链重组是有可能的,但是 100 个 block,4000 个 block 级别就变成近乎不可能的事情,一般情况下,6 个 block 确认就基本上确保一切; 历史上曾发生过最多 31 个 block 的重组事件,是在 2013 年 3 月份发生的,现在几乎不可能再有这种情况发生了;

coinbase 成熟度和区块修剪,这两个都是发生链重组时(也就是“回滚”,放弃一条分叉链,改为跟随另一条分叉链),可能带来连带损害的地方。就是为了防止出现连带损害,才要设置比较大、比较保守的限制。

coinbase 交易,就是矿工挖出新币+手续费奖励的特殊交易。如果过早允许矿工花掉这种“新挖出的币”,那很显然这些币还可以被接手的人再次花出去,这样就会产生一连串交易。如果发生了链重组,那源头的 coinbase 交易不能放到另一条链上,所以它后面的一大串交易也都会随之被判为非法、被丢弃掉,这很显然很糟糕,所以就需要尽量避免这种情况,就是为了这个才加了 100 个区块的确认的 coinbase 成熟度限制。

不过要注意,这个 100 区块确认的限制是写在全节点软件代码里的共识规则,谁都不能打破,否则就会被拒收。平时说的 6 确认就不是这样,6 确认只是一种典型的参考值,实际上在 0 确认的时候你就已经可以把收到的币发出去。一般说“请等待至少 6 个确认”,或者更多个确认,这个是**收款方为了保护自己而自愿选择去等**。对于交易所充值来说,也是如此,交易所也要保护自己,防止恶意用户利用双重支付来变相实现偷币。

区块修剪,这个很显然也是因为删掉了老区块数据就无法回滚到这个时间点之前,导致整个全节点软件都不能正常运作,所以目前就是至少也得保留 550MiB 的历史区块。
memorybox
2020-01-27 07:54:14 +08:00
@acess 感谢科普;

前几年我也花了一段时间认真学习比特币的原理知识,共用了 pyspv 和 pycoind 的实现,写了一个简单的 Segwit 分叉之前的比特币全节点;

https://github.com/brain-zhang/chainhorn

实现了 PROTOCOL_VERSION(60002)最基本的交易接收,广播功能;

之后也没什么人有兴趣关注就没有再继续下去,您有兴趣来参与一下吗?
acess
2020-01-27 12:04:53 +08:00
@memorybox 科普算不上,只是心血来潮就打了很多字,把自己的理解尽量说出来,看看是不是有偏差。

维护代码,这个对我来说是个尴尬的问题,因为我并不算是开发者……


还有,我 4 楼提到 Merkle 树不能直接实现裁剪,和我 5 楼提到的欺诈证明,很显然不是一码事,结果好像有点被我混为一谈了。

在 Merkle 树的“剪枝”上做手脚,把已经被花掉的币剪掉,或者把没花掉的币加回去,这其实压根就没有修改原先区块的结构和内容,只是在呈现上做了手脚。如果有新的全节点要同步,那这种手段已经足够欺骗新的全节点了,这不需要任何挖矿算力。

欺诈证明,这个应该是对付已经写到链上的非法数据的。欺诈证明是“无罪推定”,首先假设一条链是合法的,给出有效证据才判为非法。
按照我的理解,如果只是在 Merkle 树的剪枝上做手脚,并没有修改链上的数据,所以还不算是欺诈证明覆盖的范围。只有恶意矿工开始在自己挖出的区块上花掉“已经被花掉的币”或是“从来都没存在过的币”(这两种其实都等于在凭空造币),才算是欺诈证明负责的范围。
memorybox
2020-01-27 12:36:00 +08:00
有些地方我不是很理解;

1. 我仔细阅读了您提到的裁剪 Merkle 树对一些 SPV 节点"欺诈"的过程,其实还是没有搞明白:

Merkle 树的任何裁剪都会影响 Merkle Root,而 Merkle Root 的改变会影响 Coinbase 交易,如果要裁剪 Merkle,那么 Coinbase 交易,以及工作量证明都需要重新计算,即使是不考虑其他全节点的广播,我作为一个 SPV 节点,即使只收到了一笔有意义的最近的 block,那么就肯定得出了当前难度值的下限,那么此时我收到了许多"欺诈节点"发来的 block,即使这些 block 中的交易构造是一个裁剪过的 Merkele 树以及合法难度的 Coinbase 交易,不都是要花费相当大的算力的吗?为什么不需要有算力呢?

除非这个 SPV 节点从头到尾都沉浸在"欺诈"的全节点的包围中,但这就是私有链了;而且现在所有开源的 SPV 钱包实现,其实发行版都包含了几个 checkpoint 之前的合法的 block header 集合,接收到全节点的广播后,一般钱包会再就 SPV 同自带的本地的 block header 相比较,所以工程实现上基本上没有问题。


2. 中本聪原论文中的算力攻击计算其实省略了一部分,分叉攻击者有两种情况:

* 当两条分叉从同一起点开始竞争时,就是一个酒鬼漫步问题;攻击者一方相当于不断的要逼近诚实者一方挖出的区块高度;这时候其实只需要 50%的算力即可完成攻击;

* 从交易被收录进区块的时候开始,诚实矿工出了 z 个块。攻击矿工在此期间出块数记为 k,只要攻击者不广播别人就不知道,k 可能等于 0、1、2……直到无穷大。此时的攻击成功概率是中本聪论文中计算的结果;

关于这个问题,我也写过一篇科普文:

https://happy123.me/blog/2018/11/17/bchfen-cha-cheng-dan-de-feng-xian-51-percent-gong-ji-zhe-gai-lu-wen-ti/

严格说来,51%攻击其实是个 50%攻击问题,当然这也是吹毛求疵了。
memorybox
2020-01-27 12:57:45 +08:00
再重新说明一下第一个疑问:

Merkle 树的任何修改都会影响 Merkle Root,而 Merkle Root 的改变会影响 block header,此时要保证 block header 的合法性,就需要重新计算 coinbase 交易,这个过程为什么不需要算力呢?

一个轻节点收到一条 SPV 证明,验证逻辑是:

1. 验证 Merkle 树的合法性
2. 通过 Merkle Root 验证其所在 block header 的合法性;
3. 轻节点通过其自带的 check point HASH 值,以及接收到的其他全节点广播的最近的 block header 验证此 block header 合法性

不论怎样,要发送一个修改的 Merkle 树作为 SPV 证明欺骗轻节点,前提是需要伪造一个合法的 block header,这同样需要极大的算力才能做到啊?
memorybox
2020-01-27 13:03:51 +08:00
总结一下,就是现在几乎所有的全节点或轻节点实现,都自带有几个 bitcoin 历史上著名的 checkpoint HASH 值;

想要欺骗这些节点,代价是巨大的,因为几乎要一己之力计算整条包含这几个 checkpoint HASH 值的链;
acess
2020-01-27 15:00:25 +08:00
@memorybox #11
Merkle 树的裁剪是把内容删掉,只留一个 hash。可以只摘掉一个叶子(也就是交易),也可以摘掉一个分支。这样当然不会影响 Merkle root。这是个 feature,不是 bug。
想想全节点发给 SPV 轻钱包的 Merkle proof,不就是把其他分支都摘掉了,只剩下直通这个叶子节点的一个分支么。
acess
2020-01-27 15:02:03 +08:00
@memorybox 换一个角度来说,其实原来的 Merkle 树还是那个样子,一点没变,“裁剪”只不过是从中挑选一部分分支而已。
acess
2020-01-27 15:07:36 +08:00
@memorybox checkpoint,这个是开发者人为指定的,所以很显然是中心化的。
Bitcoin Core 的 checkpoint 基本上算是被弃用了,上一个检查点还是 2014 年的。
不过,checkpoint 有关的代码并不是完全没用了,一是可以对付低难度垃圾区块头 DoS 攻击,二是用来加速同步的 assumevalid,开发者说过,它和 checkpoint 共享同一套代码。
assumevalid 是指定一个区块 hash,在此之前的脚本(以及数字签名)验证全部都认定为有效,跳过检查验证。这大概就是为什么 Bitcoin Core 全节点在从头同步的时候,大部分时间都只让一个 CPU 核心满载,只有同步到最近的区块时,CPU 才开始满载。
虽然 assumevalid 也是开发者人为指定的,但是它并没有 checkpoint 那种“禁止回滚”的特性,assumevalid 是允许 51%攻击回滚的。而且,用户可以改配置参数来关掉这个功能。
acess
2020-01-27 15:16:17 +08:00
@memorybox #11 你还提到了“沉浸”在恶意节点中——据我所知,“日蚀攻击”( eclipse attack )就符合你说的这种情况。这一般只是被视为比特币协议的一个弱点(貌似还算是根本性的弱点),和是不是私有链 /中心化无关。

如果你还对我说的“Merkle 树裁剪不可行”有疑惑,那我再说一下:
按照通常的逻辑,“交易历史记录”和“最终余额”,这两个东西,是迥然不同的吧。
但是,中本聪的白皮书里,把“交易”直接定义成了“币”,然后又说“可以利用交易被编织成 Merkle 树这个特点来进行裁剪、回收硬盘空间”。按我的理解,他就是想“交易历史记录”和“最终余额”合为一体。但稍微想一想,就会发现这里有问题。
acess
2020-01-27 15:35:55 +08:00
@memorybox #12
再逐条回复一下:

“1. 验证 Merkle 树的合法性”

SPV 并不需要验证整棵 Merkle 树。

“2. 通过 Merkle Root 验证其所在 block header 的合法性”

反了,先验证 block header 是否合法,然后才能用这个 block header 里的 Merkle root 验证 Merkle proof,再用 Merkle proof 验证一笔交易是否进链、(再结合后面接了几个 block header 即可验证)有了几个确认。

“3. 轻节点通过其自带的 check point HASH 值,以及接收到的其他全节点广播的最近的 block header 验证此 block header 合法性”

理论上,checkpoint 并不是必要的。区块链最大的特色就是能“trustless”(无需信任),或者说,能“自证清白”。一个区块头里的各种信息,无论是前一个区块的 hash,还是是否满足挖矿难度,再有就是时间戳是否符合规则,都是可以独立完成验证的,一个节点或用户不需要询问任何人,自己就可以得出结论。
但是,你还是得能联系得上至少一个诚实的节点,如果你周围所有的节点都是恶意的,也就是日蚀攻击这种情况,那你就面临被蒙蔽 /欺骗 /攻击的风险。
acess
2020-01-27 15:40:30 +08:00
币圈外批评“trustless”的角度,大概有这么几个:
1.链上信息如果涉及现实世界,那就无法保证真伪。
2.软件出 bug 几乎无法避免,更不用说可能被插入后门。
3.说到后门的话,从操作系统到 CPU,到编译器,再到各种加密算法,甚至是币圈软件自身的“开源代码”本身,都无法保证绝对没有后门,我们都是信任着这些东西。

币圈内,大区块党,批评“trustless”,貌似就不这么说了,他们只是会强调“中本聪本来就是让矿工掌控比特币的,用户本来就是要信任矿工不作恶的”。
memorybox
2020-01-27 15:47:12 +08:00
如您所说,对 Merkle Tree 进行裁剪,把本来没花掉的币“修剪”掉, 这只能自嗨,对于现有的系统运行有什么影响呢?当前系统并没有一种场景供恶意节点利用这一点作恶。

至于"完全可以把已经花掉的币重新加回来", 且不修改 Merkle Tree,这又是怎样实现的呢?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/638949

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX