【深度知识】25种区块链共识算法全面详解

作者: 笔名辉哥 | 来源:发表于2020-07-24 10:09 被阅读0次

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

（5）PBFT算法
https://www.meiwen.com.cn/subject/owzvyxtx.html

【深度知识】25种区块链共识算法全面详解

1，摘要

2，区块链共识算法

2.1 工作量证明（PoW，Proof of Work）

2.2 权益证明（PoS，Proof of Stake）

2.3 委任权益证明（DPOS，Delegated Proof-of-Stake）

2.4 拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）

2.5 未完待续

3，参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

HiBlock区块链社区

区块链入门