Multi-layer hashmaps for state storage

[dankrad]

@alinush

Seems like the user making the transaction must know the “reads” of the SC in order to ask the state provider for proofs. This implies the user must execute the contract locally himself to get those “reads”, which might defeat the point of Ethereum to some extent.

There is a substantial discussion around this problem at the moment on DSA (dynamic state access) vs. SSA (static or predictable state access) (see here: A Short History and a Way Forward for Phase 2). In the SSA paradigm, it would actually be completely predictable which storage locations need to be read, and therefore it would be possible that the user only needs one query to get all the data as well as proofs. In the DSA world, that would become a bit more complex. However, it turns out that the SSA world is probably universal and all contracts can be mapped into it. So we probably aren’t losing that much.

@alinush

Right, but this takes O(nlogn)O(n\log{n}) time to compute “on the fly,” given a set of mm evaluation points for a polynomial ϕ(X)\phi(X) of degree-bound nn .

I assume you’d want instead to aggregate multiple, precomputed constant-sized proofs on ϕ(X)\phi(X) into a constant-sized multi-reveal proof, as Vitalik proposed.

You can use aggregation to lower bandwidth for the writes w∈W−Rw\in W-R mentioned before. e.g., given two writes w1w_1 and w2w_2 you can aggregate their proofs on pip_i . You still need as many proofs as the # of polynomials, I think. But this is better than |W|×|W|\times number of polynomials. There’s still an overhead for sending the evaluations of the polynomials (e.g., 0 or hash(k′,v′)\mathsf{hash}(k’,v’) ), I think.

I am a bit confused on what your point is here. The idea would be that at any given block height, one state provider computes the proofs for all storage locations (this can be done in O(n \log n) group operations using this scheme: GitHub - khovratovich/Kate). Then any user can query the locations relevant for their transactions and get the data+proofs from the state provider.

@alinush

But this is not ideal for sharding, where nodes switch to different shards and would need to re-download that shard’s state before being able to propose?

It is important that attesters can quickly switch between shards for security and load reasons. The same isn’t necessarily true for proposers: It would be ok to select a small number of proposers who stay on one shard for a long time, e.g. one day. This does not compromise security.