单机版区块链的实现

全部代码都已开源在git上 hyblockchain

前置知识

开始之前，首先要了解一些基础知识,这里简单的介绍一下

区块链的结构

区块（Block）包含：
区块头（Block Header）：包含前一个区块哈希、Merkle 根、时间戳、随机数等
交易列表（Transactions）：每个区块中打包的所有交易
链（Chain）：每个区块通过 previousHash 指向前一个区块形成链

哈希函数

作用：确保数据完整性、防篡改
常用：SHA256（Bitcoin）、Keccak256（Ethereum）
本实验使用的是SHA256

交易系统

  1. 交易结构（Transaction）

    • 发送方地址、接收方地址、金额、签名（可选）
    • 交易池（Mempool）：待打包的交易集合

  2. 简单账户模型或UTXO模型

    • 账户模型（如 Ethereum）：记录每个地址的余额
    • UTXO 模型（如 Bitcoin）：每个未花费输出作为新交易输入

状态树 MPT

使用的是key,value来实现

叶子节点：实际存放值的节点
分支节点：有16个子节点，用来指向多条路径
扩展节点：存储公共前缀，它的下一节点只能是分支节点

数据的持久化

如LevelDB、BoltDB 等

  • 区块数据、交易池、状态等写入数据库
  • 简单项目可以先用文件系统或内存

数据库的实现

使用LevelDB数据库，由Google LevelDB 的GO版本实现 github.com/syndtr/goleveldb/leveldb，用LevelDB封装模块，实现自定义的接口kvstore.KVStore

leveldb 是 kvstore 接口的一种具体实现，为了解耦，适应不同的后端，如：Redis,InMemoryDB等

首先定义kvstore接口

package kvstore

import (
	"io"
)

// KVStore 定义了键值存储的接口
type KVStore interface {
	// 基本操作
	Get(key []byte) ([]byte, error)
	Put(key []byte, value []byte) error
	Delete(key []byte) error
	Has(key []byte) (bool, error)

	// 批量操作
	Batch() Batch
	Write(batch Batch) error

	// 迭代器
	NewIterator(prefix []byte) Iterator

	// 关闭存储
	io.Closer
}

// Batch 定义了批量操作的接口
type Batch interface {
	Put(key []byte, value []byte)
	Delete(key []byte)
	Reset()
	Len() int
}

// Iterator 定义了迭代器的接口
type Iterator interface {
	Next() bool
	Key() []byte
	Value() []byte
	Error() error
	Release()
}

用LeveLDB进行封装（实现里面的接口方法）


package leveldb

import (
	"github.com/syndtr/goleveldb/leveldb"
	"github.com/syndtr/goleveldb/leveldb/iterator"
	"github.com/syndtr/goleveldb/leveldb/util"
	"hyblockchain/kvstore"
)

// LevelDB 实现了KVStore接口
type LevelDB struct {
	db *leveldb.DB
}

// NewLevelDB 创建一个新的LevelDB实例
func NewLevelDB(path string) (kvstore.KVStore, error) {
	db, err := leveldb.OpenFile(path, nil)
	if err != nil {
		return nil, err
	}
	return &LevelDB{db: db}, nil
}

// Get 获取指定键的值
func (l *LevelDB) Get(key []byte) ([]byte, error) {
	return l.db.Get(key, nil)
}

// Put 存储键值对
func (l *LevelDB) Put(key, value []byte) error {
	return l.db.Put(key, value, nil)
}

// Delete 删除指定键
func (l *LevelDB) Delete(key []byte) error {
	return l.db.Delete(key, nil)
}

// Has 检查键是否存在
func (l *LevelDB) Has(key []byte) (bool, error) {
	return l.db.Has(key, nil)
}

// Batch 创建新的批量操作
func (l *LevelDB) Batch() kvstore.Batch {
	return &levelDBBatch{
		batch: new(leveldb.Batch),
	}
}

// Write 执行批量操作
func (l *LevelDB) Write(batch kvstore.Batch) error {
	b, ok := batch.(*levelDBBatch)
	if !ok {
		return nil
	}
	return l.db.Write(b.batch, nil)
}

// NewIterator 创建新的迭代器
func (l *LevelDB) NewIterator(prefix []byte) kvstore.Iterator {
	iter := l.db.NewIterator(util.BytesPrefix(prefix), nil)
	return &levelDBIterator{iter: iter}
}

// Close 关闭数据库连接
func (l *LevelDB) Close() error {
	return l.db.Close()
}

// levelDBBatch 实现了Batch接口
type levelDBBatch struct {
	batch *leveldb.Batch
}

func (b *levelDBBatch) Put(key, value []byte) {
	b.batch.Put(key, value)
}

func (b *levelDBBatch) Delete(key []byte) {
	b.batch.Delete(key)
}

func (b *levelDBBatch) Reset() {
	b.batch.Reset()
}

func (b *levelDBBatch) Len() int {
	return b.batch.Len()
}

// levelDBIterator 实现了Iterator接口
type levelDBIterator struct {
	iter iterator.Iterator
}

func (i *levelDBIterator) Next() bool {
	return i.iter.Next()
}

func (i *levelDBIterator) Key() []byte {
	return i.iter.Key()
}

func (i *levelDBIterator) Value() []byte {
	return i.iter.Value()
}

func (i *levelDBIterator) Error() error {
	return i.iter.Error()
}

func (i *levelDBIterator) Release() {
	i.iter.Release()
}

MPT，储存状态

mpt是默克尔树，用来存储状态，它的结构分为：叶子节点，分支节点，扩展节点，使用key,value对来实现

叶子节点，扩展节点，分支节点

开始实现mpt的时候，首先要定义好它的三种节点，一个node节点是由一个结构体实现的，那么这个结构体包含哪些呢？

首先肯定有节点类型（nodetype），key,value(仅叶子节点使用)
那么考虑到分支节点是拥有16个子节点的数组（为什么分支节点是16子节点，可以在niblle篇章找到答案），所以还得有个16长度大小的数组，同时这个当数组索引为零时，就可以给扩展节点使用作为它的下一个节点。

type NodeType byte

const (
	BranchNode    NodeType = 0
	ExtensionNode NodeType = 1
	LeafNode      NodeType = 2
)

// Node 表示MPT中的一个节点
type Node struct {
	Type     NodeType  // 节点类型
	Key      []byte    // 压缩路径（用于扩展/叶子节点）
	Value    []byte    // 存储值（仅叶子节点用）
	Children [16]*Node // 子节点数组（仅分支节点使用）
	Hash     []byte    // 当前节点的哈希（默认为 nil，需外部生成）
}

接下来还要实现创建这三种节点的函数，根据结构体的内容，很好实现的，比如创建一个分支节点

// NewBranchNode 创建一个新的分支节点
func NewBranchNode() *Node {
	return &Node{
		Type:     BranchNode,
		Children: [16]*Node{},
	}
}

序列化

从上面可知，我们的节点是结构体，那又怎样实现key value呢，通过序列化来实现。

序列化：就是把一个结构体（如一个节点 Node）转成一串 字节（[]byte），可以存入数据库或通过网络传输。

func (m *MPT) serializeNode(n *Node) []byte

它做的就是把不同类型的节点（Leaf / Extension / Branch）变成字节流，以便后续：

  • 写入 LevelDB（db.Put(hash, bytes)）
  • 或用于计算哈希（hashNode()）

叶子节点的序列化：

case LeafNode:
	buf.Write(n.Key)    // 写入 Key（注意是 nibbles 格式）
	buf.Write(n.Value)  // 写入 Value

格式：[Type=2] [Key…] [Value…]

扩展节点的序列化：

case ExtensionNode:
	buf.Write(n.Key)              // 路由部分 key（是 nibble 数组）
	buf.Write(n.Children[0].Hash) // 连接的下一个节点的哈希

格式：[Type=1] [Key…] [Child.Hash]（32 字节）

Extension 节点只保存路径和“下一跳”的指针（哈希）

分支节点的序列化：

case BranchNode:
	for _, child := range n.Children {
		if child != nil {
			buf.Write(child.Hash)              // 写入子节点的哈希
		} else {
			buf.Write(make([]byte, 32))       // 空位写入32个 0 占位
		}
	}
	if n.Value != nil {
		buf.Write(n.Value) // 如果该分支节点自身存了值（如 key 正好在这里结束），也写入
	}

格式：
[Type=0]
[Child0.Hash (32字节)]
[Child1.Hash (32字节)]
…
[Child15.Hash (32字节)]
[Value（可选）]

serializeNode() 就是把节点对象 ➜ 转成固定格式的 byte slice，便于存储与计算哈希。

不同类型节点序列化格式不同，必须带类型标识，以便未来可以反序列化。

niblle

一个byte是8位，所以一个分支节点就要有256个子节点，很浪费内存，而我们使用nibble代表半个字节(4位)，刚好是16个子节点，正好与我们设计的分支节点有16个子节点对应

每一层的分支就是根据下一个 nibble 值来决定走哪个方向。

举例来说：

  • key := []byte(“a”)
  • “a” 的 ASCII 是 0x61，二进制是 01100001
  • 第一个nibble是0110=6，第二个nibble是0001=1
  • nibbles = [6, 1] // 因为 0x61 的高 4 位是 6，低 4 位是 1
func bytesToNibbles(b []byte) []byte {
	nibbles := make([]byte, len(b)*2)
	for i, v := range b {
		nibbles[i*2] = v >> 4         // 高四位
		nibbles[i*2+1] = v & 0x0f     // 低四位
	}
	return nibbles
}
//代码解释
nibbles[i*2]     = v >> 4     // 0110 0001 >> 4 = 0000 0110 = 0x06 = 6
nibbles[i*2 + 1] = v & 0x0f   // 0110 0001 & 0000 1111 = 0000 0001 = 0x01 = 1

计算公共前缀

找出两个字节数组（通常是两个 key 路径）前面有多少个字节是相同的，即它们的“最长公共前缀”有多长，我们构建一个树，有共同前缀的就用扩展节点存储，也是为了方便查找插入与节点的公共前缀.

func commonPrefix(a, b []byte) int {
	i := 0
	for i < len(a) && i < len(b) && a[i] == b[i] {
		i++
	}
	return i
}

以上就是mpt的核心辅助函数，接下来介绍核心操作了，mpt中的增删查改

get 从mpt中获取值

查找一个值，我们是从上往下的递归查找每次比较当前节点能否匹配 key 的前缀，然后继续递归，每次都会“缩短 key”，最终 key 用光后，如果节点匹配成功，就找到；否则失败

首先获取插入key的niblle数组，沿着 nibble 数组去穿越这棵树

// Get 从MPT中获取值
func (m *MPT) Get(key []byte) ([]byte, error) {
	nibbles := bytesToNibbles(key)
	return m.get(m.root, nibbles)
}

核心函数是get(),传入m.root(根节点进行递归查找)，niblle我们要查询的路径
在get函数中判断节点类型（前置条件是传入的节点不为空）
匹配到叶子节点

  • 说明这是该路径的最后，就不做递归调用，直接判断是否相等
    • 相等就代表已找到，返回value.
    • 不相等返回错误信息
switch n.Type {
	case LeafNode:
		if bytes.Equal(n.Key, key) {
			return n.Value, nil
		}
		return nil, errors.New("key not found")
}

匹配到扩展节点
扩展节点是存储公共路径的节点

  • 有俩种情况返回错误信息
    • key的长度小于n.key，说明接下来没有路径可以继续计较查找下去了
    • key与n.key的公共前缀不相等，说明此时没有与所查找的节点路径一致
  • 当以上俩种情况都不存在，则继续进行递归调用，匹配下一个节点
  • 此时get的参数有所改变。n.Childern[0]是该扩展节点的下一个孩子节点，key[len(n.Key):]则是继续匹配除去扩展节点的路径
case ExtensionNode:
		if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) {
			return nil, errors.New("key not found")
		}
		return m.get(n.Children[0], key[len(n.Key):])

匹配到分支节点
找key[]数组的第一位（key[0]）与分支节点匹配，继续向下递归查找

  • 只要key还存在，就继续递归匹配，如果刚好匹配完了key的路径len（key）= 0，就可直接返回value,因为已经找到
  • 都不满足以上所述，就继续递归下去，接着找
  • 此时的get参数，n.Children[key[0]]，沿着这个分支节点继续找，对应的我们的参数key[1:],也要去除分支节点即找到的key[0]
    • get(n, [2, 3, 5])
    • n.Type == BranchNode，那么key[0] == 2
    • 于是我们去 n.Children[2] 找
    • 调用下一层：get(n.Children[2], [3, 5])
case BranchNode:
		if len(key) == 0 {
			return n.Value, nil
		}
		return m.get(n.Children[key[0]], key[1:])

以上三种查找值，已经介绍完，接下来介绍mpt中delete

delete 从MPT中删除键值对

我们的删除逻辑，还是一样获取要删除的key的niblle数组，是从底向上查找，进行递归，这与get的查找逻辑是相反的
它不是向我们平常一样写代码，直接删除，而是通过return n, nil （并不意味着结构没变）递归地构建新的树结构，从底向上逐层返回。最终返回newRoot 是修改后树的新根。

func (m *MPT) Delete(key []byte) error {
	nibbles := bytesToNibbles(key)
	newRoot, err := m.delete(m.root, nibbles)
	if err != nil {
		return err
	}
	m.root = newRoot
	return m.commit()
}

在delete的函数中，还是先要判断节点类型，从最简单的叶子节点开始梳理逻辑

匹配到是叶子节点
路径相等，返回nil,表示要被删除了

switch n.Type {
case LeafNode:
	if bytes.Equal(n.Key, key) {
		return nil, nil
	}
	return n, nil
}

匹配到是扩展节点

  • 首先看是否与扩展节点相匹配，如果不是，则原路返回

  • 再进行递归查找，调用 child, err := m.delete(n.Children[0], key[len(n.Key):])
    从前可知，扩展节点下一个节点必须是分支节点,所以在递归后，分支节点的逻辑非常关键，所以先来介绍一下
    匹配到分支节点
    无论时扩展节点递归到分支节点，还是直接匹配到分支分支节点，都必须考虑删除分支节点对应的叶子节点后，是否要考虑压缩，就比如，分支节点刚好有俩个有效叶子节点，删除其中一个后，剩下那个就要考虑与分支节点或者前面还有扩展节点进行一个压缩为一个叶子节点，其核心是路径压缩

  • 首先判断key是否被消耗完了

    • 如果 key 已经消费完（len(key)==0），说明当前分支节点对应的路径上有一个值，删除它（设为 nil）
    • 否则取出 key 的第一个 nibble（key[0]），递归去对应的子节点里继续删除，删除后将子节点更新
case BranchNode:
	if len(key) == 0 {
		n.Value = nil
	} else {
		child, err := m.delete(n.Children[key[0]], key[1:])
		if err != nil {
			return nil, err
		}
		n.Children[key[0]] = child
	}
  • 统计子节点
    • 遍历16个子节点，数有多少个非空的（有效）；
    • lastChildIndex 记录最后一个非空节点索引（方便后续压缩用）
nonNilChildren := 0
lastChildIndex := -1
for i, child := range n.Children {
	if child != nil {
		nonNilChildren++
		lastChildIndex = i
	}
}
  • 判断是否压缩
if nonNilChildren == 1 && n.Value == nil {
	child := n.Children[lastChildIndex]
	if child.Type == ExtensionNode {
		return NewExtensionNode(append([]byte{byte(lastChildIndex)}, child.Key...), child.Children[0]), nil
	}
	return NewLeafNode(append([]byte{byte(lastChildIndex)}, child.Key...), child.Value), nil
}
  • 压缩的条件
    • 当前分支节点只剩下 1个有效子节点；
    • 当前分支节点没有自己的 value（即它不是路径终点）；
  • 压缩实现
    • 新节点的路径是原来的子节点路径，前面加上该子节点所在分支索引 lastChildIndex（即4bit的路径片段）；
    • 如果子节点是 ExtensionNode，就把它的 Key 合并起来，构造新的 ExtensionNode（路径更长，指向下一级）；
      • BranchNode -> index 2 → ExtensionNode [3, 4]
      • 压缩后为ExtensionNode [2, 3, 4]
    • 如果子节点是 LeafNode，也类似，构造新的叶子节点，路径合并，值继承
      • BranchNode->index 2 → LeafNode [3, 4] → “Hello”
      • 压缩后为LeafNode [2, 3, 4] → “Hello”
  • 如果都不满足压缩条件，就直接返回当前节点

那么当匹配到分支节点的时候，递归调用后，有是如何呢，让我们继续看

匹配到扩展节点时，要进行递归调用child, err := m.delete(n.Children[0], key[len(n.Key):]) 此时会进入分支节点的逻辑，

  • 如果返回的child是扩展节点，就进行压缩为一个新的扩展节点
  • 如果返回的是分支节点或者叶子节点，说明不能压缩了，保留原结构
case ExtensionNode:
		if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) {
			return n, nil
		}
		child, err := m.delete(n.Children[0], key[len(n.Key):])
		if err != nil {
			return nil, err
		}
		if child == nil {
			return nil, nil
		}
		if child.Type == ExtensionNode {
			return NewExtensionNode(append(n.Key, child.Key...), child.Children[0]), nil
		}
		return NewExtensionNode(n.Key, child), nil

删除的情况我们都说完了，小结一下，从n.root开始向下查找要删除的节点，找到删除后，再递归返回时，看有没有特殊情况进行压缩，一直递归返回一个新的root,此时删除已经完成

insert 在MPT中插入或更新节点

这个是非常难的逻辑了，很复杂，但是理清逻辑就很好写了
有了之前的递归思想，其实插入的逻辑就是考虑的情况比较多而已，要把每一种的逻辑都要想好

对传入的key,进行转化为niblle数组，方便我们比较路径，最后还是返回的是一个新root,与之前查找删除的逻辑有些区别的是，它先要找到插入的位置，所以就必须使用到之前说介绍的计算公共前缀的方式

匹配到叶子节点
还是看它的公共前缀是否相等，相等就插入

case LeafNode:
		common := commonPrefix(n.Key, key)
		if common == len(n.Key) && common == len(key) {
			n.Value = value
			return n, nil
		}

如果没有一个与之匹配的叶子节点，即common为零，就新建一个分支节点，分别把叶子节点和插入节点放入

branch := NewBranchNode()
		if common == 0 {
			if len(n.Key) > 0 {
				branch.Children[n.Key[0]] = NewLeafNode(n.Key[1:], n.Value)
			} else {
				branch.Value = n.Value
			}
			if len(key) > 0 {
				branch.Children[key[0]] = NewLeafNode(key[1:], value)
			} else {
				branch.Value = value
			}
			return branch, nil
		}

如果有公共前缀，但是不等于len(n.key)或者len(key),就创建一个扩展节点+分支节点

extension := NewExtensionNode(key[:common], branch)
		if common < len(n.Key) {
			branch.Children[n.Key[common]] = NewLeafNode(n.Key[common+1:], n.Value)
		} else {
			branch.Value = n.Value
		}
		if common < len(key) {
			branch.Children[key[common]] = NewLeafNode(key[common+1:], value)
		} else {
			branch.Value = value
		}
		return extension, nil

叶子节点是很好理解的了

匹配到是扩展节点

要考虑俩种情况，公共前缀正好匹配，公共前缀不匹配。

计算公共前缀，等于len(n.key),再进入递归，继续沿着key[common:]路径找

common := commonPrefix(n.Key, key)
	if common == len(n.Key) {
		child, err := m.insert(n.Children[0], key[common:], value)
		if err != nil {
			return nil, err
		}
		n.Children[0] = child
		return n, nil
	}

如果不等于len(n.key)，以公共前缀作为一个新的扩展节点，剩下的放入建立的分支节点中
分支一：处理扩展节点的剩余节点（common < len(n.key)）

if common < len(n.Key) {
	child, err := m.insert(n.Children[0], n.Key[common+1:], n.Children[0].Value)
	if err != nil {
		return nil, err
	}
	branch.Children[n.Key[common]] = child
}

  • 原扩展路径中有剩余：从 n.Key[common:] 开始递归插入原有子节点

  • 注意：n.Key[common] 是分歧点的第一个字节，要作为 BranchNode 的索引使用

  • 剩下的路径（n.Key[common+1:]）挂载到新插入的子节点中

解释为什么这里要递归旧路径剩余的部分：递归 insert，是为了保留原路径的“剩余部分”，并构建新的树结构。递归只是为了让逻辑统一，不必区分是 Leaf 还是 Extension

**分支二:**处理新插入的路径(common < len(key) )

if common < len(key) {
	branch.Children[key[common]] = NewLeafNode(key[common+1:], value)
} else {
	branch.Value = value
}

  • 如果新插入的 key 在分歧点后还有内容，就将其余的部分作为新 LeafNode 添加进分支中。

  • 如果新 key 恰好终止在分歧点，则直接挂值到 BranchNode.Value

特殊情况没有共同前缀，直接返回分支节点

if common == 0 {
	return branch, nil
}

匹配到分支节点
匹配到了一个 BranchNode，说明插入路径之前已经有公共前缀了，当前路径开始要根据 nibble 分支继续走

如果插入的路径已经完全匹配当前的节点，直接就把值赋值上去

case BranchNode:
		if len(key) == 0 {
			n.Value = value
			return n, nil
		}

如果不完全匹配，再次进行递归insert

child, err := m.insert(n.Children[key[0]], key[1:], value)
		if err != nil {
			return nil, err
		}
		n.Children[key[0]] = child
		return n, nil

当路径匹配到 BranchNode，继续根据 nibble 走对应子节点递归插入；如果路径正好结束，就把值挂在当前分支节点上
插入流程图

mpt的简要流程已完成，状态讲完了，接下来继续交易池。