Deep EVM #11: Huff 점프 테이블 — Solidity 오버헤드 없는 O(1) 함수 디스패치

Solidity 디스패처의 문제점

Solidity 컨트랙트를 호출하면 EVM이 가장 먼저 실행하는 것은 함수 디스패처입니다. Solidity는 콜데이터의 처음 4바이트(함수 셀렉터)를 각 알려진 셀렉터와 비교하는 선형 if-else 체인을 생성합니다:

CALLDATALOAD 0x00
SHR 224
DUP1
PUSH4 0x70a08231    // balanceOf(address)
EQ
PUSH2 dest1
JUMPI
DUP1
PUSH4 0xa9059cbb    // transfer(address,uint256)
EQ
PUSH2 dest2
JUMPI
...

N개의 함수가 있는 컨트랙트의 경우 이것은 O(N)입니다 — 최악의 경우 일치를 찾기 전에 모든 N개 셀렉터를 확인합니다. 각 비교는 약 22 가스(DUP1 + PUSH4 + EQ + PUSH2 + JUMPI)가 듭니다. 20개 함수가 있는 컨트랙트는 디스패치에만 최대 440 가스를 낭비합니다. Solidity 컴파일러(0.8.22 이후)는 때때로 큰 인터페이스에 대해 이진 검색 트리를 사용하여 O(log N)으로 줄이지만, 이것도 최적은 아닙니다.

하루에 수백만 번 호출되는 MEV 봇 컨트랙트의 경우, 호출당 400+ 가스 단위가 실제 ETH로 누적됩니다.

점프 테이블 접근법: O(1)

점프 테이블은 비교가 아닌 산술을 사용하여 함수 셀렉터를 코드 오프셋에 직접 매핑합니다. 이 아이디어는 CPU 아키텍처에서 차용되었습니다 — 계산된 GOTO는 1960년대부터 시스템 프로그래밍에서 사용되어 왔습니다.

개념:

1. 콜데이터에서 함수 셀렉터를 추출합니다 (4바이트).
2. 산술을 사용하여 셀렉터에서 점프 대상을 계산합니다.
3. 해당 대상으로 직접 JUMP합니다.

비교도 없고, 분기도 없으며, 함수 수에 관계없이 상수 시간입니다.

접근법 1: 최소 셀렉터 인코딩

컨트랙트에 소수의 함수(1-8개)가 있는 경우, 첫 번째 바이트나 두 번째 바이트가 고유한 작은 정수를 인코딩하는 배니티 셀렉터를 마이닝하여 셀렉터를 수동으로 할당할 수 있습니다:

#define macro DISPATCHER() = takes(0) returns(0) {
    0x00 calldataload       // [calldata_word]
    0xe0 shr                // [selector]

    // 라우팅 바이트 추출 — 셀렉터의 첫 번째 바이트
    0x18 shr                // [first_byte]

    // 테이블의 각 항목은 2바이트 (PUSH2 offset)
    // 테이블 시작 + first_byte * 2 = 점프 대상 포인터
    0x02 mul                // [offset_in_table]
    __tablestart(JumpTable) // [table_start, offset_in_table]
    add                     // [entry_address]
    
    // 테이블에서 2바이트 점프 대상 로드
    codecopy_dest:
    0x00 codecopy           // 코드에서 메모리로 2바이트 복사
    0x00 mload              // [jump_dest (32바이트로 패딩)]
    0xf0 shr                // [jump_dest] — 2바이트 값을 얻기 위해 오른쪽 시프트
    jump                    // 함수 본문으로 GOTO
}

#define jumptable JumpTable {
    swap_exact   // selector 0x00...
    add_liq      // selector 0x01...
    remove_liq   // selector 0x02...
    flash_loan   // selector 0x03...
}

접근법 2: 압축된 코드 테이블

최대 밀도를 위해 __tablestart와 __tablesize를 사용하여 점프 테이블을 바이트코드에 직접 패킹할 수 있습니다. Huff는 점프 테이블을 일급 구성 요소로 기본 지원합니다:

#define jumptable__packed SELECTOR_TABLE {
    fn_swap
    fn_transfer
    fn_approve
    fn_balance
}

#define macro MAIN() = takes(0) returns(0) {
    0x00 calldataload 0xe0 shr  // [selector]

    // 셀렉터를 인덱스(0-3)로 매핑
    // 셀렉터 값에 따라 다름 — 상위 바이트가 인덱스가 되도록 마이닝
    0x18 shr                    // [index]

    // 경계 확인
    dup1 0x04 lt                // [in_bounds?, index]
    valid jumpi
    0x00 0x00 revert

    valid:
    // 압축 테이블에서 로드 (항목당 2바이트)
    __tablestart(SELECTOR_TABLE)
    swap1 0x02 mul add          // [table_entry_ptr]

    // 2바이트 코드 오프셋 읽기
    0x1e mload                  // 트릭: codecopy를 통해 코드에서 mload
    jump

    fn_swap:
        SWAP_IMPL()
    fn_transfer:
        TRANSFER_IMPL()
    fn_approve:
        APPROVE_IMPL()
    fn_balance:
        BALANCE_IMPL()
}

셀렉터 추출을 위한 콜데이터 비트 시프팅

표준 셀렉터 추출은:

0x00 calldataload   // 콜데이터 위치 0에서 32바이트 로드
0xe0 shr            // 상위 4바이트를 분리하기 위해 224비트(256 - 32) 오른쪽 시프트

비용: PUSH1 (3) + CALLDATALOAD (3) + PUSH1 (3) + SHR (3) = 12 가스.

셀렉터의 1-2바이트만 필요한 경우 더 저렴한 대안:

0x00 calldataload   // [calldata_word]
0xf8 shr            // [first_byte] — 바이트 0만 얻기 위해 248비트 오른쪽 시프트

같은 가스이지만, 이제 라우팅 키가 1바이트(256개 가능한 값)입니다. 컨트랙트에 256개 이하의 함수가 있다면, 1바이트로 각각을 고유하게 식별할 수 있습니다. 각 함수의 첫 번째 셀렉터 바이트가 고유하도록 배니티 셀렉터를 마이닝합니다(cast selectors 또는 커스텀 스크립트 사용).

가스 비교

다양한 함수 수에 대한 디스패치 비용을 벤치마킹합시다:

함수 수	Solidity (if-else)	Solidity (이진)	Huff 점프 테이블
2	22-44 가스	22-44 가스	15 가스
4	22-88 가스	22-66 가스	15 가스
8	22-176 가스	22-88 가스	15 가스
16	22-352 가스	22-110 가스	15 가스
32	22-704 가스	22-132 가스	15 가스

점프 테이블 비용은 상수입니다: CALLDATALOAD (3) + SHR (3) + 산술 (3-6) + JUMP (8) = 약 15-18 가스. 함수 수에 관계없이 변하지 않습니다.

배니티 셀렉터 마이닝

점프 테이블 접근법이 작동하려면 예측 가능한 라우팅 바이트를 가진 함수 셀렉터가 필요합니다. 이를 마이닝할 수 있습니다:

import hashlib
import itertools

target_byte = 0x00  # 셀렉터의 원하는 첫 번째 바이트
base_name = "swap"

for suffix in itertools.count():
    name = f"{base_name}{suffix}(uint256,address)"
    selector = hashlib.sha3_256(name.encode()).digest()[:4]  # keccak256
    if selector[0] == target_byte:
        print(f"Found: {name} -> 0x{selector.hex()}")
        break

실무에서는 Foundry의 cast sig이나 원하는 접두사를 가진 셀렉터를 찾기 위해 함수 이름을 무차별 대입하는 Rust 도구를 사용합니다. 8개 함수가 있는 컨트랙트의 경우, 8개 호환 셀렉터를 마이닝하는 데 밀리초가 걸립니다.

바이트코드 크기 영향

바이트코드 크기는 배포 비용에 직접 영향을 미칩니다 (CREATE를 통해 바이트당 200 가스, 기본 32,000). 비교:

접근법	런타임 바이트코드	배포 가스 (런타임만)
Solidity (8 함수)	~800 바이트	160,000 가스
Huff 점프 테이블 (8 함수)	~200 바이트	40,000 가스
Huff 최소 (2 함수)	~61 바이트	12,200 가스

주소 교체나 CREATE2를 통한 매개변수 업데이트를 위해 컨트랙트를 자주 재배포하는 MEV 봇의 경우, 더 작은 바이트코드가 직접적으로 낮은 운영 비용으로 변환됩니다.

제한 사항

1. 비표준 ABI — 외부 도구(Etherscan, 지갑)가 커스텀 ABI 정의 없이는 콜데이터를 디코딩할 수 없습니다.
2. 셀렉터 마이닝 — 사전 작업이 필요하고 함수 이름을 제약합니다.
3. 유지보수 비용 — Huff는 Solidity보다 감사하고 수정하기 어렵습니다.
4. 압축 테이블 — __tablestart와 __tablesize 내장 함수에 Huff 컴파일러의 엣지 케이스가 있습니다. 철저히 테스트하세요.

요약

점프 테이블은 Solidity의 O(N) 디스패치 체인을 O(1) 계산된 점프로 대체합니다. 가스 절약은 수백만 호출에 걸쳐 복합됩니다 — MEV 봇 및 DEX 라우터와 같은 고빈도 컨트랙트에 의미 있는 이점입니다. 배니티 셀렉터 마이닝과 결합하면, 인터페이스 크기에 관계없이 디스패치 오버헤드가 20 가스 미만인 컨트랙트를 구축할 수 있습니다. 다음 기사에서는 고급 Huff 패턴을 탐구합니다: 적응형 실행, 다중 운영자 인증, 메모리 레이아웃 트릭.