分布式系统中的Gossip协议与比特币中的区块链技术

作者: yangzhe1991 分类: 我是搞技术的 发布时间: 2016-09-01 20:28 ė 6没有评论

在分布式系统中,通过网络通信传递消息来对一些状态达成一致。具体的方式有很多,总体上感觉可以分成三大类,一个是选个master出来,大家在一段时间内都听master的,master提议的大家都听,非master提议的大家都不听,任期到了就通过一种手段重新选举产生master;一个是Paxos,任何人都可以发起提议,通过具体的算法来保证大家一定都能达成一致不会冲突;一种是Gossip,大家每个周期内随机找个其他节点互相同步彼此不知道的状态,从概率上最终一定会收敛成所有节点都拿到最新的状态,只不过节点越多收敛越慢,肯定是最终一致性。今天想讲的主要是第三种,Gossip。

Gossip是最终一致性,集群越大延迟越大。但他自然也有他的好处,其中一个是没有中心节点,不存在一个中心节点挂掉整个系统就跪的问题。当然,在现代的分布式系统中,有很多种办法提高中心节点的可用性,而换来的是系统简单、可以实现强一致性,因此很多系统尤其是数据库相关的分布式存储领域,大都还是使用有中心节点的方案,只有Dynamo和对应的Cassandra等用Gossip,无论数据库本身是否火,但这类架构在最近几年已经很少有新的分布式数据库采用了。虽然Gossip这种P2P不太适合数据库,但其他地方还是可以采用的。除了不需要中心节点外,还有个好处是不需要每个节点之间两两直接互通,只要任何两个节点通过其他节点最终都能传递到,也就是一个强连通的系统,就可以达成一致。这在公网中非常重要,比如两个分别在不同内网的内网节点就是完全无法直接互连的。

历史上最火的P2P协议可能就是BT下载,大家互相从其他节点下载、向其他节点上传,只要有一个节点拥有全部数据,甚至只要整个集群中对应的文件的每一部分都有人有,最终大家都可以有完整的文件。这其实也就是Gossip协议对状态达成一致的过程,只不过从“对若干状态达成一致”变成了“对一个文件的若干区间的内容达成一致”。在一个分布式系统内,有中心节点可以方便很多,一方面是因为一般来说一个系统的所有节点都在一个机房内,是个内网,并且节点数几十几千上万也还是很有限。因此在很多情况下是比P2P好的。但是在广域网中,一个集群的节点数是非常高的,如果都去连一个中心节点,哪怕是连一个有多个节点的中心服务,其需要的机器数、带宽也是非常多的。因此P2P很好的解决了这个问题,每个人提供一点CPU和一点带宽,就可以拿到了完整的文件,并且下载速度很容易超过从某个服务器单线程下载的速度。即使某个节点下线了,照样可以接着下,想删除文件阻止发布是完全不可能的。

而无论是分布式数据库,还是BT下载,其实都依赖一个前提,就是不会有节点捣乱,故意传输错误的数据、故意抛弃一些数据不给你。在分布式系统中用“拜占庭将军问题”来描述这个问题。我们使用的分布式数据库所采用任何达成一致的算法,都是不考虑这个问题的。数据库可能还好,代码都是自己写的、网络都是内网,不存在被攻击的问题(bug啥的不算),任何数据都是可信任的。即使在公网传数据,只需要每个节点能通过一些认证协议证明自己是自己,就没问题了。而P2P下载都是匿名,无法证明自己是自己,并且如果有人故意上传错误的文件,污染整个系统,理论上就可能让绝大多数人拿到错误的内容、达成错误的一致。比如去年出现的天朝码农用迅雷下被中了木马的XCode就是如此。

所以比特币的设计者为了实现无中心节点对各种状态达成一致(每个账户有多少钱、不同账户之间的转账记录),P2P是必须要有的,关键是如何处理拜占庭将军问题。

首先和其他网络协议类似, 公钥和私钥模式的加密可以确保每个人都可以证明自己是自己,公钥可以随意传输不怕丢,私钥不能公开,通过数学运算能保证大家根据加密的结果判断出生成这条数据的人是不是这个公钥所对应的私钥的持有者。而公钥(或对应的哈希)就可以作为这个人的公开id,也就是所谓的钱包地址。

但是这样只解决了“转账记录”的正确性,其他啥都没解决,比如这个账号到底有多少钱。所以需要对“每个账号有多少余额”达成一致性,而这个数据可以通过存储每个账户的初始值和所有历史转账记录来解决(反正转账记录肯定是要存的)。并且需要保证全局使用同一个转账记录的序列,在任何人眼里都是先A给B转了50,然后B给C转了30。这样只要大家能对这个转账记录的序列达成一致,就相当于对全局每个账户的每个状态达成一致了,当然是最终一致性。但是,因为网络的通信是无法确定顺序的,不同的节点收到的转账请求顺序是完全不一样的,那么需要通过一种手段来确定“官方”所接纳的交易记录和顺序是什么样的。可以暂时由某个节点说了算(反正只要选择一些交易记录并确定了顺序以验证交易合法性就好),但不能永远让某个节点说了算(不然这个节点虽然不能伪造别人的交易记录,但可以阻止某些人做交易),也就是在短时间内独裁,但长期内必须民主。如果这在局域网内,每个节点都是两两互通的话,用本文第一段提到的“定期通过某种手段选举master”就行了,但是在广域网中,节点非常多,不可能也没必要两两之间都互通(尤其是还有内网ip的问题),而且因为采用了类似Gossip协议的方式,消息传播给整个集群都是有延迟的,因此需要采用特殊的方式来确保某个时间段内只有一个master。

因此比特币的设计者设计了所谓的“区块链”技术,其核心就是从概率上保证在一段时间内只可能有少量的节点能有资格被大家认作是master。具体的方式是,把过去大家达成一致的历史数据和自己当前准备接受的转账请求序列和一个可以随意改变的数字合并做哈希,其结果必须小于一个大家公认的数。如果我们采用的哈希算法比较复杂,理论上不可逆,那么只能通过枚举那个“可以随意改变的数”来找到一个可行(当然不唯一)的答案。因为枚举的复杂度很高,所以概率上一段时间内只会有少量的节点能算出来。并且因为哈希不可逆,不可能有人直接把一种可行解搞出来,遇到别人算出的可行解也不能随意改变内容(一旦改了交易序列那部分那么求出来的哈希就不符合要求了)。一旦某个人求出来之后,就可以把这个消息通过gossip协议传给其他节点。大家需要约定,一旦发现别人比你先算出来了,那么自己就放弃,认为这个人算出来的结果所对应的转账请求是“共识”;并且约定如果有多个人声称自己是某个时间段内的master,就以某个逻辑接受其中一个(比如谁更长选谁,同样长选两个哈希结果中更小的那个),拒绝另一个。那么根据Gossip算法可以知道,最终整个集群是可以知道这个时间段内达成共识的交易记录的。

每一次算出一个哈希,这部分数据就是一个“块”,每个块都是依赖前置条件的块的,因此是一个链条,也就是“区块链”。

因为集群中的节点数、总的计算能力是浮动的,不能因为节点多就不断的算出新的块。所以对哈希结果大小的要求也是动态调整的,如果过去几个块表明集群中的平均计算力比较大,就降低哈希结果的阈值,以提高难度;反之降低难度。从概率上保证平均每M分钟可以算出一个块,M太大,会导致转账慢,M太小,会导致概率上同时算出结果的节点太多从而冲突太多不好处理。另外因为在块中的记录才是被集群认可的交易记录,但是因为整个集群中可能同一时间算出多个不同的块,从最终一致性的角度我们可以确定这些冲突的块最终会被其中一个唯一的取代。但如果某个最终非法的块X曾经计算出某个账户多了10块钱,然后这个人当时很快再把钱转走买了现实中的东西,并且因为一些节点还没收到真正合法的块X,用这个会被取代的结果算出来块X+1,同时接受了把10块钱又转走的转账请求,那么当最终这个块和后续的块都作废后,这个人没有得到任何币,但拿到了现实中的东西,就悲剧了……所以一般来说,一个转账记录如果在块X中,必须当集群算出了块X+N之后,才允许在转账计算余额是考虑块X中的收益。这个N设置为一个安全的值之后,就可以保证即使最终一致性,大家也不会先交易再被取消。如果设置的N不够用,那这个币的公信力基本就废了,俗称“分叉”。N和M一样,也需要设定一个合适的值,太大了转账慢(准确的说是转账确认成功慢),太小了有风险。

到这为止,我们可以做到确保所有交易记录不是伪造的、并且确保确认交易过程是集群的节点轮流做的(防止某个节点故意恶心人阻止某些交易)。而这个确认过程是需要大量消耗计算资源的(枚举哈希,所以GPU算这个有很大优势),那么大家凭啥要花电费做这个事情?比特币的设计者通过“分配原始余额”的方式来鼓励大家干这个,每个算出块的人可以分到若干比特币,作为奖励,这样大家就有动力来算了,俗称“挖矿”。所以每个人的余额其实就是挖矿所得+转账收益。整个系统只要大多数人都按照约定俗成的规矩办事(比如块的认定、块难度的认定、对交易的认定等),即使有人捣乱大家也不会理。但是假如有人耗费大量的计算资源,使自己算哈希的能力超过了其他人的总和,那么就存在51%攻击。所谓51%攻击,并不能伪造交易给自己转账(因为靠公钥私钥鉴定),而是通过更快的算出合法的块,在单位时间内算出比公网中评分更大的区块链并且捂着不公开,来故意让自己和外面分叉。同时先用比特币转账买东西,然后等N个块对方确认交易后把东西给你,这个时候把自己捂着的区块链公开出来,之前的交易全部作废,然后自己就没损失任何比特币然后拿到了现实中的东西……

以上就是一个“加强版的Gossip”,很大程度上可以说是为了解决拜占庭将军问题的一个去中心化的一致性算法。因此并不是只能用在电子币中。比如可以弄个公开记录数据的系统,把转账记录改成一堆bytes,用类似的算法就支持每个人都记录一段公开的实名消息(比特币本质上是实名的,每个人都知道每个账户的全部交易记录,只不过大家不知道这个实名的比特币账户是现实中谁拥有的,所以在这种意义上才是匿名)、无法篡改伪造也无法被别人屏蔽。而这些用途可以由一些切实有需求的若干个实体(公司、国家等等)来做,他们需要一个公开公正的分布式无中心系统来记录这些(比如跨行转账、统计数据等等),完全可以实名挖矿计算块,那么只要约定每个人出特定的计算能力就可以搭一个类似的系统了,只需要考虑不被51%攻击的问题就可以。

本文出自 杨肉的演讲台,转载时请注明出处及相应链接。

本文永久链接: https://yangzhe1991.org/blog/2016/09/gossip-bitcoin-blockchain/

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Ɣ回顶部