EIP-2537 BLS12-381 곡선 연산 프리컴파일 (Precompile for BLS12-381 curve operations)

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

BLS12-381 타원곡선 연산 일곱 가지를 프리컴파일(내장 고속 연산 기능)로 추가해 스마트컨트랙트가 BLS 서명 검증과 공개키 집계를 효율적으로 수행할 수 있게 합니다.

왜 필요한가

스마트컨트랙트에서 BLS 서명(여러 서명이나 공개키를 하나로 합쳐 검증할 수 있는 서명 방식)을 검증하려면 페어링이라는 특수한 타원곡선 연산이 필요합니다. 지금 이더리움에는 BN254라는 곡선용 프리컴파일(클라이언트에 미리 내장된 고속 연산 기능)만 있는데, 이 곡선의 보안 강도는 80비트에 그칩니다. 이 EIP는 120비트 이상의 보안 강도를 주는 페어링 친화적 곡선인 BLS12-381의 연산을 프리컴파일로 추가합니다. 점 덧셈과 페어링 검사 외에 다중 스칼라 곱셈(MSM)도 함께 넣어 BLS 서명 검증 과정에서 여러 공개키나 개별 서명자의 서명을 효율적으로 집계할 수 있게 합니다.

무엇이 바뀌나

지금

EIP-2537 이후

누구에게 영향이 있나

심층 설명

일곱 개 프리컴파일의 구성

주소 0x0b부터 0x11까지 일곱 개의 프리컴파일을 추가합니다. BLS12_G1ADD(0x0b)는 기본 소수체 위 곡선 G1의 점 덧셈, BLS12_G1MSM(0x0c)은 G1의 다중 스칼라 곱셈, BLS12_G2ADD(0x0d)는 2차 확장체 위 곡선 G2의 점 덧셈, BLS12_G2MSM(0x0e)은 G2의 다중 스칼라 곱셈, BLS12_PAIRING_CHECK(0x0f)는 (G1, G2) 점 쌍 집합에 대한 페어링 검사, BLS12_MAP_FP_TO_G1(0x10)과 BLS12_MAP_FP2_TO_G2(0x11)는 체 원소를 각각 G1, G2 점으로 매핑합니다. 매핑 프리컴파일은 바이트열을 체 원소로 바꾸는 과정을 포함하지 않습니다. 그 과정은 여러 방식이 가능하고 EVM에서 효율적으로 구현할 수 있어 체 원소를 곡선 점으로 옮기는 산술만 수행합니다. 이런 매핑은 서명 스킴에 필요합니다.

입력 인코딩 규칙

Fp 원소는 부호 없는 정수의 빅엔디언 인코딩 64바이트입니다. 모듈러스 p가 381비트라서 상위 16바이트는 항상 0이어야 하고 값은 반드시 p보다 작아야 합니다. 입력의 일부만 실제 디코딩에 쓰더라도 이 조건을 검사해야 합니다. Fp2 원소는 c0과 c1의 인코딩을 이어 붙인 128바이트, G1 점은 x와 y를 이어 붙인 128바이트, G2 점은 256바이트입니다. 좌표 (0, 0)은 BLS12 곡선 위의 점이 아니므로, 전부 0인 바이트열은 관례상 무한원점(zero point)으로 해석합니다. 스칼라는 32바이트 빅엔디언이고 서브그룹 차수 q보다 작아야 할 필요는 없습니다. 유효하지 않은 인코딩, 잘못된 길이, 그리고 MSM과 페어링의 빈 입력에는 반드시 오류를 반환해야 합니다.

서브그룹 검사의 유무

G1ADD와 G2ADD에는 서브그룹 검사가 없습니다. 입력이 곡선 위의 점이거나 무한원점이기만 하면 받습니다. 반면 G1/G2 MSM과 페어링 검사는 입력 점이 차수 q의 올바른 서브그룹에 속하는지 반드시 검사해야 하고(MUST) 검사에 실패한 입력에는 오류를 반환해야 합니다. 구현은 별도 문서에 정리된 최적화된 서브그룹 검사 방법을 쓰는 것이 권장됩니다(SHOULD). 엔도모피즘 가속은 입력이 올바른 서브그룹에 있어야 하므로, 이 검사를 전제로 구현자가 사용할 수 있습니다(MAY).

가스 비용표

G1 덧셈은 375가스, G2 덧셈은 600가스입니다. 곱셈 기준 비용은 G1이 12000가스, G2가 22500가스입니다. MSM 비용은 (k * multiplication_cost * discount) // multiplier로 계산하며 multiplier는 1000, k는 (점, 스칼라) 쌍의 개수, //는 정수 나눗셈입니다. 할인율 discount는 k가 128 이하일 때 G1과 G2 각각의 할인표를 따르고 k가 128을 넘으면 max_discount(G1은 519, G2는 524)를 적용합니다. 이 할인은 MSM을 Pippenger 알고리즘으로 구현한다는 전제에서 나옵니다. 페어링 검사는 쌍 개수 k에 대해 32600*k + 37700가스입니다. Fp에서 G1으로 매핑하는 비용은 5500가스, Fp2에서 G2로 매핑하는 비용은 23800가스입니다.

가변 길이 입력의 가스 계산과 오류 처리

MSM과 페어링의 가스 계산 함수는 입력 길이를 검증하지 않고 오류도 반환하지 않습니다. 쌍 하나당 길이 LEN_PER_PAIR(G1 MSM은 160, G2 MSM은 288, 페어링은 384)로 입력 길이를 내림 나눗셈해 k를 구합니다. MSM에서 k가 0이면 가스 0을 반환하지만 CALL이나 STATICCALL 자체 비용이 0이 아니고 Blake2f 프리컴파일에 이미 가스 0인 선례가 있어 안전합니다. 입력 길이가 LEN_PER_PAIR로 나누어떨어지지 않으면 가스는 일단 계산되지만 본 처리 단계에서 인코딩 규칙 위반으로 반드시 오류를 내야 합니다. 다른 프리컴파일과 마찬가지로 호출이 오류로 끝나면 CALL이나 STATICCALL에 실어 보낸 가스는 전부 소모됩니다.

MSM을 별도 호출로 두고 전용 MUL을 없앤 이유

단일 점 곱셈 전용 프리컴파일은 두지 않았습니다. k가 1인 MSM의 ABI가 전용 곱셈과 똑같기 때문입니다. 대신 구현은 입력 길이를 검사하는 과정에서 k가 1인 경우를 인식해 복잡한 다중 스칼라 곱셈 알고리즘 대신 단일 점 곱셈 구현을 호출해 오버헤드를 피해야 합니다. MSM을 별도 연산으로 둔 이유는 두 가지입니다. Pippenger 알고리즘으로 실행 시간과 가스를 줄일 수 있고 이더리움의 CALL 연산 자체가 비싸서 점 100개의 MSM을 곱셈 프리컴파일 100번과 덧셈 99번으로 대신하면 대략 138600가스가 더 들기 때문입니다.

보안 고려사항과 현재 상태

원문은 명세를 엄격히 따르면 기존 BN254 프리컴파일과 달리 보안이나 합의 측면의 문제가 생기지 않는다고 밝힙니다. 또 이 프리컴파일의 연산을 상수 시간(constant time) 알고리즘으로 수행할 필요가 없다고(IS NOT REQUIRED) 명시합니다. 구현은 잠재적 무한 루프를 포함하지 않아야 하고 가스 일정은 최악의 경우가 존재하는 연산에서 그 경우의 계산 시간을 반영하도록 책정되었습니다. 이 EIP의 상태는 Final로 명세가 확정되어 있습니다.

EIP 원문 · ← EIPs