EIP-198 큰 정수 모듈러 거듭제곱 프리컴파일 (Big integer modular exponentiation)
최종 확정 · EVM·실행 · 원문 상태 Final · 2017-01-30 작성
0x05 주소에 큰 정수의 거듭제곱 나머지 연산(BASE**EXPONENT % MODULUS)을 계산하는 프리컴파일을 추가합니다. EVM 안에서 RSA 검증 같은 정수론 기반 암호를 효율적으로 쓸 수 있게 됩니다.
왜 필요한가
이더리움 스마트 컨트랙트가 RSA 서명을 검증하려면 아주 큰 수를 거듭제곱한 뒤 나머지를 구하는 계산, 즉 모듈러 거듭제곱(modular exponentiation)이 필요합니다. 그런데 EVM(이더리움 가상 머신)의 기본 명령어만으로 이런 큰 수 연산을 하기는 어렵습니다. 원문도 덧셈과 뺄셈은 EVM 안의 알고리즘으로 충분히 효율적이라서 프리컴파일이 필요 없다고 말하면서 거듭제곱은 따로 제공해야 한다고 봅니다. 이 EIP는 클라이언트가 미리 네이티브로 구현해 두는 계약인 프리컴파일(precompile) 형태로 모듈러 거듭제곱을 제공합니다. 덕분에 EVM 안에서 RSA 검증을 비롯한 정수론 기반 암호를 효율적으로 쓸 수 있고 곱셈도 a*b = ((a+b)**2 - (a-b)**2) / 4 공식을 이용해 이 프리컴파일 하나로 처리할 수 있습니다.
무엇이 바뀌나
지금
- EVM 안에서 임의 길이 큰 정수의 모듈러 거듭제곱을 효율적으로 계산할 수단이 없습니다
- RSA 검증 같은 정수론 기반 암호를 컨트랙트에서 쓰기 어렵습니다
EIP-198 이후
- 0x05 주소의 프리컴파일이 BASE**EXPONENT % MODULUS를 한 번의 호출로 계산합니다
- RSA 검증과 다른 정수론 기반 암호를 EVM 안에서 쓸 수 있습니다
- 자주 쓰는 지수인 2, 3, 65537은 비트 기준 가스 계산 덕분에 비용이 공정하게 낮게 책정됩니다
누구에게 영향이 있나
- 컨트랙트 개발자: RSA 서명 검증이나 정수론 기반 암호 로직을 프리컴파일 호출 한 번으로 구현할 수 있습니다.
- 클라이언트 팀: 0x05 주소의 프리컴파일과 가스 공식(mult_complexity, ADJUSTED_EXPONENT_LENGTH)을 명세대로 구현해야 합니다.
- 사용자: RSA 같은 기존 암호 체계와 연동하는 온체인 서비스를 더 싼 비용으로 이용할 수 있습니다.
심층 설명
입력 형식과 패딩 규칙
입력은 <length_of_BASE> <length_of_EXPONENT> <length_of_MODULUS> <BASE> <EXPONENT> <MODULUS> 순서입니다. 각 길이 필드는 다음 값이 차지할 바이트 수를 나타내는 32바이트 왼쪽 패딩 정수입니다. 콜데이터는 오른쪽으로 0 바이트가 무한히 이어진 것으로 간주하고 남는 데이터는 무시합니다. 그래서 length_of_BASE가 0이면 base용 데이터를 전혀 읽지 않고 바로 다음 바이트부터 EXPONENT로 해석합니다. 모듈러스 데이터가 0x80 한 바이트만 있고 길이가 32로 선언돼 있으면 뒤를 0으로 채워 2**255로 읽습니다. 출력은 (BASE**EXPONENT) % MODULUS를 모듈러스와 같은 길이의 바이트 배열로 돌려줍니다.
가스 공식과 GQUADDIVISOR
가스 소비량은 floor(mult_complexity(max(length_of_MODULUS, length_of_BASE)) * max(ADJUSTED_EXPONENT_LENGTH, 1) / GQUADDIVISOR)입니다. GQUADDIVISOR는 20입니다. 즉 베이스와 모듈러스 중 더 긴 쪽의 곱셈 난이도에 지수의 실효 비트 길이를 곱한 값을 20으로 나눕니다. 가스가 부족할 만큼 큰 입력은 실행되지 않습니다. 원문은 모듈러스 길이를 2**256 - 1로 선언한 예시를 들며, 이런 계산에 충분한 가스를 제공하는 것이 불가능하므로 즉시 실패한다고 설명합니다.
ADJUSTED_EXPONENT_LENGTH 계산
지수의 실효 크기를 비트 단위로 재는 값입니다. length_of_EXPONENT가 32 이하이고 EXPONENT의 모든 비트가 0이면 0을 반환합니다. length_of_EXPONENT가 32 이하면 EXPONENT의 최상위 비트 인덱스를 반환합니다(1 -> 0, 2 -> 1, 3 -> 1, 255 -> 7, 256 -> 8). length_of_EXPONENT가 32를 넘으면 8 * (length_of_EXPONENT - 32)에 앞 32바이트의 최상위 비트 인덱스를 더합니다. 예를 들어 100바이트 지수 \x00\x00\x01\x00.....\x00이면 8 * (100 - 32) + 253 = 797입니다. 앞 32바이트가 전부 0이면 정확히 8 * (length_of_EXPONENT - 32)를 반환합니다.
mult_complexity 함수
큰 정수 라이브러리들이 쓰는 카라츠바(Karatsuba) 곱셈의 난이도를 근사하는 함수입니다. x가 64 이하면 x ** 2, 1024 이하면 x ** 2 // 4 + 96 * x - 3072, 그보다 크면 x ** 2 // 16 + 480 * x - 199680을 반환합니다. 입력 크기가 커질수록 제곱 항의 계수를 줄여, 단순 제곱보다 완만하게 비용이 늘어나도록 설계돼 있습니다.
비용 예시: EXP 명령어와 RSA
32바이트 지수를 쓰는 예시의 가스는 mult_complexity(32) * 255 / 20 = 13056으로, 같은 계산을 EXP 명령어로 할 때의 약 8배입니다. 4096비트 RSA 거듭제곱은 최악의 경우 22853376 가스가 들지만 실제 RSA 검증은 보통 지수 3이나 65537을 쓰므로 각각 5580, 89292 가스로 줄어듭니다. 지수를 길이가 아니라 비트 기준으로 계산하는 이유가 바로 이것으로, 곱셈에 쓰는 지수 2와 RSA 검증에 쓰는 3, 65537에 공정하게 과금하기 위해서입니다.
설계 의도: RSA 검증과 곱셈 재활용
이 프리컴파일의 목적은 EVM 안에서 RSA 검증과 다른 정수론 기반 암호를 효율적으로 쓸 수 있게 하는 것입니다. 덧셈과 뺄셈 프리컴파일은 EVM 내 알고리즘이 충분히 효율적이라 추가하지 않았습니다. 큰 정수 곱셈은 a * b = ((a + b)**2 - (a - b)**2) / 4 항등식을 이용해 이 프리컴파일로 처리할 수 있습니다. 이 EIP는 상태가 Final로 확정된 명세입니다.