기술 요약: 온체인 레지스트리를 위한 상수 시간 추가(Constant-Time Append)의 비용 분석

문제 제기

프로비넌스 트리(Provenance Trees, PT)는 운영자 제어형 프로비넌스 인프라의 데이터 기질로 사용되는 추가 전용 방향성 비순환 그래프(append-only DAG)이다. 기존 연구들은 PT의 기본 추가 연산이 레지스트리 크기와 트리 깊이에 독립적인 $O(1)$ 가스 비용임을 주장했으나, 이 주장은 독립적인 프리미티브로서의 정식 격리, 명시적인 상수 경계, 또는 업계 표준인 증분 머클 트리(Incremental Merkle Tree, IMT)에 대한 경험적 벤치마킹이 결여되어 있었다.

제로 지식 증명 프로토콜(예: Tornado Cash, Semaphore) 및 롤업 상태 커밋먼트에서 지배적인 역할을 하는 IMT는 간결한 $O(\log N)$ 포함 증명(inclusion proofs)을 제공하지만, 추가 비용은 트리 깊이에 따라 로그 함수적으로 증가($\Theta(\log N)$)한다. 멤버십 증명이 주요 쿼리가 아닌 애플리케이션(예: 프로비넌스 레지스트리)의 경우, IMT의 비용 트레이드오프는 덜 유리하며, 대안이 더 저렴해지는 교차 지점(crossover point)은 아직 엄밀하게 확립되지 않았다.

방법론

본 논문은 **부모 해시 방향성 비순환 그래프(Parent-Hash Directed Acyclic Graph, PHDAG)**를 별도의 프리미티브로 격리하고, 이를 세 가지 관점에서 **증분 머클 트리(IMT)**와 비교한다:

1. 정식 복잡도 분석: 저자들은 PHDAG 추가 연산을 정식화하여, 이것이 레지스트리 크기($n$)나 깊이에 관계없이 유한한 수의 EVM 연산을 실행함을 증명한다. 이는 프런티어 업데이트 루프를 통해 깊이($d$)에 따라 선형적으로 확장되는 IMT와 대조된다.
2. 확률적 비용 모델링: 리프 인덱스의 이진 표현(해밍 무게, Hamming weight)에 따라 IMT 추가 비용이 달라짐을 인식하여, 저자들은 인덱스의 균등 분포 하에서 IMT의 삽입당 가스 비용을 확률 변수로 모델링한다. 이들은 "쓰기 레벨(프런티어 업데이트)"과 "읽기 레벨(쓰기 없이 트래버스)"을 구분하여, 평균 및 분산에 대한 폐쇄형 식(closed-form expressions)을 도출한다.
3. 경험적 검증: 두 프리미티브를 위한 독립적인 컨트랙트가 Base Sepolia 테스트넷에 배포되었다. 실험은 1에서 25 사이의 트리 깊이를 대상으로 수행되었다.
   • IMT: 변동성을 포착하기 위해 각 깊이마다 $\max(d, 2)$번의 추가 연산을 수행하는 "비례적 깊이 스윕(proportional depth sweep)"을 통해 테스트되었다.
   • PHDAG: 비용 분포와 분산을 특성화하기 위해 200회의 추가 연립 실행을 통해 테스트되었다.
   • 지표: 초기 콜드 스토리지 초기화 비용을 제외하고, 정상 상태(steady-state) 성능에 집중하기 위해 트랜잭션 영수증으로부터 가스 소비량을 측정하였다.

주요 기여

1. PHDAG의 정식 복잡도

본 논문은 PHDAG 추가가 엄격하게 $O(1)$ 가스 비용임을 입증한다.

• 메커니즘: 각 추가는 고유 식별자에 의해 키가 지정된, 이전에 손대지 않은 세 개의 스토리지 슬롯(cold SSTORE)에 기록되며, 카운터에 대한 웜 라이트(warm write) 하나를 포함한다.
• 불변성: 비용은 글로벌 레지스트리 크기 $n$ 및 어떠한 트리 깊이 개념에도 불변이다. 트랜잭션의 액세스 리스트는 매 트랜잭션 시작 시 리셋되므로, PHDAG는 매번 새로운 슬롯에 쓰기를 수행하며, 따라서 비용은 컨트랙트의 상태가 아닌 고정된 연산 수에 의존한다.
• 재구성: 본 논문은 전체 레지스트리가 공용 이벤트 로그로부터 $O(|V|)$ 시간에 재구성될 수 있음을 증명한다. 이벤트 스트림이 정형적인 이력을 보유하고 있기 때문이다.

2. IMT를 위한 확률적 모델

저자들은 IMT의 삽입당 비용 $g$가 리프 인덱스 $i$에 의존하는 확률 변수임을 도출한다:

• 평균: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$, 여기서 $c_L$과 $c_R$은 각각 쓰기 및 읽기 레벨의 한계 비용이다.
• 분산: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$.
• 시사점: 상대적 변동성(변동 계수)은 깊이가 증가함에 따라 감소하지만, 절대적 표준 편차는 $\Theta(\sqrt{d})$로 증가하여, 높은 깊이의 레지스트리에 대해 운영상의 예측 불가능성을 초래한다.

3. 경험적 교차 및 검증

• PHDGA 성능: 추가당 76,276 가스(표준 편차 $\approx 6$ 가스)로 측정되어 깊이 불변성을 확인하였다.
• IMT 성능: 비용이 깊이에 따라 선형적으로 증가하였다.
• 교차 지점: PHDAG가 IMT보다 저렴해지는 깊이는 $d \approx 6$에서 $7.2$ 사이로 식별되었다.
  • $d=6$에서 측정된 IMT 비용($\approx 78,000$ 가스)이 PHDAG 비용을 초과하였다.
  • (균등 인덱스 분포 하의) 생애 주기 평균 교차 지점은 $d^* \approx 7.2$로 계산되었다.

결과

경험적 데이터는 이론적 모델을 검증한다:

• PHDAG는 모든 테스트된 깊이에서 무시할 만한 분산과 일정한 비용을 보인다.
• IMT는 선형적인 비용 증가와 깊이에 따른 증가하는 절대적 분산을 보인다.
• 프로덕션 맥락: 조사된 모든 프로덕션 레지스트리(Tornado Cash, Semaphore, zkSync, Scroll, Linea)는 $d \ge 20$의 깊이에서 작동한다. 결과적으로, 이러한 모든 시스템은 현재 PHDAG가 엄격하게 더 저렴하며, 간결한 멤버십 증명이 필요하지 않은 경우 예측 가능한 비용을 제공하는 영역에서 작동하고 있다.

의의 및 주장

본 논문은 PHDAG 프리미티브가 다음과 같은 추가 전용 프로비넌스 레지스트리를 위한 최적의 선택이라고 주장한다:

1. 간결한 멤버십 증명이 필요하지 않은 경우: 프로비넌스 쿼리는 일반적으로 $O(\log N)$ 머클 증명보다는 부모 체인 트래버설이나 고유 ID에 의한 존재 확인을 포함하며, 이는 $O(|V|)$ 로그 기반 재구성을 통해 지원된다.
2. 비용 예측 가능성이 중요한 경우: 고용량 추가 서비스를 관리하는 운영자에게, PHDAG의 거의 제로에 가까운 분산은 IMT에 비해 최악의 가스 테일(worst-case gas tails)을 대비한 예산 책정 필요성을 제거하여 상당한 운영상의 이점을 제공한다.
3. 강건성(Robustness)이 최우선인 경우: PHDAG의 로그-캐노니컬 설계는 레지스트리의 이력이 외부 인덱싱 서비스나 현재 컨트랙트 스토리지 상태에 의존하지 않고, 공용 이벤트 로그만으로 파괴 불가능하며 재구성 가능함을 보장한다.

저자들은 PHDAG가 ZK 애플리케이션이 아닌 용도에 대해, 깊이 의존적인 IMT의 대안으로서 상수 비용 및 깊이 불변성을 제공하는, 이더리움 프로비넌스 인프라의 균일한 인터페이스로 표준화될 강력한 후보라고 결론짓는다.