区块链技术的六大核心算法简述

区块
  • AIUST.Com
  • 2018-06-23 17:56

可以说区块链技术是比特币的基石,亦是一切数字加密货币的基础。目前,火爆的币圈对区块链的讨论亦不少。但相信较少人了解过区块链技术的几个核心算法,本文主要简要介绍一下其中的核心算法,

区块链核心算法一:拜占庭将军问题

拜占庭将军问题(Byzantine failures)也叫拜占庭协定。拜占庭将军问题的故事是这样产生的。据说,拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,于是拜占庭问题就此形成。

拜占庭将军问题是一个协议问题,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。

拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数,n是系统中进程的总数。

拜占庭将军问题只有在n ≥ 3t+1时有解。

区块链核心算法二:非对称加密算法

这是一种常见的加密技术,非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。 

FDCJMSF.jpg

使用过程: 

1、乙方生成两把密钥(公钥和私钥)

2、甲方获取乙方的公钥,然后用它对信息加密。

3、乙方得到加密后的信息,用私钥解密,乙方也可用私钥加密字符串

4、甲方获取乙方私钥加密数据,用公钥解密

优点: 

更安全,密钥越长,它就越难破解

缺点: 

加密速度慢

常用算法: 

RSA、Elgamal、背包算法、Rabin、D-H、ECC(椭圆曲线加密算法)

区块链核心算法三:容错问题

在任何网络中,信息的通讯过程中都可能会丢失、损坏、延迟、重复发送,而且接收方接受到的信息,其顺序与发送的顺序不一致(比如先发一个A,再发一个B;接收方可以先收到B再收A)。除了这些问题,更重要的是节点的行为可以是任意的:可以随时加入、断开或退出网络,可以丢弃消息、黑客还可以伪造消息等,还可能发生各种人为或非人为的故障。这就需要我们的算法对由共识节点组成的共识系统,提供的容错能力,这种容错能力同时包含安全性和可用性,并适用于任何网络环境。

区块链核心算法四:Paxos 算法(一致性算法)

Paxos是能够基于一大堆完全不可靠的网络条件下却能可靠确定地实现共识一致性的算法。也就是说:它允许一组不一定可靠的处理器(服务器)在某些条件得到满足情况下就能达成确定的安全的共识,如果条件不能满足也确保这组处理器(服务器)保持一致。

一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个「一致性算法」以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。 节点通信存在两种模型:共享内存和消息传递。Paxos 算法就是一种基于消息传递模型的一致性算法。

区块链核心算法五:共识机制

具体来说是这样:分布式系统中由于网络之间通讯可能会中断,虽然概率很低,但是没有100%完美的网络因此,依靠网络通讯的计算机之间要达成共识就比较困难,假设有X, Y和Z三台计算机谋划在周一攻击人类世界,它们的攻击计划是只要所有计算机可用于战斗时就一起进行攻击,不落下任何一台机器,但是当他们决定具体什么时间开始攻击时,在这个关键问题上往往会出错。

一个基本问题是,每台机器都有自己的攻击时间建议,计算机X可以建议在08:00时间,因为这个时间正是周一早晨,而人们刚刚过完狂欢的周末休息天,但是计算机Z认为13:00比较好,理由当然也有一大堆,让这三台计算机基于某个时刻达成共识是非常困难的,因此,也给人类反击留下了机会。

另外一个情况是,这三台计算机是位于世界不同的位置,之间通讯或许通过电缆或者其他不太可靠的网络设备通讯,如果X建议在08:00,它必须确认它的这个建议能够到达活着的Y和Z,以免一个人战斗。

问题是:我们不能准确地知道某个计算机的延迟的原因:是因为性能慢了还是已经是彻底死机不能用?

那么,X怎么知道其他两个计算机是可用的呢?也就是说,当X和其他两个计算机通讯发现得到响应要过很长时间,它不能确定这两台计算机到底还能不能继续活下去,也许这次通讯有延迟了,下一次它们又活过来了没有延迟了,也许下次延迟更长了一点,也许下次延迟稍微短了一点,这些随机概率问题使得X不能确定Y和Z到底是出了什么问题造成延迟的,是因为处理了某个特别耗费CPU的任务还是因为死锁等原因?当然,有些天真的设计者会说,只要我们将性能监控到位,如果延迟超过一定时间,我们人工介入告诉X确切情况就可以,那么这种人工介入的分布式系统不是一个天然自洽的自动化系统了,不在我们讨论范围之内,而且这样的系统会让人疲于奔命。

因为X不能确定Y或Z是否可用,所以X仅仅只能和Y与Z中一台基于攻击时间达成共识,就无法完全三台机器全部投入战斗的计划。注意的是,X Y Z三台中任何一台都可能会出现延迟,这就造成了三台机器之间任何通讯都是无法确认可靠的,比如X发出消息给Z,Z确认后回执给X,但是这段时间X突然死机了,那么Z要等待X多长时间才能知道它收到确认呢?还是再次等待X回复确认的确认,这样无限循环下去也不能解决它们之间通讯可能出现随机不可靠的问题。

所有关键问题在于:由于这三台机器之间通讯是无法保证100%可靠,它们就不能就任何事情达成共识。

区块链核心算法六:分布式存储

分布式存储是一种数据存储技术,通过网络使用每台机器上的磁盘空间,并将这些分散的存储资源构成一个虚拟的存储设备,数据分散的存储在网络中的各个角落。所以,分布式存储技术并不是每台电脑都存放完整的数据,而是把数据切割后存放在不同的电脑里。就像存放 100 个鸡蛋,不是放在同一个篮子里,而是分开放在不同的地方,加起来的总和是 100 个。

1、一致性

分布式存储系统需要使用多台服务器共同存储数据,而随着服务器数量的增加,服务器出现故障的概率也在不断增加。为了保证在有服务器出现故障的情况下系统仍然可用。一般做法是把一个数据分成多份存储在不同的服务器中。但是由于故障和并行存储等情况的存在,同一个数据的多个副本之间可能存在不一致的情况。这里称保证多个副本的数据完全一致的性质为一致性。

2、可用性

分布式存储系统需要多台服务器同时工作。当服务器数量增多时,其中的一些服务器出现故障是在所难免的。我们希望这样的情况不会对整个系统造成太大的影响。在系统中的一部分节点出现故障之后,系统的整体不影响客服端的读/写请求称为可用性。

3、分区容错性

分布式存储系统中的多台服务器通过网络进行连接。但是我们无法保证网络是一直通畅的,分布式系统需要具有一定的容错性来处理网络故障带来的问题。一个令人满意的情况是,当一个网络因为故障而分解为多个部分的时候,分布式存储系统仍然能够工作。


来源:AIUST.Com作者:编辑:jiyang

本文链接: http://www.aiust.com/article/20180623/324.html

声明:除非注明,本站文章均为AIUST.Com原创或编译,转载时请注明文章作者和“来源:AIUST.Com”,AIUST.Com尊重行业规范,每篇文章都标有明确的作者和来源。文章为作者观点,不代表AIUST.Com立场。

免责:阁下应知本网站的任何内容仅供参考,不能做为投资决策依据,投资有风险,入市须警慎!

相关文章

资讯

原创

荐读

热门标签