EIP-7939 선행 0 비트 계산(CLZ) 명령어 (Count leading zeros (CLZ) opcode)
최종 확정 · EVM·실행 · 원문 상태 Final · 2025-04-28 작성
256비트 값에서 맨 앞에 연속으로 늘어선 0 비트가 몇 개인지 한 번에 세는 새 EVM 명령어 CLZ(0x1e)를 추가합니다. 비용은 5 가스입니다.
왜 필요한가
선행 0 개수 세기(count leading zeros)는 ARM 같은 많은 CPU가 기본 명령어로 제공하는 아주 기초적인 연산입니다. 로그·거듭제곱·제곱근 같은 수학 함수, 바이트 문자열 비교, 데이터 압축과 해제, 비트맵에서 다음 비트 찾기, 양자내성 서명 검증까지 폭넓게 쓰입니다. 그런데 이더리움 가상머신(EVM)에는 이 명령어가 없어서 지금은 Solidity 코드로 흉내 내야 합니다. 알려진 것 중 가장 빠른 구현도 약 184 가스를 쓰고, 큰 상수 여러 개를 담고 있어 컨트랙트 코드 크기를 키웁니다. 이 구현이 쓰는 동적 비트 시프트 연산은 영지식(ZK) 증명 환경에서 특히 비싸서 ZK 증명을 쓰는 시스템에는 부담이 더 큽니다. 명령어 하나를 추가하면 같은 계산을 5 가스에, 더 작은 코드로, 더 싼 증명 비용으로 처리할 수 있습니다.
무엇이 바뀌나
지금
- 선행 0 개수를 구하려면 Solidity로 복잡한 코드를 짜야 하고 약 184 가스가 듭니다
- 이 코드는 큰 상수를 여러 개 담고 자주 인라인되어 바이트코드가 커집니다
- 동적 비트 시프트를 여러 번 써서 ZK 증명 비용이 큽니다
EIP-7939 이후
- CLZ 명령어 하나로 같은 계산을 5 가스에 끝냅니다
- 컨트랙트 바이트코드가 작아집니다
- SP1 rv32im 기준으로 256비트 CLZ가 ADD보다 증명 비용이 싸집니다
누구에게 영향이 있나
- 스마트컨트랙트 개발자: 수학 라이브러리, 압축, 비트맵, 바이트 비교 코드가 짧아지고 가스가 줄어듭니다.
- 클라이언트 팀: 새 옵코드 0x1e를 구현해야 합니다. 상태를 건드리지 않는 단순 연산이라 구현 부담은 작습니다.
- ZK 증명 시스템과 L2: 비싼 동적 시프트 구현 대신 네이티브 명령어를 증명하므로 증명 비용이 줄어듭니다.
- 사용자: 이 연산을 많이 쓰는 앱에서 계산 비용이 싸집니다.
심층 설명
명령어 정의
새 옵코드 CLZ가 0x1e 번호로 추가됩니다. 스택에서 값 x를 하나 꺼낸 뒤, x의 최상위 1 비트 앞에 있는 0 비트 개수를 스택에 올립니다. x가 0이면 256을 올립니다. 원문은 같은 동작을 Solidity, Python, C++ 세 가지 참조 구현으로 보여 줍니다. Solidity 참조 구현은 약 184 가스를 쓰는, 알려진 것 중 가장 빠른 구현이고 C++ 구현 중 하나는 uint32 8개로 256비트 수를 표현해 SP1 rv32im 증명에 최적화한 형태입니다. 이 EIP는 Final 상태로 명세가 확정됐습니다.
가스 비용 5, MUL과 동일
명령어 비용은 5 가스로 MUL과 같습니다. 원래 3이었지만 너무 싸게 매겨서 생길 수 있는 서비스 거부(DoS) 위험을 피하려고 5로 올렸습니다. 근거로는 intx 라이브러리의 ADD 구현과 벤치마크한 결과를 제시합니다. CLZ는 ADD와 비슷한 연산 사이클을 쓰고 SP1 rv32im에 최적화한 변형은 평균과 최악의 경우 모두 ADD보다 적은 사이클을 씁니다. SP1 rv32im에서는 256비트 CLZ가 ADD보다 증명하기도 쌉니다.
0 입력의 특례 처리
CLZ(0)은 256을 반환합니다. 256은 255 바로 다음의 가장 작은 수여서 결과가 유효한 비트 위치 범위를 벗어났는지 확인할 때 추가 바이트코드가 거의 들지 않습니다. 바이트 단위로 데이터를 훑는 작업에서도 쓸모가 있습니다. 워드 전체가 0이면 256 >> 3을 계산해 건너뛸 바이트 수 32를 바로 얻을 수 있습니다. 예외를 던지는 대신 정의된 값을 돌려주는 설계입니다.
CTZ가 아니라 CLZ를 고른 이유
뒤쪽(최하위)의 0을 세는 CTZ(count trailing zeros)도 후보가 될 수 있지만 이 EIP는 CLZ만 추가합니다. 가장 낮은 1 비트는 x & -x 연산으로 쉽게 분리할 수 있어서 CLZ만 있으면 CTZ가 하는 일을 구현할 수 있기 때문입니다. 반대 방향은 성립하지 않습니다. CTZ로는 CLZ를 구현할 수 없습니다. 그래서 둘 중 표현력이 더 큰 CLZ를 선택했습니다.
ZK 증명 비용과 바이트코드 크기
현재 가장 빠른 Solidity 구현은 동적 비트 오른쪽 시프트(shr)를 여러 번 씁니다. ZK 증명 환경에서 시프트는 비싼 연산이라, SP1 rv32im에서는 32비트 오른쪽 시프트가 32비트 곱셈보다 1.6배 비쌉니다. 네이티브 CLZ 명령어는 이런 시프트 체인을 통째로 대체하므로 증명 비용이 줄어듭니다. 또 기존 Solidity 구현은 큰 상수 여러 개를 담고 있고 성능 때문에 자주 인라인되어 코드 크기를 키우는데, 옵코드 하나로 바꾸면 바이트코드도 작아집니다.
테스트 케이스
원문은 여섯 가지 테스트 케이스를 제시합니다. 입력 0은 256(0x100), 최상위 비트만 켜진 0x8000...00과 모든 비트가 켜진 0xffff...ff는 0, 0x4000...00과 0x7fff...ff는 1, 입력 1은 255(0xff)를 반환합니다. 최상위 1 비트의 위치가 같으면 그 아래 비트들이 무엇이든 결과가 같다는 점을 보여 주는 구성입니다.
보안과 하위 호환성
CLZ는 상태를 읽거나 쓰지 않는 명령어이고 메모리 사용과 연산 비용, 증명 비용 모두 최악의 경우에도 낮은 상수 수준입니다. 그래서 서비스 거부 공격에 악용될 수 없다고 원문은 설명합니다. 이전에 없던 새 옵코드이므로 기존에 배포된 컨트랙트의 동작을 바꾸지 않아 하위 호환성 문제도 없습니다.