Owners: @Mehmet @Giacomo Pasini
Reviewers: 🟢@Thomas Lavaur 🟢@Álvaro Castro-Castilla 🟢@David Rusu
Introduction
Nullifiers are cryptographic markers derived from spent notes, used to prevent double-spending in privacy-preserving systems. Once revealed, nullifiers become public information. In traditional systems, nullifiers are stored in sets maintained locally by validators. However, this approach requires validators to maintain the full nullifier set state, which can become costly and inefficient over time.
This document introduces a compact data structure, known as a nullifier tree, which eliminates the need for validators to store the nullifier set state. Instead, validators verify operations on the nullifier tree to ensure that nullifiers are correctly managed. Nullifier trees enable efficient verification of whether a nullifier has already been spent, while significantly reducing the storage and computational overhead for validators. This approach ensures data integrity and facilitates fast and secure transaction validation without compromising scalability.
This document compares two primary data structures for implementing nullifier trees in Nomos:
The objective is to evaluate these structures based on performance, scalability, and implementation complexity to determine their suitability for the Nomos ledger protocol.
This document provides a technical comparison between Sparse Merkle Trees (SMTs) and Indexed Merkle Trees (IMTs) in the context of implementing nullifier trees for the Nomos ledger protocol. The goal is to evaluate both structures based on:
In the document, SMT and IMT structures have been examined separately, and their features have been explained. Then, the differences between the two structures and performance comparisons have been made. Additionally, the details of the implementations performed for SMT and IMT have also been shared. As a result of the studies conducted, it has been observed that the IMT structure provided better performance results for Nomos ledger representation. Moreover, to achieve an efficient implementation, the IMT structure was slightly modified and used together with a Merkle Mountain Range (MMR). The details of this custom usage are explained in the relevant section.
The following sections delve into the initialization, update, and proof processes for each data structure, highlighting their ZK circuit complexity, storage requirements, and performance characteristics.
A Sparse Merkle Tree is a cryptographic data structure designed to store data in a way that allows for efficient verification of data existence or non-existence. It is characterized by having a fixed size, determined by the number of possible elements in the set, which creates a vast number of leaves. Each leaf corresponds to a potential index in the tree, derived by hashing an element of the set, and is initially initialized to a default value, representing the absence of any element at that position. When a value is added to the tree, the corresponding leaf is updated to reflect its inclusion, and the hashes along the path to the root are recomputed to maintain the tree's integrity.