Return to site

Scaling Augur, Part 1

By Joey Krug

Special thanks to Vitalik Buterin for laying the foundations of many of these ideas in his blog posts at blog.ethereum.org.

As anyone who’s run a transaction on Ethereum knows, they can get expensive. Whilst Vitalik has many great scalability ideas and proposals for Ethereum, it’ll likely be a while until they get implemented. And we may need to scale faster than that. Whilst almost all Augur transactions cost mere pennies, there is one exception, and that is the consensus transaction. This post will focus on the problem of scaling consensus.

First, an explanation of why consensus is so expensive: after everyone submits their reports of what occurred after an event on Augur, these reports must be placed into a matrix in which we calculate the covariance across reports. Then computations must be done on this; we find the first five principal components, and these tell us how much people contributed to the variance. The more someone contributes to the variance, the more they disagree with consensus, and the more reputation they lose.

While doing computations on a matrix locally aren’t that expensive (you can do the entire thing in less than a second), on a worldwide distributed computer they are. When Augur reaches the point where it has thousands of reporters reporting on thousands of events, it’s clearly unfeasible to just throw these all in one matrix and do principal component analysis (PCA) on it.

There is however, a quite interesting hack around this. In order to understand it better, I’m going to explain how our reporting mechanism works to limit collusion. So, in order to prevent collusion when you submit a report you submit a salted hash of that report. Now if someone can provide your hash, report, and salt, and prove on chain that the report and salt hash to your on chain hash, they can steal all your reputation. The only scenario this would happen is if you both reveal your report and your salt, which also happens to be the only way to prove you’re voting a certain way. So to commit to cheating, you have to provide a fellow cheater information that allows them to just steal your reputation.

Now here’s where it gets interesting: we can take this same basic idea and apply it to the consensus computations. Let’s say we need to compute consensus on 100 events with 100 reports on them, now to do this on Ethereum would be very expensive. Imagine the following scenario: you submit a bond to the network, run consensus locally, then submit your results. Now there are two paths from here, one, you told the truth, and two, you lied (perhaps giving yourself extra reputation after consensus). We’ll examine both.

First, let’s say you told the truth. One of two things can happen. One, people can simply let your consensus be incorporated into the blockchain and that’s the end of things; Augur moves on. Two, someone can challenge your consensus, claim that you’re a liar, and raise an alarm to automatically run consensus on chain. If on chain consensus agrees with the person who ran it locally, whoever raised the alarm has to pay for consensus on chain since it wasn’t needed, and the off-chain person keeps their bond.

Now, imagine the off-chain consensus person lied. People would have a certain period to challenge it (probably up until the next consensus period occurs, so around two months). If you challenge consensus and the person lied, the on-chain results will not match up with the results the person submitted from their local computer. In this case, you don’t pay for the on chain computation, instead, the liar’s bond would pay for it. Note: we should require the bond to be significantly more than the cost of on chain consensus, both to pay for on chain alarm raising, and to reward whoever raised the alarm. The liar loses their bond.

For this to work well, we should probably incorporate two things into the Augur UI, one, a button that automatically calculates consensus and offers to submit the result and a bond (provided someone else hasn’t already done so). And two, a button that checks to make sure off-chain consensus submitted to the chain is correct, and if not, it should offer the user to challenge it (perhaps this should also be something that just runs after starting the client).

Now the other challenge with consensus is having it theoretically runnable on chain, and once Augur scales to say 100,000 events and 20,000 reporters, we can’t just naively throw them all in one covariance matrix and run off chain. The reason being, if someone wanted to challenge it on chain, it would likely be nigh impossible to calculate this all in one transaction. So part of the solution here is carefully partitioning consensus and the matrices into separate transactions. I’ll talk more about how to scale this in part two of scaling Augur.

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly