EIP-3068 BN256 해시투커브 프리컴파일 (Precompile for BN256 HashToCurve Algorithms)
콜 결정 없음 · 보안·프라이버시 · 원문 상태 Stagnant · 2020-10-23 작성
BN256 타원곡선에서 임의의 메시지를 곡선 위 점으로 변환하는 해시투커브(HashToCurve) 연산을 프리컴파일로 추가해, EVM에서 BLS 서명 검증을 페어링 체크 수준의 저렴한 비용으로 할 수 있게 합니다.
왜 필요한가
BLS 서명을 검증하려면 메시지를 타원곡선 위의 점으로 바꾸는 해시투커브 연산이 필요한데, 현재 EVM에는 이 연산을 위한 전용 프리컴파일이 없습니다. Solidity로 직접 구현하면 비용이 페어링 체크(pairing check) 한 번과 비슷한데, 실제 계산량은 그보다 한 자릿수 적습니다. EIP-198과 EIP-1108로 BN256에서 덧셈, 스칼라곱, 페어링 체크 비용이 낮아지면서 ETHDKG 같은 분산 키 생성(DKG) 프로토콜의 비용도 줄었지만 DKG에서 만들어진 부분 서명이나 그룹 서명을 EVM에서 검증할 방법은 없었습니다. 초기 BLS 논문의 MapToGroup 방식은 비결정적이어서 EVM에서 계산량을 예측하기 어렵고 Fouque와 Tibouchi가 제시한 결정적 매핑 방식이 임의 오라클과 구분 불가능함을 증명해 이를 대체할 수 있었습니다.
무엇이 바뀌나
지금
- EVM에 BN256용 해시투커브 프리컴파일이 없다
- Solidity로 해시투커브를 구현하면 페어링 체크와 비슷한 가스비가 든다
- ETHDKG의 부분 서명·그룹 서명을 EVM에서 검증할 방법이 없다
EIP-3068 이후
- HashToG1, HashToG2 프리컴파일로 메시지를 BN256 곡선 위 점으로 결정적으로 매핑한다
- BLS 서명 검증 비용이 페어링 체크 수준으로 낮아진다
- ETHDKG로 만든 그룹 서명과 부분 서명을 EVM에서 검증할 수 있게 된다
누구에게 영향이 있나
- 스마트컨트랙트 개발자: BLS 서명 검증 로직을 저렴한 프리컴파일 호출로 대체할 수 있습니다.
- DKG·임계서명 프로토콜(ETHDKG 등): 오프체인에서 만든 그룹 서명과 부분 서명을 온체인에서 검증할 수 있게 됩니다.
- 클라이언트 구현팀: 새 프리컴파일 HashToG1, HashToG2와 그 가스 계산 규칙을 EVM에 추가해야 합니다.
심층 설명
HashToG1: 두 번 매핑해서 더한다
HashToG1(msg) 함수는 메시지를 서로 다른 도메인 구분 파라미터(dsp1, dsp2) 쌍인 0x00/0x01과 0x02/0x03으로 HashToBase에 각각 넣어 두 개의 체 원소를 얻습니다. 이 두 원소를 BaseToG1 함수로 BN256 G1 곡선 위의 점으로 각각 매핑한 뒤, 두 점을 타원곡선 덧셈(ECAdd)으로 더한 값이 HashToG1의 최종 결과입니다.
HashToBase: Keccak256로 체 원소 만들기
HashToBase(msg, dsp1, dsp2)는 먼저 dsp1을 메시지 앞에 붙여 Keccak256으로 해시한 값과 dsp2를 붙여 해시한 값을 각각 uint256으로 구합니다. 첫 번째 해시 결과에는 2^256을 체의 소수(fieldPrime)로 나눈 나머지인 상수를 곱하고 여기에 두 번째 해시 결과를 더한 뒤 fieldPrime으로 나눈 나머지를 취해 하나의 체 원소를 돌려줍니다.
BaseToG1: 체 원소를 곡선 위 점으로
BaseToG1(t)는 BN256 G1 곡선 방정식 y^2 = x^3 + curveB를 기준으로 t로부터 세 개의 x 후보값(x1, x2, x3)을 계산합니다. x1^3+curveB와 x2^3+curveB가 각각 체에서 제곱수인지(is_square)를 확인해 세 후보 중 실제로 곡선 위에 있는 x를 상수 시간 비교(ConstantTimeEquality)로 선택하고 y는 sign0(t)에 따라 부호가 결정된 제곱근으로 계산합니다. inverse, is_square, sqrt는 모두 체 안에서의 연산이며 이 알고리즘은 Fouque와 Tibouchi의 결정적 매핑을 따릅니다.
HashToG2와 코팩터 제거
HashToG2(msg)는 dsp 0x04부터 0x0b까지 서로 다른 네 개의 도메인 구분자로 HashToBase를 네 번 호출해 GF(fieldPrime^2) 위의 두 원소(fieldElement0, fieldElement1)를 만듭니다. 각 원소를 BaseToTwist 함수로 BN256의 트위스트(twist) 곡선 위의 점으로 매핑한 뒤 ECAdd로 더하고 마지막으로 ClearCofactor(ECMul로 cofactor를 곱하는 연산)를 적용해 실제 G2 그룹 안의 점으로 좁힙니다. BaseToTwist는 BaseToG1과 같은 구조를 twist 곡선 방정식 y^2 = x^3 + curveBPrime에 맞춰 적용한 것입니다.
설계 근거: 참고 논문과 미해결 선택
BaseToG1 알고리즘은 Fouque와 Tibouchi의 논문을 기반으로 하되 Wahby와 Boneh의 논문을 참고해 일부 수정했고 HashToG2는 Wahby-Boneh 논문을 따릅니다. HashToBase에서 쓰는 해시 함수(여기서는 Keccak256)와 HashToBase 자체의 구성은 바뀔 수 있는 선택지로 남겨 두었습니다. 또한 BaseToG1·BaseToTwist 끝에서 쓰는 sign0 호출을 is_square로 바꾸면 Fouque-Tibouchi 논문에서 증명된 원래의 결정적 매핑과 정확히 같아져 임의 오라클과 구분 불가능하다는 증명이 그대로 적용되지만 sign0를 그대로 썼을 때도 이 성질이 유지되는지는 증명되지 않았다고 밝힙니다.
가스 비용 추정치
저자는 로컬 머신에서 ECMul이 연산당 68마이크로초 걸렸고 현재 ECMul 가스비가 6000임을 기준으로 다른 연산의 비용을 추정했습니다. HashToG1은 32바이트 메시지에서 94마이크로초, 1024바이트에서 105마이크로초가 걸려 가스비를 8500 + len(bytes)로 추정했습니다. HashToG2는 32바이트에서 886마이크로초, 1024바이트에서 912마이크로초가 걸려 가스비를 80000 + 3*len(bytes)로 추정했습니다. 이 수치들은 테스트 케이스나 구현으로 확정되지 않은 추정값입니다.
보안 고려사항: BN256의 보안 강도 하향
exTNFS 관련 연구 이후 BN256 곡선이 보장하던 128비트 보안 수준은 더 이상 유지되지 않고 보수적인 추정으로는 약 100비트 수준이라고 밝힙니다. 저자는 이 정도면 여전히 많은 공격자에게는 닿기 어렵지만 주의가 필요하다고 말합니다. 이 문제는 MadNet 백서에서도 언급되었고 MadNet에서는 부분 그룹 서명이 유효하려면 Secp256k1 서명을 추가로 요구해 부분적으로 완화했습니다. 저자는 MadHive에 소속되어 MadNet 개발과 백서 작성에 참여했음을 밝힙니다. 또한 BN256의 이러한 보안 우려는 페어링 체크를 쓰는 모든 연산에 공통된 것이며 이 EIP와는 독립적이라고 설명합니다.
진행 상태: Stagnant, 미완성 항목
이 EIP는 EIP-198과 EIP-1108을 전제로 하며 원문의 Test Cases와 Implementation 항목은 모두 TBD로 비어 있습니다. 상태는 Stagnant로, 명세가 테스트나 구현으로 검증되지 않은 채 멈춰 있는 상태입니다. 콜 기록에 이 EIP에 대한 별도의 포크 포함 논의는 없습니다.