A practical distributed oracle system for cryptocurrency contracts. White Paper.

[kolinko]

Just published this whitepaper:
https://github.com/orisi/wiki/wiki/Orisi-White-Paper

It's about an implementation of a distributed oracle system. The idea is that for contracts that require external input, we may set up a set of oracles that monitor the external world and sign transactions using m of n signatures. So, instead of trusting just one oracle/arbiter to deliver the verdict, you're trusting 20-40 ones, run by trustworthy individuals who are unlikely to cheat.

Using Orisi debs will soon be able to implement cool things like:
- contracts depending on btc price, weather and so on
- human contract arbitration
- additional protection of bitcoin wallets
- sidechains - even with all the current bitcoind version

We're also wrapping up an implementation of such a system, and will be launching first oracles within the network later on today, or tomorrow.

Any feedback?

[1714100839]

1714100839

[1714100839]

1714100839

[1714100839]

1714100839

[1714100839]

1714100839

[1714100839]

1714100839

[dansmith]

I like the project. I wish you success getting off the ground. Kudos for using Bitmessage to prevent DDOS of oracle nodes.
For the sake of starting a discussion, could you break down in a nutshell how this project is superior/inferior to what https://www.realitykeys.com does? 

[kolinko]

Thanks for the kind words

Their approach is simpler than ours, but has two flaws. First of all - you have to trust them. While they look quite all secure, it would probably be unwise for you to build a big business based on such a single point of failure. Just like with exchanges - if their servers fail, if they go out of business, if they lose their keys... you'll also be lost.

In our case, if some oracles get disabled, hacked or go rogue, the other ones will be able to take over and continue. Assuming less than 50% of oracles die at the same time.

Also, let's say that you build a service that allows anonymous people to bet on weather. It's possible that one day a disgruntled employee of theirs will make a huge bet with your system and then introduce a "bug" into theirs. That's a big risk.

In our case, such a scenario is virtually impossible. There is no single person that can do such a thing - you'd have to convince the owners of a dozen other oracles to deliver a faulty result. That's not easy, especially if the oracles are being run by non-anonymous people.

The final issue with their solution is that it's limited in scope. While they offer a ton of facts to track - far more than our basic implementation available today - you cannot really do any more advanced tricks. For example - you cannot create a sidechain using their oracle, because they don't allow you to track alternative block chains. You cannot create a network of human arbiters. With our approach, the sky is the limit - you can fork Orisi and create your own arbitration software. There will still be an issue of finding trustworthy parties to run the oracles you devised, but perhaps we can help with that.

As for our faults compared to them:
- we're not yet production ready - alpha version of the client will be published today or tomorrow
- we're distributed only in theory - tomorrow we'll be having just three oracles running. but we hope to get community involved and get at least 20-40 of them being ran by trustworthy individuals
- the datasources we offer are very scarce - by the end of the week we'll have just a bitcoin price ticker, and a basic website parser - so you'll be able to get verdicts based on bitcoin price or on a website containing certain words. on the other hand, as I said, anyone can fork us and implement whatever crazy things they want
- they work with Ethereum and any other cryptocurrency, we only work with Bitcoin for now. Although we hope to get Ethereum support quite soon.

In other words - they are e-gold (centralised, closed), we're bitcoin (distributed, open source). Of course, our software is not yet polished and not yet production ready, but as the time goes, a distributed set of oracles will allow for things and security that you could never get with a single oracle.

I'm sorry if it sounds like I'm bashing them. I try to always speak in positives, but it's just that distributed oracles are really so much better I'll forward this discussion to them, perhaps we can have an interesting argumentation!

[edmundedgar]

Edmund Edgar from Reality Keys here.

This is an interesting piece of work. I think it's actually a bit less different from our approach than you're giving it credit for, because our service is designed to be combined with other authorities doing the same thing. It's entirely up to the parties whether they use a single service or a whole bunch of different ones and we aren't going to stop people who think a single authority is good enough for their purposes, but we certainly hadn't assumed that everybody would rely only on us.

We did consider open-sourcing our software to make it easy for other people to set this up. We may do this in future,  but we figured the community is better served by multiple, separate implementations rather than everybody running the same code that ends up breaking in the same way. Redundancy is no use if all the redundant parts fail at the same time for the same reason, so when we're designing these systems the risks we need to worry about most are the ones that take out a critical number of "independent" nodes simultaneously. It's all very well having three separate external power lines and two underground generators cooling your nuclear reactor but it's still going to melt down if they all get taken out by the same tsunami.

PS. The other big tsunami risk we need to be worrying about here is regulatory.

[AsymmetricInformation]

Personally, (for what its worth) I also felt that this idea was more-similar to RealityKeys than you've described, and even though this was never explained to me, assumed that RealityKeys would be some kind of "gear" in a bigger mechanism (like a multisig 3 of 5). As I mentioned on twitter, trusting >1 oracles isn't as magically decentralized as one might hope, as someone can generate a number of fake identities and wait for an opportunity to strike.

One thing I like about RealityKeys (which makes it, currently, my favorite trusted-feed solution) is how their business model cleverly plays with the economics of trust (requesting a key is free [only efficient if this part is automated], but they 'charge' for the truth, aka independent verification, so the truth is what they need to focus on, but it is off-path so would never actually need to be used [unless project grows very large]). I haven't looked into it, but I'm skeptical that people will want to become a Orisi oracle and supply data. How much can they reasonably expect to be paid for this tedium?

I really like the idea of using Bitmessage to trigger oracles and am really excited for all of the new attention that this space is getting. I still think that I have the only truly trustless and decentralized solution, but that's far from saying that I believe my idea is going to be useful, let alone the most popular.

[kolinko]

Edmund - yeah, we don't have tsunamis, but we have earthquakes here in Poland. Like one a year. 4-richter scale

As for arbiters just delivering the private keys (not signing the transaction like in Orisi) - I'm embarrassed to say that I didn't think of that before. It might be a better implementation, because right now all the oracles have to contact each other and send each other partially signed messages. We will definitely look into that.

As for many nodes going down at the same time - there is definitely such a risk with our system. We hide the nodes behind TOR and Bitmessage, and they will be distributed across various actors on various continents and various architectures. Still - someone might find an exploit within the way an Orisi node processes requests, or find a way to disrupt the BitMessage network. But isn't Bitcoin the same way really? It's a distributed system, but one that can be (and already was) brought down with a single core exploit.

@AssymetricInformation - I'm glad we moved the discussion off Twitter. It's a bit hard to explain things in 140 chars

As for a single person registering multiple nodes (i.e. a Sybil attack) - there will be short list of nodes - 20-40 position each. Those will be published on www.oracles.li, but also on other sites as well probably. The community will naturally verify that the list contains only nodes from independent parties, and complain if it's not the case. If the list administrator doesn't fix the list, people will create their own lists and the most trustworthy list will become a default choice with time. A similar approach is being used successfully in case of BitTorrent trackers.
Let's also not forget that the most traditional way of avoiding the Sybil attack is the good old identity checking. This is the way it is being done in ssl certificate verification, but also in courts all over the world - we know that judges are separate entities, and they stand a lot to lose if they decide to collude.

As for people wanting to become an Orisi oracle - we want this to be an process just as easy as setting up a Bitcoin node. You set up a virtual machine, and launch a script downloaded from repo. You don't have to track the sources yourself, you don't have to deliver arbitration by hand. Aside from occasional updates, it's supposed to be launch and forget really.
We expect the arbitration fees to be the equivalent of around USD$0.02 - if you decide to use 20 nodes, you'd have to pay $0.40+$0.10 Orisi project fee per verdict. If the default node list processes 10k verdicts a day, the people/companies running those nodes will get $100 per day. Not a fortune, but should be good enough for some people to bother doing that.
It's a different model from the Reality Keys, where the basic arbitration is free, but human intervention isn't. I think we may be targeting different markets really. In our case, you pay $0.50 to get a fully automated solution that's independent from a single company. In case of Reality Keys, you usually pay nothing, but have to trust a single provider to be still there when the time of resolution comes. You could say that the debate is really: "Do I trust a single open-source software being run by independent rather trustworthy people, or a closed-source solution being run by a single rather trustworthy company? How much am I willing to pay for that trust?"

[edmundedgar]

You could say that the debate is really: "Do I trust a single open-source software being run by independent rather trustworthy people, or a closed-source solution being run by a single rather trustworthy company? How much am I willing to pay for that trust?"

We need to distinguish between the ways we ultimately see people using this thing and what people are able to do right now.

The way we ultimately see it at Reality Keys the user (or their software) combines a bunch of competing "rather trustworthy" authorities of which we are only one, running different software implementations.

The way I think you see it the user (or their software) combines a bunch of competing "rather trustworthy" authorities, but all running your software implementation, or a variation of it.

To the extent that there's a difference, the former is slightly more decentralized than the latter, because there are more diverse software implementations. But naturally there are some substantial benefits to open source.

Then there's the question of what people can do right now, which is that in both cases you and I seem to be the only people running these services, so you just have to trust whichever you pick. But I'd imagine you'll be able to get other people to run nodes more quickly while we wait for our competitors to ship. I suspect the flip side of that will be that your nodes take a trustworthiness hit because the people running them have less skin in the game, but we'll see.

What would be particularly helpful here is if we can make it trivially easy to combine the two. If you're interested in adopting the "don't touch the contract" model where you just produce two public keys then one of the private keys, that would just be a matter of making sure our APIs can speak a common language. (Reality Keys probably won't start signing people's transactions for them any time soon, not least because it has some potential regulatory downsides that you don't need to worry about as much if you've got a bunch of guys running pseudonymous services over Tor etc.)

[kolinko]

Hm, so it seems there are two possible approaches to the m of n oracle problem. Aside from the "who signs the keys" technicality.

One is that oracles promise to deliver as good results as possible. And you trust they will do so. (this is Reality Keys)
Another one is that oracles promise to run software and not interfere with it, and keep it secure - leaving the algorithm verification on the user's side. (this is Orisi as we described it in the paper, but perhaps we should change it?).

^ just a random observation, not a critique of any approach.

As for the "who signs transactions" - I discussed it with the developers today. For now we want to wrap up the alpha / proof of concept where oracles are the ones doing the signing, so people can start playing with it as soon as possible.

But the concept of oracles just delivering the keys is very interesting. Aside from the legal stuff, it would make it easier to gather all the signatures (right now oracles have to send partially signed txs between them - it's a pain), and it would allow Orisi to easily interact with other systems. I'll get back to you via e-mail on this one, ok?

By the way, I just published this:
http://orisi.net/discussion/4/mturk-and-distributed-oracles-two-tiered-arbitration
Just some random thoughts - not sure how they fit the whole discussion we're having here. But we gave credit to RealityKeys in the article

[edmundedgar]

Hm, so it seems there are two possible approaches to the m of n oracle problem. Aside from the "who signs the keys" technicality.

One is that oracles promise to deliver as good results as possible. And you trust they will do so. (this is Reality Keys)
Another one is that oracles promise to run software and not interfere with it, and keep it secure - leaving the algorithm verification on the user's side. (this is Orisi as we described it in the paper, but perhaps we should change it?).

Yup, that sounds right. The second approach reduces the amount you have to trust the oracle to be competent to do (as opposed to honest, where it doesn't help), since you can check the code they'll be running. It doesn't completely remove the need for competence because it's still possible to screw up the setup and operations, but the more completely you specify and automate the recommended setup and operations the closer you get to removing it.

What would make this approach really useful would be if there was a way to verify that the oracle really is running what they say they are. I've occasionally fruitlessly pestered cloud hosting providers to provide a service like this, where they'd give you a virtual machine that would only install the software you publicly specified, and would publish a record of what it was installing. Obviously this only shifts the need for trust along rather than getting rid of it, but cloud providers might be good people to shift the trust to because their businesses depend on strong existing reputations and they have a lot of skin in the game. The usefulness of this kind of service would go well beyond oracles - it would be useful for pretty much any case where you have some open source software that you need to run on a server and you need some kind of trust from your users.

As for the "who signs transactions" - I discussed it with the developers today. For now we want to wrap up the alpha / proof of concept where oracles are the ones doing the signing, so people can start playing with it as soon as possible.

But the concept of oracles just delivering the keys is very interesting. Aside from the legal stuff, it would make it easier to gather all the signatures (right now oracles have to send partially signed txs between them - it's a pain), and it would allow Orisi to easily interact with other systems. I'll get back to you via e-mail on this one, ok?

Sounds good. I like this approach a lot but TBF there are some real practical advantages to signing the transactions:
1) People are more used to the signing model, and some clients can do it already without modification.
2) A lot of the patterns you need for the key-publishing model are either non-standard (so you have to send them to a miner like Eligius instead of broadcasting to the network) or need some rather unorthodox ECC voodoo to shoe-horn them into the standard script patterns, which makes me a little bit uncomfortable.
3) If you sign the transaction, you have more flexibility over what you sign, beyond what you could get into a bitcoin script. For example, you may want to say, "This transaction pays out (X * the BTC-USD) rate to Alice, and the rest to Bob". Whereas as far as I can figure conditions on the key-publishing model basically have to be binary.

[Unshakeable Convoy]

There is a kicker to both approaches as well - make Oracles deposit some amount as collateral. Use that then to run some form of insurance policy enforced via contracts, so that affected parties could be remedied.

Also I've been thinking about introducing civil disputes within the chain itself. Could that work? Or is that something that could easily be abused?

[edmundedgar]

There is a kicker to both approaches as well - make Oracles deposit some amount as collateral. Use that then to run some form of insurance policy enforced via contracts, so that affected parties could be remedied.

Yup, that sounds like something that would be particularly valuable for kolinko's model, because the people running the nodes don't otherwise have any skin in the game, aside from their personal reputations.

BTW, although we obviously like to use our own tools for everything, in some circumstances oracle insurance might actually turn out to be a job for a big, old-school legacy insurance company rather than a blockchain-based setup whose failure modes may end up looking too much like the failure modes of the thing they're insuring...

[kolinko]

make Oracles deposit some amount as collateral.

the nodes don't otherwise have any skin in the game

That was actually our original idea. We considered requiring oracles to burn some funds to prove that they are serious, or put up a collateral as you said.

First of all though, there's no real need for that. If oracle proves to not be trustworthy it will be thrown out, and will lose all the future profits. You could call this "an implicit collateral". If your oracle nets you 1BTC in fees per month, if you get thrown out, you'll effectively lose 10-50BTC you'd otherwise earn by running the oracle for the next 1-5 years.
But more importantly, a collateral would be extremely hard to track. Let's say that all the oracles.li oracles put up 100BTC in collateral. You want to sign a contract for 1BTC with Bob for a nice weather tomorrow, and you want to secure the contract with them. Are you safe to do so? Not necessarily. It could be that Bob already signed ten thousand contracts for 1BTC with other schmucks, and will bribe oracles to deliver a false verdict.
Ergo, a collateral doesn't really protect you unless you know how many contracts are being secured by it. And even then, it would probably ineffective to use X collateral to protect X in contracts, because oracles would need to require huge fees to earn their collateral back in any reasonable amount of time. So, you'd want X in collateral protecting 10*X in contracts - a "fractional reserve" you could say.

Is it doable? Well, perhaps. But I think a collateral of time spent setting up the oracle and building trust, and of future fees to be lost, should be good enough. I have no doubt that some oracles will lose the community - Mark Kerpeles, or PirateAt who had a large WoT score, or this guy who bet people 10kBTC that pirateAt will actually pay... But there chances that 20 of 40 oracles will do that at the same moment? Without their intent leaking out beforehand?

Besides that, you can have a set or Orisi nodes which you convince to set up a collateral fund, or burn money. And the market would decide whether it really matters that much.

What would make this approach really useful would be if there was a way to verify that the oracle really is running what they say they are

There's a section on that in the Contract page in Bitcoin wiki: https://en.bitcoin.it/wiki/Contracts#Trust_minimization:_Amazon_AWS_oracles . I think the guys from bitsquare.io are working on that.

Also I've been thinking about introducing civil disputes within the chain itself.

I think it's the matter of practicality for now. What kind of civil disputes would benefit from being mediated through blockchain? In most cases courts and existing arbitration companies do a good enough job.

[edmundedgar]

But there chances that 20 of 40 oracles will do that at the same moment?

I haven't seen your code yet and I may be misunderstanding what you're doing but that implies you've got 39 to 79 public keys or hashes in a single script, which doesn't sound feasible on the current bitcoin network, absent a lot of ECC clevers.

Either way, what makes managing these risks a bit harder than it might sound is that:
1) A lot of your risks are highly correlated, so the redundancy is actually reducing the probability of a fail less than you'd like. (See the earlier point about Fukushima-1, who had five separate methods of powering their cooling systems, did their Probabilistic Risk Assessment and calculated that they'd get one melt-down every 21 million years, but failed to account for the fact that when the 900-year tsunami showed up, it would take out all five at once...)
2) The "moment" is actually the duration of your contract. There are some use-cases where it's almost instant, but for others it could be quite a long time...

Edit to add: You need to be a bit careful how you design this to avoid opening up new holes but if you haven't already, you might want to consider features to switch out oracles that have been proven bad before the contract is up and create a new contract with replacements that are still standing.

[Unshakeable Convoy]

There are use cases where putting down a collateral actually makes perfect sense and is easy to track/reimburse.

Allow me to elaborate. I was considering using that for a coin 2 coin exchange. Say you wanted to exchange 2 CwapCoins for 5 ShetCoins. Say both of which are closely equivalent to 0.1BTC.

Then an Oracle could facilitate the transaction so long as they have put 0.1BTC as collateral. In other words they could only guarantee transactions in the amount of collateral they have put in.

In the even that the Oracle takes the coins and runs, the collateral is then easily distributed by including a proof that the Oracle has not done the right thing. There could be a separate "Court" chain that can follow those rules without the needs of judges.

Just a thought. I agree though that yes in most cases instead of negative reinforcement, you could provide positive reinforcement and enough incentives for an Oracle to never do bad.

Keep in mind however that an Oracle's machine could be hacked. Even if they mean well others might take advantage of their situation. Just like an eBay powerseller could be shaken and used to scam with fake big ticket items.

In short: I think insurance/collateral has its merit and is not entirely out of the question. Insurance might be easier to implement, than tracking down bad oracles.

[kolinko]

That implies you've got 39 to 79 public keys or hashes in a single script, which doesn't sound feasible on the current bitcoin network, absent a lot of ECC clevers.

Yeah, we discovered that a bit too late. Fortunately, 8 out of 15 go through Eligius, so there's that. I hope that once the system gets popular, we'll be able to convince miners to accept a higher number of signatures.

There are also some hacks that would might allow to map 40 oracles onto 15 signatures, but I really hope it won't come to that.

you might want to consider features to switch out oracles that have been proven bad before the contract is up

Yeah, we included that in the original whitepaper, in the section about "amendments". The highest risk - especially at the beginning - is really not trust, but the fact that operators will shut down their oracles. Once other ones realise one of them went offline for a longer period of time, they would sign a transaction transferring funds into an address with that oracle switched out for another one.

Say you wanted to exchange 2 CwapCoins for 5 ShetCoins

I think you may be right. When criticising collateral I considered only medium- and longterm contracts. In that case it would be too expensive to handle the collateral. But in the scenario you're talking about it might make sense.

If you want to build such an exchange, pm me - perhaps we can help some way.

News flash: we performed the first transaction settled by oracles yesterday - so the client is ready. We'll be setting up first official nodes today.

[AsymmetricInformation]

make Oracles deposit some amount as collateral.

I think about this all the time, trying to get it to work, but actually it doesn't make any sense at all!

This idea implies that if the Oracle misbehaves, they'll lose some collateral. But how do you ever know that the Oracle misbehaved? My solution, to use a simultaneous coordination game, and redistribute ownership, is actually a pretty weak solution, but it really is the only solution I've come across (aside from the similar and non-scalable Baysian Truth Serum). Its the only thing that provides any reliable meta-information for assessing honesty.

The only way this could make sense would be to have a separate mechanism, with a greater emphasis on accuracy and less of an emphasis cost (speed, effort, employed-capital). If someone has one, but more importantly, a way of triggering it, I'd like to hear it. The tricky part is that if the cost to triggering an audit is too low, people will trigger audits all the time, to attack the network (ie it might make attacking easier), and if it is too high, it actually encourages attacks or and make threats-to-attack more credible. Its the same problem as before: what costs more for the attacker?

I invite you all to read this section of my FAQ, which discusses incentive-systems: https://github.com/psztorc/Truthcoin/tree/master/docs#why-dont-you

[Unshakeable Convoy]

This idea implies that if the Oracle misbehaves, they'll lose some collateral. But how do you ever know that the Oracle misbehaved?

It's not always possible. In effect that's why you have Oracles, to produce decentralized consensus, where it is not possible to enforce through the block-chain.

If we assume that Oracles will never collude and take over 51%, it is possible to have other Oracles verify the data and slap the bad ones on the wrist.

However with your idea of randomizing and redistributing ownership, this might get even more stable.

Also if you consider that the position for an Oracle is a perpetual auction, you could have the ones waiting in line spank the bad ones as well.

Say you have 5 active oracles at a time (for simplicity only) and you sort them by the total they have deposited as collateral:

O1 | 35 BTC
O2 | 31 BTC
O3 | 27 BTC
O4 | 23 BTC
O5 | 16 BTC
------------- <-- CUT OFF NEXT GUYS ARE WAITING IN LINE TO TAKE THE POSITION AND COULD ALSO PLAY POLICE
O6 | 12 BTC
O7 | 11 BTC

etc.

So let's say O1 and O2 collude and O1 does something bad - then there is the court I mentioned, it gets decided in an off-the record chain, until a verdict is reached.
O3,O4,O5 can verify the same data and decide oh hell no O1 and O2 are lying - kick them out.


Scenario 2 which might even solve the 51%:

Once there is a problem detected by a single Oracle, say O7 detects O1 is being a bad actor, he starts investigation. Let's say during the investigation O2 and O3 collude and defend O1.
Since the oracles in line will also be allowed to vote, they may get the truth correctly even when 51% of the active oracles are colluding.

I will admit I don't have a concrete system that works, just random bits and pieces of the puzzle.

I think there is a way to make this work, but so far none of this is elegant and to my liking.

[kolinko]

@AssymetricInformation

But how do you ever know that the Oracle misbehaved?

That is actually quite easy. As all the signatures are public, you see who voted how. This is not a problem at all. The problem is that at every single moment, one oracle may be playing "long con", and delivering good results, waiting for that opportunity to strike big.

There is absolutely no way you can "trigger an audit" that would be meaningful in any way. Because all audits would show that the malicious oracles are working fine. Until one day all the oracles would decide to "take the money" and run.

CUT OFF NEXT GUYS ARE WAITING IN LINE TO TAKE THE POSITION AND COULD ALSO PLAY POLICE

What you're describing is a de facto proof of stake oracle system. And it's the one we started off with. The idea was for oracles to burn BTC to get into the line, to show that they are serious. Or to pay collateral.

The problem with such a solution is that you're beginning to sort oracles not by their trustworthiness, but by the amount of BTC they are willing to sacrifice when something goes wrong. This opens you up to a "simple" way of attacking. Say there's a line like the one you showed. The simple way of attacking is then for Evil Edmund to jump in and spend 3*28 BTC to get into the three cheapest above the line spots.
What Evil Edmund then does, is he silently signs up contracts that say "if it rains tomorrow on Sahara, you pay me 1BTC". With 150 random people. Every one of those random people sees that the network is being "protected" by 150 in collateral (3*28 Edmunds + O1 + O2), and thinks he's safe.

Edmund then performs a 51% attack, and votes that it's raining in Sahara. He takes the 150 BTC from random people, loses 3*28 of collateral, and he's on his way off. People lose a part of their money.

Of course, you could say that people should only protect up to the amount of collateral of the three "cheapest" oracles. That would cause additional problems:

- first of all, for anything but very short-term, it would provide too expensive (explained earlier in the thread). For short-term, why not. But by short term I mean "minutes", perhaps hours.
- who would you forward the disputes to? who judges that oracles really lied? another set of oracles?

So yeah - short term would work. Anything above a few hours, and you need to either introduce "partial reserve", where you allow the transactions protected by the system to be higher than collateral, or you need super-high fees. Because nobody will lock up 30 BTC in collateral to protect an arbitration for 30 BTC that lasts for half a year and gives him 10mBTC in profit.

[Anotheranonlol]

is it not possible for you to use something like CounterParty broadcasts
Instead of bitmessage?

[AsymmetricInformation]

kolinko: Are you trolling me with such a bad answer? Surely you aren't saying that, for every contract, you personally will look at how people signed to make sure that they signed correctly, then yourself provide a final signature. The challenge is to do this decentralized. Welcome to square 1??