State-minimised executions

What confirms unconfirmed virtual state roots? Some passage of time without successful challenges?

In the proposed scheme, yes.

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.

Without a random rotation of executors, what is to stop them from being bribed?

what is to stop them from being bribed?

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.

Impressed with some of your constructions, very creative!

See above posts please :slight_smile:

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.

1 Like

Ah, I hadn’t seen that before- neat solution. I wonder if it could be made non-interactive.

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”).

Can we walk through how this would work with an actual contract C’?

Say I have a Token Contract that initializes my virtual root to give the owner the balance 1000000 tokens (see code here Block Persistent Storage for a general ref, I’m actually calculating the roots on each transfer, but with this proposal, we’re going to get rid of that).

So between collations I sent one address 700000 tokens and another address 700000 tokens. We end up with two logs of type TRANSFER 0xTHEM 700000.

Now I only have 1,000,000 so how do the validators handle this? The first virtual transaction passes and the second fails?

Question 1: How do they actually calculate that this second virtual transaction should fail? My contract doesn’t have access to storage so I can’t compare my balance. In the linked code I require a proof of current balance, but I won’t have that for transaction 2.
Question 2: How do I find out that transaction 2 failed?
Question 3: If someone sends me back 250,000 later, what is there to keep someone from ‘replaying’ my transaction 2 and spending my 700,000 and leaving me with 50,000.

I think it’s possible if it’s non-interactive to a degree… the final poof is non-interactive, although data must be shared with others beforehand.

The first virtual transaction passes and the second fails?

Yep!

In the linked code I require a proof of current balance, but I won’t have that for transaction 2.

For transaction 2 to be valid it would need to have a proof based on the post-state of transaction 1.

Question 2: How do I find out that transaction 2 failed?

Probably though some receipt mechanism, or by simply scanning the chain.

Question 3: If someone sends me back 250,000 later, what is there to keep someone from ‘replaying’ my transaction 2 and spending my 700,000 and leaving me with 50,000.

Note that this is already possible in the current ethereum. If you want it not to be possible, perhaps require transactions to have timeouts.

This question was asked higher up in this thread (see here). One approach is to build a parallel (“virtual”) accumulator (e.g. a trie) for the transactions that have not executed as no-ops. With it you can then build “proofs of execution” or “proofs of no-op”.

What is in place to keep us from doing this with the current EVM + Collators?

Say we write new contracts where each state-changing function has a corresponding virtual function that is view only. The state changing function does not do any work and only emits an OpLog requesting that a transaction should be performed. It is provided with a data hash and some funds for extra-gas and stake.

Collators see the OpLog and download the data from the datahash(say from IPFS or from some libp2p chatter network). This DataHash contains all the witnesses needed to execute the function ‘for real’, but it doesn’t get executed on the chain. Instead, the collator executes the view only function in whatever off chain client they like. This means we are not limited by max block gas limit. This makes high-cost transactions like snarks or massive air drops much more feasible(if you can get a collator willing to do the collation).

This virtual function does emit data logs(adds and dels) to the collator according to the contract. These logs don’t get appended to the EVM because this is a view function. These logs will be included in the resulting collation. The collator does this for as many OpLogs as it has found in the current time period. Becuase this is an external program it can keep track of short-term hash swaps for witnesses updates such that items can continue to be processed across collations.

Finally, it produces a collation log root that goes into our log accumulator and also updates an Op Patricia Tree with a hash of the OpLog so that we can later prove that this OpLog has already been processed. The collator is also responsible for producing the witnesses for the Datalogs and the proofs for the Op Tree and puts them somewhere they can be retrieved.

These two items are the inputs for proposing a collation. The collation can be challenged with a log proof showing that an add witness was used that already had a del witness invalidating it. A collation can also be challenged with an Op proof that shows the collator submitted an Op that had already been processed. If the collation is invalidated they have to start over or someone else has a turn.

There is some sort of confirmation(Maybe Truebit style challenge game based on random EVM stack challenges, or maybe a form of Casper, or maybe the proofs are enough). Once the collation is committed users can download all the relevant witnesses. We may have a proof of publication problem here, but that may be easily solvable by making the confirmers reassemble a hidden hash. Recommendations on confirmation encouraged.

If the confirmation is successful then the collator and set of confirmers split up the extra-gas provided in the initial transaction.

What major items am I missing?

I do still have concerns that I can’t prove that a value is 0. We may have to have some kind of special witness type for this, but it seems that it might be easy to exploit if someone isn’t paying attention to the whole history.

Which brings me to the question of why not use a Patrica Tree? The tradeoff is that the witnesses need to constantly be updated instead of being updated just once, but if we are using an external program to do that then we should be able to process and publish the hash swaps that need to occur. This table would be a new data set that users would need to sync with to update their witnesses. I have no frame of reference as to what the data size would end up being here, but most of this can all be kept in off EVM storage and queried as needed. If the ‘swaps’ computation gives you an invalid collation buffer then you did something wrong.

I haven’t run this path all the way out yet but I think you could also have contracts that track cross-shard collations as well such that the witnesses from those shards are easy to check. Maybe update the witness inputs to be (networkid,add/del/null,nonce,path,value) or maybe have the network ID be part of the path.

Any and all feedback encouraged. Here is a diagram of the process for discussion. I’d love to spend more time running down this rabbit hole and building out the contracts and collator software, so feel free to point me in the right direction.

Perhaps we should change the terminology from stateless clients to state-minimized clients. We don’t want to offload all of the state into secondary markets, but give people a choice between storage rent on the blockchain and secondary markets.

This is a much better term.

1 Like