Merkle Sum Tree Efficiency Improvement

[enricobottazzi]

The current logic of hashing inside the Merkle Sum Tree is based on DAPOL, paragraph 4.1.

In particular, each middle node stores an hash and a balance. The hash is equal to H(HLeftChild, BalanceLeftChild, HRightChild, BalanceRightChild), the balance is equal to BalanceLeftChild + BalanceRightChild

This is a fix to the original Maxwell tree in which the hash of a middle node is equal to H(BalanceLeftChild + BalanceRightChild, HLeftChild, HRightChild).

This Maxwell tree has a vulnerability described in Broken Proofs of Solvency in Blockchain Custodial Wallets and Exchanges, paragraph 4.1.. The exchange could set the balance of a middle node as Max(BalanceLeftChild, BalanceRightChild) therefore reducing its total liabilities.

When generating a Merkle Proof for a user, the Exchange could modify the balances of the sibling nodes on the fly such that the sum matches Max(BalanceLeftChild, BalanceRightChild).

This issue is possible because Alice h2. If she could open h2=h(10, Bob, idBob), she could tell that the v2 should be 10 and not 5. Unfortunately, in such architecture where each user is receiving a Merkle Proof, we don't want Alice to be able to open Bob's hash because this would reveal the identity and the balance of another user.

Differently, in the zk-based setting of Summa, each user is receiving a zk Proof of Inclusion in the Merkle Sum Tree. The prover knows all the information and is able to open each hash. Therefore, the CEX can build the Merkle Sum Tree using the "broken" Maxwell implementation and, when generating a proof of inclusion for Alice, enforce that the balance associated with a node is "included" in the hash. In that case, it would set the constraints such that:

• v2=10
• h2=H(v2, Bob, BobID)
• v6=12
• h6=H(v6, h3, h4)

With such constraints, the attack presented in the paper would be unfeasible.

If the exchange provides an Invalid Merkle Proof claiming that the balance associated with Leaf Node 2 is equal to 5, they won't be able to generate a valid zk proof of inclusion, as the circuit will enforce that the balance of Node 2 is equal to the balance used as preimage of the hash.

The same goes for the Middle Node 6.

The security of such design seems solid to me. In terms of performance:

• benefit of shorter hashing for building the tree, as for building middle nodes as the argument of the hash function go from 2 + 2*N_ASSETS to 2 + N_ASSETS

• benefit of shorter hashing for building the zk proof of inclusion, as for building middle nodes as the argument of the hash function go from 2 + 2*N_ASSETS to 2 + N_ASSETS

• cost for building the zk proof of inclusion, as more hashes have to be computed inside the circuit. In particular, it goes from N_LEVELS hashes to 2*N_LEVELS hashes to be performed inside the circuit

• Update benchmarks