_____ _ ____ _ __ __ | ___ | _ _ | | _____ / ___ | | \ \ / / | | _ / _` | |/ / _ \ | | _| | \ \ / /| _| (_| | < __/ | |_| | |__\ V /|_| \__,_|_|\_\___| \____|_____\_/

Bạn không cần một phép nội cấu hiệu quả để thực hiện phép nhân vô hướng giống GLV trong mạch SNARK

• Giới thiệu
  • Các ứng dụng khác
• Lý lịch
• Thủ thuật GLV giả
  • Thực hiện
    • Điểm chuẩn
    • So sánh

Giới thiệu

P-256, còn được gọi là secp256r1 và prime256v1, là đường cong Weierstrass trường nguyên tố 256 bit được chuẩn hóa bởi NIST. Nó được áp dụng rộng rãi trong các hệ thống internet, điều này giải thích cho vô số trường hợp sử dụng của nó trong các nền tảng như TLS, DNSSEC, Secure Enclave của Apple, Passkeys, Android Keystore và Yubikey. Hoạt động chính trong mật mã dựa trên đường cong elliptic là phép nhân vô hướng. Khi đường cong được trang bị một phép nội hình hiệu quả, có thể tăng tốc hoạt động này thông qua thuật toán GLV nổi tiếng. Thật không may, P-256 không có phép nội hình hiệu quả (xem tham số ) để tận hưởng tốc độ tăng tốc này.

Xác minh chữ ký ECDSA trên Ethereum thông qua các hợp đồng được biên dịch trước, tức là các hợp đồng thông minh được tích hợp vào giao thức Ethereum (chỉ có 9 hợp đồng) chỉ có thể thực hiện được bằng đường cong secp256k1 chứ không phải P-256.
Xác minh chữ ký ECDSA trên P-256 yêu cầu tính toán phép nhân vô hướng trong Solidity và đặc biệt hữu ích cho ví hợp đồng thông minh, cho phép khóa ký dựa trên phần cứng và tự lưu giữ an toàn hơn, dễ dàng hơn. Các giải pháp khác nhau có thể đưa chữ ký P-256 lên chuỗi. Về cơ bản có ba cách tiếp cận thú vị: trình xác minh dựa trên (zk)-SNARK, trình xác minh hợp đồng thông minh (ví dụ: [Dubois23] , Ledger/FCL (đã lỗi thời), smoo.th/SCL và daimo/p256verifier ) và biên dịch trước giao thức gốc ( EIP/RIP 7212 ).

Sử dụng các thuộc tính SNARK (succinctness) cung cấp một cách tuyệt vời để giảm chi phí gas cho việc tính toán trên Ethereum (ví dụ: ~232k gas cho Groth16 , ~285k gas cho PLONK và ~185k gas cho FFLONK ). Điều này rất cạnh tranh với (và đôi khi tốt hơn) trình xác minh hợp đồng thông minh tối ưu về gas hiện tại. Hơn nữa, người ta có thể nhóm nhiều xác minh ECDSA trong một bằng chứng duy nhất, do đó khấu hao chi phí gas. Tuy nhiên, việc xác minh chữ ký P-256 trong mạch SNARK có thể rất tốn kém, tức là thời gian chứng minh dài. Điều này là do trường mà các điểm trên đường cong P-256 nằm khác với trường mà tính toán SNARK thường được thể hiện. Để có thể xác minh bằng chứng trên chuỗi thông qua quá trình biên dịch trước, trường SNARK cần phải là trường vô hướng BN254 . Các nhóm khác nhau đã cố gắng triển khai xác minh ECDSA trên P-256 trong mạch BN254 SNARK một cách hiệu quả. Trong số này: zkwebauthn/webauthn-halo2 , https://github.com/zkwebauthn/webauthn-circom và PSE/circom-ecdsa-p256 .

Nếu P-256 có phép nội cấu hiệu quả, chúng ta có thể tối ưu hóa thời gian chứng minh rất nhiều!

Trong ghi chú này, chúng tôi trình bày một cách để triển khai phép nhân vô hướng giống GLV trong mạch mà không cần phải có phép nội cấu hiệu quả.

Các ứng dụng khác

• Kỹ thuật này có thể được áp dụng cho bất kỳ đường cong elip nào mà không cần phép nội cấu hiệu quả (ví dụ: Curve25519 , P-384 , MNT-753 ( k=4 , k=6 ), đường cong STARK , \mathcal{B} B của “cycle5” , …). Xem cơ sở dữ liệu này để biết các đường cong khác.
• Điều này sẽ đặt câu hỏi về sự lựa chọn Bandersnatch ( một đường cong được nhúng với phép nội suy trên BLS12-381 ) so với Jubjub ( một đường cong được nhúng trên BLS12-381 không có phép nội suy ) cho cây Ethereum Verkle .
• Điều này có thể đẩy nhanh quá trình xác minh ECDSA trong Starknet và Cairo (thông qua đường cong STARK ).
• Điều này có thể tăng tốc bước gấp (à la Nova) của các chữ ký Ed25519 thông qua 2 chu kỳ được Aurore Guillevic đề xuất ở đây .

Lý lịch

Phép nhân vô hướng chuẩn

Cho E E là một đường cong elip được xác định trên trường nguyên tố \mathbb{F}_p F p và cho r r là ước nguyên tố của cấp đường cong \#E(\mathbb{F}_p) # E ( F p ) (tức là số điểm).
Cho s \in \mathbb{F}_r s ∈ F r và P(x,y) \in E(\mathbb{F}_p) P ( x , y ) ∈ E ( F p ) , chúng ta quan tâm đến việc chứng minh phép nhân vô hướng s\cdot P s ⋅ P trên nhóm con r r -xoắn của E E , ký hiệu là E[r] E [ r ] (tức là tập hợp con các điểm có cấp r r ).

Thuật toán đơn giản nhất là thuật toán chuẩn từ trái sang phải và cộng :

 INPUT : s = (s_{t− 1 },..., s_1, s_0), P ∈ E(Fp).OUTPUT: sP. 1 . Q ← ∞. 2 . For i from t− 1 downto 0 do 2.1 Q ← 2 Q. 2.2 If s_i = 1 then Q ← Q + P. 3 . Return (Q).

Không thể phân nhánh If/else trong mạch SNARK nên điều này được thay thế bằng tra cứu bảng cửa sổ hằng số bên trong mạch. Điều này có thể đạt được bằng cách sử dụng các đa thức biến mất tại các hằng số không được chọn, tức là tra cứu bảng 1 bit Q ← s_i * Q + (1 - s_i) * (Q+P) . Do đó, thuật toán nhân đôi và cộng này yêu cầu t t nhân đôi, t t phép cộng và t t tra cứu bảng 1 bit.
Điều này có thể được mở rộng thành phép cộng và nhân đôi có cửa sổ , tức là quét nhiều hơn một bit cho mỗi lần lặp bằng cách sử dụng các bảng cửa sổ lớn hơn, nhưng độ sâu nhân của phép đánh giá tăng theo cấp số nhân. Chúng tôi sử dụng tọa độ affine để nhân đôi/cộng các điểm vì các phép nghịch đảo tốn kém như phép nhân, tức là thay vì kiểm tra xem 1/x 1 / x có phải là y y hay không, chúng tôi cung cấp mạch ra y y và kiểm tra mạch vào rằng x\cdot y = 1 x ⋅ y = 1. Tuy nhiên, vì chúng tôi bắt đầu với Q ← ∞ Q ← ∞ nên không thể tránh được việc phân nhánh có điều kiện vì các công thức affine không đầy đủ. Thay vào đó, chúng tôi quét các bit từ phải sang trái và giả sử rằng bit đầu tiên s_0 là 1 (do đó chúng tôi bắt đầu tại Q ← P ), chúng tôi nhân đôi điểm đầu vào P thay vì bộ tích lũy Q trong thuật toán này và cuối cùng trừ có điều kiện (sử dụng tra cứu 1 bit) P nếu s_0 bằng 0.

 INPUT : s = (s_{t− 1 },..., s_1, s_0), P ∈ E(Fp).OUTPUT: sP. 1 . Q ← P. 2 . For i from 1 to t− 1 do 2.1 If s_i = 1 then Q ← Q + P. 2.2 P ← 2 P. 3 . if s_0 = 0 then Q ← Q - P 4 . Return (Q).

Phép nhân vô hướng GLV

Tuy nhiên, người ta đều biết rằng nếu đường cong được trang bị một phép nội suy hiệu quả thì sẽ tồn tại một thuật toán nhanh hơn được gọi là [GLV] .

Ví dụ 1: giả sử E E có Phép nhân phức (CM) với phân biệt -D=-3 − D = − 3 , tức là E E có dạng y^2=x^3+b y 2 = x 3 + b , với b \in \mathbb{F}_p b ∈ F p . Đây là trường hợp của các đường cong elliptic BN254 , BLS12-381 và secp256k1 được sử dụng trong Ethereum. Có một phép nội đồng cấu hiệu quả \phi: E \rightarrow E ϕ : E → E được định nghĩa bởi (x,y)\mapsto (\omega x,y) ( x , y ) ↦ ( ω x , y ) (và \mathcal{O} \mapsto \mathcal{O} O ↦ O ) tác động lên P \in E[r] P ∈ E [ r ] khi \phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P . Cả \omega ω và \lambda λ đều là căn bậc ba của đơn vị trong \mathbb{F}_p F p và \mathbb{F}_r F r tương ứng, tức là \omega^2+\omega+1 \equiv 0 \pmod p ω 2 + ω + 1 ≡ 0 ( chế độ p ) và \lambda^2+\lambda+1 \equiv 0 \pmod r λ 2 + λ + 1 ≡ 0 ( chế độ (đ ) .

Ví dụ 2: giả sử E E có Phép nhân phức (CM) với phân biệt -D=-8 − D = − 8 , nghĩa là vành nội đồng là \mathbf{Z}[\sqrt{−2}] Z [ √ − 2 ] . Đây là trường hợp của các đường cong elliptic Bandersnatch được chỉ định trong Ethereum Verkle trie. Có một nội đồng hiệu quả \phi: E \rightarrow E ϕ : E → E có hạt nhân được tạo bởi một điểm xoắn 2. Có thể tìm bản đồ bằng cách xem các đường cong 2-đồng dạng và áp dụng các công thức của Vélu. Đối với Bandersnatch, nó được định nghĩa bởi (x,y)\mapsto (u^2\cdot \frac{x^2+wx+t}{x+w},u^3\cdot y\cdot \frac{x^2+2wx+v}{(x+w)^2}) ( x , y ) ↦ ( u 2 ⋅ x 2 + w x + t x + w , u 3 ⋅ y ⋅ x 2 + 2 w x + v ( x + w ) 2 ) đối với một số hằng số u,v,w,t u , v , w , t (và \mathcal{O} \mapsto \mathcal{O} O ↦ O ) tác động lên P \in E[r] P ∈ E [ r ] khi \phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P với \lambda^2+2 \equiv 0 \pmod r λ 2 + 2 ≡ 0 ( chế độ (đ ) .

Thuật toán GLV bắt đầu bằng cách phân tích s s thành s = s_0 + \lambda s_1 s = s 0 + λ s 1 rồi thay thế phép nhân vô hướng s \cdot P s ⋅ P bằng s_0 \cdot P + s_1 \cdot \phi(P) s 0 ⋅ P + s 1 ⋅ ϕ ( P ) . Vì s_0 s 0 và s_1 s 1 được đảm bảo là \leq \sqrt{r} ≤ √ r (xem Mục 4 của [GLV] và Mục 4 của [FourQ] để biết mẹo tối ưu hóa), chúng ta có thể giảm một nửa kích thước của vòng lặp for trong thuật toán nhân đôi và cộng. Sau đó, chúng ta có thể quét đồng thời các bit của s_0 s 0 và s_1 s 1 và áp dụng thủ thuật Strauss-Shamir . Điều này dẫn đến tốc độ tăng đáng kể nhưng chỉ khi có phép nội đồng cấu. Ví dụ, phép nhân đôi và cộng từ trái sang phải sẽ trở thành:

 INPUT: s and P ∈ E(Fp).OUTPUT: sP. 1. Find s1 and s2 st s = s1 + 𝜆 * s2 mod r 1.1 let s1 = (s1_{t− 1 },..., s1_1, s1_0) 1.2 and s2 = = (s2_{t− 1 },..., s2_1, s2_0) 2. P1 ← P, P2 ← 𝜙(P) and Q ← ∞. 3. For i from t− 1 downto 0 do 3.1 Q ← 2Q. 3.2 If s1_i = 0 and s2_i = 0 then Q ← Q. 3.3 If s1_i = 1 and s2_i = 0 then Q ← Q + P1. 3.4 If s1_i = 0 and s2_i = 1 then Q ← Q + P2. 3.5 If s1_i = 1 and s2_i = 1 then Q ← Q + P1 + P2. 4. Return(Q).

Cũng có thể sử dụng phép nội đồng cấu hiệu quả trong mạch (xem [Halo, Phần 6.2 và Phụ lục C] hoặc [thực hiện gnark] để biết các đường cong Weierstrass ngắn và [arkworks] và [gnark] thực hiện cho Edwards xoắn). Nhưng người ta nên cẩn thận về một số kiểm tra bổ sung của phép phân tích s = s_0 + \lambda s_1 \mod r s = s 0 + λ s 1 chế độ r (không phải môđun SNARK). Các số nguyên s_0, s_1 s 0 , s 1 có thể âm, trong trường hợp đó chúng sẽ bị giảm trong mạch theo môđun trường SNARK chứ không phải r r .

Thủ thuật GLV giả

Hãy nhớ rằng chúng ta đang chứng minh rằng s\cdot P = Q s ⋅ P = Q chứ không phải tính toán nó. Chúng ta có thể "gợi ý" kết quả Q Q và kiểm tra trong mạch rằng s\cdot P - Q = \mathcal{O} s ⋅ P − Q = O . Bây giờ, nếu chúng ta có thể tìm thấy u,v \leq \sqrt{r} u , v ≤ √ r sao cho v\cdot s = u \pmod r v ⋅ s = u ( chế độ r ) thì chúng ta có thể kiểm tra thay vào đó

(v\cdot s)\cdot P - v\cdot Q = \mathcal{O} ( v ⋅ s ) ⋅ P − v ⋅ Q = O

tương đương với

u\cdot P - v\cdot Q = \mathcal{O} u ⋅ P − v ⋅ Q = O

Vấn đề bây giờ là u u và v v “nhỏ” và chúng ta có thể, tương tự như thuật toán GLV, giảm một nửa kích thước của vòng lặp nhân đôi và cộng và áp dụng thủ thuật Strauss-Shamir.

Giải pháp : chạy thuật toán nửa GCD (tức là chạy GCD nửa chừng) là đủ để tìm u u và v v . Chúng ta có thể áp dụng chính xác cùng một mẹo để tìm cơ sở mạng như trong bài báo GLV (Phần 4). Để đầy đủ, chúng ta sẽ nhắc lại thuật toán sau đây.
Chúng tôi áp dụng thuật toán Euclid mở rộng để tìm ước chung lớn nhất của r r và s s (ƯCLN này bằng 1 vì r r là số nguyên tố.) Thuật toán tạo ra một chuỗi các phương trình

w_i \cdot r + v_i \cdot s = u_i w i ⋅ r + v i ⋅ s = u i

với i = 0, 1, 2, \dots i = 0 , 1 , 2 , … với w_0 = 1, v_0 = 0, u_0 = r, w_1 = 0, v_1 = 1, u_1 = s w 0 = 1 , v 0 = 0 , u 0 = r , w 1 = 0 , v 1 = 1 , u 1 = s và u_i \geq 0 u i ≥ 0 với mọi i i . Ta dừng tại chỉ số m m mà u_m \geq \sqrt{r} u m ≥ √ r và lấy u = u_{m+1} u = u m + 1 và v = -v_{m+1} v = − v m + 1 .
Lưu ý: Theo cấu trúc u u được đảm bảo là một số nguyên dương nhưng v v có thể âm, trong trường hợp đó nó sẽ được rút gọn trong mạch theo modulo môđun SNARK chứ không phải r r . Để tránh điều này, chúng ta trả về trong gợi ý u u , v v và a \texttt{b}=1 b = 1 nếu v v âm và \texttt{b}=0 b = 0 nếu không. Trong mạch, chúng ta phủ định Q Q thay vào đó khi \texttt{b}=1 b = 1 .

Thực hiện

Một triển khai chung trong thư viện gnark có sẵn tại gnark.io (nhánh feat/fake-GLV) . Đối với Short Weierstrass (ví dụ P256), hãy xem phương thức scalarMulFakeGLV trong gói được mô phỏng và đối với twisted Edwards (ví dụ Bandersnatch/Jubjub), hãy xem phương thức scalarMulFakeGLV trong gói gốc.

Điểm chuẩn

Thuật toán tốt nhất để thực hiện phép nhân vô hướng trong mạch không phải mạch gốc (tức là trường mạch ≠ trường đường cong) khi không có phép nội suy hiệu quả là bản chuyển thể của [Joye07] (được thực hiện trong gnark tại đây ).
Tiếp theo, chúng tôi so sánh phép nhân vô hướng này với GLV giả của chúng tôi trong mạch vanilla PLONKish (tức là không có cổng tùy chỉnh) (scs) trên đường cong BN254 (tương thích với Ethereum). Chúng tôi cũng đưa ra điểm chuẩn trong R1CS.

Lưu ý ở đây rằng xác minh ECDSA cũ sử dụng thủ thuật Strauss-Shamir để tính toán [s]P+[t]Q [ s ] P + [ t ] Q trong khi phiên bản mới chỉ là hai phép nhân GLV giả và một phép cộng.

So sánh

p256wallet.org là ví hợp đồng thông minh ERC-4337 tận dụng zk-SNARK để xác minh chữ ký WebAuthn và P-256. Ví này sử dụng PSE/circom-ecdsa-p256 để tạo bằng chứng webAuthn và bên dưới PSE/circom-ecdsa-p256 để tạo bằng chứng ECDSA trên đường cong P-256. Tệp README của github báo cáo 1,972,905 R1CS . Biên dịch mạch của chúng tôi trong R1CS cho kết quả là 195,266 R1CS . Con số này giảm hơn 10 lần , không chỉ do thuật toán GLV giả mà còn do phép tính số học trường không phải gốc được tối ưu hóa trong gnark.

Các đường cong khác

Kết quả tương tự được ghi nhận đối với các đường cong khác trong Weirstrass ngắn, ví dụ đường cong P-384 và STARK:

và cũng trong Twisted Edwards ví dụ như Jubjub đấu với Bandersnatch: