Simple synchronous cross-shard transaction protocol

[cdetrio]

@vbuterin

Once concern with synchronous cross-shard tx’s in a delayed state execution model is that the state execution gadget (which is not a consensus game) won’t be able to keep up with block proposals/finalization (the consensus game at the data layer)

Why wouldn’t it? As long as you design it so that each level of state execution only takes at most 1-2 rounds of network latency plus the usual ~200ms of execution, then it should be well within bounds.

Right, so the concern is about designs where state execution might take more than 1-2 rounds of network latency (like with high towers of dependent tx’s).

@vbuterin

It will be progress to recognize that we have a protocol that works, even if it is low throughput.

In that case, why not go with my protocol, that allows for one cross-shard transaction per block per account? Forcing participants to sometimes try sending the transaction several times before it succeeds would only increase de-facto fees by maybe a factor of ~2 due to the redundancy, much less than if there was only one transaction of cross-shard block space per shard.

A question about your protocol, is the purpose of the block structure containing the Merkle tree (mapping address => tx with each tx bundle [shard[1], address[1], shard[2], address[2] ... shard[n], address[n], data]) to make it easy for shards to verify that each account is only affected by one cross-shard tx in a slot (i.e. only affected by one cross-shard tx at some block height across all shards)?

This brings to mind the other major concern with synchronous cross-shard tx’s (particularly under delayed state execution): what prevents block proposers from stuffing the blocks with invalid tx’s (i.e. tx’s that don’t pay gas)? You say:

if the transaction specifies [A, 123, A, 485, B, 769, data] , then for data to get executed the transaction must appear at position 123 of block N in shard A, position 485 of block N in shard A and position 769 of block N in shard B.

But the validator on shard A is proposing shard-A-block-N without checking against shard-B-block-N, right? (perhaps shard-B-block-N has not even been proposed yet, as both shards are still on the same height N). If the tx doesn’t appear in shard-B-block-N position 769 (btw, not clear why its included twice at two different positions in shard A), then data is not executed. So the concern is what prevents validators from stuffing blocks with transactions where data is not executed, or is it not a problem if shard blocks are stuffed with invalid tx’s?