A Decentralized Lie Detector

http://www.augur.net/blog/a-decentralized-lie-detector

by joeykrug • 11 years ago

54 25 11 years ago

Interesting, I wonder how this could be used in a consensus smart contract.

diminou• 11 years ago

Smart contracts can use oracle systems to get consensus on info from the outside world. So a smart contract normally can't communicate with anything besides its internal state, but with Augur they can get info about outside events.

One example of how this could be used (and our primary focus) is on prediction markets using the oracles to report on the outcomes of events after they occur. (Imagine a decentralized InTrade)

wyager2• 11 years ago

This doesn't address Sybil attacks.

Bitcoin is unique in that it presented the first viable decentralized solution to Sybil attacks (via proof-of-work).

To leverage that solution here, it would require that only people who successfully solve the proof-of-work puzzle are able to submit statements to the "decentralized lie detector", otherwise I could just spin up a billion VMs to spread the lies I wanted.

The only other solutions to this problem are centralized, a la government identification.

That said, the math is certainly cool; I just doubt it's very useful in a decentralized system.

woah• 11 years ago

You think they haven't thought of that?

wyager2• 11 years ago

Yes... Or at least, they decided to ignore the issue. They don't mention it at all in the article.

jewel• 11 years ago

People have suggested proof-of-work as a way to stop spam. Legitimate users wouldn't notice if their computer spent a few seconds generating a proof in the background as the email is being sent out. The only problem is that spammers have access to vast amounts of computing power in the form of zombie PCs.

The reason proof-of-work worked for bitcoin back when an army of zombie PCs could have legitimately controlled 51% of the network was that the rewards for a 51% attack were far less than just doing legitimate mining. I think that setting up a system similar to bitcoin won't work when there aren't the same financial incentives to keep the miners honest.

P.S. Isn't the PGP web of trust also a decentralized solution to Sybil attacks?

desdiv• 11 years ago

P.S. Isn't the PGP web of trust also a decentralized solution to Sybil attacks?

PGP web of trust requires a secure channel to broadcast the public keys, so it's not the type of P2P network that the Sybil attacks is applicable to.

logicallee• 11 years ago

I didn't read the article but the issue with "a few seconds" to send a legitimate email is this: it's not actually "a few seconds" (as in, ten seconds to send an email, a hundred seconds to send ten emails, 1,000 seconds to send a hundred, 10,000 seconds - which is 2.7 hours - to send a thousand). That would be prohibitive. But it's actually a few seconds at the rate YOUR computing device can solve the problem. Sending from a desktop might be okay. But a laptop? An iPad? A smart phone? It is trivial to imagine cheap dedicated hardware (such as a beefy quad-core server as compared with a smart phone) that can do 50x the rate. And suddenly your "2.7 hours to send a thousand emails" is "2.7 hours to send 50,000 emails from one machine", 27 hours to send half a million, ten days to send ten million. With ten quad-core servers (instead of 1), ten days to send a hundred million. With a hundred quad-core servers, ten days to send a billion emails. (Or adjust the number of servers up if you get less than 50x the performance from a dedicated server.)

And this was assuming TEN SECONDS of your whole smart phone (or PC!) hanging to send an email. That seems rather unacceptable. And what if you have even 3 recipients? Do you have to wait 30 seconds?

So proof-of-work in this way is really a no-go. On the other hand, slowing down spam servers by trickling through the connection with them, saturating their number of active open connections, seems like it's a good way to limit the amount of spam coming from them, assuming you can be sure they're spam-servers. Better doing that at the mail server end than trying to put that work into the client.

Incidentally, this is the same reason you can't hash something with a small address space (such as social security number, of which there are one billion possible numbers (according to Google if you google the phrase "how many possible social security numbers are there".)

Say you don't want to send your SSN in the plain, you just want to store a hash so that you can verify it but can't recover it.

Well, this doesn't work. An idea you might have is to securely hash it with a long, random nonce so that nobody can use a precomputed lookup table. Well, if you want to be able to verify the number next time, you need to store the nonce. So you're storing the nonce (salt) and the hash, but not the number.

Okay. Now someone who wants to break your number can just compute the hash with every possible SSN, of which there are a billion. That's only 2^29 and change possibilities. A 4 Ghz computer does 4 billion (2^32) operations every second multiplied by the number of cores. It can easily do 16 times as many flop's per second as your total address space, so just multiply that by the number of FLOP's you need per hash to see how few seconds it takes to brute-force it back.

So, your next idea might be, well, we'll just make the hash take really long. Use a complicated hash that takes several seconds to compute.

This works, as long as nobody has a billion times as many "yourPC-seconds" as you do. The problem is they do. If you take a few minutes to do your hash, someone else might have a billion times as many "yourPC-minutes" to do theirs. Your PC is one puny computer not dedicated to the task. Theirs can be a few thousand PC's - or highly dedicated hardware - that does nothing but that hash.

So while in a practical sense, and at great inconvenience to you, this kind of proof of work might slightly slow the rate of attack -- by making you wait seconds to minutes to computer your hash -- in fact even for cryptographic hashes it often doesn't stop a search of the entire hash space.

The bitcoin network currently performs between three hundred million and four hundred million gigahashes (billion hashes) per second. That is 300 to 400 quadrillion hashes per second. By most estimates on about $300 million in hardware.

And you're not asking for it to stop a brute-force search. You're asking it to be so inconvenient they won't bother to brute-force an address space of 1 possibility. (That even though there is only one possibility, they just won't bother to compute it; but your computer will).

I think the idea is a non-starter.

david-given• 11 years ago

This has been done; it's possible to exploit the SMTP rules to force the client to do proof-of-work before the server accepts the email. What you do is reply to the client's first connection with a temporary failure; this forces the client to cache the message locally and resubmit. On the client's second connection, you accept the message.

It's called greylisting, and it works really well as a cheap and easy spam prevention mechanism. I wrote an implementation and used it for years as a first-line-of-defence; it let me use a crappy little 32MB ARM box as an SMTP server. (<plug> http://spey.sf.net </plug>)

kordless• 11 years ago

What, specifically, is cool to you about the math?

tinybike3• 11 years ago

Why, the tensors, of course!

joeykrug5• 11 years ago

Sybil attacks are addressed due to the way reputation works. Reports are a weighted average - so the more reputation you have, the more your votes are weighted. You could make a billion separate accounts and send them each one reputation, but there's no discernible difference than if you had just reported with one account with one billion reputation.

joeykrug5• 11 years ago

but you can't make more reputation out of thin air by creating new accounts/addresses, just as you can't create Bitcoin by making new addresses

tinybike3• 11 years ago

I neglected to introduce the Reputation concept in the blog post. As joeykrug said, Reputation is needed to report on events, and your report is weighted by the number of Reputation tokens you have. So you can't sybil attack simply by splitting your tokens across multiple accounts, as this wouldn't amplify your reports in any way.

The other key point is that Reputation holders are not able to report on events as often as they want to. Instead, they only can report on events at fixed, pre-defined intervals. This precludes sybil attacks by simply report-spamming the network.

mdbco• 11 years ago

This consensus algorithm looks pretty good, but it seems it could get into trouble in cases where the distribution of outcomes is multimodal. One thing that is mentioned is that users would be reporting on several events simultaneously (let's say k events), but it seems entirely possible that there could be strong consensus among k-1 events, but multimodality in the reported outcomes for the kth event, making it very difficult to see who is wrong and who is correct for that event.

I know that Augur is planning to allow people to report event outcomes as "invalid", and that might clear up some of these cases, but what about an event where the outcome initially appears to be objective, but after-the-fact it is unclear and open to interpretation, resulting in two distinct camps of reported outcomes (and hence multimodality)? Perhaps one solution would be to simply declare events with strongly multimodal properties in the distribution of reported outcomes as invalid, and thus avoid the somewhat arbitrary decision where one mode would be declared the "consensus" by the algorithm, costing reputation to those who reported the other mode as the outcome.

joeykrug5• 11 years ago

In events without a clear outcome (say greater than 65% certainty, this is a tunable parameter) there's an audit system where a different group of reporters is asked to answer the question. The idea is that they'd notice the extreme multimodality of the last group who reported on it, and in self interest of preserving their reputation, report an "invalid" outcome.

LukeFitzpatrick• 11 years ago

I think this will have multiple applications for various devices in the future, not only subject to Bitcoin.

gzur• 11 years ago

That page loads but doesn't render for me (Chrome 4.x/FF 36) ... I feel so excluded.

  Uncaught TypeError: Cannot read property 'in_china' of undefined

bjackman• 11 years ago

Same here

TypeError: $S.global_conf is undefined blog_editor-8c9dc8f38e8dff53f0a4430e9075aaca.js:35040

"Invalid App Id: Must be a number or numeric string representing the application id." all.js:61

"FB.getLoginStatus() called before calling FB.init().

http://www.motherfuckingwebsite.com/ is looking better by the day

edit: wow I'm counting over 50k lines of JS in this page.. I think it's this: https://github.com/craigcollie/Bobcat

This makes me feel sad

pards• 11 years ago

Something isn't necessarily true just because the majority of people believe it to be true.

At one point in history most people believed the world was flat.

joshuapants• 11 years ago

Which point in history was that?

joeykrug5• 11 years ago

;) --- idea is that truth is a schelling point

tippy23• 11 years ago

Something isn't necessarily true just because the majority of people believe it to be true.

I'll add to that. At one point in history in 2014 most people believed that all their ancestors regarded the world as flat.

http://en.wikipedia.org/wiki/Myth_of_the_Flat_Earth

tinybike3• 11 years ago

This is a very important point, and is something I (unfortunately) glossed over in the blog post:

In Augur, truth equals consensus. As such, the Augur oracle is intended to be used for events which are easily and objectively determinable after the event has occurred. (For example, the winner of an election.)

However, as you correctly point out, there are MANY cases where consensus might not reflect the truth, such as:

- Events where there is ongoing controversy about what happened (e.g., "Malaysia Airlines Flight 370 was brought down by terrorists")

- Events where the outcome is subjective (e.g., "was Carter a good President?")

- Events where the outcome is unreasonably difficult to determine (e.g., "what is President Obama's checking account balance?")

These events are NOT good candidates for Augur! In fact, all questions include a "this was a bad question" answer, in case a user is asked to report on an ill-defined or unanswerable event.

Of course, Augur's oracle can dutifully report the consensus in these cases -- and the consensus very often will be "this was a bad question" -- but it's up to you to use your judgment as to whether this consensus is an accurate reflection of the truth.

A Decentralized Lie Detector

Related Stories