BLOCKCHAIN 01: HÀM HASH VÀ ỨNG DỤNG

Định nghĩa

Hàm hash là một hàm số toán học ánh xạ từ dữ liệu có độ dài bất kỳ thành dữ liệu có độ dài cố định.

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, mã hash, 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 Hashtable.

Tuy vậy, trong bitcoin người ta sử dụng hàm hash mật mã (cryptographic hash functions), hàm này 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 khi không thể tìm được 2 chuỗi đầu vào (input)  x và y khác nhau, x≠y nhưng lại có giá trị hash bằng nhau H(x)=H(y). (Chú ý: trên thực tế luôn tồn tại va chạm). Vì đối với hàm hash f:X→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 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 được giá trị x để H(k||x)=y trong thời gian ít hơn 2n .

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

 

So sánh 3 tính chất

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

Trong đó, tính chất puzzle-friendliness 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 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 – Ứng dụng của tính chất không va chạm

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.

Với tính chất không va chạm (collision-resistance), khi thấy 2 giá trị hash $latex H(x)$ và H(y) có giá trị khác nhau, thì có thể kết luận là giá trị đầu vào x và 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.

 

Cam kết số  – Ứng dụng tính chất dấu một chiều

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[latex] 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 msg (mà ta đã cam kết) do tính chất dấu một chiều 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 thân thiện với Puzzle

Á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)inY. Ý 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ó 2n 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.

 

Emanvn | Trần Tuấn Anh