Đo lường hiệu suất SNARK: Giao diện người dùng, phụ trợ và tương lai

SNARK (Đối số kiến ​​thức không tương tác Succinct) là một ứng dụng tìm kiếm tiền mã hóa quan trọng đối với khả năng mở rộng của blockchain (ví dụ: cuộn lên L2) và quyền riêng tư. SNARK cho phép ai đó chứng minh với người xác minh không tin tưởng V (ví dụ: chuỗi khối Ethereum) mà họ biết một số dữ liệu (ví dụ: một loạt các giao dịch hợp lệ). Một cách ngây thơ để chứng minh điều này là gửi dữ liệu đến V, người sau đó có thể trực tiếp kiểm tra tính hợp lệ của nó. SNARK đạt được điều tương tự, nhưng với chi phí tốt hơn để V. Đặc biệt, bằng chứng SNARK phải ngắn hơn bằng chứng ngây thơ bao gồm chính dữ liệu. (Để biết thêm chi tiết, hãy xem bản nháp sách giáo khoa của tôi, Chứng minh, Lập luận và Không có Kiến thức. Để được giới thiệu về SNARK, hãy xem Sarah Meicklejohn's trình bày tại tiền điện tử a16z Loạt bài nghiên cứu mùa hè.)

Chi phí xác minh cho SNARK có thể khác nhau, nhưng được hiểu rõ và thường khá tốt. Ví dụ, PlonK chi phí chứng minh khoảng 290,000 khí để xác minh trên Ethereum, trong khi các bằng chứng của StarkWare tốn khoảng 5 triệu gas. SNARK có khả năng áp dụng trong các cài đặt đa dạng ngay cả bên ngoài blockchain - ví dụ: cho phép sử dụng máy chủ và phần cứng. 

Nhưng vì xác minh SNARK thường rẻ, yếu tố quyết định chính của khả năng áp dụng là chi phí của câu tục ngữ SNARK P. Trong bài đăng này, tôi giải thích cách ước tính các chi phí này để xác định thời điểm sử dụng SNARK là hợp lý và SNARK có thể cải thiện như thế nào trong tương lai. Cần lưu ý rằng đây là một không gian chuyển động nhanh và một số dự án được thảo luận trong bài đăng này đang tích cực cải thiện hiệu suất của chúng.

Nhưng trước tiên: Cách SNARK được triển khai

Trong triển khai SNARK, một nhà phát triển thường viết một chương trình máy tính ψ lấy dữ liệu đầu vào w mà câu tục ngữ tuyên bố là biết (w là viết tắt của nhân chứng), và kiểm tra điều đó w là hợp lệ. Ví dụ: trong bản tổng hợp, chương trình sẽ kiểm tra xem tất cả các giao dịch trong w được ký điện tử, không làm cho bất kỳ số dư tài khoản nào giảm xuống dưới XNUMX, v.v. Chương trình ψ sau đó được cho ăn thông qua một Giao diện người dùng SNARK biên dịch nó thành một định dạng phù hợp hơn với việc áp dụng công nghệ SNARK. Định dạng thân thiện với SNARK này được gọi là đại diện trung gian (IR). 

Thông thường, IR là một số loại ví dụ thỏa mãn mạch tương đương với ψ. Điều này có nghĩa là mạch C lấy dữ liệu đầu vào w, cũng như một số đầu vào bổ sung thường được gọi là "lời khuyên không xác định" và chạy ψ on w. Các đầu vào tư vấn được sử dụng để giúp C chạy ψ, trong khi giữ C nhỏ bé. Ví dụ, mọi lúc ψ chia hai số x và y, thương số q và phần còn lại r có thể được cung cấp như lời khuyên cho Cvà C có thể chỉ cần kiểm tra điều đó x = qy + r. Kiểm tra này ít tốn kém hơn so với làm C chạy một thuật toán phân chia để tính toán q và r từ đầu.

Cuối cùng, SNARK để đáp ứng mạch được áp dụng cho C. Đây được gọi là Chương trình phụ trợ SNARK. Đối với một số vấn đề có cấu trúc cao như Phép nhân ma trận, sự lộn xộnvà một số vấn đề về đồ thị, SNARK đã biết tồn tại để tránh mô hình giao diện người dùng / phụ trợ này và do đó đạt được một câu châm ngôn nhanh hơn rất nhiều. Nhưng trọng tâm của bài đăng này là về SNARK có mục đích chung.

Như chúng ta sẽ thấy, chi phí châm ngôn của chương trình phụ trợ SNARK tăng lên cùng với C'S kích thước. Duy trì C nhỏ có thể là một thách thức, bởi vì mạch là một định dạng cực kỳ hạn chế để thể hiện một phép tính. Chúng bao gồm cổng, kết nối bởi Dây điện. Mỗi cổng g được cung cấp một số giá trị và áp dụng rất hàm đơn giản đối với các giá trị đó. Kết quả sau đó được đưa vào các cửa "hạ lưu" thông qua các dây dẫn phát ra từ g.

Khả năng mở rộng SNARK: Nó thực sự mất bao nhiêu thời gian?

Câu hỏi quan trọng là, câu tục ngữ SNARK mất bao nhiêu thời gian, liên quan đến việc đơn giản là thực thi lại ψ trên dữ liệu? Câu trả lời là câu tục ngữ trên không của SNARK, liên quan đến kiểm tra nhân chứng trực tiếp. Biểu thức sau đề cập đến thực tế là, trong bằng chứng ngây thơ, trong đó P gửi w đến V, V kiểm tra whiệu lực của bằng cách thực thi ψ trên đó. 

Sẽ rất hữu ích nếu bạn chia nhỏ câu tục ngữ thành “chi phí giao diện người dùng” và “chi phí phụ trợ”. Nếu đánh giá mạch C từng cổng là F đắt gấp nhiều lần so với chạy ψ, sau đó chúng tôi nói chi phí giao diện người dùng là F. Nếu áp dụng câu châm ngôn phụ trợ cho C is B đắt gấp nhiều lần so với đánh giá C từng cổng, sau đó chúng tôi nói rằng chi phí phụ trợ là B. Tổng chi phí của câu tục ngữ là sản phẩm, F·B. Chi phí nhân số này có thể đáng kể ngay cả khi F và B là cá nhân khiêm tốn. 

Trong thực tế, F và B cả hai đều có thể là khoảng 1000 hoặc lớn hơn. Điều này có nghĩa là tổng chi phí liên quan đến việc kiểm tra nhân chứng trực tiếp có thể là 1 triệu đến 10 triệu hoặc hơn. Một chương trình chỉ chạy trong một giây trên máy tính xách tay có thể dễ dàng dẫn đến câu châm ngôn SNARK đòi hỏi thời gian tính toán hàng chục hoặc hàng trăm ngày (đơn luồng). May mắn thay, công việc này thường có thể song song hóa ở các phạm vi khác nhau (tùy thuộc vào SNARK). 

Tóm lại, nếu bạn muốn sử dụng SNARK trong một ứng dụng ngày hôm nay, thì một trong ba điều cần phải đúng:

1. Việc kiểm tra nhân chứng trực tiếp chỉ mất chưa đầy một giây trên máy tính xách tay.
2. Kiểm tra nhân chứng trực tiếp đặc biệt thích hợp để biểu diễn trong một mạch, vì vậy chi phí giao diện người dùng là nhỏ.
3. Bạn sẵn sàng đợi nhiều ngày để câu tục ngữ SNARK hoàn thành và / hoặc trả tiền cho các tài nguyên tính toán song song khổng lồ.

Tphần còn lại của bài đăng này giải thích chi phí đầu vào của giao diện người dùng và phụ trợ đến từ đâu và cách tôi ước tính chúng cho các SNARK khác nhau. Sau đó, chúng tôi sẽ chuyển sang các triển vọng để cải thiện. 

Tách giao diện người dùng và phụ trợ

Việc tách biệt hoàn toàn các giao diện người dùng khỏi các phần mềm phụ trợ có thể là một thách thức vì các phần mềm phụ trợ khác nhau hỗ trợ các loại mạch khác nhau. Do đó, giao diện người dùng có thể khác nhau tùy thuộc vào chương trình phụ trợ mà chúng muốn giao tiếp.

Các phần mềm phụ trợ SNARK thường hỗ trợ cái gọi là mạch số học, có nghĩa là đầu vào của mạch là các phần tử của một trường hữu hạn nào đó và các cổng của mạch thực hiện phép cộng và phép nhân hai phần tử trường. Các mạch này gần tương ứng với các chương trình máy tính đường thẳng (không có nhánh, câu lệnh điều kiện, v.v.) có bản chất đại số - nghĩa là, kiểu dữ liệu ban đầu của chúng là các phần tử trường. 

Hầu hết các chương trình phụ trợ thực sự hỗ trợ tổng quát hóa các mạch số học thường được gọi là các trường hợp Thỏa mãn ràng buộc Xếp hạng-1 (R1CS). Với ngoại lệ đáng chú ý của Groth16 và những người tiền nhiệm của nó, những SNARK này cũng có thể được tạo ra để hỗ trợ các IR khác. Ví dụ: StarkWare sử dụng một thứ gọi là Biểu diễn Trung gian Đại số (AIR), cũng tương tự như một khái niệm được gọi là Số học PlonKish có thể được hỗ trợ bởi PlonK và các chương trình phụ trợ khác. Khả năng của một số phụ trợ hỗ trợ nhiều IR chung hơn có thể làm giảm chi phí của các giao diện người dùng tạo ra các IR đó. 

Các phần hỗ trợ cũng khác nhau về các trường hữu hạn mà chúng hỗ trợ ban đầu. Tôi sẽ thảo luận thêm về vấn đề này trong phần tiếp theo.

Các cách tiếp cận khác nhau đối với giao diện người dùng

Một số chương trình máy tính (rất đặc biệt) đương nhiên tương ứng với các mạch số học. Một ví dụ là chương trình máy tính thực hiện phép nhân đơn thuần các ma trận trên một số trường. Nhưng hầu hết các chương trình máy tính không phải là đường thẳng cũng không phải là đại số. Chúng thường liên quan đến các câu lệnh có điều kiện, các phép toán như phép chia số nguyên hoặc số học dấu phẩy động không tự nhiên tương ứng với số học trường hữu hạn, v.v. Trong những trường hợp này, chi phí giao diện người dùng sẽ rất lớn. 

Một cách tiếp cận giao diện người dùng phổ biến là tạo ra các mạch về cơ bản thực thi từng bước một số CPU đơn giản, còn được gọi là máy ảo (VM). Các nhà thiết kế giao diện người dùng chỉ định một tập hợp các “hoạt động nguyên thủy” tương tự như các hướng dẫn lắp ráp cho bộ xử lý máy tính thực. Các nhà phát triển muốn sử dụng giao diện người dùng sẽ viết “chương trình kiểm tra nhân chứng” trực tiếp bằng ngôn ngữ hợp ngữ hoặc bằng một số ngôn ngữ cấp cao hơn như Solidity và để các chương trình của họ tự động được biên dịch thành mã hợp ngữ. 

Ví dụ, StarkWare's Cairo là một ngôn ngữ hợp ngữ rất hạn chế, trong đó các lệnh hợp ngữ cho phép gần như cho phép cộng và nhân trên một trường hữu hạn, các lệnh gọi hàm và đọc và ghi vào một bộ nhớ bất biến (tức là ghi một lần). Cairo VM là một kiến ​​trúc von Neumann, có nghĩa là các mạch được tạo ra bởi giao diện người dùng về cơ bản lấy một chương trình Cairo làm đầu vào công khai và "chạy" chương trình trên nhân chứng. Ngôn ngữ Cairo là Turing Complete - mặc dù tập lệnh giới hạn của nó, nó có thể mô phỏng các kiến ​​trúc tiêu chuẩn hơn, mặc dù làm như vậy có thể tốn kém. Giao diện người dùng Cairo biến các chương trình Cairo thực thi T hướng dẫn ban đầu vào cái được gọi là “mức độ-2 AIR với T hàng và khoảng 50 cột." Gì chính xác thì điều này có nghĩa là không quan trọng đối với bài đăng này, nhưng theo như các chuyên gia SNARK có liên quan, điều này tương ứng với các mạch có từ 50 đến 100 cổng cho mỗi T các bước của CPU Cairo. 

RISC Không có cách tiếp cận tương tự như Cairo, nhưng với máy ảo được gọi là Kiến trúc RISC-V, một kiến ​​trúc mã nguồn mở với hệ sinh thái phần mềm phong phú đang ngày càng phổ biến. Là một tập lệnh rất đơn giản, việc thiết kế giao diện người dùng SNARK hiệu quả hỗ trợ nó có thể tương đối dễ kiểm soát (ít nhất là so với các kiến ​​trúc phức tạp như x86 hoặc ARM). Kể từ tháng XNUMX, RISC Zero đang chuyển chương trình thi hành T hướng dẫn RISC-V nguyên thủy thành AIR cấp độ 5 với 3T hàng và 160 cột. Điều này tương ứng với các mạch có ít nhất 500 cổng mỗi bước của CPU RISC-V. Những cải tiến hơn nữa được dự đoán trong tương lai gần.

Các dự án zkEVM khác nhau (ví dụ: zkSync 2.0, Scroll, Polygon's zkEVM) đưa máy ảo trở thành (duh) Máy ảo Ethereum. Quá trình biến mọi lệnh EVM thành một “tiện ích” tương đương (tức là một mạch được tối ưu hóa thực hiện lệnh) về cơ bản có liên quan nhiều hơn so với các kiến ​​trúc Cairo và RISC-V đơn giản hơn. Vì lý do này và lý do khác, một số dự án zkEVM không trực tiếp triển khai tập lệnh EVM mà là biên dịch các chương trình Solidity cấp cao sang các ngôn ngữ hợp ngữ khác trước khi biến chúng thành các mạch. Kết quả hoạt động từ các dự án này đang chờ xử lý.

Các dự án “trình giả lập CPU” như RISC-V và Cairo tạo ra một mạch duy nhất có thể xử lý tất cả các chương trình bằng hợp ngữ liên quan. Các cách tiếp cận thay thế là “giống ASIC”, tạo ra các mạch khác nhau cho các chương trình khác nhau. Cách tiếp cận giống ASIC này có thể mang lại các mạch nhỏ hơn cho một số chương trình, đặc biệt khi lệnh hợp ngữ mà chương trình thực hiện ở mỗi bước thời gian không phụ thuộc vào đầu vào của chương trình. Ví dụ, nó có thể tránh hoàn toàn chi phí giao diện người dùng cho các chương trình đường thẳng như phép nhân ma trận đơn giản. Nhưng cách tiếp cận ASIC cũng có vẻ rất hạn chế; Theo như tôi biết, không biết làm thế nào để sử dụng nó để hỗ trợ các vòng lặp mà không có giới hạn lặp được xác định trước. 

Thành phần cuối cùng của frontend overhead xuất phát từ thực tế là tất cả SNARK sử dụng các mạch hoạt động trên các trường hữu hạn. CPU trên máy tính xách tay của bạn có thể nhân hoặc cộng hai số nguyên với một lệnh máy duy nhất. Nếu giao diện người dùng xuất một mạch qua một trường có đặc tính đủ lớn, về cơ bản nó có thể mô phỏng phép nhân hoặc phép cộng đó thông qua thao tác trường tương ứng. Tuy nhiên, việc thực hiện thao tác trường trên một CPU thực thường sẽ yêu cầu nhiều lệnh máy (mặc dù một số bộ xử lý hiện đại có hỗ trợ riêng cho một số trường nhất định). 

Một số phần mềm phụ trợ SNARK cho phép lựa chọn trường linh hoạt hơn những phần khác. Ví dụ: nếu chương trình phụ trợ sử dụng một nhóm mật mã G, trường của mạch phải khớp với số phần tử trong G, điều này có thể bị hạn chế. Ngoài ra, không phải tất cả các trường đều hỗ trợ các thuật toán FFT thực tế. 

Chỉ có một SNARK được triển khai, phanh gấp, vốn dĩ hỗ trợ tính toán trên các trường tùy ý (đủ lớn). Cùng với nó con cháu, nó có hiệu suất phát ngôn cụ thể nhanh nhất được biết đến ngay cả trên các lĩnh vực mà các SNARK khác hỗ trợ, nhưng các bằng chứng của nó hiện quá lớn đối với nhiều ứng dụng blockchain. Công việc gần đây tìm cách cải thiện kích thước bằng chứng, nhưng câu tục ngữ tiệm cận chậm hơn và ở đó trông như thể là rào cản đến tính thực tế.

Một số dự án đã chọn làm việc trên các lĩnh vực có số học đặc biệt nhanh. Ví dụ, Plonky2 và những người khác sử dụng trường đặc điểm 2⁶⁴ - 2³² + 1 vì số học trong trường này có thể được triển khai nhanh hơn nhiều lần so với các trường ít cấu trúc hơn. Tuy nhiên, việc sử dụng đặc tính nhỏ như vậy có thể dẫn đến những thách thức trong việc biểu diễn hiệu quả số học số nguyên thông qua các phép toán trường (ví dụ: nhân hai số nguyên không dấu 32 bit có thể mang lại kết quả lớn hơn đặc tính trường). 

 Nhưng không có vấn đề gì, để tất cả SNARK phổ biến hiện nay đạt được 128 bit bảo mật (mà không tăng đáng kể chi phí xác minh), chúng phải làm việc trên một trường có kích thước lớn hơn 2¹²⁸. Theo như tôi có thể nói, điều này có nghĩa là mỗi hoạt động trường sẽ yêu cầu ít nhất khoảng mười phép nhân máy 64-bit, và nhiều phép cộng và phép toán bit hơn đáng kể. Do đó, người ta phải tính đến ít nhất một thứ tự cường độ chi phí giao diện người dùng do nhu cầu về các mạch hoạt động trên các trường hữu hạn. 

Tóm lại, các giao diện người dùng hiện có sử dụng trừu tượng hóa máy ảo tạo ra các mạch có cổng 100x đến 1000x mỗi bước của máy ảo và có thể nhiều hơn nữa đối với các máy ảo phức tạp hơn. Trên hết, số học trường hữu hạn chậm hơn ít nhất 10 lần so với các lệnh tương tự trên bộ xử lý hiện đại (có thể có ngoại lệ nếu bộ xử lý có hỗ trợ tích hợp cho các trường nhất định). “Phương pháp tiếp cận giao diện người dùng ASIC” có thể giảm bớt một số chi phí này nhưng hiện đang bị giới hạn trong các loại chương trình mà nó có thể hỗ trợ.

Các nút thắt cổ chai phụ trợ là gì?

SNARK để đáp ứng yêu cầu của mạch thường được thiết kế bằng cách kết hợp một giao thức an toàn thông tin về mặt lý thuyết được gọi là “IOP đa thức”Với một giao thức mật mã được gọi là“chương trình cam kết đa thức. ” Trong hầu hết các trường hợp, điểm nghẽn cụ thể cho câu tục ngữ là sơ đồ cam kết đa thức. Đặc biệt, những SNARK này có câu tục ngữ cam kết bằng mật mã đối với một hoặc nhiều đa thức có mức độ (ít nhất là) |C|, số lượng cổng trong mạch C. 

Đổi lại, nút thắt cổ chai bê tông trong sơ đồ cam kết đa thức sẽ phụ thuộc vào sơ đồ được sử dụng và kích thước mạch. Nhưng nó sẽ luôn là một trong ba phép toán sau: tính toán FFT, lũy thừa trong một nhóm mật mã, hoặc Merkle-băm. Merkle-băm thường chỉ là một nút cổ chai nếu mạch nhỏ, vì vậy chúng ta sẽ không thảo luận thêm về nó. 

Các cam kết đa thức dựa trên nhật ký rời rạc

Trong các cam kết đa thức dựa trên độ khó của bài toán logarit rời rạc trong một nhóm mật mã G (KZG, Chống đạn, xuồng ba lávà Hyrax-cam kết), câu tục ngữ phải tính toán một Cam kết vector Pedersen thành các hệ số của đa thức. Điều này liên quan đến một lũy thừa nhiều, có kích thước bằng bậc của đa thức. Trong SNARK, mức độ này thường là kích thước |C| của mạch C.

Thực hiện một cách ngây thơ, một lũy thừa nhiều kích thước |C| yêu cầu khoảng 1.5·|C|·đăng nhập |G| ≈ 400·|C| hoạt động nhóm, ở đâu |G| biểu thị số phần tử trong nhóm G. Tuy nhiên, có một cách tiếp cận, được gọi là thuật toán Pippenger, có thể giảm điều này bằng hệ số xấp xỉ log |C|. Đối với các mạch lớn (giả sử, |C| ≥ 225), nhật ký này |C| hệ số cụ thể có thể là 25 hoặc hơn, nghĩa là, đối với các mạch lớn, chúng tôi hy vọng rằng cam kết vectơ Pedersen có thể tính toán được với hơn 10 một chút·|C| hoạt động nhóm. Đến lượt mình, mỗi hoạt động nhóm có xu hướng (như một sân bóng rất thô) chậm hơn khoảng 10 lần so với hoạt động trên sân hữu hạn. SNARK sử dụng các cam kết đa thức này đắt tiền đối với P khoảng 100·|C| lĩnh vực hoạt động. 

Thật không may, SNARK hiện tại có chi phí bổ sung nằm trên hệ số 100x ở trên. Ví dụ:

• SpartanCâu tục ngữ sử dụng cam kết đa thức Hyrax phải làm |C|^½ nhiều lũy thừa mỗi kích thước |C|^½, làm suy yếu tốc độ tăng tốc từ thuật toán của Pippenger xuống khoảng hai lần. 
• In Groth16, P phải hoạt động trên một nhóm thân thiện với việc ghép nối, mà các hoạt động của nhóm này thường chậm hơn ít nhất 2 lần so với các nhóm không thân thiện với việc ghép nối. P cũng phải thực hiện 3 phép lũy thừa thay vì 1. Kết hợp lại, điều này dẫn đến ít nhất một thừa số 6 bổ sung chậm lại so với 100·|C| ước tính ở trên. 
• Marlin và PlonK cũng yêu cầu các cặp và các provers của chúng phải cam kết nhiều hơn 3 đa thức. 
• Đối với bất kỳ SNARK nào sử dụng Chống đạn (ví dụ, hào quang2, đại khái là PlonK nhưng với Bulletproofs chứ không phải là cam kết đa thức KZG), câu tục ngữ phải tính toán lôgarit nhiều lũy thừa trong giai đoạn “mở đầu” của lược đồ cam kết và điều này phần lớn xóa bỏ mọi tốc độ tăng tốc của Pippenger. 

Tóm lại, các SNARK đã biết sử dụng cam kết vectơ Pedersen dường như có chi phí phụ trợ ít nhất 200x và lên đến 1000x hoặc hơn. 

Các cam kết đa thức khác

Đối với SNARK sử dụng các cam kết đa thức khác (chẳng hạn như Miễn phí và Ligero-cam kết), điểm nghẽn là câu tục ngữ cần thực hiện các FFT lớn. Ví dụ, trong AIR cấp độ 2 do Cairo sản xuất (với 51 cột và T hàng, một mỗi bước của CPU Cairo), câu châm ngôn được triển khai của StarkWare thực hiện ít nhất 2 FFT trên mỗi cột, có độ dài giữa 16 ·T và 32 ·T. Các hằng số 16 và 32 phụ thuộc vào các thông số nội bộ của FRI do StarkWare thiết lập và có thể được giảm bớt - nhưng với chi phí xác minh tăng lên. 

Lạc quan, FFT có độ dài 32·T mất khoảng 64·T·log (32T) phép nhân trường. Điều này có nghĩa là ngay cả đối với các giá trị tương đối nhỏ của T (ví dụ, T ≥ 2²⁰), số lượng thao tác trường trên mỗi cột ít nhất là 64·25·T= 1600·T. Vì vậy, chi phí phụ trợ dường như ít nhất là hàng nghìn. Hơn nữa, có thể các FFT lớn thậm chí còn bị tắc nghẽn bởi băng thông bộ nhớ hơn là bởi các hoạt động hiện trường. 

Trong một số ngữ cảnh, chi phí phụ trợ của SNARK thực hiện FFT lớn có thể được giảm thiểu bằng một kỹ thuật được gọi là tổng hợp bằng chứng. Đối với bản tổng hợp, điều này có nghĩa là P (dịch vụ tổng hợp) chia một loạt giao dịch lớn thành 10 lô nhỏ hơn. Đối với từng lô nhỏ i, P tạo ra một bằng chứng SNARK πi về hiệu lực của lô. Nhưng mà P không đăng những bằng chứng này lên Ethereum, vì điều này sẽ dẫn đến chi phí gas tăng gần 10 lần. Thay vào đó, SNARK được áp dụng một lần nữa, lần này là để tạo ra một bằng chứng π thiết lập điều đó P biết π₁ …,π₁₀. Đó là, nhân chứng rằng P tuyên bố biết là mười bằng chứng π₁,…, Π₁₀, và việc kiểm tra nhân chứng trực tiếp áp dụng quy trình xác minh SNARK cho từng bằng chứng. Bằng chứng duy nhất này π được đăng lên Ethereum. 

Trong các cam kết đa thức như FRI và Ligero-commit, có một sự căng thẳng mạnh mẽ giữa P thời gian và V chi phí, với các thông số bên trong hoạt động như một núm xoay có thể đổi cái này lấy cái kia. Từ π₁ ,…, Π₁₀ không được đăng lên Ethereum, núm có thể được điều chỉnh để các bằng chứng này lớn và sản xuất chúng nhanh hơn. Chỉ trong ứng dụng cuối cùng của SNARK, để tổng hợp π₁ ,…, Π₁₀ thành một bằng chứng duy nhất π, lược đồ cam kết có cần được định cấu hình để đảm bảo một bằng chứng nhỏ hay không. 

StarkWare có kế hoạch triển khai tổng hợp bằng chứng sắp xảy ra. Đây cũng là tâm điểm của các dự án như Plonky2.

Các điểm nghẽn khác đối với khả năng mở rộng SNARK là gì?

Bài đăng này đã tập trung vào tục ngữ thời gian, nhưng các chi phí tục ngữ khác cũng có thể là điểm nghẽn về khả năng mở rộng. Ví dụ: đối với nhiều phần mềm phụ trợ SNARK, câu tục ngữ cần lưu trữ một số phần tử trường cho mỗi cổng trong Cvà chi phí không gian này có thể rất lớn. Ví dụ, một chương trình ψ chạy trong một giây trên máy tính xách tay có thể thực hiện có lẽ một tỷ hoạt động nguyên thủy trên một bộ xử lý hiện đại. Như chúng ta đã thấy, nói chung, người ta nên mong đợi C để yêu cầu hơn 100 cổng cho mỗi hoạt động như vậy. Điều này có nghĩa là 100 tỷ cổng, tùy thuộc vào SNARK, có thể có nghĩa là hàng chục hoặc hàng trăm terabyte không gian cho P. 

Một ví dụ khác: nhiều SNARK phổ biến (ví dụ: PlonK, Marlin, Groth16) yêu cầu một "buổi lễ thiết lập đáng tin cậy" phức tạp để tạo một "khóa chứng minh" có cấu trúc mà phải được lưu giữ bởi câu tục ngữ. Theo như tôi biết, buổi lễ lớn nhất như vậy đã tạo ra một khóa chứng minh có khả năng hỗ trợ các mạch với khoảng 2²⁸≈250 triệu cổng. Khóa chứng minh có kích thước vài chục gigabyte. 

Trong bối cảnh có thể tổng hợp bằng chứng, những tắc nghẽn này có thể được giảm thiểu đáng kể. 

Sắp tới: triển vọng cho SNARK có thể mở rộng hơn

Cả chi phí đầu vào của giao diện người dùng và phụ trợ có thể là ba cấp độ lớn hoặc hơn. Chúng ta có thể mong đợi những điều này sẽ giảm đáng kể trong tương lai gần không? 

Tôi nghĩ chúng ta sẽ - đến một điểm. Đầu tiên, các chương trình phụ trợ nhanh nhất hiện nay (ví dụ: Spartan và phanh gấpvà các SNARK khác kết hợp giao thức tổng kiểm tra với các cam kết đa thức) có các bằng chứng lớn - thường là căn bậc hai theo kích thước của mạch - vì vậy mọi người không thực sự sử dụng chúng. Tôi hy vọng kích thước bằng chứng và thời gian xác minh sẽ giảm đáng kể trong tương lai gần thông qua bố cục chuyên sâu với SNARK chống nhỏ. Tương tự như tập hợp bằng chứng, điều này có nghĩa là một câu tục ngữ sẽ tạo ra bằng chứng SNARK trước tiên π với SNARK “nhanh nhạy, có khả năng chống chọi lớn”, nhưng không gửi π đến V. Hơn, P sẽ sử dụng SNARK chống nhỏ để tạo ra bằng chứng π' rằng nó biết π, và gửi π' đến V. Điều này có thể loại bỏ một mức độ lớn của các chi phí phụ trợ của SNARK phổ biến ngày nay. 

Thứ hai, tăng tốc phần cứng có thể giúp ích. Một nguyên tắc chung rất đơn giản là GPU có thể tăng tốc độ gấp 10 lần so với CPU và ASIC có tốc độ tăng gấp 10 lần so với GPU. Tuy nhiên, tôi có ba mối quan tâm trên mặt trận này. Đầu tiên, các FFT lớn có thể bị tắc nghẽn bởi băng thông bộ nhớ hơn là các hoạt động trường, vì vậy SNARK thực hiện các FFT như vậy có thể thấy tốc độ giới hạn từ phần cứng chuyên dụng. Thứ hai, trong khi bài đăng này tập trung vào nút thắt cổ chai về cam kết đa thức, nhiều SNARK yêu cầu câu tục ngữ thực hiện các phép toán khác chỉ ít tốn kém hơn một chút. Vì vậy, phá vỡ nút thắt cam kết đa thức (ví dụ: tăng tốc độ nhiều lũy thừa trong SNARK dựa trên log rời rạc) có thể để lại một hoạt động tắc nghẽn mới không tốt hơn nhiều so với hoạt động cũ. (Ví dụ: SNARK bao gồm Groth16, Marlin và PlonK cũng có câu tục ngữ là FFTs, ngoài phép tính đa lũy thừa.) Cuối cùng, các trường và đường cong elip dẫn đến SNARK hiệu quả nhất có thể tiếp tục phát triển trong một thời gian và điều đó có thể tạo ra những thách thức cho việc tăng tốc phương pháp dựa trên ASIC.

Về mặt giao diện người dùng, chúng ta có thể ngày càng thấy rằng phương pháp tiếp cận “trình giả lập CPU” của các dự án như Cairo, RISC Zero, zkEVMs và những dự án khác thực sự mở rộng quy mô khá tốt (về hiệu suất) với sự phức tạp của các tập lệnh CPU. Thật vậy, đây chính xác là hy vọng của các dự án zkEVM khác nhau. Điều này có thể có nghĩa là, trong khi chi phí của giao diện người dùng vẫn là ba cấp độ lớn hơn hoặc nhiều hơn, các giao diện người dùng quản lý để hỗ trợ các máy ảo ngày càng phù hợp với kiến ​​trúc CPU thực. Một mối quan ngại đối kháng là các giao diện người dùng có thể trở nên phức tạp và khó kiểm tra, vì các tiện ích viết tay thực hiện các hướng dẫn ngày càng phức tạp ngày càng tăng. Các phương pháp xác minh chính thức có thể sẽ đóng một vai trò quan trọng trong việc giải quyết mối quan tâm này. 

Cuối cùng, ít nhất là trong các ứng dụng blockchain, chúng ta có thể thấy rằng hầu hết các hợp đồng thông minh xuất hiện trong tự nhiên chủ yếu sử dụng các hướng dẫn đơn giản, thân thiện với SNARK. Điều này có thể cho phép chi phí giao diện người dùng thấp trong thực tế trong khi vẫn giữ được tính tổng quát và cải thiện trải nghiệm của nhà phát triển đi kèm với việc hỗ trợ các ngôn ngữ lập trình cấp cao như Solidity và các bộ hướng dẫn phong phú bao gồm cả EVM. 

***

Justin thaler is một Phó Giáo sư tại Đại học Georgetown. Trước khi gia nhập Georgetown, anh ấy đã có hai năm làm Nhà khoa học nghiên cứu tại Yahoo Labs ở New York, trước đó anh ấy là Nghiên cứu viên tại Viện Simons về lý thuyết máy tính tại UC Berkeley. 

***

Lời cảm ơn: Tôi biết ơn Elena Burger để đề xuất chủ đề của bài đăng này và Arasu Arun, Joseph Bonneauvà Sam Ragsdale cho những nhận xét sâu sắc. Đặc biệt cũng cảm ơn biên tập viên của tôi, Tim Sullivan.

***

Các quan điểm được trình bày ở đây là quan điểm của từng nhân viên AH Capital Management, LLC (“a16z”) được trích dẫn và không phải là quan điểm của a16z hoặc các chi nhánh của nó. Một số thông tin trong đây đã được lấy từ các nguồn của bên thứ ba, bao gồm từ các công ty danh mục đầu tư của các quỹ do a16z quản lý. Mặc dù được lấy từ các nguồn được cho là đáng tin cậy, a16z đã không xác minh độc lập thông tin đó và không đưa ra tuyên bố nào về tính chính xác lâu dài của thông tin hoặc tính thích hợp của nó đối với một tình huống nhất định. Ngoài ra, nội dung này có thể bao gồm các quảng cáo của bên thứ ba; a16z đã không xem xét các quảng cáo đó và không xác nhận bất kỳ nội dung quảng cáo nào có trong đó.

Nội dung này chỉ được cung cấp cho mục đích thông tin và không được dựa vào như lời khuyên về pháp lý, kinh doanh, đầu tư hoặc thuế. Bạn nên tham khảo ý kiến ​​của các cố vấn của riêng mình về những vấn đề đó. Các tham chiếu đến bất kỳ chứng khoán hoặc tài sản kỹ thuật số nào chỉ dành cho mục đích minh họa và không cấu thành khuyến nghị đầu tư hoặc đề nghị cung cấp dịch vụ tư vấn đầu tư. Hơn nữa, nội dung này không hướng đến cũng như không nhằm mục đích sử dụng cho bất kỳ nhà đầu tư hoặc nhà đầu tư tiềm năng nào và không được dựa vào bất kỳ trường hợp nào khi đưa ra quyết định đầu tư vào bất kỳ quỹ nào do a16z quản lý. (Đề nghị đầu tư vào quỹ a16z sẽ chỉ được thực hiện bởi bản ghi nhớ phát hành riêng lẻ, thỏa thuận đăng ký và các tài liệu liên quan khác về bất kỳ quỹ nào như vậy và phải được đọc toàn bộ.) Bất kỳ khoản đầu tư hoặc công ty danh mục đầu tư nào được đề cập, đề cập đến, hoặc được mô tả không phải là đại diện cho tất cả các khoản đầu tư vào xe do a16z quản lý và không thể đảm bảo rằng các khoản đầu tư sẽ sinh lời hoặc các khoản đầu tư khác được thực hiện trong tương lai sẽ có các đặc điểm hoặc kết quả tương tự. Danh sách các khoản đầu tư được thực hiện bởi các quỹ do Andreessen Horowitz quản lý (không bao gồm các khoản đầu tư mà tổ chức phát hành không cho phép a16z tiết lộ công khai cũng như các khoản đầu tư không thông báo vào tài sản kỹ thuật số được giao dịch công khai) có tại https://a16z.com/investments /.

Các biểu đồ và đồ thị được cung cấp bên trong chỉ nhằm mục đích cung cấp thông tin và không nên dựa vào khi đưa ra bất kỳ quyết định đầu tư nào. Hiệu suất trong quá khứ không cho thấy kết quả trong tương lai. Nội dung chỉ nói kể từ ngày được chỉ định. Mọi dự đoán, ước tính, dự báo, mục tiêu, triển vọng và / hoặc ý kiến ​​thể hiện trong các tài liệu này có thể thay đổi mà không cần báo trước và có thể khác hoặc trái ngược với ý kiến ​​của người khác. Vui lòng xem https://a16z.com/disclosures để biết thêm thông tin quan trọng.