基于Golang在单机下创建一个区块链

算法讨论 Karos

​

前端时间wld很火，这段时间meme币也如火如荼，所以我打算看看区块链到底是什么。

区块链定义

请在此添加图片描述

区块链的数据结构

废话不多说，区块链，其实是由区块头、区块节点组成

区块节点中，又包括上一个区块的地址、Nonce、时间戳、区块信息等。

这里说说区块信息。

每一个区块链的用处，都是用来存储交易信息的，但是一个区块链只存储一个信息特别站内存，那么有没有办法存放多比交易？区块链套链表数组？理论可以，但是有可能某个数组中，会被修改，无法校验。

这里提到校验，主要原因是因为，区块链有一个特性：去中心化。

去中心化是啥？

简单来说，传统的B/S或C/S架构，都是很多个客户端对接一台或一个集群上的服务器，而去中心化就是说，服务器不再管理数据，所有数据在每个客户端节点上面自行存在，最终通过分布式共识算法来做到区块同步。

但是这里不说去中心化分布式共识的实现，感兴趣的话可以去看看Raft算法和bftp算法。

这里的代码，我是用Golang来实现，因为Golang在后续写分布式共识上比较方便，语法也比Java简洁，当然，你也可以用C/C++来实现。

区块链表

type BlockChain struct {
    Nodes    []*BlockNode `json:"nodes,omitempty"`    // 节点数组
    Version  string       `json:"version,omitempty"`  // 版本号
    TreeSize int64        `json:"treeSize,omitempty"` // 默克尔树大小
}

这个结构体中，记录了一系列的区块指针数组，当前区块链的版本号，对于TreeSize，具体的作用是用于表示该区块链中，默克尔树的最大大小（为了存储大量数据以及便于校验）。

区块节点

type BlockNode struct {
    // 前一个结点的"Hash值
    Prev"Hash      string            `json:"prev"Hash,omitempty"`
    // 当前节点的版本号
    Version       string            `json:"version,omitempty"`
    // 当前节点创建时的时间戳
    Datestamp     long              `json:"datestamp,omitempty"`
    // 当前节点中默克尔树
    RootTree      merkal.MerkalTree `json:"rootTree,omitempty"`
    // 默克尔书的"Hash码
    RootTreeCode  string            `json:"propertyCode,omitempty"`
    // 令牌，用于难度计算，计算 nonce 值的过程就是对区块 header 不断的运算哈希，直至找到能使区块哈希小于 target 的 nonce。（这里不做过多的阐述，这和挖矿有关）
    Nonce         string            `json:"nonce,omitempty"`
    // 当前节点默克尔树的大小
    LocalTreeSize int64             `json:"LocalTreeSize,omitempty"`
}

默克尔树

先来说说默克尔树的数据结构是什么样的，为什么能够快速进行区块链的校验。

假设我们有一堆消息数组，我们分成n组，然后再两两一组，依次这样，知道剩余一个节点为止。

每一个节点存储的内容，是其来源的两个节点的"Hash值，

默克尔树数据结构

type MerkalTree struct {
    RootNode *MerkalNode `json:"rootNode,omitempty"`
    DataSet  *[]Message  `json:"dataSet,omitempty"`
    RootHash string      `json:"root"Hash,omitempty"`
}

如果校验失败，那么我们跟着根节点递归下去校验，即可，时间复杂度是$log_n$

如果说，节点信息是奇数呢？

很简单，保留，把其他的合并即可，奇数的最后合并，或者一开始就把奇数节点复制一份，但是不建议这么做，这样做空间一定会加倍

信息原型

package merkal

import (
    "encoding/json"
    "reflect"
    "time"
)

type Message struct {
    Title      string    `json:"title"`
    Text       string    `json:"text"`
    CreateTime time.Time `json:"createTime"`
}

func (this *Message) String() string {
    res, _ := json.Marshal(this)
    return string(res)
}

func (this *Message) Equals(other Message) bool {
    return reflect.DeepEqual(this, other)
}

区块链的操作逻辑

哈希操作—深度哈希的实现

这里需要把哈希单独拿出来，为什么？因为这里不是用的地址，也不是像C系语言一样手搓哈希表的哈希计算方式，我们需要保证信息和节点的强一致性，所以我们是对内容进行哈希。

那么如何实现呢？

要实现深度哈希计算，那么首先就是要实现一个深拷贝的方法

Golang有着深拷贝的实现，但是我们要加密。

我们可以模仿js实现深拷贝的方式，转换为json字符串，然后我们再将json字符串进行RSA加密得到哈希值

对于区块节点的hash计算

type BlockChain struct {
    Nodes    []*BlockNode `json:"nodes,omitempty"`    // 节点数组
    Version  string       `json:"version,omitempty"`  // 版本号
    TreeSize int64        `json:"treeSize,omitempty"` // 默克尔树大小
}

func (this *BlockChain) String() string {
    marshal, _ := json.Marshal(this)
    return string(marshal)
}
func NewBlockChain(treeSize int64) *BlockChain {
    return &BlockChain{TreeSize: treeSize, Version: "V1.0.0"}
}

func hash(node BlockNode) string {
    sum256 := sha256.Sum256([]byte(node.String()))
    return fmt.Sprintf("0x%x", sum256)
}

在这里，我们使用Sprintf来进行16进制输出

好了，这里是基础部分，接下来是比较重要的

默克尔树节点的hash计算

这里，我们要注意，默克尔树的哈希又两种数据结构，一种是信息原型，另一种是默克尔树叶，所以我们使用一个统一接口来实现，然后我们再向下转型

func hash(o1 common.Object, o2 common.Object) string {
    t1 := ""
    if o1 != nil {
        te, f := (o1).(*Message)
        if f {
            let := *te
            t1 = let.String()
            //fmt.Println(let, "=", t1)

        } else {
            let := *(o1).(*MerkalNode)
            t1 = let.String()
            //fmt.Println(let, "=", t1)
        }
    }
    t2 := ""
    if o2 != nil {
        te, f := (o2).(*Message)
        if f {
            let := *te
            t2 = let.String()
            //fmt.Println(let, "=", t2)

        } else {
            let := *(o2).(*MerkalNode)
            t2 = let.String()
            //fmt.Println(let, "=", t2)
        }
    }
    //fmt.Println("正在哈希", t1, t2)
    bytes := []byte(t1 + t2)
    sum256 := sha256.Sum256(bytes)
    return fmt.Sprintf("0x%x", string(sum256[:]))
}

默克尔树的校验

func (this *MerkalTree) Valid(other MerkalTree) (*Message, bool) {
    if this.RootHash == other.RootHash {
        return nil, true
    }
    return this.RootNode.Valid(other.RootNode, this.DataSet, other.DataSet)
}

func (this *MerkalNode) Valid(other *MerkalNode, oldData *[]Message, newData *[]Message) (*Message, bool) {
    if this.Equals(other) {
        return nil, true
    }
    if this.Left != nil && other.Left == nil {
        return nil, false
    }
    if (this.Right != nil && other.Right == nil) || (this.Right == nil && other.Right != nil) {
        return nil, false
    }
    if this.Left == nil && other.Left != nil {
        return nil, true
    }
    if this.Left == nil && this.Right == nil && this.Rp != -1 && this.Lp != -1 {
        LpMsg := (*newData)[other.Lp]
        if this.Lp != other.Lp {
            return &LpMsg, false
        }
        RpMsg := (*newData)[other.Rp]
        if this.Rp != other.Rp {
            return &RpMsg, false
        }
        oldLpMsg := (*oldData)[other.Lp]
        if LpMsg != oldLpMsg {
            return &LpMsg, false
        }
        oldRpMsg := (*oldData)[other.Rp]
        if RpMsg != oldRpMsg {
            return &RpMsg, false
        }
    }
    valid, b := this.Left.Valid(other.Left, oldData, newData)
    if !b {
        return valid, b
    }
    node, b2 := this.Right.Valid(other.Right, oldData, newData)
    if !b2 {
        return node, b2
    }
    return nil, true
}

其实就是个二分，我们只需要递归找到最后一个出错的节点就可以了，但是这个代码有个问题，不知大家有没有发现？

比如有这样的节点

默克尔树节点校验

B没有问题，C也没有问题，但是客户端在传输的过程中，A出现了错误怎么办？

所以这里我们还需要对当前节点进行校验

最后的代码如下

if b && b2 && !this.Equals(other) {
   return nil, false
}

这里我们就不反回哪个节点报错了，因为没有意义。

如果需要返回的话，自行进行一次接口抽象吧，哈哈，最后的代码

func (this *MerkalNode) Valid(other *MerkalNode, oldData *[]Message, newData *[]Message) (*Message, bool) {
   if this.Equals(other) {
      return nil, true
   }
   if this.Left != nil && other.Left == nil {
      return nil, false
   }
   if (this.Right != nil && other.Right == nil) || (this.Right == nil && other.Right != nil) {
      return nil, false
   }
   if this.Left == nil && other.Left != nil {
      return nil, true
   }
   if this.Left == nil && this.Right == nil && this.Rp != -1 && this.Lp != -1 {
      LpMsg := (*newData)[other.Lp]
      if this.Lp != other.Lp {
         return &LpMsg, false
      }
      RpMsg := (*newData)[other.Rp]
      if this.Rp != other.Rp {
         return &RpMsg, false
      }
      oldLpMsg := (*oldData)[other.Lp]
      if LpMsg != oldLpMsg {
         return &LpMsg, false
      }
      oldRpMsg := (*oldData)[other.Rp]
      if RpMsg != oldRpMsg {
         return &RpMsg, false
      }
   }
   valid, b := this.Left.Valid(other.Left, oldData, newData)
   if !b {
      return valid, b
   }
   node, b2 := this.Right.Valid(other.Right, oldData, newData)
   if !b2 {
      return node, b2
   }
   if b && b2 && !this.Equals(other) {
      return nil, false
   }
   return nil, true
}

一些基本的CRUD和默克尔树的生成

这些就轻轻松松了，我这上面就全部写在一起，具体的源代码可以去看我的github仓库，嘿嘿

BlockChain

func (this *BlockChain) String() string {
    marshal, _ := json.Marshal(this)
    return string(marshal)
}
func NewBlockChain(treeSize int64) *BlockChain {
    return &BlockChain{TreeSize: treeSize, Version: "V1.0.0"}
}

func hash(node BlockNode) string {
    sum256 := sha256.Sum256([]byte(node.String()))
    return fmt.Sprintf("0x%x", sum256)
}
func (this *BlockChain) AddMsg(message *merkal.Message) {
    nodeLen := 0
    Lock.Lock()
    nodeLen = len(this.Nodes)
    defer Lock.Unlock()
    if nodeLen == 0 {
        this.AddNode(NewBlockNode("head", this.Version, merkal.MerkalTree{}))
        nodeLen = len(this.Nodes)
    }
    prev := this.Nodes[nodeLen-1]
    useSize := prev.RootTree.Size()
    if useSize < this.TreeSize {
        prev.RootTree.AddNode(message)
        return
    }
    tree := new(merkal.MerkalTree)
    tree.AddNode(message)
    node := NewBlockNode(hash(*prev), this.Version, *tree)
    this.AddNode(node)

}
func (this *BlockChain) AddNode(node *BlockNode) {
    defer func() {
        a := recover()
        if a != nil {
            fmt.Println(a)
        }
    }()
    if node.Version != this.Version {
        panic("版本号不对")
    }
    nodeLen := len(this.Nodes)
    if nodeLen == 0 {
        this.Nodes = append(this.Nodes, NewBlockNode("head", this.Version, merkal.MerkalTree{}))
        nodeLen = len(this.Nodes)
    }
    prev := this.Nodes[nodeLen-1]
    node.PrevHash = hash(*prev)
    this.Nodes = append(this.Nodes, node)
}

BlockNode

func NewBlockNode(prevHash string, version string, rootTree merkal.MerkalTree) *BlockNode {
   node := &BlockNode{PrevHash: prevHash,
      Version:   version,
      Datestamp: long(time.Now().UnixMilli()),
      RootTree:  rootTree,
      Nonce:     getNonce(),
   }
   node.Build()
   return node
}

func getNonce() string {
   return string("test")
}

func (this *BlockNode) Build() {
   this.RootTreeCode = this.RootTree.RootHash
   this.LocalTreeSize = this.RootTree.Size()
}

func (this *BlockNode) Valid(node *BlockNode) bool {
   defer func() bool {
      err := recover()
      if err != nil {
         log.Println(err)
         return false
      }
      return true
   }()
   this.Build()
   node.Build()
   localVersion, localSize := node.Version, node.LocalTreeSize
   if this.Version != localVersion || this.LocalTreeSize != localSize {
      return false
   }
   valid, b := this.RootTree.Valid(node.RootTree)
   if b {
      return true
   } else {
      panic(valid.String())
   }
}
func (this *BlockNode) String() string {
   this.LocalTreeSize = this.RootTree.Size()
   jsonBytes, _ := json.Marshal(this)
   return string(jsonBytes)
}

MerkalNode

func (this *MerkalNode) String() string {
   marshal, _ := json.Marshal(this)
   return string(marshal)
}

func (this *MerkalNode) Equals(other *MerkalNode) bool {
   if other == nil {
      return false
   }
   return reflect.DeepEqual(this, other)
}
func NewMerkalNode(Left *MerkalNode, Right *MerkalNode, Hash string, Lp int, Rp int) *MerkalNode {
   res := &MerkalNode{Left: Left, Right: Right, Hash: Hash, Lp: Lp, Rp: Rp}
   //fmt.Println(res)
   return res
}

MerkalTree

func getSize(node *MerkalNode, size int64) int64 {
   if node == nil {
      return size
   }
   size = getSize(node.Left, size)
   size++
   size = getSize(node.Right, size)
   return size
}
func (this MerkalTree) Size() int64 {
   return getSize(this.RootNode, 0)
}
func (this *MerkalTree) AddNode(data *Message) {
   if this.DataSet == nil {
      this.DataSet = (new([]Message))
   }
   messages := append((*this.DataSet), *data)
   this.DataSet = (&messages)
   this.Detail()
}

func (this *MerkalTree) String() string {
   res, _ := json.Marshal(this)
   return string(res)
}

func (this *MerkalTree) binaryDetail(data *[]Message, l int, r int) (resNode *MerkalNode) {
   if r == l {
      resNode = NewMerkalNode(nil, nil, hash(&(*data)[l], nil), l, r)
      return resNode
   }
   if r-l == 1 {
      resNode = NewMerkalNode(nil, nil, hash(&(*data)[l], &(*data)[r]), l, r)
      return resNode
   }
   mid := (l-r)>>1 + r
   left := this.binaryDetail(data, l, mid)
   right := this.binaryDetail(data, mid+1, r)
   resNode = NewMerkalNode(left, right, hash(left, right), -1, -1)
   return resNode
}

func (this *MerkalTree) Detail() {
   data := this.DataSet
   l := 0
   r := len(*data) - 1
   detail := this.binaryDetail(data, l, r)
   this.RootNode = detail
   this.RootHash = (hash(detail, nil))
}

func NewMerkalTree(dataSet *[]Message) (res *MerkalTree) {
    res = &MerkalTree{DataSet: dataSet}
    res.RootHash = hash(res, nil)
    return res
}

Message

func (this *Message) String() string {
   res, _ := json.Marshal(this)
   return string(res)
}

func (this *Message) Equals(other Message) bool {
   return reflect.DeepEqual(this, other)
}

公共父接口

type Object interface {
   String() string
}

总结

以上内容便是本期的分享，关于Raft和bftp我将在以后进行实践后再发文，大家也可以去看看etcd来扩展下见识

源代码github地址：https://github.com/Karosown/blockLink.git
目前raft和bftp算法暂未实现，同时也欢迎大家一起来完善这个项目

  • 微信或QQ扫一扫

发表回复

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

→ 目录