Blockchain 01: Hàm Băm (Hash Function) 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:

  • http://bitcoinbook.cs.princeton.edu/
  • https://www.bitcoinbook.info/

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) á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 hay đượ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 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). Hàm này là một thuật toán toán học (mathematical algorithm) ánh xạ dữ liệu của một chuỗi ký tự bất kỳ thành một chuỗi có độ dài cố định, có tính chất là hàm một chiều (one-way function), tức là khi nhìn kết quả của hàm hash này thì không thể nào đoán được đầu vào (input) là gì.

Để 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 y =H(x) 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} .

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

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)

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.

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.

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

xxxx

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

Thực hành

SHA-256

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 (bitcoin sử dụng chuẩn này).

$ 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

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.

Balance

“The basic requirements of production: to build and deliver products in response to the demands of the customer at a scheduled delivery time, at an acceptable quality level, and at the lowest possible cost.” – High Output Management by Andrew S.Grove

“The art of product management is to combine a deep understanding of your target customer’s needs and desires with the capabilities of your engineering team and the technologies they have to work with in order to come up with a product definition that is both compelling and achievable.”  – Behind Every Great Product by Martin Cagan

“Ngon, Bổ, Rẻ” – Urban Vietnamese proverb 🙂

The Basic of Production

  • The basic requirements of production: to build and deliver products in response to the demands of the customer at a scheduled delivery time, at an acceptable quality level, and at the lowest possible cost.
  • production flow: limiting step. We plan our flow around the most critical step.
  • Three fundamental types of production operations: process, assembly, and test.
  • trade-offs between various factors: manpower, capacity, and inventory, reduce the understanding to a quantifiable set of relationships.
  • Adding Value: all production flows have a basic characteristic: the material becomes more valuable as it moves through the process.
  • Common rule: detect and fix any problem … at the lowest-value stage possible.

from High Output Management by Andrew S.Grove

High Output Management

applying the methods of production, exercising managerial leverage, and eliciting an athlete’s desire for peak performance can help nearly everyone to work more productively.

Thee basic ideas:

  • Output-oriented approach to management: apply some of the principles and the discipline of manufacturing to other forms of business enterprise, it gave a systematic way of managing it.
  • The output of a manager is the output of the organizational units under his supervision or influence. Choosing to perform tasks that possess high managerial leverage which measures the impact of what managers do to increase the output of their teams.
  • A team will perform well only if peak performance is elicited from the individuals in it: sport analogy and task-relevant feedback.

from High Output Management – Andrew S.Grove

On Enterprise Selling

“…the most important discussions and deliberations go on when the seller isn’t present, during the interval between calls”

Neil Rackham

On Management

The output of a manager is the output of the organizational units under his supervision or influence.

(some other ways of looking at management: management is getting work done through other people, or bringing people together to accomplish desired goals)

Reports are more a medium of self-discipline than a way to communicate information. Writing the report is important; reading it often is not.

Like a housewife’s, a manager’s work is never done. There is always more to be done, more that should be done, always more than can be done.

[manager] should move to the point where his leverage will be the greatest.

The art of management lies in the capacity to select from the many activities of seemingly comparable significance the one or two or three that provide leverage well beyond the others and concentrate on them.

delegation without follow-through is abdication.

if you have a choice you should delegate those activities you know best.

supervisory should have six to eight subordinates; … a manager should allocate about a half day per week to each of his subordinates.

The … important production concept we can apply to managerial work is to strive toward regularity.

 High Output Management by Andrew S. Grove

On scientific words

Science looks for things in nature, including our human nature and activities, which can be grouped together and understood. Such understanding is a ability to see what complicated or diverse events really do have in common and to describe the behavior accurately and simply.. The words use in such scientific descriptions are often drawn from our everyday vocabulary.

John R.Pierce – An Introduction to Information Theory

On technology company management style

A journalist puzzled by our management style once asked me, “Mr. Grove (legendary former Intel CEO Andy Grove ), isn’t your company’s emphasis on visible signs of egalitarianism such as informal dress, partitions instead of offices…just so much affectation?” My answer was that this is not affectation, but a matter of survival. In our business we have to mix knowledge-power people with position-power people daily, and together they make decisions that could affect us for years to come.

The Little Prince: the fox quotes

“Trungpa (in Shambhala: Sacred Path of the Warrior) alludes that we might make special ties to every moment that we experience as the little prince makes to the fox by taming him.”

“I am looking for friends. What does that mean — tame?”

“It is an act too often neglected,” said the fox. “It means to establish ties.”

“To establish ties?”

“Just that,” said the fox. “To me, you are still nothing more than a little boy who is just like a hundred thousand other little boys. And I have no need of you. And you, on your part, have no need of me. To you I am nothing more than a fox like a hundred thousand other foxes. But if you tame me, then we shall need each other. To me, you will be unique in all the world. To you, I shall be unique in all the world….”

“People have forgotten this truth,” the fox said. “But you mustn’t forget it. You become responsible forever for what you’ve tamed. You’re responsible for your rose.”

“And now here is my secret, a very simple secret: It is only with the heart that one can see rightly; what is essential is invisible to the eye.”
― Antoine de Saint-Exupéry, The Little Prince

 

Rants

Trải lòng đêm khuya 🙂 – I always believe BJJ is the best gift to a child; he or she can keep it till rest of his/her life; to me it is not a sport or a martial art, more like a way of life, second only to zazen. Many of my professional sport friends don’t understand me this point. I stopped talk about and “advertise” about Jiu Jitsu to my friends long time ago, many of my “normal” friends do not know I run a BJJ club. I still talk a person into trying out Jiu Jitsu because I truly believe it is good for him/her; it is a precious thing I can give to that person. At this age in life, I see (in the sense that it is not think or believe) that fate (karma or cơ duyên are better words) will bring us (people) together. May all of you find peace in new year! Happy 2017! Last words, the purpose of training Jiu Jitsu is to keep training Jiu Jitsu (not wining medals or getting the belts). If you understand this, you will find the secret of Jiu Jitsu which is to keep training Jiu Jitsu. – Một đêm mất ngủ 🙂