EIP-197 alt_bn128 페어링 검사 프리컴파일 (Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128)

최종 확정 · EVM·실행 · 원문 상태 Final · 2017-02-06 작성

타원곡선 alt_bn128 위의 페어링 검사를 수행하는 프리컴파일 컨트랙트를 주소 0x8에 추가합니다. EIP-196과 결합하면 스마트 컨트랙트 안에서 zkSNARK 증명을 블록 가스 한도 안에서 검증할 수 있습니다.

왜 필요한가

지금 이더리움 스마트 컨트랙트 실행은 모두 공개됩니다. 누가 무엇을 했는지 그대로 드러나기 때문에 위치, 신원, 과거 거래 내역처럼 민감한 정보를 다루는 용도에는 맞지 않습니다. 영지식 증명의 한 종류인 zkSNARK(영지식 간결 비대화형 지식 논증)는 내용을 공개하지 않고도 어떤 사실이 참임을 증명할 수 있어 이 문제의 해법이 될 수 있습니다. 이론상 이더리움 가상머신(EVM)으로도 zkSNARK를 검증할 수 있지만 지금은 비용이 너무 커서 블록 가스 한도 안에 들어가지 않습니다. 그래서 이 제안은 zkSNARK에 필요한 기본 연산의 매개변수를 미리 정해 두고 전용 계약으로 제공해 구현을 효율화하고 가스 비용을 낮춥니다. 원문은 매개변수를 고정해도 zkSNARK의 쓰임새가 제한되지 않으며, 추가 하드포크 없이도 이후 zkSNARK 연구 성과를 일부 받아들일 수 있다고 설명합니다.

무엇이 바뀌나

지금

EIP-197 이후

누구에게 영향이 있나

심층 설명

무엇을 검사하는가: 이산로그 합이 0인지

프리컴파일은 입력 (a1, b1, a2, b2, ..., ak, bk)에 대해 log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0 (F_q에서)이 성립하면 1을, 아니면 0을 반환합니다. 입력 길이가 잘못되었거나 어떤 입력이 해당 그룹의 원소가 아니거나 인코딩이 틀리면 호출이 실패합니다. k는 입력 길이를 192로 나눈 값으로 입력에서 유도되고 빈 입력은 유효하며 1을 반환합니다. 명세가 페어링 함수의 평가가 아니라 이 검사만 정의한 이유도 원문에 있습니다. 페어링 함수의 공역은 복잡한 체여서 인코딩 문제가 생길 수 있고 zkSNARK에서 알려진 모든 쓰임은 이 검사만 필요하기 때문입니다.

두 그룹 G_1과 G_2의 정의

G_1과 G_2는 모두 소수 위수 q = 21888242871839275222246405745257275088548364400416034343698204186575808495617의 순환군입니다. G_1은 체 F_p (p = 21888242871839275222246405745257275088696311157297823662689037894645226208583) 위의 곡선 Y^2 = X^3 + 3에 정의되고 생성원은 P1 = (1, 2)입니다. G_2는 확대체 F_p^2 = F_p[i] / (i^2 + 1) 위의 곡선 Y^2 = X^3 + 3/(i+9)에 정의되며 원문에 생성원 P2의 구체적 좌표가 명시되어 있습니다. G_1 소속 검사는 좌표 인코딩 확인과 곡선 방정식 검사(또는 무한원점 인코딩 확인)로 충분하지만 G_2는 추가로 원소의 위수가 q인지 검사해야 합니다. 원문은 G_2가 해당 곡선에서 위수 q인 유일한 그룹이므로 다른 생성원을 택해도 같은 그룹이 된다고 덧붙입니다.

인코딩 규칙

F_p의 원소는 32바이트 빅엔디언 숫자로 인코딩하며 p 이상의 값은 무효입니다. F_p^2의 원소 a * i + b는 F_p 원소 두 개 (a, b)로 인코딩합니다. 이 순서는 원소 자체의 빅엔디언 인코딩과 맞추기 위해 선택되었습니다. 타원곡선 점은 (X, Y) 쌍으로 인코딩하고 무한원점은 (0, 0)으로 나타냅니다. 따라서 G_1 점은 64바이트, G_2 점은 128바이트가 되어 점 쌍 하나가 192바이트입니다. 반환 데이터 길이는 항상 정확히 32바이트이며 32바이트 빅엔디언 숫자로 인코딩됩니다. 압축하지 않은 점 인코딩을 쓴 이유는 전체 y 좌표가 포함되어 컨트랙트 안에서 일부 연산을 직접 할 수 있고 세 번째 사영 좌표가 없어 인코딩된 두 점을 그대로 비교할 수 있기 때문입니다.

가스 비용

프리컴파일의 가스 비용은 80 000 * k + 100 000입니다. 여기서 k는 점 쌍의 개수, 즉 입력 길이를 192로 나눈 값입니다. 입력 크기에 비례하는 부분과 고정 비용으로 나뉜 구조여서 검사할 페어링 항이 늘어날수록 비용이 선형으로 증가합니다. 곡선과 체의 매개변수를 입력으로 받는 일반화 방안도 검토되었지만 기각되었습니다. 명세가 복잡해지고 가스 비용을 정하기 훨씬 어려워지며 실제 타원곡선이 아니거나 효율적인 페어링 구현이 없는 대상으로 계약을 호출할 수 있게 되기 때문입니다.

구현: 최적 아테 페어링과의 동치

명세는 이산로그로 정의되어 있지만 실제 구현은 효율적으로 계산할 수 있는 alt_bn128 곡선 위의 최적 아테 페어링(optimal ate pairing)으로 합니다. 페어링 함수 e: G_1 x G_2 -> G_T는 e(m * P1, n * P2) = e(P1, P2)^(m * n)이라는 쌍선형성과 비퇴화성을 만족하므로, 이산로그 합이 0이라는 조건은 e(a1, b1) * ... * e(ak, bk) = 1을 확인하는 것과 동치입니다. 원문은 참고 구현으로 libff(C++), bn(Rust), py_ecc의 bn128_pairing(Python)을 제시합니다.

왜 alt_bn128 곡선인가

alt_bn128은 zkSNARK, 더 구체적으로는 그 검증의 핵심 구성 요소인 페어링 함수에 특히 잘 맞아서 선택되었습니다. 또 이 곡선을 택하면 지캐시(ZCash)와의 시너지를 활용해 그쪽의 구성 요소와 산출물 일부를 재사용할 수 있습니다. 원문 Motivation은 페어링 함수가 현재 zkSNARK에 필요한 제한된 형태의 곱셈 준동형 연산을 수행하는 데 쓰인다고 설명합니다.

적용 시점과 하위 호환성

이 프리컴파일은 block.number >= BYZANTIUM_FORK_BLKNUM인 블록부터 적용됩니다. 프리컴파일 도입이 늘 그렇듯 해당 주소를 이미 쓰고 있던 컨트랙트는 동작 의미가 바뀌는데, 이 때문에 주소를 256 미만의 예약 범위에서 가져왔습니다. 이 EIP의 상태는 Final로 확정된 명세이며 원문의 Test Cases 절은 작성 예정(To be written)으로 남아 있습니다.

EIP 원문 · ← EIPs