Ethereum Scalability and Kleros
Our Director of Research, Dr. William George goes on an in-depth investigation into different scaling solutions for Kleros, as well as the Ethereum ecosystem as a whole.
Ethereum gas prices have risen dramatically in these past months, which has affected many projects, including Kleros.
On some level, the high costs of gas are just the result of a wide interest in using Ethereum, which represents increased demand for limited space in blocks. As Kleros is particularly well-positioned to offer resolution to disputes that arise natively on Ethereum one might see high gas prices as a sign that there are that many more opportunities for situations where Kleros can be applied.
Nonetheless, Kleros is designed to be a general dispute resolution platform, particularly aimed at disputes poorly handled by existing systems. Some of the proposals for using Kleros involve large financial amounts. However, many of the cases we seek to address target small disputes that do not make sense to take before the existing court system or traditional arbitration. For small disputes, for example a freelancing dispute over a few hundred dollars or content moderation on a decentralized platform (such as disputes in the style of those that arise as part of our Storytelling campaign), it can make a big impact on the viability of using Kleros if gas costs to trigger the dispute or for jurors to vote rise from a few cents to a few dollars.
To some degree, that Ethereum would need to evolve in order to scale to meet increases in its usage has been known for a long time. Ultimately, while the current structure of blockchains like Ethereum, in which nodes process every transaction, offers a great deal of decentralization, this structure provides challenges in terms of how many transactions the network can support. With the technology that existed at the time of release of Ethereum, a network had to accept a trilemma of tradeoffs between decentralization, scalability, and consistency.
Kleros benefits from the decentralization of being on a blockchain by offering automatic execution of awards as well as having completely transparent processes for juror selection, all without requiring trusted third parties. However, in order for Kleros to be effective in the range of use cases that we hope to apply it to, the trilemma above needs to be at least partially resolved so that the blockchain that underlies Kleros offers more scale (while still offering consistency and decentralization).
Fortunately, a great deal of progress has been made in this direction, building off years of research by the Ethereum Foundation and others. In this article we will survey some of the developments in the efforts of various projects to make Ethereum more scalable, with a particular emphasis on their potential effects on Kleros.
Of course, the most fundamental aspect of the upcoming scaling landscape is the eventual transition to Eth 2.0. The basic idea on how Eth 2.0 should make Ethereum more scalable compared to the status quo is that not all participants to the consensus algorithm will have to validate all transactions. Instead, the network will be split into shards. Validators will be periodically randomly assigned a shard and a transaction need only be validated on its own shard.
In more detail, the transition to Eth 2.0 is planned to take place in several stages some of which with have more impact on scaling than others.
To summarize the planned stages of the Eth 2.0 deployment :
- Phase 0. The launch of the "beacon chain". This is a core element of the new consensus algorithm. This is where eventually validators for the different shards will be determined. The beacon chain will eventually also enable cross-shard communication. Ethereum as it exists will continue to run in parallel and one will not have particular scaling advantages at this stage.
- Phase 1. At this point, shards will exist; however, they will not have the logic of full smart contract platforms. Nevertheless, one will be able to post data in these shards in a way that will increase the capacity of transactions that are used for "data availability", see the discussion of rollups below.
- Phase 1.5. Here the current state of Ethereum will be inserted into this system as a distinguished shard (while the other shards will still only be capable of holding data without smart contract logic). At this point, Ethereum will be using the new proof-of-stake consensus protocol of Eth 2.0, even if shards will still not be capable of smart contract logic.
- Phase 2. Finally, shards will be capable of executing general purpose smart contracts, and one should be able to take full advantage of the increased capacity of sharding.
Phase 2 is still being actively researched. However, already, the community is preparing for phase 0 with the multi-client Medalla testnet. Phase 1 is planned to go live about one year after phase 0.
Now we will probe a bit deeper into how aspects of the new structure of Eth 2.0 may affect Kleros.
A set of concerns surrounding Eth 2.0 consider how cross-shard communication will operate, and what effect this will have on the ability of Dapps to operate across shards, particularly synchronously.
Eventually, we envisage that the Kleros court will probably live on a single shard. However, different arbitrable applications may be on other shards. Indeed, Kleros is designed so that it can be widely integrated into different Dapps so that it can resolve disputes arising from across the ecosystem. It already takes a non-negligible amount of time for jurors to rule on cases in Kleros. (This is typically measured in days so that jurors can comfortably participate from anywhere in the world; though there are some proposals that would have shorter turnarounds.) Hence, issues arising from lack of synchronicity as decisions are transmitted from one shard to another are not likely to significantly impact Kleros.
Random Number Generation
As of phase 1.5, when Ethereum as we know it becomes one of the shards of Eth 2.0, the new proof-of-stake consensus algorithm will be fully in effect. For Kleros, one needs to be particularly attentive to how this transition changes Ethereum's mechanism for generating random numbers.
Using a good pseudo-random number generators when choosing panels of jurors in Kleros is fundamental to knowing that the panel is not being manipulated by some attacker. Currently, Kleros uses Ethereum blockhashes for this.
Generally, one should judge security against manipulation (for random number generation and in general) according to a framework where you ask who can manipulate the system, and how much does it cost them. Currently, miners can manipulate by "rerolling" if they are willing to give up a block reward. This block reward is 2 ETH plus any gas fees in that block, which is a significant price for a miner to pay for a chance to redraw a jury in a Kleros case in the hopes that the new jury will be slightly more favorable.
The future Eth 2.0 random number generator will be based on a RANDAO type system. Here block producers reveal a pseudo-random value, given as the signature (under the BLS signature scheme) of data that they must validate in order to participate. Hence, again the choice for a block producer is to participate or not in a given slot, so she only controls "one bit of manipulation".
However, the cost of that one bit of manipulation seems like it will be reduced compared to the status quo. Eth 2.0 is planned to be calibrated (you can read more about it here and here) so that the total reward per epoch (6.4 minutes) will be roughly 1.2 ETH. That reward is then split between the participants/the block producers in that epoch, so a given "reroll" only costs a fraction of that. This all makes sense considering that validators will not need to be incentivized to take on mining electricity costs. Moreover, to the degree that Eth 2.0 will use its own random number generation to shuffle the roles for which validators participate in a given epoch, considering the size of the panels of validators that are selected, any control that current block producers have in being able to bias the next set of validators will be very limited. Nonetheless, for us continuing to use this random number generator would mean a somewhat lower cost for block producers trying to bias Kleros juror selection than before. So this is something for one to keep an eye on. For the long term, we intend to continue research on using RNGs based on verified delay functions (VDF).
Another approach to provide better scaling to Ethereum makes use of "Layer 2" solutions. Here to get around the bottleneck that classically all Ethereum transactions are executed by all nodes, Layer 2 platforms allow for transactions to usually take place off-chain. Namely, users can interact with contracts deployed on a given Layer 2 platform, issuing transactions which alter state as seen by the consensus mechanism of this off-chain platform.
Then users would normally only need to issue on-chain transactions that have to be validated by nodes when some information about the state of this contract is needed on-chain. For example, on-chain transactions would be necessary when a user withdraws funds or when a Kleros court that lives on a Layer 2 platform needs to return a verdict to a contract that lives on-chain. Then a variety of techniques are considered for how to obtain the security guarantees of the main chain for these transactions while having to make a minimal number of on-chain computations.
In the space of these ideas, a variety of design choices are frequently considered. The first question is how the main chain can know information being reported back to it about the state of a contract on Layer 2 is valid (without having to revalidate the state itself, defeating the point).
Fraud Proof based Layer 2 and Optimistic Rollups
A popular approach is to use "fraud proofs". Here the idea is that someone can submit a claim on the main chain, generally along with a deposit, for what the state should be, and this can be challenged by other participants who submit a fraud proof, showing the original claim was incorrect. Then these solutions are generally engineered so that the EVM can check the fraud proof, to determine whether the original claim was indeed incorrect, in a relatively small number of steps. Note that this process generally requires a long withdrawal period (e.g. typically of > several days) in order to give people time to flag and challenge malicious transactions.
An issue that plagued early attempts at Layer 2 solutions was the "Data Availability Problem". When generating a fraud proof, a user would typically need information about other transactions that were issued on the Layer 2 platform. For example, if the Layer 2 platform commits to transactions which are included as updating its state with the root of a Merkle tree on-chain, then a user might need a Merkle branch to show that her transaction was actually included in the state of the Layer 2 platform. However, if this Merkle branch is not available, a malicious party may be able to issue a claim on-chain that honest users won't be able to challenge.
To solve this issue, many more recent Layer 2 proposals have adapted by including the data necessary to reconstruct the off-chain state on-chain. A Layer 2 structure that includes data in this way is called a rollup, and specifically a rollup that is based on fraud proofs is called an Optimistic Rollup.
At first glance, this might seem to defeat the point of Layer 2, as Ethereum nodes will still need to process all of this data. However, gas prices are structured that including the information that makes up an off-chain transaction as "call data" on-chain, without applying any logic to it or requiring that it be kept in state, is substantially cheaper than if one had made the same transaction on-chain. Ultimately, this reflects the fact that the resources being required of nodes to check that a block of data hashes to a given value are not as high as those to execute logic applied to that transaction and potentially keep information on its consequences in state.
Of course, this means that the gas limit per block still implies some total ceiling on how many transactions can be issued on an Optimistic Rollup platform per unit time, but this limit is on the order of 20-200 times that of status quo. Further, as noted above, in phase 1 of Eth2.0, shards will be added that will only be used for data availability, increasing the total capacity for rollup transactions.
We briefly highlight a short, non-exhaustive list of some of the promising Optimistic Rollup projects to highlight some of the types of design choices that they are making. For further information on the space of such projections and the tradeoffs that they make, see this article.
- Optimism This project intends to create a general purpose, "OVM (Optimistic Virtual Machine)" which will allow a rollup on which one will be able to deploy Solidity contracts with minimal alterations compared to an on-chain deployment. Optimism has a demo/partial version already available for open finance protocol Synthetix. A general purpose testnet has been announced for September 2020.
- Off-chain Labs The Arbitrum system being developed by Off-chain Labs, like Optimism, offers the ability to simulate the full EVM. Here, fraud proofs can take a logarithmic number of interactive rounds (as a function of the number of the steps of the computation on the Arbitrum virtual machine that is being challenged). In exchange for requiring this additional interactivity, fraud proofs are more compact.
- Fuel Labs Off-chain transactions here use a UTXO model. This allows fraud proofs that can be verified by the EVM (in a single round) in a particularly efficient fashion, notably avoiding the need for the EVM to have access to intermediate state roots. On the other hand, this different model will likely require a more significant transition to migrate existing Dapps to Layer 2. Fuel has a live demo consisting of a decentralized version of Pokemon. Their roadmap has them releasing their V2, which would allow enough generality for Ethereum style smart contracts, in 2021.
Another approach is that of zk-Rollups. Here, when information is brought on-chain, a zero-knowledge proof (typically using a zk-SNARK or zk-STARK) is included that it reflects the state of the Layer 2 platform, as it has been committed to on-chain.
Note that, as with Optimistic Rollup, in zk-Rollup the data of transactions is included on-chain as call data. Hence the fundamental limits on how much scaling Optimistic Rollup and zk-Rollup can offer are similar. Moreover, despite the fact that these zero knowledge tools are often associated with privacy preserving protocols, in zk-Rollup as the call data is as public as publishing a traditional transaction on-chain, there are no privacy advantages to this approach compared to the status quo. Hence, zk-Rollup doesn't really make use of the zero-knowledge properties of zk-SNARKs and zk-STARKs; rather it uses them to efficiently convince the EVM of some statement. So, one should not confuse zk-Rollup with approaches that attempt to offer privacy solutions while on Layer 2, such as Zkopru which proposes creating privacy guarantees similar to those of Zcash … on an Optimistic Rollup.
Compared to Optimistic Rollup, zk-Rollup has some advantages and some disadvantages :
- No long withdrawal period – as any on-chain claim is accompanied by a proof, one no longer needs to have a withdrawal period long enough for users to catch malicious claims.
- Better trust assumptions – if Alice is a user of an Optimistic Rollup and she goes offline for long periods of time, she would not necessarily notice if a malicious actor submits a false claim on-chain that harms her interests. As any user of an Optimistic Rollup has enough information, the ability, and generally the incentive to challenge that malicious claim, there is a reasonable chance that it would be flagged even despite Alice's absence. However, in zk-Rollup the malicious actor would not be able to submit such a claim on-chain in the first place, so Alice's interests are secure even if there are zero honest actors of the rollup.
- More novel (i.e. on some level experimental) cryptography – the cryptographic community generally gains confidence in primitives that have existed and been widely used for a long time. If no one has seemed to break a long-standing, important building block, that is a good sign that it is secure. The cryptographic tools (SNARKs and STARKs) used by zk-rollup are still relatively new, so one might not have as much confidence in them compared to more well-established tools.
We briefly mention a few projects (again this is a non-exhaustive list) to illustrate the state of zk-Rollup development. Note that several zk-Rollups are already being used, live in production, on the Ethereum mainnet. However, these projects tend to have zk-Rollups that are fairly application specific. Indeed, for example if one wants to make a zk-SNARK based rollup, then one needs to implement a circuit that represents the conditions that the EVM will need to be able to verify. Doing this in a way that is both efficient and general purpose is challenging.
- Loopring Loopring developed a zk-Rollup protocol that is customized for the specific application of their exchange, allowing "1000x greater throughput".
- StarkEx In addition to similar application specific deployments (including for DeversiFi 2.0), StarkEx has recently launched a test version of a general purpose platform (!), Cairo. It will be exciting to follow Cairo as it becomes more tested and more developer tools are released making it more usable.
Kleros and Layer 2
One might consider the following points when asking how Kleros could work using a (Optimistic or zk) Rollup.
- When will a rollup solution be deployed that is sufficiently general purpose to handle Kleros' needs? Most of the existing application specific solutions are for payment channels (or for the operations required for decentralized exchanges). While the voting and redistribution schemes of the Kleros court are not necessarily substantially more complicated, they are different enough that new research and development would probably have to be done to create an application specific rollup for Kleros. Thus, the most convenient possibility would, of course, be if a usable general purpose solution becomes available.
- Would it make sense for the Kleros general court to be on-chain, even as child courts were on a Layer 2 solution? One could imagine that setups where, if there are attacks on the rollup that prevent the child court from functioning properly, one can just appeal to the on-chain version of the court. Then Kleros would be no more dependent on the proper functioning of the rollup than it is on the integrity of its appeal system. However, currently PNK stakes won and lost in cases in child courts affect the chances of a juror to be drawn in the general court; it would be potentially complicated to give the on-chain court access to the current stakes of each juror (information that exists on the Layer 2 court) when it is time to draw jurors for a case.
- If a Kleros court on an Optimistic Rollup makes a ruling that is used by some other Dapp (that is not also on the same Optimistic Rollup), there would be delay that one would have to wait for the challenge period before this information would finalize on-chain and the ruling would be enforceable. As previously mentioned, Kleros rulings already take on the order of days, so this would not be the end of the world, even if having to wait for additional delays is not ideal.
Based on our read of the progress of talented teams that are dedicated to scaling Ethereum, we believe that the solutions discussed above will provide solutions to this problem in the mid-term.
However, we have also done research internally to consider what kinds of Kleros-specific approaches one might take if these general purpose solutions hit roadblocks.
It is worth remembering that the key difference between zk-Rollup and Optimistic Rollup is how information about the state of a contract on Layer 2 can be moved on-chain. However Kleros itself, in its role as an oracle, can also be used to bring information on-chain.
Hence one can imagine a setup where some Kleros courts, including the general court, are on-chain, and other courts exist on a Layer 2. Then, similar to Optimistic Rollup, if a user wants to unstake PNK from one of the Layer 2 courts or if an on-chain contract needs access to a ruling made by a Layer 2 court, this information can be submitted with a bond on-chain. Then, if this information is incorrect, it can be flagged by a challenger. Whereas in Optimistic Rollup this challenge would include a fraud proof that the EVM can process to see that the challenge is correct, a Kleros based system might send this disagreement to an (on-chain) Kleros court. This approach is similar to how our governor already works.
Compared to other rollup solutions, this approach has some disadvantages.
- This setup creates an extra dependence on the integrity of the Kleros court. While this might be acceptable for use in Kleros, as one must already have confidence in the general court, if any other project where to implement such an approach, this would add new security assumptions to their model.
- Similar to Optimistic Rollup, the step of requiring a challenge period to bring a result on-chain adds an extra delay, beyond the time that it already takes for a Kleros jury to rule, before the decision can be enforced.
- If Kleros is ultimately on the same Optimistic/zk-Rollup as other applications, they could potentially interact directly in a way that is less obviously viable if Kleros has a custom Layer 2 solution.
On the other hand, this approach means that you never have to bring the full state on-chain. This could remove implementation issues compared to Optimistic Rollup; you don't need to worry about the size of on-chain fraud proofs and you don't need the on-chain EVM to be able to simulate an off-chain execution environment that is equivalent to itself. You completely avoid scenarios where you need to bring so much information on-chain at the same time that you tax the capacity of the main chain. Instead, all of this information would be in the minds of jurors.
Hence, if the other scaling solutions that are being explored in the Ethereum ecosystem run into unexpected obstacles, we are rather confident that this kind of approach would be a viable backup. For a more detailed view of what such a system might look like, see this draft proposal.
Bridges to Other Chains and Short Term Solutions
A related approach to that of the Layer 2 solutions would be to use bridges between Ethereum and other blockchains where transaction costs are less expensive. For example, one could deploy versions of Dapps that use Kleros as their arbitrator, such as Curate or Linguo on these alternative chains. Then, if an Arbitrary Message Bridge exists between that chain and Ethereum, that Dapp could call the Kleros court on Ethereum and receive a ruling on its chain in a manner that remains decentralized. This kind of solution can make use of one-off bridges between two given chains, or take the more generalized approach of connecting a wide number or different blockchains taken by Polkadot, particularly once the Polkadot-Ethereum bridge is available.
Along these lines, we are considering deploying our upcoming translation Dapp Linguo to a "Proof-of-Authority (PoA)" Chain using a bridge so that it can receive rulings from the Ethereum-based Kleros court. Obviously, the PoA chain, as it makes use of a small number of trusted validators, in this case a group of notaries, is less decentralized than Ethereum. One asks what are the consequences of this greater centralization for a given Dapp. By keeping the Kleros court that is making decisions related to Linguo on Ethereum, one has as much confidence as ever in the juror selection mechanism and the integrity of the process by which Kleros comes to a ruling. However, the correct execution of this ruling on the PoA chain would depend on trusting that (most) of its validators are behaving correctly. As other scaling solutions become available, Linguo can later be transitioned to more decentralized alternatives.
Ultimately, the growth pains relating to gas costs and scaling are the price that is being paid for using still-developing technology to achieve decentralization. We at Kleros are confident that eventually scaling solutions will be sufficiently available, one way or another, that the cost of using a blockchain will not be a significant barrier to offering decentralized, peer-to-peer, affordable dispute resolution.
Where Can I Find Out More?
Join the community chat on Telegram.
Visit our website.
Follow us on Twitter.
Join our Slack for developer conversations.
Contribute on Github.
Download our Book