Reducing the number of Merkle Tree updates through lazy evaluation

Benaloh ら(EUROCRYPT'97)によち提案された暗号学的アキュムレータは，集合の要素に対するメンバーシップ証明を効率的に行うためのデータ構造である．Merkle Treeは，暗号学的ハッシュ関数を利用した暗号学的アキュムレータの一形態であり，ブロックチェーン技術において重要な役割を担っている．Merkle Treeの主要な問題点は，要素の追加または削除が行われる際に全体の更新が必要である点である．本研究では，遅延評価を行うMerkle Treeを提案し，これにより，Merkle Treeの更新回数を削減を行う．この提案手法では，各ノードに遅延部を設け，新たなデータのハッシュ値を一時的に保存することで，根の即時更新を避けながら要素の追加や削除を行うことが可能である．さらに，Barthoulotら(AFRICACRYPT'24)が提案した暗号学的アキュムレータのモデルのもとで，提案手法が暗号学的アキュムレータとしての性質を満たすことを示す．

The cryptographic accumulator proposed by B. Benaloh et al. (EUROCRYPT'97) is a data structure designed for efficiently proving membership of elements within a set. The Merkle Tree (CRYPTO'87), a form of cryptographic accumulator utilizing cryptographic hash functions, plays a crucial role in blockchain technology. One of the primary limitations of the Merkle Tree is the need for complete updates when elements are added or deleted. In this study, we propose a Merkle Tree with lazy evaluation to reduce the number of updates required. Our proposed method introduces a lazy component at each node, temporarily storing the hash value of new data, thereby enabling the addition or deletion of elements without immediate updates to the root. Additionally, we demonstrate that our proposed method satisfies the properties of a cryptographic accumulator within the model proposed by Barthoulot et al. (AFRICACRYPT'24).