A suggestion about updating the Merkle Tree by replacement instead of deletions & insertions

[Shymaa-Arafat]

I hesitated in discussing my idea here in Utreexo, but those words from one of the authors of "Merkle Trees Optimized for Stateless Clients in Bitcoin" encouraged me to.

.
Replacing old UTXOS with new one in place: an idea/suggested complexity reduction"
.
This is a suggestion that, I think, will introduce a significant complexity reduction in the process of adding/removing UTXOS from the proofs Merkle Tree...
.
Intuition/ Rationale:
Since any transaction somehow follows the Energy Law from the point that SUM of inputs = SUM of outputs, a lot of unnecessary overhead could be avoided if deletions & insertions happened simultaneously in a replacement manner.
.
Summary:
When processing a transaction, replace the old TXOs that became input with the new ones; ie if they're the same number there will be no actual deletions/a and thus no tree swaps.. just modify the corresponding values& hashes along the proof path.
-If one old TXO led to more than one change the value of the old leaf node to be the root of a corresponding subtree of the new TXOs.

-Only if n1 inputs created n2 outputs where n1>n2 u will have to choose (n1-n2) leaves to delete according to some criteria/heuristics
-Then deletions will this way definitely happen much less often, and a suitable heuristic could be thought of later according to some data analysis of existing blocks.
.
Examples:
I traced some inputs and outputs in 2 consecutive blocks Block 1973321,1973322 from the site:
https://blockstream.info/testnet/block/000000000000001eedf8cd0e358a0ca6144e82f5c3da263769f7ad208b8e07ba

You will find that
57.64177548 tBTC=⟩
0.01322037 tBTC

• 57.62838604 tBTC
  
  
  Then in the next block
  57.62838604 tBTC=⟩
  57.61015944 tBTC
• 0.01322037 tBTC
  
  

-So, in my method a subtree evolves in place of the original leaf that represented the UTXO 57.64177548 tBTC, and no other branch of the tree get modified.
.
-If u traced a number of blocks u'll find that the situation where the number of inputs n1 is larger than the number of outputs n2 (n1›n2) is a very rare event. Even if it is not, we still guaranteed to have less deletions
.
(More details & discussions
https://bitcointalk.org/index.php?topic=5334763.0)
.
I think it would be better to test this idea starting with a regular Merkle first to exclude the correlated effect of other enhancements, then with a Utreexo forest maybe, but I think with no cache at first?

[Shymaa-Arafat]

As a flow of thoughts when I was thinking that this approach could help tracing how certain amount of cryptocurrency got spent by putting them in the same Merkle subtree, I connected that thought to:
1- a research direction I haven't get into before about "transaction graphs", if u observe this figure

From the paper
"Do Bitcoin Users Really Care About Anonymity?
An Analysis of the Bitcoin Transaction Graph"
Anil Gaihre, Yan Luo, Hang Liu
, University of Massachusetts Lowell

I noticed that these r the different cases I have to deal with in my replacement algorithm.
.
2-In reading the paper, I read about "address reuse", when a company or marchant use the same public key more than once.
https://en.bitcoin.it/wiki/Address_reuse

Address reuse refers to the use of the same address for multiple transactions. It is an unintended practice, abusing the privacy and security of the participants of the transactions as well as future holders of their value.

3-Connecting this to Andrew Miller response about my idea

This works if the UTXO set is not key ordered like a binary search tree right? I haven't been following the non-BST approaches as well mentioned on that thread
.

»»»The point is if it's bad to use the same public key, I don't think it's bad for the Merkle Tree branches structure, ie we can have an idea (predict how the tree will look like) from those days Merkle Trees when the same address were reused and the tree was BST indexed on the key
...
to be continued...
.
-In other words, if in 2013 Merkle Trees were BST based on the public key & public keys were allowed to be used more than once for the remaining value, then in that time(I think) the delete then insert of the same key will reach a similar tree like the one I am suggesting now (only maybe they would do it in two steps instead of one).
-and the fact that address reuse was found to be a bad idea doesn't mean that the resulting tree structure is also as bad.

[kcalvinalvin]

Yes the idea of doing additions and deletions at the same time has been floating around. While it can work, we're not looking to go in that direction at the moment as hashing is not the bottleneck, bandwidth is.

In this picture, you'll notice that there's vertical stripes in many places. These are where the new leaves get placed. But as they are deleted, it gets replaced by a new leaf. This causes an increase in proof sizes and Tadge has detailed an accumulator design where we can avoid this problem. #249 (comment)

While the design where additions and deletions happen at the same time would help a bit, hash savings would be limited and wouldn't help with the real bottleneck, the proof size. Maybe later down the road when proof sizes are less of a concern, we could visit this idea again but for now, we likely won't be heading this way.

[Shymaa-Arafat]

Neglecting the effect on the proof size (which depends on the tree height)at least for now, I think replacement reduces the size/amount of "change" in proofs. When less branches r modified, less internal nodes change their concatenated hashes. This could be helpful, especially when u r caching some of them.
.
For example in the run results we were discussing, the numbers suggest an av of +9 (165251/180000) insertions, 6-7 deletions per block (surely this is a small test data), resulting in 2-3 increase in the no of UTXOs per block.
When inserting then deleting u change 15-17 branches along with the corresponding internal nodes hashes, while if u modified when possible u only mess with 9-10 branches.
Anyways, I'm not trying to convince u to go in this direction, I'm just brainstorming and hearing different opinions.