「区块链入门笔记」3.2 共识算法-最长链机制

比特币网络要求所有节点遵循一个协议(共识),即所有保存到本地的区块链必须是被本地节点验证通过的最长链。

且矿工只有在最长区块链上打造的区块才会获得系统的承认并得到挖矿奖励。

打包区块获得的奖励在该区块上增加 99 个新区块(100 个确认)之后才能使用。这是保证区块链不发生分裂的重要机制。

1. 算力攻击

比特币设计之初是为了实现一个点对点的电子现金系统,而这一系统的难题是如何避免双重支付问题。

共识算法的目的就是降低双重支付的可能性。在中本聪的白皮书里验证整个比特币体系里发生双重支付的概率:

1.1 计算

当一个攻击者生成一条具有替代性的链,并且这条链的延长速度比诚实链的延长速度更快。但也不意味着系统可以任攻击者为所欲为,比如凭空制造币或者拿走从来不属于他的币。

节点不会接受一个无效的交易,而诚实节点永远不会接受包含无效交易的区块。

攻击者唯一能尝试的是:改变一笔自己的交易,并尝试把钱从他最近的花费中拿回来。

诚实链和攻击链之间的竞赛具有二项随机漫步(Binomial Random walk)的特点。成功事件意味着诚实链延长了一个区块,领先加 1,失败事件意味着攻击链延长了一个区块,差距减 1。

攻击者成功填补某一既定差距的概率类似于赌徒破产问题(Gambler’ s Ruin Problem)。假定一个赌徒拥有无限的透支信用,然后开始进行潜在次数为无穷的赌博,以试图填补自己的亏空,那么可以计算他补上亏空的概率,也就是该攻击链赶上诚实链的概率,如下所示:

p=诚实节点制造出下一区块的概率
q=攻击者制造出下一个区块的概率
qz=攻击者最终消弭了z个区块的落后差距

img

假定 p > q,那么攻击成功的概率就随着攻击者要追上的区块数的增长而呈现指数下降。

如果攻击者最开始不能获得突破,那么随着他落后的越多,他成功的机会就会变得无限渺茫。

现在考虑一下,一个新交易的收款人需要等到多长时间,才能足够确信发款人已经不可能改变这笔交易了。假设付款人是一个攻击者,他希望收款人相信他已经付过款了,然后过一段时间将已支付的款项重新发回给自己。付款人希望就算届时收款人会察觉这一点,也于事无补。

对此,收款人生成一个新的密钥对,然后在交易签署前不久将公钥发送给付款人。可以防止付款人预先准备好一个链,然后持续地对此区块进行运算,直到他的链幸运地超越了诚实链,然后立即执行支付。

在此情形下,只要交易一发出,攻击者就开始悄悄地准备一条包含了该交易替代版本的平行链条。

收款人等待交易出现在首个区块中,然后等到 z 个区块连接在其后。此时,他仍不能确切地知道攻击者已经进展了多少个区块,但是假设诚实区块产生一个区块将耗费平均预期时间,那么攻击者的潜在进展就是一个泊松分布,分布的期望为

img

在此情形下,为了计算攻击者追赶上的概率,将攻击者取得进展区块数量的泊松分布的概率密度乘以在该数量下攻击者依然能够追赶上的概率:

img

转换为 C 语言代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include double AttackerSuccessProbability(double q, int z)
{
    double p = 1.0 - q;
    double lambda = z * (q / p);
    double sum = 1.0;
    int i, k;
    for (k = 0; k <= z; k++)
    {
        double poisson = exp(-lambda);
        for (i = 1; i <= k; i++)
            poisson *= lambda / i;
            sum -= poisson * (1 - pow(q / p, z - k));
    }
    return sum;
}

运行程序,可以得到如下的概率结果,发现概率对 z 值呈指数下降。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
当q = 0.1时:
z = 0 p = 1.000 000 0
z = 1 p = 0.204 587 3
z = 2 p = 0.050 977 9
z = 3 p = 0.013 172 2
z = 4 p = 0.003 455 2
z = 5 p = 0.000 913 7
z = 6 p = 0.000 242 8
z = 7 p = 0.000 064 7
z = 8 p = 0.000 017 3
z = 9 p = 0.000 004 6
z = 10 p = 0.000 001 2
当q = 0.3时:
z = 0 p = 1.000 000 0
z = 5 p = 0.177 352 3
z = 10 p = 0.041 660 5
z = 15 p = 0.010 100 8
z = 20 p = 0.002 480 4
z = 25 p = 0.000 613 2
z = 30 p = 0.000 152 2
z = 35 p = 0.000 037 9
z = 40 p = 0.000 009 5
z = 45 p = 0.000 002 4
z = 50 p = 0.000 000 6

求解令 p < 0.1%的 z 值,具体如下。
为使 p < 0.001,则

1
2
3
4
5
6
7
8
q = 0.10 z = 5
q = 0.15 z = 8
q = 0.20 z = 11
q = 0.25 z = 15
q = 0.30 z = 24
q = 0.35 z = 41
q = 0.40 z = 89
q = 0.45 z = 340

计算结果表明,随着区块链里区块确认数增加,发生双重支付的概率就越来越低

只有当攻击者的算力占比比较高的时候才有成功的可能,而这个又可以通过增加确认数来避免。

支付方与接收方调整相应的参数作为交易的条件,比如规定 N 个确认才算交易完成,那么区块链的双花问题在这个体系下变得异常困难。

1.2 51% 算力攻击

攻击者拥有超过整个网络一半算力的情况下,就有能力推翻原有已经确认过的交易,使恶意的双花成为可能,称之为 51%算力攻击

攻击者掌握了全网51%的算力后,发动攻击,则能做到:

  1. 控制自己的交易,一笔发给接收者,另一笔发送给自己,让最终发给自己的交易成功而接收者的失效,欺骗接收者,实现双花成功。

  2. 阻止别人的交易被打包到区块,让交易不能确认。

  3. 阻止别人生成新的区块,获得区块奖励。

不能做的事情如下:

  1. 控制别人发送的交易。
  2. 阻止别人发送交易。
  3. 更改每个区块的奖励数量。
  4. 凭空产生币。
  5. 发送不属于他自己的币。

攻击者实施 51%算力攻击时唯一对自己有利的就是,完成对自己交易的双花,骗取交易接收方的利益。

但攻击者通过攻击来获取利益,需要算力成本,只有当攻击获取的收益大于成本,也大于他诚实工作所获取的收益时,攻击者才会自发动攻击的意图。

攻击者发起攻击要考虑自身利益,出于较高的成本,算力拥有者都会选择诚实的工作。

攻击其实依赖于社区的理性选择。

历史上 Ghash.io 曾经出现过算力接近于 51%的情形,造成了社区恐慌,矿工选择撤离,最终让 Ghash.io 的算力急剧下降。而国内 4 家矿池也曾出现整体算力接近 51%的情形。

2. 共识算法探索

2.1 POW

Proof of Work,使用的哈希算法原理(SHA-256)接近一个暴力破解的过程。于是市场上出现了 ASIC 矿机,是针对比特币的SHA-256 算法研发的,从而使系统总算力不断上升。但算力的快速上涨既降低了挖矿过程的去中心化,又带来了越来越高的能源消耗。

于是有了其他竞争币的共识算法的探索。例如莱特币使用 Scrypt 哈希算法,Darkcoin 使用X11算法,Spreadcoin 使用 SpreadX11。

2.2 POS

###
Proof of Stack(权益证明),不通过竞争性的哈希计算,而是通过节点对所有权的证明来达成共识。有人认为,随着区块奖励减少,POW 会导致「公地悲剧」。

运用 POS 机制的有点点币(PPCoin)。拥有的点点币币龄越高的节点拥有产生新区块的权力。

币龄:
UTXO 所位于区块的高度与当前最长链高度之间的差值决定着该笔 Unspent 币龄的大小,差值越大,代表着币龄越高。该 Unspent 的使用也就代表着币龄的消耗。在 POS 机制里,一笔交易可以消耗的币龄被视为 POS 的一种形式,POS 指的是一种对货币所有权的证明。