allow Merkle trees of larger heights than 32 about twenty-first HOT 7 CLOSED

Yes, please! We would welcome a PR.

from twenty-first.

I'm fully in support of using an architecture independent type. 👍

from twenty-first.

Can I work on this?

from twenty-first.

Alright, will work on this.

from twenty-first.

Hey @aszepieniec, moving to 1 << 64 is a great choice as it future-proofs our design by accommodating a larger number of hashes.

I suggest making the variable type independent of the CPU/OS architecture. Therefore, instead of using the usize data type, I recommend using u64 or u128. This approach ensures consistent behavior, whether we're on a 16-bit device or a 256-bit behemoth (LOL).

Additionally, employing 1 << 64 allows us to potentially store up to 2^65 - 1 hashes. If each hash is a 32-byte SHA-256, we would require approximately 1 exabyte of storage.

Does this sound good to you?

from twenty-first.

So I've been talking about this with @jan-ferdinand and @aszepieniec, and we've come to the conclusion that nothing needs to be changed in the merkle_tree module.

I'm sorry that I haven't caught this earlier, but I don't see a reason to change from usize indices to u64 indices. I should have killed this issue before someone started working on it, @elielnfinic.

The reason this issue was opened is that @aszepieniec saw that Merkle Trees were being used in neptune-core where we also have Merkle Mountain Ranges that use u64 for indexing into the leaves. Notice that Merkle Mountain Ranges (MMR) is a entirely different data structure from Merkle trees, as the two implementations do not share any code (other than for a few (paranoid) tests).

The reason we want to use usize for the public-facing interface is that MerkleTree uses a Vec<Digest> to store all nodes in the tree. If the public interface was changed type conversion would just happen inside of the merkle_tree module instead of being handled by the caller. Since the Vec<T> type from the standard library always uses usize for lookups. In other words, you would just be sweeping the restriction under the rug and not actually fixing anything if you changed the public-facing interface of merkle_tree.

Notice that Vec<Digest> is used to store all nodes:

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MerkleTree<H>
where
    H: AlgebraicHasher,
{
    nodes: Vec<Digest>,
    _hasher: PhantomData<H>,
}

On the question of the size-limits:
The limits that are in place are actually good for cross-platform support, as they ensure that no one makes a MerkleTree that cannot be indexed on a 32-bit architecture.

const MAX_NUM_NODES: usize = 1 << 32;
const MAX_NUM_LEAVES: usize = MAX_NUM_NODES / 2;
pub const MAX_TREE_HEIGHT: usize = MAX_NUM_LEAVES.ilog2() as usize;

Removing these limits would exclude 32-bit architectures from handling all instances of a MerkleTree that could be generated on a 64-bit machine. So the current limits just ensure that 64-bit machines don't exclude 32-bit machines.

TL;DR: Let's not change anything, and sorry for not killing this issue before someone started working on it.

The only thing I see that could be improved is a comment on why these limits are there, so we don't go down this rabbit hole again.

from twenty-first.

Alright @Sword-Smith, thank you for clarification.

from twenty-first.