Blockchain 02: Con trỏ hash và cấu trúc dữ liệu

Đây là bài tiếp theo phần 1 về hàm hash.

Con trỏ Hash

Trong bài này chúng ta sẽ tìm hiểu con trỏ hash (hash pointers) và cấu trúc dữ liệu xây dựng trên khái niệm này.  Con trỏ hash là một con trỏ thông thường (pointers) nhưng có kèm theo giá trị hash của nội dung được trỏ tới.

Con trỏ hash vừa trỏ đến dữ liệu vừa lưu giá trị hash (digest) của dữ liệu đó.

Con trỏ hash được dùng để xây dựng các cấu trúc dữ liệu (data structures) tương tự các cẫu trúc dữ diệu được xây dựng bằng con trỏ thường (regular pointers), ví dụ như linked list hoặc cây nhị phân (binary search tree). Với giá trị hash của dữ liệu được trỏ tới, con trỏ hash giúp ta kiểm tra (verify) rằng nội dung của thông tin không bị thay đổi.

Singly-linked-list.svg
Cấu trúc dữ liệu Linked List xây dựng bằng con trỏ (pointer)

Blockchain

Khi chúng ta sử dụng con trỏ hash (hash pointers) thay cho con trỏ thông thường để xây dựng cấu trúc dữ liệu linked list, thì cấu trúc mới này được gọi là blockchain.  Ở cấu trúc linked list thông thường thì bao gồm một chuỗi các khối (block), mỗi khối này sẽ bao gồm dữ liệu (data) và một con trỏ (pointers) chỉ về khối đằng trước trong chuỗi; đối với cấu trúc blockchain thì con trỏ này được thay bằng con trỏ hash (hash pointers).

Blockchain là cấu trúc dữ liệu Linked List nhưng dùng con trỏ hash (thay cho con trỏ bình thường)

Với blockchain, thì ở mỗi block sẽ không chỉ trỏ tới block trước đó mà còn lưu giá trị digest (giá trị hash) của khối được trỏ tới, dùng giá trị hash này ta có thể kiểm tra nội dung của khối được trỏ tới không bị thay đổi.

Với cấu trúc blockchain như vậy cho phép chúng ta chỉ cần lưu giá trị của con trỏ chỉ tới khối cuối cùng (head of the list), nhưng vẫn chắc chắn được là nội dung của cả blockchain (các khối còn lại) là không bị thay đổi. Ví dụ, một người nào đó muốn thay đổi nội dung dữ liệu của blockchain ở một khối k nào đó trong danh sách; vì nội dung ở khối k này bị thay đổi, con trỏ hash của khối k+1 sẽ không còn đúng. Lúc này khi ta tính giá trị hash của nội dung khối k, thì giá trị này sẽ không giống như giá trị hash được lưu ở con trỏ hash (hash pointer) ở khối sau đó là khối k+1. Để không bị phát hiện, người muốn thay đổi nội dung phải tiếp tục thay đổi nội dung dữ liệu của khối k+1, nhưng việc này sẽ dẫn đến chuyện giá trị con trỏ hash ở khối k+2 không còn chính xác; tiếp tục như vậy sẽ dẫn đến việc phải thay đổi nội dung ở khối cuối cùng. Nhưng chúng ta lưu trữ giá trị của khối này, nên sẽ phát hiện ra sự thay đổi đó.

Thực hành: con trỏ hash trong Bitcoin

Bitcoin là hệ thống đầu đưa ra khái niệm blockchain, đây cũng là một phát mình chính của hệ thống bitcoin. Blockchain trong  Bitcoin có nhiều đặc tính, nhưng trong bài này chúng ta tập trung vào khía cạnh sử dụng con trỏ hash (hash pointers) để liên kết các block trong blockchain.

Minh họa cấu trúc blockchain của hệ thống Bitcoin

Hệ thống blockchain của Bitcoin bao gồm một chuối các block, ở mỗi block bao gồm con trỏ hash chỉ tới khối trước nó và dữ liệu (data) của khối đó. Khối đầu tiên trong chuỗi này được gọi là genesis block. Khối này đươc đánh số là block #0, các khối tiếp theo được đánh số tăng dần.

Phần nội dung (data) của mỗi block trong chuỗi blockchain của Bitcoin ghi lại các giao dịch tiền ảo (digital currency) của hệ thống Bitcoin; trong bài này chúng ta sẽ chưa tìm hiểu cụ thể nội dung này vội.

Ví dụ đây là nội dung của block đầu tiên (#0) trong chuỗi blockchain của Bitcoin:

https://webbtc.com/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Chúng ta lưu ý chú ý là  trường Prev Block chính là con trỏ hash trong trường hợp này có giá trị bằng 0 vì đây là black đầu tiên; thuật ngữ bitcoin gọi block này là genesis block.

Còn đây là nội dung của block tiếp theo (#1) trong chuối blockchain của bitcoin:

https://webbtc.com/block/00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048

Trường Prev Block trong block này chính là con trỏ hash (hash pointer) chỉ về block đầu tiên (genesis block). Giá trị của trường này ở đây là:

000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Như định nghĩa phía trên thì con trỏ hash cần làm 2 việc: thứ nhất nó cần trỏ tới khỗi dữ liệu trước ở đây là block #0 của bitcoin, thứ 2 nó chứa giá trị  hash của block #0. Ở đây giá trị hash của block #0 được lưu ở trường (field) Prev Block trong block #1 làm cả 2 việc này 1 lúc. Bởi vì tính chất không va chạm của hàm hash mật mã, giá trị hash của một block trong blockchain được sử dụng như là định danh (identifier) của khối đó.

Lấy một ví dụ khác để ta hình dùng việc sử dụng giá trị hash value làm định danh (identifier) của một block. Giả sử ta download toàn bộ nội dung blockchain của bitcoin về máy local và lưu dữ liệu này trong một database nào đó; nếu chúng ta nhận được một hash pointer có giá trị:

00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

Chúng ta có thể tính giá trị hash của tất cả các block trong blockchain của bitcoin và so sánh với giá trị này, chúng ta sẽ thấy block #125552 sẽ có giá trị hash như trên. Nôi dung của block #12552 có thể được xem ở đây:

https://webbtc.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

Nhắc lại là một trong những tính chất quan trọng của blockchain: một khi nội dung được lưu vào blockchain thì nội dung đó không thể thay đổi. Nếu ta biết giá trị đúng của con trỏ hash tới khối cuối cùng của blockchain, thì ta có thể kiểm tra được nội dung của tât cả các khối trong blockchain là không bị sửa đổi.

Thực hành: tính giá trị hash của một block

Trong hệ thống Bitcoin, nội dung của một khối được chưa thành 2 phần: Header và Body. Trong phần Body của một khối chứa thông tin các giao dịch (transactions, ai chuyển tiền cho ai), còn phần Header chứa các trường sau:

Field Nội dung
Version Số version
hashPrevBlock 256-bit giá trị hash của khối trước đó
hashMerkleRoot 256-bit giá trị hash của các giao dịch trong block này
Time timestamp
Bits Độ khó của bài toán puzzle (liên quan đến vấn đề mining)
Nonce số 32-bit

Khi tính giá trị hash của một block thì người ta chỉ tính hash của phần header này, vì nội dung của phần body chứa các giao dịch đã được tóm tắt và đại diện bởi giá trị hash của cây Markle tại phần header này rồi. Chúng ta sẽ tìm hiểu cấu trúc cây Markle ở bài khác, ở đây chúng ta chỉ cần biết là nội dung của phần transactions đã được đại diện bởi giá trị hash Merkle, hashing giá trị này cũng coi như là hashing nội dung phần body.

Sau đây chúng ta sẽ tính lại giá trị hash của block #12552 của Bitcoin, nội dung của block này có thể xem ở đây:

https://webbtc.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d.json

Field Giá trị
Version 1
hashPrevBlock “00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81”
hashMerkleRoot “2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3”
Time 1305998791
Bits 440711666
Nonce 2504433986

Bitcoin sử dụng công thức sau để tính giá trị hash: SHA256(SHA256(Block_Header))

Theo như thông tin của hệ thống webbtc.com trả về thì block #12552 có giá trị hash là: 00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

Chúng ta sẽ thử tính lại giá trị hash của khối này theo công thức trên xem có đúng như giá trị của hệ thống trả lại không. Hàm hash SHA256 nhận giá trị đầu vào là một chuỗi các bytes (sequence of bytes) và trả lại kết quả là một chuỗi 32 bytes (256 bits). Vì vậy việc đầu tiên chúng ta cần biểu diễn các giá trị của Block_header dưới dạng chuỗi các bytes (hex). Bitcoin tính giá trị hex này theo format little endian.

Field Giá trị Độ dài bằng bytes Biểu diễn Hex Hex (little endian)
Version 1 4 00000001 01000000
hashPrevBlock 00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81 32 00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81
81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000
hashMerkleRoot 2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3 32 2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3
e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b
Time 1305998791 4 4DD7F5C7
c7f5d74d
Bits 440711666 4 1A44B9F2
f2b9441a
Nonce 2504433986 4 9546A142
42a14695

Đoạn code python sau sẽ tính giá trị hash theo dữ liệu chúng ta chuẩn bị ở bảng trên.

import hashlib
header_hex = ("01000000" +
 "81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
 "e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
 "c7f5d74d" +
 "f2b9441a" +
 "42a14695")
header_bin = header_hex.decode('hex')
hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

Kết quả cho thấy giá trị hash của block 125552 đúng như giá trị mà hệ thống webbtc trả lại.

Leave a Reply