Building Blockchain in Go. Part 2: Proof-of-Work

Proof-of-Work

Ý tưởng chính của blockchain đó là việc đưa dữ liệu vào nó phải thật khó khăn. Bởi vì đó là công việc khó khăn nên nó làm cho blockchain an toàn và nhất quán. Ngoài ra, thì sẽ có một phần thưởng được trả cho công việc khó khăn này (đây là cách mọi người nhận được tiền coins cho việc khai thác).

Cơ chế này rất giống với cơ chế trên thực tế: người ta phải làm việc chăm chỉ để có được phần thưởng và duy trì cuộc sống của họ. Trong blockchain, một số người tham gia (thợ mỏ) của mạng lưới làm việc để duy trì mạng lưới, để thêm các khối mới vào mạng lưới, và nhận được một phần thưởng cho công việc của họ. Kết quả của công việc của họ là một khối được kết hợp vào blockchain một cách an toàn, mà duy trì sự ổn định của cơ sở dữ liệu toàn bộ blockchain. Cần lưu ý rằng, người đã hoàn thành công việc phải chứng minh điều này.

Toàn bộ cơ chế "làm việc và chứng minh" này được gọi là Proof of work (bằng chứng của công việc). Thật khó vì nó đòi hỏi rất nhiều sức mạnh tính toán: ngay cả các máy tính hiệu suất cao cũng không thể làm điều đó một cách nhanh chóng. Hơn nữa, khó khăn của công việc này tăng theo thời gian để giữ các khối mới tỷ lệ khoảng 6 khối mỗi giờ. Trong Bitcoin, mục đích của công việc đó là tìm một hash cho một khối, đáp ứng một số yêu cầu. Và cái hash này được sử dụng làm bằng chứng. Do đó, việc tìm ra bằng chứng là công việc thực tế.

Một điều cuối cùng cần lưu ý. Các thuật toán Proof-of-Work phải đáp ứng được yêu cầu: làm công việc khó khăn, nhưng việc xác minh bằng chứng là dễ dàng. Bằng chứng thường được trao cho người khác, vì vậy đối với họ, không nên mất nhiều thời gian để xác minh nó.

Hashing

Trong đoạn này, chúng ta sẽ thảo luận về hash. Nếu bạn đã quen thuộc với khái niệm, bạn có thể bỏ qua phần này. Hashing là một quá trình thu thập một hash cho dữ liệu cụ thể. Một hash là một đại diện duy nhất của dữ liệu nó đã được tính trên. Hàm hash là một hàm lấy dữ liệu có kích thước tùy ý và tạo ra mã hash có một kích thước cố định. Dưới đây là một số tính năng chính của hashing:

1. Dữ liệu ban đầu không thể khôi phục từ một mã hash. Vì vậy, hashing không phải là mã hóa.
2. Một số dữ liệu có thể chỉ có một mã hash và mã hash là duy nhất.
3. Thay đổi một byte trong dữ liệu đầu vào sẽ sinh ra một mã hash hoàn toàn khác. Hashing được sử dụng rộng rãi để kiểm tra tính nhất quán của dữ liệu. Một số nhà cung cấp phần mềm đã publish checksums. Sau khi tải một tệp tin, bạn có thể nạp nó vào một hàm hash và so sánh hash được sản xuất với một phần được cung cấp bởi nhà phát triển phần mềm.

Trong blockchain, hash được sử dụng để đảm bảo tính nhất quán của một khối. Dữ liệu đầu vào cho một thuật toán hash có chứa các hash của khối trước, do đó làm cho nó không thể (hoặc, ít nhất, khá khó khăn) để sửa đổi một khối trong chuỗi. Có 1 cách để sửa đó là tính toán hash của nó và hash tất cả các khối sau nó :v

Hashcash

Bitcoin sử dụng thuật toán Hashcash, một thuật toán Proof of Work được phát triển ban đầu để ngăn chặn spam email. Nó có thể được chia thành các bước sau:

1. Lấy một số dữ liệu công khai (trong trường hợp email, đó là địa chỉ email của người nhận. Trong trường hợp Bitcoin, đó là tiêu đề khối).
2. Thêm một bộ đếm vào nó. Bộ đếm bắt đầu từ 0.
3. Lấy một mã hash của dữ liệu + kết hợp bộ đếm.
4. Kiểm tra xem mã hash đó có đáp ứng các yêu cầu nhất định ko. Nếu có bạn đã hoàn tất. Nếu không, tăng bộ đếm lại và lặp lại các bước 3 và 4.

Vì vậy, đây là một thuật toán brute force: bạn thay đổi các truy cập, tính toán một hash mới, kiểm tra nó, tăng truy cập, tính toán một hash, ..vv. Bây giờ chúng ta hãy xem xét kỹ hơn các yêu cầu mà một hash phải đáp ứng. Trong việc thực hiện Hashcash ban đầu, 1 yêu cầu như "20 bit đầu tiên của một hash phải là 0". Trong Bitcoin, yêu cầu được điều chỉnh theo thời gian, bởi vì theo thiết kế, một khối phải được tạo ra mỗi 10 phút, mặc dù sức mạnh tính toán gia tăng theo thời gian và ngày càng có nhiều thợ mỏ tham gia mạng lưới. Để giải thích thuật toán này, tôi lấy dữ liệu từ ví dụ trước ("I like donuts") và tìm thấy một mã hash bắt đầu với 3 zero bytes : ca07ca là giá trị thập lục phân của bộ đếm, là 13240266 trong hệ thập phân.

Implementation

Ok, chúng ta đã hoàn thành với lý thuyết, chúng ta hãy viết code! Trước tiên, chúng ta hãy xác định độ khó của mining:

const targetBits = 24

Trong Bitcoin, "target bits" là header của khối lưu trữ những khó khăn mà tại đó khối được khai thác. Chúng ta sẽ không thực hiện một thuật toán điều chỉnh target, vì bây giờ, chúng ta chỉ có thể xác định độ khó là global constant. 24 là một số tùy ý, mục tiêu của chúng tôi là có một target mà có ít hơn 256 bit trong bộ nhớ. Và chúng ta muốn sự khác biệt đủ lớn, nhưng không quá lớn, bởi vì sự khác biệt càng lớn thì càng khó tìm ra một mã hash hợp lý.

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
}

Ở đây tạo ra cấu trúc ProofOfWork chứa một con trỏ tới một block và một con trỏ tới một target. "Target" là một tên khác cho yêu cầu được mô tả trong đoạn trước. Chúng ta sử dụng một số nguyên lớn bởi vì chúng ta sẽ so sánh một hash với đích: chúng ta sẽ chuyển một hash sang một số nguyên lớn và kiểm tra nếu nó nhỏ hơn target.

Trong hàm NewProofOfWork, chúng ta khởi tạo một big.Int với giá trị là 1 và dịch chuyển nó sang trái bằng 256-bits target bits. 256 là chiều dài của một băm SHA-256 trong các bit, và đó là thuật toán băm SHA-256 mà chúng ta sẽ sử dụng. Biểu diễn hệ thập lục phân của target là:

0x10000000000000000000000000000000000000000000000000000000000

Và nó chiếm 29 byte trong bộ nhớ. Và đây là so sánh trực quan của nó với các hash từ các ví dụ trước đây:

0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
0000010000000000000000000000000000000000000000000000000000000000
0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca

Mã hash đầu tiên (đc tính theo "I like donuts") là lớn hơn target, vì vậy nó không phải là bằng chứng hợp lệ. Mã hash thứ hai (tính trên "I like donutsca07ca") là nhỏ hơn so với mục tiêu, do đó nó là một bằng chứng hợp lệ.

Bạn có thể nghĩ đến một target như là biên trên của một range: nếu một số (một hash) thấp hơn ranh giới, nó có giá trị, và ngược lại. Việc hạ thấp ranh giới sẽ làm giảm số lượng hợp lệ, và do đó, công việc sẽ khó khăn hơn để tìm một hợp lệ.

Bây giờ, chúng ta cần dữ liệu để hash. Hãy chuẩn bị nó:

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

	return data
}

Phần này là đơn giản: chúng ta chỉ cần hợp nhất các blocks với target và nonce. nonce ở đây là truy cập từ mô tả Hashcash ở trên, đây là một thuật ngữ mật mã.

Ok, tất cả các chuẩn bị được thực hiện, bây giờ implement cái cốt lõi của thuật toán PoW nào:

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

	fmt.Printf("Mining the block containing "%s"
", pow.block.Data)
	for nonce < maxNonce {
		data := pow.prepareData(nonce)
		hash = sha256.Sum256(data)
		fmt.Printf("
%x", hash)
		hashInt.SetBytes(hash[:])

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

")

	return nonce, hash[:]
}

Đầu tiên, chúng ta khởi tạo các biến: hashInt là đại diện số nguyên của hash; nonce là bộ đếm. Tiếp theo, chúng ta chạy một vòng lặp "vô hạn": nó giới hạn bởi maxNonce, nó bằng với math.MaxInt64; điều này được thực hiện để tránh sự tràn lan của nonce. Mặc dù độ khó trong việc thực hiện PoW của chúng ta là quá thấp để việc chống tràn, nhưng tốt hơn hết là kiểm tra việc này.

Trong vòng lặp chúng ta:

1. Chuẩn bị dữ liệu.
2. Hash nó với SHA-256.
3. Chuyển đổi mã hash sang big integer.
4. So sánh số nguyên với target.

Dễ dàng như đã được giải thích trước đó. Bây giờ chúng ta có thể loại bỏ method SetHash của Block và modify hàm NewBlock:

func NewBlock(data string, prevBlockHash []byte) *Block {
	block := &Block{time.Now().Unix(), []byte(data), prevBlockHash, []byte{}, 0}
	pow := NewProofOfWork(block)
	nonce, hash := pow.Run()

	block.Hash = hash[:]
	block.Nonce = nonce

	return block
}

Ở đây bạn có thể thấy rằng nonce được lưu như một thuộc tính Block. Điều này là cần thiết vì nonce là cần thiết để xác minh một bằng chứng. Cấu trúc Block bây giờ trông như sau:

type Block struct {
	Timestamp     int64
	Data          []byte
	PrevBlockHash []byte
	Hash          []byte
	Nonce         int
}

Ok! Giờ hãy chạy chương trình để xem mọi thứ có hoạt động tốt ko nào:

Mining the block containing "Genesis Block"
00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1

Mining the block containing "Send 1 BTC to Ivan"
00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804

Mining the block containing "Send 2 more BTC to Ivan"
000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe

Prev. hash:
Data: Genesis Block
Hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1

Prev. hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1
Data: Send 1 BTC to Ivan
Hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804

Prev. hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804
Data: Send 2 more BTC to Ivan
Hash: 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe

Yay! Bạn có thể thấy rằng mỗi hash bây giờ bắt đầu với 3 zero bytes, và phải mất một thời gian để có được những mã hash.

Còn có một điều nữa để làm: hãy làm cho nó có thể thể xác minh bằng chứng của công việc.

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
}

Và đây là nơi chúng ta cần lưu nonce.

Hãy kiểm tra lại một lần nữa rằng mọi thứ đều ok:

func main() {
	...

	for _, block := range bc.blocks {
		...
		pow := NewProofOfWork(block)
		fmt.Printf("PoW: %s
", strconv.FormatBool(pow.Validate()))
		fmt.Println()
	}
}

Output:

...

Prev. hash:
Data: Genesis Block
Hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
PoW: true

Prev. hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
Data: Send 1 BTC to Ivan
Hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
PoW: true

Prev. hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
Data: Send 2 more BTC to Ivan
Hash: 000000e42afddf57a3daa11b43b2e0923f23e894f96d1f24bfd9b8d2d494c57a
PoW: true

Conclusion

Blockchain của chúng ta đang một bước gần hơn với kiến trúc thực tế của nó: việc bổ sung khối vào chuỗi giờ đòi hỏi khó khăn hơn, do đó mining là có thể. Nhưng nó vẫn thiếu một số tính năng quan trọng: cơ sở dữ liệu blockchain không liên tục, không có ví, địa chỉ, giao dịch, và không có cơ chế đồng thuận. Tất cả những điều này chúng ta sẽ thực hiện trong các bài viết sau.

Reference

1. https://jeiwan.cc/posts/building-blockchain-in-go-part-2/
2. Full source codes
3. Blockchain hashing algorithm
4. Proof of work
5. Hashcash