区块链共识算法研究

区块链共识算法研究

by HenceZhang@Lancet

Quickly glimpse of all contents:

motivation

完成分布式大作业

拖了好几个星期，不能再拖了

研究区块链中的共识算法的设计思想、具体实现以及运行性能

介绍一下byzantine general的问题

pos和pow的简要介绍

通过达成共识的速度，即收敛的快慢来判断运行的性能，因为时间限制，最终只实现了一种共识算法

研究分布式系统中相关机制在区块链中的具体应用

在区块链中运用到分布式系统知识的地方，节点发现，消息交换，RPC，状态转移与同步

深入理解区块链中设计的细节，以及在实现区块链时可能存在的问题与解决方案

In cryptography we trust

target

一个具体而微的、简化的区块链骨架

省略了大量完整区块链中应该有的元素，仅仅保留与共识和分布式系统实现紧密相关的内容;

弱化了签名验证和各种安全性认证，假设所有的节点都是安全可信的；

对区块链的数据结构做了大幅度的修正，只保留关键的参数；

在区块的交易部分，不进行任何的交易的记录，只记录原本的coinbase交易；

修改UXTO部分，将这一部分直接并入到coinbase交易；

简化网络拓扑，平均化节点算力等等；

一套具有一定完备性的消息协议和rpc协议

区块的同步势必涉及到消息的交换，对此，我们总共设计了4种类型的消息；

节点响应消息而产生的状态转移，通过RPC来实现

一个能够稳定运行的客户端+服务端

所有的节点使用相同的代码，既作为服务端又作为客户端，所有的初始配置均是一样的

一个自治的分布式系统

在分布式系统运转过程，所有区块链节点能够实现收敛的弱同步，而不需要再运行过程中加入其他人为的干预）

两种区块链中的共识算法：POW和POS

一个快速部署所有分布式节点的方案

使用docker集群来部署所有的分布式节点，运行空间隔离，使用ip来作为命名系统的参考

一个参考区块链browser的可视化方案

通过一个命令行可视化软件，打印出当前区块链的状态，以及各节点的相关信息，如网路拓扑等

implementation

节点发现与主机维护

方案一：固定的发现协议，通过分发配置文件预先设计每个节点所能连接的节点

方案二：动态发现协议，存活节点，每隔10s向全网广播存活状态，并将其收到的最早的广播两个的源节点作为其邻接节点

采用方案二。

节点发现需要单独启动一个线程，以共享全局变量的方式，实现与其他线程之间的消息交换

实现：

初始化，广播，并同时开始接受信息，写状态文件，维护状态数组，写日志

难度更新与迭代

pow:

与传统pow方式一致，但是为了降低多节点时的负载，每计算一次hash，sleep 0.5s，1min大概做100次hash，10个节点大概1000次hash

难度表示：sha256(block)

难度调整：1分钟产生一个区块，0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff/1000为标准难度，难度调整基于前5次区块产生的间隔与默认的区块产生间隔的比值：

new_ difficulty = ( span_time/5*60) * lastest_difficulty

pos：

要求进行一段时间的pos后，通过管理信息的作用，有pow算法转为pos算法

此处的pos采用pos与pow结合的方式，根据当前节点的stake数量占总stake数量的百分比，以当前标准难度作为参考，调整每个节点各自的难度

难度表示:sha256(block) coff （coff = your_stake/ block_height * miner_award）

难度调整：new_difficulty = ( span_time/5*60) * lastest_difficulty

pow/pos

默认使用pow，为pos预留了开发的接口，通过发送管理消息，可以在pow执行过程中切换到pos;

此处的pos并不是纯粹的pos，通过结合pow来实现

消息设计

UDP消息：

UDP广播消息：haozigege字符串

TCP消息

{"method":"block_request", "height":height,"content":extra}

消息基本格式：

block_request (height) 向目标服务器请求指定高度的区块信息

block_reply(height) 向目标服务器发送指定高度的区块信息

legacy_reply 向目标服务器发送一条空消息

global_request 请求当前节点的meta信息（包括网路拓扑以及区块信息）

global_reply 返回当前节点的meta信息（包括网路拓扑以及区块信息）

admin 发送管理信息，主要用于pos/pow之间的切换（未实现）

四种类型消息：

区块设计

区块格式设计：

pre_hash: 00000000000000000000000000000000

nonce: 00000000000000000000000000000000

diffculty: 01

height: 1

transaction:

coinbase:

input: [{'address':'god','amount':'100'}]

output: {'address':'68417869136203721917051245941136583605259118843664693293743712222590878008563'}

signature:

data: 'The Times 24/4/2018 Hencecoin starts'

创世区块：

{"nonce":"0000000000000000000000000000000000000000000000000000000000000000","difficulty":"4189374bc6a7ef9db22d0e5604189374bc6a7ef9db22d0e5604189374bc6a7","height":1,"transaction": [{"input": [{"amount":100,"address":"god"}, {"amount":,"address":"ba7693c5c1f80bd85c0ede83713f491c2b9a72039f77683495155e66e6dddd2f1c107c6b1a5b5419aa1324cfe8fb61afe892bd3250760e9255594090b39a0019"}],"signature":"","data":"The Times 24/4/2018 Hencecoin start","output": {"address":"ba7693c5c1f80bd85c0ede83713f491c2b9a72039f77683495155e66e6dddd2f1c107c6b1a5b5419aa1324cfe8fb61afe892bd3250760e9255594090b39a0019"}}],"prev_hash":"0000000000000000000000000000000000000000000000000000000000000000"}

签名与验证

在初始化过程中，每一个节点均使用RSA算法，产生自己的公私钥，p,q长度512位，创世区块中使用的公私钥如下：

公钥：

私钥：

63636f70795f7265670a5f7265636f6e7374727563746f720a70300a28637273612e6b65790a507269766174654b65790a70310a635f5f6275696c74696e5f5f0a6f626a6563740a70320a4e7470330a5270340a284c393736353836393739393832333338333335393632323335393735343138313831323632353332343233313531323032363037373038323338313635313238373434303334313637323337393833393031343732323235373338363131313737343033353135323937343434303738313738313336373338333835353030343031373530363830333033313436333032313439333438353539334c0a4936353533370a4c353831383936303532313237393633303133353534353631373731383234373730343039313130373438343934303438353830363634343539373736313330363936343639363932303235343738373036373936353439373135393631343031353830343430343538333331333938303336303535363732333130383339363637303837373034353838313239383930363730333435343437334c0a4c363234303538323136313038393337353833343939313233373131393033393237363938373635353831343633333131323632303935383538333238323931353032393235353231313235373338343738334c0a4c313536343839373233393939303630373234323032323435303933323034313934393036393538353839383435303233323730363131373034333838303337323337313230323037314c0a4c353431363035323439313835313033383633303733373331373631393932303238393234383838303539333031393234333738303638363937353239353837333138363635373538313330333635333338314c0a4c3732323634353938373332313239353431343338353237303232393134323538343239303433303536303330343833333033353034373737373833353335333931333639383531334c0a4c333634323938343436303739373836383530313038303632343836353931323039383732353137303735363930323232393133353934393830393538373935313435303136323732383339363338393933374c0a7470350a622e

私钥的字符串通过pickle序列化产生，本质上是一个rsa模块的privkey对象，使用时需要反序列化;

消息的签名以及区块的hash函数均使用sha256;

在产生新区块的过程中，使用节点自身的私钥签名某个消息内容，然后在接受新区块的过程中，对该信息进行验证。

区块消息同步机制

以双节点同步为例：

node A ， 当前miner区块高度 Ha，当前存储区块高度Ha-1

node B， 当前miner区块高度Hb，当前存储区块高度Hb-1

node A广播 Ha - 1, node B广播Hb -1

for node A:

if Ha = Hb -1,

if prev_hash matches, 使用B发送的区块Hb-1更新当前区块

if prev_hash not match, 区块高度-1

if Ha > Hb-1, 向B发送Hb的区块

if Ha

if Ha -1 = Hb-1 ,pass

自动化部署

自动化部署我们使用docker，每一个节点对应一台docker，所有的节点使用同一套代码文件，使用不同的文件目录记录区块链状态以及公私钥;

在代码目录下，每次使用命令./docker.sh，即可开启一台全新的docker，并启动区块链节点。所有的节点使用ip进行区分。

runtime

初始化区块链与客户端公私钥，载入已有区块

生成或加载私钥，如果当前区块高度为0，则生成创世区块，如果存在已有区块，则加载已有的区块

启动存活广播线程

存活主机每间隔一定时间，使用UDP协议向整个局域网广播存活消息。

启动UDP广播发现线程

接受其他节点广播的存活信息，并动态维护节点主动连接的其他节点的列表。

启动区块信息广播线程

使用TCP协议，向维护的host_list数组中的全部主机节点广播最高高度的区块信息

启动区块信息接收线程

接受来自其他节点的消息，并使用异步消息7队列存储消息

启动消息消费者线程

通过队列获取消息，并使用处理函数处理，处理原理，参考于RPC协议设计

启动miner线程

获取当前区块信息，按照一定速率生成计算hash值，并使用满足条件的hash值对应的nonce，生成当前区块

启动watch dog线程

定时检测以上线程的状态，并将结果输出到终端

outcome

场景一：节点之间的相互发现

发送发起udp广播，接收方接收广播，并把节点加入到host_list数组中

场景二：节点的关闭

关闭某节点已经建立连接的另一节点，因为TCP广播信息传输超时，抛出错误，并将节点从host_list中除去。

场景三：通过miner挖取到新的区块

通过不断地更新nonce以及时间戳来生成新的区块。新的区块必须满足的条件：区块的hash

场景四：接收到来自其他主机的更高的区块

接受到来自其他节点的区块通知，发现区块高度高于本地。在对区块信息做校验之后，使用接受到区块信息来更新本地的区块信息，并更新miner进程的meta信息。

场景五：区块链分叉与收敛

区块链的分叉现象在区块生成速度较快时会出现，在共识算法的作用下，这些分叉会快速收敛到难度最高的主链。

我们使用四个节点用于演示：

由图，我们可以看到172.17.0.4与172.17.0.5达成了共识，但是172.17.0.6产生了高度相同、hash值不同的区块，此时，区块链出现了分叉；节点172.17.0.7，尚未同步完成，区块高度小于其他节点。

一段时间后，172.17.0.6率先发现了新的区块，全场区块高度最高；且172.17.0.4接收到了172.17.0.6的区块信息，开始用回溯算法，向172.17.0.6同步区块。

当然，因为生成区块的速度很快，在同步的同时，也有可能生成新的分叉：

对于每一个节点而言，区块的检测到分叉后会有如下行为：

用接受的临近区块更新当前区块，更新balance_list，从文件系统中删除旧的区块，更新miner的meta信息。

场景五：难度的收敛

我们将难度调整设置为动态调整，大致的原理是通过前五次的区块产生时间间隔来调整标准难度，使得每次区块产生时间最终收敛到1min左右。因为测试时间比较紧，短期内只能观测到区块生成时间不断地在较短时间和较长时间中震荡。

场景六：可视化软件对区块链状态与主机状态的监控

在区块链节点所在的局域网中开启一个监控节点，通过global_request方法发送请求，获取当前节点主要的全局信息。并通过python的curses模块，在终端下，对区块链状态和节点信息做可视化处理。

效果如下所示：

resources

PPT, 思维导图，源代码： https://github.com/zhl2008/blockchain-ex

记得给个star哦 (｡･ω･｡)ﾉ♡

ackownledgements

introspelliam

marvin-kun