TLDR: We detail a cryptoeconomic mechanism for EMV executions with sublinear use of the state trie. It is an alternative to cryptoeconomic accumulators with the benefit that users do not need to post collateral, and only have to push logs (the cheapest kind of onchain activity).
Construction
Given a “normal” stateful contract C we construct a state-minimised equivalent contract C’. The contract C’ has a “virtual state” maintained as follows:
The contract stores a single confirmed virtual state root at a corresponding collation height.
Users can push logs of the form [LOG T], called “virtual transactions”. (Log shards are an ideal substrate for such logs, providing cheap log ordering, friendly witnesses, and real-time data availability.)
Virtual state transitions for C’ given a virtual transaction [LOG T] happen like state transitions for C given a transaction T.
Collaterised “executors” can suggest unconfirmed virtual state roots at more recent collation heights than the current confirmed virtual state.
Whistleblowers can challenge unconfirmed virtual state roots and engage in a TrueBit-style protocol with executors.
Whistleblowers earn a share of the collateral of adversarial executors.
Non-adversarial executors advance the virtual state root and are rewarded with an internal fee system that mimics coinbase rewards and/or gas.
Conclusion
The construction takes the traditional notion of a transaction and decouples data availability (via logs on log shards) and validity (via TrueBit-style cryptoeconomic execution). The end result is a state-minimised execution protocol where the cost of validation is pushed away from (onchain) validators onto (offchain) executors.
Note also that transactions corresponding to virtual transactions can assume a stateful model for executors (as opposed to a stateless model), so virtual transactions do not need to includes witnesses. In such a setup users get both short transactions (improving upon the standard stateless model) and cheap transactions with logs (improving upon standard execution).
A virtual transaction of C' (a log) was executed successfully when the collation/block height corresponding to the confirmed virtual state root is greater than the height of the collation/block containing the virtual transaction.
How can the contract be certain it’s transaction has actually been included in latest virtual state of C’, as opposed to simply being ignored due to invalidity?
I see—How does one distinguish no-ops from transactions that actually change state? One idea is to require that the virtual state root be accompanied by a transaction trie root (similar to today’s Ethereum block headers). Then it’s just a matter of asking an executor for a membership or non-membership witness for the transaction in the transaction trie.
An alternative scheme is to confirm unconfirmed virtual state roots with SNARKs/STARKs. That would have the advantage that the “passage of time without successful challenges” part can be skipped.
This has been a fantastic series, I’ve followed closely for the most part but having difficulty with this one.
How do the executors work here?
If executors are stateful then aren’t we back to the same problems that motivate stateless clients (e.g. rotation of executors among shards when each shard state is huge/ever-increasing)?
I really like the idea of a “virtual state root”, though I also imagine the shard executors being stateless, either the standard merkle trie and witnesses, or (much butter imo) via cryptoeconomic accumulators. It sounds like the virtual state serves to reassign the job of state maintenance from validators to a new role (executors). Then virtual state is an additional gadget to combine with a cryptoeconomic accumulator, rather than an alternative to replace it. I’ll try to explain the Construction as I understand it, glossing over blanks or filling them with best guesses.
Old model: Validators read the stream of transactions, and execute them by reading current state from a state root (and witnesses, in a stateless client). In other words, Validators do everything, including calculate the state roots. The Collation body has a transaction list and witness list. The witnesses are rather large, supplying leaves for all accessed state.
New model: Validators only read the stream of transactions (“virtual transactions”), in the form of an ordered list of logs and log witnesses and a log accumulator (hand-wave). Validators normally do not execute transactions and do not calculate state roots, but they do write the state roots that are submitted by executors (“virtual state roots”). Executors execute transactions; they read the current state (from witnesses if stateless), calculate the new state root, and submit it to the Validators. When an adversarial Executor submits an incorrect state root, a whistleblower initiates a challenge, which is then adjudicated by the Validators. During the challenge, Executors provide the state reads (i.e. witnesses for state roots, including intermediate state roots) to the Validators. After the challenge period has passed, the state root becomes finalized/confirmed. Under normal periods (with no challenges), collation bodies are much smaller as they only contain virtual transaction logs and not the witnesses for accessed state.
So in the new model, Validators only validate the data availability of transaction logs (under normal periods without challenges). The job of transaction execution is shifted to Executors.
Good guesses or wrong? Reemphasizing my first question, it makes sense that “virtual transactions” (ordered list of logs) don’t need witnesses because Validators don’t (normally) execute them. But the choice of stateful or stateless Executors seems orthogonal to the virtual state of a Validator. With Executors that maintain the full state, then users get short transactions (i.e. tx’s without witnesses). But that’s not improving the stateless model, its just reversing the stateless vs stateful tradeoff (bigger tx’s vs pain of an ever-growing state).
Your descriptions of the “Old model” and “New model” are good! A couple things I probably should have made more explicit:
The scheme comes in two flavours, with either stateless executors or stateful executors. In either case, validators do not have to execute transactions (other than for adjudication) so there is a gas/CPU saving there. In case the executors are stateful then there is the extra saving that the logs do not have to include witnesses, and so the logs are considerably smaller (maybe around ~5x smaller).
The scheme is “configurably local”. That is, it can apply to a single contract, to a group of contracts within a single shard, or to a group of contracts across several shards, but not to whole shards. So the job of an executor (to validate transactions, and optionally maintain state in the stateful flavour) is local. Contrast that to the job of validators, which is global across all contracts and shards.
If executors are stateful then aren’t we back to the same problems that motivate stateless clients (e.g. rotation of executors among shards when each shard state is huge/ever-increasing)?
As noted above, the scheme is local. So an executor for a specific application will not rotate among shards. Instead, it will continuously follow the specific shards it is interested in, and filter the logs for only the relevant contracts it has to execute. Stateful executors need to have the setup to deal with the ever-growing state of a particular application, but this shouldn’t be a problem as the state growth is segregated to that single application.
In theory we could enshrine the scheme at the shard protocol level. In this case executors would still be local to a given shard and would not have to rotate among shards.
The only thing executors do is suggest virtual state roots. What kind of bribing attack are you thinking about? Let’s see:
They could maybe be bribed to not suggest virtual state roots (for slower finality) but this is an open-access model where anyone can become an executor and there are rewards for suggesting virtual state roots (and these rewards grow with the amount of unexecuted logs).
They could maybe be bribed to suggest invalid state roots (consensus attack) but they stand to lose their entire collateral (anyone can be a whistleblower). Because state roots shown invalid are disregarded, I don’t see any clear benefit for the briber beyond the above bribe (itself not useful).
I was mainly thinking about the data availability problem. What is to stop an attacker (large group of validators, together with some normal users and a large group of executors) from creating a state root with all but one transaction valid, but withholding the transactions to create that root from the rest of the network.
Won’t challenging these transactions be very difficult (entailing that the prover send all blocks in the chain to some independent authority)? Whistleblowers would be hard pressed to find the actual transaction that is invalid, if it indeed exists.
The state-minimised application defines where the logs need to be pushed. A natural choice is simply to push logs in the same shard where the state-minimised application lives, which at a minimum has real-time data availability. As mentioned in the original post, a separate log shard would be an alternative substrate for such logs, providing cheap log ordering and real-time data availability.
The adjudication process only accepts as evidence logs from the log source specified in the state-minimised application. Both (stateful) shards and log shards benefit from real-time data availability, so withholding logs is not an option. Put another way, withheld logs are irrelevant by construction because they necessarily haven’t been pushed onchain. Anyone who wants to be a whistleblower has the opportunity to download all the relevant logs.
This is indeed why data availability is hard. @MaxC, have you seen this post https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding yet? It’s about erasure-coding blocks to turn a “100% availability” problem into a “50% availability” problem, which then can be probabilistically checked, plus some fraud proof mechanisms to ensure the erasure coding is correct.
You can with STARKs - just attack a STARK proving that the erasure code was constructed correctly, and then any client can probabilistically check availability just by randomly sampling a few chunks.
Unless by “non-interactive” you mean “a single proof that convinces everyone”, in which case the answer is no because the block proposer could publish just the proof without ever publishing any of the other data, and the single proof would not have enough data to reconstruct the block. Notice that this argument also applies if there is only one client in the network; so the availability check mechanism relies on at least some minimum number of other (honest) clients existing on the network, though this is an absolute number (eg. “1750 honest clients”), not a percentage (eg. “10% of clients must be honest”).
