Blockhain bằng Go, Bước 2: Proof of Work

Series lập trình blockchain với Go

Block và blockchain sơ khai

Lời mở đầu

Trong bài viết đầu tiên của series về lập trình blockchain sử dụng ngôn ngữ Go, ta đã tạo được một data structure cơ bản cho blockchain của mình, đồng thời cũng implement các tính năng để các block mới có thể được add thêm vào chain. Tuy nhiên, khác với các blockchain hoàn chỉnh, hiện tại ở blockchain của chúng ta, các block được thêm vào 1 cách quá dễ dàng, không tốn công sức gì cả. Bài viết này sẽ giới thiệu bước tiếp theo để giải quyết vấn đề trên: implement Proof-of-Work (PoW), cơ chế hiện tại được dùng trong hầu hết các blockchain của các đồng tiền ảo (Bitcoin, Ethereum...).

Proof-of-Work là gì?

Trong cuộc sống mưu sinh hàng ngày của các nhân viên làm công ăn lương (như tác giả bài viết này), hầu hết chúng ta cày cuốc làm việc để đến cuối tháng có thể nghe tiếng ting ting báo hiệu tiền về tài khoản. Tuy nhiên, để công ty trả cho chúng ta khoản lương (có thể kèm phụ cấp) đó, các công sức và đóng góp của chúng ta trong vòng 1 tháng phải đã được ghi nhận và kiểm chứng là tương ứng với mức lương như vậy bởi các tầng lớp lãnh đạo bằng một cách nào đó. Trừ 1 số trường hợp đặc biệt, một nhân viên trình độ yếu, không đóng góp gì đáng kể nhưng lại nhận được lương cao chắc chắn báo hiệu một công ty có vấn đề.

Đối với 1 blockchain thì cũng tương tự như vậy. Một số thành viên tham gia blockchain (miners) phải tốn công sức (điện năng, thời gian) để thêm data vào blockchain (mining -> tạo block mới), khi hoàn thành sẽ chứng minh với hệ thống công sức (hard-work) mình bỏ ra và nhận được phần thưởng tương tứng (coin, token). Cơ chế "cày cuốc bỏ công sức và chứng minh" này được gọi chung là Proof-of-Work. Có thể nói việc đảm bảo một bài toán để khiến việc mining không quá dễ dàng, phải tốn công sức và cung cấp một cơ chế để miner có thể chứng minh công sức mình bỏ ra và nhận phần thưởng có thể nói là vấn đề quyết định sự sống còn của một blockchain.

Như vậy các thuật toán Proof-of-Work phải giải quyết được hai vấn đề: (1) bài toán phải khó, tiêu tốn nhiều tài nguyên thời gian, (2) bài toán tuy khó, nhưng việc kiểm chứng là bài toán đã giải quyết (công sức giải toán là đúng) phải nhanh và dễ dàng. Trong blockchain của Bitcoin, thì bài toán đó là việc tìm hash của một block và hash này phải đáp ứng một số yêu cầu nhất định, độ khó của việc tìm hash này sẽ thay đổi sao cho tốc độ mining ~ 6 blocks/hour.

Hashcash

Trước tiên, mình sẽ nói qua hash là gì? Các hàm hash là các hàm dùng để biểu diễn data bất kì về một chuỗi với độ dài cố định. Chuỗi này được gọi là hash và có các đặc tính sau:

Từ hash không thể phục hồi lại được data
Với một data nhất định sẽ chỉ có 1 hash
Một thay đổi nhỏ nhất của data ban đầu cũng sẽ sinh ra một hash hoàn toàn khác

Các thuật toán hash hay được dùng có thể kể đến MD5, SHA1, SHA256...

uc?id=1rTX6BwE7pdLudxchF9wOvHEPIP29jCVg&export=download

Hiện tại Bitcoin đang sử dụng thuật toán Hashcash, một thuật toán sinh ra với mục đích để chống spam email, làm thuật toán Proof-of-Work của mình. Hashcash có thể chia ra làm những bước sau:

Lấy một data mà ai cũng có thể kiểm chứng được (với email thì là email người nhận, với Bitcoin thì là block header)
Tạo ra một con đếm bắt đầu từ 0
Tạo ra chuỗi hash của data kết hợp với con đếm đã tạo ra ở trên.
Kiểm tra xem hash tạo ra có đáp ứng các yêu cầu nhất định hay không.
- Nếu có thì công việc đã hoàn thành .
- Nếu chưa thì tăng con đếm và lặp lại bước 3 và 4.

Ta có thể thấy Hashcash là một thuật toán trâu bò (brute-force): tăng con đếm -> tạo hash -> kiểm tra, lặp đi lặp lại đến khi nào thoả mãn điều kiện thì thôi. Công việc tạo hash lặp đi lặp lại tùy theo điều kiện đưa ra sẽ tốn thời gian và đòi hỏi sức mạnh tính toán của máy tính, đây chính là phần Work mà các miner phải thực hiện. Tuy nhiên do đặc tính của thuật toán hash, việc chứng minh mảng hash tạo ra đã thỏa mãn điều kiện (Proof) sẽ dễ dàng và tốn ít thời gian.

Với thuật toán Hashcash nguyên thuỷ thì điều kiện sẽ là chuỗi hash phải có 20 bit đầu là 0. Tuy nhiên, trong Bitcoin thì số lượng bit là 0 này sẽ thay đổi tuỳ theo tình trạng hiện tại của chuỗi blockchain để đảm bảo tốc độ tạo block mới ~ 6 blocks/hour.

Implementation

Trong folder code đã tạo từ phần 1. Ta tạo thêm một file mới cho việc implement Proof-of-Work và add đoạn code ban đầu sau:

// pow.go
const targetBits = 16

targetBits ở đây chính là độ dài của chuỗi bit 0 dùng để làm điều kiện trong thuật toán Hashcash. Với Bitcoin thì nó sẽ là một block header chứa độ khó mà block đã được đào ra. Trong phạm vi bài viết này, ta sẽ không thực hiện việc tự điều chỉnh độ khó, nên độ dài chuỗi bit 0 ở đây là cố định. Folder code của chúng ta giờ sẽ như sau:

gochain
 |-- .gitignore	
 |-- Gopkg.lock	
 |-- Gopkg.toml	
 |-- block.go
 |-- blockchain.goo
 |-- gochain
 |-- main.go
 |-- pow.go
 |-- util.go

Tiếp theo cũng trong file pow.go, ta sẽ implement cấu trúc dữ liệu và code khởi tạo thuật toán Proof-of-Work:

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

// InitProofOfWork Create new POW
func InitProofOfWork(b *Block) *ProofOfWork {
	target := big.NewInt(1)
	target.Lsh(target, uint(256-targetBits))

	pow := &ProofOfWork{b, target}

	return pow
}

Struct Proof-of-Work có 2 trường, một trường là pointer trỏ đến 1 block, trường target là pointer trỏ đến một số lớn Integer. Số này sẽ dùng để so sánh điều kiện sau khi hashing và như trong hàm khởi tạo Proof-of-Work được tạo thành từ số targetBits ở trên. Biểu diễn của số này dưới dạng HEX sẽ là như sau:

0x0000100000000000000000000000000000000000000000000000000000000000

Tiếp theo là đoạn code chuẩn bị data cho việc hashing

// pow.go
func (pow *ProofOfWork) prepareData(nonce int) []byte {
	data := bytes.Join(
		[][]byte{
			pow.block.PrevBlockHash,
			pow.block.Data,
			IntToBytes(pow.block.Timestamp),
			IntToBytes(int64(targetBits)),
			IntToBytes(int64(nonce)),
		},
		[]byte{},
	)

	return data
}

Đoạn code này khá đơn giản, gộp thông tin của block với độ khó targetBits và nonce. nonce chính là con đếm trong thuật toán Hashcash, nonce cũng là một thuật ngữ cryptogaphic.

Sau khi mọi đoạn code chuẩn bị đã hoàn tất thì là đoạn code để chạy Proof-of-Code:

// pow.go
const maxNonce = math.MaxInt64
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)

	for nonce < maxNonce {
		data := pow.prepareData(nonce)

		hash = sha256.Sum256(data)
		fmt.Printf("\r%x", hash)
		hashInt.SetBytes(hash[:])

		if hashInt.Cmp(pow.target) == -1 {
			break
		} else {
			nonce++
		}
	}

	fmt.Print("\n\n")

	return nonce, hash[:]
}

hashInt là biểu diễn dưới dạng Integer của chuỗi hash, còn maxNonce là giá trị (lấy bằng số Integer lớn nhất) để đề phòng trường hợp nonce bị overflow (khó mà xảy ra với setting độ khó hiện tại). Còn đoạn code trong vòng loop thì tương ứng với thuật toán Hashcash:

Chuẩn bị data
Hash với thuật toán SHA256
Đổi Hash sang dạng Integer
So sánh với target, nếu nhỏ hơn thì thoả mãn điều kiện -> xong, còn không thì tăng nonce và lặp lại 1->4

Với code chạy Proof-of-Work đã sẵn sàng, ta sửa lại code hiện có để sử dụng nó trong việc khởi tạo block.

// block.go
type Block struct {
	Timestamp     int64
	Data          []byte
	PrevBlockHash []byte
	Hash          []byte
	Nonce         int
}

// SetHash Calculate hash of current block
func (b *Block) SetHash() {
	timestamp := []byte(strconv.FormatInt(b.Timestamp, 10))
	headers := bytes.Join([][]byte{b.PrevBlockHash, b.Data, timestamp}, []byte{})
	hash := sha256.Sum256(headers)

	b.Hash = hash[:]
}

// NewBlock Create a new block
func NewBlock(data string, prevBlockHash []byte) *Block {
	block := &Block{time.Now().Unix(), []byte(data), prevBlockHash, []byte{}, 0}
	pow := InitProofOfWork(block)

	// Run proof of work
	nonce, hash := pow.Run()

	block.Hash = hash
	block.Nonce = nonce

	return block
}

Hash của block mới được tạo sẽ là kết quả của việc chạy Proof-of-Work, đồng thời giá trị nonce thoả mãn điều kiện cũng sẽ được lưu thành một trường của block mới. Vì giá trị này sẽ cần đến khi kiểm chứng xem hash này có đúng là đã được sinh ra từ data của block và thoả mãn điều kiện hay không (chứng minh công sức bỏ ra).

Cuối cùng là hàm để kiểm chứng hash, thực hiện chức năng như nói ở trên:

// pow.go
func (pow *ProofOfWork) Validate() bool {
	var hashInt big.Int

	data := pow.prepareData(pow.block.Nonce)
	hash := sha256.Sum256(data)
	hashInt.SetBytes(hash[:])

	isValid := hashInt.Cmp(pow.target) == -1

	return isValid
}

Hàm này khá đơn giản, chỉ cần tạo lại hash của thông tin của block kết hợp với giá trị nonce được chọn và check xem có đúng nó thoả mãn điều kiện nhỏ hơn target hay không.

Vậy là ta đã hoàn tất việc thêm Proof-of-Work vào blockchain đơn giản của mình. Chạy thử thôi, vì giờ có Proof-of-Work rồi nên sẽ tốn thời gian chút:

./gochain                                                                                                                  
Mining the block containing "Genesis Block"
0000f051d3ec839522770f9acf8d796e7f0952550a3036bb85024fff8d53b73b

Mining the block containing "Linh Dep Trai"
000017231df3ac466d5b254b3996c593ffe011771d144a7f95ab7e12ac14ea7c

Mining the block containing "Linh Dep Trai x2"
0000c6f30d1b0db83810e01a6db9e319220c3482ef2e074962d79924dcaa202d

Prev block's hash:
Current block's hash: 0000f051d3ec839522770f9acf8d796e7f0952550a3036bb85024fff8d53b73b
Current block's data: Genesis Block
PoW: true

Prev block's hash: 0000f051d3ec839522770f9acf8d796e7f0952550a3036bb85024fff8d53b73b
Current block's hash: 000017231df3ac466d5b254b3996c593ffe011771d144a7f95ab7e12ac14ea7c
Current block's data: Linh Dep Trai
PoW: true

Prev block's hash: 000017231df3ac466d5b254b3996c593ffe011771d144a7f95ab7e12ac14ea7c
Current block's hash: 0000c6f30d1b0db83810e01a6db9e319220c3482ef2e074962d79924dcaa202d
Current block's data: Linh Dep Trai x2
PoW: true

Kết

Vậy là blockchain tối giản của chúng ta đã có thêm tính năng Proof-of-Work, bắt đầu giống một blockchain đầy đủ hơn một chút, tuy còn thiếu rất nhiều các tính năng khác như network, lưu thông tin transaction... Các tính năng này sẽ được giới thiệu và thêm vào ở các phần sau của series.

Blockchain bằng ngôn ngữ Go - 2nd Step: Proof of Work

Lời mở đầu

Proof-of-Work là gì?

Hashcash

Implementation

Kết

Link tham khảo