Tất cả các loại tiền tệ cần một số cách để kiểm soát nguồn cung và thực thi các đặc tính bảo mật khác nhau để ngăn chặn gian lận. Đối với tiền tệ pháp định (fiat currencies), các tổ chức như ngân hàng trung ương kiểm soát nguồn cung tiền và thêm các tính năng chống giả mạo vào tiền tệ vật chất. Những tính năng bảo mật này nâng cao tầm kiểm soát đối với kẻ tấn công, nhưng chúng không khiến tiền bạc không thể làm giả. Cuối cùng, việc thực thi pháp luật là cần thiết để ngăn chặn mọi người vi phạm các quy tắc của hệ thống.
Tiền điện tử cũng phải có các biện pháp bảo mật để ngăn chặn mọi người can thiệp vào trạng thái của hệ thống và không làm nhầm lẫn (nghĩa là đưa ra các tuyên bố không nhất quán lẫn nhau với những người khác nhau). Ví dụ: nếu Alice thuyết phục Bob rằng cô ấy trả cho anh ta một đồng tiền kỹ thuật số, thì cô ấy sẽ không thể thuyết phục Carol rằng cô ấy đã trả cho cô ấy đồng xu đó. Nhưng không giống như tiền tệ fiat, các quy tắc bảo mật của tiền điện tử cần phải được thực thi hoàn toàn về mặt công nghệ và không dựa vào cơ quan trung ương.
Như từ gợi ý, tiền điện tử sử dụng nhiều mật mã học. Cryptography cung cấp một cơ chế để mã hóa các quy tắc của một hệ thống tiền điện tử trong chính hệ thống một cách an toàn. Chúng ta có thể sử dụng nó để ngăn chặn việc can thiệp và làm nhầm lẫn, cũng như để mã hóa, trong một giao thức toán học, các quy tắc để tạo ra các đơn vị tiền tệ mới. Do đó, trước khi chúng ta có thể hiểu đúng về tiền điện tử, chúng ta cần phải nghiên cứu sâu hơn về nền tảng mật mã mà chúng dựa vào.
Mật mã học là một lĩnh vực nghiên cứu học thuật sâu sử dụng nhiều kỹ thuật toán học tiên tiến nổi tiếng là tinh vi và phức tạp. May mắn thay, Bitcoin chỉ dựa trên một số ít các cấu trúc mật mã tương đối đơn giản và nổi tiếng. Trong chương này, chúng ta đặc biệt nghiên cứu về hàm băm mật mã và chữ ký số (digital signatures), hai nguyên thủy được chứng minh là hữu ích để xây dựng tiền điện tử. Các chương sau giới thiệu các sơ đồ mật mã phức tạp hơn, chẳng hạn như bằng chứng không có kiến thức, được sử dụng trong các phần mở rộng và sửa đổi được đề xuất đối với Bitcoin.
Sau khi các nguyên thủy mật mã cần thiết đã được giới thiệu, chúng ta sẽ thảo luận về một số cách mà chúng được sử dụng để xây dựng tiền điện tử. Chúng ta sẽ hoàn thành chương này với các ví dụ về tiền điện tử đơn giản minh họa một số thách thức thiết kế cần được giải quyết.
1.1. Các hàm băm mật mã
Nguyên thủy mật mã đầu tiên mà chúng ta cần hiểu là một hàm băm mật mã. Hàm băm là một hàm toán học có ba tính chất sau:
- Đầu vào của nó có thể là bất kỳ chuỗi nào với kích thước bất kỳ.
- Nó tạo ra một đầu ra có kích thước cố định. Với mục đích làm cho cuộc thảo luận trong chương này trở nên cụ thể, chúng ta sẽ giả định kích thước đầu ra 256-bit. Tuy nhiên, thảo luận của chúng ta đúng với bất kỳ kích thước đầu ra nào, miễn là nó đủ lớn.
- Nó có thể tính toán một cách hiệu quả. Theo trực giác, điều này có nghĩa là đối với một chuỗi đầu vào nhất định, bạn có thể tìm ra đầu ra của hàm băm là bao nhiêu trong một khoảng thời gian hợp lý. Về mặt kỹ thuật hơn, tính toán băm của một chuỗi n-bit nên có thời gian chạy là O(n).
Các thuộc tính này xác định một hàm băm chung, một hàm có thể được sử dụng để xây dựng cấu trúc dữ liệu, chẳng hạn như bảng băm (hash table). Chúng ta sẽ tập trung hoàn toàn vào các hàm băm mật mã. Để một hàm băm được bảo mật về mặt mật mã, chúng ta yêu cầu nó phải có ba đặc tính bổ sung sau: (1) khả năng chống va chạm, (2) ẩn và (3) tính thân thiện với câu đố.
Chúng ta sẽ xem xét kỹ hơn từng thuộc tính này để hiểu được lý do tại sao lại hữu ích khi có một hàm đáp ứng chúng. Người đọc đã nghiên cứu về mật mã nên lưu ý rằng cách xử lý các hàm băm trong cuốn sách này hơi khác so với cách xử lý trong sách giáo khoa mật mã tiêu chuẩn. Đặc biệt, thuộc tính thân thiện với câu đố không phải là một yêu cầu chung cho các hàm băm mật mã, mà là một yêu cầu đặc biệt hữu ích cho tiền điện tử.
Thuộc tính 1: Khả năng chống va chạm
Thuộc tính đầu tiên mà chúng ta cần từ một hàm băm mật mã là nó có khả năng chống va chạm. Xung đột xảy ra khi hai đầu vào khác nhau tạo ra cùng một đầu ra. Một hàm băm H(·) có khả năng chống va chạm nếu không ai có thể tìm thấy xung đột (Hình 1.1). Về mặt hình thức:
Khả năng chống va chạm. Một hàm băm H được cho là có khả năng chống va chạm nếu không thể tìm thấy hai giá trị, x và y, sao cho x ≠ y, nhưng H(x) = H(y).
Lưu ý rằng chúng tôi đã nói “không ai có thể tìm thấy” một vụ va chạm, nhưng chúng tôi không nói rằng không có va chạm nào tồn tại. Trên thực tế, xung đột tồn tại đối với bất kỳ hàm băm nào và chúng ta có thể chứng minh điều này bằng một đối số đếm đơn giản. Không gian đầu vào cho hàm băm chứa tất cả các chuỗi có độ dài, nhưng không gian đầu ra chỉ chứa các chuỗi có độ dài cố định cụ thể. Bởi vì không gian đầu vào lớn hơn không gian đầu ra (thực sự, không gian đầu vào là vô hạn, trong khi không gian đầu ra là hữu hạn), phải có các chuỗi đầu vào ánh xạ đến cùng một chuỗi đầu ra. Trên thực tế, sẽ có một số đầu ra mà vô số đầu vào có thể sẽ ánh xạ (Hình 1.2).
HÌNH 1.1. Một va chạm băm. x và y là các giá trị khác nhau, nhưng khi nhập vào hàm băm H, chúng tạo ra cùng một đầu ra.
Bây giờ, để làm cho mọi thứ thậm chí còn tồi tệ hơn, chúng tôi đã nói rằng không thể tìm thấy một vụ va chạm. Tuy nhiên, có những phương pháp được đảm bảo để tìm ra va chạm. Hãy xem xét phương pháp đơn giản sau để tìm xung đột cho một hàm băm có kích thước đầu ra 256-bit: chọn 2256 + 1 giá trị khác biệt, tính toán các giá trị băm của mỗi giá trị đó và kiểm tra xem hai đầu ra có bằng nhau hay không. Vì chúng ta đã chọn nhiều đầu vào hơn đầu ra có thể, nên một số cặp trong số chúng phải xung đột khi bạn áp dụng hàm băm.
Phương pháp trên được đảm bảo để tìm thấy một va chạm. Nhưng nếu chúng ta chọn đầu vào ngẫu nhiên và tính toán các giá trị băm, chúng ta sẽ tìm thấy xung đột với xác suất cao trước khi kiểm tra 2256 + 1 đầu vào. Trên thực tế, nếu chúng ta chọn ngẫu nhiên chỉ 2130 + 1 đầu vào, thì có 99,8% khả năng ít nhất hai trong số chúng sẽ va chạm. Điều đó chúng ta có thể tìm thấy một va chạm bằng cách chỉ kiểm tra gần đúng căn bậc hai của số lượng kết quả đầu ra có thể có từ một hiện tượng xác suất được gọi là nghịch lý sinh nhật (birthday paradox). Trong các câu hỏi bài tập về nhà (xem tài liệu bổ sung trực tuyến cho cuốn sách này, có thể tìm thấy tại http://press.princeton.edu/titles/10908.html), chúng tôi xem xét vấn đề này chi tiết hơn.
HÌNH 1.2. Khả năng không thể tránh khỏi va chạm. Bởi vì số lượng đầu vào vượt quá số lượng đầu ra, chúng ta đảm bảo rằng phải có ít nhất một đầu ra mà hàm băm ánh xạ nhiều hơn một đầu vào.
Thuật toán phát hiện xung đột này hoạt động cho mọi hàm băm. Nhưng, tất nhiên, vấn đề là phải mất một thời gian rất dài để thực hiện. Đối với một hàm băm có đầu ra 256-bit, bạn sẽ phải tính hàm băm 2256 + 1 lần trong trường hợp xấu nhất và trung bình khoảng 2128 lần. Tất nhiên đó là một con số lớn về mặt thiên văn — nếu một máy tính tính toán 10.000 băm mỗi giây, thì sẽ mất hơn một octillion (1027) năm để tính 2128 băm! Đối với một cách suy nghĩ khác về vấn đề này, chúng ta có thể nói rằng nếu mọi máy tính do con người tạo ra đều đã sử dụng tính toán từ thuở sơ khai của vũ trụ, thì khả năng chúng tìm thấy một vụ va chạm cho đến bây giờ vẫn là rất nhỏ. Nhỏ đến mức nó thấp hơn nhiều so với khả năng Trái đất sẽ bị phá hủy bởi một thiên thạch khổng lồ trong hai giây tới.
Do đó, chúng ta đã tìm ra một thuật toán chung nhưng không thực tế để tìm xung đột cho bất kỳ hàm băm nào. Một câu hỏi khó hơn là: Có một số phương pháp khác có thể được sử dụng trên một hàm băm cụ thể để tìm xung đột không? Nói cách khác, mặc dù thuật toán phát hiện xung đột chung không khả thi để sử dụng, nhưng có thể có một số thuật toán khác có thể tìm ra xung đột cho một hàm băm cụ thể một cách hiệu quả.
Ví dụ, hãy xem xét hàm băm sau:
H(x)= x mod 2256
Hàm này đáp ứng các yêu cầu của chúng ta về một hàm băm vì nó chấp nhận đầu vào có độ dài bất kỳ, trả về đầu ra có kích thước cố định (256 bit) và có thể tính toán hiệu quả. Nhưng hàm này cũng có một phương pháp hiệu quả để tìm ra va chạm. Lưu ý rằng hàm này chỉ trả về 256 bit cuối cùng của đầu vào. Khi đó, một va chạm sẽ là các giá trị 3 và 3 + 2256. Ví dụ đơn giản này minh họa rằng mặc dù phương pháp phát hiện va chạm chung của chúng ta không thể sử dụng được trong thực tế, nhưng có ít nhất một số hàm băm mà phương pháp phát hiện va chạm hiệu quả tồn tại.
Tuy nhiên, đối với các hàm băm khác, chúng ta không biết liệu các phương thức đó có tồn tại hay không. Chúng ta nghi ngờ rằng chúng có khả năng chống va chạm. Tuy nhiên, không có hàm băm nào được chứng minh là có khả năng chống va chạm. Các hàm băm mật mã mà chúng ta dựa vào trong thực tế chỉ là các hàm mà mọi người đã thực sự cố gắng, thực sự khó để tìm ra va chạm và vẫn chưa thành công. Và vì vậy chúng ta chọn tin rằng chúng có khả năng chống va chạm. (Trong một số trường hợp, chẳng hạn như hàm băm được gọi là MD5, các xung đột cuối cùng đã được tìm thấy sau nhiều năm làm việc, dẫn đến việc hàm không được chấp nhận và loại bỏ dần khỏi sử dụng thực tế.)
ỨNG DỤNG: KỸ THUẬT SỐ THÔNG ĐIỆP
Bây giờ chúng ta đã biết khả năng chống va chạm là gì, câu hỏi hợp lý là: Nó có ích cho việc gì? Đây là một ứng dụng: Nếu chúng ta biết rằng hai đầu vào x và y cho hàm băm chống va chạm H là khác nhau, thì sẽ an toàn khi giả sử rằng hàm băm H(x) và H(y) của chúng khác nhau—nếu ai đó biết x và y khác nhau nhưng có cùng hàm băm, điều đó sẽ vi phạm giả định của chúng ta rằng H có khả năng chống va chạm.
Đối số này cho phép chúng ta sử dụng đầu ra băm như một bản tóm tắt thông báo. Hãy xem xét SecureBox, một hệ thống lưu trữ tệp trực tuyến đã được xác thực cho phép người dùng tải tệp lên và đảm bảo tính toàn vẹn của tệp khi họ tải xuống. Giả sử rằng Alice tải lên các tệp thực sự lớn và cô ấy muốn có thể xác minh sau rằng tệp mà cô ấy tải xuống có giống với tệp mà cô ấy đã tải lên hay không. Một cách để làm điều đó là lưu toàn bộ tệp lớn cục bộ và so sánh trực tiếp với tệp mà cô ấy tải xuống. Trong khi điều này hoạt động, nó phần lớn đánh bại mục đích của việc tải nó lên ở nơi đầu tiên; nếu Alice cần có quyền truy cập vào bản sao cục bộ của tệp để đảm bảo tính toàn vẹn của nó, cô ấy chỉ có thể sử dụng bản sao cục bộ trực tiếp.
Hàm băm chống va chạm cung cấp một giải pháp thanh lịch và hiệu quả cho vấn đề này. Alice chỉ cần nhớ hàm băm của tệp gốc. Sau đó, khi tải tệp xuống từ SecureBox, cô ấy sẽ tính toán hàm băm của tệp đã tải xuống và so sánh với tệp mà cô ấy đã lưu trữ. Nếu các hàm băm giống nhau, thì cô ấy có thể kết luận rằng tệp thực sự giống với tệp mà cô ấy đã tải lên, nhưng nếu chúng khác nhau, thì Alice có thể kết luận rằng tệp đã bị giả mạo. Do đó, việc ghi nhớ hàm băm cho phép cô ấy phát hiện không chỉ lỗi ngẫu nhiên của tệp trong quá trình truyền hoặc trên máy chủ của SecureBox mà còn cả việc máy chủ sửa đổi tệp có chủ ý. Những đảm bảo như vậy khi đối mặt với hành vi nguy hiểm tiềm ẩn của các thực thể khác là cốt lõi của những gì mật mã mang lại cho chúng ta.
Hàm băm đóng vai trò là một thông báo có độ dài cố định hoặc bản tóm tắt rõ ràng, của một thông báo. Điều này cung cấp cho chúng ta một cách rất hiệu quả để nhớ lại những thứ chúng ta đã thấy trước đây và nhận ra chúng một lần nữa. Trong khi toàn bộ tệp có thể dài hàng gigabyte, hàm băm có độ dài cố định—256 bit cho hàm băm trong ví dụ của chúng ta. Điều này làm giảm đáng kể yêu cầu lưu trữ của chúng ta. Ở phần sau của chương này và trong suốt cuốn sách, chúng ta sẽ thấy các ứng dụng hữu ích khi sử dụng hàm băm làm thông báo tóm tắt.
Thuộc tính 2: Ẩn
Thuộc tính thứ hai mà chúng ta muốn từ các hàm băm của mình là nó đang ẩn. Thuộc tính ẩn khẳng định rằng nếu chúng ta cung cấp đầu ra của hàm băm y = H(x), không có cách nào khả thi để tìm ra đầu vào, x, là gì. Vấn đề là thuộc tính này không thể đúng trong biểu mẫu đã nêu. Hãy xem xét ví dụ đơn giản sau: chúng ta sẽ thực hiện một thử nghiệm trong đó chúng ta tung một đồng xu. Nếu kết quả của việc lật đồng xu là ngửa, chúng ta sẽ công bố hàm băm của chuỗi “ngửa”. Nếu kết quả là sấp, chúng ta sẽ thông báo hàm băm của chuỗi “sấp”.
Sau đó, chúng ta hỏi một người nào đó, một đối thủ, người không nhìn thấy đồng xu lật mà chỉ nhìn thấy đầu ra băm này, để tìm ra chuỗi nào đã được băm (chúng ta sẽ sớm biết lý do tại sao chúng ta có thể muốn chơi các trò chơi như thế này) . Đáp lại, họ chỉ cần tính toán cả băm của chuỗi “ngửa” và băm của chuỗi “sấp”, và họ có thể xem họ được cung cấp cái nào. Và như vậy, chỉ trong vài bước, họ có thể tìm ra đầu vào là gì.
Đối thủ có thể đoán chuỗi là gì vì chỉ có thể có hai giá trị của x, và đối thủ chỉ cần thử cả hai giá trị đều rất dễ dàng. Để có thể đạt được thuộc tính ẩn, không được có giá trị nào của x có khả năng xảy ra đặc biệt. Nghĩa là, x phải được chọn từ một tập hợp, theo một nghĩa nào đó, rất dàn trải. Nếu x được chọn từ một tập hợp như vậy, phương pháp thử một vài giá trị của x đặc biệt có khả năng sẽ không hoạt động.
Câu hỏi lớn là: Liệu chúng ta có thể đạt được thuộc tính ẩn khi các giá trị mà chúng ta muốn không đến từ một tập hợp dàn trải như trong thử nghiệm “ngửa” và “sấp” của chúng ta không? May mắn thay, câu trả lời là có! Chúng ta có thể ẩn ngay cả một đầu vào không trải rộng bằng cách nối nó với một đầu vào khác được trải rộng. Bây giờ chúng ta có thể chính xác hơn một chút về ý nghĩa của chúng ta khi ẩn (thanh dọc kép ‖ biểu thị sự nối).
Tính ẩn. Hàm băm H được cho là ẩn nếu khi một giá trị bí mật r được chọn từ phân phối xác suất có entropy min cao, khi đó, cho trước H(r ‖ x), không thể tìm thấy x.
Trong lý thuyết thông tin, min-entropy là thước đo mức độ dự đoán của một kết quả, và min-entropy cao nắm bắt ý tưởng trực quan rằng phân phối (tức là của một biến ngẫu nhiên) là rất dàn trải. Điều đó có nghĩa cụ thể là khi chúng ta lấy mẫu từ phân phối, không có giá trị cụ thể nào có khả năng xảy ra. Vì vậy, đối với một ví dụ cụ thể, nếu r được chọn đồng nhất trong số tất cả các chuỗi dài 256 bit, thì bất kỳ chuỗi cụ thể nào cũng được chọn với xác suất 1/2256, đây là một giá trị cực kỳ nhỏ.
ỨNG DỤNG: CAM KẾT
Bây giờ chúng ta hãy xem xét một ứng dụng của thuộc tính ẩn. Đặc biệt, những gì chúng ta muốn làm là một thứ gọi là cam kết. Cam kết là tương tự kỹ thuật số của việc lấy một giá trị, niêm phong nó trong một phong bì và đặt phong bì đó lên bàn nơi mọi người có thể nhìn thấy nó. Khi bạn làm điều đó, bạn đã cam kết với những gì bên trong phong bì. Nhưng bạn chưa mở nó, vì vậy mặc dù bạn đã cam kết với một giá trị, nhưng giá trị đó vẫn là một bí mật đối với những người khác. Sau đó, bạn có thể mở phong bì và tiết lộ giá trị mà bạn đã cam kết trước đó.
Đề án cam kết. Một lược đồ cam kết bao gồm hai thuật toán:
• com := commit(msg, nonce) Hàm commit nhận một thông báo và giá trị ngẫu nhiên bí mật, được gọi là nonce, làm đầu vào và trả về một cam kết.
• verify(com, msg, nonce) Hàm verify lấy một cam kết, nonce và tin nhắn làm đầu vào. Nó trả về true nếu com == commit(msg, nonce) và false nếu ngược lại.
Chúng ta yêu cầu giữ hai thuộc tính bảo mật sau:
• Ẩn: Với com, không thể tìm thấy msg.
• Ràng buộc: Không thể tìm được hai cặp (msg, nonce) và (msg′, nonce′) sao cho msg ≠ msg′ và commit(msg, nonce) == commit(msg′, nonce′).
Để sử dụng lược đồ cam kết, trước tiên chúng ta cần tạo một nonce ngẫu nhiên. Sau đó, chúng ta áp dụng hàm cam kết cho nonce này cùng với tin nhắn, giá trị được cam kết và chúng ta công bố cam kết com. Giai đoạn này tương tự như đặt phong bì niêm phong trên bàn. Sau đó, nếu chúng ta muốn tiết lộ giá trị mà chúng ta đã cam kết trước đó, chúng ta công bố số ngẫu nhiên mà chúng ta đã sử dụng để tạo cam kết này và thông báo, msg. Bây giờ bất kỳ ai cũng có thể xác minh rằng tin nhắn đó thực sự là tin nhắn được cam kết trước đó. Giai đoạn này tương tự như mở phong bì.
Mỗi khi bạn cam kết một giá trị, điều quan trọng là bạn phải chọn một giá trị ngẫu nhiên mới nonce. Trong mật mã, thuật ngữ nonce được sử dụng để chỉ một giá trị chỉ có thể được sử dụng một lần.
Hai thuộc tính bảo mật chỉ ra rằng các thuật toán thực sự hoạt động giống như niêm phong và mở một phong bì. Đầu tiên, đã đưa ra cam kết com, ai đó nhìn vào phong bì không thể hiểu được thông điệp là gì. Thuộc tính thứ hai là nó có tính ràng buộc. Điều này đảm bảo rằng khi bạn cam kết với những gì trong phong bì, bạn sẽ không thể thay đổi ý định sau này. Đó là, không thể tìm thấy hai thông báo khác nhau, để bạn có thể cam kết với một thông báo và sau đó tuyên bố rằng bạn đã cam kết với một thông báo khác.
Vì vậy, làm thế nào để chúng ta biết rằng hai thuộc tính này giữ? Trước khi có thể trả lời điều này, chúng ta cần thảo luận về cách chúng ta sẽ thực sự triển khai một kế hoạch cam kết. Chúng ta có thể làm như vậy bằng cách sử dụng một hàm băm mật mã. Hãy xem xét sơ đồ cam kết sau:
commit(msg, nonce) := H(nonce ‖ msg),
trong đó nonce là giá trị 256 bit ngẫu nhiên
Để cam kết một tin nhắn, chúng ta tạo một nonce 256-bit ngẫu nhiên. Sau đó, chúng ta nối nonce và thông báo và trả về giá trị băm của giá trị được nối này làm cam kết. Để xác minh, một người nào đó sẽ tính toán cùng một băm này khi chúng được cung cấp để nối với tin nhắn. Và họ sẽ kiểm tra xem kết quả có đúng như cam kết mà họ đã thấy hay không.
Hãy xem xét hai thuộc tính cần thiết của các chương trình cam kết của chúng ta. Nếu chúng ta thay thế việc khởi tạo commit và verify cũng như H(nonce ‖ msg) cho com, thì các thuộc tính này sẽ trở thành:
- Ẩn: Với H(nonce ‖ msg), không thể tìm thấy msg.
- Ràng buộc: Không thể tìm được hai cặp (msg, nonce) và (msg′, nonce′) sao cho msg ≠ msg′ và H(nonce ‖ msg) == (nonce′ ‖ msg′).
Thuộc tính ẩn của các cam kết chính xác là thuộc tính ẩn mà chúng ta cần cho các hàm băm của mình. Nếu khóa được chọn làm giá trị 256-bit ngẫu nhiên, thì thuộc tính ẩn nói rằng nếu chúng ta băm sự kết hợp của khóa và thông báo, thì không thể khôi phục thông báo từ đầu ra băm. Và hóa ra thuộc tính ràng buộc được ngụ ý bởi thuộc tính chống va chạm của hàm băm bên dưới. Nếu hàm băm có khả năng chống va chạm, thì sẽ không khả thi khi tìm các giá trị msg và msg′ riêng biệt sao cho H(nonce ‖ msg) = H(nonce′ ‖ msg′), vì các giá trị đó thực sự sẽ là xung đột. (Lưu ý rằng hàm ý ngược lại không đúng. Nghĩa là, bạn có thể tìm thấy va chạm, nhưng không có va chạm nào có dạng H(nonce ‖ msg) == H(nonce′ ‖ msg′). Ví dụ: nếu bạn chỉ có thể tìm thấy một xung đột trong đó hai ký tự khác biệt tạo ra cùng một cam kết cho cùng một thông báo, thì lược đồ cam kết vẫn còn ràng buộc, nhưng hàm băm bên dưới không có khả năng chống xung đột.)
Do đó, nếu H là một hàm băm có cả khả năng chống va chạm và ẩn, sơ đồ cam kết này sẽ hoạt động, theo nghĩa là nó sẽ có các thuộc tính bảo mật cần thiết.
Tính chất 3: Sự thân thiện của câu đố
Tính chất bảo mật thứ ba mà chúng ta sẽ cần từ các hàm băm là chúng thân thiện với các câu đố. Thuộc tính này hơi phức tạp. Trước tiên, chúng ta giải thích các yêu cầu kỹ thuật của thuộc tính này là gì và sau đó đưa ra một ứng dụng minh họa tại sao thuộc tính này lại hữu ích.
Sự thân thiện của câu đố. Hàm băm H được cho là thân thiện với câu đố nếu với mọi giá trị đầu ra n-bit có thể có y, nếu k được chọn từ phân phối có entropy min cao, thì không thể tìm thấy x sao cho H(k ‖ x) = y trong thời gian nhỏ hơn đáng kể 2n.
Theo trực giác, nếu ai đó muốn nhắm mục tiêu hàm băm để có một giá trị đầu ra cụ thể nào đó là y và nếu một phần của đầu vào đã được chọn theo cách ngẫu nhiên phù hợp, thì rất khó để tìm một giá trị khác đạt chính xác mục tiêu đó.
ỨNG DỤNG: CÂU ĐỐ TÌM KIẾM
Hãy xem xét một ứng dụng minh họa tính hữu ích của thuộc tính này. Trong ứng dụng này, chúng ta sẽ xây dựng một câu đố tìm kiếm, một vấn đề toán học yêu cầu tìm kiếm trong một không gian rất lớn để tìm ra lời giải. Đặc biệt, một câu đố tìm kiếm không có đường tắt. Đó là, không có cách nào để tìm ra giải pháp hợp lệ ngoài việc tìm kiếm trong không gian rộng lớn đó.
Câu đố tìm kiếm. Một câu đố tìm kiếm bao gồm
• một hàm băm, H,
• một giá trị, id (mà chúng ta gọi là ID câu đố), được chọn từ phân phối entropy tối thiểu cao và
• một tập hợp mục tiêu Y.
Giải pháp cho câu đố này là một giá trị, x, sao cho
Trực giác là: nếu H có đầu ra n-bit, thì nó có thể nhận bất kỳ giá trị nào trong 2n giá trị. Việc giải câu đố đòi hỏi phải tìm một đầu vào sao cho đầu ra nằm trong tập Y, thường nhỏ hơn nhiều so với tập tất cả các đầu ra. Kích thước của Y xác định độ khó của câu đố. Nếu Y là tập hợp tất cả các chuỗi n-bit, thì câu đố là nhỏ, trong khi nếu Y chỉ có một phần tử, thì câu đố khó tối đa. Rằng ID câu đố có entropy tối thiểu cao đảm bảo rằng không có đường tắt. Ngược lại, nếu một giá trị cụ thể của ID có khả năng xảy ra, thì ai đó có thể gian lận, chẳng hạn, bằng cách tính toán trước một giải pháp cho câu đố với ID đó.
Nếu hàm băm thân thiện với câu đố, thì không có chiến lược giải câu đố này tốt hơn nhiều so với việc chỉ thử các giá trị ngẫu nhiên của x. Và vì vậy, nếu chúng ta muốn đặt ra một câu đố khó giải, chúng ta có thể làm theo cách này miễn là chúng ta có thể tạo ra các ID câu đố một cách ngẫu nhiên phù hợp. Chúng ta sẽ sử dụng ý tưởng này sau, khi chúng ta nói về khai thác Bitcoin, bắt đầu từ Chương 2—khai thác là một loại câu đố tính toán.
SHA-256
Chúng ta đã thảo luận về ba thuộc tính của hàm băm và một ứng dụng của mỗi thuộc tính này. Bây giờ chúng ta hãy thảo luận về một hàm băm cụ thể mà chúng ta sẽ sử dụng rất nhiều trong cuốn sách này. Nhiều hàm băm tồn tại, nhưng đây là hàm mà Bitcoin sử dụng chủ yếu và nó là một hàm khá tốt để sử dụng. Nó được gọi là SHA-256.
Nhớ lại rằng chúng ta yêu cầu các hàm băm của chúng ta hoạt động trên các đầu vào có độ dài tùy ý. May mắn thay, miễn là chúng ta có thể xây dựng một hàm băm hoạt động trên các đầu vào có độ dài cố định, thì có một phương pháp chung để chuyển nó thành một hàm băm hoạt động trên các đầu vào có độ dài tùy ý. Nó được gọi là biến đổi Merkle-Damgård. SHA-256 là một trong số các hàm băm thường được sử dụng tận dụng phương pháp này. Theo thuật ngữ thông thường, hàm băm kháng va chạm có độ dài cố định cơ bản được gọi là hàm nén (compression function). Người ta đã chứng minh rằng nếu hàm nén bên dưới có khả năng chống va chạm thì hàm băm tổng thể cũng có khả năng chống va chạm.
Phép biến đổi Merkle-Damgård khá đơn giản. Giả sử rằng hàm nén nhận đầu vào có độ dài m và tạo ra đầu ra có độ dài nhỏ hơn n. Đầu vào cho hàm băm, có thể có kích thước bất kỳ, được chia thành các khối có chiều dài m – n. Việc xây dựng hoạt động như sau: chuyển từng khối cùng với đầu ra của khối trước đó vào chức năng nén. Lưu ý rằng độ dài đầu vào sau đó sẽ là (m – n) + n = m, là độ dài đầu vào cho hàm nén. Đối với khối đầu tiên, không có đầu ra khối trước đó, thay vào đó chúng ta sử dụng một vectơ khởi tạo (initialization vector) (IV trong hình 1.3). Số này được sử dụng lại cho mọi lệnh gọi đến hàm băm và trong thực tế, bạn chỉ cần tra cứu nó trong một tài liệu tiêu chuẩn. Đầu ra của khối cuối cùng là kết quả mà bạn trả về.
HÌNH 1.3. Hàm băm SHA-256 (đơn giản hóa). SHA-256 sử dụng phép biến đổi Merkle-Damgård để biến một hàm nén chống va chạm có độ dài cố định thành một hàm băm chấp nhận các đầu vào có độ dài tùy ý. Đầu vào được đệm, để độ dài của nó là bội số của 512 bit. IV là viết tắt của vectơ khởi tạo.
Lập mô hình các hàm băm
Hàm băm là con dao mật mã của Quân đội Thụy Sĩ: chúng tìm thấy một vị trí trong một loạt các ứng dụng ngoạn mục. Mặt trái của tính linh hoạt này là các ứng dụng khác nhau yêu cầu các thuộc tính hơi khác nhau của các hàm băm để đảm bảo tính bảo mật. Nó đã được chứng minh nổi tiếng là khó xác định danh sách các thuộc tính hàm băm có thể dẫn đến bảo mật có thể chứng minh được trên mọi lĩnh vực.
Trong cuốn sách này, chúng tôi đã chọn ba thuộc tính quan trọng đối với cách các hàm băm được sử dụng trong Bitcoin và các loại tiền điện tử khác. Ngay cả trong không gian này, không phải tất cả các thuộc tính này đều cần thiết cho mọi việc sử dụng các hàm băm. Ví dụ: sự thân thiện với câu đố chỉ quan trọng trong khai thác Bitcoin, như chúng ta sẽ thấy.
Các nhà thiết kế các hệ thống an toàn thường bỏ qua vấn đề và các hàm băm mô hình là các hàm xuất ra một giá trị ngẫu nhiên độc lập cho mọi đầu vào có thể. Việc sử dụng “mô hình tiên tri ngẫu nhiên” này để chứng minh tính bảo mật vẫn còn gây tranh cãi trong mật mã. Bất kể quan điểm của ai về cuộc tranh luận này, lý luận về cách giảm các thuộc tính bảo mật mà chúng ta muốn trong các ứng dụng của mình thành các thuộc tính cơ bản của các nguyên thủy cơ bản là một bài tập trí tuệ có giá trị để xây dựng các hệ thống an toàn. Phần trình bày của chúng tôi trong chương này được thiết kế để giúp bạn học kỹ năng này.
SHA-256 sử dụng hàm nén lấy đầu vào 768-bit và tạo ra đầu ra 256-bit. Kích thước khối là 512 bit. Xem Hình 1.3 để mô tả bằng đồ họa về cách SHA-256 hoạt động.
Chúng ta đã nói về các hàm băm, các hàm băm mật mã với các thuộc tính đặc biệt, các ứng dụng của các thuộc tính đó và một hàm băm cụ thể mà chúng ta sử dụng trong Bitcoin. Trong phần tiếp theo, chúng ta sẽ thảo luận về các cách sử dụng hàm băm để xây dựng các cấu trúc dữ liệu phức tạp hơn được sử dụng trong các hệ thống phân tán như Bitcoin.