Tác giả: Blockstream Team
Biên dịch: Saoirse, Foresight News
Blockstream Research đã công bố một báo cáo nghiên cứu toàn diện về chữ ký dựa trên lưới (lattice-based signatures) 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 cốt lõi và các đề xuất liên quan. Báo cáo đầy đủ có thể được truy cập tại đây.
Chữ ký số là cơ chế cốt lõi để ủy quyền giao dịch Bitcoin, hiện được thực hiện bởi chữ ký Schnorr và ECDSA 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 này ra đời vẫn còn được tranh luận rộng rãi, chúng ta cần xây dựng một kế hoạch triển khai chữ ký hậu lượng tử khả thi trước khi vấn đề thực sự xảy ra.
Các giải pháp chữ ký dựa trên lưới là ứng cử viên nổi bật để thay thế các chữ ký hiện tại. Mật mã học dựa trên lưới đã 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 thập kỷ. Trong hệ thống mật mã hậu lượng tử, chữ ký dựa trên lưới có nhiều ưu điểm: tổng kích thước 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ó hứa hẹn hỗ trợ chữ ký đa thành phần (multisig), chữ ký ngưỡng (threshold signature) và các bằng chứng ngắn gọn (succinct proof) trong tương lai.
Báo cáo này nghiên cứu ba giải pháp: Dilithium, Falcon và Hawk. Dành cho độc giả chưa quen với mật mã lưới, chúng tôi trình bày ý tưởng thiết kế của từng giải pháp, giới thiệu đầy đủ quy trình thuật toán, và phân tích từ các khía cạnh như bảo mật, hiệu suất, triển khai thực tế (ví dụ: dẫn xuất khóa trong ví). Trong ba giải pháp này, giải pháp 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 giải pháp chữ ký cho Bitcoin có những ràng buộc riêng. Lần đánh giá này tập trung vào bốn tiêu chí 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 (output) đượ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 đủ (full node) 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ẽ tạo gánh nặng cho toàn mạng.
- Độ phức tạp triển khai: Khả năng triển khai an toàn của một giải pháp là tối 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 tinh vi, một khi triển khai sai hoặc gặp phải các cuộc tấn công phân tích thời gian (timing analysis) như tấn công kênh bên (side-channel), có thể làm lộ khóa riêng tư. Để di chuyển suôn sẻ, độ phức tạp triển khai là yếu tố không thể bỏ qua.
- Rủi ro triển khai: 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 giải pháp ứng cử sử dụng SHAKE, trong khi 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: Đa số ví Bitcoin sử dụng cơ chế xác định phân cấp BIP-32: từ một khóa chủ (master public key), có thể dẫn xuất vô số khóa con (child keys) mà không cần chạm vào khóa riêng tư. Hiện tại, các giải pháp chữ ký hậu lượng tử đã được chuẩn hóa đều không hỗ trợ nguyên bản tính năng này. Do đó, chúng tôi nghiên cứu chi phí phải trả để bổ sung khả năng này; đồng thời xem xét các biến thể giải pháp không chuẩn, chúng có thể mang lại nhiều lợi ích hơn.
Nên Chọn Cấp Độ Bảo Mật Nào?
Trước khi so sánh kích thước, cần xác định cấp độ bảo mật mục tiêu, và lựa chọn này không đơn giản như vẻ ngoài. NIST phân chia cấp độ bảo mật thành các cấp 1-5; cấp độ càng cao thì bảo mật 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 sử dụng tiêu chuẩn bảo mật cấp 3. Các đầ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 độ bảo mật thực tế của giải pháp, tài sản sẽ bị khóa bởi các khóa đã bị suy yếu, phơi bày lâu dài trước rủi ro. Giả định mật mã lưới đã trải qua gần ba thập kỷ 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 mật mã lưới vẫn còn nhiều điểm yếu có thể bị khai thác trong các cuộc tấn công tương lai, chúng ta không nên đặt cược toàn bộ an ninh cho tương lai xa vào đó.
Các sản phẩm chính thống cũng đưa ra đánh giá tương tự. Giao thức PQ3 của iMessage từ Apple đã bỏ hoàn toàn tham số mật mã lưới cấp 1, sử dụng toàn bộ tham số cấp 3 và 5; Cloudflare sử dụng ML-KEM-768 (cấp 3) trong triển khai TLS hậu lượng tử, 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 dung sai bảo mật cho hàng chục năm phân tích mật mã sắp tới. Trong khi đó, thời gian bảo mật của Bitcoin còn dài hơn cả hai trường hợp trên.
Nâng cấp độ bảo mật cần trả giá. Ví dụ, từ cấp 2 lên cấp 3 của Dilithium, tổng kích thước sẽ tăng khoảng 1.5 kilobyte. Báo cáo so sánh tất cả các bộ tham số ở mọi cấp độ bảo mật, độc giả có thể tự cân nhắc. Trường hợp của Hawk chứng minh rằng việc cân nhắc bảo mật thận trọng không chỉ là lý thuyết suông.
Chi Tiết Các Giải Pháp Ứng Cử
Dilithium: Giải Pháp 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 (commitment-challenge-response) của chữ ký Schnorr lên số học mô-đun lưới.
Đặ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 tính vòng, nhân ma trận-vectơ, băm, làm tròn, không có phép tính dấu phẩy động và cũng không cần lấy mẫu Gauss rời rạc. Điều này giúp dễ dàng viết được mã triển khai an toàn, thời gian không đổi (constant-time). Nó cũng là giải pháp ứng cử đượ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 khá lớn. ML-DSA-65 cấp bảo mật 3 có khóa công khai 1952 byte, chữ ký 3309 byte, tổng cộng 5261 byte, khoảng gấp 55 lần tổng kích thước khóa công khai, khóa riêng và chữ ký gốc của Bitcoin, là giải pháp có kích thước lớn nhất trong ba giải pháp cùng cấp bảo mật.
Điều có giá trị nhất của Dilithium đối với Bitcoin: đây là giải pháp duy nhất trong ba giải pháp gần như đạt được việc dẫn xuất khóa theo phong cách BIP-32. Cấu trúc khóa có thể tái ngẫu nhiên hóa DilithiumRK, cho phép tạo khóa con từ khóa cha chỉ dựa trên thông tin công khai. Báo cáo phân tích ba biến thể, bao gồm DilithiumRKS mà chúng tôi đề xuất, trong đó logic dẫn xuất được đặt hoàn toàn bên trong phần mềm ví, trên chuỗi chỉ cần bộ xác minh tiêu chuẩn xử lý chữ ký ML-DSA thông thường. Tuy nhiên, cả ba biến thể đều chưa đạt tiêu chuẩn để triển khai: hai biến thể cần sửa đổi bộ xác minh, bản thân DilithiumRKS còn thiếu bằng chứng đầy đủ về tính không thể giả mạo (unforgeability); tất cả các giải pháp đều phụ thuộc vào một ma trận chung trên 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ẽ liên kết bảo mật của tất cả các khóa với cùng một thể hiện (instance). Chúng tôi cho rằng hiện tại, dẫn xuất khóa công khai dựa trên Dilithium chỉ thuộc dạng chứng minh khái niệm (proof-of-concept) và không thể triển khai thực tế.
Falcon: Giải Pháp Kích Thước Gọn Nhẹ
Falcon được NIST lựa chọn, tên chuẩn hóa là FN-DSA, và là giải pháp gọn nhẹ nhất trong ba giải pháp. Falcon-512 cấp bảo mật 1 có tổng khóa công khai và chữ ký là 1563 byte; Falcon-1024 cấp 5 có tổng 3073 byte. Falcon-1024 với dung sai bảo mật cao hơn thậm chí còn có kích thước nhỏ hơn Dilithium cấp 3.
Falcon áp dụng cách tiếp cận khác với Dilithium: dựa trên mô hình hash-and-sign của lưới NTRU. Khóa riêng tư của người ký là một cơ sở ngắn (short basis) của lưới; thông điệp được băm và á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 vectơ trên lưới rất gần điểm đó. Điểm và vectơ lân cận đó cùng tạo thành chữ ký; việc xác minh chỉ kiểm tra xem vectơ có thuộc lưới đó không và khoảng cách có đủ gần không. Thách thức triển khai nằm ở việc tìm vectơ mà không được làm lộ thông tin về cơ sở. Các giải pháp ban đầu như GGH, NTRUSign lấy trực tiếp điểm lưới gần nhất, mỗi lần ký sẽ làm lộ một phần thông tin hình học. Falcon sử dụng khuôn khổ GPV, lấy mẫu vectơ 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 lên đáng kể.
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, yêu cầu 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à lỗ hổng bảo mật: 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 (digest), người ký tuyệt đối không xuất ra hai tập hợp vectơ ngắn khác nhau; một khi chữ ký trở thành chữ ký xác định (deterministic signature), sự khác biệt về làm tròn dấu phẩy động do nền tảng sẽ phá vỡ điều kiện đó. Có giải pháp khả thi: Falcon xác định có thể sử dụng mô phỏng số nguyên thay thế cho dấu phẩy động phần cứng, tạo ra chữ ký hoàn toàn nhất quán trên tất cả nền tảng. Cái giá phải trả là tốc độ ký giảm khoảng 15 lần, tốc độ tạo khóa giảm khoảng 2 lần.
Điều quan trọng là, quá trình xác minh không bị ảnh hưởng: việc xác minh Falcon sử dụng toàn bộ phép tính số nguyên, kết quả xác định, đồng thời cũng là giải pháp ứng cử có tốc độ xác minh nhanh nhất. Đặc tính không đối xứng này rất thân thiện với Bitcoin: chữ ký được ví thực hiện một lần khi chi tiêu giao dịch, trong khi mỗi chữ ký phải được tất cả các nút đầy đủ trên mạng xác minh. Việc ký chậm hơn 15 lần thuộc chi phí tần suất thấp, đổi lại khả năng tái tạo đa nền tảng và 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 là trở ngại có thể giải quyết bằng biện pháp kỹ thuật, không phải là lỗi 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 5. Dựa trên cân nhắc dung sai bảo mật, chúng tôi đề xuất Falcon-1024. Thứ hai, việc ký sẽ tiêu thụ nhiều bộ nhớ: bộ lấy mẫu của 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 theo từng nhánh một cách động, nén dung lượng bộ nhớ xuống còn 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: Giải Pháp Đã Thất Bại
Mục tiêu của Hawk là kết hợp ưu điểm của hai giải pháp kia: chữ ký Hawk-512 chỉ có 555 byte, nhỏ hơn cả Falcon; phía ký sử dụng toàn bộ phép tính số nguyên, chiếm dụng bộ nhớ tối thiểu chỉ 6 kilobyte. Nó cũng là ứng cử viên dựa trên lưới duy nhất còn sót lại ở vòng thứ ba của cuộc thi chữ ký bổ sung NIST, và báo cáo dành nhiều trang để giới thiệu giải pháp này.
Cái giá nằm ở giả định bảo mật. Nó không tiếp tục sử dụng các bài toán NTRU, SIS đã trải qua hàng chục năm phân tích mật mã, mà dựa vào bài toán đẳng cấu lưới (lattice isomorphism problem) và giả định one-more-SVP, những giả định này có lịch sử nghiên cứu tương đối ngắn hơn.
Ngay trước khi báo cáo hoàn thành, Straznickas và Weis từ Anthropic đã phát hiện cấu trúc lưới của Hawk có lỗ hổng cấu trúc: chiều (dimension) 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ế. Độ an toàn khôi phục khóa của các bộ tham số ứng cử 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 (end-to-end) đầy đủ đối với tham số thử thách HAWK-256 được sử dụng cho phân tích mật mã; 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 giải pháp khỏi quy trình NIST; nhóm cho biết, nếu sửa lỗi bằng cách tăng gấp đôi tham số, lợi 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 chương 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 hoàn toàn 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 minh chứng trực quan lý do chúng tôi kiên trì với dung sai bảo mật thận trọng: một giải pháp 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 đáng kể cấp độ bảo mật ước tính của nó.
Bảng Đối Chiếu Các Giải Pháp
Tất cả các giải pháp trong bảng trên (bao gồm SPHINCS+) đều là chữ ký không trạng thái (stateless signature): người ký không cần ghi lại các chữ ký trước đó. Các chữ ký dựa trên 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ý; có thể tham khảo bá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 Thực Tế
Falcon thiếu giải pháp dẫn xuất khóa khả dụng. Hiện tại, giải pháp duy nhất theo phong cách BIP-32 cho Falcon được công bố công khai, sẽ tái ngẫu nhiên hóa cơ sở khóa riêng tư, làm tăng đáng kể giới hạn chuẩn (norm) của chữ ký, khiến chữ ký trên chuỗi phình lên khoảng 23.7 kilobyte. Hơn nữa, tham số của giải pháp này không đạt điều kiện an toàn của chính nó, nếu sửa vấn đề này, kích thước sẽ còn tăng vọt 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 đề chưa được giải quyết có giá trị nhất mà báo cáo đề cập.
Tiêu chuẩn Falcon chưa được hoàn thiện. Mặc dù NIST đã chọn Falcon, nhưng dự thảo FN-DSA vẫn chưa chính thức được công bố. Sau khi quá trình chuẩn hóa hoàn tất, mới có các bản 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 sẽ giảm thiểu 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 công bố, trước thời điểm đó 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ỏ (rejection sampling) để bù đắp, tổng kích thước cấp 1 được nén xuống 1114 byte, cấp 5 xuống 2387 byte, giảm hơn nữa so với Falcon gốc. 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 và 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 bằng chứng về tính không thể giả mạo mạnh (strong unforgeability) của giải pháp phái sinh có 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 giải pháp ưu việt hơn không? Ngoài các giải pháp trên, dòng Fiat-Shamir bắt nguồn từ BLISS năm 2013, kết quả mới nhất do Gärtner đề xuất 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 Falcon. Gốc rễ của việc khó triển khai kỹ thuật dòng này nằm ở vấn đề an toàn triển khai: BLISS từng bị tấn công kênh bên do lấy mẫu Gauss không thời gian không đổi; các giải pháp tiếp theo đều chưa 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 giải pháp này chỉ có sức hấp dẫn về mặt lý thuyết và không phù hợp để triển khai.
Chữ ký dựa trên lưới và chữ ký dựa trên băm có thể bổ sung cho nhau. Chữ ký dựa trên lưới có thể là thành phần của giải pháp 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+ có kích thước vài KB; thay thế bằng chữ ký Falcon (hoặc Falcon-WS) sẽ có kích thước nhỏ hơn, xác minh nhanh hơn, giảm đáng kể chi phí đường dẫn khôi phục tần suất thấp, trong khi đườ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ứ hạng ưu nhược của các giải pháp ứng cử dựa trên lưới rất rõ ràng: Hawk đã rút khỏi cuộc cạnh tranh sau cuộc tấn công của nhóm Anthropic; Dilithium có độ khó triển khai thấp nhất và là giải pháp 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 và giả định bảo mật đã 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ý, đã có giải pháp kỹ thuật khả thi. Nếu bây giờ buộc phải chọn một giải pháp chữ ký dựa trên lưới 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 thống nhất 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, với giả định bảo mật chín muồi nhất, rủi ro thấp nhất, phù hợp làm giải pháp chuyển tiếp. Sau khi FN-DSA chính thức hoàn thiện, có quy chuẩn ổn định, thư viện mã đã được kiểm toán, hỗ trợ ví phần cứng, Falcon sẽ mang lại cải thiện đáng kể so với chữ ký dựa trên băm thuần túy; cũng có thể triển khai hỗn hợp, để hai hệ thống chữ ký bổ sung cho nhau.
