Tổng hợp chữ ký hậu lượng tử: Một cách tiếp cận gấp khúc

Tác giả: Thomas Coratger , Srinath Setty

Giới thiệu: Sự chuyển đổi dấu ấn hậu lượng tử

Trong các hệ thống Proof-of-Stake như Ethereum, chữ ký số cung cấp trách nhiệm giải trình cho hàng trăm nghìn người xác thực bảo mật mạng lưới. Khối lượng xác nhận khổng lồ tạo ra một thách thức đáng kể về khả năng mở rộng: làm thế nào để xác minh hiệu quả nhiều chữ ký như vậy? Để giải quyết vấn đề này, lớp đồng thuận của Ethereum đã áp dụng lược đồ chữ ký BLS , một lựa chọn đóng vai trò then chốt trong việc cho phép mạng lưới mở rộng quy mô.

Ưu điểm của BLS nằm ở cấu trúc đại số độc đáo của nó, cho phép tổng hợp chữ ký hiệu quả cao bằng cách sử dụng các phép ghép mật mã ( e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T e : G 1 × G 2 → G T ). Tính chất song tuyến của ánh xạ ghép cặp cho phép một đặc tính đáng chú ý: tính hợp lệ của toàn bộ tập hợp n chữ ký có thể được xác nhận bằng một phương trình duy nhất .

Trong quá trình triển khai thực tế của Ethereum, chữ ký tổng hợp đi kèm với một trường bit (các \texttt{aggregation_bits} aggregation_bits ) xác định những người xác thực nào từ một ủy ban đã tham gia. Người xác minh sử dụng trường bit này để tính toán khóa công khai tổng hợp \sum pk_i ∑ p k i trước khi thực hiện kiểm tra mật mã cuối cùng. Mặc dù kiểm tra cuối cùng có thời gian không đổi (hai phép ghép cặp), chi phí xác minh tổng thể bao gồm một bước có thời gian tuyến tính để xây dựng khóa công khai tổng hợp này:

Mô hình này rất cần thiết cho khả năng mở rộng và được mô tả rất chi tiết trong cuốn sách Eth2 , nhưng tính bảo mật của BLS dựa trên các vấn đề mà máy tính lượng tử không thể giải quyết được. Quá trình chuyển đổi cần thiết sang một giải pháp thay thế hậu lượng tử, chẳng hạn như XMSS dựa trên hàm băm , lại đặt ra thách thức về khả năng mở rộng. XMSS thiếu các thuộc tính đại số của BLS; chữ ký của nó lớn hơn và tốn nhiều tài nguyên tính toán để xác minh, khiến việc xác minh riêng lẻ hàng nghìn chữ ký trên mỗi khối trở nên không khả thi.

Giải pháp là một hình thức tổng hợp chữ ký mới sử dụng các lập luận tri thức ngắn gọn (SNARK) để tạo ra một bằng chứng ngắn gọn duy nhất cho toàn bộ tập hợp chữ ký (mặc dù thường được gọi là có kích thước không đổi để đơn giản, nhưng về mặt kỹ thuật, bằng chứng từ các SNARK dựa trên hàm băm hiện đại có kích thước đa logarit theo kích thước của câu lệnh). Vì các trình xác thực được phân tán trên mạng ngang hàng, nên việc một nút duy nhất thu thập tất cả các chữ ký là không khả thi. Thay vào đó, việc tổng hợp cũng phải diễn ra theo cách phi tập trung, trong đó các nút khác nhau tổng hợp các tập con chữ ký chồng chéo. Yêu cầu "bằng chứng của bằng chứng" này dẫn đến một kiến trúc đệ quy. Bài viết này so sánh hai mô hình chính để triển khai đệ quy này:

1. Xác minh SNARK đệ quy: Xác minh một bằng chứng SNARK hoàn chỉnh bên trong một mạch SNARK khác.
2. Các nguyên thủy đệ quy chuyên biệt: Sử dụng các lược đồ gấp để kết hợp trực tiếp các phát biểu toán học cơ bản của các chứng minh, tránh bước xác minh đầy đủ.

Chúng tôi phân tích cơ chế, hiệu suất và sự đánh đổi của từng phương pháp để định hướng con đường cho việc tổng hợp chữ ký hậu lượng tử của Ethereum.

Khung tổng hợp

Để xử lý các xác nhận từ một tập hợp người xác thực có thể mở rộng lên đến hàng trăm nghìn người tham gia, hệ thống tổng hợp hậu lượng tử phải được thiết kế như một quy trình song song, đa lớp. Không giống như việc cộng đơn giản các chữ ký BLS, việc tổng hợp các bằng chứng dựa trên SNARK yêu cầu một phương pháp đệ quy, có cấu trúc. Quá trình này diễn ra trên một mạng ngang hàng gồm các nút tổng hợp, dẫn đến một bằng chứng duy nhất, ngắn gọn để xác minh trên chuỗi.

Thực tiễn tổng hợp dữ liệu BLS: Hiện trạng

Trước khi đi sâu vào phương pháp hậu lượng tử, điều hữu ích là hiểu cách thức tổng hợp hiện đang được triển khai với chữ ký BLS trong lớp đồng thuận của Ethereum. Cơ chế cốt lõi dựa trên việc theo dõi sự tham gia để đảm bảo tính trách nhiệm, điều cần thiết để áp dụng phần thưởng và hình phạt một cách chính xác.

Các trình xác thực được tổ chức thành các ủy ban cho mỗi vị trí. Khi một trình xác thực trong một ủy ban tạo ra một chứng thực, đối tượng đã ký sẽ bao gồm một trường có tên là `aggregation_bits` . Đây là một danh sách bit, trong đó mỗi vị trí tương ứng với chỉ số của trình xác thực trong ủy ban cụ thể đó. Trình xác thực thực hiện chứng thực sẽ đặt bit của chính họ thành 1.

Sau đó, các xác nhận từ các trình xác thực khác nhau cùng xác nhận một quan điểm về chuỗi có thể được tổng hợp lại. Điều này được thực hiện bằng cách thực hiện phép toán OR bitwise trên các bit tổng hợp và cộng các chữ ký BLS riêng lẻ lại với nhau (như phép cộng điểm trên đường cong elip). Kết quả là một đối tượng xác nhận duy nhất với trường bit kết hợp và một chữ ký tổng hợp. Để xác minh, một nút sẽ tái tạo khóa công khai tổng hợp bằng cách cộng các khóa công khai của chỉ những trình xác thực có bit được đặt thành 1 trong bit tổng hợp cuối cùng. Hệ thống này cho phép xác minh hàng trăm chữ ký chỉ với một lần kiểm tra ghép nối hiệu quả, nhưng điều quan trọng là nó vẫn lưu giữ hồ sơ chính xác về những người đã tham gia.

Theo dõi sự tham gia bằng trường bit trong một hệ thống hậu lượng tử

Khung lý thuyết hậu lượng tử kế thừa nhu cầu thiết yếu này về việc theo dõi sự tham gia một cách chính xác. Một bằng chứng chỉ đơn thuần xác nhận tính hợp lệ của một tập hợp chữ ký ẩn danh sẽ không đủ cho giao thức đồng thuận. Do đó, hệ thống tiếp tục sử dụng trường bit để xác định từng người ký.

Trong mô hình phi tập trung của Ethereum, tập hợp các trình xác thực là động. Để quản lý điều này, trạng thái beacon duy trì một sổ đăng ký chuẩn hóa, có thứ tự của tất cả các trình xác thực đang hoạt động tại bất kỳ thời điểm nào. Chỉ số của một trình xác thực là vị trí duy nhất của nó trong sổ đăng ký toàn cầu này cho một trạng thái cụ thể. Mặc dù sổ đăng ký thay đổi khi các trình xác thực tham gia hoặc rời đi, chỉ số vẫn cung cấp một tham chiếu ổn định và rõ ràng cho bất kỳ hoạt động đồng thuận nào. Điều này đảm bảo rằng ngay cả trong môi trường năng động, sự tham gia vẫn có thể được theo dõi một cách chính xác.

Như minh họa trong Hình 1, mỗi chữ ký hậu lượng tử được liên kết với một trường bit đánh dấu chỉ số toàn cầu của người ký là 1. Khi các bằng chứng được tổng hợp, các trường bit tương ứng của chúng được kết hợp bằng phép toán OR bitwise. Trường bit tổng hợp thu được trở thành đầu vào công khai cho SNARK, đảm bảo bằng chứng cuối cùng chứng thực chính xác tuyên bố: “tất cả các trình xác thực được chỉ định bởi trường bit cụ thể này đều đã cung cấp chữ ký hợp lệ.”

Hình 1 292×224 7,72 KB

Thiết kế cấp cao: \texttt{Tổng hợp} Tổng hợp và \texttt{Hợp nhất} Hợp nhất

Hệ thống được xây dựng dựa trên hai thao tác mã hóa cốt lõi tạo nên nền tảng của cấu trúc đệ quy. Các thao tác này cho phép phân bổ khối lượng công việc và sau đó kết hợp chúng một cách tuần tự.

• \texttt{Tổng hợp} Tổng hợp : Đây là bước ban đầu, không đệ quy. Một nút tổng hợp thu thập một loạt chữ ký XMSS thô từ một tập hợp con các trình xác thực. Nó xác minh từng chữ ký này một cách riêng lẻ và sau đó tạo ra bằng chứng SNARK ban đầu chứng thực tính hợp lệ chung của chúng. Để xác minh các chữ ký này và xây dựng trường bit chính xác, mỗi nút hoạt động Tổng hợp phải có quyền truy cập vào sổ đăng ký trình xác thực toàn cầu. Sổ đăng ký này, ánh xạ chỉ mục của mỗi trình xác thực đến khóa công khai tương ứng của chúng, đóng vai trò là đầu vào công khai cần thiết. Thao tác này chuyển đổi một tập hợp các chữ ký lớn, tốn kém để xác minh thành một đối tượng bằng chứng duy nhất, nhỏ gọn.

• \texttt{Hợp nhất} Hợp nhất : Đây là bước đệ quy. Một nút tổng hợp lấy hai bằng chứng hiện có, mỗi bằng chứng chứng thực tính hợp lệ của một tập hợp chữ ký riêng biệt, và kết hợp chúng. Kết quả đầu ra là một bằng chứng mới duy nhất cung cấp cùng một sự đảm bảo mật mã như thể người ta đã xác minh tất cả các chữ ký cơ bản từ cả hai bằng chứng đầu vào. Thao tác này là động lực của khả năng mở rộng, cho phép kết hợp các bằng chứng một cách hiệu quả.

Để giải thích rõ ràng quy trình mã hóa, chúng tôi mô hình hóa quá trình tổng hợp dưới dạng một cây đệ quy logic, như minh họa trong Hình 2. Cấu trúc cây này là một sự trừu tượng hữu ích vì nó cho phép chúng ta phân tích rõ ràng hai bước mã hóa cốt lõi — Tổng hợp (Aggregate) và Hợp nhất (Merge) — là những khối xây dựng cơ bản của hệ thống chứng minh.

Trên thực tế, mô hình logic này được triển khai trên một mạng ngang hàng (P2P) động. Để quản lý yêu cầu băng thông cao, tập hợp các trình xác thực được phân chia thành nhiều mạng con. Quá trình bắt đầu song song trong các mạng con này, nơi các bằng chứng ban đầu được tạo ra từ các tập hợp chữ ký cục bộ bằng cách sử dụng thao tác \texttt{Aggregate} . Như được minh họa trong Hình 2, mỗi thao tác Agg (Tổng hợp) thể hiện sự phụ thuộc của nó vào Trạng thái Toàn cục (Sổ đăng ký Trình xác thực). Điều này cho thấy rằng một bộ tổng hợp phải truy vấn sổ đăng ký toàn cục này để lấy các khóa công khai tương ứng với các trình xác thực mà nó đang xác minh chữ ký và để cập nhật chính xác trường bit tổng hợp cho bằng chứng được tạo ra. Sau đó, các bằng chứng ban đầu này được lan truyền khắp mạng. Khi các nút tổng hợp nhận được bằng chứng, chúng thực hiện thao tác \texttt{Merge} , kết hợp chúng để chứng thực cho các tập hợp trình xác thực ngày càng lớn hơn. Việc hợp nhất phân tán này tiếp tục cho đến khi tạo ra một bằng chứng cuối cùng duy nhất, đại diện cho các chứng thực của toàn bộ tập hợp trình xác thực tham gia.

Hình 2 815×499 32,4 KB

Kết quả quan trọng của thiết kế này là chỉ có bằng chứng cuối cùng được gửi lên blockchain. Đối tượng duy nhất này, có kích thước không đổi, thay thế nhu cầu xử lý hàng ngàn chữ ký riêng lẻ trên chuỗi. Mô hình mật mã được chọn phải hỗ trợ hiệu quả cả hai thao tác \texttt{Aggregate} và \texttt{Merge} . Sự khác biệt cơ bản về kiến trúc, mà chúng ta sẽ tìm hiểu tiếp theo, nằm ở chính cách thức triển khai hai thao tác này.

Phương án A: Đệ quy SNARK bằng phương pháp vét cạn

Mô hình kiến trúc trực tiếp nhất để triển khai đệ quy là đặt một bộ xác thực SNARK hoàn chỉnh bên trong một mạch SNARK khác. Trong mô hình này, thao tác \texttt{Merge} Merge là một SNARK chứng minh tính xác thực của các SNARK khác. Phương pháp “chứng minh-xác minh-một-bằng chứng” này là một cách đơn giản, mặc dù tốn nhiều tài nguyên tính toán, để đạt được đệ quy.

Cơ chế cốt lõi: Bằng chứng xác minh bằng chứng

Nhiệm vụ cơ bản của phép toán \texttt{Merge} Merge là lấy hai bằng chứng đầu vào, \text{proof}_A proof A và \text{proof}_B proof B , và tạo ra một bằng chứng đầu ra mới, \text{proof}_{\text{out}} proof out , chứng minh tính hợp lệ của chúng. Mối quan hệ được chứng minh bởi \texttt{Merge} Merge SNARK có thể được biểu diễn chính thức như sau:

Ở đây, V V đại diện cho thuật toán xác minh của hệ thống SNARK. Để tạo ra bằng chứng đầu ra ( proof out ), người chứng minh cho bước Hợp nhất (Merge) phải thực thi toàn bộ logic của thuật toán xác minh V V cho cả hai bằng chứng đầu vào trong mạch số học của bằng chứng mới. Điều này bao gồm việc số hóa mọi bước mã hóa của người xác minh, bao gồm tính toán hàm băm, kiểm tra cam kết đa thức và số học trường. Các hệ thống chứng minh dựa trên hàm băm hiện đại rất phù hợp với điều này, vì người xác minh của chúng không yêu cầu các phép toán ghép nối tốn kém.

Vai trò của lớp trừu tượng zkVM

Thách thức chính của phương pháp này là sự phức tạp vô cùng lớn của mạch xác thực. Mạch xác thực cho một hệ thống SNARK hiện đại bao gồm một chuỗi các thao tác mã hóa phức tạp, dẫn đến một hệ thống ràng buộc khổng lồ và vô cùng rắc rối. Việc xây dựng, kiểm tra và bảo trì mạch như vậy bằng tay là không khả thi trên thực tế và cực kỳ dễ xảy ra lỗi.

Đây là lúc Máy ảo không kiến thức (Zero-Knowledge Virtual Machine - zkVM) trở thành một nhu cầu thiết thực. zkVM đóng vai trò như một lớp trừu tượng quản lý sự phức tạp này, cho phép các nhà phát triển làm việc với mô hình lập trình quen thuộc thay vì các ràng buộc mạch cấp thấp. Quá trình hoạt động như sau:

1. Logic cấp cao: Thay vì thiết kế mạch, nhà phát triển viết chương trình cho logic của bộ kiểm chứng bằng cách sử dụng kiến trúc tập lệnh (ISA) cấp cao đơn giản. Chương trình này có thể thể hiện logic cho cả hai bước \texttt{Aggregate} và \texttt{Merge} một cách thống nhất.

2. Biên dịch trước mã hóa: zkVM được trang bị các mạch được biên dịch trước, tối ưu hóa cao cho các thuật toán mã hóa phức tạp. Các thao tác như hoán vị hàm băm POSEIDON có thể được gọi dưới dạng các lệnh đơn lẻ, hiệu quả trong chương trình cấp cao.

3. Biên dịch và Theo dõi Thực thi: Trình biên dịch dịch chương trình cấp cao thành mã bytecode của zkVM. Khi chương trình này được chạy, trình chứng minh của zkVM sẽ tạo ra một bản ghi theo dõi thực thi hoàn chỉnh, ghi lại mọi chuyển đổi trạng thái của máy ảo — từ việc nạp lệnh đến truy cập bộ nhớ. Toàn bộ bản ghi theo dõi này sau đó được tự động chuyển đổi thành hệ thống ràng buộc quy mô lớn cuối cùng được chứng minh bởi SNARK.

Chương trình \texttt{AggregateMerge} bên trong zkVM

Mô hình zkVM cho phép cả hai thao tác \texttt{ Aggregate } và \texttt{Merge} được triển khai trong một chương trình thống nhất duy nhất. Một phiên bản đơn giản hóa của chương trình đó, mà chúng ta có thể gọi là \texttt{AggregateMerge} , sẽ nhận đầu vào công khai là danh sách tất cả các khóa công khai của trình xác thực và trường bit cho biết trình xác thực nào đang được chứng thực trong bước này. Là đầu vào riêng tư, nó sẽ nhận được hỗn hợp các chữ ký XMSS thô và các bằng chứng SNARK hiện có.

Logic của chương trình khi đó sẽ là:

1. Xác minh đệ quy các bằng chứng đầu vào: Đối với mỗi bằng chứng bên trong được cung cấp, nó sẽ gọi hàm xác minh SNARK (được triển khai bằng cách sử dụng các lệnh và biên dịch trước của zkVM).
2. Xác minh trực tiếp chữ ký thô: Với mỗi chữ ký thô được cung cấp, hệ thống sẽ thực thi thuật toán xác minh chữ ký XMSS.
3. Kiểm tra tính nhất quán của trường bit: Chức năng này đảm bảo rằng các trường bit của bằng chứng bên trong và các chỉ số của chữ ký thô được kết hợp chính xác để tạo thành trường bit đầu ra mới, lớn hơn.

Sau đó, trình chứng minh zkVM sẽ tạo ra một bằng chứng SNARK duy nhất cho toàn bộ quá trình thực thi chương trình \texttt{AggregateMerge} AggregateMerge này.

Hồ sơ hiệu năng và các điểm nghẽn

Nhược điểm chính của phương pháp dựa trên zkVM là chi phí tính toán đáng kể mà bên chứng minh phải gánh chịu. Bên chứng minh không chỉ có nhiệm vụ chứng minh logic ứng dụng—xác minh chữ ký và bằng chứng—mà còn phải chứng minh tính đúng đắn của quá trình thực thi máy ảo. Chi phí máy ảo này bao gồm việc tính toán mọi bước nội bộ của CPU, từ việc tìm nạp và giải mã lệnh đến cập nhật thanh ghi, truy cập bộ nhớ và logic điều khiển luồng như các lệnh nhảy.

Khối lượng công việc bổ sung này làm cho mỗi bước hợp nhất (Merge) trở nên tốn nhiều tài nguyên tính toán và trực tiếp dẫn đến độ trễ cao hơn, điều này có thể trở thành nút thắt cổ chai trong mạng tổng hợp P2P nhạy cảm về thời gian. Điều này trái ngược với đệ quy "chương trình cố định", trong đó mạch kiểm chứng được chuyên biệt hóa cho một chương trình duy nhất, được xác định trước tại thời điểm biên dịch, loại bỏ nhu cầu về kiến trúc CPU đa năng và chi phí liên quan.

Tuy nhiên, điều quan trọng cần lưu ý là hiệu năng của các SNARK dựa trên hàm băm đang phát triển nhanh chóng. Nguyên tắc “đủ tốt” có thể áp dụng nếu hiệu năng thô của hệ thống chứng minh cơ bản đủ cao. Những tiến bộ gần đây trong kỹ thuật chứng minh đang cho thấy thông lượng cực kỳ cao. Nếu xu hướng này tiếp tục, chi phí vận hành liên tục của zkVM có thể trở thành sự đánh đổi chấp nhận được cho những lợi ích về trải nghiệm và tính linh hoạt của nhà phát triển, khiến nó trở thành một lựa chọn khả thi ngay cả trong các ứng dụng nhạy cảm về thời gian. Mặc dù chi phí chứng minh cao, các SNARK dựa trên hàm băm hiện đại có thể tạo ra các bằng chứng rất nhỏ gọn, giúp đáp ứng được các mục tiêu về kích thước trên chuỗi.

Phương án B: Các kiểu dữ liệu đệ quy chuyên biệt

Một giải pháp thay thế cho phương pháp đệ quy vét cạn là tận dụng các thuật toán mật mã được thiết kế đặc biệt cho nhiệm vụ này: các lược đồ gấp và tích lũy. Thay vì xác minh một SNARK hoàn chỉnh trong một mạch, mô hình này hoạt động trực tiếp trên các phát biểu toán học cơ bản của bằng chứng. Nó cung cấp một lối tắt mật mã hiệu quả cao, kết hợp nhiều tuyên bố về tính toàn vẹn tính toán thành một tuyên bố duy nhất, tương đương, giảm đáng kể khối lượng công việc của người chứng minh ở mỗi bước đệ quy.

Khung Nhân chứng-Thể hiện

Cốt lõi của phương pháp này là khái niệm về một cặp thể hiện-nhân chứng, được ký hiệu là (x , w ) , đại diện cho một phát biểu tính toán cho một quan hệ NP cụ thể R R. Thể hiện x x chứa dữ liệu công khai của phát biểu, trong khi nhân chứng w w chứa dữ liệu có thể là bí mật thỏa mãn phát biểu đó. Cấu trúc thống nhất này được sử dụng cho cả hai thao tác \texttt{Aggregate} và \texttt{Merge} .

• Bước Tổng hợp (Aggregate) : Thao tác này tạo ra cặp dữ liệu chứng thực-thực thể đầu tiên. Quan hệ R là thuật toán xác minh chữ ký XMSS. Thực thể x bao gồm dữ liệu công khai (thông điệp, trường bit và các khóa công khai liên quan), và thực thể chứng thực w bao gồm dữ liệu bí mật (chữ ký XMSS thô). Kết quả đầu ra là một cặp dữ liệu chứng thực-thực thể ban đầu sẵn sàng để được gộp hoặc tích lũy.
• Bước hợp nhất (Merge) : Thao tác này lấy hai cặp chứng cứ-nhân chứng, (x_1, w_1) ( x 1 , w 1 ) và (x_2, w_2) ( x 2 , w 2 ) , và sử dụng một giao thức nhẹ để tính toán một cặp gấp duy nhất, (x_{\text{folded}}, w_{\text{folded}}) ( x folded , w folded ) , cho cùng một quan hệ R R . Quá trình này tiết kiệm chi phí tính toán hơn nhiều so với việc chạy một trình xác minh SNARK đầy đủ bên trong một mạch. Ngoài ra, trình chứng minh gấp cũng rẻ hơn trình chứng minh SNARK cho cùng một quan hệ.

Giờ đây, chúng ta sẽ tìm hiểu hai cơ chế hậu lượng tử thực hiện mô hình này.

Gấp dựa trên mạng lưới

Sơ đồ gấp là một giao thức lấy hai trường hợp của một mối quan hệ và kết hợp chúng thành một trường hợp mới duy nhất của cùng mối quan hệ đó. Một ví dụ nổi bật về sơ đồ gấp hậu lượng tử là Neo , dựa trên các giả định về mạng lưới hậu lượng tử có vẻ hợp lý.

Một thách thức quan trọng trong mật mã dựa trên mạng lưới là quản lý chuẩn của bằng chứng. Việc thực hiện các phép toán mật mã như tổ hợp tuyến tính khiến chuẩn này tăng lên. Nếu chuẩn tăng quá lớn, tính bảo mật của lược đồ cam kết có thể bị phá vỡ. Neo được thiết kế dựa trên chu kỳ ba giai đoạn giúp quản lý cẩn thận sự tăng trưởng của chuẩn này.

Đối với trường hợp sử dụng của chúng tôi, bước \texttt{ Aggregate } tạo ra một cặp thể hiện-nhân chứng ban đầu cho một quan hệ được gọi là Matrix CCS (MCS), đại diện cho mạch xác minh XMSS. Sau đó, thao tác \texttt{Merge} lấy thể hiện MCS mới này và một bộ tích lũy đang chạy (là một thể hiện của quan hệ đánh giá đơn giản hơn, ME) và thực thi chu trình của Neo (Hình 3 mô tả quy trình làm việc này):

Hình 3 824×450 65,3 KB

Tích lũy phân tách dựa trên hàm băm

Một cơ chế đệ quy khác là lược đồ tích lũy phân tách, duy trì một bộ tích lũy liên tục chứng thực tính hợp lệ của một tập hợp các yêu cầu, thậm chí có thể dành cho các mối quan hệ khác nhau. Lược đồ tích lũy phân tách và lược đồ gấp được giới thiệu đồng thời. Mặc dù có một số khác biệt cụ thể giữa chúng, nhưng chúng không quan trọng đối với phần trình bày của chúng ta. Thao tác \texttt{Merge} tương ứng với việc thêm một yêu cầu mới vào bộ tích lũy này. Một ví dụ hàng đầu về lược đồ tích lũy phân tách hậu lượng tử là WARP , dựa trên các hàm băm hậu lượng tử khả thi và được thiết kế đặc biệt để đạt hiệu suất chứng minh tối đa.

Sơ đồ tích lũy phân chia

Ý tưởng cốt lõi của sơ đồ tích lũy phân tách là chia bộ tích lũy thành hai phần: một phần nhỏ, công khai và một phần lớn, riêng tư dùng làm bằng chứng. Ở mỗi bước đệ quy, người chứng minh ( P_{ACC} P A C C ) lấy bộ tích lũy cũ và một yêu cầu mới, tạo ra một bộ tích lũy được cập nhật và tạo ra một bằng chứng nhỏ về quá trình chuyển đổi này.

Điều quan trọng là, bộ xác minh ( V_{ACC} V A C C ) chỉ cần các phần thể hiện công khai của bộ tích lũy cũ và mới để kiểm tra bằng chứng chuyển đổi này. Bộ xác minh không bao giờ nhìn thấy hoặc xử lý phần chứng thực lớn, làm cho bước xác minh đệ quy cực kỳ nhẹ nhàng. Toàn bộ chứng thực chỉ được yêu cầu ở giai đoạn cuối cùng của quy trình bởi người chứng minh cuối cùng ("người quyết định"), người tạo ra SNARK duy nhất trên chuỗi.

Từ mạch điện đến đa thức: PESAT

Trong khuôn khổ WARP, các yêu cầu được tích lũy được biểu diễn dưới dạng các trường hợp của Tính thỏa mãn phương trình đa thức (PESAT). Thay vì biểu diễn một phép tính dưới dạng một mạch cổng, WARP biểu diễn nó dưới dạng một tập hợp các phương trình đa thức mà tất cả đều phải có giá trị bằng không đối với một trường hợp và bằng chứng nhất định. Đây là một khuôn khổ rất tổng quát có thể nắm bắt các hệ thống ràng buộc phổ biến như R1CS và CCS. Đối với trường hợp sử dụng của chúng tôi, thuật toán xác minh chữ ký XMSS và logic trường bit được biên dịch thành một trường hợp PESAT.

Một công cụ chứng minh thời gian tuyến tính

Ưu điểm chính của WARP là trình chứng minh có thời gian thực thi tuyến tính. Thời gian chạy của trình chứng minh, được đo bằng các phép toán trường và tính toán băm, tăng tuyến tính với kích thước của phép tính. Đây là một bước đột phá đáng kể về hiệu quả của trình chứng minh, tránh được hai nguồn chi phí chính thường gặp trong các hệ thống khác:

• Chi phí siêu tuyến tính ( O(N \log N) O ( N log N ) ) của mật mã dựa trên nhóm, chủ yếu là các phép nhân đa vô hướng lớn.
• Chi phí vận hành cố định lớn của một zkVM đa năng là phải chứng minh khả năng thực thi kiến trúc CPU của chính nó bên cạnh logic ứng dụng.

Đối với một tác vụ quy mô lớn, lặp đi lặp lại như tổng hợp chữ ký, một công cụ chứng minh thời gian tuyến tính mang lại sự cải thiện hiệu suất đáng kể, khiến nó trở thành một lựa chọn rất hấp dẫn cho công cụ đệ quy.

Hoàn thiện: Tạo SNARK trên chuỗi

Quá trình hợp nhất đệ quy \texttt{Merge} , dù bằng cách gấp lại hay tích lũy, đều tạo ra một cặp chứng cứ-nhân chứng cuối cùng duy nhất. Cặp này hợp lệ về mặt tính toán—nó thể hiện chính xác toàn bộ tập hợp các chữ ký đã được tổng hợp—nhưng nó không ngắn gọn theo nghĩa truyền thống. Thành phần nhân chứng vẫn hiện diện và được yêu cầu bởi người chứng minh cuối cùng, khiến đối tượng quá lớn để xác minh trực tiếp trên chuỗi.

Do đó, nút tổng hợp cuối cùng phải thực hiện thêm một bước nữa: tạo ra một SNARK tiêu chuẩn, không đệ quy của cặp dữ liệu đã được gấp lại cuối cùng này. Điều này dẫn đến một kiến trúc lai sử dụng hai công cụ mã hóa riêng biệt:

1. Cơ chế đệ quy: Một lược đồ thu gọn hoặc tích lũy được lựa chọn để tối ưu hiệu quả của trình chứng minh. Mục đích chính của nó là kết hợp nhiều câu lệnh thành một câu lệnh duy nhất với chi phí tính toán thấp ở mỗi bước đệ quy.
2. Công cụ Succinctness Engine: Một SNARK cuối cùng, không đệ quy, được sử dụng để tạo ra bằng chứng ngắn gọn và có thể kiểm chứng hiệu quả để sử dụng trên chuỗi.

Quy trình hoàn thiện cuối cùng như sau:

1. Cặp bằng chứng-thí sinh được thu gọn cuối cùng được coi là tuyên bố cần được chứng minh.
2. Một bằng chứng Oracle tương tác đa thức (PIOP), chẳng hạn như (Super)Spartan , được áp dụng để giảm bớt nhiệm vụ chứng minh kiến thức về bằng chứng được gấp lại thành một tập hợp các khẳng định đánh giá đa thức đa tuyến tính.
3. Một lược đồ cam kết đa thức hậu lượng tử (PCS), chẳng hạn như BaseFold hoặc WHIR , được sử dụng để chứng minh các đánh giá.

Kiến trúc lai này tách biệt chức năng đệ quy hiệu quả khỏi chức năng ngắn gọn cuối cùng. Nó tận dụng những ưu điểm tương ứng của mỗi phương pháp để xây dựng một hệ thống có khả năng mở rộng và tạo ra bằng chứng trên chuỗi nhỏ gọn.

Thử thách kỹ thuật: Quản lý nhân chứng

Một thách thức kỹ thuật đáng kể đối với lộ trình này là việc quản lý dữ liệu chứng thực trên mạng P2P. Bên chứng minh cho bất kỳ bước Hợp nhất nào đều cần truy cập vào các chứng thực của hai bằng chứng đang được kết hợp. Một cách triển khai đơn giản sẽ yêu cầu truyền tải các chứng thực lớn này, điều này có thể tạo ra nút thắt cổ chai băng thông đáng kể.

Vấn đề này có thể được giải quyết ở cấp độ giao thức bằng cách sử dụng kỹ thuật phân đoạn chứng thực. Cách tiếp cận này giảm thiểu yêu cầu về băng thông bằng cách thay đổi cách xử lý các chứng thực:

1. Cam kết theo từng phần: Một bằng chứng lớn không được coi là một đối tượng nguyên khối mà được chia thành nhiều vectơ nhỏ hơn, có kích thước không đổi. Sau đó, bên chứng minh sẽ cam kết với từng phần này một cách riêng lẻ.

2. Gấp các khối dữ liệu: Khi hai bằng chứng được gấp lại, bằng chứng đã gấp lại chỉ là một vectơ nhỏ duy nhất. Do đó, trạng thái mật mã cần được truyền giữa các bước đệ quy vẫn nhỏ gọn và có kích thước không đổi, ngăn chặn sự gia tăng dữ liệu theo cấp số nhân.

3. Xác minh hiệu quả: Mặc dù phương pháp này làm tăng số lượng cam kết mà bộ xác minh đệ quy phải xử lý, nhưng các lược đồ như Neo được thiết kế để xử lý việc này một cách hiệu quả. Các cam kết đối với các khối chứng thực có thể được gộp lại mà không làm tăng đáng kể độ phức tạp hoặc chi phí cho mạch xác minh.

Thiết kế này định hình lại thách thức từ hạn chế về mật mã thành vấn đề về tính khả dụng của dữ liệu P2P: đảm bảo rằng các nút tổng hợp có thể định vị và lấy các khối chứng thực cần thiết từ mạng để thực hiện thao tác \texttt{Hợp nhất} Hợp nhất .

Sự đánh đổi: Các kiểu dữ liệu cơ bản dựa trên lưới so với các kiểu dữ liệu cơ bản dựa trên hàm băm

Việc lựa chọn giữa một lược đồ gấp dựa trên mạng lưới như Neo và một lược đồ tích lũy dựa trên hàm băm như WARP liên quan đến các đánh đổi về kiến trúc, chủ yếu tập trung vào các giả định về bảo mật so với hiệu suất và độ phức tạp trong triển khai.

• Giả định về bảo mật: Đây là ưu điểm chính của các lược đồ dựa trên hàm băm. Tính bảo mật của chúng chỉ dựa vào các thuộc tính của hàm băm mật mã, thường được mô hình hóa như một oracle ngẫu nhiên. Đây là một giả định tối thiểu và được tin tưởng rộng rãi, mặc dù chỉ áp dụng cho việc tích lũy gấp/phân tách. Ngược lại, các lược đồ dựa trên mạng lưới dựa trên các giả định có cấu trúc như bài toán Giải pháp số nguyên ngắn mô-đun (Module-SIS). Mặc dù được cho là khó giải quyết trong kỷ nguyên hậu lượng tử, tính bảo mật thực tế của các tham số mạng lưới cụ thể là một lĩnh vực nghiên cứu tích cực và đang phát triển. Những tiến bộ liên tục trong phân tích mật mã, chẳng hạn như những cải tiến thực tế đối với các cuộc tấn công lai , liên tục tinh chỉnh sự hiểu biết của chúng ta về các mức độ bảo mật cụ thể và đưa ra một yếu tố rủi ro dài hạn không có trong các phương pháp dựa trên hàm băm đơn giản hơn.

• Chi phí đệ quy: Đây là một lợi thế quan trọng của các lược đồ dựa trên mạng lưới. Bước "Hợp nhất" đệ quy trong hệ thống dựa trên hàm băm yêu cầu xác minh các phép mở đường dẫn Merkle trong bằng chứng tiếp theo. Trong lược đồ dựa trên mạng lưới, thao tác gấp gọn mang tính đại số hơn, trực tiếp kết hợp các phát biểu toán học mà không cần xác minh toàn bộ đối tượng mật mã. Điều này dẫn đến mạch xác minh đệ quy đơn giản hơn nhiều, có thể dẫn đến chi phí tính toán thấp hơn đáng kể.

• Tính năng chuyên biệt: Các cấu trúc dựa trên lưới như Neo có thể mang lại những lợi ích hiệu năng độc đáo. Ví dụ, Neo đưa ra chi phí cam kết "trả tiền theo từng bit", trong đó chi phí cam kết với một chứng thực tỷ lệ thuận với độ rộng bit của các giá trị của nó. Điều này rất có lợi cho các phép tính thực tế, nơi nhiều giá trị chứng thực có kích thước nhỏ, một tính năng thường không có trong các hệ thống dựa trên hàm băm, vốn coi tất cả dữ liệu là các phần tử trường có kích thước đầy đủ cho hàm băm Merkle.

Phân tích so sánh về các sự đánh đổi trong kiến trúc

Việc lựa chọn giữa phương pháp đệ quy vét cạn và các thuật toán cơ bản chuyên dụng liên quan đến những sự đánh đổi khác nhau trong thiết kế hệ thống. Hai phương pháp này khác nhau chủ yếu ở vị trí đặt độ phức tạp—hoặc trong cơ sở hạ tầng chứng minh mật mã hoặc ở lớp giao thức ngang hàng—và do đó, ở sự cân bằng giữa hiệu suất và tính trừu tượng trong phát triển. Bảng sau đây tóm tắt những điểm khác biệt chính giữa hai hướng kiến trúc này.

Bảng 1: So sánh các kiến trúc tổng hợp đệ quy

Phần kết luận

Việc chuyển đổi sang lược đồ chữ ký hậu lượng tử cho lớp đồng thuận của Ethereum đòi hỏi một kiến trúc tổng hợp đệ quy. Việc lựa chọn kiến trúc này không phải là một quyết định đơn giản: zkVM và các lược đồ gấp gọn đều có những điểm mạnh và thách thức kỹ thuật riêng.

Phương pháp A, đặc trưng bởi thuật toán đệ quy SNARK vét cạn, quản lý độ phức tạp mật mã bằng cách trừu tượng hóa nó đằng sau một zkVM. Cách tiếp cận này đơn giản hóa việc phát triển logic ứng dụng nhưng lại tạo ra chi phí tính toán đáng kể và không thể tránh khỏi trong bước đệ quy do yêu cầu người chứng minh phải chứng minh dấu vết thực thi của VM.

Phương pháp B, sử dụng các thuật toán cơ bản chuyên biệt như lược đồ gấp và tích lũy, được thiết kế để đạt hiệu suất cao bằng cách sử dụng một công cụ mã hóa hiệu quả hơn cho đệ quy. Thiết kế này đẩy sự phức tạp ra khỏi lõi mã hóa và vào lớp giao thức P2P, lớp này sau đó phải giải quyết các thách thức như tính khả dụng của dữ liệu chứng thực.

Tóm lại, con đường tối ưu cho Ethereum vẫn chưa được xác định và là một lĩnh vực nghiên cứu đang được quan tâm. Quyết định sẽ phụ thuộc vào sự phát triển liên tục của cả công nghệ zkVM và folding, phân tích sâu hơn về động lực mạng P2P, các yêu cầu chính xác về hiệu năng và bảo mật của lớp đồng thuận, và lựa chọn chiến lược về giá trị lâu dài của tính tổng quát so với tính chuyên biệt. Một giải pháp dựa trên zkVM, mặc dù có thể kém hiệu quả hơn đối với nhiệm vụ này, nhưng cung cấp một cơ sở hạ tầng linh hoạt có thể phục vụ các nhu cầu khác trong tương lai của giao thức, trong khi một lược đồ folding chuyên biệt đại diện cho một giải pháp được tối ưu hóa cao nhưng có thể hạn chế. Bài viết này nhằm mục đích làm rõ các sự đánh đổi cơ bản liên quan, cung cấp một khuôn khổ có cấu trúc cho cuộc tranh luận đang diễn ra.