Thank you Dankrad! I hope it is relevant to clarify here (below your post) the setting in which these polycommit-based authenticated data structures need to operate in. If not, we can move this conversation somewhere else.
This should work for simple transactions that just transfer ETH from A to B, but what about transactions that trigger smart contract (SC) executions?
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.
I presume what happens instead is the user sends the transaction without the reads to a block proposer who is either stateful or can contact the state provider to get state and proofs. However, since I assume block proposers should be fast (e.g., non-interactive), it might be too slow to have to ask state providers over the network for state + proofs, no?
Right, but this takes O(n\log{n}) time to compute “on the fly,” given a set of m evaluation points for a polynomial \phi(X) of degree-bound n.
I assume you’d want instead to aggregate multiple, precomputed constant-sized proofs on \phi(X) into a constant-sized multi-reveal proof, as Vitalik proposed.
You can use aggregation to lower bandwidth for the writes w\in W-R mentioned before. e.g., given two writes w_1 and w_2 you can aggregate their proofs on p_i. You still need as many proofs as the # of polynomials, I think. But this is better than |W|\times number of polynomials. There’s still an overhead for sending the evaluations of the polynomials (e.g., 0 or \mathsf{hash}(k',v')), I think.
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?