Blockchain 01: Hàm Băm (Hash Function) và Ứng dụng
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 bitcoin vào 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) với những tính chất sau:
- 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à $latex 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.
Đây là những tính chất của một hàm hash nói chung, ví dụ người ta dùng hàm hash để xây dựng cấu trúc dữ liệu (data structure) Hashtable. Tuy vậy, trong bitcoin chúng 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) $latex x$ và $latex y$ khác nhau, $latex x \neq y$ nhưng lại có giá trị hash bắng nhau $latex 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 $latex f: X \rightarrow Y$, thì tập nguồn $latex X$ lớn hơn tập đích $latex 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ả $latex y$ của hàm hash $latex y =H(x)$ thì không có cách nào tìm ra giá trị đầu vào $latex 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 $latex x$ người ta sẽ đính thêm một biến đầu vào bí mật (secret value) $latex r$ được chọn ngẫu nhiên để khi đưa ra $latex H(r || x)$ thì không thể nào tìm được giá trị $latex x$.
Tính chất 3. Thân thiện với Puzzle.
Một hàm hash $latex 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) $latex y$, khi chọn $latex k$ từ một phân phối với high min-entropy, thì không thể tìm dược giá trị $latex x$ để $latex H(k || x) = y$ trong thời gian ít hơn $latex 2^{n}$ .
Ứng dụng
Tóm tắt văn bản (message digests) — ứng dụng của tính chất 1.
Khi ta biết hàm hash $latex H$ có tính chất không va chạm (collision-resistance), thì nếu ta thấy 2 giá trị hash $latex H(x)$ và $latex H(y)$ có giá trị khác nhau, thì có thể kết luận là giá trị đầu vào $latex x$ và $latex y$ 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.
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.
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 $latex msg$, ta chọn một giá trị $latex nonce$ ngẫu nhiên 256-bit. Sau đó ta tính giá trị hash $latex com = H(nonce || msg)$ và dùng giá trị $latex com$ này như cam kết số.
Khi một người biết được giá trí $latex com$ này thì không thể nào đoán được nội dung gốc $latex 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 $latex msg$ (cùng với giá trị $latex nonce$) thì ta vẫn có thể chứng minh được nội dung $latex msg$ chính là nội dung mà ta đã cam kết số bằng giá trị $latex 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ị $latex msg’$ khác với $latex msg$ để mà $latex H(nonce || msg) = H(nonce’ || msg’)$.
Tìm kiếm puzzle — ứng dụng tính chất 3.
dđ
Thực hành
SHA-256
$ python
Python 2.7.1
>>> import hashlib
>>> print hashlib.sha256("I am Satoshi Nakamoto").hexdigest()
5d7c7ba21cbbcd75d14800b100252d5b428e5b1213d27c385bc141ca6b47989eKeccak
