Khám phá Circle STARKs

Trong những năm gần đây, thiết kế giao thức STARKs đã có xu hướng 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, tương thích với chữ ký dựa trên đường cong elliptic. Tuy nhiên, thiết kế này có hiệu suất tương đối thấp, việc xử lý các số lớn sẽ lãng phí sức mạnh tính toán. Để 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: đầu tiên là Goldilocks, sau đó là Mersenne31 và BabyBear.

Sự chuyển biến này nâng cao 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. Chỉ cần chúng ta tin tưởng Poseidon2 là hàm băm, chúng ta có thể giải quyết bài toán phát triển ZK-EVM hiệu quả. Vậy những công nghệ này hoạt động như thế nào? Những chứng minh này được thiết lập trên các trường nhỏ hơn như thế nào? Bài viết này sẽ khám phá những chi tiết này, đặc biệt tập trung vào giải pháp Circle STARKs.

Các vấn đề thường gặp khi sử dụng các trường toán học nhỏ hơn

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

Ví dụ, giả sử yêu cầu tạo ra commitment cho đa thức A, phải thỏa mãn A^3(x) + x - A(ωx) = x^N. Giao thức có thể yêu cầu chọn tọa độ ngẫu nhiên r và chứng minh A(r) + r - A(ωr) = r^N. Sau đó, suy ngược A(r) = c, chứng minh Q = (A - c)/(X - r) là một đa thức.

Để ngăn chặn tấn công, cần chọn r sau khi kẻ tấn công cung cấp A. Trong các giao thức dựa trên đường cong elliptic, có thể chọn số ngẫu nhiên 256 bit. Nhưng trong STARKs với trường nhỏ hơn, chỉ có khoảng 2 tỷ giá trị r có thể chọn, kẻ tấn công có thể phá vỡ bằng cách thử tất cả.

Giải pháp có hai:

1. Thực hiện nhiều cuộc 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 có vấn đề về hiệu suất. Trường mở rộng tương tự như số phức, nhưng dựa trên trường hữu hạn. Giới thiệu giá trị mới α, tuyên bố α^2 = một giá trị nào đó. Như vậy có thể thực hiện các phép toán phức tạp hơn trên trường hữu hạn. Trường mở rộng chỉ được sử dụng trong các tình huống như giao thức FRI, hầu hết các phép toán toán học vẫn diễn ra trên trường cơ sở.

FRI thông thường

Khi xây dựng SNARK hoặc STARK, bước đầu tiên là tính toán hóa, chuyển đổi vấn đề tính toán thành phương trình đa thức. Để chứng minh có nghiệm, cần chứng minh giá trị được đề xuất là đa thức hợp lý và có bậc tối đa. Để làm điều này, sử dụng kỹ thuật kết hợp tuyến tính ngẫu nhiên áp dụng từng bước:

1. Giả sử có giá trị đánh giá của đa thức A, cần chứng minh bậc < 2^20
2. Xem xét B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D là tổ hợp tuyến tính ngẫu nhiên của B và C: D = B + rC

Về bản chất, B tách biệt các hệ số chẵn, C tách biệt các hệ số lẻ. Với B và C, A có thể được phục hồi. Nếu bậc của A < 2^20, bậc của B và C lần lượt là bậc của A và bậc của A - 1. D là một tổ hợp tuyến tính ngẫu nhiên, bậc nên là bậc của A.

FRI thông qua việc đơ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, do đó đơn giản hóa quá trình xác minh. 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.

Để đạt được sự giảm dần của miền, sử dụng ánh xạ hai trên một. Ánh xạ này cho phép giảm kích thước tập dữ liệu xuống một nửa và có thể lặp lại. Bắt đầu từ nhóm nhân, thực hiện phép bình phương trên tập S, tập mới S^2 giữ nguyên các thuộc tính như cũ. Điều này cho phép tiếp tục giảm kích thước tập dữ liệu cho đến khi cuối cùng chỉ còn lại một giá trị.

Số mũ BabyBear khiến nhóm nhân lớn nhất của nó bao gồm tất cả các giá trị khác không, kích thước nhóm là 2k-1. Có thể chọn nhóm kích thước 2^k, sau đó áp dụng phương pháp FRI để giảm dần bậc của đa thức xuống 15. Số mũ Mersenne31 khiến kích thước nhóm nhân là 2^31-1, chỉ có thể bị chia cho 2 một lần, sau đó không thể sử dụng các kỹ thuật trên.

Miền Mersenne31 phù hợp cho tính toán trên CPU/GPU 32 bit. Tính chất modulo của nó cho phép nhiều phép toán được thực hiện bằng các thao tác bit hiệu quả. Trong miền Mersenne31, phép toán số học nhanh hơn khoảng 1.3 lần so với miền BabyBear. Nếu có thể triển khai FRI trong miền Mersenne31, sẽ nâng cao hiệu suất tính toán đáng kể.

Circle FRI

Điểm tinh tế của Circle STARKs là, với một số nguyên tố p, có thể tìm thấy một nhóm có kích thước p với đặc tính tương tự như hai trên 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ể, chẳng hạn như tập hợp các điểm mà x^2 mod p bằng một giá trị nhất định.

Những điểm này tuân theo quy tắc cộng. (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Hình thức gấp đôi là: 2 * (x,y) = (2x^2 - 1, 2xy)

Chúng tôi tập trung vào các điểm ở vị trí lẻ trên vòng tròn. Đầu tiên, thu hẹp tất cả các điểm về một đường thẳng: f0(x) = (F(x,y) + F(x,-y))/2

Sau đó thực hiện kết hợp tuyến tính ngẫu nhiên, thu được đa thức một chiều P(x).

Từ vòng thứ hai trở đi, ánh xạ trở thành: f0(2x^2-1) = (F(x) + F(-x))/2

Sự ánh xạ này mỗi lần giảm một nửa kích thước tập hợp. 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

Nhóm Circle cũng hỗ trợ FFT, cách cấu trúc tương tự như FRI. Đối tượng mà Circle FFT xử lý là không gian Riemann-Roch: đa thức theo mô hình tròn (x^2 + y^2 - 1 = 0).

Hệ số đầu ra của Circle FFT là cơ sở cụ thể: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Các nhà phát triển gần như có thể bỏ qua điều này. STARKs chỉ cần lưu trữ đa thức như một tập hợp các giá trị đánh giá. FFT được sử dụng để mở rộng mức độ thấp: với N giá trị đã cho, tạo ra k*N giá trị trên cùng một đa thức.

Giao dịch thương mại

Trong giao thức STARK, thao tác thường gặp là thực hiện phép nhân trên các điểm cụ thể. Ví dụ, chứng minh P(x)=y:

1. Tính toán thương Q = (P - y)/(X - x)
2. Chứng minh Q là đa thức chứ không phải phân số

Trong nhóm circle STARK, do không có hàm tuyến tính tại một điểm đơn, cần sử dụng các kỹ thuật khác để thay thế cho phương pháp thương mại truyền thống. Bằng cách chứng minh qua việc đánh giá tại hai điểm, thêm một điểm ảo mà không cần quan tâm.

Nếu đa thức P tại x1 bằng y1, tại x2 bằng y2, chọn hàm nội suy L tại x1 bằng y1, tại x2 bằng y2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Sau đó chứng minh P - L bằng 0 tại hai điểm này, chứng minh rằng thương Q là một đa thức bằng cách chia L cho L.

Đa thức biến mất

Trong STARK, phương trình đa thức thường có dạng C(P(x), P(next(x))) = Z(x) · H(x), Z(x) bằng không trên toàn bộ miền đánh giá.

Trong STARK hình tròn, hàm tương ứng là: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Đa thức biến mất có thể được suy ra từ hàm gập: STARK thông thường lặp lại x → x^2, STARK hình tròn lặp lại x → 2x^2 - 1.

Đảo ngược thứ tự

Trong STARKs, việc đánh giá đa thức thường được sắp xếp theo thứ tự bit ngược. Ví dụ với n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Sắp xếp này giúp giá trị của các nhóm sớm trong quá trình đánh giá FRI nằm cạnh nhau trong sắp xếp, tiết kiệm không gian.

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

Kích thước 16 của thứ tự ngược gập: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Hiệu quả

Circle STARKs rất hiệu quả. Tính toán thường liên quan đến:

1. Toán học nguyên thủy: được sử dụng cho logic kinh doanh
2. Toán học nguyên thủy: được sử dụng trong mật mã học
3. Tìm kiếm tham số: Phương pháp tính toán hiệu quả chung

Chìa khóa hiệu quả nằm ở việc tận dụng triệt để không gian theo dõi tính toán. Kích thước trường Circle STARKs là 2^31, lãng phí không gian ít hơn.

Binius tốt hơn Circle STARKs, cho phép kết hợp các trường kích thước khác nhau, đạt được việc đóng gói bit hiệu quả hơn. Nhưng cái giá là khái niệm phức tạp hơn, khái niệm Circle STARKs tương đối đơn giản.

Kết luận

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

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

1. Tối đa hóa hiệu quả toán học của hàm băm và chữ ký.
2. Xây dựng đệ quy để kích hoạt nhiều song song hơn
3. Máy ảo số học để cải thiện trải nghiệm của nhà phát triển