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. Để giải quyết vấn đề này, STARKs đã bắt đầu chuyển sang sử dụng các trường nhỏ hơn, như Goldilocks, Mersenne31 và BabyBear.

Sự chuyển đổi này đã nâng cao đáng kể tốc độ chứng minh. Ví dụ, Starkware có thể chứng minh 620.000 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, có thể giải quyết bài toán ZK-EVM hiệu quả.

Bài viết này sẽ khám phá cách thức 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ác 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 mẹo 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 giúp đơn giản hóa đáng kể quá trình chứng minh.

Tuy nhiên, việc thực hiện quá trình lấy mẫu ngẫu nhiên trên các trường nhỏ như vậy có vấn đề về an ninh. Chẳng hạn, trường Mersenne31 chỉ có khoảng 2 tỷ điểm mẫu có thể, điều này là khả thi đối với những kẻ tấn công quyết tâm.

Có hai giải pháp:

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

Nhiều lần kiểm tra đơn giản và hiệu quả, nhưng tồn tại vấn đề về hiệu suất. Trường mở rộng có thể cung cấp nhiều lựa chọn điểm lấy mẫu hơn, từ đó nâng cao tính bảo mật.

FRI thông 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 đề xuất thực sự là một đa thức hợp lý và có bậc tối đa nhất định.

FRI thực hiện điều này bằng cách dần dần đơn giản hóa vấn đề chứng minh bậc đ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 giảm một nửa quy mô vấn đề.

Mỗi bước của FRI sẽ giảm một nửa bậc đa thức và kích thước tập điểm. Thứ nhất là điều kiện then chốt để FRI hoạt động, thứ hai giúp thuật toán chạy cực nhanh.

Circle FRI

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

Từ vòng hai trở đi, sự ánh xạ sẽ thay đổi:

f_0(2x^2-1) = (F(x) + F(-x))/2

Sự ánh xạ này sẽ giảm kích thước của tập điểm một nửa mỗi lần.

FFT vòng tròn

Nhóm Circle cũng hỗ trợ FFT, cách xây dựng tương tự như FRI. Tuy nhiên, đối tượng mà Circle FFT xử lý không phải là đa thức nghiêm ngặt, mà là không gian Riemann-Roch được gọi.

Là một nhà phát triển, bạn gần như có thể bỏ qua điều này. STARKs chỉ yêu cầu bạn lưu trữ đa thức như một tập hợp các giá trị đánh giá. Nơi duy nhất cần FFT là thực hiện mở rộng bậc thấp.

Thương mại toán học

Trong Circle STARKs, do không có hàm tuyến tính có thể thông qua một điểm, cần phải sử dụng các kỹ thuật khác để thay thế cho phương pháp chia truyền thống.

Chúng tôi phải đánh giá ở hai điểm để chứng minh, từ đó thêm một điểm ảo không cần chú ý.

Đa thức biến mất

Trong Circle STARKs, dạng của đ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

Ngược vị trí

Cần điều chỉnh thứ tự ngược trong Circle STARKs để phản ánh cấu trúc gấp đặc biệt của nó. Cụ thể, cần đảo ngược từng vị trí ngoại trừ vị trí cuối cùng, và sử dụng vị trí cuối cùng để quyết định xem có đảo ngược các vị trí khác hay không.

Hiệu suất

Circle STARKs rất hiệu quả. So với SNARKs với trường lớn, chúng có thể tận dụng không gian trong theo dõi tính toán tốt hơn.

Binius tốt hơn Circle STARKs ở một số khía cạnh, nhưng cái giá phải trả là khái niệm phức tạp hơn. So với đó, Circle STARKs đơn giản hơn về mặt khái niệm.

Kết luận

Circle STARKs không phức tạp hơn STARKs thông thường đối với các nhà phát triển. Mặc dù toán học đằng sau rất phức tạp, nhưng sự phức tạp này đã được ẩn giấu một cách tốt đẹp.

Kết hợp các công nghệ như Mersenne31, BabyBear và Binius, chúng ta dường như đang tiến gần đến giới hạn hiệu quả của lớp cơ sở STARKs. Hướng tối ưu hóa trong tương lai có thể bao gồm:

1. Tối đa hóa hiệu suất hàm băm và chữ ký
2. Cấu trúc đệ quy để tăng cường tính song song
3. Tối ưu hóa máy ảo để cải thiện trải nghiệm phát triển