A simulation of a new approach to sharding that allows executing transactions as if the underlying protocol was not sharded (i.e. atomically, with serializability).

Inspiration

Ethereum 2 is close to launching its data availability layer. The current plan is to use it to run a multitude of optimistic and zk-Rollups to get linear scalability. While each rollup internally is fully atomic, and runs transactions serially, communication across rollups is asynchronous. This will lead to either congregation of all the services and liquidity on one rollup, or in liquidity being spread across all the rollups.

In the former case the system will not take advantage of the linear scalability Eth2 can offer, in the latter it will not take full advantage of the available liquidity.

Here we present a different approach, called Cytonic, in which the underlying execution and storage layer is sharded, but the transactions are executed atomically with serializability.

What it does

The demo we've built simulates a system with some large-ish number of shards that "executes" a large number transactions, that collectively touch heavily-intersecting set of data. In Cytonic data shards, execution shards and mempool shards are separate from each other. In each block it finds some assignment of the transactions in the mempool to execution shards in such a way that it (a) guarantees that no two execution shards are touching the same data, (b) the number of data transfers is minimized, and (c) the number of transactions executed is as large as possible given a and b.

We tried out several approaches for computing such an assignment in the last 48 hours, and are presenting one of them.

How we built it

We wrote a simulation of somewhat-realistic workload, with various data pieces having power law distribution of how frequently they are accessed (i.e. hypothetical Uniswap is accessed more frequently, than the account of some person back in my hometown).

We then built an assignment algorithm that given such a workload, and a mapping from pieces of data to data shards computes some assignment of transactions to execution shards that would maximize the number of txs executed under the constraints described above.

Finally, we've built a visualizer that shows in real time the assignment of transactions between mempool and execution shards, and the data transfer between execution and data shards.

Challenges we ran into

To build a realistic workload, we needed to extract from Ethereum mainnet the information on how much of an intersection in terms of touching the same pieces of data transactions on Ethereum have. Thus turned out to be quite hard. It is relatively easy to see the intersection on the granularity of accounts (and contracts) touched, but not on the granularity of the actual pieces of data they touch.

Accomplishments that we're proud of

The main accomplishment is the actual assignment algorithm. Provided that the data pieces the transactions are trying to read heavily intersect, most assignment algorithms end up either discarding too many transactions, or assigning more to a single shard that the shard can handle. We tried out close to a dozen of different approaches with different parametrization. The one we finally found is rather promising, though likely it can still be improved significantly.

What we learned

Coming back the the challenge described two paragraphs ago, we talked here at the hackathon (and associated events) with several founders of various projects in the ecosystem and learned that with higher scalability and cheaper gas price there's demand for significantly more cross-contract interactions. There are projects that would love to be able to read data from dozens of various sources on chain to make decisions. We haven't incorporated those findings to our workload (given they were not quantifiable), but this provides an important requirement for systems like Cytonic: it is not sufficient to build something good enough for the current usage patterns. With higher scalability the usage patters will change.

What's next for Cytonic

Cytonic can be built on top of any protocol that provides data availability and supports smart contract, such as Ethereum 2.

We plan to build the actual production version of Cytonic.

Built With

  • ethereum
Share this project:

Updates