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, điều này khiến cho các giao thức này tương thích với chữ ký dựa trên đường cong elip. 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í rất nhiều 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: trước 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 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, có thể giải quyết vấ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ú trọng vào giải pháp Circle STARKs.
Các câu hỏi thường gặp về việc sử dụng trường nhỏ
Khi tạo ra bằng chứng dựa trên băm, một mẹo quan trọng là gián tiếp xác minh tính chất của đa thức thông qua kết quả đánh giá của đ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ử yêu cầu tạo ra một lời hứa 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 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 phải chọn r sau khi kẻ tấn công cung cấp A. Trong giao thức trường lớn, có thể chọn 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ó thể chọn, kẻ tấn công có thể thử tất cả các khả năng.
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 gặp 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 α^2 = một giá trị nào đó, tạo ra cấu trúc toán học mới. Điều này cho phép chúng ta có nhiều giá trị lựa chọn hơn, nâng cao tính bảo mật.
Regular FRI
Bước đầu tiên của giao thức FRI thường là số hóa, chuyển đổi vấn đề tính toán thành phương trình P(X,Y,Z)=0, trong đó P là đa thức, X, Y, Z là các tham số. Giải phương trình tương đương với việc giải quyết vấn đề gốc.
Để chứng minh tính đúng đắn của giải pháp, cần chứng minh rằng giá trị được đưa ra là một đa thức hợp lý và có bậc tối đa. Sử dụng kỹ thuật tổ hợp tuyến tính ngẫu nhiên:
Giả sử có giá trị đánh giá của đa thức A, cần chứng minh rằng bậc của nó < 2^20
D là tổ hợp tuyến tính ngẫu nhiên của B và C: D = B + rC
Về cơ bản, B tách biệt hệ số chẵn, C tách biệt hệ số lẻ. B và C có thể phục hồi A. 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 như một tổ hợp ngẫu nhiên, bậc của nó nên là bậc của A.
FRI lặp lại quá trình đơn giản hóa này, mỗi lần giảm một nửa vấn đề. Thiết kế này phát hiện hiệu quả các đầu vào không đáp ứng yêu cầu.
Circle FRI
Điều tinh tế của Circle STARKs chính là ở đây. 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 cặp hai. Nhóm này bao gồm các điểm thỏa mãn những đ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ị nào đó.
Những điểm này tuân theo quy luật 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 hình tròn, thu gọn tất cả các điểm vào 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, thu đượ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
Phép ánh xạ này sẽ giảm kích thước tập hợp một nửa mỗi lần. 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 tạo tương tự như FRI. Nhưng đối tượng mà Circle FFT xử lý là không gian Riemann-Roch, không phải đa thức nghiêm ngặt.
Với tư cách là nhà phát triển, có thể bỏ qua điểm này. STARKs chỉ cần lưu trữ đa thức dưới dạng tập hợp giá trị đánh giá. FFT chủ yếu được sử dụng cho việc 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.
Chia
Trong Circle STARKs, do 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. Bằng cách chứng minh tại hai điểm đánh giá, thêm một điểm ảo.
Nếu đa thức P bằng y1 tại x1, bằng y2 tại x2, chọn hàm nội suy L có giá trị bằng nhau tại hai điểm này. Sau đó, chứng minh P-L bằng 0 tại hai điểm, bằng cách chia L để được thương Q là đa thức.
Các đa thức biến mất
Đa thức biến mất trong Circle STARKs 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: sử dụng lại x → 2x^2 - 1.
Đảo ngược thứ tự bit
Cần điều chỉnh thứ tự ngược trong Circle STARKs: đả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.
Circle STARKs rất hiệu quả. Tính toán thường liên quan đến:
Toán học gốc của logic kinh doanh
Số học nguyên thủy của mật mã
Tìm kiếm tham số
Chìa khóa hiệu suất là tận dụng tối đa không gian theo dõi tính toán. Trường số nguyên 31 bit giảm thiểu lãng phí. Binius kết hợp các trường kích thước khác nhau hiệu quả hơn, nhưng khái niệm phức tạp hơn.
Kết luận
Circle STARKs không phức tạp đối với các nhà phát triển. Việc hiểu toán học đằng sau cần thời gian, nhưng sự phức tạp được ẩn giấu rất tốt. Nó cũng là một con đường để hiểu các FFT đặ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 trong tương lai có thể bao gồm:
Tối đa hóa hiệu suất của các nguyên thủy mật mã cơ bản như hàm băm
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.
Khám Phá Circle STARKs: Cuộc Cách Mạng Chứng Minh Hiệu Quả Mang Lại Từ Các Trường Nhỏ
Khám Phá Sâu Về 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, điều này khiến cho các giao thức này tương thích với chữ ký dựa trên đường cong elip. 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í rất nhiều 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: trước 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 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, có thể giải quyết vấ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ú trọng vào giải pháp Circle STARKs.
Các câu hỏi thường gặp về việc sử dụng trường nhỏ
Khi tạo ra bằng chứng dựa trên băm, một mẹo quan trọng là gián tiếp xác minh tính chất của đa thức thông qua kết quả đánh giá của đ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ử yêu cầu tạo ra một lời hứa 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 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 phải chọn r sau khi kẻ tấn công cung cấp A. Trong giao thức trường lớn, có thể chọn 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ó thể chọn, kẻ tấn công có thể thử tất cả các khả năng.
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 gặp 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 α^2 = một giá trị nào đó, tạo ra cấu trúc toán học mới. Điều này cho phép chúng ta có nhiều giá trị lựa chọn hơn, nâng cao tính bảo mật.
Regular FRI
Bước đầu tiên của giao thức FRI thường là số hóa, chuyển đổi vấn đề tính toán thành phương trình P(X,Y,Z)=0, trong đó P là đa thức, X, Y, Z là các tham số. Giải phương trình tương đương với việc giải quyết vấn đề gốc.
Để chứng minh tính đúng đắn của giải pháp, cần chứng minh rằng giá trị được đưa ra là một đa thức hợp lý và có bậc tối đa. Sử dụng kỹ thuật tổ hợp tuyến tính ngẫu nhiên:
Về cơ bản, B tách biệt hệ số chẵn, C tách biệt hệ số lẻ. B và C có thể phục hồi A. 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 như một tổ hợp ngẫu nhiên, bậc của nó nên là bậc của A.
FRI lặp lại quá trình đơn giản hóa này, mỗi lần giảm một nửa vấn đề. Thiết kế này phát hiện hiệu quả các đầu vào không đáp ứng yêu cầu.
Circle FRI
Điều tinh tế của Circle STARKs chính là ở đây. 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 cặp hai. Nhóm này bao gồm các điểm thỏa mãn những đ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ị nào đó.
Những điểm này tuân theo quy luật 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 hình tròn, thu gọn tất cả các điểm vào 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, thu đượ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
Phép ánh xạ này sẽ giảm kích thước tập hợp một nửa mỗi lần. 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 tạo tương tự như FRI. Nhưng đối tượng mà Circle FFT xử lý là không gian Riemann-Roch, không phải đa thức nghiêm ngặt.
Với tư cách là nhà phát triển, có thể bỏ qua điểm này. STARKs chỉ cần lưu trữ đa thức dưới dạng tập hợp giá trị đánh giá. FFT chủ yếu được sử dụng cho việc 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.
Chia
Trong Circle STARKs, do 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. Bằng cách chứng minh tại hai điểm đánh giá, thêm một điểm ảo.
Nếu đa thức P bằng y1 tại x1, bằng y2 tại x2, chọn hàm nội suy L có giá trị bằng nhau tại hai điểm này. Sau đó, chứng minh P-L bằng 0 tại hai điểm, bằng cách chia L để được thương Q là đa thức.
Các đa thức biến mất
Đa thức biến mất trong Circle STARKs 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: sử dụng lại x → 2x^2 - 1.
Đảo ngược thứ tự bit
Cần điều chỉnh thứ tự ngược trong Circle STARKs: đả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.
16 kích thước gập ngược thứ tự là: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
Hiệu suất
Circle STARKs rất hiệu quả. Tính toán thường liên quan đến:
Chìa khóa hiệu suất là tận dụng tối đa không gian theo dõi tính toán. Trường số nguyên 31 bit giảm thiểu lãng phí. Binius kết hợp các trường kích thước khác nhau hiệu quả hơn, nhưng khái niệm phức tạp hơn.
Kết luận
Circle STARKs không phức tạp đối với các nhà phát triển. Việc hiểu toán học đằng sau cần thời gian, nhưng sự phức tạp được ẩn giấu rất tốt. Nó cũng là một con đường để hiểu các FFT đặ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 trong tương lai có thể bao gồm: