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 sản xuất đầ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, điều này làm 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, 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í 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: đầ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, 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 máy tính xách tay 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ì 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 ra sao? Những giao thức này so với các giải pháp như Binius thì 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 một giải pháp có tên là Circle STARKs, giải pháp này có các 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 trường số học nhỏ hơn

Khi tạo ra bằng chứng dựa trên băm, một kỹ thuật rất quan trọng là thông qua việc chứng minh kết quả đánh giá của đa thức tại các điểm ngẫu nhiên, có thể gián tiếp xác minh các thuộc tính của đa thức. Phương pháp này có thể đơn giản hóa đáng kể 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.

Để 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. Fiat-Shamir là một kỹ thuật được sử dụng để tăng cường độ an toàn của các giao thức, bằng cách đặt một số tham số thành một giá trị băm nhất định để tránh các cuộc tấn công. 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 các tham số này, từ đó nâng cao độ an toàn của hệ thống.

Trong các giao thức dựa trên đường cong elip và STARKs thời kỳ 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 một vấn đề: chỉ có khoảng 2 tỷ giá trị r có thể chọn, vì vậy một kẻ tấn công muốn giả mạo chứng cứ 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 đó hoàn toàn có thể thực hiện đượ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

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 ở một tọa độ, hãy kiểm tra lạ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 thực sự có thể xây dựng các đa thức độc hại trông có vẻ bình thường ở những vị trí này. Do đó, việc họ có thể thành công trong việc phá hoại giao thức hay không là một vấn đề xác suất, vì vậy cần tăng số vòng kiểm tra để tăng cường 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: trường mở rộng, trường mở rộ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, được 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 = một giá trị nào đó. 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, phép nhân trở thành phép nhân sử dụng giá trị mới α. Chúng tôi giờ đây có thể thao tác với các cặp giá trị trong trường mở rộng, chứ không chỉ là 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, sự 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ừ đó nâng cao tính bảo mật. Để tăng thêm kích thước của trường, chúng tôi có thể lặp lại việc áp dụng cùng một kỹ thuật. 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 trong Mersenne31 thể hiện là chọn α sao cho α2 = một giá trị nào đó.

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ó đủ đảm bảo 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 bảo mật.

Miền mở rộng chỉ được sử dụng thực tế trong giao thức FRI và các tình huống khác cần 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ở, các trường này thường là trường modulo 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 hiệu quả của các trường nhỏ, trong khi khi cần nâng cao tính bảo mật, có thể sử dụng các trường lớn hơn.

FRI Thường

Khi 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 vấn đề tính toán tùy ý 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 sẽ 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 vấn đề tính toán cơ sở.

Để chứng minh rằng bạn có một nghiệm, bạn cần phải chứng minh rằng giá trị mà 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à những đa thức này có 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 áp dụng từng bước:

• Giả sử bạn có một giá trị đánh giá của đ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à 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 xem 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 biến vấn đề chứng minh bậc đa thức là d thành vấn đề chứng minh bậc đa thức là 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 đề.

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

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ư các 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 một nửa, đồng thời cũng giảm một nửa tập hợp điểm (tập hợp các điểm mà chúng ta quan tâm). Điều đầu tiên là chìa khóa để giao thức FRI hoạt động bình thường. Điều thứ hai giúp thuật toán chạy cực nhanh: vì quy mô của 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)).

Để thực hiện việc giảm dần miền, một ánh xạ hai trên một đã được sử dụng, tức là mỗi điểm sẽ được ánh xạ đến một trong hai điểm. Á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 ưu điểm quan trọng của ánh xạ hai trên 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 ánh xạ này, tập kết quả nhận đượ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. 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 có 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 đến x^2), tập hợp mới S^2 cũng sẽ giữ lại cùng các thuộc tính. Phép toán 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 hẹp tập dữ liệu xuống còn một giá trị duy nhất, nhưng trong thực tế, thường thì chúng ta 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 đường (ví dụ, đoạn thẳng hoặc cung) trên vòng tròn ra xung quanh, khiến nó quay vòng quanh vòng tròn hai lần. Ví dụ, nếu một điểm trên vòng tròn ở vị trí x độ, 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 vòng tròn từ vị trí 0 đến 179 độ đều có một điểm tương ứng ở vị trí 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 độ sang 2x độ, nó sẽ trùng với một điể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 vò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 gốc 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ô-đun cụ thể, với mô-đun là một giá trị nào đó, khiến nhóm nhân lớn nhất của nó 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 này rất phù hợp với công nghệ đã đề cập ở trên, vì nó cho phép giảm hiệu quả bậc của đa thức thông qua việc lặp lại các phép toán ánh xạ. Trong BabyBear, bạn có thể chọn một 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 dần bậc của đa thức xuống còn 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ị nào đó, khiến 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ố, khiến nó chỉ có thể chia cho 2 một lần. Các xử lý sau đó không còn áp dụng công nghệ đã đề cập ở trên, tức là không thể sử dụng FFT để giảm bậc đ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 trên CPU/GPU 32 bit hiện tại. Bởi vì đặc tính của mô số (ví dụ 2^31 - 1) cho phép 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 tổng của hai số vượt quá mô số, có thể giảm xuống phạm vi thích hợp bằng cách thực hiện thao tác dịch bit với mô số. Thao tác dịch bit là một phép toán rất hiệu quả. Trong phép nhân, có thể sử dụng các lệnh CPU cụ thể (thường được gọi là lệnh dịch bit cao) để xử lý kết quả. Những lệnh này có thể tính toán hiệu quả phần cao của phép nhân, từ đó cải thiện hiệu suất tính toán. Trong miền Mersenne31, do các đặc tính trên, phép toán số học nhanh hơn khoảng 1,3 lần so với miền BabyBear. Mersenne31 cung cấp hiệu suất tính toán cao hơn. Nếu có thể triển khai FRI trong miền Mersenne31, điều này sẽ nâng cao đáng kể hiệu suất tính toán, làm cho FRI có thể...