Multi-layer hashmaps for state storage

[dankrad]

@alinush

This means for each such ww , say with key kk and value vv , the auxiliary information needs to have non-membership proofs w.r.t. dn−1d_{n-1} for kk not being in all other pj,j≠ip_j, j\ne i (as described in my earlier comment).

Is my understanding correct?

Yes.

@alinush

Also, who in the Ethereum ecosystem would be responsible for computing and updating proofs as the data structure is updated?

This is a good question. It would likely be a “state provider” role that needs to be established. The state provider could be queried by individuals when making transactions and will give them the witnesses. Using the multireveal scheme in Hashmap-based polynomial commitments for state would allow constructing the multireveal from the individual proofs.
Another possibility would be to require block proposers to hold state, so that they are able to construct proofs. This avoids problems with constantly updating witnesses.