Move away from XORing hashes

[damip]

Problem

XORing 256 bit item hashes to compute the hash of a list of items is vulnerable: people are able to generate lists of elements that have a zero hash.

https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf

Sparse Merkle Trees

Maybe a Sparse Merkle Tree is the way to go ? Efficient insertion/deletion on sorted entries, efficient proofs of existence but also (unlike merkle trees) efficient proof of absence !

Intros:

https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837

https://medium.com/newcryptoblock/sparse-merkle-tree-introduction-a267f3a29223

http://www.links.org/files/RevocationTransparency.pdf

Some crates to explore :

https://diem.github.io/diem/diem_jellyfish_merkle/index.html

https://github.com/y-pakorn/cw-merkle-tree

https://docs.rs/lsmtree/latest/lsmtree/

https://docs.rs/sparse-merkle-tree/latest/sparse_merkle_tree/

https://docs.rs/monotree/latest/monotree/ => Looks really cool: out of the box blake3 and rocksdb support !

[dr-chain]

Apparently, since our current approach of XORing hashes (or Multiset Hashing) is prone to birthday paradox vulnerability, we need to replace it with something similar but resistant to birthday paradox attacks.

Currently, the proposed solutions are -

1. Sparse Merkle Tree
2. Incremental Hashing (like in PCR Extend)

While Sparse Merkle Tree is like a Merkle tree which is sparse, the algorithm of Incremental Hashing is rather simple New Hash = HASHalg( Old Hash || New Value).

In order to make an informed decision, several factors for existing and two proposed solutions need to be compared. The following table gives a gist of the comparison.

Features	Multiset Hashing - XOR (Current)	Sparse Merkle Tree	Incremental Hashing (PCR Extend)
Insertion	O(1)	Log(NE)	O(1)
Deletion	O(1)	Log(NE)	O(1)
Proof of Change	N.A.	N.A.	O(NC)
Proof of Presence	N.A.	Log(NE)	N.A.
Proof of Absence	N.A.	Log(NE)	N.A.
Factors to Consider	Can be attacked (birthday problem)	Needs a performance benchmark	Changes must be deterministic (fused, pruned and sorted)

*Legends: NE - Number of Elements, NC - Number of Changes

ToDos:

• Benchmark the performance of various Sparse Merkle Tree libraries and compare them.
• Start implementation of deterministic order for any changes in the database. This property is highly desirable whether XOR hashing is replaced with Incremental hashing or not.
• If benchmark performance is OK, start integration of Sparse Merkle Tree, else - start integration of Incremental Hashing.

[damip]

Benchmark task: #3859

[dr-chain]

Just for information's sake, I went through the Verkle Tree concept. The promise of this is the proofs are compact compared to Patricia Trie. The proofs and intermediate nodes are constructed using certain polynomial functions (still not clear). So the drawback of this is, it takes a little more time to create and edit the Verkle Tree (with my basic understanding).

So, even if the Proof of Presence can be quicker than Sparse Merkle Tree, for other operations like Insertion, Deletion, etc., it might be heavier.

[litchipi]

Sorry I forgot yesterday to upload the presentation I did along with the benchmark results: smt.pdf

[damip]

After further study with Seb, there is a way to make the XOR secure against the algorithm we mentioned.
The paper states an attack complexity of O(2^'2sqrt(n)) where n is the number of bits of the hash.

So if we want a 128 bit security (the same as the one of 256bit hash collisions) we need to increase the hash size to n=4096bits which is 512 bytes. (that's a big hash !). This can be done with the blake3 crate using XOF extensions, see the "extended output" example in https://docs.rs/blake3/latest/blake3/#examples