PART1

实验目的

  • 了解区块链上的简单数据结构
  • 实现Merkle树的构建
  • 初步理解UTXO的使用和验证
  • 理解比特币上的交易创建

实验内容

区块链的基本结构

type BlockChain struct{
    tip []byte//最新区块的哈希值
    db *bolt.DB//数据库连接
}

区块链通过链式结构连接各个区块，形成一个不断增长的分布式账本系统。

区块的基本结构

作为区块链的主要组成部分，区块由区块头和区块体构成，区块头存储了版本号，上一个区块的哈希值，当前区块交易的哈希值，时间戳等信息，唯一标识一个区块。

type BlkHeader struct {
	Version       int64
	PrevBlockHash []byte
	MerkleRoot    []byte
	Timestamp     int64
	Bits          int64
	Nonce         int64
}

实验步骤

Merkle树

每一个区块的交易节点从底向上构建Merkle树，采用哈希加密（单次sha256）。

  • 新建Merkle节点，分为叶子节点和非叶子节点

    func NewMerkleNode(left, right *MerkleNode, data []byte) *MerkleNode {
	NewNode:=&MerkleNode{}
	NewNode.Left=left
	NewNode.Right=right
	if left==nil && right==nil{
		data_sha:=sha256.Sum256(data)
		NewNode.Data=data_sha[:]
	} else{
		data_c:=append(left.Data,right.Data...)
		data_sha:=sha256.Sum256(data_c)
		NewNode.Data=data_sha[:]
	}
	return NewNode
}

  • 新建Merkle树，调用新建节点的函数自底向上构建，直到结点数为1，并且保证节点数量为偶数

    func NewMerkleTree(data [][]byte) *MerkleTree {
	NewTree:=&MerkleTree{}
	var nodes []MerkleNode
	NewTree.Leaf=data
	for _,data_i := range data{
		node_i:=NewMerkleNode(nil,nil,data_i)
		nodes=append(nodes,*node_i)
	}
	for len(nodes)>1{
		var newnodes []MerkleNode
		for i:=0;i<len(nodes)/2;i++{
			node:=NewMerkleNode(&nodes[2*i],&nodes[2*i+1],nil)
			newnodes=append(newnodes,*node)
		}
		if len(nodes)%2==1{
			node:=NewMerkleNode(&nodes[len(nodes)-1],&nodes[len(nodes)-1],nil)
			newnodes=append(newnodes,*node)
		}
		nodes=newnodes
	}
	NewTree.RootNode=&nodes[0]
	return NewTree
}

  • SPV证明路径，自底向上获取节点的路径的兄弟结点的哈希值

    先根据结点的index判断节点在树的具体位置，自顶向下访问路径，再将路径逆序即可获取SPV证明路径

    func (t *MerkleTree) SPVproof(index int) ([][]byte, error) {
	t_len:=len(t.Leaf)
	if index>t_len{
		return nil,fmt.Errorf("Outof Index")
	}
	depth:=0
	leaf_number:=1
	t_node:=t.RootNode.Left
	for t_node!=nil{
		t_node=t_node.Left
		depth+=1
		leaf_number*=2
	}
	var n_path [][]byte
	t_node=t.RootNode
	for t_node!=nil && t_node.Left!=nil{
		if index>=leaf_number/2{
			index-=leaf_number/2
			n_path=append(n_path,t_node.Left.Data)
			t_node=t_node.Right
		} else{
			n_path=append(n_path,t_node.Right.Data)
			t_node=t_node.Left
		}
		leaf_number/=2
	}
	var path [][]byte
	for i:=0;i<len(n_path);i++{
		path=append(path,n_path[len(n_path)-1-i])
	}
	return path, nil
}

  • 验证SPV路径，将该节点的哈希值和SPV证明路径依次计算，最终和根节点的哈希值比较即可完成SPV路径的验证。

    func (t *MerkleTree) VerifyProof(index int, path [][]byte) (bool, error) {
	if index>len(t.Leaf){
		return false,fmt.Errorf("Outof Index")
	}
	data_sha:=sha256.Sum256(t.Leaf[index])
	n_data:=data_sha[:]
	for _,t_data :=range path{
		if index%2==1{
			temp:=append(t_data,n_data...)
			temp2:=sha256.Sum256(temp)
			n_data=temp2[:]
		} else{
			temp:=append(n_data,t_data...)
			temp2:=sha256.Sum256(temp)
			n_data=temp2[:]
		}
		index/=2
	}
	for i:=0;i<len(n_data);i++{
		if t.RootNode.Data[i]!=n_data[i]{
			return false,nil
		}
	}
	return true, nil
}

判断Coinbase交易

每个区块新建立时，可以加入一笔coinbase交易，这笔交易只有输出，没有输入，判断的基本依据为：

  • 只出现在第一笔交易，其他交易均不是coinbase交易
  • 输入的Txid为空，Vout为-1
func (t *Transaction) IsCoinBase() bool {
	if len(t.Vin[0].Txid)==0  && (t.Vin[0].Vout==-1){
		for i:=1;i<len(t.Vin);i++{
			if len(t.Vin[i].Txid)==0 && (t.Vin[i].Vout==-1){
				return false}}
		return true}
	return false}

计算公钥对应的地址

比特币上的地址的计算如下

  1. 计算公钥的哈希值（RIPEMD16(SHA256(PubKey))）
  2. 地址计算前加入版本号
  3. 把步骤2的内容通过计算公钥哈希的双重SHA256哈希加密，取前4个字节作为校验和
  4. 版本号，公钥哈希，校验和的组合通过Base58加密生成比特币的地址
func (w *Wallet) GetAddress() []byte {
	key_hash:=HashPublicKey(w.PublicKey)
	var temp []byte
	temp=append(temp,version)
	temp=append(temp,key_hash...)
	checksum:=sha256.Sum256(temp)
	hash_checksum:=checksum[:]
	checksum=sha256.Sum256(hash_checksum)
	hash_checksum=checksum[:]
	var res []byte
	res=append(res,version)
	res=append(res,key_hash...)
	res=append(res,hash_checksum[0:checkSumlen]...)
	res=[]byte(base58.Encode(res))
	return res
}

P2PKH锁定部分

P2PKH指的是向公钥的哈希支付，根据公钥的地址的计算方法，类似的可以通公钥地址获取公钥的哈希：

公钥地址经过base58解码后，第一位是version版本号，后四位为校验和，中间即为公钥哈希

func (out *TXOutput) Lock(address []byte) {
	data,_:=base58.Decode(string(address))
	out.PubKeyHash=data[1:len(data)-4]
}

实验结果

借助go test对实验结果进行检验

PS E:\2023spring\blockchain\lab2\lab2> go test
PASS
ok      lab2    0.657s

PART2

实验目的

  • 进一步理解区块链上的数据结构
  • 实现基于的POW共识算法出块
  • 实现比特币上的账户创建和查询
  • 理解UTXO的基本使用方法
  • 实现区块链与数据库的交互

实验内容

工作量证明

工作量的证明机制（POW），简单来说就是通过提交一个容易检测，但是难以计算的结果，来证明节点做过一定量的工作。

首先完成Run函数，该函数代表矿工通过如下流程完成挖矿工作：

  1. 首先构建当前区块头，区块头包含版本号，上⼀个区块哈希值(32位)，当前区块数据对应哈希（32位，即区块数据的merkle根），时间戳，区块难度，计数器(nonce)。
  2. 添加计数器，作为随机数。计算器从0开始基础，每个回合+1
  3. 对于上述的数据来进行一个哈希的操作。
  4. 判断结果是否满足计算的条件：
    1. 如果符合，则得到了满足结果。
    2. 如果没有符合，从2开始重新直接2、3、4步骤。
func (pow *ProofOfWork) Run() (int64, []byte) {
	nonce := int64(0)
	var hash [32]byte
	var hashInt big.Int
	blkh := pow.block.Header
	for nonce < maxNonce {
		var data []byte
		data=append(data,IntToHex(blkh.Version)...)
		data=append(data,blkh.PrevBlockHash[:]...)
		data=append(data,blkh.MerkleRoot[:]...)
		data=append(data,IntToHex(blkh.Timestamp)...)
		data=append(data,IntToHex(blkh.Bits)...)
		data=append(data,IntToHex(nonce)...)
		hash = sha256.Sum256(data)
		hashInt.SetBytes(hash[:])
		if hashInt.Cmp(pow.target) == -1 {
			break
		} else {
			nonce++
		}
	}
	return nonce, hash[:]
}

借助Validate函数完成对挖矿结果的验证，即验证矿工给出的Nonce是否是该难题的答案。

func (pow *ProofOfWork) Validate() bool {
	var hashInt big.Int
	var hash [32]byte
	blkh := pow.block.Header
	var data []byte
	data=append(data,IntToHex(blkh.Version)...)
	data=append(data,blkh.PrevBlockHash[:]...)
	data=append(data,blkh.MerkleRoot[:]...)
	data=append(data,IntToHex(blkh.Timestamp)...)
	data=append(data,IntToHex(blkh.Bits)...)
	data=append(data,IntToHex(blkh.Nonce)...)
	hash = sha256.Sum256(data)
	hashInt.SetBytes(hash[:])
	return hashInt.Cmp(pow.target) == -1
}

UTXO

UTXO(Unspent Transaction Outputs)，即没有花掉的交易输出，实际可以理解为在一次转账时剩余没有转出的资金。UTXO的交易模型上，用户通过使用未使用的交易输出（UTXO）来执行一笔交易。

构建新的UTXO交易的方法如下所示：

  • 找到输入地址对应的交易PubKeyHash，借助findunspentOutputs找到输入账户的UTXO
  • 根据UTXO构建交易并进行签名
  • 完成找零操作：剩余的金额作为UTXO返回到原输入中
func NewUTXOTransaction(from, to []byte, amount int, UTXOSet *UTXOSet) *Transaction {
	var inputs []TXInput
	var outputs []TXOutput
	wal , _ := NewWallets()
	bc := UTXOSet.Blockchain
	pubKeyHash := HashPublicKey(wal.GetWallet(from).PublicKey)
	acc, validOutputs := UTXOSet.FindUnspentOutputs(pubKeyHash, amount)
	if acc < amount {
		log.Panic("ERROR: Not enough funds")
	}
	for txid, outs := range validOutputs {
		txID, err := hex.DecodeString(txid)
		if err != nil {
			log.Panic(err)
		}
		for _, out := range outs {
			input := TXInput{
				Txid:      txID,
				Vout:      out,
				Signature: nil,
				PubKey:    wal.GetWallet(from).PublicKey,
			}
			inputs = append(inputs, input)
		}
	
	out_1 := TXOutput{amount,nil}
	out_1.Lock(to)
	outputs = append(outputs, out_1)
	if acc > amount {
		out_2 := TXOutput{acc-amount,nil}
		out_2.Lock(from)
		outputs = append(outputs, out_2) 
	}
	tx := Transaction{nil, inputs, outputs}
	
	bc.SignTransaction(&tx,wal.GetWallet(from).PrivateKey)
	tx.SetID()
	return &tx
}

UTXO池

比特币所有的交易都是放在UTXO池中，这样的好处是为了快速的得到某个UTXO是否当前可用。需要通过公私钥的唯一标识来算出我们当前的余额。在构建UTXO的交易时，我们需要通过UTXO池来需要当前属于自己的UTXO，然后获得相对应的账户金额，然后再生成对应的输出。FindUnspentOutputs函数来查询用户当前未未花费的UTXO金额及其映射关系(存储txid和对应的index，便于后续查找)，具体实现如下所示：

func (u UTXOSet) FindUnspentOutputs(pubkeyHash []byte, amount int) (int, map[string][]int) {
	unspentOutputs := make(map[string][]int)
	totalAmount := 0
	db := u.Blockchain.db
	err := db.View(func(tx *bolt.Tx) error {
		b := tx.Bucket([]byte(utxoBucket))
		c := b.Cursor()

		for k, v := c.First(); k != nil; k, v = c.Next() {
			outs := DeserializeOutputs(v)
			txid := hex.EncodeToString(k)
			for outIndex, out := range outs.Outputs {
				if out.IsLockedWithKey(pubkeyHash)  {
					unspentOutputs[txid] = append(unspentOutputs[txid], outIndex)
					totalAmount += out.Value
					if totalAmount >= amount {
						return nil
					}
				}
			}
		}
		return nil
	})
	if err != nil {
		log.Panic(err)
	}
	return totalAmount, unspentOutputs
}

BlockChain

除此之外，还需要完成mineblock来生成新的区块：针对一组交易在区块链上写入一个新块，维护区块链的相关信息

func (bc *Blockchain) MineBlock(transactions []*Transaction) *Block {
	var last_hash []byte
	err := bc.db.View(func(tx *bolt.Tx) error {
		b := tx.Bucket([]byte(blocksBucket))
		last_hash = b.Get([]byte("l"))
		return nil
	})
	if err != nil {
		log.Panic(err)
	}
	var prev_hash [32]byte
	copy(prev_hash[:],(last_hash)[:32])
	newBlock := NewBlock(transactions,prev_hash)
	err = bc.db.Update(func(tx *bolt.Tx) error {
		b := tx.Bucket([]byte(blocksBucket))
		b.Put(newBlock.CalCulHash(), newBlock.Serialize())
		b.Put([]byte("l"), newBlock.CalCulHash())
		bc.tip = newBlock.CalCulHash()
		return nil
	})
	if err != nil {
		log.Panic(err)
	}	
	return newBlock
}

另外，为了维护UTXO，需要找到所有UTXO并构建映射，通过函数findUTXO实现：

  • UTXO的特点：“未使用的交易”
  • 对于每笔非CoinBase交易，每个输入都指向之前的输出，根据所有交易的输入判断之前的交易是否已被输出
  • 维护UTXO和spentTXOs通过循环求得最终的UTXO
func (bc *Blockchain) FindUTXO() map[string]TXOutputs {
	UTXO := make(map[string]TXOutputs)
	spentTXOs := make(map[string][]int)
	bci := bc.Iterator()
	for {
		block := bci.Next()
		for _, tx := range block.GetTransactions() {
			txID := hex.EncodeToString(tx.ID)
		Outputs:
			for outIdx, out := range tx.Vout {
				if spentTXOs[txID] != nil {
					for _, spentOutIdx := range spentTXOs[txID] {
						if spentOutIdx == outIdx {
							continue Outputs
						}
					}
				}
				outs := UTXO[txID]
				outs.Outputs = append(outs.Outputs, out)
				UTXO[txID] = outs
			}
			if tx.IsCoinBase() == false {
				for _, in := range tx.Vin {
					inTxID := hex.EncodeToString(in.Txid)
					spentTXOs[inTxID] = append(spentTXOs[inTxID], in.Vout)
				}
			}
		}
		if block.GetPrevhash() == [32]byte{} {
			break
		}
	}
	return UTXO
}

实验结果

本次实验基本完成了基于比特币的区块链搭建，具有以下功能：

go run .  createblockchain -address ADDRESS //创建区块链
go run .  createwallet //创建钱包
go run .  getbalance -address ADDRESS //查询账户余额
go run .  listaddresses //查询区块链上的地址
go run .  printchain //打印区块链
go run .  reindexutxo //重构UTXO池
go run .  send -from FROM -to TO -amount AMOUNT //发起转账交易

对实现的区块链进行go test

...
PASS
ok      lab3    0.188s