Giới thiệu về SPHINCS+

Tác giả: NIFTY

Nguồn: https://insider.btcpp.dev/p/sphincs

Tuần trước, Presido Bitcoin, một không gian làm việc chung chỉ dành cho Bitcoin tại San Francisco, đã tổ chức một hội nghị chuyên ngành về Bitcoin và điện toán lượng tử. @roasbeef , người bảo trì chính của máy trạmbtcd và lnd , đồng thời là Giám đốc Công nghệ của Lightning Labs , đã trình bày đề xuất bổ sung một lược đồ chữ ký an toàn lượng tử, SPHINCS+, Bitcoin. Trong báo cáo hôm nay, chuyên gia giao thức @niftynei của Insider đã giải thích về đề xuất này.

Các vấn đề an ninh lượng tử

Hầu hết tiền trên blockchain Bitcoin đều được bảo vệ bằng private key . Để giao dịch Bitcoin (chuyển tiền) của bạn được xác nhận blockchain , bạn cần chứng minh thẩm quyền chi tiêu số tiền đó bằng cách cung cấp chữ ký. Chữ ký hợp lệ chỉ có thể được tạo bởi người có quyền truy cập vào private key chính xác.

Theo một nghĩa nào đó, Bitcoin cũng đạt được "bảo mật thông qua việc che giấu". "Che giấu" ở đây ám chỉ độ khó của việc đoán private key. Số lượng các số có thể là private key là vô cùng lớn. Việc đoán một private key duy nhất sẽ tốn rất nhiều thời gian và công sức đến mức vượt quá khả năng của bất kỳ con người nào trong một khoảng thời gian hợp lý (ví dụ: hàng trăm năm).

Tuy nhiên, các khóa Bitcoin hiện tại dựa trên các phương trình toán học dựa trên đường cong elliptic. Đường cong elliptic là một lựa chọn tốt để tạo khóa công khai và khóa riêng tư vì chúng thường an toàn hơn phương pháp phân tích thừa số nguyên tố (một "hệ thống toán học" khác làm cơ sở cho mật mã khóa công khai và khóa riêng tư), và khóa công khai và khóa riêng tư cũng nhỏ hơn.

Tuy nhiên, mật mã đường cong elliptic cũng có một vấn đề. Thuật toán Shor, được Peter Shor phát minh năm 1994, dựa trên phép biến đổi Fourier và cho phép một máy tính lượng tử với đủ Bitcoin(qubit) có thể nhanh chóng tính toán private key của bất kỳ khóa công khai nào.

Thuật toán Shor cho thấy chúng ta biết cách phá vỡ mật mã đường cong elliptic, nhưng các công cụ để làm điều đó vẫn chưa tồn tại. Liệu những công cụ như vậy có xuất hiện hay không và khi nào sẽ xuất hiện vẫn là một chủ đề gây tranh cãi sôi nổi, không chỉ trong cộng đồng Bitcoin mà còn trong cộng đồng mật mã nói chung. Tính bảo mật của mọi private key được sử dụng để lưu trữ Bitcoin phụ thuộc vào thực tế là sẽ không ai có thể tiếp cận một công cụ có khả năng thực thi thuật toán Shor trong tương lai không xác định.

Sự đồng thuận chung là vào một thời điểm nào đó trong tương lai, Bitcoin sẽ cần phải chuyển sang hệ thống mật mã khóa công khai-riêng hậu lượng tử . Đề xuất của @roasbeef tại Presidio tuần trước dựa trên lược đồ chữ ký băm "SPHINCS+". Hãy cùng xem xét nhanh cách thức hoạt động của nó và lý do tại sao nó có thể là một lựa chọn tốt để bảo mật Bitcoin.

Lượng tử an toàn, nhưng dữ liệu nặng

SPHINCS+ là một phương pháp xây dựng chữ ký dựa trên hàm băm. Về cơ bản, nó dựa vào các hàm băm mật mã (thay vì các phương trình đường cong elliptic tinh vi hay phân tích thừa số nguyên tố bí mật) để xây dựng khóa công khai và xác minh chữ ký. Các lược đồ mật mã dựa trên hàm băm miễn nhiễm với thuật toán Shor vì chúng không sử dụng các hệ thống toán học hàm số đằng sau các hàm một chiều của chúng. Thay vào đó, các hàm băm dựa vào phương pháp xếp chồng dữ liệu brute-force. Các phương pháp brute-force không chứa các mối quan hệ toán học (hoặc các lối tắt) dễ bị tổn thương bởi phép biến đổi Fourier lượng tử, khiến chúng dễ bị tổn thương bởi thuật toán Shor.

Việc xếp chồng dữ liệu hoặc hàm băm có một nhược điểm: khóa công khai và chữ ký của nó yêu cầu nhiều dữ liệu hơn đáng kể để chia sẻ. Satoshi Nakamoto đã chọn đường cong elliptic cho Bitcoin chính xác vì mật mã dựa trên đường cong elliptic yêu cầu ít dữ liệu hơn để chia sẻ khi xác minh chữ ký và khóa tiền vào khóa công khai. Tôi muốn nói rằng Bitcoin là ứng dụng sát thủ cho mật mã đường cong elliptic; Satoshi Nakamoto triển khai secp256k1 (một đường cong elliptic cụ thể) trong giao thức Bitcoin, hầu hết các hệ thống mật mã đều sử dụng RSA (hoặc phân tích thừa số nguyên tố) làm hệ thống toán học cơ bản. Theo tài liệu tham số SEC 2 , để đạt được bảo mật chữ ký 128 bit, khóa công khai RSA cần dài 3072 bit, trong khi khóa công khai đường cong elliptic chỉ yêu cầu 256 bit.

Kích thước nhỏ gọn rất quan trọng đối với các hệ thống blockchain , vì bất kỳ dữ liệu được thêm vào blockchain đều phải được gửi đến và lưu trữ bởi mọi nút trong mạng. Kích thước chữ ký và khóa công khai nhỏ gọn đồng nghĩa với việc có thể đóng gói nhiều giao dịch hơn vào cùng một không gian dữ liệu. Việc giảm kích thước này được cho là lý do Satoshi Nakamoto chọn mật mã đường cong elliptic thay vì RSA Bitcoin.

Để so sánh, cả khóa công khai và chữ ký trong các hệ thống mật mã hậu lượng tử đều cực kỳ lớn. Khóa công khai trong hệ thống SPHINCS+ có cùng kích thước với khóa công khai trong hệ thống khóa hiện tại của Bitcoin, nhưng chữ ký lại dài tới vài nghìn byte. Chữ ký Schnorr trong Segregated Witness v1 (còn được gọi là Taproot) dài 64 byte; chữ ký SPHINCS+ chuẩn mực dài từ 3 đến 7 kilobyte.

- Trích từ Bài báo tham số NIST SPHINCS+ -

SPHINCS+

SPHINCS+ là một lược đồ chữ ký phức tạp được phát triển bằng cách sử dụng nhiều lớp "tiện ích" chữ ký hậu lượng tử; khi kết hợp, chúng tạo ra một cặp private key an toàn lượng tử, có thể ký an toàn nhiều thông điệp. Không giống như tiền thân của nó, "Lược đồ Chữ ký Merkle Mở rộng (XMSS)" (cũng là một lược đồ chữ ký hậu lượng tử dựa trên hàm băm), SPHINCS+ loại bỏ nhu cầu ghi nhớ các chữ ký tạo ra cho một cặp khóa.

"Cấu trúc" SPHINCS+ có thể tạo ra khóa công khai có thể ký nhiều tin nhắn mà không tiết lộ private key.

"Cấu trúc" SPHINCS+ bao gồm ba phần:

• FORS là viết tắt của "Rừng các tập con ngẫu nhiên". Đây là lớp nền tảng của "cấu trúc" SPHINCS+, nơi các thông điệp được sử dụng để xác định ảnh tiền mã hóa nào cần được tiết lộ. Tập hợp các ảnh tiền mã hóa được tiết lộ trở thành cơ sở cho chữ ký SPHINCS+. Trong SPHINCS+, các thông điệp thực sự được "ký" bằng FORS. Phần tiếp theo sẽ liên quan đến việc liên kết chữ ký FORS với khóa công khai gốc của "cấu trúc thượng tầng" SPHINCS+ (như tôi đã chọn gọi).

• WOTS+, hay "Winternitz One-Time Signature Plus", là một thuật toán chữ ký hậu lượng tử, dựa trên hàm băm, có thể ký một thông điệp một cách an toàn. SPHINCS+ sử dụng chữ ký WOTS+ để liên kết ảnh tiền được tiết lộ trong FORS với một Merkle trees XMSS phân cấp. Gốc của Merkle trees phân cấp này là khóa công khai SPHINCS+. (Điểm khác biệt duy nhất giữa WOTS và WOTS+ là biến thể "+" bao gồm một tiền tố ngẫu nhiên trong mỗi thao tác băm, giảm thiểu các cuộc tấn công băm đa mục tiêu. "+" trong "SPHINCS+" cũng có nghĩa là mỗi thao tác băm bao gồm một tiền tố được tạo ngẫu nhiên.)

• Merkle trees XMSS. Mỗi lá của Merkle trees XMSS là một khóa công khai WOTS+. SPHINCS+ tạo ra một cấu trúc kim tự tháp lớn bằng cách sử dụng các lớp Merkle trees XMSS. Các cây chồng lên nhau thường được gọi là "siêu cây". Mỗi lá của cây mẹ là một khóa công khai WOTS+, dùng để ký gốc của cây bên dưới nó, do đó liên kết các cây lại với nhau (tạo thành một cấu trúc). Số lượng cây, và do đó số lượng lớp, có thể thay đổi tùy thuộc vào kích thước chữ ký mong muốn cho một "siêu cấu trúc" SPHINCS+. Kích thước chữ ký mong muốn càng nhỏ thì càng cần nhiều hàm băm để xác minh và tạo chữ ký. Mỗi lá ở cấp thấp nhất của tất cả các cây là một FORS. Nhiều Merkle trees và nhiều lớp đồng nghĩa với việc có nhiều FORS ở đáy kim tự tháp, có thể được sử dụng tạo ra chữ ký an toàn với xác suất tái sử dụng rất thấp.

  (Ghi chú của người dịch: Lý do cấu trúc SPHINCS+ được gọi là "kim tự tháp" thay vì "toàn bộ cây" là vì nó thực sự không giống như một Merkle trees duy nhất, bắt đầu từ các lá và hợp nhất từng lớp để tạo thành một gốc (do đó, một gốc cam kết với tất cả các lá ở cấp độ dưới cùng); thay vào đó, mỗi lá của Merkle trees XMSS ở lớp trên cùng là một khóa công khai WOTS+ và mỗi khóa công khai WOTS+ ký vào gốc của Merkle trees. Merkle trees Merkle XMSS cấp độ thứ hai này cũng được xây dựng theo cùng một cách: mỗi lá là một khóa công khai WOTS+; v.v.; do đó, số lượng Merkle trees XMSS ở lớp tiếp theo luôn là bội số của số lượng ở lớp trước đó, tức là một kim tự tháp. Lớp dưới cùng không phải là Merkle trees XMSS mà là Merkle trees FORS (rừng) - một khóa công khai FORS tương ứng với nhiều Merkle trees, có thể được sử dụng để tạo ra chữ ký.)

- Một phiên bản đơn giản hóa của biểu đồ siêu cây. PK trong sơ đồ trên thực chất là chữ ký FORS trong ngữ cảnh của SPHINCS+. "Gốc" là khóa công khai SPHINCS+. -

Quy trình cơ bản để tạo khóa công khai SPHINCS+ là tạo khóa công khai WOTS+ tại gốc của một cây, sau đó tính toán gốc Merkle của các cây này. Gốc của cây cao nhất là khóa công khai SPHINCS+. Kích thước của gốc cây Merkle được xác định bởi hàm băm được sử dụng để tính toán nó. Thông thường, hàm băm SHA256 được sử dụng, với đầu ra 256 bit. Điều này có nghĩa là gốc của một Merkle trees Merkle trees như vậy sẽ là 32 byte. Khóa công khai SPHINCS+ ra đời như vậy.

Việc tạo chữ ký SPHINCS+ yêu cầu sử dụng hàm băm của thông điệp để chọn ngẫu nhiên một cây con FORS để tham gia vào siêu cây SPHINCS+ và tạo chữ ký FORS. Sau khi chữ ký FORS được tạo, nó được ký private key của khóa công khai WOTS+ trong cây XMSS phía trên nó; chữ ký này sau đó được kết hợp với đường dẫn Merkle (của khóa công khai) lên qua cây cho đến khi đạt đến khóa công khai SPHINCS+ trên cùng. Sự kết hợp của tất cả các chữ ký WOTS+, các chữ ký FORS và đường dẫn Merkle dẫn từ chữ ký FORS đến khóa công khai SPHINCS+ tạo thành chữ ký của thông điệp. Như bạn có thể tưởng tượng, đây là rất nhiều dữ liệu, đó là lý do tại sao chữ ký SPHINCS+ lớn hơn nhiều lần so với chữ ký đường cong elliptic (64 byte).

- Sơ đồ dữ liệu chứa trong chữ ký SPHINCS+; "dấu hiệu" bên phải tạo ra chữ ký FORS; trong khi "dấu hiệu" ở giữa tạo ra chữ ký WOTS+. -

Tại sao nên sử dụng SPHINCS+?

SPHINCS+ hoàn toàn theo hệ thống phân cấp, khá cồng kềnh và dựa vào một số "công cụ" khác nhau để tạo chữ ký: chữ ký Witnernitz, FORS và cây con XMSS.

Sự phức tạp của SPHINCS+ bắt nguồn từ bộ tính năng mạnh mẽ của nó. Đây là một tối ưu hóa nghiêm ngặt của XMSS, cũng là một lược đồ chữ ký hậu lượng tử cho phép một khóa công khai duy nhất ký nhiều thông điệp, nhưng yêu cầu theo dõi những nhánh Merkle trees nào đã được sử dụng để ký. SPHINCS+ sử dụng tính ngẫu nhiên được tạo ra từ bản tóm tắt của thông điệp đã ký để chọn một cách xác định một nhánh cây con trong siêu cây.

Trong Bitcoin, lý tưởng nhất là bạn nên xoay vòng một khóa công khai cho mỗi giao dịch, nghĩa là bạn tạo ra một siêu cấu trúc SPHINCS+ mới cho mỗi khóa công khai được sử dụng trong Bitcoin.

Lúc đầu, tôi thấy bối rối vì sao khả năng lần chữ ký mạnh mẽ như vậy lại được cung cấp trên một khóa công khai dùng một lần (lý tưởng nhất là như vậy).

Jonas Nick từ Blockstream Research chỉ ra rằng bạn sẽ phải ký lại khi muốn thêm phí bổ sung hoặc giao dịch bị mất vì lý do nào đó; Laolu (còn được gọi là roasbeef) chỉ ra rằng các giao thức ngoài Chuỗi như Lightning Network yêu cầu lần chữ ký (của cùng một khóa công khai) để theo dõi quá trình chuyển đổi trạng thái trong các hợp đồng riêng tư.

Trong Bitcoin, bạn có thể không cần chức năng ký lại không giới hạn, cho phép chúng ta xây dựng một siêu kiến ​​trúc SPHINCS+ nhỏ hơn để tạo khóa công khai. Siêu kiến ​​trúc nhỏ hơn đồng nghĩa với việc chữ ký nhỏ hơn vì cần ít đường dẫn Merkle trees hơn. Tuy nhiên, điều này cũng đồng nghĩa với việc số lượng chữ ký bạn có thể tạo ra trước khi bảo mật bắt đầu giảm sẽ giảm. Trong mật mã đường cong elliptic, việc tái sử dụng nonce của chữ ký sẽ ngay lập tức làm rò rỉ private key; trong SPHINCS+, việc lạm dụng khóa công khai (để ký) chỉ làm giảm dần tính bảo mật bắt đầu từ 128 bit (khi FORS cấp thấp hơn bắt đầu tái sử dụng một phần khóa).

Sau khi tìm hiểu sâu hơn, tôi phải nói rằng tôi thực sự rất thích đề xuất của roasbeef về việc sử dụng SPHINCS+ làm sơ đồ chữ ký hậu lượng tử. Vẫn còn rất nhiều công việc thiết kế cần được thực hiện để xác định các thông số chính xác. Tôi rất mong chờ một bản thảo BIP (mà ông ấy cho biết đang được tiến hành) có thể giúp lấp đầy một số khoảng trống xung quanh mối quan hệ giữa số lớp trong kiến ​​trúc thượng tầng và số lần thử ký lại an toàn.

Cũng cần lưu ý rằng, như đã đề cập trong bài nói chuyện của roasbeef, SPHINCS+ không cho phép sử dụng đường dẫn dẫn xuất khóa gốc/khóa con. Điều này có nghĩa là ví phân cấp BIP32 đã chết. Có những lựa chọn thay thế, nhưng chúng ta sẽ mất khả năng sử dụng đường dẫn dẫn xuất phân cấp để mô tả các khóa công khai tạo nên ví (như hiện đang được ngành công nghiệp sử dụng với xpub và ví con).

Đi theo hướng nào?

Bitcoin sẽ chuyển sang một hệ thống chữ ký hậu lượng tử. Khi nào, sử dụng hệ thống nào và với những thông số nào sẽ là những chủ đề nóng trong vài năm tới.

Đề xuất SPHINCS+ của Roasbeef là một lựa chọn hấp dẫn, bất chấp sự phức tạp của kiến ​​trúc thượng tầng cây nhiều lớp. Theo tôi, tất cả các lược đồ khóa công khai hậu lượng tử dựa trên hàm băm đều rất tệ. SPHINCS+ cũng xấu xí, nhưng đó là vì nó cung cấp nhiều tính năng nhất, đặc biệt là tính năng không trạng thái khi ký lặp lại.

Khi tôi hiểu rõ hơn nhân vật của từng phần trong giao thức, tôi bắt đầu đánh giá cao sự thông minh trong việc thiết kế cấu trúc nhiều lớp này.

Roasbeef vẫn còn nhiều việc phải làm với BIP, đặc biệt là về độ sâu của mỗi cây và số lượng cấp cây con, kích thước của chữ ký Winternitz, và các tham số cho FORS. Có một vấn đề nan giải giữa kích thước của chữ ký và số lượng băm cần thiết để tạo ra nó. Việc tìm ra sự cân bằng phù hợp giữa nỗ lực tính toán và khả năng truy xuất nguồn gốc trên Chuỗi là rất quan trọng trước khi một BIP chính thức có thể được phát hành.

Vậy thì còn một câu hỏi cuối cùng nữa:

Liệu việc chuyển sang SPHINCS+ có đồng nghĩa với việc Bitcoin đã trở thành một mô hình kim tự tháp không? Thật khó để định nghĩa, nhưng chắc chắn là như vậy.

(Ghi chú của người dịch: Đây là một cách chơi chữ, vì "pyramid-scheme" có thể có nghĩa là "sơ đồ kim tự tháp" và "cấu trúc kim tự tháp" của SPHINCS+.)

Lời cảm ơn

Cảm ơn Jonas Nick và Olaoluwa Osuntokun đã giúp giải thích về việc tái sử dụng khóa công khai SPHINCS+ và điều chỉnh tham số.

Đọc thêm

Bạn muốn tìm hiểu sâu hơn? Dưới đây là một số nguồn tài liệu tuyệt vời mà tôi đã sử dụng làm nguồn tham khảo cho bài viết này:

• Các slide từ bài thuyết trình của Laolu tại Hội nghị Bitcoin và Máy tính lượng tử Presidio vào ngày 17 tháng 7.
• Giải thích về chữ ký Winternitz của Sphere10 đã giúp tôi nắm vững những kiến ​​thức cơ bản về chữ ký hậu lượng tử
• Bài đăng trên blog độ sâu của nhà phát triển phần mềm Ethan Rahn, bao gồm các sơ đồ đẹp mắt và một số thông tin về lịch sử phát triển chữ ký hậu lượng tử.
• Giải thích độ sâu tuyệt vời về SPHINCS+ của John Kelsey đến từ NIST. Một trong những giải thích chi tiết nhất tôi từng thấy, nhưng hình như nó đã bị chôn vùi.

(qua)