Semi-serious: The State Oligarchy

@lithp wrote:

Kittenless, and statelessness in general, is relatively well defined, save for one very vague and unanswered section. Somehow, nodes need to fetch state!

There are a few categories of state fetch and stateless ethereum needs to be able to support them all:

  • Full nodes (and especially new miners) need to be able to fetch all the state
  • Stateless clients need to be able to fetch accounts, so they can prove the senders for the transactions they create.
  • Clients need to be able to fetch arbitrary accounts and storage items, so they can run eth_estimateGas.

There are two major approaches. The first is incentivized state retrieval, which hasn’t been very carefully explored but is widely considered a bit tricky. The second is putting all the data into some sort of DHT, which has the drawbacks that it’s vulnerable to sybil attacks, and that we’ll have to go to great lengths to ensure that leechers don’t bring down the network

I want to propose a third approach, which I argue provides the benefits of both with none of their drawbacks. Under this approach:

  • Very little research needs to be done to make sure it works, it could ship within months, leaving us plenty of time to focus on the tricky parts of stateless ethereum, such as the migration to a binary trie
  • Each second thousands of mobile clients could join and leech state and then quit without seeding any of it back to the network and this would be fine and not at all a concern.
  • Given some kind of bridge they can use to connect to the network the same applies to web browsers.
  • eth_call and eth_estimateGas not only work, but they run quickly. The only way a stateless clients could run eth_call faster would be if it became a full node, and even then it might not be able to compete.
  • DOS attacks against state retrieval are difficult to perform, and require facing off against teams of people who have strong incentives to make you fail. (This is as opposed to DHTs, where we have to consider all possible attacks beforehand and try to build in countermeasures. In the DHT approach there will be nobody in charge of stopping attacks while they’re happening. It’s a cat and mouse game with a blind mouse)
  • A very natural point is created which client developers can use to fund themselves

The idea behind the State Oligarchy is, let’s come up with a standard protocol which nodes can use to fetch state from state providers. The value of using a standard is that state providers which turn out to be evil can easily be replaced with alternatives. In order to retrieve state you send some eth to a state provider. This is part of the protocol, to get around the bootstrapping problem where you need to already be using the protocol in order to fetch the state required to send a transaction and opens a balance you can use to pay for future requests. There’s also a second bootstrapping problem here, you need eth in order to talk to a state provider, getting you some eth is something your client can do for you, and they might fund themselves by asking you for a donation during the process.

This solution is obviously a bit heretical, but I’ll argue there’s no technical reason why it won’t work. You might think there are returns to scale or some kind of centralization risk, but they’re no stronger than the returns to scale or centralization risk of mining pools! The big unanswered question is how payments work, we don’t want state retrieval to fall over when transaction fees rise, but that feels more easily solvable and coming up with a sybil-proof DHT.

Posts: 1

Participants: 1

Read full topic

Kittenless: A concrete proposal for stateless ethereum

@lithp wrote:

I think it’s been difficult to follow some of the conversations about stateless ethereum, because there are so many different proposals and it’s difficult to think about how they tie together. I hope that having a set of concrete named proposals will help with that. To that end, here’s a Least Ambitious Proposal, a Little Baby Stateless Ethereum, Kittenless:

  1. Stateless clients look just like full nodes today, except they do not download the state trie. In order to sync they must download the header chain and block bodies, as full nodes do today. (It’s not really “stateless”, it’s “less state”)

  2. In order to support stateless clients a new version of the eth protocol is launched, eth/66. Most messages are the same, but it does not have GetNodeData. State is fetched using a different mechanism, described below.

  3. When miners create a block they also create a witness for that block. The witness specifies a subtree of the state from the previous block. It contains every part of the state tree which is read from or written to by the transactions in the block. Block headers include an additional field, the hash of the witness.

  4. There’s a new block propagation rule, peers will only propagate blocks which are accompanied by a witness. (In the eth/66 subprotocol the NewBlock message includes a field which contains the witness)

  5. Transactions look almost exactly as they do today. However, nodes do not accept them unless they’re accompanied by a witness proving the sending account. An affordance for this is made in eth/66.

  6. Somehow, we migrate the account trie from the patricia tree to a binary trie. This will reduce witness sizes.

  7. Somehow, we merkelize contract bytecodes. Witnesses only include the parts of the bytecode which are actually touched. This also reduces witness sizes.

  8. We add a gas cost. Transactions must pay an amount proportional to the number of accounts and storage items and bytes of code they touch. This gas cost is set such that the witnesses are bounded to a reasonable size, at most 1MB?

  9. There’s a new subprotocol, state/1, which nodes can use to fetch chunks of state (Geth calls these tiles) from each other. Both full nodes and stateless clients use this protocol to fetch state, stateless clients just fetch less state.

  10. In the state/1 subprotocol each node advertises a list of chunks which they store, and the protocol provides a method of looking up which nodes store a given chunk. Nodes can request chunks from each other. All chunks are sent along with proofs which can be used to verify them. As blocks are added to the chain each node updates the chunks they store locally. The witness for each block is enough to update chunks. However, nodes must be careful to properly handle reorgs. A witness is not sufficient to undo changes to a chunk, when updating chunks the node must store some additional data it can later use to undo changes, if necessary.

  11. There is a social convention that nodes which have fetched a chunk must advertise it until they’ve served it to at least one other node. Full nodes will automatically follow this rule, they’ll always serve the entire state. Stateless clients might provide some kind of feedback to the user: “The current ratio of uploads to downloads is below 1, please continue running the node until the ratio is above 1”. Stateless clients will not support any features likely to break this invariant. Most notably:

  12. eth_call does not work unless you are running a full node, or your stateless client already has access to all the state necessary to service the request. Stateless clients do not attempt to fetch missing state from the network. eth_call is a fundamentally expensive operation and if you want to do it you should pay someone to do it for you.

  13. There’s a second social convention: When fetching state, nodes prioritize fetching state from stateless clients (which which aren’t advertising “I have everything”). This reduces the load on the full nodes, who are only asked to serve state which no stateless clients are serving.

You can see that even though I’ve called this “Least Ambitious” some of these bullets are still rather ambitious. Am I missing anything that would prevent this from working? Is there a way to simplify it even further?

Posts: 3

Participants: 2

Read full topic