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 đầu tiên sử dụng trường 256 bit, tức là thực hiện phép toán modulo trên các số lớn. Tuy nhiên, thiết kế này có hiệu suất thấp, việc xử lý các số lớn sẽ lãng phí nhiều 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: đầu tiên là Goldilocks, sau đó là Mersenne31 và BabyBear.
Sự chuyển đổi này đã nâng cao đáng kể tốc độ chứng minh. Ví dụ, Starkware hiện có thể chứng minh 620.000 hàm băm Poseidon2 mỗi giây trên một chiếc laptop M3. Điều này có nghĩa là chỉ cần chúng ta tin tưởng Poseidon2 như một hàm băm, chúng ta 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? Chứng minh trên trường nhỏ được xây dựng ra sao? Bài viết này sẽ khám phá những chi tiết này, đặc biệt chú ý đến Circle STARKs, một giải pháp tương thích với trường Mersenne31.
Các vấn đề thường gặp khi sử dụng trường nhỏ
Khi tạo ra chứng minh dựa trên hàm băm, một mẹo quan trọng là xác thực gián tiếp tính chất đ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 có thể đơn giản hóa đáng kể quá trình chứng minh.
Ví dụ, giả sử giao thức yêu cầu bạn tạo một commitment cho đ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 bạn chọn tọa độ ngẫu nhiên r và chứng minh A(r)^3 + r - A(ωr) = r^N. Sau đó, suy diễn A(r) = c, bạn chứng minh Q = (A - c)/(X - r) là một đa thức.
Để ngăn chặn cuộc tấn công, chúng ta 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 ellip, điều này rất đơn giản: chúng ta có thể chọn một số ngẫu nhiên 256 bit làm r. Nhưng trong STARKs trường nhỏ, chỉ có khoảng 2 tỷ giá trị r có sẵn, kẻ tấn công có thể giải mã thông qua phương pháp thử tất cả.
Vấn đề này có hai giải pháp:
Thực hiện nhiều lần kiểm tra ngẫu nhiên
Trường mở rộng
Nhiều lần kiểm tra ngẫu nhiên đơn giản và hiệu quả, nhưng có thể gặp vấn đề về hiệu suất. Miền mở rộng tương tự như số phức, nhưng dựa trên miền hữu hạn. Chúng tôi giới thiệu giá trị mới α, tuyên bố rằng α^2 = một giá trị nào đó. Như vậy, đã tạo ra một 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.
Thông qua việc mở rộng miền, chúng tôi có đủ giá trị để lựa chọn, đáp ứng nhu cầu an toàn. Phần lớn các phép toán toán học vẫn được thực hiện trên trường cơ sở, chỉ sử dụng các trường lớn hơn khi cần tăng cường an toàn.
FRI Thường
FRI (Fast Reed-Solomon Interactive) giao thức là bước quan trọng trong việc xây dựng SNARK hoặc STARK. Nó đơn giản hóa quy trình xác minh bằng cách biến vấn đề chứng minh đa thức bậc d thành vấn đề chứng minh đa thức bậc d/2. Quá trình này có thể được lặp lại nhiều lần, mỗi lần đều giảm nửa vấn đề.
Cách hoạt động của FRI là lặp lại quá trình đơn giản hóa. Bắt đầu từ việc chứng minh bậc của đa thức là d, thông qua một loạt các bước, cuối cùng chứng minh bậc là d/2. Sau mỗi lần đơn giản hóa, bậc của đa thức được tạo ra sẽ giảm dần. Nếu đầu ra ở một giai đoạn nào đó không đạt yêu cầu, thì vòng kiểm tra đó sẽ thất bại.
Để đạt được sự giảm dần của miền, đã sử dụng ánh xạ hai một. Ánh xạ này cho phép giảm một nửa kích thước tập dữ liệu, đồng thời giữ nguyên thuộc tính. Phép toán này có thể được tưởng tượng như quá trình kéo dài đoạn thẳng trên vòng tròn hai vòng quanh vòng tròn.
Để công nghệ ánh xạ có hiệu quả, kích thước của nhóm nhân gốc cần có một bội số lớn của 2. Mô-đun của BabyBear cho phép nhóm nhân tối đa bao gồm tất cả các giá trị khác 0, rất phù hợp với công nghệ này. Kích thước nhóm nhân của Mersenne31 chỉ có một bội số 2, hạn chế phạm vi ứng dụng của nó.
Miền Mersenne31 rất phù hợp cho các phép toán số học trên CPU/GPU 32 bit, 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 đáng kể hiệu quả tính toán.
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ư một quan hệ hai chiều. 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.
Các điểm này tuân theo quy tắc cộng: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
Hình thức bội đôi là: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI trước tiên sẽ hội tụ tất cả các điểm về một đường thẳng, sau đó thực hiện kết hợp tuyến tính ngẫu nhiên để có được đa thức một chiều P(x). Bắt đầu từ vòng thứ hai, ánh xạ trở thành: f0(2x^2-1) = (F(x) + F(-x))/2
Bản đồ này giảm nửa kích thước tập hợp mỗi lần, 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 đã nhân đôi. Điều này có thể được thực hiện trong không gian hai chiều, nhưng thao tác một chiều hiệu quả hơn.
Circle FFTs
Circle group 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, chứ không phải là đa thức nghiêm ngặt. Hệ số đầu ra của Circle FFT là cơ sở đặc trưng cho Circle FFT.
Là một nhà phát triển, bạn gần như có thể hoàn toàn bỏ qua điều này. STARKs chỉ cần lưu trữ các đa thức dưới dạng 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: với N giá trị, tạo ra k*N giá trị trên cùng một đa thức.
Phân số
Trong Circle STARKs, do không có hàm tuyến tính có thể được tính qua một điểm, cần phải sử dụng các kỹ thuật khác thay thế cho phép toán thương mại truyền thống. Chúng tôi buộc phải chứng minh bằng cách đánh giá tại hai điểm, thêm một điểm ảo.
Nếu đa thức P bằng y1 tại x1 và bằng y2 tại x2, chúng ta chọn hàm nội suy L sao cho nó bằng nhau tại hai điểm này. Sau đó chứng minh rằng P-L bằng 0 tại hai điểm, bằng cách chia L cho L để chứng minh thương Q là một đa thức.
Các đa thức biến mất
Trong Circle STARKs, đa thức biến mất là:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Điều này có thể được suy ra từ hàm gập: trong Circle STARKs, lặp lại x → 2x^2 - 1. Vòng đầu tiên cần xử lý đặc biệt.
Đảo ngược thứ tự bit
Circle STARKs sử dụng thứ tự bit ngược đã chỉnh sửa, đảo ngược từng bit ngoại trừ bit cuối cùng, dùng bit cuối cùng để quyết định có đảo ngược các bit khác hay không. Điều này phản ánh cấu trúc gấp đặc trưng của Circle STARKs.
Hiệu quả
Circle STARKs rất hiệu quả. Tính toán thường liên quan đến:
Toán học nguyên sinh: dùng cho logic kinh doanh
Số học nguyên sinh: sử dụng trong mật mã ( như băm Poseidon )
Tìm tham số: Thực hiện các phép tính khác nhau thông qua bảng tra cứu giá trị
Circle STARKs tận dụng không gian tính toán đầy đủ, lãng phí ít hơn. Kém hơn Binius một chút, nhưng khái niệm đơn giản hơn.
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. Hiểu Circle FRI và FFTs có thể giúp hiểu các FFTs đặc biệt khác. Hiện tại, hiệu suất của lớp cơ sở STARKs gần đạt giới hạn, hướng tối ưu hóa trong tương lai có thể bao gồm:
Tối đa hóa hiệu quả toán học của hàm băm và chữ ký
Trang này có thể chứa nội dung của bên thứ ba, được cung cấp chỉ nhằm mục đích thông tin (không phải là tuyên bố/bảo đảm) và không được coi là sự chứng thực cho quan điểm của Gate hoặc là lời khuyên về tài chính hoặc chuyên môn. Xem Tuyên bố từ chối trách nhiệm để biết chi tiết.
16 thích
Phần thưởng
16
4
Đăng lại
Chia sẻ
Bình luận
0/400
NftBankruptcyClub
· 2giờ trước
Chữ nhỏ hơn nhưng hiệu quả lại cao hơn...666
Xem bản gốcTrả lời0
GasWhisperer
· 2giờ trước
hmm... các trường nhỏ hơn = bằng chứng nhanh hơn, nhưng chúng ta có thể tin tưởng poseidon2 không? thực sự cảm thấy conflicted về sự đánh đổi hiệu suất/bảo mật này.
Xem bản gốcTrả lời0
alpha_leaker
· 2giờ trước
Stark mạnh mẽ đến mức hơi đáng sợ.
Xem bản gốcTrả lời0
ChainDetective
· 2giờ trước
Mới hiểu, cơ bản là tinh giản khối lượng để tính toán nhanh.
Circle STARKs: Khám phá và đột phá trong chứng minh ZK hiệu quả với trường nhỏ
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 đầu tiên sử dụng trường 256 bit, tức là thực hiện phép toán modulo trên các số lớn. Tuy nhiên, thiết kế này có hiệu suất thấp, việc xử lý các số lớn sẽ lãng phí nhiều 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: đầu tiên là Goldilocks, sau đó là Mersenne31 và BabyBear.
Sự chuyển đổi này đã nâng cao đáng kể tốc độ chứng minh. Ví dụ, Starkware hiện có thể chứng minh 620.000 hàm băm Poseidon2 mỗi giây trên một chiếc laptop M3. Điều này có nghĩa là chỉ cần chúng ta tin tưởng Poseidon2 như một hàm băm, chúng ta 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? Chứng minh trên trường nhỏ được xây dựng ra sao? Bài viết này sẽ khám phá những chi tiết này, đặc biệt chú ý đến Circle STARKs, một giải pháp tương thích với trường Mersenne31.
Các vấn đề thường gặp khi sử dụng trường nhỏ
Khi tạo ra chứng minh dựa trên hàm băm, một mẹo quan trọng là xác thực gián tiếp tính chất đ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 có thể đơn giản hóa đáng kể quá trình chứng minh.
Ví dụ, giả sử giao thức yêu cầu bạn tạo một commitment cho đ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 bạn chọn tọa độ ngẫu nhiên r và chứng minh A(r)^3 + r - A(ωr) = r^N. Sau đó, suy diễn A(r) = c, bạn chứng minh Q = (A - c)/(X - r) là một đa thức.
Để ngăn chặn cuộc tấn công, chúng ta 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 ellip, điều này rất đơn giản: chúng ta có thể chọn một số ngẫu nhiên 256 bit làm r. Nhưng trong STARKs trường nhỏ, chỉ có khoảng 2 tỷ giá trị r có sẵn, kẻ tấn công có thể giải mã thông qua phương pháp thử tất cả.
Vấn đề này có hai giải pháp:
Nhiều lần kiểm tra ngẫu nhiên đơn giản và hiệu quả, nhưng có thể gặp vấn đề về hiệu suất. Miền mở rộng tương tự như số phức, nhưng dựa trên miền hữu hạn. Chúng tôi giới thiệu giá trị mới α, tuyên bố rằng α^2 = một giá trị nào đó. Như vậy, đã tạo ra một 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.
Thông qua việc mở rộng miền, chúng tôi có đủ giá trị để lựa chọn, đáp ứng nhu cầu an toàn. Phần lớn các phép toán toán học vẫn được thực hiện trên trường cơ sở, chỉ sử dụng các trường lớn hơn khi cần tăng cường an toàn.
FRI Thường
FRI (Fast Reed-Solomon Interactive) giao thức là bước quan trọng trong việc xây dựng SNARK hoặc STARK. Nó đơn giản hóa quy trình xác minh bằng cách biến vấn đề chứng minh đa thức bậc d thành vấn đề chứng minh đa thức bậc d/2. Quá trình này có thể được lặp lại nhiều lần, mỗi lần đều giảm nửa vấn đề.
Cách hoạt động của FRI là lặp lại quá trình đơn giản hóa. Bắt đầu từ việc chứng minh bậc của đa thức là d, thông qua một loạt các bước, cuối cùng chứng minh bậc là d/2. Sau mỗi lần đơn giản hóa, bậc của đa thức được tạo ra sẽ giảm dần. Nếu đầu ra ở một giai đoạn nào đó không đạt yêu cầu, thì vòng kiểm tra đó sẽ thất bại.
Để đạt được sự giảm dần của miền, đã sử dụng ánh xạ hai một. Ánh xạ này cho phép giảm một nửa kích thước tập dữ liệu, đồng thời giữ nguyên thuộc tính. Phép toán này có thể được tưởng tượng như quá trình kéo dài đoạn thẳng trên vòng tròn hai vòng quanh vòng tròn.
Để công nghệ ánh xạ có hiệu quả, kích thước của nhóm nhân gốc cần có một bội số lớn của 2. Mô-đun của BabyBear cho phép nhóm nhân tối đa bao gồm tất cả các giá trị khác 0, rất phù hợp với công nghệ này. Kích thước nhóm nhân của Mersenne31 chỉ có một bội số 2, hạn chế phạm vi ứng dụng của nó.
Miền Mersenne31 rất phù hợp cho các phép toán số học trên CPU/GPU 32 bit, 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 đáng kể hiệu quả tính toán.
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ư một quan hệ hai chiều. 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.
Các điểm này tuân theo quy tắc cộng: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Hình thức bội đôi là: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI trước tiên sẽ hội tụ tất cả các điểm về một đường thẳng, sau đó thực hiện kết hợp tuyến tính ngẫu nhiên để có được đa thức một chiều P(x). Bắt đầu từ vòng thứ hai, ánh xạ trở thành: f0(2x^2-1) = (F(x) + F(-x))/2
Bản đồ này giảm nửa kích thước tập hợp mỗi lần, 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 đã nhân đôi. Điều này có thể được thực hiện trong không gian hai chiều, nhưng thao tác một chiều hiệu quả hơn.
Circle FFTs
Circle group 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, chứ không phải là đa thức nghiêm ngặt. Hệ số đầu ra của Circle FFT là cơ sở đặc trưng cho Circle FFT.
Là một nhà phát triển, bạn gần như có thể hoàn toàn bỏ qua điều này. STARKs chỉ cần lưu trữ các đa thức dưới dạng 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: với N giá trị, tạo ra k*N giá trị trên cùng một đa thức.
Phân số
Trong Circle STARKs, do không có hàm tuyến tính có thể được tính qua một điểm, cần phải sử dụng các kỹ thuật khác thay thế cho phép toán thương mại truyền thống. Chúng tôi buộc phải chứng minh bằng cách đánh giá tại hai điểm, thêm một điểm ảo.
Nếu đa thức P bằng y1 tại x1 và bằng y2 tại x2, chúng ta chọn hàm nội suy L sao cho nó bằng nhau tại hai điểm này. Sau đó chứng minh rằng P-L bằng 0 tại hai điểm, bằng cách chia L cho L để chứng minh thương Q là một đa thức.
Các đa thức biến mất
Trong Circle STARKs, đa thức biến mất là: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Điều này có thể được suy ra từ hàm gập: trong Circle STARKs, lặp lại x → 2x^2 - 1. Vòng đầu tiên cần xử lý đặc biệt.
Đảo ngược thứ tự bit
Circle STARKs sử dụng thứ tự bit ngược đã chỉnh sửa, đảo ngược từng bit ngoại trừ bit cuối cùng, dùng bit cuối cùng để quyết định có đảo ngược các bit khác hay không. Điều này phản ánh cấu trúc gấp đặc trưng của Circle STARKs.
Hiệu quả
Circle STARKs rất hiệu quả. Tính toán thường liên quan đến:
Circle STARKs tận dụng không gian tính toán đầy đủ, lãng phí ít hơn. Kém hơn Binius một chút, nhưng khái niệm đơn giản hơn.
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. Hiểu Circle FRI và FFTs có thể giúp hiểu các FFTs đặc biệt khác. Hiện tại, hiệu suất của lớp cơ sở STARKs gần đạt giới hạn, hướng tối ưu hóa trong tương lai có thể bao gồm: