Xây dựng blockchain đơn giản với golang. P3 - Persistent + Proof Of Work
Blockchain
23
Bitcoin
12
White

Trần Mỹ viết ngày 11/02/2018

Xin chào mọi người.

Đây là phần 3 trong bài viết của mình về xây dựng blockchain với ngôn ngữ Go.

Các bạn có thể có thể tham khảo 2 phần trước của mình ở đây :
Phần 1 : Cấu trúc cơ bản
Phần 2 : CLI + Network

Ở phần trước, mình đã xây dựng 1 cấu trúc mạng đơn giản để có thể mô hình hóa các tính chất của blockchain rõ ràng hơn, và CLI giúp chương trình trở nên dễ mở rộng khi tương tác với người dùng hơn.

Ở phần này mình sẽ xây dựng 2 tính chất của blockchain về :

  • Persistent (Lưu trữ dữ liệu): Giả sử ta là 1 node trong mạng lưới, ta sẽ cần tải blockchain của mạng lưới về của mình để xử lý. Về lý thuyết thì ta có nhiều lựa chọn như lưu in memory, lưu vào file, lưu vào database (mà thực chất cũng là file) ... Ta sẽ xem xét về cách lưu trữ phù hợp với đối tượng là blockchain.
  • Proof of Work - PoW (Bằng chứng công việc): Giả sử blockchain của ta sẽ cần để lưu các transactions của người dùng. Nếu việc thêm dữ liệu vào blockchain cũng đơn giản như việc gọi lệnh INSERT để thêm record vào 1 table blocks thì với tính chất công khai của mạng lưới thì nó sẽ đầy lên rất nhanh chóng. Ta cần 1 cơ chế để đảm bảo dữ liệu không sinh ra nhiều, và các block sinh ra mang theo dữ liệu có ý nghĩa chứ không phải spam. PoW là 1 giải pháp có thể giải quyết được vấn đề này, mình sẽ trình bày cụ thể hơn khi đi vào chi tiết.

(Note: Về cách viết thì thường thì sẽ có 1 bài lý thuyết riêng, và bài mình tập trung vào thực hành hơn. Nhưng mình cũng không đủ khả năng viết 1 bài lý thuyết đầy đủ + các bạn đọc bài này có thể đa số cũng nhập môn lý thuyết blockchain như mình, nên bài viết mình kết hợp cả lý thuyết + thực hành, cấu trúc có thể hơi lộn xộn các bạn thông cảm)

1. Persistent - Lưu trữ dữ liệu

Đầu tiên ta sẽ tham khảo về cách lưu trữ dữ liệu của đồng tiền ảo đầu tiên trên thế giới là Bitcoin.

1.1. Bitcoin

1.1.1. Kích cỡ blockchain

Xét về kích thước, ta có thể tìm hiểu về kích cỡ dung lượng blockchain của bitcoin tại đây
alt text

Hiện tại kích cỡ blockchain của bitcoin tại thời điểm bài viết là ~15GB, mình nghĩ đây không phải là mức dung lượng lớn nếu so với các database của các dịch vụ nổi tiếng, ta hoàn toàn có thể lưu nó trong máy tính cá nhân, thậm chí là usb, và không phải lo lắng về việc thiếu dung lượng trong nhiều năm.

Với kích thước như vậy và tính chất công khai của mạng phân tán thì lưu in memory sẽ không phù hợp, vậy nên ta sẽ có thể chọn lưu với file hoặc database.

1.1.2. Cách lưu trữ

Các bạn có thể tham khảo về cách lưu trữ của bitcoin tại đây. Mình tóm tắt lại cấu trúc lưu trữ của blockchain như sau :

  1. blocks/blk*.dat: Tập hợp các file chứa dữ liệu các blocks chính.
  2. blocks/index/*: Đây là 1 LevelDB chứa metadata index đến các file dữ liệu block ở trên, giúp truy xuất nhanh hơn.
  3. chainstate/*: Cũng là LevelDB nhưng chứa 1 phiên bản thu gọn của blockchain, chỉ bao gồm các unspend transaction. Unspend transaction là dữ liệu được truy xuất rất thường xuyên khi ta tạo 1 giao dịch, mình sẽ đề cập đến cụ thể hơn ở bài viết về phần Transaction.
  4. blocks/rev*.dat: Chứa dữ liệu phục vụ cho việc undo blockchain khi cần thiết.

Các bạn có thể thấy tổ chức lưu trữ của bitcoin cũng khá phức tạp và nhiều thành phần. Mặc dù lý thuyết blockchain là "chain of blocks" cho phép ta có 1 cách lưu đơn giản nhất đó là lưu từng block một, block này ánh xạ đến block kia như 1 linked list. Nhưng thực tế ta sẽ cần điều chỉnh, ví dụ như xây dựng cơ chế index như trên để truy vấn nhanh chóng và hiệu quả hơn.

Với mục đích giả lập đơn giản, mình sẽ không triển khai hết 4 thành phần trên, và sẽ cố gắng xây dựng 1 và 2, gộp lại thành 1 DB chung.

Tiếp theo mình sẽ trình bày cụ thể hơn ở phần xây dựng dưới đây.

1.2. Xây dựng

1.2.1. Chọn Database

Để đơn giản, mình chọn lưu trữ dưới dạng DB. Mình chọn sử dụng BoltDB với số ưu điểm như sau:

  • Dạng lưu trữ key-value: BoltDB cũng là dạng lưu trữ key-value, cũng giống với blockchain của bitcoin mình trình bày ở trên là LevelDB. Ta sẽ có lợi thế là dữ liệu không phải quan tâm quá nhiều vào config liên quan đến DBMS như charset, type... trong SQL RDBMS, do đó sẽ dễ đảm bảo thống nhất dữ liệu giữa các node, và dễ dàng cho việc serialize (cùng kiểu là []byte), đổi lại ta sẽ cần chú ý trong việc chuyển đổi dữ liệu.
  • Nhẹ, dễ cài đặt : Mình sử dụng thử và thấy dùng rất dễ dàng, không cần cấu hình nhiều, phù hợp với mục đích giả lập đơn giản của bài viết.

Các bạn có thể tham khảo thêm bài viết trình bày cụ thể hơn tại đây

Ngoài ra các bạn có thể có 1 số lựa chọn khác như :

  • LevelDB : Mình nghĩ dùng sẽ dễ tham khảo đến các implement sâu của bitcoin.
  • Rocksdb : Là 1 DBMS được đánh giá cao về hiệu năng do facebook phát triển. Cài đặt ban đầu cho golang có thể sẽ mất công 1 chút xíu.

1.2.2. Cấu trúc

Ở các các phần trước mình implement blockchain là 1 mảng lưu trong memory, ở phần này mình sẽ thay bằng con trỏ đến DB.

type Blockchain struct {
    db *bolt.DB
}

Ta sẽ lưu các blocks dưới dạng key-value như sau :

Key Value Ví dụ
32-byte block-hash Dữ liệu block đã được serialize 00007d4c0...f494 --> {dữ liệu block}
l giá trị hash của block mới nhất l --> 00007d4c0...f494

Với nguyên tắc cấu trúc dữ liệu của linked list, khi ta biết node đầu tiên, và vì nó chứa con trỏ đến node tiếp theo, ta có thể duyệt được đến hết list. Cũng tương tự như vậy, 2 loại key này là đủ để ta có thể duyệt hết các blocks, nên mình sẽ chỉ lưu 2 loại key này.

Mình xây dựng thêm 1 cấu trúc mới là BlockchainIterator hỗ trợ cho việc duyệt mảng :

type BlockchainIterator struct {
    currentHash []byte
    bc          *Blockchain
}
  • currentHash là con trỏ đến block hiện tại khi duyệt list các block.
  • bc chứa blockchain để duyệt tham chiếu xử lý.
func (i *BlockchainIterator) next() *Block {
    var block *Block

    err := i.bc.db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte(blocksBucketName))
        encodedBlock := b.Get(i.currentHash)
        block = deserializeBlock(encodedBlock)

        return nil
    })

    if err != nil {
        Error.Panic(err)
    }

    i.currentHash = block.Header.PrevBlockHash

    return block
}

next đưa ta đến block tiếp theo tình từ vị trí hiện tại, khi duyệt mảng ta sẽ gọi next cho đến khi biết được đó là block cuối cùng trong list (genesis block)

Với việc thay đổi cấu trúc lưu trữ, đa số các xử lý ở các phần trước của mình sẽ bị sửa lại. Nhưng logic thì mình không thay đổi nhiều, các bạn có thể tham khảo chi tiết tại source code.

1 số logic xử lý bị ảnh hưởng do thay đổi cấu trúc lưu trữ mình sẽ trình bày ở phần cuối cùng.

2. Proof of Work - Bằng chứng công việc

2.1. Lý thuyết

Như mình đã nói ở phần đầu, chúng ta sẽ cần 1 cơ chế để đảm bảo rằng các block sinh ra 1 cách ổn định và trật tự, và PoW là 1 cơ chế để giải quyết vấn đề này. (Ngoài ra bạn có thể tham khảo Proof of Stake - là 1 giải pháp thậm chí tốt hơn PoW)

Bạn có thể tham khảo thêm về PoW tại đây. Trong bài viết này mình sẽ trình bày qua.

PoW là cơ chế được sinh ra trước bitcoin với mục đích ta hiểu 1 cách đơn giản là chống DDOS và spam.

Xét 1 case đơn giản, giả sử ta có 1 hòm thư điện tử. 1 hacker muốn quấy rối hòm thư của ta bằng cách viết 1 chương trình gửi spam 20000 email vào hòm thư mỗi giây, hòm thư của ta sớm muộn sẽ thành 1 thùng rác.

PoW là cơ chế yêu cầu rằng các email gửi đến phải thỏa mãn 1 điều kiện nhất định thì server mới chấp nhận rằng nó hợp lệ và không phải là spam. Và điều kiện này đồng nghĩa với việc rằng hacker sẽ phải mất 1s để giải 1 bài toán khó thỏa mãn điều kiện đó trước khi gửi đi, và server chỉ cần 0.0001s để xác nhận rằng email đó thỏa mãn điều kiện.

Điều này dẫn đến hệ quả rằng hacker sẽ phải tốn cost và thời gian để có thể spam - họ sẽ phải tính toán lại chi phí bỏ ra để tiếp tục thực hiện. Trong khi đó server hạn chế được số email gửi đến trong 1s từ 20000 xuống 1 hoặc mất 2s để check bỏ đi 19999 email spam.

alt text

Quay trở lại blockchain, cũng trường hợp tương tự sẽ xảy ra khi 1 node spam broadcast các block đến network. Có vẻ như rất nhiều vấn đề có thể xảy ra khi mà số lượng block tăng 1 cách không kiểm soát vào mạng.

Với PoW, ta sẽ xây dựng cơ chế sau để :

  1. Thời gian trung bình sinh ra 1 block nằm trong khoảng chấp nhận được (Không quá nhanh cũng không quá lâu)
  2. Độ khó bài toán mà mỗi node cần giải tỉ lệ thuận với thời gian block được sinh ra.
  3. Thời gian để kiểm tra lời giải của bài toán (validation) là rất nhanh, và cost cho việc validation là rất ít.
  4. Hệ thống có khả năng tự điều chỉnh đề thời gian sinh ra block xấp xỉ hằng số.

Mình sẽ chỉ implement 1,2,3 trong phần này, 4 hơi phức tạp vì có thể sẽ cần cơ chế version nên nếu có thời gian mình sẽ bổ sung sau.

Bài toán

Có lẽ sẽ có rất nhiều cách để chọn bài toán, bài toán mà bitcoin chọn đó là giải 1 bất phương trình : Tìm x để f(x) < M. với M là hằng số cho trước
(Và do đó M càng lớn thì bài toán càng dễ và ngược lại)

Các bạn có thể tham khảo cụ thể hơn tại đây

Vậy nếu M là số 1 biểu diễn bằng 256 bit, và có giá trị bằng $2^{240}$ thì ta sẽ có M ở dạng nhị phân (Big Endien) như sau :
0000 0000 0000 0001 0000 0000 .... 0000 (1 ở index số 240 tính từ 0, ngoài ra là 0)

Và coi dữ liệu của ta là D, và ta chọn hàm :
f(x) = sha256(D + x)

Và bởi vì tính chất toán học nên sha256 sẽ không thể giải ngược để tìm ra x, chúng ta chỉ có thể tìm nó bằng cách chọn x từ 0 -> $\infty$, thay lần lượt vào f(x) rồi kiểm tra bất phương trình nghiệm đúng không.

Mình sẽ dùng hàm sha256() như trên để làm bài toán cho chương trình của chúng ta.

2.2. Xây dựng

Mình tham khảo và thêm 1 cấu trúc mới là ProofOfWork. Cấu trúc này thực hiện việc giải bài toán và kiểm tra lời giải.

2.2.1. Giải toán.

proofofwork.go

// ProofOfWork represents a proof-of-work
type ProofOfWork struct {
    block  *Block
    target *big.Int
}
  • block : block tham chiếu đến để thực hiện xử lý
  • target : mục tiêu cho lời giải của bài toán (Ví dụ $2^{240}$)
func newProofOfWork(b *Block) *ProofOfWork {
    target := big.NewInt(1)
    target.Lsh(target, uint(256-difficulty))

    pow := &ProofOfWork{b, target}
    return pow
}

newProofOfWork khởi tạo 1 PoW mới với block được gán, khởi tạo target = $2^{240}$

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

    return data
}

Dữ liệu D block của mình đó là :

  • PrevBlockHash : hash của block trước đó
  • Data : dữ liệu của block
  • Timestamp : thời gian block được khởi tạo
  • nonce : tham số truyền vào - giá trị x mà ta cần tìm

Ta sẽ nối 4 phần tử này thành 1 byte slice.
prepareData thực hiện việc chuẩn bị dữ liệu trước khi chạy hàm f(x) : run

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

    Info.Println("Mining...")
    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.Printf("\n\n")
    return nonce, hash[:]
}

run là 1 vòng lặp với x chạy từ 0 --> $2^{63} -1 $

Bài toán được giải khi giá trị nonce thỏa mãn f(x) được tìm thấy. Giá trị hash = sha256.Sum256(data) tính được khi đó cũng chính là giá trị hash chọn cho block.

Đến đây, việc giải bài toán kết thúc.

2.2.2. Kiểm tra lời giải (Validation)

proofOfWork.go

func (pow *ProofOfWork) validate() bool {
    var hashInt big.Int

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

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

    return isValid
}

Giả sử ta ở 1 node B và nhận được 1 block gửi từ A. Ta cần kiểm tra xem rằng A có thỏa mãn bài toán (không phải là block spam) không. Khi đó ta chỉ cần gọi pow.validate(), không như việc phải chạy vòng lặp để tính toán lời giản, kiểm tra lời giải chỉ cần chạy lại hàm và kiểm tra nghiệm đúng của phương trình nên rất nhanh.

Phần trình bày về PoW của mình kết thúc tại đây.

Tiếp theo trước khi kết thúc bài viết, mình trình bày nốt về 1 số thay đổi khác về chương trình so với các phần trước.

3. Những thay đổi khác.

3.1. Thêm block header

Ở phần trước mình chỉ có 1 struct là Block thể hiện dữ liệu cho 1 block. Ở phần này mình có thêm cải thiện cơ chế đồng bộ block giữa các node, đó là các node sẽ gửi các header cho nhau để kiểm tra xem block của mình có khớp với của đối phương không, do đó mình tách ra thành BlockHeader

type Block struct {
    Data   []byte `json:"Data"`
    Header Header `json:"BlockHeader"`
}

/*Header of block */
type Header struct {
    Timestamp     int64  `json:"Timestamp"`
    Hash          []byte `json:"Hash"`
    PrevBlockHash []byte `json:"PrevBlockHash"`
    Height        int    `json:"Height"`
    Nonce         int    `json:"Nonce"`
}

3.2. Thêm cơ chế kiểm tra đồng bộ block giữa các node.

Khi chạy chương trình, các node có thêm cơ chế kiếm tra xem blockchain ở local của mình có đồng bộ với node gần nhất không.
Cụ thể các bạn có thể tham khảo source code.

Hết!

4. Tổng kết

Ở phần này mình đã mô phỏng được 1 cách đơn giản cơ chế lưu trữ và PoW của 1 blockchain điển hình là bitcoin.
Ở phần tiếp theo, mình dự định sẽ implement cơ chế address và private - public key, làm nền tảng để chúng ta có thể thêm vào 1 trong những thành phần làm nên giá trị của bitcoin là transaction.

Source code : https://github.com/mytv1/blockchain_go/tree/part_3

Tham khảo

https://jeiwan.cc/posts/building-blockchain-in-go-part-2/
https://jeiwan.cc/posts/building-blockchain-in-go-part-3/
https://github.com/ethereum/go-ethereum

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Trần Mỹ

9 bài viết.
85 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
38 9
XIn chào mọi người. Thời gian gần đây mình có tìm hiểu về blockchain và golang. Mình viết bài viết này với mục đích chia sẻ và tổng hợp những kiến...
Trần Mỹ viết 7 tháng trước
38 9
White
28 5
Xin chào mọi người. Thời gian ngắn gần đây mình có tìm hiểu 1 chút về Bitcoin và Blockchain, và để củng cố kiến thức thu nạp được mình quyết định ...
Trần Mỹ viết 9 tháng trước
28 5
White
15 1
Xin chào mọi người. Đây là phần 2 trong bài viết về xây dựng blockchain đơn giản với golang của mình. Ở (Link) mình đã trình bày về việc xây dựng...
Trần Mỹ viết 6 tháng trước
15 1
Bài viết liên quan
White
11 5
Tạm xóa
Giaosucan viết 5 tháng trước
11 5
White
10 2
Xin chào mọi người. Đây là phần 4 trong bài viết của mình về xây dựng 1 blockchain đơn giản với ngôn ngữ Go. Các bạn có thể có thể tham khảo 3 ph...
Trần Mỹ viết 5 tháng trước
10 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
9 bài viết.
85 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!