Mở đầu
Bạn đã sẵn sàng để khám phá một khía cạnh phức tạp hơn của zk-SNARK? Trong phần trước, chúng ta đã tìm hiểu về một số khái niệm nâng cao hơn như Arithmetic Circuit và Quadratic Arithmetic Program. Trong phần này, chúng ta sẽ mở rộng kiến thức của mình bằng cách đào sâu vào một khái niệm mạnh mẽ khác: Elliptic Curve Pairings (Ghép Cặp Đường Cong Elip)
Lưu ý: Việc hiểu sâu về một chủ đề như Elliptic Curve Pairings đôi khi có thể là một thách thức đối với nhiều người. Tuy nhiên, đó là lý do tại sao chúng ta có bài viết này – để giúp bạn có được ít nhất một cái nhìn cơ bản về điều này.
Mục tiêu của tôi không chỉ là giải thích một cách cặn kẽ về Elliptic Curve Pairings mà còn làm cho chủ đề này trở nên thú vị và dễ hiểu hơn. Hy vọng, qua bài viết này, bạn sẽ thấy được sức mạnh của các cặp đường cong elip trong toán học và mật mã nói chung, cũng như trong các ứng dụng cụ thể của chúng trong zk-SNARK nói riêng.
Elliptic curves
Elliptic curves(các đường cong elip) là một phần của lĩnh vực Elliptic Curve Cryptography(mật mã đường cong elip). Đây là một chủ đề phức tạp mà không phải ai cũng dễ dàng hiểu được. Để hiểu rõ hơn về chúng, hãy xem qua bài viết của tôi về ECC ở phần trước.
Elliptic Curve Cryptography liên quan đến các “điểm” trong không gian hai chiều, mỗi “điểm” được đặc trưng bởi một cặp tọa độ (x, y).
Có các quy tắc cụ thể để thực hiện các phép toán như cộng và trừ giữa các điểm, cho phép tính toán tọa độ của một điểm mới khi đã biết các điểm khác.
Ví dụ: Tính tọa độ R = P + Q
Bạn cũng có thể nhân một điểm với một số nguyên bằng cách lặp lại việc cộng điểm đó với chính nó nhiều lần tương ứng với số nguyên đó.
Ví dụ: P * n = P + P + … + P
Điều này cung cấp một cách hiệu quả để thực hiện các phép toán trong Elliptic Curve Cryptography
Trên đường cong elip, có một điểm đặc biệt gọi là “điểm vô cùng”(point at infinity) (O), tương đương với số 0 trong phép tính điểm, luôn đúng rằng P + O = P.
Một đường cong cũng có một “bậc”(order); tồn tại một số n sao cho P * n = O đối với mọi P ( P * (n+1) = P, P * (7*n + 5) = P * 5, và cứ tiếp tục như vậy).
Ngoài ra, cũng có một “điểm sinh” (generator point) (G), được hiểu là đại diện cho số 1 theo một cách nào đó. Theo lí thuyết, bất kỳ điểm nào trên đường cong (ngoại trừ O) cũng có thể là G.
Pairings
Pairings cho phép kiểm tra phương trình phức tạp hơn trên các điểm của đường cong elip.
Ví dụ:
bạn có thể kiểm tra xem p * q có bằng r không chỉ từ P, Q và R.
Mặc dù thông tin về p có thể rò rỉ từ P, nhưng sự rò rỉ này được kiểm soát một cách cẩn thận.
Pairings cho phép kiểm tra các ràng buộc bậc hai(Quadratic constraints).
Ví dụ: Kiểm tra e(P, Q) * e(G, G * 5) = 1 thực sự đang kiểm tra p * q + 5 = 0.
là phép toán được gọi là pairing. Các nhà toán học còn gọi nó là một ánh xạ song tuyến. “Song tuyến”(bilinear) ở đây sẽ tuân thủ các quy tắc sau:
Chú ý rằng bạn có thể sử dụng các toán tử + và * theo bất kỳ cách nào, miễn là chúng tuân thủ các quy tắc như sau:
và
Nếu P, Q, R và S là các số đơn giản, việc tạo ra một phép toán pairing đơn giản là dễ dàng với biểu thức:
Kết quả như sau:
Đó chính là song tuyến !
Tuy nhiên các phép toán pairing đơn giản như vậy không phù hợp cho mật mã vì chúng hoạt động trên các số nguyên đơn giản và quá dễ phân tích.
Khi biết một số và kết quả của nó khi thực hiện phép toán pairing, bạn có thể dễ dàng tính toán và tìm ra số còn lại.
Ta sử dụng các phép toán giống như “hộp đen”(black boxes), nơi chỉ có thể thực hiện các phép toán cơ bản mà không thể phân tích hay tìm hiểu chi tiết hơn. Đây là lý do tại sao đường cong elip và phép toán pairing trên đường cong elip trở nên quan trọng trong mật mã.
Prime Fields and Extension Fields
Có thể tạo ra một ánh xạ song tuyến(Bilinear Maps) trên các điểm đường cong elip — tức là tạo ra một hàm
trong đó P và Q là các điểm đường cong elip, và kết quả là một loại phần tử được gọi là F_p¹²
Đầu tiên, hãy hiểu về các trường số nguyên tố(prime fields) và trường mở rộng(extension fields).
Đường cong Elliptic trong hình ảnh ở phía trên khá đẹp mắt như vậy vì phương trình của đường cong được định nghĩa bằng các số thực thông thường.
Tuy nhiên, trong mật mã học, sử dụng số thực thông thường có thể dẫn đến việc sử dụng logarithms để “đi ngược”, và làm hỏng mọi thứ cũng như lượng không gian cần thiết để lưu trữ và biểu diễn các số có thể tăng một cách tùy ý. Do đó, chúng ta sử dụng các số trong một prime fields.
Một prime field bao gồm tập hợp các số 0, 1, 2… p-1, trong đó p là số nguyên tố và các phép toán khác nhau được định nghĩa như sau:
Tất cả các phép toán đều được thực hiện theo modulo p
Phép chia là trường hợp đặc biệt; thông thường, 3/2 không phải là số nguyên và bây giờ tôi chỉ muốn xử lý các số nguyên, vì vậy thay vào đó tôi cố gắng tìm số x sao cho
x * 2 = 3.
Điều này có thể được thực hiện bằng cách sử dụng Extended Euclidean Algorithm. Ví dụ, nếu p = 7, thì:
Tiếp theo, chúng ta sẽ nói về extension fields.
Một ví dụ phổ biến mà bạn thường gặp trong sách toán học là trường số phức, nơi trường số thực được “extended” với phần tử bổ sung sqrt(-1) = i.
Extension fields hoạt động bằng cách lấy một trường hiện có, sau đó “bổ sung” một phần tử mới và định nghĩa mối quan hệ giữa phần tử mới đó và các phần tử đã có trong trường ban đầu (ví dụ như i² + 1 = 0).
Điều quan trọng là phương trình này không đúng cho bất kỳ số nào trong trường gốc, và sau đó xem xét tất cả các tổ hợp tuyến tính của các phần tử trong trường gốc và phần tử mới vừa tạo ra.
Chúng ta cũng có thể mở rộng prime fields
Ví dụ: mở rộng prime field mod 7 mà ta đã mô tả ở trên với i, ta có thể làm như sau:
Nếu bạn muốn thấy toàn bộ các phép toán được thực hiện dưới dạng mã, prime fields và field extensions được thực hiện ở đây
Elliptic Curve Pairings
Ghép nối đường cong Elliptic(Elliptic Curve pairing) là một cơ chế nhận hai điểm từ hai đường cong Elliptic và ánh xạ những điểm đó thành một số duy nhất.
Bạn có thể nghĩ ánh xạ này tương đương việc nhân điểm trên đường cong Elliptic.
Về mặt toán học, Elliptic Curve pairing được định nghĩa như việc ánh xạ hai điểm trên đường cong Elliptic sang một phần tử trong một nhóm khác như một trường hữu hạn(finite field):
Ở đây e là pairing, E1 và E2 là Elliptic Curves and 𝐹 is a finite field.
Lưu ý rằng Elliptic Curves E1 và E2 không cần phải khác biệt.
Sau khi ghép nối xảy ra, kết quả là một phần tử trong nhóm khác thì không thể sử dụng lại cho lần ghép nối tiếp theo.
Elliptic Curve Pairings có một số thuộc tính nhất định được gọi là bilinear mappings:
Ở đây P, Q and R là các điểm trên Elliptic Curve and 𝑎∈𝑍, 𝑏∈𝑍
Bằng cách sử dụng “bilinear mappings” này, ta có thể “move around” các hệ số 𝑎 và 𝑏 trên 2 đường cong đó trong khi vẫn giữ nguyên ánh xạ:
Nguồn: https://muens.io/elliptic-curve-pairing
Ta có thể hình dung Elliptic curve pairing là một ánh xạ từ G2 x G1 -> Gt, trong đó:
G1 là một đường cong elip, nơi các điểm thoả mãn một phương trình dạng
và cả hai tọa độ đều là các phần tử của F_p (chúng là các số đơn giản, nhưng các phép toán được thực hiện theo modulo của một số nguyên tố cụ thể)
G2 cũng là một đường cong elip, nơi các điểm thoả mãn cùng một phương trình như G1, nhưng các tọa độ của chúng thuộc vào trường F_p¹² ( ta định nghĩa một “magic number” mới w, được định nghĩa bởi một đa thức bậc 12 như:
Gt là loại đối tượng mà kết quả của đường cong elip đi vào. Trong các đường cong mà chúng ta xem xét, Gt là F_p¹² (cùng một số phức mạnh mẽ như được sử dụng trong G2)
Ở đây nó phải thỏa mãn tính song tuyến:
Cùng với hai tiêu chí quan trọng khác:
Efficient computability: Khả năng tính toán hiệu quả có nghĩa là phải có khả năng tính toán phép ghép một cách nhanh chóng và không quá phức tạp.Ví dụ: Nếu ta chỉ cần lấy logarithm rời rạc của các điểm và nhân chúng với nhau để tạo ra một phép ghép, thì điều này sẽ trở nên quá khó khăn tính toán, giống như việc phá vỡ mật mã của đường cong elip ban đầu. Do đó, một phép ghép được coi là hiệu quả tính toán nếu nó có thể được tính toán một cách hiệu quả mà không gây ra quá nhiều gánh nặng tính toán.
Non-degeneracy: Không suy biến đảm bảo rằng phép ghép không phải là một phép ghép không hữu ích, tức là nó không chỉ trả về một giá trị cố định mà không phụ thuộc vào các điểm đầu vào.Ví dụ: Nếu ta định nghĩa phép ghép là e(P, Q) = 1 cho mọi P và Q, điều này không cung cấp bất kỳ thông tin hữu ích nào về mối quan hệ giữa các điểm trên đường cong elip. Do đó, một phép ghép được coi là Non-degeneracy nếu nó cung cấp thông tin hữu ích về mối quan hệ giữa các điểm đầu vào.
Vậy làm thế nào để làm được điều đó?
Đầu tiên, chúng ta cần hiểu khái niệm số chia(divisor),một cách khác để biểu diễn hàm số trên các điểm trên đường cong elip.
A divisor của một hàm về cơ bản là đếm các số 0 và các số vô cực của hàm. Để hiểu điều này có nghĩa là gì, hãy xem qua một số ví dụ. Hãy sửa một số điểm P = (P_x, P_y), và xem xét hàm sau:
The divisor là [P] + [-P] – 2 * [O]
[P] + [Q] không giống như [P + Q]. Lý do như sau:
Hàm số bằng 0 tại P vì khi x là P_x, nên x – P_x = 0.
Hàm số bằng 0 tại -P vì -P và P có cùng tọa độ x.
Hàm số tiến tới vô cùng khi x tiến tới vô cùng, do đó chúng ta nói hàm số này bằng vô cùng tại O.
Lý do là trong phương trình của đường cong Elliptic:
y tăng lên vô cực nhanh hơn khoảng “1,5 lần” so với x để có thể theo kịp x^3 . Do đó, nếu một hàm tuyến tính chỉ có x, thì nó sẽ được biểu diễn dưới dạng vô cực với bội số 2, nhưng nếu hàm đó có y, thì nó sẽ được biểu diễn dưới dạng vô cực với bội số 3.
Bây giờ, xem xét một “line function”:
Trong đó a, b và c được chọn cẩn thận để đường thẳng đi qua các điểm P và Q trên đường cong Elliptic.
Bởi vì cách phép cộng trên đường cong elip hoạt động, điều này cũng có nghĩa là nó đi qua điểm -P-Q. Hàm số này cũng tiến tới vô cùng tùy thuộc vào cả x và y, do đó chia khả năng trở thành
Mỗi “rational function” (một hàm được xác định chỉ sử dụng một số hữu hạn các phép toán +, -, *, / trên các tọa độ của điểm) tương ứng một cách duy nhất với một divsor, với điều kiện nhân với một hằng số (nghĩa là nếu hai hàm F và G có cùng một divisor, thì F = G * k với k là một hằng số).
Chia của tích hai hàm số bằng tổng của chia của từng hàm số, nên
thì
Nguồn bài viết: Team Tech/Research Alphatrue
Nguồn tham khảo:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627