Tiêu đề gốc: "Cách thiết kế một sơ đồ đệ quy bằng chứng tinh tế" Tác giả gốc: Lin Yanxi, CTO của Fox Tech; Mạnh Huyền Cơ, nhà khoa học trưởng của Fox Tech Lời nói đầu: Hầu hết tất cả các vấn đề gặp phải trong các bản nhạc zkRollup và zkEVM, trong số đó Chúng là về cơ bản là các vấn đề thuật toán. Lý do chính khiến việc tăng tốc phần cứng ZKP thường được nhắc đến là do các thuật toán hiện tại nhìn chung còn chậm. Để tránh rơi vào tình trạng lúng túng “thuật toán không đủ, phần cứng sẽ bù”, chúng ta nên giải quyết vấn đề bằng thuật toán. Thiết kế một sơ đồ chứng minh tái diễn tinh tế là chìa khóa để giải quyết vấn đề này. Với sự phát triển không ngừng của các hợp đồng thông minh, ngày càng có nhiều ứng dụng web3 dần xuất hiện và khối lượng giao dịch của Layer1 truyền thống như Ethereum đang tăng lên nhanh chóng và tình trạng tắc nghẽn có thể xảy ra bất cứ lúc nào. Làm thế nào để đạt được hiệu quả cao hơn trong khi vẫn đảm bảo tính bảo mật do Lớp 1 cung cấp đã trở thành một vấn đề cấp bách cần được giải quyết. Đối với Ethereum, zkRollup sử dụng thuật toán chứng minh không có kiến ​​thức làm thành phần cơ bản để di chuyển các phép tính đắt tiền mà ban đầu cần được thực hiện trên chuỗi ngoài Lớp 1 và cung cấp bằng chứng về tính chính xác của việc thực thi cho chuỗi. Đường đua chủ yếu bao gồm các dự án như StarkWare, zkSync, Scroll và Fox Tech. Trên thực tế, trong thiết kế zkRollup, có những yêu cầu rất cao về hiệu quả: người ta hy vọng rằng giá trị chứng minh được gửi đủ nhỏ để giảm tải tính toán của Lớp 1. Để có được độ dài chứng minh đủ nhỏ, các dự án zkRollup khác nhau đang cải tiến các thuật toán và thiết kế kiến ​​trúc. Ví dụ: Fox đã phát triển thuật toán chứng minh FOAKS của riêng mình dựa trên thuật toán chứng minh không có kiến ​​thức mới nhất để có được thời gian chứng minh và độ dài chứng minh tối ưu. Ngoài ra, ở giai đoạn xác minh bằng chứng, phương pháp đơn giản nhất là tạo ra các bằng chứng tuyến tính và xác minh chúng một cách tuần tự. Để nâng cao hiệu quả, điều đầu tiên mọi người nghĩ đến là gói nhiều bằng chứng thành một bằng chứng, điều này thường được gọi là tập hợp bằng chứng (Proof Aggregation). Nói một cách trực quan, việc xác minh các bằng chứng do zkEVM tạo ra là một quy trình tuyến tính và người xác minh (Verifier) ​​​​cần xác minh lần lượt từng giá trị bằng chứng được tạo ra. Tuy nhiên, hiệu quả của phương pháp xác minh này tương đối thấp và chi phí liên lạc tương đối lớn.Đối với kịch bản zkRollup, chi phí phía bên xác minh cao hơn có nghĩa là tính toán lớp Layer1 nhiều hơn, điều này cũng sẽ dẫn đến phí Gas cao hơn.Trước tiên hãy xem một ví dụ: Alice muốn chứng minh cho cả thế giới thấy rằng cô ấy đã đến Fox Park từ ngày 1 đến ngày 7 tháng này. Để làm được điều này, cô ấy có thể chụp ảnh trong công viên với tờ báo của ngày hôm đó từ ngày 1 đến ngày 7, và gói 7 bức ảnh này sẽ trở thành bằng chứng. Hình 1: Sơ đồ tổng hợp bằng chứng chung. Trong ví dụ trên, việc đặt 7 bức ảnh trực tiếp vào một phong bì là cách tổng hợp bằng chứng theo nghĩa trực quan. Trong các tình huống thực tế, điều này tương ứng với việc kết nối các bằng chứng khác nhau lại với nhau và xác minh chúng một cách tuyến tính theo trình tự, nghĩa là trước tiên Xác minh bằng chứng đầu tiên, sau đó là bằng chứng thứ hai và các bằng chứng tiếp theo. Vấn đề là cách làm này sẽ không làm thay đổi quy mô chứng minh cũng như thời gian chứng minh mà chỉ có tác dụng như việc chứng minh và kiểm chứng từng cái một. Nếu bạn muốn đạt được mức nén không gian ở mức logarit, bạn cần sử dụng bằng chứng đệ quy (Proof Recursion) được đề cập bên dưới. Sơ đồ chứng minh đệ quy được Halo2 và STARK sử dụng Để giải thích rõ hơn chứng minh đệ quy là gì, chúng ta hãy quay lại ví dụ trên. 7 bức ảnh của Alice thực chất là 7 bằng chứng. Bây giờ hãy cân nhắc việc ghép chúng lại, như vậy Alice có thể chụp ảnh tờ báo số 1, chụp ảnh tờ báo số 2 ở số 2, và chụp ảnh tờ báo số 2 và tờ báo số 3 ở số 3. . hình chụp. Bằng cách tương tự, Alice chụp bức ảnh cuối cùng vào ngày 7 với bức ảnh của ngày 6 và tờ báo vào ngày 7. Khi những người bạn khác nhìn thấy bức ảnh cuối cùng của ngày 7, họ có thể xác minh rằng từ ngày 1 đến ngày 7 Alice đều đi đến công viên . Như bạn có thể thấy, bảy bức ảnh chứng minh trước đó đã được nén thành một. Một kỹ thuật quan trọng trong quá trình này là "ảnh chứa ảnh", tương đương với việc lồng các ảnh trước đó vào các ảnh tiếp theo theo cách đệ quy. Điều này khác với việc ghép nhiều bức ảnh lại với nhau rồi chụp một bức ảnh. Thủ thuật chứng minh đệ quy của zkRollup có thể giảm đáng kể kích thước chứng minh. Cụ thể, mỗi giao dịch sẽ tạo ra một bằng chứng, chúng ta giả sử mạch tính toán giao dịch ban đầu là C0, P0 là bằng chứng về tính đúng đắn của C0, V0 là quá trình tính toán kiểm chứng P0, và Prover (Prover) cũng chuyển đổi V0 thành The tương ứng. mạch được ký hiệu là C0'. Tại thời điểm này, đối với quá trình tính toán bằng chứng C1 của một giao dịch khác, các mạch của C0' và C1 có thể được hợp nhất. Bằng cách này, khi bằng chứng P1 về tính chính xác của mạch được hợp nhất được xác minh, nó tương đương với việc xác minh hai mạch trên tại đồng thời Đạt được tính chính xác của một giao dịch, nghĩa là đạt được sự nén.Nhìn lại quá trình trên, chúng ta có thể thấy rằng nguyên tắc nén là chuyển đổi quá trình xác minh và chứng minh thành một mạch, sau đó tạo ra một "bằng chứng chứng minh". Vì vậy, từ góc độ này, nó là một hoạt động có thể đệ quy liên tục nên còn gọi là chứng minh đệ quy. Hình 2: Lược đồ chứng minh đệ quy được Halo2 và Stark sử dụng Lược đồ đệ quy chứng minh được Halo2 và STARK sử dụng có thể tạo ra các bằng chứng song song và hợp nhất nhiều bằng chứng, để có thể xác minh tính chính xác của nhiều lần thực hiện giao dịch trong khi xác minh một giá trị bằng chứng. , mà có thể nén chi phí tính toán và cải thiện đáng kể hiệu quả của hệ thống. Tuy nhiên, sự tối ưu hóa như vậy vẫn ở mức cao hơn thuật toán chứng minh không có kiến ​​thức cụ thể. Để nâng cao hiệu quả hơn nữa, chúng ta cần tối ưu hóa và đổi mới ở cấp độ thấp hơn. . Đã đến thời điểm này. Sơ đồ đệ quy đã được chứng minh được FOAKS sử dụng là một dự án zkRollup dựa trên zkEVM tại Fox Tech. Trong hệ thống chứng minh của mình, nó cũng sử dụng kỹ thuật chứng minh đệ quy, nhưng nội hàm khác với phương pháp đệ quy nêu trên, điểm khác biệt chính là Fox sử dụng ý tưởng đệ quy bên trong một chứng minh. Để diễn đạt ý tưởng cốt lõi của chứng minh đệ quy được Fox sử dụng là liên tục rút gọn bài toán cần chứng minh cho đến khi bài toán rút gọn đủ đơn giản, chúng ta cần đưa ra một ví dụ khác. Trong ví dụ trên, Alice chụp một bức ảnh để chứng minh rằng cô ấy đã đến Công viên Fox vào một ngày nhất định, vì vậy Bob đưa ra những gợi ý khác nhau. Anh ấy tin rằng vấn đề chứng minh Alice đã đến công viên có thể được quy giản thành việc chứng minh rằng điện thoại di động của Alice điện thoại đã được chuyển đến công viên. Và việc chứng minh vấn đề này có thể được tóm tắt thành việc chứng minh rằng điện thoại di động của Alice nằm trong phạm vi của công viên. Vì vậy, để chứng minh rằng Alice đã đến công viên, cô ấy chỉ cần gửi vị trí bằng điện thoại của mình khi cô ấy đang ở công viên. Bằng cách này, kích thước của bằng chứng thay đổi từ ảnh gốc (dữ liệu có chiều rất cao) sang dữ liệu 3 chiều (vĩ độ, kinh độ và thời gian), tiết kiệm chi phí một cách hiệu quả. Ví dụ này không hoàn toàn phù hợp, vì một số người có thể đặt câu hỏi rằng việc điện thoại di động của Alice đã đến Công viên Fox không có nghĩa là chính Alice đã ở đó, nhưng trong các tình huống thực tế, quá trình rút gọn này rất nghiêm ngặt về mặt toán học.Cụ thể, việc sử dụng bằng chứng đệ quy của Fox là đệ quy ở cấp độ mạch. Khi thực hiện chứng minh không có kiến ​​thức, chúng ta sẽ viết bài toán cần chứng minh vào một mạch, sau đó tính một số phương trình cần thỏa mãn thông qua mạch. Thay vì chỉ ra rằng các phương trình này được thỏa mãn, chúng ta viết lại các phương trình này thành các mạch, v.v., cho đến khi cuối cùng phương trình chứng minh chúng thỏa mãn trở nên đủ đơn giản để chúng ta có thể dễ dàng chứng minh nó một cách trực tiếp. Từ quá trình này chúng ta có thể thấy rằng làm như vậy gần với ý nghĩa của "đệ quy" hơn. Điều đáng nói là không phải thuật toán nào cũng có thể sử dụng kỹ thuật đệ quy này, giả định rằng mỗi lần đệ quy sẽ biến chứng minh có độ phức tạp O(n) thành chứng minh O(f(n)), và tính toán đệ quy chính quá trình Độ phức tạp là O(g(n)), sau đó sau một lần đệ quy, tổng độ phức tạp tính toán sẽ trở thành O1(n)=O(f(n))+O(g(n)), và sau hai lần đệ quy, nó sẽ trở thành O2 (n )=O(f(f(n)))+O(g(n))+O(g(f(n))), sau ba lần nó là O3(n)=O(f(f( f(n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., v.v. Do đó, chỉ khi f và g là hai hàm tương ứng với các thuộc tính thuật toán thỏa mãn Ok(n) với k nhất định thì Hình 3: Sơ đồ chứng minh đệ quy được ZK-FOAKS sử dụng. quan trọng trong các ứng dụng chứng minh không có kiến ​​thức. Một trong những chìa khóa, việc chứng minh độ phức tạp sẽ ngày càng trở nên quan trọng hơn khi những thứ cần chứng minh ngày càng trở nên phức tạp hơn, đặc biệt là trong các kịch bản ứng dụng ZK khổng lồ như zkEVM, độ phức tạp của chứng minh sẽ ảnh hưởng đến hiệu suất và hiệu suất của sản phẩm Trải nghiệm người dùng có tác động quyết định. Trong số nhiều phương pháp nhằm giảm độ phức tạp của bằng chứng cuối cùng, việc tối ưu hóa thuật toán cốt lõi là quan trọng nhất. Fox đã thiết kế một sơ đồ chứng minh đệ quy tinh tế dựa trên các thuật toán tiên tiến nhất và sử dụng công nghệ này để tạo ra một giải pháp phù hợp phù hợp nhất cho zkEVM. Thuật toán ZK-FOAKS được kỳ vọng sẽ trở thành thuật toán dẫn đầu về hiệu suất trong thế giới zkRollup. Tài liệu tham khảo https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Bài viết này là từ một bài gửi và không thể hiện quan điểm của BlockBeats