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

Golang
44
0
0
2024-06-11
标签   区块链

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

前端时间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算法暂未实现,同时也欢迎大家一起来完善这个项目