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, thực hiện phép toán modulo trên các số lớn, tương thích với chữ ký dựa trên đường cong ellip. Tuy nhiên, thiết kế này có hiệu suất thấp, xử lý các số lớn tốn lãng phí sức mạnh tính toán. Để giải quyết vấn đề này, STARKs bắt đầu sử dụng các trường nhỏ hơn: Goldilocks, Mersenne31 và BabyBear.

Sự chuyển đổi 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 tin tưởng vào Poseidon2 như một hàm băm, có thể giải quyết vấ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? Làm thế nào để thiết lập chứng minh trên các trường nhỏ? Bài viết này sẽ khám phá những chi tiết này, đặc biệt chú ý đến giải pháp Circle STARKs.

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 làm đơn giản hóa đáng kể quá trình chứng minh.

Ví dụ, giả sử cần chứng minh đa thức A 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 trường trường 256 bit, điều này rất đơn giản: chỉ cần chọn một số ngẫu nhiên 256 bit. Nhưng trong các trường nhỏ, số giá trị r có thể chọn chỉ khoảng 2 tỷ, kẻ tấn công mặc dù khối lượng công việc rất lớn nhưng vẫn có thể cố gắng thử tất cả các khả năng.

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 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 miền hữu hạn. Giới thiệu giá trị mới α thỏa mãn một quan hệ, chẳng hạn như α^2 = một giá trị nào đó. Điều này tạo ra cấu trúc toán học mới, 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. Miền mở rộng chỉ được sử dụng khi cần kết hợp tuyến tính ngẫu nhiên, hầu hết các phép toán vẫn diễn ra trong trường cơ sở.

FRI thông thường

Bước đầu tiên để xây dựng SNARK hoặc STARK là chuyển đổi vấn đề tính toán thành phương trình đa thức P(X,Y,Z)=0. Giải pháp cần chứng minh rằng giá trị được đưa ra là đa thức hợp lý và có bậc hữu hạn. Điều này được thực hiện thông qua việc áp dụng các kết hợp tuyến tính ngẫu nhiên 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

B cách ly hệ số chẵn của A, C cách ly hệ số lẻ. Cho B và C có thể phục hồi A: A(x) = B(x^2) + xC(x^2). 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à tổ hợp ngẫu nhiên, bậc nên là bậc của A.

FRI đơn giản hóa việc xác minh bằng cách giảm chứng minh đa thức bậc d thành chứng minh bậc d/2. Quá trình này có thể được lặp lại nhiều lần, mỗi lần giảm nửa vấn đề. Nếu đầu ra của một giai đoạn không đạt được bậc mong đợi, thì vòng kiểm tra đó sẽ thất bại.

FRI sẽ giảm một nửa số bậc của đa thức và quy mô tập điểm ở mỗi bước. Điều trước là chìa khóa cho sự hoạt động của FRI, điều sau giúp thuật toán chạy rất nhanh: tổng chi phí tính toán là O(N) thay vì O(N*log(N)).

Để giảm dần miền, sử dụng ánh xạ hai trên một. Ánh xạ này cho phép giảm một nửa kích thước tập dữ liệu và có thể lặp lại. Bắt đầu từ nhóm phụ nhân, mỗi phần tử x thì bội số 2x cũng nằm trong tập hợp. Thực hiện bình phương tập hợp S, tập hợp mới S^2 giữ nguyên thuộc tính đó. Đ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 chỉ còn một giá trị.

Mô đun của BabyBear cho phép nhóm nhân tối đa của nó chứa tất cả các giá trị khác không, với kích thước 2^k-1. Điều này rất phù hợp với công nghệ trên, có thể giảm bậc đa thức hiệu quả thông qua việc ánh xạ lặp lại. Kích thước của nhóm nhân Mersenne31 là 2^31-1, chỉ có thể chia cho 2 một lần, sau đó không thể sử dụng công nghệ này.

Miền Mersenne31 rất phù hợp cho tính toán trên CPU/GPU 32 bit. Đặc tính mô đun của nó ( như 2^31-1) cho phép nhiều phép tính có thể được tối ưu hóa bằng thao tác bit: Kết quả vượt quá mô đun có thể được giảm thông qua dịch chuyển. Phép nhân có thể được xử lý hiệu quả bằng các lệnh CPU cụ thể. Các phép toán số học của Mersenne31 nhanh hơn BabyBear khoảng 1.3 lần. Nếu có thể triển khai FRI trên Mersenne31, điều này sẽ nâng cao hiệu suất một cách đáng kể.

Circle FRI

Điểm thông minh 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, có đặc tính tương tự như một cặp một. Nhóm này được cấu thành từ các điểm thỏa mãn các điều kiện nhất định, chẳng hạn như tập hợp các điểm mà x^2 mod p bằng một giá trị nào đó.

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: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 thập tất cả các điểm lại thành một đường thẳng: f0(x) = (F(x,y) + F(x,-y))/2

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

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

Bản ánh 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) là quy tắc nhân điểm. Chúng tôi chuyển đổi tọa độ x của hai điểm đối xứng trên vòng tròn thành tọa độ x của điểm sau khi nhân.

FFT Vòng

Nhóm Circle cũng hỗ trợ FFT, cách cấu trúc tương tự như FRI. Sự khác biệt chính là Circle FFT xử lý không phải đa thức nghiêm ngặt, mà là không gian Riemann-Roch: đa thức mô 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 hầu như có thể bỏ qua điều này. STARK chỉ cần lưu trữ đa thức như một tập hợp các giá trị đánh giá. FFT chỉ được sử dụng cho mở rộng bậ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

Các thao tác thường gặp trên STARK là thực hiện phép toán thương trên các điểm cụ thể. Ví dụ, chứng minh P(x)=y có thể được thực hiện qua các bước sau:

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 là phân số

Trong nhóm STARK của circle, do không qua được hàm tuyến tính đơn điểm, cần những kỹ thuật khác nhau. Có thể xây dựng hàm tiếp tuyến, nhưng nó có bội số 2 tại điểm đó. Do đó, phải đánh giá tại hai điểm để chứng minh.

Nếu P tại x1 bằng y1, tại x2 bằng y2, chúng ta chọn hàm nội suy L tại hai điểm này bằng nhau. Sau đó chứng minh rằng P-L tại hai điểm này bằng không, bằng cách chia L cho L để chứng minh thương Q là một đa thức.

Đa thức biến mất

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

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

Phân vị ngược

Đánh giá đa thức trong STARKs thường được sắp xếp theo thứ tự bit ngược. Trong circle STARKs, cấu trúc gập có một chút khác biệt:

• Bước đầu tiên: (x,y) và (x,-y) ghép đôi
• Bước hai: ghép x với -x
• Bước tiếp theo: ghép p và q, sao cho Q^i(p) = -Q^i(q)

Để điều chỉnh thứ tự ngược, cần đảo ngược từng vị trí ngoại trừ vị trí cuối cùng, dùng vị trí cuối cùng để quyết định có đảo ngược các vị trí khác hay không.

Hiệu suất

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ã ( như hàm băm Poseidon )
3. Tìm kiếm tham số: Phương pháp tính toán hiệu quả chung

Chìa khóa của hiệu suất là tận dụng tối đa không gian theo dõi tính toán. Kích thước trường ở đây là 2^31, không lãng phí không gian nhiều. Các hàm băm như Poseidon tận dụng đầy đủ từng bit của mỗi số trong bất kỳ trường nào.

Binius thông qua việc kết hợp các trường có kích thước khác nhau để đạt được gói bit hiệu quả hơn, nhưng cái giá phải trả là khái niệm trở nên phức tạp hơn. Circle STARKs về bản chất 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. Sự khác biệt chính trong việc thực hiện so với FRI thông thường nằm ở ba vấn đề đã nêu trên. Mặc dù toán học phía sau phức tạp, nhưng sự phức tạp này được ẩn giấu rất tốt.

Hiểu về Circle FRI và FFTs có thể trở thành cách để hiểu các FFT đặc biệt khác, như FFT trong trường nhị phân và FFT trong đường cong ellip.

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. Tương lai của việc tối ưu hóa có thể tập trung vào:

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