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.

Blockchain 01: Hàm Hash và Ứng dụng

Đây là bài đầu tiên trong chuỗi bài về Blockchain, nội dung tôi dịch và tổng hợp từ các nguồn để cung cấp kiến thức cơ bản để tìm hiểu về công nghệ blockchain. Nội dung chủ yếu lấy từ 2 cuốn sách:

Bài viết này sẽ giới thiệu về hàm hash (hash function) và ứng dụng của nó trong công nghệ blockchain. Hàm hash là công cụ toán học quan trọng được xử dụng trong nhiều lĩnh vực, trong bài này không đi sâu về khía cạnh toán học mà cung cấp đủ thông tin và kiến thức về hash function để tìm hiểu về bitcoin và công nghệ blockchain.

Định nghĩa

Hàm hash là một hàm số toán học (mathematical function) ánh xạ (mapping) từ dữ liệu (data) có độ dài bất kỳ (arbitrary size) thành dữ liệu có độ dài cố định (fixed size). Các tính chất của hàm hash:

  • Tập nguồn (input) là một chuỗi ký tự có độ dài bất kỳ.
  • hàm hash trả lại kết quả (ouput) là một chuỗi có độ dài cố định. Trong văn cảnh bitcoin thì ta mặc định tập đích là chuỗi 256 bit.
  • Hàm này có thể thực hiện nhanh, nói chính xác là khi tính giá trị của hàm hash trên một chuỗi n-bit thì độ phức tạp của thuật toán là O(n). Hiểu nôm na là với mỗi một chuỗi (input string) đầu vào thì ta có thể tính ra kết quả trong khoản thời gian ngắn.

Kết quả của hàm hash trong tiếng Anh được gọi là giá trị hash (hash values), mã hash (hash codes), digests, hoặc đơn giản là hash. Đây là những tính chất của một hàm hash bình thường. Một ứng dụng của hàm hash thường gặp là để xây dựng cấu trúc dữ liệu (data structure) Hashtable.

Tuy vậy, trong bitcoin người ta sử dụng hàm hash mật mã (cryptographic hash functions). Để một hàm hash có tính bảo mật (cryptographically secure), hàm đó phải có thêm các tính chất sau:

Tính chất 1. Không va chạm (Collision resistance).

Hàm hash được gọi là không va chạm (collision resistant) khi không thể tìm được 2 chuỗi đầu vào (input) x và  y khác nhau,   x \neq y nhưng lại có giá trị hash bắng nhau H(x) = H(y). Chú ý là tính chất này nói là không tìm được va chạm, chứ chắc chắn tồn tại va chạm. Vì đối với hàm hash f: X \rightarrow Y, thì tập nguồn X lớn hơn tập đích Y (trong trường hợp này thì tập nguồn là vô hạn, còn tập đích là hữu hạn).

Lưu ý là không có hàm hash nào được chứng minh (proven) là có tính chất không va chạm, các hàm hash mật mã được dùng trên thực tế là những hàm mà chưa tìm được phương pháp tính va chạm một cách hiệu quả.

Tính chất 2. Dấu một chiều (hiding one-way)

Tính chất này có nghĩa là khi đưa ra kết quả  y của hàm hash H(x) = y thì không có cách nào tìm ra giá trị đầu vào x.

Trên thực tế để đạt được tính chất này khi tính hàm hash của biến đầu vào x người ta sẽ đính thêm một biến đầu vào bí mật (secret value) r được chọn ngẫu nhiên để khi đưa ra H(r || x) thì không thể nào tìm được giá trị x.

Tính chất 3.  Thân thiện với Puzzle (puzzle-friendliness).

Một hàm hash H được gọi là thân thiện với puzzle nếu với mọi giá trị n-bit đầu ra (output) y, khi chọn k từ một phân phối với min-entropy cao (hiểu là một giá trị ngẫu nhiên), thì không thể tìm dược giá trị x để H(k || x) = y trong thời gian ít hơn 2^{n} .

Giải thích một các đơn giản thì tính chất puzzle-friendliness có nghĩa là:

  • Cho: một giá trị z và một giá trị được chọn ngẫu nhiên r
  • Thì: rất khó tìm được giá trị x để mà H(r || x) = z (khó nhưng mà nó tồn tại và sẽ tìm được)

Ba tính chất trên có liên quan, nhưng hơi na ná như nhau, để phân biệt bạn có thể đọc thêm ở đây: https://stackoverflow.com/a/43360135/8315748

Tính chất puzzle-friendliness này khác với tính chất collision-free (không va chạm) vì kể cả khi ta có thuật toán tìm được va chạm tức là tìm được một giá trị y để mà H(y) = z thì việc yêu cầu (contraints) là giá trị  y phải bắt đầu với r khiến y không phải là lời giải cho bài toán puzzle-friendliness.

Tính chất puzzle-friendliness này cũng khác với tính chất dấu-một-chiều (hiding one-way function) theo cùng lý do là kể cả khi ta có thuật toán giải được hàm một chiều tức là tìm được một giá trị y để mà H(y) = z thì giá trị y này cũng chưa chắc là lời giải cho bài toán puzzle-friendliness vì yêu cầu y phải bắt đầu với r ( y = r || x ).

Ứng dụng

Tóm tắt văn bản (message digests) – ứng dụng của tính chất 1.

Giá trị của hàm hash mật mã được dùng như một bản tóm tắt chính xác (unambiguous) của văn bản gốc; đây là giải pháp rất hiệu quả để ghi nhớ những nội dung đã thấy và nhận ra (kiểm tra) lại sau này.

Khi ta biết hàm hash H có tính chất không va chạm (collision-resistance), thì nếu ta thấy 2 giá trị hash H(x)H(y) có giá trị khác nhau, thì  có thể kết luận là giá trị đầu vào xy là khác nhau. Với tính chất này ta có thể dùng giá trị hash đầu ra như là bản tóm tắt văn bản (message digests) của băn bản gốc.

Ví dụ bạn update một file dữ liệu rất lớn lên dịch vụ lưu trữ, sau này khi bạn download file đó xuống nhưng muốn chắc chắn là nội dung của file này đúng y nguyên như file bạn upload lên hồi trước. Hàm hash với tính chất không va chạm giúp làm việc này rất hiệu quả: bạn chỉ phải lưu lại giá trị hash (256 bits) của file gốc đó (vài gigabytes). Sau này khi download file xuống bạn chỉ phải so sánh xem 2 giá trị hash có giống nhau hay không; với giải pháp này ta không phải lưu lại cả file gốc rất lớn để kiểm tra nội dung.

Cam kết số  (commitments) – ứng dụng của tính chất 2.

Cam kết số giống như việc bạn ghi một nội dung vào một tờ giấy vào cho vào phong bì, sau đó bạn dán phong bì lại và đặt phong bì đó ra bàn cho mọi người xem. Như vậy bạn đã cam kết với mọi người về nội dung trong phong bì, nhưng mọi người chưa biết nội dung đó là gì. Lúc sau bạn có thể mở phong bì ra để cho mọi người thấy nội dung mà bạn cam kết.

Việc cam kết số này có thể được thực hiện bằng hàm hash mật mã như sau. Với mỗi một thông điệp nội dung msg, ta chọn một giá trị nonce ngẫu nhiên 256-bit. Sau đó ta tính giá trị hash com = H(nonce || msg) và dùng giá trị com này như cam kết số.

Khi một người biết được giá trí com này thì không thể nào đoán được nội dung gốc msg (mà ta đã cam kết) do tính chất dấu một chiều (hiding) của hàm hash. Tuy vậy, sau này khi ta đưa ra giá trị của nội dung gốc msg (cùng với giá trị nonce) thì ta vẫn có thể chứng minh được nội dung msg chính là nội dung mà ta đã cam kết số bằng giá trị com. Điều này được đảm bảo do tính chất không va chạm của hàm hash, không có cách nào tìm được giá trị msg' khác với msg để mà H(nonce || msg) = H(nonce' || msg').

Tìm kiếm puzzle – ứng dụng tính chất 3.

Áp dụng tính chất 3, chúng ta có thể xây dựng bài toán tìm kiếm như sau:

  • Cho một hàm hash mật mã H
  • Cho một giá trị id được chọn ngẫu nhiên
  • Cho một tập đích Y

Bài toán ở đây là tìm một giá trị x sao cho H(id || x) in Y

Ý tưởng của bài toán tìm kiếm puzzle ở trên là: nếu hàm H có tập kết quả là n-bit, thì nó có thể có thể có 2^n giá trị khác nhau, tập đích Y thường là tập rất bé so với tập tất cả các giá trị kết quả. Bởi vậy kích thước của tập Y này sẽ xác định độ khó của bài toàn tìm kiếm giá trị x.

Ứng dụng này được dùng trong bitcoin, thuật ngữ của bitcoin gọi việc này là mining, có liên quan đến khái niệm prove-of-work. Chúng ta sẽ quay lại khái niệm này trong các bài sau.

Thực hành

SHA-256

SHA-256 là một thành viên trong họ hàm hash SHA-2 được thiết kế bởi NSA (Cục An ninh Quốc Gia Hoa Kỳ). SHA-256 nhận vào một văn bản text bất kỳ và đưa ra giá trị hash có độ dài 256 bit.  là một hàm hash được dùng thông dụng, bitcoin sử dụng hàm này.

Bạn có thể chạy đoạn code Python sau để tính ra giá trị hash của một chuỗi ký tự theo chuẩn SHA256.

$ python
Python 2.7.1
>>> import hashlib
>>> print hashlib.sha256("I am Satoshi Nakamoto").hexdigest()
5d7c7ba21cbbcd75d14800b100252d5b428e5b1213d27c385bc141ca6b47989e

Trong mật mã (cryptography) , thuật ngữ nonce được dùng để chỉ đến một giá trị chỉ được sử dụng một lần.

# example of iterating a nonce in a hashing algorithm's input
import hashlib
text = "I am Satoshi Nakamoto"
# iterate nonce from 0 to 19
for nonce in xrange(20):
   # add the nonce to the end of the text
   input = text + str(nonce)
   # calculate the SHA-256 hash of the input (text+nonce)
   hash = hashlib.sha256(input).hexdigest()
   # show the input and hash result
   print input, '=>', hash

Trong đoạn code trên, giá trị nonce được dùng dùng mới nội dung của một thông điệp msg để tạo ra các giá trị hash SHA256 khác nhau của thông điệp đó.

Bạn cũng có thể dùng tool CyberChef để thử nhanh các hàm hash.

https://gchq.github.io/CyberChef/#recipe=%5B%7B%22op%22%3A%22SHA256%22%2C%22args%22%3A%5B%5D%7D%5D&input=SSBhbSBTYXRvc2hpIE5ha2Ftb3Rv

Trong hệ thống Ethereum, người ta dùng hệ thống hàm hash mới hơn  KECCAK-256, họ hàm hash mới này được cho là ưu việt hơn: nhanh hơn và tính bảo mật tốt hơn.

Hàm hash được sử dụng khắp nơi trong công nghệ blockchain, nên ta cần làm quen với khái niệm và tính chất cơ bản của hash đồng thời sử dụng các công cụ hash để thao tác.