区块链实验

本学期一门实验课，以此记录

week1

实验1 入门练习

实验1要求三个不同正整数的最小公倍数

实验流程

1. 辗转相除法构造求解最大公约数的函数

2. 最小公倍数即乘积除以最大公约数

3. 先求任意两数的最小公倍数再与第三个数求最小公倍数

实验结果

实验代码

package main

import (
	"fmt"
)

func gcd(x, y int) int {
	tmp := x % y
	if tmp > 0 {
		return gcd(y, tmp)
	} else {
		return y
	}
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func main() {
	var a int
	var b int
	var c int
	fmt.Println("Please input three numbers:")
	fmt.Scanf("%d %d %d", &a, &b, &c)
	fmt.Println(" lowest common multiple = ", lcm(lcm(a, b), c))
}

实验2 比特币测试网地址的生成

实验流程

1. 调用库对输入公钥进行HASH160，即RIPEMD160(SHA256(Public Key))

2. 将第一步结果与Version byte拼接

3. 将第二步结果进行HASH256，即进行两次SHA256，取前4字节作为Checksum

4. 将二三步结果拼接进行Base58编码得到地址

实验结果

实验代码

package main

import (
	"base58"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"golang.org/x/crypto/ripemd160"
)

const VERSION = byte(0x6f)
const CHECKSUM_LENGTH = 4

func GetAddress(PublicKey []byte) string {

	Fingerprint := HASH160(PublicKey)
	addVersion := append([]byte{VERSION}, Fingerprint[:]...)
	Checksum := HASH256(addVersion)
	finalHash := append(addVersion, Checksum...)

	myAlphabet := base58.NewAlphabet("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz")
	address := base58.Encode(finalHash, myAlphabet)
	return address
}

func HASH160(publicKey []byte) []byte {
	sha256PK := sha256.Sum256(publicKey)
	r := ripemd160.New()
	r.Write(sha256PK[:])
	Fingerprint := r.Sum(nil)
	return Fingerprint
}

func HASH256(addVersion []byte) []byte {
	addVersion1 := sha256.Sum256(addVersion)
	addVersion2 := sha256.Sum256(addVersion1[:])
	Checksum := addVersion2[:CHECKSUM_LENGTH]
	return Checksum
}

func main() {
	pk_1, _ := hex.DecodeString("02b1ebcdbac723f7444fdfb8e83b13bd14fe679c59673a519df6a1038c07b719c6")
	pk_2, _ := hex.DecodeString("036e69a3e7c303935403d5b96c47b7c4fa8a80ca569735284a91d930f0f49afa86")
	BitcoinAddress_1 := GetAddress(pk_1)
	BitcoinAddress_2 := GetAddress(pk_2)
	fmt.Println("pk_1:", BitcoinAddress_1)
	fmt.Println("pk_2:", BitcoinAddress_2)
}

调库颇费周折，要注意把第三方库装到GOROOT或GOPATH所在路径下，一般推荐是后者

实验3 Merkle Tree

实验流程

1. 定义结构体 MerkleNode 作为节点

   type MerkleNode struct {
   	left  *MerkleNode
   	right *MerkleNode
   	Data  []byte
   	index int
   }

2. 初始化16个叶子节点，Data为对应的字符串，左右子节点都为空，索引依次赋值

3. 从下往上逐层构建树，先把相邻两个叶子节点合为子树，保存子树节点

4. 处理完叶子层再对子树结点层进行合并，最后合并到根节点，完成树的构造

5. 快速定位流程：

   • 从根节点的hash值开始比对，当根节点hash不同，叶节点有一处变动时有且只有一条路径上所有hash值都不同
   • 两树左枝相同时就转向右枝，右枝相同时就转向左枝

实验结果

实验代码

package main

import (
	"bytes"
	"crypto/sha256"
	"fmt"
	// "github.com/pochard/commons/randstr"
)

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

// 结点
type MerkleNode struct {
	left  *MerkleNode
	right *MerkleNode
	Data  []byte
	index int
}

func NewMerkleNode(left, right *MerkleNode, data []byte) *MerkleNode {

	mNode := MerkleNode{}
	if left == nil && right == nil {
		hash := sha256.Sum256(data)
		mNode.Data = hash[:]
	} else {
		preHashes := append(left.Data, right.Data...)
		hash := sha256.Sum256(preHashes)
		mNode.Data = hash[:]
	}
	mNode.left = left
	mNode.right = right

	return &mNode
}

func NewMerkleTree(data []string) *MerkleNode {

	var nodes []MerkleNode

	// 构建叶子节点
	for i, datum := range data {
		node := NewMerkleNode(nil, nil, []byte(datum))
		node.index = i
		nodes = append(nodes, *node)
	}

	j := 0
	for nSize := len(data); nSize > 1; nSize = (nSize + 1) / 2 {
		for i := 0; i < nSize; i += 2 {

			i2 := min(i+1, nSize-1)

			node := NewMerkleNode(&nodes[j+i], &nodes[j+i2], nil)
			nodes = append(nodes, *node)
		}

		j += nSize
	}

	return &nodes[len(nodes)-1]
}

func compareMerkleTree(mTree1 *MerkleNode, mTree2 *MerkleNode) int {
	if bytes.Equal(mTree1.Data, mTree2.Data) {
		return -1
	} else {
		for mTree1.left != nil {
			if bytes.Equal(mTree1.left.Data, mTree2.left.Data) {
				mTree1 = mTree1.right
				mTree2 = mTree2.right
			} else {
				mTree1 = mTree1.left
				mTree2 = mTree2.left
			}
		}
	}
	return mTree1.index
}

func main() {

	data1 := []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "0", "1", "2", "3", "#"}
	mTree1 := NewMerkleTree(data1)
	fmt.Printf("The root Hash of MerkleTree1 is %x\n", mTree1.Data)

	data2 := []string{"a", "b", "c", "d", "e", "f", "-", "h", "i", "j", "k", "0", "1", "2", "3", "#"}
	mTree2 := NewMerkleTree(data2)
	fmt.Printf("The root Hash of MerkleTree2 is %x\n", mTree2.Data)

	if compareMerkleTree(mTree1, mTree2) == -1 {
		fmt.Println("They are same")
	} else {
		fmt.Println("They are different at ", compareMerkleTree(mTree1, mTree2))
	}
}

这个实验重点就是把树构建出来，然后定位时从根节点开始直接比就可以，熟悉语言特性的话还是蛮简单的，（菜狗作者还没学会go硬着头皮写了好久）

拓展实验

是一个生成挖比特币公私钥的实验，后面再看

week2

实验一 构建区块

实验要求：

• 将空缺字段补充完整
• 实现对Block的Hash计算

实验流程

• 区块链的基本构成单位是区块，而区块又分为区块头和区块体两部分，实现的简单区块包括字段：

  字段	解释	数据类型
  Time	当前时间戳，也就是区块创建的时间	int64
  PrevHash	前一个块的哈希，即父哈希	[]byte
  Hash	当前块的哈希	[]byte
  Data	区块存储的实际有效信息，也就是交易	[]byte

  故补全结构体为：

  type Block struct {
  	Time     int64
  	Data     []byte
  	PrevHash []byte
  	Hash     []byte
  }

• 实验一要求对Block的Hash计算方法为：Hash=SHA256(PrevHash + Time+ Data)，直接实现即可

实验结果

实验代码

package main

import (
	"crypto/sha256"
	"encoding/binary"
	"time"
)

type Block struct {
	Time     int64
	Data     []byte
	PrevHash []byte
	Hash     []byte
}

func NewBlock(data string, prevHash []byte) *Block {
	block := &Block{time.Now().Unix(), []byte(data), prevHash, []byte{}}
	block.SetHash()
	return block
}

func (b *Block) SetHash() {
	//为Block生成hash，使用sha256.Sum256(data []byte)函数
	Hash := sha256.Sum256(append(append(b.PrevHash, Int64ToBytes(b.Time)...), b.Data...))
	b.Hash = Hash[:]
}

func Int64ToBytes(i int64) []byte {
	var buf = make([]byte, 8)
	binary.BigEndian.PutUint64(buf, uint64(i))
	return buf
}

实验二 链接区块成链

实验要求：

• 生成创世区块 NewGenesisBlock()
• 添加新区块 Blockchain.AddBlock()

实验流程

• 生成创世区块 NewGenesisBlock()，即调用NewBlock(),Data初始化为Genesis Block，Hash值置为空
• 添加新区块 Blockchain.AddBlock()，维护一个区块数组blocks作为区块链，将传入的Data与前一个区块的hash来构建新区块，然后把新区块放入数组中。

实验结果

实验代码

package main

type Blockchain struct {
	blocks []*Block
}

func (bc *Blockchain) AddBlock(data string) {
	//可能用到的函数：
	//	len(array)：获取数组长度
	//	append(array,b):将元素b添加至数组array末尾
	Hash := bc.blocks[len(bc.blocks)-1].Hash
	block := NewBlock(data, Hash)
	bc.blocks = append(bc.blocks, block)

}

func NewGenesisBlock() *Block {
	//创世区块前置哈希为空，Data为"Genesis Block"
	return NewBlock("Genesis Block", []byte(""))
}

func NewBlockchain() *Blockchain {
	return &Blockchain{[]*Block{NewGenesisBlock()}}
}

实验三 添加工作量证明模块

回答问题：工作量证明中的difficulty值的大小会怎样影响PoW计算时间？

设difficulty=$d$,PoW算法要求找到的hash值前$d$比特需要满足要求,成功的概率为$\frac{1}{2^d}$,当$d$线性增大时,计算时间指数级增大

实验流程

• 完善工作量证明算法，主要是Hashcash算法
  • 选择部分公开数据–在 NewProofOfWork()模块中完成
  • 维护一个初始值为0的计数器nonce
  • 首先通过prepareData()模块来准备用来Hash计算的数据
  • 计算完成后与目标值比较判断是否在给定范围内，是则结束，否则nonce加一继续循环
• 修改Block类，将nonce添加至Block结构中，修改SetHash()函数，使其调用ProofOfWork算法获得哈希值
• 完成验证函数Validate()，如区块的hash在目标范围内则返回true，否则返回false
  • 在main中增加验证部分，对每一个区块调用NewProofOfWork()算法中的Validate()方法

实验结果

实验代码

proofofWork部分

package main

import (
	"bytes"
	"crypto/sha256"
	"fmt"
	"math/big"
)

const targetBits = 4

type ProofOfWork struct {
	block  *Block
	target *big.Int
}

func NewProofOfWork(b *Block) *ProofOfWork {
	target := big.NewInt(1)
	target.Lsh(target, uint(256-targetBits))

	pow := &ProofOfWork{b, target}

	return pow
}

func (pow *ProofOfWork) prepareData(nonce int) []byte {
	data := bytes.Join(
		[][]byte{
			pow.block.PrevHash,
			pow.block.Data,
			IntToHex(pow.block.Time),
			IntToHex(int64(targetBits)),
			IntToHex(int64(nonce)),
		},
		[]byte{},
	)

	return data
}

func (pow *ProofOfWork) Run() (int, []byte) {
	var hashInt big.Int
	var hash [32]byte
	nonce := 0

	fmt.Printf("Mining the block containing \"%s\"\n", pow.block.Data)

	//Hashcash算法
	for {
		a := pow.prepareData(nonce)
		hash = sha256.Sum256(a)
		hashInt.SetBytes(hash[:])
		if hashInt.Cmp(pow.target) < 0 {
			break
		}
		nonce += 1
	}

	fmt.Printf("\r%x", hash)
	fmt.Print("\n\n")
	return nonce, hash[:]
}

func (pow *ProofOfWork) Validate() bool {
	var hashInt big.Int
	hashInt.SetBytes(pow.block.Hash)

	return hashInt.Cmp(pow.target) < 0
}

block部分

package main

import (
	"time"
)

type Block struct {
	Time     int64
	Data     []byte
	PrevHash []byte
	Hash     []byte
	Nonce    int
}

func NewBlock(data string, prevHash []byte) *Block {
	block := &Block{time.Now().Unix(), []byte(data), prevHash, []byte{}, 0}
	block.SetHash()
	return block
}

func (b *Block) SetHash() {

	pow := NewProofOfWork(b)
	b.Nonce, b.Hash = pow.Run()
}

main部分

package main

import (
	"fmt"
	"time"
)

func main() {
	t := time.Now()
	bc := NewBlockchain()

	bc.AddBlock("Send 1 BTC to Ivan")
	bc.AddBlock("Send 2 more BTC to Ivan")

	for _, block := range bc.blocks {
		fmt.Printf("PrevHash: %x\n", block.PrevHash)
		fmt.Printf("Data: %s\n", block.Data)
		fmt.Printf("Hash: %x\n", block.Hash)
		fmt.Println("Pow: ", NewProofOfWork(block).Validate())
		fmt.Println()
	}

	fmt.Println("Time using: ", time.Since(t))
}