【深度知识】25种区块链共识算法全面详解
1，摘要
本文尽可能列出所有主要的共识算法，评估各自的优劣之处。共识算法是区块链的核心技术，本文会跟随作者的理解，持续更新。如果读者发现有所遗漏，或是存在错误，希望能通过评论指出。
2，区块链共识算法
2.1 工作量证明（PoW，Proof of Work）
优点： 自2009年以来得到了广泛测试，目前依然得到广泛的使用。
不足：速度慢。耗能巨大，对环境不好。易受“规模经济”（economies of scale）的影响。
使用者： Bitcoin、Ethereum、LiteCoin、Dogecoin等。
类型：有竞争共识(Competive consensus）。
解释：PoW是是首个共识算法。它是由中本聪在他的论文中提出的，用于建立分布式无信任共识并识别“双重支付”（double spend）问题。PoW并非一个新理念，但是中本聪将Pow与加密签名、Merkle链和P2P网络等已有理念结合，形成一种可用的分布式共识系统。加密货币是这样系统的首个基础和应用，因而独具创新性。
在PoW的工作方式中，区块链参与者（称为“矿工”）要在区块链中添加一块交易，必须解决某种“复杂但是无用”的计算问题。
只要由矿工提交的工作有超过一半是值得信任的，那么Bitcoin就是安全的。
从某种角度来看，PoW有点像买彩票，只是概率高一点而已。
技术原理：
工作量证明最核心的技术原理是散列函数（哈希）。在比特币中，PoW工作其实就是如何去计算一个区块的目标哈希值问题，让用户进行大量的穷举运算，同时得出这个哈希值还必须满足一些必要条件，这个条件在区块链中其实就是一个难度系数值，通过计算出的哈希值是否符合前面N位全是0，最终达成工作量证明。
举个例子：
比如现在给出一个固定的字符串“Hello, blockchain”，现在要求计算的难题是将这个字符串与一个随机数（Nonce）拼接起来，并通过SHA256哈希计算一个固定256位长度的哈希值，如果计算结果得到的前5位全是0，即认为满足计算条件，同时得到的随机数（Nonce）值证明为达成工作量证明的有效随机数。
2.2 权益证明（PoS，Proof of Stake）
优点：节能、攻击者代价更大、不易受“规模经济”的影响。
不足：“无利害关系“（Nothing at stake）”攻击问题。
使用者：Ethereum（即将推出）、Peercoin、Nxt。
类型：有竞争共识。
解释：
类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。
简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度，在股权证明POS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。以太坊就是采用POS共识算法。
从某种角度来看，PoS有点像银行存款，你持有的时间越长，本金越大，你得到的利息会越多。
技术原理：
每个旷工都有出块(即挖矿)的权力，只要出块成功，就有系统给出的奖励，这里不需要通过复杂的计算来挖矿，问题只在于谁来出块，股权越大，出块的概率就越大，反之，则相反。POS有很多变种，股权可以是持有币的数量，或者支付的数量等等。
go的demo代码实现:
package main
import (
"time"
"strconv"
"crypto/sha256"
"math/rand"
"fmt"
"encoding/hex"
)
//实现pos挖矿的原理
type Block struct {
Index int
Data string //
PreHash string
Hash string
Timestamp string
//记录挖矿节点
Validator *Node
}
func genesisBlock() Block {
var genesBlock = Block{0, "Genesis block","","",time.Now().String(),&Node{0, 0, "dd"}}
genesBlock.Hash = hex.EncodeToString(BlockHash(&genesBlock))
return genesBlock
}
func BlockHash(block *Block) []byte {
record := strconv.Itoa(block.Index) + block.Data + block.PreHash + block.Timestamp + block.Validator.Address
h := sha256.New()
h.Write([]byte(record))
hashed := h.Sum(nil)
return hashed
}
//创建全节点类型
type Node struct {
Tokens int //持币数量
Days int //持币时间
Address string //地址
}
//创建5个节点
//算法的实现要满足 持币越多的节点越容易出块
var nodes = make([]Node, 5)
//存放节点的地址
var addr = make([]*Node, 15)
func InitNodes() {
nodes[0] = Node{1, 1, "0x12341"}
nodes[1] = Node{2, 1, "0x12342"}
nodes[2] = Node{3, 1, "0x12343"}
nodes[3] = Node{4, 1, "0x12344"}
nodes[4] = Node{5, 1, "0x12345"}
cnt :=0
for i:=0;i<5;i++ {
for j:=0;j<nodes[i].Tokens * nodes[i].Days;j++{
addr[cnt] = &nodes[i]
cnt++
}
}
}
//采用Pos共识算法进行挖矿
func CreateNewBlock(lastBlock *Block, data string) Block{
var newBlock Block
newBlock.Index = lastBlock.Index + 1
newBlock.Timestamp = time.Now().String()
newBlock.PreHash = lastBlock.Hash
newBlock.Data = data
//通过pos计算由那个村民挖矿
//设置随机种子
rand.Seed(time.Now().Unix())
//[0,15)产生0-15的随机值
var rd =rand.Intn(15)
//选出挖矿的旷工
node := addr[rd]
//设置当前区块挖矿地址为旷工
newBlock.Validator = node
//简单模拟 挖矿所得奖励
node.Tokens += 1
newBlock.Hash = hex.EncodeToString(BlockHash(&newBlock))
return newBlock
}
func main() {
InitNodes()
//创建创世区块
var genesisBlock = genesisBlock()
//创建新区快
var newBlock = CreateNewBlock(&genesisBlock, "new block")
//打印新区快信息
fmt.Println(newBlock)
fmt.Println(newBlock.Validator.Address)
fmt.Println(newBlock.Validator.Tokens)
}
输出结果：
{1 new block 72e8838ad3bb761c7d3ba42c4e6bad86409dd3f4ce958c890409c4b9ddf44171 e4f9575cfb14ee146810862c9e5cc78ebff185f5888f428dbb945bd9060b31f7 2018-06-29 19:29:04.827332898 +0800 CST m=+0.000837770 0xc42007e0a0}
0x12341
2
2.3 委任权益证明（DPOS，Delegated Proof-of-Stake）
优点：
节能、快速、高流量博客网站Steemit就使用了它。EOS 的块时间是 0.5 秒。
不足：
略为中心化、拥有高权益的参与者可投票使自己成为一名验证者。这是近期已在 EOS 中出现的问题。
采用者：BitShares、Steemit、EOS、Lisk、Ark。
类型：协同型共识
解释：在 DPoS 系统中，权益持有者可以选举领导者（或称为见证人，Witness）。经权益持有者授权，这些领导者可进行投票。该机制使得 DPoS 要快于正常的 PoS。
例如，EOS 中选举出 21 位见证人，并且有一堆节点（潜在的见证人）作为候选者。一旦见证人节点死亡或是做出了恶意行为，新节点就会立刻替代见证人节点。见证人会因为生成区块而获得一笔支付费用。该费用是由权益持有者设立的 。
通常，所有节点采用轮询方式，一次生成一个区块。该机制防止一个节点发布连续的块，进而执行“双重支付”攻击。如果一个见证人在分配给他的时间槽中未生成区块，那么该时间槽就被跳过，并由下一位见证人生成下一个区块。如果见证人持续丢失他的区块，或是发布了错误的交易，那么权益持有者将投票决定其退出，用更好的见证人替换他。
在 DPoS 中，矿工可以合作生成块，而不是像在 PoW 和 PoS 中那样竞争生成。通过区块生成的部分中心化，DPoS 的运行可以比其它共识算法呈数量级快。
从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。EOS就是采用DPOS共识算法。
技术原理：
假设n为21，竞选的节点有几百个，持币人对这些节点进行投票，选出票数最多的21位，由这21位轮流来出块。
GO DEMO简单实现：
package main
import (
"fmt"
"math/rand"
"time"
"strconv"
"crypto/sha256"
"encoding/hex"
)
type Block struct {
Index int
Timestamp string
Prehash string
Hash string
Data []byte
delegate *Node// 代理 区块由哪个节点挖出
}
func GenesisBlock() Block {
gene := Block{0, time.Now().String(),"", "", []byte("genesis block"), nil}
gene.Hash = string(blockHash(gene))
var delegate *Node = new(Node)
delegate.Name = "Genis Block"
delegate.Votes = 0;
gene.delegate = delegate
return gene
}
func blockHash(block Block) []byte {
record := strconv.Itoa(block.Index) + block.Timestamp + block.Prehash + hex.EncodeToString(block.Data)
h := sha256.New()
h.Write([]byte(record))
hashed := h.Sum(nil)
return hashed
}
//节点类型
type Node struct {
Name string //节点名称
Votes int // 被选举的票数
}
func (node *Node)GenerateNewBlock(lastBlock Block, data []byte) Block {
var newBlock = Block{lastBlock.Index+1, time.Now().String(), lastBlock.Hash, "", data, nil}
newBlock.Hash = hex.EncodeToString(blockHash(newBlock))
newBlock.delegate = node
return newBlock
}
//创建节点
var NodeArr = make([]Node,10)
func CreateNode() {
for i := 0; i < 10; i++ {
name := fmt.Sprintf("NODE %d num", i+1)
NodeArr[i] = Node{name, 0}
}
}
//简单模拟投票
func Vote() {
for i := 0; i < 10; i++ {
rand.Seed(time.Now().UnixNano())
vote := rand.Intn(10) + 1
NodeArr[i].Votes = vote
}
}
//选出票数最多的前3位
func SortNodes() []Node {
n:= NodeArr
for i := 0; i<len(n) ;i++ {
for j := 0; j < len(n)-1 ;j++ {
if n[j].Votes < n[j+1].Votes {
n[j],n[j+1] = n[j+1],n[j]
}
}
}
return n[:3]
}
func main() {
CreateNode()
fmt.Println(NodeArr)
Vote()
nodes := SortNodes()
fmt.Println(nodes)
//创建创世区块
gene := GenesisBlock()
lastBlock := gene
for i:= 0; i< len(nodes) ;i++ {
//打印新区块信息
// var node *Node
node := lastBlock.delegate
fmt.Println("区块号:",lastBlock.Index,"节点名称:",node.Name,"节点投票数:",node.Votes)
lastBlock = nodes[i].GenerateNewBlock(lastBlock,[]byte(fmt.Sprintf("new block %d",i)))
}
}
输出结果：
[{NODE 1 num 0} {NODE 2 num 0} {NODE 3 num 0} {NODE 4 num 0} {NODE 5 num 0} {NODE 6 num 0} {NODE 7 num 0} {NODE 8
num 0} {NODE 9 num 0} {NODE 10 num 0}]
[{NODE 1 num 3} {NODE 2 num 3} {NODE 3 num 3}]
区块号: 0 节点名称: Genis Block 节点投票数: 0
区块号: 1 节点名称: NODE 1 num 节点投票数: 3
区块号: 2 节点名称: NODE 2 num 节点投票数: 3
2.4 拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）
优点：高速、可扩展。
不足：通常用于私有网络和许可网络。
采用者：Hyperledger Fabric、Stellar、Ripple、Dispatch
解释：拜占庭将军问题是分布式计算中的一个经典问题。问题描述为，几位拜占庭将军分别率领部队合力包围了一座城市。他们必须一致决定是否发起攻城。如果一些将军在没有其他将军参与的情况下决定发起攻城，那么他们的行动将以失败告终。将军们之间相互隔着一定的距离，必须依靠信息传递进行交流。 一些加密货币协议在达成共识时使用了特定版本的 BFT，每种版本都具有各自的优缺点：
[1] 实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）：首个提出的该问题解决方案称为“实用拜占庭容错”（PBFT），当前已被 Hyperledger Fabric 采用。PBFT 使用了较少（少于 20 个，之后会稍有增加）的预选定将军数，因此运行非常高效。它的优点是高交易通量和吞吐量，但是不足之处在于是中心化的，并用于许可网络。
从某种角度来看，PBFT有点像《天黑请闭眼杀人游戏》的玩法。
[2] 联邦拜占庭协议（FBA，Federated Byzantine Agreement）：另一类拜占庭将军问题的解决方案是 FBA，已被 Stellar 和 Ripple 等代币使用。FBA 的通用理念是每个拜占庭将军负责自身的链、消息一旦到来，通过排序建立事实。在 Ripple 中，将军（验证者）是 Ripple 基金会预先选定的。在 Stellar 中，任何人都可以成为验证者，需要用户选择去相信哪个验证者。
由于 FBA 可提供令人难以置信的吞吐量、低交易开销和网络扩展性，我相信 FBA 类公式算法是目前提出的最好的分布式共识发现算法。
技术原理：
PBFT基于拜占庭将军问题，一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：
其中C为发送请求端，0123为服务端，3为宕机的服务端，具体步骤如下：
1.Request：请求端C发送请求到任意一节点，这里是0
2.Pre-Prepare：服务端0收到C的请求后进行广播，扩散至123
3.Prepare：123,收到后记录并再次广播，1->023，2->013，3因为宕机无法广播
4.Commit：0123节点在Prepare阶段，若收到超过一定数量的相同请求，则进入Commit阶段，广播Commit请求；
5.Reply：0123节点在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈；
GO demo代码样例：
package main
import (
"os"
"fmt"
"net/http"
"io"
)
//声明节点信息,代表各个小国家
type nodeInfo struct {
//标示
id string
//准备访问的方法
path string
//服务器做出的相应
writer http.ResponseWriter
}
//存放四个国家的地址
var nodeTable = make(map[string]string)
//拜占庭在Fabric中的使用
func main() {
//获取执行的参数
userId :=os.Args[1]//获取执行的第一个参数
fmt.Println(userId)
//./main Apple
//创建四个国家的地址
nodeTable = map[string]string {
"Apple":"localhost:1111",
"MS":"localhost:1112",
"Google":"localhost:1113",
"IBM":"localhost:1114",
}
node:=nodeInfo{userId,nodeTable[userId],nil}
fmt.Println(node)
//http协议的回调函数
//http://localhost:1111/req?warTime=8888
http.HandleFunc("/req",node.request)
http.HandleFunc("/prePrepare",node.prePrepare)
http.HandleFunc("/prepare",node.prepare)
http.HandleFunc("/commit",node.commit)
//启动服务器
if err:=http.ListenAndServe(node.path,nil);err!=nil {
fmt.Print(err)
}
}
//此函数是http访问时候req命令的请求回调函数
func (node *nodeInfo)request(writer http.ResponseWriter,request *http.Request){
//设置允许解析参数
request.ParseForm()
//如果有参数值，则继续处理
if (len(request.Form["warTime"])>0){
node.writer = writer
//激活主节点后，广播给其他节点,通过Ａpple向其他节点做广播
node.broadcast(request.Form["warTime"][0],"/prePrepare")
}
}
//由主节点向其他节点做广播
func (node *nodeInfo)broadcast(msg string ,path string ){
//遍历所有的国家
for nodeId,url:=range nodeTable {
if nodeId == node.id {
continue
}
//调用Get请求
//http.Get("http://localhost:1112/prePrepare?warTime=8888&nodeId=Apple")
http.Get("http://"+url+path+"?warTime="+msg+"&nodeId="+node.id)
}
}
func (node *nodeInfo)prePrepare(writer http.ResponseWriter,request *http.Request) {
request.ParseForm()
//fmt.Println("hello world")
//在做分发
if(len(request.Form["warTime"])>0){
//分发给其他三个人
node.broadcast(request.Form["warTime"][0],"/prepare")
}
}
func (node *nodeInfo)prepare(writer http.ResponseWriter,request *http.Request){
request.ParseForm()
//调用验证
if len(request.Form["warTime"])>0{
fmt.Println(request.Form["warTime"][0])
}
if len(request.Form["nodeId"])>0 {
fmt.Println(request.Form["nodeId"][0])
}
node.authentication(request)
}
var authenticationsuccess = true
var authenticationMap = make(map[string]string)
//获得除了本节点外的其他节点数据
func (node *nodeInfo)authentication(request *http.Request) {
//接收参数
request.ParseForm()
if authenticationsuccess!=false {
if len(request.Form["nodeId"])>0 {
authenticationMap[request.Form["nodeId"][0]]="ok"
}
}
if len(authenticationMap)>len(nodeTable)/3 {
//则拜占庭原理实现,通过commit反馈给浏览器
node.broadcast(request.Form["warTime"][0],"/commit")
}
}
func (node *nodeInfo)commit(writer http.ResponseWriter,request *http.Request){
//给浏览器反馈相应
io.WriteString(node.writer,"ok")
}
如何运行：开启4个终端，eg：go run main.go Apple ...
然后在浏览器输入：http://localhost:1112/req?warTime=1234
输出结果待补充...
2.5 未完待续
3，参考
（1）分布式共识算法专栏 - 汇集各种共识算法
https://recomm.cnblogs.com/blogpost/11284374?page=1
（2）区块链共识算法全面详解
http://www.elecfans.com/blockchain/843819.html
（3）共识算法DPOS原理及实现
https://www.meiwen.com.cn/subject/hxqzyftx.html
（4）拜占庭PBFT简单实现
https://www.meiwen.com.cn/subject/prvjuftx.html
