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 sản xuất STARKs sớm nhất đã 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, đ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 elliptic. Tuy nhiên, hiệu quả của thiết kế này tương đối thấp, trong hầu hết các trường hợp, việc xử lý tính toán các số lớn này không có mục đích thực tế, và còn 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 tiên là Goldilocks, sau đó là Mersenne31 và BabyBear.

Sự chuyển biến này đã nâng cao tốc độ chứng minh, chẳng hạn như Starkware có thể chứng minh 620.000 giá trị băm Poseidon2 mỗi giây trên một chiếc laptop M3. Điều này có nghĩa là, miễn là chúng ta sẵn lòng tin tưởng Poseidon2 như một hàm băm, thì 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? 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? Các giao thức này so với các giải pháp như Binius ra sao? Bài viết này sẽ khám phá những chi tiết này, đặc biệt chú ý đến một giải pháp có tên là Circle STARKs, giải pháp này có những thuộc tính độc đáo tương thích với trường Mersenne31.

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 chứng minh dựa trên băm ( hoặc bất kỳ loại chứng minh nào ), một kỹ thuật rấ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, có thể gián tiếp xác minh tính chất của đa thức. Phương pháp này có thể đơn giản hóa rất nhiều quá trình chứng minh, vì việc đánh giá tại các điểm ngẫu nhiên thường dễ hơn nhiều so với việc xử lý toàn bộ đa thức.

Ví dụ, giả sử một hệ thống chứng minh yêu cầu bạn tạo ra một cam kết cho một đa thức, A, phải thỏa mãn A^3(x) + x - A(ωx) = x^N(. Đây là một loại chứng minh rất phổ biến trong giao thức ZK-SNARK ). Giao thức có thể yêu cầu bạn chọn một tọa độ ngẫu nhiên r và chứng minh A(r) + 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 các 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. Các tham số được chọn cần đến từ một tập hợp đủ lớn để đảm bảo rằng kẻ tấn công không thể dự đoán hoặc đoán trước những tham số này, từ đó nâng cao tính bảo mật của hệ thống.

Trong các giao thức dựa trên đường cong ellip và STARKs vào năm 2019, vấn đề này rất đơn giản: tất cả các phép toán toán học của chúng tôi đều được thực hiện trên các số 256 bit, vì vậy chúng tôi có thể chọn r là một số ngẫu nhiên 256 bit, như vậy là đủ. Tuy nhiên, trong STARKs trên các trường nhỏ hơn, chúng tôi gặp phải một vấn đề: chỉ có khoảng 2 tỷ giá trị r có thể chọn, do đó một kẻ tấn công muốn giả mạo chứng minh chỉ cần thử 2 tỷ lần, mặc dù khối lượng công việc rất lớn, nhưng đối với một kẻ tấn công quyết tâm, điều đó là hoàn toàn khả thi!

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

Phương pháp thực hiện nhiều kiểm tra ngẫu nhiên là đơn giản và hiệu quả nhất: thay vì kiểm tra tại một tọa độ, tốt hơn là kiểm tra lại tại bốn tọa độ ngẫu nhiên. Điều này về lý thuyết là khả thi, nhưng có vấn đề về hiệu suất. Nếu bạn đang xử lý một đa thức có bậc nhỏ hơn một giá trị nào đó và thực hiện trên một miền có kích thước nhất định, kẻ tấn công có thể thực sự xây dựng một đa thức độc hại trông có vẻ bình thường tại những vị trí này. Do đó, khả năng họ có thể phá hoại giao thức hay không là một vấn đề xác suất, vì vậy cần phải tăng số vòng kiểm tra để nâng cao an toàn tổng thể, đảm bảo có thể phòng thủ hiệu quả trước các cuộc tấn công của kẻ tấn công.

Điều này dẫn đến một giải pháp khác: mở rộng trường, mở rộng trường tương tự như số phức, nhưng nó dựa trên trường hữu hạn. Chúng tôi giới thiệu một giá trị mới, ký hiệu là α, và tuyên bố rằng nó thỏa mãn một mối quan hệ nào đó, chẳng hạn như α^2=some value. Bằng cách này, chúng tôi tạo ra một cấu trúc toán học mới, có khả năng thực hiện các phép toán phức tạp hơn trên trường hữu hạn. Trong trường mở rộng này, việc tính toán phép nhân trở thành phép nhân sử dụng giá trị mới α. Chúng tôi hiện có thể thao tác các cặp giá trị trong trường mở rộng, thay vì chỉ các số đơn lẻ. Ví dụ, nếu chúng tôi làm việc trên các trường như Mersenne hoặc BabyBear, việc mở rộng như vậy cho phép chúng tôi có nhiều lựa chọn giá trị hơn, từ đó tăng cường tính bảo mật. Để tăng cường kích thước trường hơn nữa, chúng tôi có thể áp dụng cùng một kỹ thuật một lần nữa. Vì chúng tôi đã sử dụng α, nên chúng tôi cần định nghĩa một giá trị mới, điều này thể hiện trong Mersenne31 bằng việc chọn α sao cho α^2=some value.

Thông qua việc mở rộng miền, chúng tôi hiện có đủ giá trị để lựa chọn, đáp ứng nhu cầu bảo mật của chúng tôi. Nếu xử lý các đa thức có bậc nhỏ hơn d, mỗi vòng có thể cung cấp 104 bit bảo mật. Điều này có nghĩa là chúng tôi có đủ bảo đảm an ninh. Nếu cần đạt được mức độ bảo mật cao hơn, chẳng hạn như 128 bit, chúng tôi có thể thêm một số công việc tính toán bổ sung vào giao thức để tăng cường độ an toàn.

Miền mở rộng chỉ thực sự được sử dụng trong giao thức FRI(Fast Reed-Solomon Interactive) và các tình huống khác cần các tổ hợp tuyến tính ngẫu nhiên. Hầu hết các phép toán toán học vẫn được thực hiện trên các trường cơ sở, những trường này thường là trường theo mô p hoặc q. Đồng thời, gần như tất cả dữ liệu băm đều được thực hiện trên các trường cơ sở, do đó mỗi giá trị chỉ cần băm bốn byte. Cách làm này có thể tận dụng tính hiệu quả của các trường nhỏ, trong khi khi cần tăng cường an ninh, có thể sử dụng các trường lớn hơn.

FRI Thường

Trong quá trình xây dựng SNARK hoặc STARK, bước đầu tiên thường là arithmetization. Đây là việc chuyển đổi một bài toán tính toán bất kỳ thành một phương trình, trong đó một số biến và hệ số là đa thức. Cụ thể, phương trình này thường có dạng P(X,Y,Z)=0, trong đó P là một đa thức, X, Y và Z là các tham số đã cho, và bộ giải cần cung cấp giá trị cho X và Y. Khi có một phương trình như vậy, nghiệm của phương trình tương ứng với nghiệm của bài toán tính toán cơ bản.

Để chứng minh rằng bạn có một nghiệm, bạn cần chứng minh rằng giá trị bạn đưa ra thực sự là một đa thức hợp lý ( chứ không phải là một phân số, hoặc ở một số nơi trông giống như một đa thức, nhưng ở những nơi khác lại là một đa thức khác, v.v. ), và các đa thức này có một bậc tối đa nhất định. Để làm điều này, chúng tôi đã sử dụng một kỹ thuật kết hợp tuyến tính ngẫu nhiên được áp dụng từng bước:

• Giả sử bạn có giá trị đánh giá của một đa thức A, bạn muốn chứng minh rằng bậc của nó nhỏ hơn 2^20.
• Xem xét đa thức B(x^2) = A(x) + A(-x),C(x^2) = (A(x) - A(-x))/x
• D là một tổ hợp tuyến tính ngẫu nhiên của B và C, tức là D = B + rC, trong đó r là một hệ số ngẫu nhiên.

Về bản chất, những gì xảy ra là B cô lập hệ số chẵn A, và C cô lập hệ số lẻ. Với B và C đã cho, bạn có thể khôi phục đa thức gốc A: A(x) = B(x^2) + xC(x^2). Nếu bậc của A thực sự nhỏ hơn 2^20, thì bậc của B và C sẽ lần lượt là bậc của A và bậc của A trừ đi 1. Bởi vì sự kết hợp của các hạng mục chẵn và lẻ sẽ không làm tăng bậc. Do D là một tổ hợp tuyến tính ngẫu nhiên của B và C, bậc của D cũng nên là bậc của A, điều này cho phép bạn xác minh bậc của A có đáp ứng yêu cầu hay không thông qua bậc của D.

Đầu tiên, FRI đã đơn giản hóa quy trình xác minh bằng cách giảm bài toán chứng minh bậc đa thức là d thành bài toán chứng minh bậc đa thức là d/2. Quá trình này có thể lặp lại nhiều lần, mỗi lần sẽ giảm một nửa bài toán.

Cách thức hoạt động của FRI là lặp lại quá trình đơn giản này. Ví dụ, nếu bạn bắt đầu từ một đa thức có bậc d, qua một loạt các bước, cuối cùng bạn sẽ chứng minh rằng bậc của đa thứ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 giảm dần. Nếu đầu ra ở một giai đoạn nào đó không phải là bậc đa thức mong đợi, thì vòng kiểm tra đó sẽ thất bại. Nếu ai đó cố gắng đẩy một đa thức không phải có bậc d bằng kỹ thuật này, thì trong đầu ra vòng thứ hai, bậc của nó sẽ có xác suất nhất định không phù hợp với mong đợi, và trong vòng thứ ba, khả năng không phù hợp sẽ tăng lên, và cuối cùng, vòng kiểm tra sẽ thất bại. Thiết kế này có thể phát hiện và từ chối hiệu quả các đầu vào không đáp ứng yêu cầu. Nếu tập dữ liệu ở hầu hết các vị trí bằng với một đa thức có bậc d, thì tập dữ liệu này có thể được xác thực qua FRI. Tuy nhiên, để xây dựng một tập dữ liệu như vậy, kẻ tấn công cần biết đa thức thực tế, vì vậy ngay cả khi có một bằng chứng hơi khiếm khuyết cũng cho thấy rằng người chứng minh có khả năng tạo ra một bằng chứng "thực".

Hãy cùng tìm hiểu chi tiết hơn về những gì đang diễn ra ở đây, cũng như những thuộc tính cần thiết để mọi thứ hoạt động bình thường. Ở mỗi bước, chúng ta giảm bậc của đa thức xuống một nửa, đồng thời cũng giảm một nửa tập hợp các điểm mà chúng ta quan tâm là (. Điều đầu tiên là chìa khóa để giao thức FRI) Fast Reed-Solomon Interactive( hoạt động bình thường. Điều thứ hai khiến cho thuật toán chạy rất nhanh: do kích thước mỗi vòng giảm một nửa so với vòng trước, tổng chi phí tính toán là O)N(, thay vì O)N*log(N().

Để đạt được sự giảm dần của miền, một phép ánh xạ hai-trong-một đã được sử dụng, tức là mỗi điểm đều ánh xạ đến một trong hai điểm. Phép ánh xạ này cho phép chúng ta giảm kích thước của tập dữ liệu xuống một nửa. Một lợi ích quan trọng của phép ánh xạ hai-trong-một này là nó có thể lặp lại. Nói cách khác, khi chúng ta áp dụng phép ánh xạ này, tập kết quả thu được vẫn giữ lại các thuộc tính giống nhau. Giả sử chúng ta bắt đầu từ một nhóm con nhân )multiplicative subgroup(. Nhóm con này là một tập hợp S, trong đó mỗi phần tử x đều có bội số 2x cũng nằm trong tập hợp. Nếu thực hiện phép bình phương trên tập hợp S ) tức là ánh xạ mỗi phần tử x trong tập hợp thành x^2(, tập hợp mới S^2 cũng sẽ giữ lại cùng thuộc tính. Phép thao tác này cho phép chúng ta tiếp tục giảm kích thước của tập dữ liệu cho đến khi cuối cùng chỉ còn lại một giá trị. Mặc dù lý thuyết chúng ta có thể thu nhỏ tập dữ liệu chỉ còn một giá trị, nhưng trong thực tế, thường sẽ dừng lại trước khi đạt được một tập hợp nhỏ hơn.

Bạn có thể tưởng tượng thao tác này như một quá trình kéo một đoạn thẳng trên đường tròn, ví dụ như đoạn thẳng hoặc cung ), trải dài quanh đường tròn và làm cho nó quay hai vòng quanh đường tròn. Ví dụ, nếu một điểm nằm ở vị trí x độ trên đường tròn, thì sau khi thực hiện thao tác này, nó sẽ di chuyển đến vị trí 2x độ. Mỗi điểm trên đường tròn từ vị trí 0 đến 179 độ đều có một điểm tương ứng ở vị trí từ 180 đến 359 độ, và hai điểm này sẽ trùng nhau. Điều này có nghĩa là, khi bạn ánh xạ một điểm từ x độ đến 2x độ, nó sẽ trùng với một điểm nằm ở vị trí x+180 độ. Quá trình này có thể được lặp lại. Nói cách khác, bạn có thể áp dụng thao tác ánh xạ này nhiều lần, mỗi lần di chuyển các điểm trên đường tròn đến vị trí mới của chúng.

Để công nghệ ánh xạ có hiệu quả, kích thước của nhóm nhân nguyên thủy cần có một lũy thừa lớn của 2 làm yếu tố. BabyBear là một hệ thống có một mô-đun cụ thể, với mô-đun là một giá trị, khiến cho nhóm nhân lớn nhất chứa tất cả các giá trị khác không, do đó kích thước của nhóm là 2k−1(, trong đó k là số bit của mô-đun ). Kích thước của nhóm như vậy rất phù hợp với công nghệ trên, vì nó cho phép giảm bậc của đa thức một cách hiệu quả bằng cách lặp đi lặp lại thao tác ánh xạ. Trong BabyBear, bạn có thể chọn nhóm có kích thước 2^k ( hoặc sử dụng toàn bộ tập hợp ), sau đó áp dụng phương pháp FRI để giảm bậc của đa thức dần dần xuống 15, và cuối cùng kiểm tra bậc của đa thức. Phương pháp này tận dụng tính chất của mô-đun và kích thước của nhóm nhân, khiến cho quá trình tính toán rất hiệu quả. Mersenne31 là một hệ thống khác, với mô-đun là một giá trị, khiến cho kích thước của nhóm nhân là 2^31 - 1. Trong trường hợp này, kích thước của nhóm nhân chỉ có một lũy thừa của 2 làm yếu tố, điều này khiến cho nó chỉ có thể bị chia cho 2 một lần. Sau đó, việc xử lý sẽ không còn áp dụng công nghệ trên nữa, nghĩa là không thể sử dụng FFT để giảm bậc của đa thức một cách hiệu quả như BabyBear.

Miền Mersenne31 rất phù hợp cho các phép toán số học trong các hoạt động CPU/GPU 32-bit hiện tại. Bởi vì đặc tính của mô đun ( ví dụ 2^31 - 1) khiến cho nhiều phép toán có thể được thực hiện bằng các thao tác bit hiệu quả: nếu kết quả của hai số cộng lại vượt quá mô đun, có thể thực hiện bằng cách lấy kết quả với mô đun.