[논문] Parent-Hash DAG: 온체인 레지스트리의 상시 시간 추가 비용 분석

개요

Provenance 트리는 퍼블릭 블록체인에 고정된 아티팩트 등록을 위한 append‑only(추가 전용) 방향성 비순환 그래프(DAG)이며, 최근 연산자 기반 접근 제어 프로비넌스 인프라의 데이터 기반으로 도입되었습니다. 이 구조의 핵심 데이터 패턴은 부모‑해시 방향성 비순환 그래프(PHDAG) 로, 각 추가 연산은 이전에 한 번도 사용되지 않은 슬롯에 대해 일정한 수의 저장 쓰기만 수행합니다. 이 패턴은 기존에 독립적인 원시 연산으로 분리되거나, 명시적인 상수와 함께 형식적으로 한정되지 않았으며, 표준 대안인 증분 머클 트리(IMT) 와 비교한 벤치마크도 없었습니다. 우리는 PHDAG 추가 연산을 가스 비용 O(1) 로 정량화했으며, 이는 레지스트리 크기와 트리 깊이에 무관합니다. 또한 IMT에 대해 삽입 비용을 리프 인덱스에 대한 확률 변수로 모델링하고, 평균과 분산에 대한 닫힌 형태 식을 도출했습니다. 두 모델 모두 Base Sepolia 네트워크에서 깊이 1부터 25까지 실험적으로 검증했습니다. PHDAG는 깊이에 관계없이 76,276 가스(표준편차 약 6 가스)로 일정했으며, IMT 비용은 깊이에 따라 선형적으로 증가했습니다. IMT가 더 저렴해지는 교차점은 조사한 모든 실서비스 레지스트리 깊이보다 훨씬 낮은 수준에 위치합니다. 또한 우리는 오프체인 의존 없이 퍼블릭 이벤트 로그만으로 레지스트리를 선형 시간에 신뢰성 있게 재구성할 수 있음을 입증했습니다.

주요 기여

이 논문은 다음 분야의 연구를 다룹니다:

• cs.DC
• cs.CR

방법론

자세한 방법론은 전체 논문을 참고하십시오.

실용적 함의

본 연구는 cs.DC 분야의 발전에 기여합니다.

저자

• Ian C. Moore
• Fernando Paredes Garcia

논문 정보

• arXiv ID: 2606.09593v1
• 분류: cs.DC, cs.CR
• 발표일: 2026년 6월 8일
• PDF: PDF 다운로드