Tác giả: Blockstream Team
Biên dịch: Saoirse, Foresight News
Blockstream Research vừa công bố một báo cáo nghiên cứu toàn diện về chữ ký dựa trên lattice (lưới) cho Bitcoin. Bài viết này tóm tắt nội dung nghiên cứu, những phát hiện chính và các khuyến nghị liên quan. Đọc báo cáo đầy đủ tại đây.
Chữ ký số là cơ chế cốt lõi cho phép giao dịch Bitcoin hoạt động, hiện do các sơ đồ chữ ký Schnorr và ECDSA đảm nhận với chi phí cực thấp. Năm 1994, Shor đã chứng minh rằng một máy tính lượng tử đủ mạnh có thể phá vỡ cả hai loại chữ ký này. Mặc dù thời điểm loại máy móc này ra đời vẫn còn được tranh luận rộng rãi, nhưng chúng ta cần xây dựng một kế hoạch triển khai khả thi cho chữ ký hậu lượng tử trước khi vấn đề thực sự xảy ra.
Các sơ đồ chữ ký dựa trên lattice là ứng cử viên nổi bật để thay thế các chữ ký hiện có. Mật mã lattice đã có lịch sử nghiên cứu hơn một thế kỷ và các ứng dụng mật mã của nó cũng đã phát triển gần ba mươi năm. Trong hệ thống mật mã hậu lượng tử, chữ ký dựa trên lattice có nhiều ưu điểm: kích thước tổng của khóa công khai và chữ ký có thể nhỏ hơn 1,6 kilobyte, đồng thời cấu trúc đại số của nó trong tương lai hứa hẹn hỗ trợ chữ ký đa bên, chữ ký ngưỡng và các chứng minh ngắn gọn.
Báo cáo này nghiên cứu ba sơ đồ: Dilithium, Falcon và Hawk. Dành cho độc giả chưa quen với mật mã lattice, chúng tôi giải thích ý tưởng thiết kế của từng sơ đồ, giới thiệu đầy đủ quy trình thuật toán và phân tích từ các góc độ an ninh, hiệu suất và triển khai thực tế (ví dụ: dẫn xuất khóa trong ví). Trong ba sơ đồ này, những sơ đồ nào thực sự có thể được triển khai trên chuỗi Bitcoin?
Các tiêu chí đánh giá
Việc lựa chọn sơ đồ chữ ký cho Bitcoin có những ràng buộc riêng. Đánh giá lần này tập trung vào bốn tiêu chuẩn cốt lõi:
- Chi phí trên chuỗi: Một trong những chỉ số quan trọng nhất là tổng kích thước của khóa công khai và chữ ký. Khi một đầu ra được chi tiêu, cả khóa công khai và chữ ký đều được ghi lại trên chuỗi, các nút đầy đủ cần tải xuống và lưu trữ từng byte. Chi phí xác minh cũng rất quan trọng: mỗi chữ ký đều phải được xác minh bởi tất cả các nút trên mạng, tốc độ xác minh chậm sẽ gây gánh nặng cho toàn mạng lưới.
- Độ phức tạp triển khai: Việc một sơ đồ có thể được triển khai an toàn hay không là rất quan trọng. Nếu thiết kế yêu cầu tính toán dấu phẩy động hoặc lấy mẫu Gauss phức tạp, một khi triển khai sai hoặc gặp phải các cuộc tấn công kênh kề như phân tích thời gian, khóa riêng tư có thể bị lộ. Độ phức tạp triển khai là yếu tố không thể bỏ qua nếu muốn chuyển đổi suôn sẻ.
- Rủi ro triển khai: Khi tích hợp thực tế vào Bitcoin sẽ gặp phải nhiều trở ngại thực tế: lựa chọn hàm băm ở cấp độ đồng thuận (hầu hết các sơ đồ ứng viên sử dụng SHAKE, Bitcoin sử dụng SHA-256), khả năng tái tạo kết quả chữ ký đa nền tảng, và liệu chương trình ký có phù hợp với giới hạn bộ nhớ của ví phần cứng hay không.
- Tiềm năng phát triển: Hầu hết các ví Bitcoin sử dụng cơ chế xác định phân cấp BIP-32: thông qua một khóa chủ công khai duy nhất, có thể dẫn xuất vô số khóa con công khai mà không cần chạm vào khóa riêng tư. Hiện tại, các sơ đồ chữ ký hậu lượng tử đã được chuẩn hóa đều không hỗ trợ natively tính năng này, vì vậy chúng tôi nghiên cứu chi phí phải trả để bổ sung khả năng đó; đồng thời cũng xem xét các biến thể sơ đồ không chuẩn, chúng có thể mang lại nhiều lợi ích hơn.
Nên chọn cấp độ an ninh nào?
Trước khi so sánh kích thước, cần xác định cấp độ an ninh mục tiêu, và lựa chọn này không đơn giản như vẻ ngoài. NIST chia cấp độ an ninh thành cấp 1-5; cấp độ càng cao thì an ninh càng mạnh, nhưng kích thước khóa và chữ ký tương ứng cũng sẽ lớn hơn.
Chúng tôi cho rằng Bitcoin ít nhất nên áp dụng tiêu chuẩn an ninh cấp 3. Đầu ra Bitcoin có thể không được chi tiêu trong nhiều thập kỷ, nếu tiến bộ trong phân tích mật mã làm giảm cấp độ an ninh thực tế của sơ đồ, tài sản sẽ bị khóa bởi khóa bị suy yếu và tiếp xúc lâu dài với rủi ro. Giả định mật mã lattice đã trải qua gần ba mươi năm phân tích mật mã công khai, lâu hơn cả nền tảng nghiên cứu khi Bitcoin áp dụng đường cong elliptic. Tuy nhiên, cấu trúc đại số phức tạp của lattice vẫn còn nhiều điểm yếu để các cuộc tấn công trong tương lai khai thác, chúng ta không nên đặt cược toàn bộ an ninh trong tương lai xa vào đó.
Các sản phẩm chính thống cũng đưa ra phán đoán tương tự. Giao thức PQ3 của iMessage từ Apple trực tiếp bỏ qua tham số lattice cấp 1, sử dụng tham số cấp 3 và 5 xuyên suốt; Cloudflare trong triển khai TLS hậu lượng tử sử dụng ML-KEM-768 (cấp 3), cho biết mặc dù cấp 1 hiện tại có vẻ an toàn, nhưng cần dự phòng dư lượng an ninh cho phân tích mật tử trong nhiều thập kỷ tới. Trong khi đó, khoảng thời gian an ninh của Bitcoin còn dài hơn cả hai trường hợp trên.
Nâng cao cấp độ an ninh phải trả giá. Ví dụ, Dilithium từ cấp 2 lên cấp 3, tổng kích thước sẽ tăng khoảng 1,5 kilobyte. Báo cáo so sánh các bộ tham số ở tất cả các cấp độ an ninh, độc giả có thể tự mình cân nhắc. Tình huống của Hawk chứng minh rằng việc cân nhắc an ninh thận trọng không chỉ là lý thuyết.
Chi tiết các sơ đồ ứng viên
Dilithium: Sơ đồ thiết kế đơn giản
Dilithium được NIST chuẩn hóa thành ML-DSA trong tiêu chuẩn FIPS 204. Nó di chuyển mô hình cam kết-thử thách-phản hồi của chữ ký Schnorr lên số học lattice mô-đun.
Đặc điểm lớn nhất của nó là sự đơn giản. Tất cả các phép tính của Dilithium đều là phép tính số nguyên: phép toán vòng, nhân ma trận-vector, băm, làm tròn, không có phép tính dấu phẩy động, cũng không cần lấy mẫu Gauss rời rạc. Dễ dàng hơn để viết một triển khai an toàn, thời gian không đổi. Nó cũng là sơ đồ ứng viên được triển khai rộng rãi nhất, đã được tích hợp vào OpenSSL, BoringSSL, AWS-LC và Apple CryptoKit.
Cái giá phải trả là kích thước tương đối lớn. ML-DSA-65 an ninh cấp 3, khóa công khai 1952 byte, chữ ký 3309 byte, tổng cộng 5261 byte, xấp xỉ 55 lần tổng kích thước khóa công khai/riêng tư + chữ ký gốc của Bitcoin, là sơ đồ có kích thước lớn nhất trong ba sơ đồ ở cùng cấp độ an ninh.
Điểm có giá trị nhất của Dilithium đối với Bitcoin: Nó là sơ đồ duy nhất trong ba sơ đồ gần như triển khai được việc dẫn xuất khóa kiểu BIP-32. Cấu trúc khóa có thể tái ngẫu nhiên hóa DilithiumRK, chỉ dựa vào thông tin công khai có thể tạo khóa con từ khóa cha. Báo cáo phân tích ba biến thể, bao gồm DilithiumRKS mà chúng tôi đề xuất, logic dẫn xuất hoàn toàn đặt trong phần mềm ví, trên chuỗi chỉ cần trình xác minh tiêu chuẩn xử lý chữ ký ML-DSA thông thường. Nhưng cả ba đều chưa đạt tiêu chuẩn sẵn sàng triển khai: hai trong số các biến thể cần sửa đổi trình xác minh, bản thân DilithiumRKS còn thiếu chứng minh đầy đủ về tính không thể giả mạo; tất cả các sơ đồ đều phụ thuộc vào ma trận dùng chung toàn mạng, mặc dù an toàn về mặt hình thức dưới giả định Module-LWE, nhưng sẽ ràng buộc an ninh của tất cả các khóa vào cùng một thể hiện. Chúng tôi cho rằng việc dẫn xuất khóa công khai dựa trên Dilithium ở giai đoạn hiện tại chỉ thuộc về khái niệm xác minh, không thể đưa vào triển khai thực tế.
Falcon: Sơ đồ kích thước gọn nhẹ
Falcon được NIST lựa chọn, tên chuẩn hóa là FN-DSA, trong ba sơ đồ thì nó là sơ đồ gọn nhẹ nhất. Falcon-512 an ninh cấp 1, tổng khóa công khai và chữ ký là 1563 byte; Falcon-1024 an ninh cấp 5 tổng cộng 3073 byte. Falcon-1024 với dư lượng an ninh cao hơn, kích thước thậm chí còn nhỏ hơn Dilithium cấp 3.
Falcon áp dụng cách tiếp cận khác với Dilithium: mô hình băm-chữ ký dựa trên lattice NTRU. Khóa riêng của người ký là một cơ sở ngắn của lattice; thông điệp được băm ánh xạ đến một điểm trong không gian, người ký sử dụng cơ sở ngắn để tìm một vector trên lattice rất gần điểm đó. Điểm và vector lân cận đó cùng tạo thành chữ ký; xác minh chỉ kiểm tra vector thuộc lattice đó và khoảng cách đủ gần. Khó khăn trong triển khai là tìm vector đồng thời không được tiết lộ thông tin về cơ sở. Các sơ đồ ban đầu như GGH, NTRUSign lấy điểm lattice gần nhất trực tiếp, mỗi lần ký sẽ tiết lộ một phần thông tin hình học. Falcon sử dụng khung GPV, lấy mẫu vector lân cận từ phân phối Gauss, có thể chứng minh đầu ra lấy mẫu độc lập với cơ sở, loại bỏ rủi ro rò rỉ, nhưng độ khó triển khai bộ lấy mẫu tăng mạnh.
Bộ lấy mẫu là điểm yếu về mặt kỹ thuật của Falcon. Nó hoạt động trong miền Fourier phức, cần tính toán dấu phẩy động. Các bộ xử lý, trình biên dịch, tùy chọn tối ưu hóa biên dịch khác nhau đều có thể dẫn đến kết quả đầu ra dấu phẩy động không nhất quán. Đây không chỉ là vấn đề tương thích, mà còn là nguy cơ an ninh: chứng minh an toàn của GPV yêu cầu, đối với cùng một bản tóm tắt, người ký tuyệt đối không xuất ra hai vector ngắn khác nhau; một khi chữ ký trở thành chữ ký xác định, sự khác biệt do làm tròn dấu phẩy động từ nền tảng sẽ phá vỡ điều kiện đó. Có những giải pháp khả thi: Falcon xác định có thể sử dụng mô phỏng số nguyên thay thế dấu phẩy động phần cứng, xuất ra chữ ký hoàn toàn giống nhau trên tất cả các nền tảng. Cái giá là tốc độ ký giảm khoảng 15 lần, tốc độ tạo khóa giảm khoảng 2 lần.
Quan trọng là, khâu xác minh không bị ảnh hưởng: Xác minh Falcon toàn bộ là phép tính số nguyên, kết quả xác định, đồng thời cũng là khâu xác minh nhanh nhất trong các sơ đồ ứng viên. Đặc tính không đối xứng này rất thân thiện với Bitcoin: việc ký được ví thực hiện một lần khi chi tiêu giao dịch, trong khi mỗi chữ ký đều được tất cả các nút đầy đủ trên mạng xác minh. Khâu ký chậm hơn 15 lần thuộc về chi phí tần suất thấp, đổi lại khả năng tái tạo đa nền tảng, tính toán số nguyên, theo chúng tôi là sự đánh đổi hợp lý. Do đó, vấn đề dấu phẩy động thuộc về trở ngại có thể giải quyết bằng biện pháp kỹ thuật, không phải lỗ hổng chí mạng.
Hai điểm cần lưu ý: Do ràng buộc cấu trúc, Falcon không có tham số cấp 3, chỉ có thể chọn cấp 1 hoặc cấp 5. Dựa trên cân nhắc dư lượng an ninh, chúng tôi đề xuất Falcon-1024. Điểm thứ hai, việc ký sẽ tiêu tốn nhiều bộ nhớ: bộ lấy mẫu cho bộ tham số 1024 phụ thuộc vào cây tính toán trước, chiếm khoảng 90 kilobyte bộ nhớ. Ví phần cứng có thể xây dựng lại cây này động theo từng nhánh, nén mức sử dụng bộ nhớ xuống 16 kilobyte, nhưng thời gian ký sẽ tăng gấp đôi. Việc ký chậm hơn trên thiết bị phần cứng là chi phí thực tế, nhưng vẫn có thể chấp nhận được.
Hawk: Sơ đồ đã thất bại
Mục tiêu của Hawk là kết hợp ưu điểm của hai sơ đồ còn lại: Hawk-512 chữ ký chỉ có 555 byte, nhỏ hơn cả Falcon; phía ký toàn bộ là phép tính số nguyên, mức sử dụng bộ nhớ tối thiểu chỉ 6 kilobyte. Nó cũng là ứng viên dựa trên lattice duy nhất còn lại trong vòng thứ ba của cuộc thi chữ ký bổ sung của NIST, báo cáo dành nhiều trang giới thiệu sơ đồ này.
Cái giá nằm ở giả định an ninh. Nó không tiếp tục sử dụng các bài toán NTRU, SIS đã được kiểm nghiệm qua nhiều thập kỷ phân tích mật mã, mà dựa vào bài toán đẳng cấu lattice và giả định one-more-SVP, hai loại giả định này có lịch sử nghiên cứu tương đối ngắn.
Ngay trước khi báo cáo hoàn tất, Straznickas và Weis từ Anthropic đã phát hiện lỗ hổng cấu trúc trong cấu trúc lattice của Hawk: kích thước chiều của bài toán SVP thực tế cần giải để khôi phục khóa chỉ bằng một nửa so với dự kiến của nhà thiết kế. Cấp độ an ninh khôi phục khóa của bộ tham số ứng viên bị suy yếu đáng kể. Các nhà nghiên cứu đã hoàn thành cuộc tấn công khôi phục khóa đầu cuối đầy đủ vào tham số thử thách dùng cho phân tích mật mã HAWK-256; ngay cả khi bị tấn công, các đề xuất chính thức HAWK-512, HAWK-1024 vẫn không thể bị phá vỡ trong thực tế. Nhóm Hawk xác nhận cuộc tấn công có hiệu lực và đã rút sơ đồ khỏi quy trình của NIST; nhóm cho biết, nếu sửa lỗ hổng bằng cách nhân đôi tham số, ưu thế về kích thước vốn là niềm tự hào của Hawk sẽ biến mất hoàn toàn.
Báo cáo vẫn giữ lại các phần liên quan đến Hawk, vì cuộc tấn công này nhắm vào đặc tính đại số của trường số cụ thể, không phải phủ nhận toàn bộ mô hình thiết kế này. Việc thiết kế lại có thể tránh được lỗ hổng hay không vẫn chưa có kết luận. Sự kiện Hawk cũng trực tiếp xác nhận lý do chúng tôi kiên trì dư lượng an ninh thận trọng: một sơ đồ dù có kích thước ưu việt, tốc độ đáng kể và đã trải qua nhiều vòng chuẩn hóa, chỉ một bài báo có thể làm giảm mạnh cấp độ an ninh ước tính của nó.
Bảng so sánh các sơ đồ
Tất cả các sơ đồ trong bảng trên (bao gồm SPHINCS+) đều là chữ ký không trạng thái: người ký không cần ghi lại chữ ký trước đó. Các chữ ký băm có trạng thái như XMSS có thể đạt kích thước chữ ký nhỏ hơn, nhưng cần duy trì trạng thái ký; tham khảobáo cáo chuyên đề về chữ ký dựa trên băm để biết so sánh.
Vẫn còn nhiều trở ngại để triển khai
Falcon thiếu sơ đồ dẫn xuất khóa khả dụng. Hiện tại, sơ đồ dẫn xuất kiểu BIP-32 duy nhất công khai cho Falcon, sẽ tái ngẫu nhiên hóa cơ sở khóa riêng, giới hạn chuẩn của chữ ký bị phóng đại mạnh, chữ ký trên chuỗi phình ra đến khoảng 23,7 kilobyte. Hơn nữa, tham số của sơ đồ này không đạt điều kiện an ninh của chính nó, nếu sửa vấn đề đó, kích thước sẽ còn bùng nổ hơn nữa. Hiện không có triển khai khả thi nào cho việc dẫn xuất khóa công khai Falcon, đây cũng là vấn đề cần giải quyết có giá trị nhất mà báo cáo đề xuất.
Tiêu chuẩn Falcon chưa được hoàn thiện. Mặc dù NIST đã chọn Falcon, nhưng bản dự thảo FN-DSA vẫn chưa chính thức được công bố. Sau khi chuẩn hóa hoàn tất, mới mang lại các triển khai đã được kiểm toán, vector kiểm tra và hỗ trợ ở cấp độ phần cứng. Việc triển khai rộng rãi có thể giảm rủi ro và độ khó khi tích hợp vào lớp đồng thuận của Bitcoin. Chúng tôi đề xuất chờ FN-DSA chính thức được phát hành, trước đó Falcon vẫn đang trong trạng thái thay đổi.
Biến thể Falcon-WS: Biến thể này nới lỏng tham số nội bộ, dựa vào lấy mẫu loại bỏ để bù đắp, tổng kích thước cấp 1 được nén xuống 1114 byte, cấp 5 nén xuống 2387 byte, so với Falcon nguyên bản, kích thước giảm thêm. Hướng này có giá trị nghiên cứu, nhưng sẽ không được đưa vào tiêu chuẩn chính thức, cần nhiều phân tích mật mã xác minh hơn. Đã có nghiên cứu phát hiện chứng minh tính không thể giả mạo mạnh của sơ đồ phát sinh từ nó tồn tại lỗ hổng (tính không thể giả mạo thông thường không bị ảnh hưởng).
Tương lai có xuất hiện sơ đồ ưu việt hơn không? Ngoài các sơ đồ trên, dòng Fiat-Shamir ban đầu xuất phát từ BLISS năm 2013, kết quả mới nhất được đề xuất bởi Gärtner tại hội nghị CRYPTO 2025, dựa trên giả định chín muồi, kích thước trên giấy có thể sánh ngang với Falcon. Gốc rễ khó triển khai kỹ thuật của dòng này nằm ở vấn đề an ninh triển khai: BLISS từng bị tấn công kênh kề do lấy mẫu Gauss không thời gian không đổi; các sơ đồ sau đó đều không giải quyết triệt để nguy cơ này, kết quả mới nhất cũng cảnh báo độ khó bảo vệ ở khâu lấy mẫu cao hơn. Trước khi vấn đề được giải quyết, các sơ đồ loại này chỉ có sức hấp dẫn lý thuyết, không phù hợp để triển khai.
Chữ ký dựa trên lattice và chữ ký băm có thể bổ sung cho nhau. Chữ ký dựa trên lattice có thể là thành phần của sơ đồ hỗn hợp. Ví dụ trong SHRINCS, đường dẫn khôi phục không trạng thái hiện sử dụng chữ ký SPHINCS+ kích thước vài KB; thay thế bằng chữ ký Falcon (hoặc Falcon-WS), kích thước nhỏ hơn, xác minh nhanh hơn, chi phí đường dẫn khôi phục tần suất thấp giảm mạnh, đường dẫn sử dụng hàng ngày không bị ảnh hưởng.
Kết luận nghiên cứu
Thứ tự ưu nhược điểm của các sơ đồ ứng viên dựa trên lattice rất rõ ràng: Hawk bị tấn công bởi nhóm Anthropic và rút khỏi cuộc cạnh tranh; Dilithium có độ khó triển khai thấp nhất, cũng là sơ đồ duy nhất có nền tảng nghiên cứu liên quan đến dẫn xuất khóa, nhưng kích thước không thân thiện với chi phí trên chuỗi của Bitcoin; Falcon cân bằng giữa kích thước gọn nhẹ, xác minh nhanh, giả định an ninh chín muồi; điểm yếu chính của nó - tính toán dấu phẩy động phía ký, đã tồn tại giải pháp kỹ thuật khả thi. Nếu bây giờ bắt buộc phải chọn sơ đồ chữ ký dựa trên lattice cho Bitcoin, chúng tôi sẽ chọn Falcon-1024.
Về hiện tại, quan điểm của chúng tôi vẫn nhất quán với báo cáo về chữ ký dựa trên băm: con đường thận trọng ngắn hạn vẫn là chữ ký dựa trên băm, giả định an ninh chín muồi nhất, rủi ro thấp nhất, phù hợp làm sơ đồ chuyển tiếp. Sau khi FN-DSA chính thức hoàn thiện, có đặc tả ổn định, thư viện mã đã được kiểm toán, hỗ trợ ví phần cứng, Falcon so với chữ ký băm thuần túy sẽ mang lại cải thiện đáng kể; cũng có thể triển khai hỗn hợp, để hai hệ thống chữ ký bổ sung cho nhau.
