- when using
HistoricMerkleTree<n, T>, does setting n to 32 affect proof generation time compared to smaller values? - is the data structure capable of holding an unlimited amount of data?
research:
does setting n=32 take longer?
yes. n is the tree depth, and operations scale with it. the findPathForLeaf method has an explicit O(n) warning:
“Finds the path for a given leaf in a Merkle tree. Be warned that this is O(n) and should be avoided for large trees.”
source: compact/doc/ledger-adt.mdx at main · LFDT-Minokawa/compact · GitHub |
can it hold infinite data?
no - capacity is bounded to exactly 2^n leaves:
the compiler enforces 2 ≤ n ≤ 32:
“a bounded Merkle tree of depth nat where 2 <= nat <= 32 containing values of type value_type, with history”
source: compact/compiler/midnight-ledger.ss at main · LFDT-Minokawa/compact · GitHub
also documented in lang-ref:
“HistoricMerkleTree<n, T>, for a compile time integer 1 < n <= 32”
source: compact/doc/lang-ref.mdx at main · LFDT-Minokawa/compact · GitHub
questions for the team:
- what are the practical performance implications of n=32 vs n=16?
- are there recommended depth values for different use cases?
- does the history map also scale with operations, affecting performance?
- any guidance on when to use MerkleTree vs HistoricMerkleTree?