The Stateless Client Concept

Sharding
15

How would this new stateless transition function work if the structure of the tree changes? (i.e. an account is created)

For example, let’s say D is sending some ETH to a new account, H which falls between F and G. The proof for F’s balance consists of [D, hash(E), hash(C)], but to add H, we would also need hash(F) to find the new Merkle root. Would the transaction witness also include Merkle branches where the new account would be inserted?

      A
    /   \
   B     C
  / \   / \
 D   E F   G

        K
       / \
      J   \
    /   \  \
   B     I  \
  / \   / \  \
 D   E F   H  G

Worst case - if you were inserting an account in the middle of the tree, you’d need half of the state to find the new state root. (inserting between E and F, you would need hash(F) and hash(G))

EDIT: I believe this is solved by using accumulators instead of merkle trees: Accumulators, scalability of UTXO blockchains, and data availability