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

SNARK 회로에서 GLV와 유사한 스칼라 곱셈을 구현하려면 효율적인 엔도모피즘이 필요하지 않습니다.

• 소개
  • 다른 응용 프로그램
• 배경
• 가짜 GLV 트릭
  • 구현
    • 기준
    • 비교

소개

P-256은 secp256r1 및 prime256v1로도 알려져 있으며, NIST에서 표준화한 256비트 소수 필드 바이어슈트라스 곡선입니다. 인터넷 시스템에서 널리 채택되어 TLS, DNSSEC, Apple의 Secure Enclave, Passkeys, Android Keystore, Yubikey와 같은 플랫폼에서 수많은 사용 사례를 설명합니다. 타원 곡선 기반 암호화의 핵심 연산은 스칼라 곱셈입니다. 곡선에 효율적인 엔도모피즘이 장착되어 있으면 잘 알려진 GLV 알고리즘을 통해 이 연산을 가속화할 수 있습니다. P-256은 불행히도 이러한 속도 향상을 즐길 수 있는 효율적인 엔도모피즘( 매개변수 참조)이 없습니다.

사전 컴파일된 계약, 즉 이더리움 프로토콜에 내장된 스마트 계약(총 9개)을 통해 이더리움에서 ECDSA 서명을 확인하는 것은 secp256k1 곡선을 사용해서만 가능하며 P-256을 사용해서는 불가능합니다.
P-256에서 ECDSA 서명을 검증하려면 Solidity에서 스칼라 곱셈을 계산해야 하며, 특히 스마트 계약 지갑에 유용하여 하드웨어 기반 서명 키와 더 안전하고 쉬운 자체 보관을 가능하게 합니다. 다양한 솔루션을 통해 P-256 서명을 온체인으로 가져올 수 있습니다. 주로 세 가지 흥미로운 접근 방식이 있습니다. (zk)-SNARK 기반 검증기, 스마트 계약 검증기(예: [Dubois23] , Ledger/FCL (더 이상 사용되지 않음), smoo.th/SCL 및 daimo/p256verifier ), 네이티브 프로토콜 사전 컴파일( EIP/RIP 7212 ).

SNARK(간결함) 속성을 사용하면 Ethereum에서 계산에 드는 가스 비용을 크게 줄일 수 있습니다(예: Groth16 의 경우 ~232k 가스, PLONK 의 경우 ~285k 가스, FFLONK 의 경우 ~185k 가스). 이는 현재 가스 최적화 스마트 계약 검증기와 매우 경쟁력이 있으며(때로는 그보다 더 좋음) 가스 비용을 상각합니다. 게다가 여러 ECDSA 검증을 단일 증명으로 일괄 처리하여 가스 비용을 상각할 수 있습니다. 그러나 SNARK 회로에서 P-256 서명을 검증하는 것은 매우 비쌀 수 있습니다. 즉, 검증 시간이 길어질 수 있습니다. 이는 P-256 곡선의 점이 있는 필드가 일반적으로 SNARK 계산이 표현되는 필드와 다르기 때문입니다. procompile을 통해 체인에서 증명을 검증하려면 SNARK 필드가 BN254 스칼라 필드여야 합니다. 여러 팀이 BN254 SNARK 회로에서 P-256에 대한 ECDSA 검증을 효율적으로 구현하려고 시도했습니다. 여기에는 zkwebauthn/webauthn-halo2 , https://github.com/zkwebauthn/webauthn-circom 및 PSE/circom-ecdsa-p256이 있습니다.

만약 P-256에 효율적인 엔도모피즘이 있었다면 우리는 증명 시간을 크게 최적화할 수 있었을 겁니다!

이 노트에서는 효율적인 엔도모피즘 없이 GLV와 유사한 스칼라 곱셈을 회로 내에서 구현하는 방법을 보여줍니다.

다른 응용 프로그램

• 이 기술은 효율적인 엔도모피즘이 없는 모든 타원 곡선에 적용될 수 있습니다(예: Curve25519 , P-384 , MNT-753( k=4 , k=6 ), STARK 곡선 , "cycle5"의 \mathcal{B} B , ...). 다른 곡선은 이 데이터베이스를 참조하세요.
• 이는 Ethereum Verkle 트리 의 경우 BLS12-381 위에 있는 엔도모피즘이 장착된 곡선 인 Bandersnatch 를 선택하는 것과 엔도모피즘이 없는 BLS12-381 위에 있는 임베디드 곡선 인 Jubjub를 선택하는 것에 대한 의문을 제기합니다.
• 이를 통해 Starknet 및 Cairo 에서 ECDSA 검증 속도를 높일 수 있습니다( STARK 곡선을 통해).
• 이를 통해 Aurore Guillevic 이 제안한 2주기를 통해 Ed25519 시그니처의 폴딩 단계(Nova 방식)를 기본적으로 가속화할 수 있습니다.

배경

표준 스칼라 곱셈

E E 가 소수체 \mathbb{F}_p F p 위에 정의된 타원 곡선이고, r r 이 곡선 순서 \#E(\mathbb{F}_p) # E ( F p ) (즉, 점의 개수)의 소수 약수라고 하자.
s \in \mathbb{F}_r s ∈ F r 이고 P(x,y) \in E(\mathbb{F}_p) P ( x , y ) ∈ E ( F p ) 라고 하면, E E 의 r r - 비틀림 부분군(즉, r r 차수 점의 부분 집합)인 E[r] E [ r ] 에 대한 스칼라 곱 s\cdot P s ⋅ P 를 증명하는 데 관심이 있습니다.

가장 간단한 알고리즘은 표준적인 왼쪽에서 오른쪽으로 두 배로 더하는 것 입니다.

 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).

SNARK 회로에서는 if/else 분기가 불가능하므로 이는 회로 내부의 상수 윈도우 테이블 조회로 대체됩니다. 이는 선택되지 않는 상수에서 사라지는 다항식을 사용하여 달성할 수 있습니다. 즉, 1비트 테이블 조회 Q ← s_i * Q + (1 - s_i) * (Q+P) . 따라서 이 더블 앤 덧셈 알고리즘에는 t t 더블링, t t 덧셈 및 t t 1비트 테이블 조회가 필요합니다.
이것은 윈도우 더블 앤 덧셈으로 확장될 수 있는데, 즉 더 큰 윈도우 테이블을 사용하여 반복당 1비트 이상을 스캔하지만 평가의 곱셈 깊이는 기하급수적으로 증가합니다. 역수는 곱셈만큼 비용이 들기 때문에 점을 두 배/덧셈할 때 아핀 좌표를 사용합니다. 즉, 1/x 1 / x 가 y y 인지 확인하는 대신 y y 아웃회로를 제공하고 인회로에서 x\cdot y = 1 x ⋅ y = 1 인지 확인합니다. 그러나 Q ← ∞ Q ← ∞ 로 시작하기 때문에 아핀 공식이 불완전하기 때문에 조건 분기를 피하는 것은 불가능합니다. 대신, 우리는 비트를 오른쪽에서 왼쪽으로 스캔하고 첫 번째 비트 s_0 가 1이라고 가정합니다(따라서 Q ← P 에서 시작합니다). 이 알고리즘에서 어큐뮬레이터 Q 대신 입력 지점 P 두 배로 늘리고 마지막으로 s_0 0이면 (1비트 조회를 사용하여) P 조건부로 뺍니다.

 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).

GLV 스칼라 곱셈

그러나 곡선에 효율적인 엔도모피즘이 장착되어 있다면 [GLV] 라고 알려진 더 빠른 알고리즘이 존재한다는 것이 잘 알려져 있습니다.

예 1: E E 가 판별식 -D=-3 − D = − 3 을 갖는 복소수 곱셈(CM)을 갖는다고 가정하자. 즉, E E 는 y^2=x^3+b y 2 = x 3 + b 형태이고, b \in \mathbb{F}_p b ∈ F p 이다 . 이는 이더리움에서 사용되는 BN254 , BLS12-381 및 secp256k1 타원 곡선의 경우이다. 효율적인 엔도모사상 \phi: E \rightarrow E ϕ : E → E 가 있는데, 이는 (x,y)\mapsto (\omega x,y) ( x , y ) ↦ ( ω x , y ) (및 \mathcal{O} \mapsto \mathcal{O} O ↦ O )로 정의되며, 이는 P \in E[r] P ∈ E [ r ] 에 작용합니다 . \phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P . \omega ω 와 \lambda λ는 각각 \mathbb{F}_p F p 와 \mathbb{F}_r F r 에서 단위의 세제곱근입니다. 즉, \omega^2+\omega+1 \equiv 0 \pmod p ω 2 + ω + 1 ≡ 0 ( 모드 p ) 와 \lambda^2+\lambda+1 \equiv 0 \pmod r λ 2 + λ + 1 ≡ 0 ( 모드 라 ) .

예제 2: E E 에 판별식 -D=-8 − D = − 8을 갖는 복소수 곱셈(CM)이 있고, 이는 엔도모사즘 링이 \mathbf{Z}[\sqrt{−2}] Z [ √ − 2 ] 임을 의미합니다. 이는 Ethereum Verkle trie에 지정된 Bandersnatch 타원 곡선의 경우입니다. 2-비틀림 점에 의해 생성된 커널을 갖는 효율적인 엔도모사즘 \phi: E \rightarrow E ϕ : E → E 가 있습니다. 이 맵은 2-등차 곡선을 살펴보고 Vélu의 공식을 적용하여 찾을 수 있습니다. Bandersnatch의 경우 (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 ) 일부 상수 u,v,w,t u , v , w , t (및 \mathcal{O} \mapsto \mathcal{O} O ↦ O )에 대해 이는 P \in E[r] P ∈ E [ r ] 에 작용하며 , \phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P 여기서 \lambda^2+2 \equiv 0 \pmod r λ 2 + 2 ≡ 0 ( 모드 라 ) .

GLV 알고리즘은 s s를 s = s_0 + \lambda s_1 s = s 0 + λ s 1 로 분해한 다음 스칼라 곱 s \cdot P s ⋅ P를 s_0 \cdot P + s_1 \cdot \phi(P) s 0 ⋅ P + s 1 ⋅ ϕ ( P ) 로 대체하는 것으로 시작합니다. s_0 s 0 및 s_1 s 1 은 \leq \sqrt{r} ≤ √ r 임이 보장되므로(최적화 트릭에 대해서는 [GLV] 의 섹션 4 및 [FourQ] 의 섹션 4 참조), double-and-add 알고리즘에서 for 루프의 크기를 절반으로 줄일 수 있습니다. 그런 다음 s_0 s 0 및 s_1 s 1 의 비트를 동시에 스캔하고 Strauss-Shamir 트릭을 적용할 수 있습니다. 이는 상당한 속도 향상을 가져오지만 엔도모피즘이 사용 가능할 때만 가능합니다. 예를 들어, 왼쪽에서 오른쪽으로 두 배로 더하는 것은 다음과 같습니다.

 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).

효율적인 엔도모피즘 인서킷을 사용하는 것도 가능합니다(짧은 Weierstrass 곡선의 경우 [Halo, Sec. 6.2 및 부록 C] 또는 [gnark 구현], 꼬인 Edwards의 경우 [arkworks] 및 [gnark] 구현 참조). 그러나 s = s_0 + \lambda s_1 \mod r s = s 0 + λ s 1 분해에 대한 몇 가지 추가 검사에 주의해야 합니다. 모드 r (SNARK 모듈러스가 아님). 정수 s_0, s_1 s 0 , s 1 은 음수가 될 수 있으며 이 경우 SNARK 필드에 대한 모듈러스로 회로 내에서 축소되고 r r 이 아닙니다.

가짜 GLV 트릭

s\cdot P = Q s ⋅ P = Q 임을 증명하고 있는 것이지 계산하고 있는 것이 아니라는 점을 기억하세요. 결과 Q Q 에 "힌트"를 주고 회로 내에서 s\cdot P - Q = \mathcal{O} s ⋅ P − Q = O 임을 확인할 수 있습니다. 이제 u,v \leq \sqrt{r} u , v ≤ √ r 을 찾을 수 있고, 여기서 v\cdot s = u \pmod r v ⋅ s = u ( 모드 r ) 그런 다음 대신 확인할 수 있습니다.

(v∈ s)∈ P - v∈ Q = O ( v ⋅ s ) ⋅ P − v ⋅ Q = O

이는 다음과 같습니다

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

이제 문제는 u u 와 v v가 "작다"는 것이고, GLV 알고리즘과 유사하게 더블 앤 덧셈 루프의 크기를 절반으로 줄이고 Strauss-Shamir 트릭을 적용할 수 있다는 것입니다.

해결책 : 반 GCD 알고리즘을 실행하면(즉, GCD를 반쯤 실행하면) u u 와 v v 를 찾는 데 충분합니다. GLV 논문(4절)에서와 같이 격자 기반을 찾는 데 정확히 동일한 트릭을 적용할 수 있습니다. 완전성을 위해 이하에서 알고리즘을 상기합니다.
우리는 r r 과 s s 의 최대공약수를 찾기 위해 확장된 유클리드 알고리즘을 적용합니다. (이 최대공약수는 r r이 소수이기 때문에 1입니다.) 알고리즘은 일련의 방정식을 생성합니다.

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

i = 0, 1, 2, \dots i = 0 , 1 , 2 , … 에 대해 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 이고 모든 i i 에 대해 u_i \geq 0 u i ≥ 0 입니다 . u_m \geq \sqrt{r} u m ≥ √ r 인 인덱스 m m 에서 멈추고 u = u_{m+1} u = u m + 1 및 v = -v_{m+1} v = − v m + 1을 취합니다.
참고: 구성상 u u 는 양의 정수임이 보장되지만 v v 는 음수가 될 수 있으며, 이 경우 SNARK 모듈러스로 회로 내에서 모듈로 축소되고 r r 로 축소되지 않습니다. 이를 피하기 위해 힌트에서 u u , v v , a \texttt{b}=1 b = 1 ( v v 가 음수이면)을 반환하고 \texttt{b}=0 b = 0 (그렇지 않으면)을 반환합니다. 회로 내에서 \texttt{b}=1 b = 1 일 때 Q Q 를 부정합니다.

구현

gnark 라이브러리의 일반 구현은 gnark.io(feat/fake-GLV branch) 에서 제공됩니다. Short Weierstrass(예: P256)의 경우 에뮬레이트된 패키지의 scalarMulFakeGLV 메서드를 살펴보고 twisted Edwards(예: Bandersnatch/Jubjub)의 경우 네이티브 패키지의 scalarMulFakeGLV 메서드를 살펴보세요.

기준

효율적인 엔도모피즘을 사용할 수 없을 때 비네이티브 회로(즉, 회로 필드 ≠ 곡선 필드)에서 스칼라 곱셈을 구현하는 최상의 알고리즘은 [Joye07] 의 변형입니다( 여기 gnark 에 구현됨).
다음으로 우리는 이 스칼라 곱셈을 BN254 곡선(Ethereum 호환)을 통한 PLONKish vanilla(즉, 사용자 정의 게이트 없음) 회로(scs)의 가짜 GLV와 비교합니다. 또한 R1CS에서 벤치마크를 제공합니다.

여기서 이전 ECDSA 검증은 [s]P+[t]Q [ s ] P + [ t ] Q 를 계산하기 위해 Strauss-Shamir 트릭을 사용했지만 새로운 버전은 단순히 두 개의 가짜 GLV 곱셈과 덧셈입니다.

비교

p256wallet.org 는 WebAuthn 및 P-256 서명 검증을 위해 zk-SNARK를 활용하는 ERC-4337 스마트 계약 지갑입니다. PSE/circom-ecdsa-p256을 사용하여 webAuthn 증명을 생성하고, PSE/circom-ecdsa-p256 아래에서 P-256 곡선에 대한 ECDSA 증명을 생성합니다. github README는 1,972,905 R1CS 보고합니다. R1CS에서 회로를 컴파일하면 195,266 R1CS 생성됩니다. 이는 10배 이상 감소한 것으로, 가짜 GLV 알고리즘 때문일 뿐만 아니라 gnark에서 최적화된 비네이티브 필드 산술 때문이기도 합니다.

기타 곡선

짧은 Weirstrass의 다른 곡선, 예를 들어 P-384 및 STARK 곡선에서도 유사한 결과가 나타났습니다.

그리고 뒤틀린 에드워즈에서도 예를 들어 Jubjub 대 Bandersnatch: