EIP-7885 NTT 연산 프리컴파일 (Precompile for NTT operations)
콜 결정 없음 · EVM·실행 · 원문 상태 Draft · 2025-02-12 작성
다항식 곱셈을 빠르게 하는 NTT(수론 변환)와 역변환, 벡터 모듈러 곱셈·덧셈 등 4개 연산을 프리컴파일로 추가합니다. 양자내성 서명 검증과 STARK 검증 비용을 크게 낮추는 것이 목적입니다.
왜 필요한가
지금 이더리움의 일반 계정은 ECDSA라는 서명 방식을 씁니다. 이 방식은 충분히 강력한 양자컴퓨터가 등장하면 깨질 수 있습니다. 이를 대체할 양자내성 서명 알고리즘(FALCON, DILITHIUM 등)은 다항식 곱셈이 핵심 연산인데, 지금 EVM에서 직접 구현하면 가스가 너무 비쌉니다. 원문 측정으로 FALCON 서명 검증 한 번에 약 180만 가스가 들어, 수수료가 싼 L2에서나 실험할 수 있고 L1에서는 쓰기 어렵습니다. 이 EIP는 다항식 곱셈의 공통 부품인 NTT 변환을 프리컴파일(클라이언트에 미리 내장된 고속 연산)로 제공해 이 비용을 크게 낮춥니다. 특정 알고리즘 하나를 내장하는 대신 범용 연산을 내장하므로 DILITHIUM이든 FALCON이든 적은 비용으로 구현할 수 있고 같은 연산이 STARK 검증기 가속에도 쓰여 확장성과 양자 위협 대비에 함께 도움이 됩니다.
무엇이 바뀌나
지금
- FALCON 서명 검증을 순수 솔리디티로 구현하면 약 180만 가스가 듭니다
- 양자내성 서명은 수수료가 싼 L2에서나 실험할 수 있습니다
- STARK 검증기의 다항식 연산도 EVM에서 비싸게 수행해야 합니다
EIP-7885 이후
- 통합 테스트 기준 FALCON 검증이 약 479,341가스로 줄어듭니다(73.4% 절감)
- 격자 기반 암호를 이더리움 애플리케이션에서 실용적으로 쓸 수 있게 됩니다
- 같은 NTT 프리컴파일로 STARK 검증도 가속할 수 있습니다
누구에게 영향이 있나
- 사용자: 양자컴퓨터 위협에 대비한 서명 방식으로 옮겨 갈 수 있는 기반이 마련됩니다.
- 지갑·앱 개발자: FALCON, DILITHIUM(ML-DSA) 같은 양자내성 서명 검증을 온체인에서 훨씬 싼 가스로 구현할 수 있습니다.
- 클라이언트 팀: 네 개의 프리컴파일을 새로 구현해야 합니다. op-geth용 참조 구현이 순수 Go 버전과 liboqs 버전으로 제공됩니다.
- L2: 원문은 순수 솔리디티만으로도 가스가 싼 L2에서 FALCON 실험이 가능하다고 보며 실제 통합 테스트도 OP-Stack 테스트넷에서 수행됐습니다.
심층 설명
네 개의 프리컴파일 구성
NTT_FW(순방향 NTT, negative wrap convolution), NTT_INV(역 NTT), NTT_VECMULMOD(벡터 모듈러 곱셈), NTT_VECADDMOD(벡터 모듈러 덧셈)의 네 개 프리컴파일을 추가합니다. Specification의 상수 표에서 주소는 아직 TBD이며 참조 구현(op-geth)에서는 0x12, 0x13, 0x14, 0x15를 사용합니다. Specification 본문은 NTT_FW와 NTT_INV의 가스 비용을 각각 600으로 제시하고 벡터 연산 두 개는 별도 공식으로 정의합니다.
수학적 바탕: 원분환과 필드 파라미터
연산은 원분환 R = F_q[X]/(Xⁿ+1) 위에서 정의됩니다. n은 2의 거듭제곱인 차수, q는 q ≡ 1 mod 2n을 만족하는 소수입니다. ω는 F_q의 n차 단위근, ψ는 2n차 단위근입니다. R의 원소는 차수 n-1 이하의 다항식이고 길이 n의 계수 벡터로 표현됩니다. 이 조건(q ≡ 1 mod 2n)을 만족하는 소수에서만 NTT가 동작하므로, 테스트 케이스에도 이 조건을 어긴 모듈러스를 거부하는 검사가 포함됩니다.
NTT_FW와 NTT_INV 알고리즘
NTT_FW는 표준 순서의 벡터 a를 입력받고 ψ의 거듭제곱을 비트 역순(bit-reversed)으로 저장한 사전 계산 테이블 Ψrev를 사용해 비트 역순 출력으로 변환합니다. NTT_INV는 반대로 비트 역순 입력을 Ψ⁻¹rev 테이블로 표준 순서로 되돌리고 마지막에 모든 계수에 n⁻¹을 곱합니다. 두 알고리즘 모두 버터플라이 구조의 삼중 루프로 기술되어 있으며 기능 테스트는 INTT(NTT(x)) = x의 왕복 복원을 검증합니다. Rationale은 f×g = NTT_INV(NTT_VECMULMOD(NTT_FW(a), NTT_FW(b)))로 곱셈이 완성되고 복잡도가 n² 대신 n·log₂n임을 명시합니다.
벡터 연산과 두 가지 가스 모델
NTT_VECMULMOD는 두 벡터의 성분별 곱셈, NTT_VECADDMOD는 성분별 덧셈을 mod q로 수행합니다. Specification은 k를 log₂(q)보다 큰 가장 작은 2의 거듭제곱이라 할 때 곱셈 가스를 k·log₂(n)/8, 덧셈 가스를 k·log₂(n)/32로 정의합니다. 한편 Rationale의 가스 분석은 다른 모델을 제시합니다. NTT는 스킴별 고정 비용(nocgo 기준 Falcon-512 790, Falcon-1024 1,750, ML-DSA NTT_FW 220·NTT_INV 270 / cgo 기준 각각 500, 1,080, 256, 340), 벡터 연산은 길이 N에 선형인 VECMULMOD ceil(0.32×N), VECADDMOD ceil(0.3×N)입니다. 목표 처리량은 ECRECOVER와 같은 수준인 약 50~55 mgas/s입니다. 두 모델이 문서 안에 함께 있어 확정 수치는 아직 아닙니다.
지원 필드: 양자내성 암호와 STARK를 모두 포괄
설계가 적용되는 필드로 FALCON(q=3·2¹²+1), DILITHIUM(q=2²³-2¹³+1), KYBER(q=13·2⁸+1) 같은 NIST 선정 양자내성 스킴과 Babybear(q=15·2²⁷+1, Risc0), Goldilocks(q=2⁶⁴-2³²+1, Polygon Plonky2), M31(q=2³¹-1, Circle STARKs·STwo·Plonky3), StarkCurve(q=2²⁵¹+17·2¹⁹²+1)가 나열됩니다. 특정 알고리즘 전용이 아니라 범용 NTT를 내장하는 선택이 서명 스킴과 STARK 증명 시스템 양쪽에 걸친 유연성을 주는 근거입니다.
벤치마크: 솔리디티 대비 절감 효과
순수 Yul 최적화 솔리디티 구현에서 Falcon(q=12289, n=512)은 NTT 1회에 1.8M 가스, 전체 추정 3.6M 가스가 들고 Dilithium은 전체 약 2.3M 가스로 추정됩니다. 원문은 이 EIP를 채택하면 Falcon 서명 검증을 1,500가스로 줄일 수 있고 해시 함수를 별도 EIP로 채택하면 2,000가스 검증이 가능하다고 적습니다. op-geth 통합 테스트(OP-Stack 테스트넷)에서는 ETHFALCON 검증이 1,800,000가스에서 479,341가스로 73.4% 줄었고 ETHDILITHIUM은 검증당 2.1M 가스 이상이 절감됐습니다. liboqs(cgo) 구현은 순수 Go 대비 NTT 가스가 36~38% 낮습니다.
입력 형식과 테스트
참조 구현의 입력 형식은 ring_degree 4바이트 + modulus 8바이트 + 계수(FALCON은 uint16×N, ML-DSA는 int32×N)입니다. 테스트는 잘못된 연산 코드, 2의 거듭제곱이 아니거나 16 미만인 링 차수, q ≡ 1 mod 2N을 만족하지 않는 모듈러스, 모듈러스를 넘는 계수, 입력 길이 불일치 같은 비정상 입력 거부와 링 차수 16·모듈러스 97을 쓴 기능 검증, Falcon-512(n=512, q=12289)·Kyber-128(n=256, q=3329)·Dilithium-256(n=256, q=8380417) 벤치마크를 포함합니다. Python, Solidity, op-geth(nocgo·cgo) 참조 구현이 제공됩니다.
아직 Draft 단계입니다
이 EIP의 상태는 Draft로, 내용이 바뀔 수 있습니다. 프리컴파일 주소는 상수 표에서 TBD이고 Specification과 Rationale의 가스 모델이 서로 다르게 적혀 있으며 Security Considerations 절은 '논의 필요'로 비어 있습니다. 코어 개발자 콜에서 포크 포함이 결정된 기록은 없습니다.