Khám Phá Circle STARKs

Trong những năm gần đây, xu hướng thiết kế giao thức STARKs là chuyển sang sử dụng các trường nhỏ hơn. Các triển khai STARKs sớm nhất sử dụng trường 256 bit, nhưng thiết kế này có hiệu suất thấp hơn. Để giải quyết vấn đề này, STARKs đã bắt đầu sử dụng các trường nhỏ hơn, chẳng hạn như Goldilocks, Mersenne31 và BabyBear.

Sự chuyển biến này đã nâng cao đáng kể tốc độ chứng minh. Ví dụ, Starkware có thể chứng minh 620,000 giá trị băm Poseidon2 mỗi giây trên máy tính xách tay M3. Điều này có nghĩa là chỉ cần tin tưởng Poseidon2 như một hàm băm, vấn đề của ZK-EVM hiệu quả có thể được giải quyết.

Bài viết này sẽ khám phá cách hoạt động của các công nghệ này, đặc biệt chú ý đến giải pháp Circle STARKs tương thích với trường Mersenne31.

Câu hỏi thường gặp về việc sử dụng các trường nhỏ

Khi tạo ra chứng minh dựa trên băm, một kỹ thuật quan trọng là xác minh gián tiếp tính chất của đa thức thông qua việc đánh giá đa thức tại các điểm ngẫu nhiên. Điều này đã đơn giản hóa đáng kể quá trình chứng minh.

Để ngăn chặn tấn công, chúng ta cần chọn điểm ngẫu nhiên sau khi kẻ tấn công cung cấp đa thức. Trong trường trường 256 bit, điều này rất đơn giản, nhưng trong các trường nhỏ, các giá trị ngẫu nhiên có thể chọn quá ít, dễ dàng bị kẻ tấn công thử tất cả.

Giải pháp có hai loại:

1. Thực hiện nhiều lần kiểm tra ngẫu nhiên
2. Trường mở rộng

Kiểm tra ngẫu nhiên nhiều lần đơn giản và hiệu quả, nhưng hiệu suất thì khá thấp. Trường mở rộng thì tương tự như số phức, có thể thực hiện các phép toán phức tạp hơn trên miền hữu hạn.

FRI Thường

Bước đầu tiên của giao thức FRI là chuyển đổi vấn đề tính toán thành phương trình đa thức. Sau đó, chứng minh rằng nghiệm đa thức được đưa ra thực sự thỏa mãn phương trình và bậc không vượt quá yêu cầu.

FRI xác minh bằng cách đơn giản hóa vấn đề chứng minh bậc của đa thức là d thành vấn đề chứng minh bậc là d/2. Quá trình này có thể được lặp lại nhiều lần, mỗi lần đơn giản hóa vấn đề một nửa.

Chìa khóa của FRI là sử dụng ánh xạ hai trên một để giảm một nửa kích thước của tập dữ liệu. Ánh xạ này cần có khả năng được áp dụng lặp đi lặp lại, cho đến khi cuối cùng chỉ còn lại một giá trị.

Circle FRI

Điểm thú vị của Circle STARKs là đối với số nguyên tố p, có thể tìm thấy một nhóm có kích thước p, có đặc tính tương tự như hai-một. Nhóm này được tạo thành từ các điểm thỏa mãn các điều kiện cụ thể.

Các điểm này tuân theo một quy luật cộng, tương tự như hàm số lượng giác hoặc phép nhân số phức.

Từ vòng thứ hai, sự ánh xạ xảy ra sự thay đổi. Mỗi x đại diện cho hai điểm: (x,y) và (x,-y). (x → 2x^2 - 1) chính là quy tắc nhân điểm.

Circle FFTs

Circle group cũng hỗ trợ FFT, cách cấu trúc tương tự như FRI. Nhưng đối tượng mà Circle FFT xử lý không phải là đa thức theo nghĩa chặt chẽ, mà là không gian Riemann-Roch.

Là một nhà phát triển, bạn gần như có thể bỏ qua những chi tiết này. Chỉ cần lưu trữ đa thức như một giá trị đánh giá và sử dụng FFT khi cần mở rộng ở mức độ thấp.

Quotienting

Trong STARK của nhóm circle, vì không có hàm tuyến tính điểm đơn, cần sử dụng các kỹ thuật khác để thay thế cho phép toán thương truyền thống.

Chúng tôi chứng minh bằng cách đánh giá tại hai điểm, thêm một điểm ảo.

Đa thức biến mất

Trong STARK hình tròn, đa thức biến mất là:

Z_1(x,y) = y Z_2(x,y) = x Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Đảo ngược thứ tự bit

Trong STARKs, việc đánh giá đa thức thường được sắp xếp theo thứ tự ngược. Trong Circle STARKs, cần điều chỉnh thứ tự này để phản ánh cấu trúc gập đặc biệt của nó.

Hiệu suất

Circle STARKs rất hiệu quả. Điều quan trọng là tận dụng không gian trong theo dõi tính toán để thực hiện công việc hữu ích mà không để lại nhiều không gian trống.

So với Binius, Circle STARKs về mặt khái niệm đơn giản hơn, nhưng hiệu suất hơi thấp.

Kết luận

Circle STARKs không phức tạp hơn so với STARKs thông thường đối với các nhà phát triển. Hiểu Circle FRI và FFTs sẽ giúp hiểu các FFT đặc biệt khác.

Tương lai tối ưu hóa STARK có thể tập trung vào:

1. Tối đa hóa hiệu suất của hàm băm và các nguyên tắc mật mã cơ bản khác.
2. Xây dựng đệ quy để tăng cường khả năng song song
3. Máy ảo số học để cải thiện trải nghiệm phát triển