phần 1, bạn đọc đã được tìm hiểu các thông tin về Định nghĩa hàm Hash, tính chất, ứng dụng và một số bài toán thực hành. Ở phần tiếp theo, người viết sẽ cùng quý độc giả tìm hiểu thêm về con trỏ Hash và Blockchain – cấu trúc dữ liệu xây dựng trên khái niệm này.

Con trỏ Hash

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 (Hash pointers) 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 được dùng để xây dựng các cấu trúc dữ liệu tương tự các cấu trúc dữ diệu được xây dựng bằng con trỏ thường, 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 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

Cấu trúc linked list thông thường 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 và một con trỏ chỉ về khối đằng trước trong chuỗi. Khi sử dụng con trỏ hash thay cho con trỏ thông thường để xây dựng cấu trúc dữ liệu linked list, cấu trúc mới này được gọi là blockchain.

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, ngoài việc có thể trỏ tới block trước đó, mỗi block còn có thể lưu giá trị digest (giá trị hash) của khối được trỏ tới. Thông qua việc kiểm tra giá trị hash, ta có thể nhận dạng khối được trở tới có bị thay đổi hay không. 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, đồng thời vẫn kiểm soát được nội dung của các khối còn lại không bị thay đổi.

Ví dụ, một người nào đó muốn thay đổi nội dung của dữ liệu của Blockchain ở một khối \(k\) 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 ở 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 tiên đưa ra khái niệm blockchain, đây cũng là một phát minh 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 để liên kết các block trong blockchain.

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

Trong chuỗi các block thuộc hệ thống blockchain, khối đầu tiên đượ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.

(Dữ liệu của mỗi block trong chuỗi blockchain của Bitcoin ghi lại các giao dịch tiền ảo của hệ thống Bitcoin; trong bài này chúng ta sẽ chưa đề cập đến nội dung này.)

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

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à block đầu tiên.

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 chỉ về block đầu tiên. Giá trị của trường này ở đây là:

Như định nghĩa phía trên thì con trỏ hash cần làm 2 việc gồm: trỏ tới khối dữ liệu liền trước và chứa giá trị hash của khối dữ liệu.

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ị:

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, 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. (Cấu trúc cây Markle sẽ được người viết giới thiệu tới độc giả ở những bài viết kì sau)

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
hashMerkleRoot 2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3 32 2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3
Time 1305998791 4 4DD7F5C7
Bits 440711666 4 1A44B9F2
Nonce 2504433986 4 9546A142

 

Đ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.

Trần Tuấn Anh – FPT HO

Tin liên quan: