Bitcoin chống lại máy tính lượng tử thế nào? So sánh ba sơ đồ chữ ký dựa trên lưới

Tác giả gốc: Nhóm Blockstream

Biên soạn gốc: 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 cho Bitcoin. Bài viết này tóm tắt nội dung nghiên cứu, các phát hiện chính và các khuyến nghị liên quan. Có thể truy cập báo cáo đầy đủ tại đây.

Chữ ký số là cơ chế cốt lõi để ủy quyền giao dịch Bitcoin, và các chữ ký Schnorr và ECDSA hiện đang được sử dụng cho mục đích này có chi phí cực kỳ 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ù vẫn còn tranh luận về thời điểm những cỗ máy như vậy sẽ xuất hiện, chúng ta cần phát triển 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 sơ đồ chữ ký dựa trên lưới là một ứng cử viên phổ biến để thay thế các chữ ký hiện có. Mật mã 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 phát triển trong gần ba thập kỷ. Trong mật mã hậu lượng tử, chữ ký dựa trên lưới mang lại một số lợi thế: tổng kích thước của khóa công khai và chữ ký có thể thấp tới dưới 1,6 kilobyte, và cấu trúc đại số của chúng hứa hẹn hỗ trợ đa chữ ký, chữ ký ngưỡng và các bằng chứng ngắn gọn trong tương lai.

Báo cáo này nghiên cứu ba sơ đồ: Dilithium, Falcon và Hawk. Đối với những độc giả chưa quen với mật mã lưới, chúng tôi giải thích lý do thiết kế của từng sơ đồ, cung cấp mô tả đầy đủ về quy trình thuật toán và phân tích chúng từ các khía cạnh như bảo mật, hiệu suất và triển khai thực tế (ví dụ: dẫn xuất khóa ví). Trong ba sơ đồ, sơ đồ nào thực sự có thể được triển khai trên blockchain Bitcoin?

Tiêu chí đánh giá

Bitcoin có những ràng buộc riêng đối với việc lựa chọn sơ đồ chữ ký, và đá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 được chi tiêu, cả khóa công khai và chữ ký đều được ghi lại trên chuỗi, và 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 quan trọng không kém: mọi chữ ký đều được xác minh bởi tất cả các nút trong mạng, và việc xác minh chậm sẽ tạo gánh nặng cho toàn bộ mạng.
• Độ phức tạp triển khai: Việc sơ đồ có thể được triển khai một cách an toàn hay không là rất quan trọng. Nếu thiết kế yêu cầu số học dấu phẩy động hoặc lấy mẫu Gaussian tinh tế, một lỗi triển khai hoặc một cuộc tấn công kênh bên như phân tích thời gian có thể làm rò rỉ khóa. Để đạt được quá trình chuyển đổi suôn sẻ, độ phức tạp triển khai là một yếu tố không thể bỏ qua.
• Rủi ro triển khai: Khi thực sự tích hợp vào Bitcoin, có 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 ứng cử viên sử dụng SHAKE, trong khi Bitcoin sử dụng SHA-256), khả năng tái tạo kết quả chữ ký trên các nền tảng và liệu quy 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: Phần lớn các ví Bitcoin sử dụng cơ chế phân cấp xác định BIP-32: từ một khóa công khai chính, có thể dẫn xuất vô số khóa công khai con mà không cần truy cập vào khóa riêng. Hiện tại, không có sơ đồ chữ ký hậu lượng tử được chuẩn hóa nào hỗ trợ tính năng này một cách tự nhiên, vì vậy chúng tôi nghiên cứu chi phí để thêm khả năng này; chúng tôi cũng xem xét các biến thể sơ đồ phi tiêu chuẩn khác nhau có thể mang lại lợi ích bổ sung.

Nên chọn mức bảo mật nào?

Trước khi so sánh kích thước, trước tiên chúng ta phải xác định mức bảo mật mục tiêu, và lựa chọn này không đơn giản như vẻ bề ngoài. NIST phân loại các mức bảo mật từ 1 đến 5; mức cao hơn cung cấp bảo mật mạnh hơn nhưng cũng có kích thước khóa và chữ ký lớn hơn.

Chúng tôi tin rằng Bitcoin nên áp dụng ít nhất mức bảo mật 3. Các đầu ra Bitcoin có thể không được chi tiêu trong nhiều thập kỷ, và nếu những tiến bộ trong phân tích mật mã làm giảm mức bảo mật thực tế của sơ đồ, tài sản sẽ bị khóa bởi các khóa yếu và phải đối mặt với rủi ro dài hạn. Các giả định dựa trên lưới đã chịu đựng gần ba thập kỷ phân tích mật mã công khai, lâu hơn 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 hướng tấn công trong tương lai, và chúng ta không nên đặt toàn bộ bảo mật dài hạn của mình vào nó.

Các sản phẩm chính thống lớn đã đưa ra đánh giá tương tự. Giao thức iMessage PQ3 của Apple trực tiếp loại bỏ các tham số lưới mức 1 và sử dụng các tham số mức 3 và mức 5 trong toàn bộ; Cloudflare sử dụng ML-KEM-768 (mức 3) trong triển khai TLS hậu lượng tử của mình, tuyên bố rằng mặc dù mức 1 hiện có vẻ an toàn, cần phải dự trữ biên độ bảo mật cho nhiều thập kỷ phân tích mật mã trong tương lai. Chân trời bảo mật của Bitcoin thậm chí còn dài hơn cả hai.

Việc nâng mức bảo mật đi kèm với chi phí. Ví dụ, chuyển Dilithium từ mức 2 lên mức 3 làm tăng tổng kích thước khoảng 1,5 kilobyte. Báo cáo so sánh các bộ tham số ở tất cả các mức bảo mật, cho phép độc giả tự cân nhắc các sự đánh đổi. Trường hợp của Hawk chứng minh rằng các cân nhắc bảo mật thận trọng không chỉ là lý thuyết.

Phân tích chi tiết các sơ đồ ứng cử viên

Dilithium: Một thiết kế đơn giản

Dilithium, được NIST chuẩn hóa thành ML-DSA trong FIPS 204, chuyển mô hình cam kết-thách thức-phản hồi của chữ ký Schnorr sang số học lưới mô-đun.

Đặc điểm lớn nhất của nó là sự đơn giản. Tất cả các phép toán trong Dilithium đều là phép toán số nguyên: phép toán vành, nhân ma trận-vector, băm và làm tròn. Không có số học dấu phẩy động và không có lấy mẫu Gaussian rời rạc. Việc viết các triển khai an toàn, thời gian hằng số dễ dàng hơn. Đây cũng là ứng cử 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.

Sự đánh đổi là kích thước lớn hơn. Ở mức bảo mật 3, ML-DSA-65 có khóa công khai 1952 byte và chữ ký 3309 byte, tổng cộng 5261 byte, gấp khoảng 55 lần tổng kích thước của khóa công khai/riêng tư và chữ ký gốc của Bitcoin, khiến nó trở thành sơ đồ lớn nhất trong ba sơ đồ ở cùng mức bảo mật.

Đối với Bitcoin, khía cạnh giá trị nhất của Dilithium là nó là sơ đồ duy nhất trong ba sơ đồ gần như triển khai đượ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 có thể tạo khóa con từ khóa cha chỉ sử dụng thông tin công khai. Báo cáo phân tích ba biến thể, bao gồm DilithiumRKS do chúng tôi đề xuất, trong đó logic dẫn xuất hoàn toàn nằm trong phần mềm ví và chuỗi chỉ yêu cầu một trình xác minh tiêu chuẩn để xử lý các chữ ký ML-DSA thông thường. Tuy nhiên, không có biến thể nào trong ba biến thể sẵn sàng cho sản xuất: hai biến thể yêu cầu sửa đổi trình xác minh, và bản thân DilithiumRKS thiếu bằng chứng không thể giả mạo hoàn chỉnh; tất cả các sơ đồ đều dựa vào một ma trận chia sẻ trên toàn mạng, về mặt hình thức là an toàn theo giả định Module-LWE nhưng ràng buộc bảo mật của tất cả các khóa vào một thể hiện duy nhất. Chúng tôi tin rằng dẫn xuất khóa công khai dựa trên Dilithium hiện chỉ là một bằng chứng khái niệm và không thể triển khai trong thực tế.

Falcon: Một sơ đồ nhỏ gọn

Falcon, được NIST lựa chọn và chuẩn hóa thành FN-DSA, là sơ đồ nhỏ gọn nhất trong ba sơ đồ. Ở mức bảo mật 1, Falcon-512 có tổng kích thước khóa công khai và chữ ký là 1563 byte; ở mức 5, Falcon-1024 tổng cộng 3073 byte. Falcon-1024, với biên độ bảo mật cao hơn, thậm chí còn nhỏ hơn Dilithium mức 3.

Falcon áp dụng một cách tiếp cận khác với Dilithium: mô hình băm-và-ký dựa trên lưới NTRU. Khóa riêng của người ký là một cơ sở ngắn của lưới; thông điệp được băm thành một điểm trong không gian, và người ký sử dụng cơ sở ngắn để tìm một vector lưới gần điểm đó. Điểm và vector gần đó cùng nhau tạo thành chữ ký; việc xác minh chỉ kiểm tra rằng vector thuộc về lưới và đủ gần. Thách thức triển khai là tìm vector mà không làm rò rỉ thông tin về cơ sở. Các sơ đồ ban đầu GGH và NTRUSign trực tiếp chọn các điểm lưới gần đó, làm rò rỉ một số thông tin hình học với mỗi chữ ký. Falcon áp dụng khung GPV, lấy mẫu các vector gần đó từ phân phối Gaussian, điều này có thể chứng minh làm cho đầu ra được 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 của bộ lấy mẫu tăng đáng kể.

Bộ lấy mẫu là điểm yếu kỹ thuật của Falcon. Nó hoạt động trong miền Fourier phức tạp và yêu cầu tính toán dấu phẩy động. Các bộ xử lý, trình biên dịch và tùy chọn tối ưu hóa biên dịch khác nhau có thể gây ra kết quả 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à mối lo ngại về bảo mật: bằng chứng bảo mật GPV yêu cầu người ký không bao giờ xuất ra hai vector ngắn khác nhau cho cùng một bản tóm tắt; nếu chữ ký trở nên xác định, sự khác biệt làm tròn dấu phẩy động do nền tảng gây ra sẽ vi phạm điều kiện này. Có một giải pháp khả thi: Falcon xác định có thể thay thế dấu phẩy động phần cứng bằng mô phỏng số nguyên, tạo ra các chữ ký giống hệt nhau trên tất cả các nền tảng. Chi phí là tốc độ ký chậm hơn khoảng 15 lần và tốc độ tạo khóa chậm hơn khoảng 2 lần.

Quan trọng là, việc xác minh không bị ảnh hưởng: xác minh Falcon hoàn toàn dựa trên số nguyên, xác định và cũng là nhanh nhất trong số các ứng cử viên. Tính chất bất đối xứng này rất thân thiện với Bitcoin: việc ký được thực hiện một lần bởi ví khi chi tiêu giao dịch, trong khi mọi chữ ký đều được xác minh bởi tất cả các nút đầy đủ trong mạng. Việc ký chậm hơn 15 lần là chi phí tần suất thấp, và đổi lại chúng ta có được khả năng tái tạo đa nền tảng và số học số nguyên, điều mà chúng tôi coi là một sự đánh đổi hợp lý. Do đó, vấn đề dấu phẩy động là một trở ngại có thể giải quyết bằng các biện pháp kỹ thuật, không phải là một lỗ hổng chết người.

Hai điểm cần lưu ý: do các ràng buộc cấu trúc, Falcon không có tham số mức 3; người ta phải chọn mức 1 hoặc mức 5. Dựa trên cân nhắc biên độ bảo mật, chúng tôi khuyến nghị Falcon-1024. Thứ hai, việc ký tiêu thụ một lượng lớn bộ nhớ: bộ lấy mẫu cho bộ tham số 1024 dựa vào một cây được 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 theo từng nhánh một cách động, giảm mức sử dụng bộ nhớ xuống 16 kilobyte, nhưng thời gian ký tăng gấp đôi. Việc ký chậm hơn trên thiết bị phần cứng là một chi phí thực tế, nhưng vẫn có thể chấp nhận được.

Hawk: Một sơ đồ thất bại

Hawk nhằm mục đích kết hợp các ưu điểm của hai sơ đồ còn lại: chữ ký Hawk-512 chỉ có 555 byte, nhỏ hơn Falcon; việc ký hoàn toàn dựa trên số nguyên, với dung lượng bộ nhớ tối thiểu chỉ 6 kilobyte. Đây cũng là ứng cử viên dựa trên lưới duy nhất còn lại trong vòng thứ ba của cuộc thi chữ ký bổ sung của NIST, và báo cáo dành không gian đáng kể cho sơ đồ này.

Sự đánh đổi nằm ở các giả định bảo mật. Nó không dựa vào các bài toán NTRU hoặc SIS đã chịu nhiều thập kỷ phân tích mật mã, mà dựa vào bài toán đẳng cấu lưới và giả định one-more-SVP, cả hai đều có lịch sử nghiên cứu tương đối ngắn.

Ngay trước khi báo cáo được hoàn thiện, Straznickas và Weis từ Anthropic đã phát hiện ra một lỗ hổng cấu trúc trong cấu trúc lưới của Hawk: chiều của bài toán SVP thực sự cần giải để khôi phục khóa chỉ bằng một nửa so với dự định của các nhà thiết kế. Các bit bảo mật khôi phục khóa của các bộ tham số ứng cử viên đã bị suy yếu đáng kể. Các nhà nghiên cứu đã hoàn thành một cuộc tấn công khôi phục khóa đầu cuối đầy đủ trên tham số thách thức HAWK-256 được sử dụng để phân tích mật mã; ngay cả khi bị tấn công, HAWK-512 và HAWK-1024 được đề xuất chính thức vẫn không thể bị phá vỡ trong thực tế. Nhóm Hawk đã xác nhận tính hợp lệ của cuộc tấn công và rút sơ đồ khỏi quy trình NIST; nhóm tuyên bố rằng nếu lỗ hổng được khắc phục bằng cách nhân đôi tham số, lợi thế kích thước ban đầu của Hawk sẽ hoàn toàn biến mất.

Báo cáo giữ lại phần Hawk vì cuộc tấn công nhắm vào các tính chất đại số của một trường số cụ thể và không hoàn toàn phủ nhận mô hình thiết kế. Liệu một thiết kế lại có thể tránh được lỗ hổng hay không vẫn là một câu hỏi mở. Sự cố Hawk cũng xác nhận một cách trực quan sự kiên định của chúng tôi về biên độ bảo mật thận trọng: một sơ đồ có kích thước và tốc độ tuyệt vời, đã trải qua nhiều vòng chuẩn hóa, có thể bị giảm mạnh mức bảo mật ước tính chỉ bởi một bài báo.

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 các chữ ký trướ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 yêu cầu duy trì trạng thái chữ ký; xem báo cáo đặc biệt về chữ ký dựa trên băm để so sánh.

Nhiều trở ngại vẫn còn cho việc triển khai

Falcon thiếu một sơ đồ dẫn xuất khóa khả dụng. Sơ đồ dẫn xuất kiểu BIP-32 duy nhất được công khai cho Falcon tái ngẫu nhiên hóa cơ sở khóa riêng, khiến giới hạn trên của chuẩn chữ ký tăng mạnh, và chữ ký trên chuỗi phình to lên khoảng 23,7 kilobyte. Hơn nữa, các tham số của sơ đồ không đáp ứng các điều kiện bảo mật của chính nó, và việc khắc phục vấn đề này sẽ làm tăng thêm kích thước. Hiện không có triển khai dẫn xuất khóa công khai Falcon khả thi, đây cũng là vấn đề mở có giá trị nhất được xác định trong báo cáo.

Tiêu chuẩn Falcon chưa được hoàn thiện. Mặc dù NIST đã chọn Falcon, dự thảo FN-DSA chưa được công bố chính thức. Chỉ sau khi quá trình chuẩn hóa hoàn tất, chúng ta mới có các triển khai được kiểm toán, các vector kiểm thử và hỗ trợ cấp phần cứng. Việc áp dụng rộng rãi có thể giảm rủi ro và khó khăn khi tích hợp vào lớp đồng thuận của Bitcoin. Chúng tôi khuyến nghị chờ đợi bản phát hành chính thức của FN-DSA; cho đến lúc đó, Falcon vẫn ở trạng thái thay đổi.

Biến thể Falcon-WS: Biến thể này nới lỏng các tham số nội bộ và dựa vào lấy mẫu loại bỏ để bù đắp, nén tổng kích thước xuống 1114 byte ở mức 1 và 2387 byte ở mức 5, giảm thêm kích thước 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 thêm xác nhận phân tích mật mã. Nghiên cứu hiện có đã tìm thấy lỗ hổng trong các bằng chứng không thể giả mạo mạnh của các sơ đồ dẫn xuất của nó (không thể giả mạo thông thường không bị ảnh hưởng).

Liệu các sơ đồ tốt hơn sẽ xuất hiện trong tương lai? Ngoài các sơ đồ trên, họ Fiat-Shamir có từ BLISS năm 2013. Kết quả mới nhất của Gärtner tại CRYPTO 2025, dựa trên các giả định đã chín muồi, có kích thước giấy tờ tương đương với Falcon. Nguyên nhân gốc rễ của khó khăn trong việc kỹ thuật hóa họ này nằm ở bảo mật triển khai: BLISS đã bị phá vỡ bởi các cuộc tấn công kênh bên do lấy mẫu Gaussian không thời gian hằng số; các sơ đồ sau đó chưa giải quyết triệt để vấn đề này, và kết quả mới nhất cũng gợi ý rằng việc bảo vệ bước lấy mẫu thậm chí còn khó khăn hơn. Cho đến khi vấn đề được giải quyết, các sơ đồ như vậy chỉ 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à dựa trên băm có thể bổ sung cho nhau. Chữ ký dựa trên lưới có thể đóng vai trò là thành phần của các sơ đồ lai. 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+ vài kilobyte; thay thế chúng bằng chữ ký Falcon (hoặc Falcon-WS) sẽ nhỏ hơn và xác minh nhanh hơn, giảm đáng kể chi phí của đường dẫn khôi phục không thường xuyên mà không ảnh hưởng đến đường dẫn sử dụng hàng ngày.

Kết luận nghiên cứu

Xếp hạng các ứng cử viên dựa trên lưới rất rõ ràng: Hawk đã rút khỏi cuộc thi sau cuộc tấn công của nhóm Anthropic; Dilithium có độ khó triển khai thấp nhất và là sơ đồ duy nhất có nền tảng nghiên cứu về dẫn xuất khóa, nhưng kích thước của nó không thân thiện với chi phí trên chuỗi của Bitcoin; Falcon kết hợp kích thước nhỏ gọn, xác minh nhanh và các giả định bảo mật đã chín muồi; điểm yếu chính của nó—số học dấu phẩy động ở phía ký—đã có giải pháp kỹ thuật khả thi. Nếu phải chọn một sơ đồ chữ ký dựa trên lưới cho Bitcoin ngày hôm nay, chúng tôi sẽ chọn Falcon-1024.

Hiện tại, quan điểm của chúng tôi nhất quán với báo cáo về chữ ký dựa trên băm: lộ trình ngắn hạn thận trọng vẫn là chữ ký dựa trên băm, với các giả định bảo mật chín muồi nhất và rủi ro thấp nhất, phù hợp làm sơ đồ chuyển tiếp. Một khi FN-DSA được hoàn thiện chính thức, với các đặc tả ổn định, cơ sở mã được kiểm toán và hỗ trợ ví phần cứng, Falcon sẽ mang lại những cải tiến đáng kể so với chữ ký dựa trên băm thuần túy; cũng có thể áp dụng triển khai lai, cho phép hai hệ thống chữ ký bổ sung cho nhau.