Merkle tree does extra hashing that increases the cost in POSW

[kobigurk]

The native Merkle tree implementation is doing extra hashing which is not crucial:

• The root hash is being hashed: againhttps://github.com/AleoHQ/snarkOS/blob/51b71c1cbd9eec0ccd95016a1b247ce0cd1f2375/algorithms/src/merkle_tree/merkle_tree.rs#L72
• The leaves are hashed: https://github.com/AleoHQ/snarkOS/blob/51b71c1cbd9eec0ccd95016a1b247ce0cd1f2375/algorithms/src/merkle_tree/merkle_tree.rs#L44

Both of them are not necessary for correctness/security (although hashing the leaves is standard practice).

If we remove these then the proof can be focused on hashing the transaction IDs, resulting in a higher possible capacity.

[howardwu]

What's the status on this?

[kobigurk]

The root hash being hashed is fixed and merged as of https://github.com/AleoHQ/snarkOS/pull/98 (this was actually a bug for full trees).

The hashed leaves are not relevant anymore for POSW, which now receives subroots.