Kleros and Augur — Keeping people honest on the blockchain through game theory

Written by Clément Lesaege and William George

Augur has recently released a new version of its white paper, and we at the Kleros team have decided to take a moment to reflect on the choices Augur and Kleros are making to attack related problems. Augur and Kleros are different. Augur is an oracle for prediction markets while Kleros is a general purpose dispute resolution mechanism. However, the two projects have some underlying similarities. Both projects plan to deploy on Ethereum, and in both cases, information external to the blockchain needs to be used. For Augur this is the true outcome of a prediction market. For Kleros this is the honest verdict to resolve some dispute. In both cases, there is a mechanism for people to vote on submitted information depending on how many tokens they have — REP in the case of Augur and pinakion (PNK) in the case of Kleros. Both systems were heavily influenced by the Truthcoin white paper and the SchellingCoin mechanism as means to keep these voters honest. Thus, it is interesting to compare how the two systems have evolved.

First, we note some of the differing constraints and requirements imposed by prediction market oracles versus general dispute resolution mechanisms. For example,

• A general dispute resolution system may involve non-fungible assets (for example, one could have a dispute over a contract holding a cryptokitty) and even assets without a clear monetary value (for example an entry in an ENS blacklist). In a betting market all of the bets are generally placed in a given currency such as USD or ETH.
• Prediction markets have a more severe problem with parasitic markets; namely markets that use the result of the oracle without paying in appropriate fees. It is reasonable to expect a prediction market that is issuing bets on well-known events to have competition from other markets speculating on the same event, and there is the risk that this competitor will reuse the result of an Augur market without paying for reporting costs required to obtain this result. In contrast, in most of the day-to-day disputes that would be handled by a general purpose dispute resolution system (such as a contract dispute between a freelance web developer and a client) one would not expect outside parties to have a significant interest in creating a secondary market on how the dispute is resolved.
• There is greater uncertainty in how a given honest juror will vote on general disputes. A general dispute mechanism needs to be able to handle the fact that sometimes there will be judgement calls on which reasonable people would disagree. This is not really the case for prediction market oracles, where one is reporting on some established fact in the world. (Although there can be rare edge cases such as the TradeSports market Augur mentions in their white paper. In this market, bets were placed on whether North Korea would launch a missile that landed outside of their airspace before the end of July 2006. North Korea successfully launched such a missile, but the event was not recognized by the US Department of Defense as was required by the contract creating a controversy between the spirit and the letter of the betting market.)

We note that both Kleros and Augur ended up with an appeal system. Previous work in Truthcoin did not have an appeal system which posed serious scalability issues; the total amount of work was O(amount_of_disputes * amount_of_holders), which can’t scale. Truthcoin’s proposed solution to this was for the system to subdivide itself into “branches”. Then a given case was considered by a single branch where all of the VoteCoin holders vote. Then as the branch gets too big, there is a process to further subdivide it. The problem with this is that the VoteCoins as described in the Truthcoin paper are not transferable between branches. Thus, you either wind up with a few giant branches where the coin holders are overworked or many small branches that are vulnerable to having an attacker buy up the coins of that branch. Even if the current Augur paper does not talk about “appeals”, their proposal for disputing a tentative outcome is an “appeal”. This allows only requiring input from a subset of token holders. Kleros handles appeals explicitly, by drawing the jurors which need to solve the dispute. In Augur, this is implicit, token holders could look at all markets to find some to stake their tokens.

In the Augur appeal system, rational token holders should adopt a mixed strategy and randomly choose markets in which to stake their tokens. However, this leads to cartels (voting pools) or large actors having an advantage. They would be able to stake their tokens with less work as they only need to determine the result of a given market a single time. We could argue Kleros has the same issue with jurors drawn more than once in a dispute who only need to do their arbitration work once. With large courts it is unlikely that even a relatively large voting pool would be chosen enough times to have meaningful work savings, but for small courts or very large cartels, this becomes an issue. Both projects would benefit from some additional work to deal with, or at least reduce, this issue.

Augur proposes an ultimate appeal mechanism for markets that are disputed beyond a fixed percentage of all REP. In this case, the network is forked creating parallel sets of REP based on the result of the disputed outcome. We consider this an interesting approach as it lets the market sort out very contentious cases. However, we note that having users irrevocably bet their holdings by migrating to one of the two forks (as in Augur) would not be viable for a general dispute resolution system such as Kleros. As we noted above, in a general setting there will be more frequently occuring cases where jurors will be forced to make judgement calls where the right solution is not obvious. Thus, in a general dispute resolution mechanism a forking-based appeal would be much more likely to result in multiple versions of the token with non-negligible value. (Nonetheless, the Kleros community might want to fork PNK at some point as a last-ditch defense against an attack by social consensus; however, this does not need to written into the smart contracts in advance.)

The Augur paper does not take into account market depth. The cost of an attack is not the price of the value of tokens required for the attack, but the price of getting those tokens which is significantly higher. You can get 1 REP at market value, but if you try to get a large amount of REP you will probably not find them at market value as trying to buy that much will greatly increase the price. So Augur should have an even higher security level than stated in their paper.

Augur has introduced a system of participation tokens to attempt to encourage active participation in the system. This replaces the idea of previous work in Truthcoin that coin holders who do not participate in a vote receive a small penalty. It is certainly a problem (for Augur and for Kleros) if too small a percentage of token holders are voting/actively involved. (In Kleros this would correspond to the proportion of users who have their PNK activated to receive assignments.) If too few token holders participate, it becomes easier to obtain 51% of the effective number of tokens in the market. However, it seems that the Augur proposal of selling participation tokens that allow users to obtain a percentage of fees in exchange for having “showed up for the fee window” could be largely automated and wouldn’t be that great an incentive to actively participate. Kleros intends to deal with the problem of encouraging participation by providing tokens to users who have activated their PNK for use in the general court. These new tokens are funded via a low rate of inflation, where active users receive (at least) enough to compensate for inflation. This is de facto equivalent to the Truthcoin proposal of not having inflation but burning tokens of inactive users, but our proposal is easier to implement because of Ethereum gas costs as well as potential regulatory restrictions on third parties that might hold tokens such as exchanges. Cases will rarely go to the general court, so users who have activated PNK there are not signing up for too much work, but if they are selected for a case and don’t perform their juror duties they are subject to a penalty.

We really like Augur’s proposed fee determination system. This system reacts to the amount of ETH at stake in active markets and automatically pushes the market cap high enough to deter rational attackers. We wonder if Kleros could also draw inspiration from this idea. This may be difficult as it would require knowing the value at stake in smart contracts arbitrable by Kleros. However, as we noted above, the assets at stake do not necessarily always have clear monetary values. Conceivably, we could use Kleros itself as an oracle on these values, but it is a subject of future research whether this would be viable.

So, to recap, we summarize a few of the differing choices made by the two systems in the following table:

Clément Lesaege is the CTO of Kleros and a computer scientist and researcher focused on random number generation and game theory applied to dispute resolution. (Disclaimer: he also holds some REP tokens.)

William George (PhD in mathematics, University of Toronto) is a blockchain and cryptoeconomics researcher for Kleros.

For more information on Augur, see their whitepaper. Similarly, for more information on Kleros, see our whitepaper.