Tiêu đề gốc: Khám phá vòng tròn STARKs

Tác giả gốc: Vitalik Buterin,

Người dịch gốc: Kurt Pan, XPTY

Bài viết này giả định rằng bạn đã quen với những kiến thức cơ bản về cách thức hoạt động của SNARK và STARK; nếu chưa, bạn nên đọc một số phần đầu tiên của bài viết này. Đặc biệt cảm ơn Eli ben-Sasson, Shahar Papini, Avihu Levy và những người khác tại starkware vì những phản hồi và thảo luận của họ.

· https://vitalik.eth.limo/general/2024/04/29/binius.html

· https://en.wikipedia.org/wiki/Karatsuba_algorithm

· https://polygon.technology/blog/plonky2- a-deep-dive

· https://blog.icme.io/small-fields-for-zero-know/

Sự thay đổi này đã dẫn đến sự gia tăng đáng kể về tốc độ kiểm chứng, đáng chú ý nhất là khả năng Starkware có thể chạy trên một nền tảng Máy tính xách tay M3 Chứng minh 620.000 hàm băm Poseidon2 mỗi giây trên máy tính. Cụ thể, điều này có nghĩa là miễn là chúng ta sẵn sàng tin tưởng Poseidon2 như một phần của hàm băm thì một trong những phần khó khăn nhất trong việc xây dựng ZK-EVM hiệu quả đã được giải quyết một cách hiệu quả. Nhưng những kỹ thuật này hoạt động như thế nào và bằng chứng mật mã (thường yêu cầu số nguyên lớn để bảo mật) được xây dựng trên các miền này như thế nào? Và làm thế nào để so sánh các giao thức này với các cấu trúc kỳ lạ hơn như Binius? Bài viết này sẽ khám phá một số khác biệt nhỏ, đặc biệt tập trung vào cấu trúc có tên Circle STARK (được triển khai trong stwo của Starkware, plonky3 của Polygon và triển khai python của riêng tôi), có một số thuộc tính độc đáo được thiết kế để Tương thích với miền Mersenne31 hiệu quả.

Các vấn đề thường gặp trong các miền nhỏ

Một trong những "thủ thuật" quan trọng nhất khi thực hiện chứng minh dựa trên hàm băm (hoặc thực tế là bất kỳ loại chứng minh nào) là chứng minh điều gì đó về việc đánh giá đa thức tại các điểm ngẫu nhiên thay vì chứng minh điều gì đó về đa thức cơ bản.

· https://en.wikipedia.org/wiki/Fiat% E2%80%93Shamir_heuristic

Bài toán này có hai cách giải tự nhiên:

· Thực hiện nhiều thử nghiệm ngẫu nhiên

· Mở rộng miền

· https://www2.clarku.edu/faculty/djoyce/complex/mult.html

Việc triển khai ở đây chưa tối ưu (có thể tối ưu hóa bằng Karatsuba), nó chỉ thể hiện nguyên tắc

Thứ Sáu thường lệ

· https://eccc.weizmann.ac.il/ báo cáo /2017/134/

Vòng tròn FRI

· https://elibensasson.blog/why-im-excited-by-circle-stark-and-stwo/

Những điểm này tuân theo định luật cộng, có vẻ quen thuộc với bạn nếu gần đây bạn học lượng giác hoặc nhân số phức:

- https://unacademy.com/content/cbse-class-11/study-material/mathematics/algebra-of-complex-numbers-multiplication/

Từ vòng thứ hai trở đi, cách ánh xạ thay đổi:

Vòng tròn FFT

· https://vitalik.eth.limo/general/2019/05/12/fft.html

https://www.researchgate. net/publication/353344649_Elliptic_Curve_Fast_Fourier_Transform_ECFFT_Part_I_Fast_Polynomial_Algorithms_over_all_Finite_Fields

Từ đây, chúng ta hãy đi sâu vào một số chi tiết bí truyền hơn, đối với những người triển khai vòng tròn STARK, so với STARK thông thường, những chi tiết này sẽ khác nhau.

Khởi động kinh doanh

· https://eprint.iacr.org/2019/336

Đa thức biến mất

Thứ tự bit đảo ngược

Hiệu quả

Do đó, vòng tròn STARK thực sự rất gần với điểm tối ưu! Binius thậm chí còn mạnh mẽ hơn vì nó cho phép trộn và kết hợp các miền có kích thước khác nhau, mang lại khả năng đóng gói bit hiệu quả hơn cho mọi thứ. Binius cũng cung cấp tùy chọn để thực hiện các phép cộng 32 bit mà không cần sử dụng bảng tra cứu. Tuy nhiên, những lợi ích này phải trả giá bằng (theo ý kiến của tôi) độ phức tạp về mặt lý thuyết cao hơn đáng kể, trong khi vòng tròn STARK (và STARK thông thường dựa trên BabyBear) về mặt khái niệm khá đơn giản.

Kết luận: Tôi nghĩ gì về STARK hình tròn?

So với STARK thông thường, Circle STARK không mang lại nhiều sự phức tạp hơn cho các nhà phát triển. Trong khi triển khai nó, ba vấn đề trên về cơ bản là điểm khác biệt duy nhất mà tôi thấy so với FRI thông thường. Toán học đằng sau "đa thức" mà Circle FRI vận hành khá phản trực giác và phải mất một thời gian để hiểu và đánh giá cao. Nhưng điều xảy ra là sự phức tạp này bị ẩn đi nên các nhà phát triển không nhìn thấy nhiều. Sự phức tạp của toán học Vòng tròn được gói gọn chứ không mang tính hệ thống.

Hiểu FRI vòng tròn và FFT vòng tròn cũng là một cách tiếp cận trí tuệ tốt để hiểu các "FFT kỳ lạ" khác: đáng chú ý nhất là FFT miền nhị phân, trước đây được sử dụng trong Binius và LibSTARK , có nhiều cấu trúc kỳ lạ hơn, chẳng hạn như FFT đường cong elip, sử dụng nhiều ánh xạ đến một và có thể được sử dụng tốt với các phép toán điểm trên đường cong elip.

Bằng cách kết hợp các công nghệ Mersenne31, BabyBear và miền nhị phân như Binius, chúng tôi cảm thấy rằng chúng tôi đang tiến gần đến giới hạn về hiệu quả "lớp cơ sở" của STARK. Tại thời điểm này, tôi hy vọng giới hạn tối ưu hóa STARK sẽ chuyển sang hướng số học hiệu quả nhất các nguyên hàm như hàm băm và chữ ký (và tối ưu hóa chính các nguyên hàm đó cho mục đích này), các cấu trúc đệ quy để mở khóa nhiều khả năng song song hơn, Số học hóa các máy ảo để cải thiện kinh nghiệm của nhà phát triển và các nhiệm vụ cấp cao khác.

Liên kết gốc

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia