접근 빈도가 항목마다 다르고 시간에 따라 변할 수 있는 동적 워크로드를 위한 인증 데이터 구조(ADS) '허프만-머클 트리(HMT)'를 제안한 연구다. 검증 가능한 스토리지, 인터넷 투명성 서비스, 블록체인 등에 쓰이는 ADS는 짧은 커밋먼트로 대규모 가변 상태에 대한 항목 소속 증명을 가능케 하는데, 기존 연구는 지속적으로 변화하는 접근 편향에 대한 성능 최적화를 충분히 다루지 못했다. HMT는 진화하는 접근 빈도를 지원하도록 확장한 허프만 코딩 기반 머클트리 레이아웃과, 핫·콜드 계층으로 항목을 분할해 적응적으로 이전시키는 탄력적 계층화 방식을 결합했다. 실제 데이터로 이더리움의 머클 패트리샤 트라이(MPT) 및 그 대체안인 통합 이진 트리(UBT)와 비교한 결과, HMT의 최적 정책은 평균 해시 연산량이 MPT 대비 약 2.4배, UBT 대비 0.34배 적었고 증명 크기도 MPT 대비 0.18배, UBT 대비 0.55배로 짧았다.

• •접근 빈도 변화에 대응하는 동적 인증 데이터 구조 '허프만-머클 트리(HMT)' 제안
• •자주 접근되는 항목을 루트에 가깝게 배치하는 허프만 코딩 기반 레이아웃 적용
• •핫·콜드 계층 분할과 적응적 이전을 결합한 탄력적 계층화 방식 도입
• •이더리움 MPT 대비 평균 해시 연산 약 2.4배 감소, 증명 크기 0.18배로 단축
• •대체안 UBT 대비도 해시 연산 0.34배, 증명 크기 0.55배로 우수한 성능