Designing distributed contracts

[Mike Hearn]

(edit) The article this thread discusses can now be found here:

   https://en.bitcoin.it/wiki/Contracts

[unk]

thanks for writing this up. i'm going to think about this more, but in the meantime i wanted to give you some initial feedback.

i think it works, technically, though i'm going only on your description and a very cursory review of the code. when multiple non-atomic transactions are necessary, there's always a concern about at least mischief that could be caused if one of them is delayed or obstructed, but the motivation for such attacks is unclear out of the context of particular forms of transactions, and nothing particularly dangerous jumps out to me in general.

i suspect, practically, that there may be a dearth of enthusiasm for scripting, at least initially. i'm inclined to think it's one of the more powerful and interesting features of bitcoin, but in many cases the extra distribution of trust that you get from the system is, i hate to admit, quite small practically compared to out-of-band protocols. for example, does the 'escrow' example achieve much more than sending the funds initially to the escrow agent?

still, simply committing to tie up funds without a trusted third party has compelling potential uses, as does CHECKMULTISIGVERIFY, which enables many kinds of 'contracts' on its own (though i would prefer the term 'commitments' or 'conditional payments', myself).

[Mike Hearn]

I call them contracts because that's what Satoshi called them. I guess it's a reasonable analogy though conditional payments might be more precise.

I haven't made up my mind about their value yet. Introducing new contract types means writing a patch for the Bitcoin software then waiting for miners to upgrade. It's probably not a big deal, but it's not free.

Still the minimization of trust strikes me as good practice. Bitcoin doesn't have chargebacks nor does it have any big, trusted names taking part so escrow is pretty essential. A trusted escrow service like ClearCoin might easily end up with really huge amounts of of money sitting in it, waiting for mediation. Whilst Gavin is a highly trustworthy fellow, what if the site gets hacked? There's tremendous incentive to break into servers which are acting as escrow agents.

If I send money to the merchant using a multi-pay contract, it's easier for us to do business. If the mediator, on receiving the funds, immediately ties them up in yet another multi-pay contract that sends the coins either to me or the merchant then I know even if the mediator/escrow service gets hacked my coins cannot be stolen. At worst the hacker might destroy the keys and get nothing. This chaining of multi-pay contracts can be done with a slightly different protocol/set of SIGHASH flags so at no point is the money ever "in the open".

Building up trust is difficult, slow and the fact that the Bitcoin economy is being bootstrapped from zero means that lack of trust is a drag on commerce. If contracts can help grease the wheels they seem like a useful feature to me.

[kjj]

Still the minimization of trust strikes me as good practice

Mental note to read the first post again when I'm not so tired.  My initial impression was that trust was being pushed around to (allegedly) trusted third parties, like bubbles under wallpaper, not being minimized.

By the way, I highly advise anyone interested in third party services to read about the history of ISK banking (AKA scams) in EVE Online.  The odds that a third party will remain trustworthy once the incentive to cheat becomes high enough has been holding steady at zero percent there for like 8 years now.

[Mike Hearn]

Not really. It's about limiting peoples options at each stage to remove the chances of bad things happening, or set up incentives to ensure good things happen.

Without a third party dispute mediator, buyer or seller has an incentive to screw the other person, so it's hard to do trade.

With a third party, you no longer need as much trust in the counterparty, but now you need to trust the third party instead. They also have an incentive to screw with you, although presumably there are far fewer escrow services than traders, and the escrow people have more to lose. The bigger risks are that the escrow service gets hacked and all the coins currently waiting for transactions to complete are stolen, or that trust becomes so centralized that escrow becomes very expensive.

With multi-pay contracts, we can minimize the chances of bad things happening:

• If a trade goes well the third party is never involved at all. So there's no need for us to pay any fees.
• If a trade goes south, as a buyer my only option is to get a pre-agreed mediator involved. I can't screw the merchant by taking back the coins (not a chargeback).
• If the mediator gets hacked, the hacker can't steal any of the clients coins. They could only steal the companies own profits derived from mediation fees. That means I don't have to trust the security of their setup nearly as much, which in turn means it's easier for new mediation services to get started, leading to a more competitive and healthier market.

The cryptography of contracts lets us entirely remove various ways of things going wrong. The only trust you need is in the quality of the dispute resolution process. Other problems disappear entirely.

[dacoinminster]

This contract stuff could be incredibly important. What I don't see here is how to enforce the single most important kind of transaction bitcoin will be useful for: the bet.

Example: Person A wishes to bet Person B whether the price of bitcoins will rise or fall over the next 30 days.

Desired features:
 - If person A and person B agree on who won the bet, no third parties are needed
 - If they don't agree, a third party mediator settles the dispute and decides who gets the money
 - Both persons commit their bitcoins, and they are locked (can't be spent) until the bet is over
 - The terms of the bet (i.e. how to decide who won) are encoded in the contract and permanently embedded in the block-chain. The terms can be viewed by either party, and can be viewed by the mediator if they must be brought in to settle a dispute. In this case the terms might be: "If MtGox average of highest and lowest price on July 1st 2011 is lower than $10, person A gets all bitcoins, otherwise person B gets them. Disputes will be settled by person C." (bitcoin addresses and email addresses would be included for all parties)
 - The mediator should be able to take a fee if their services are needed

If someone is able to describe how the above contract system could be used for a bet like this one, I would be VERY interested. Extra points if the bet can pay out partially to both parties, i.e. "Person A pays 5 BTC now to get $50 USD worth of bitcoins from person B on July 1st 2011"

[arturh]

What you are describing is a multipay as above. Just with a string embedded in it.

[Stefan Thomas]

Awesome, I can't wait to have "native" escrow support without a third party.

One question regarding the trust example:

Imagine you open an account on a website (eg, a forum or wiki) and wish to establish your trustworthyness with the operators, but you don't have any pre-existing reputation to leverage. One solution is to buy trust by paying the website some money. But if at some point you close your account you'd probably like that money back.

Hmm, but you would get your money back no matter what, so if you wanted you could thoroughly ruin an identity and just start over with a new one once your deposit expires and is returned, correct?

It's true that it would incur capital costs for scammers as their money is tied up in this kind of escrow, but the costs for a scammer would be the same as for a legitimate user, no?

How does this compare to the following system:

- Global trust rating based on total fees paid from an address, perhaps weighted by age as well.
- Trust rating can be raised by sending a high-fee zero output transaction - think of it as buying trust from miners.
- There would have to be some place to lodge complaints against an address. Could be a website or a custom blockchain (that shares work with Bitcoin of course).

The result should be that a legitimate user can spend say 10 BTC on his trust rating once and use it for decades (assuming he doesn't get negative reviews). Whereas a scammer can do the same, but negative reviews and complaints lodged against the address will quickly make his 10 BTC investment void, requiring him to get another identity and spend another 10 BTC.

(Sorry if this is off-topic, it's not an example for a Bitcoin contract strictly speaking.)

[marcus_of_augustus]

just listening.

[Mike Hearn]

Hmm, but you would get your money back no matter what, so if you wanted you could thoroughly ruin an identity and just start over with a new one once your deposit expires and is returned, correct?

Yes. The use case I was thinking of is places where CAPTCHAs are used today and are ineffective (ie, the use cases that keep me employed .

I missed out something that would have made this clearer - if your account is terminated for violating the ToS, you still have to wait the 6 months to get your money back. Assuming that accounts "go bad" and are terminated faster than that, the abusers lose. This is already the case with paying people to solve CAPTCHAs, the problem is that CAPTCHA solutions cost ~$1 per thousand, so it's cheap enough for spammers to just swallow as the cost of business.

The result should be that a legitimate user can spend say 10 BTC on his trust rating once and use it for decades (assuming he doesn't get negative reviews). Whereas a scammer can do the same, but negative reviews and complaints lodged against the address will quickly make his 10 BTC investment void, requiring him to get another identity and spend another 10 BTC.

(Sorry if this is off-topic, it's not an example for a Bitcoin contract strictly speaking.)

Yes, it could be done that way. The problem is authenticating the reviews and ensuring they're globally distributed/respected.

There's already something like this today, see StopForumSpam, but it doesn't have many reviews and many forums don't use it. If it did then we'd run into a different problem of the registry of bad people being abused itself.

Another example: big webmail providers rely on user feedbacks to train the spam filter and shut down abusive accounts. But I can tell you now that people press the "Report Spam" button on mail from their friends and relatives all the time, so it takes a lot of work to scrub the abuse report feeds and turn them into something useful.

The nice thing about putting up a deposit at each site you want to use is that the site can individually raise or lower the threshold as they see fit. A forum for discussing mega-yaughts might prefer to not have any moderators and just charge a hefty deposit, whereas a forum like this one may prefer to have more active moderators and manual spam fighting with a lower deposit.

[Latregetic]

This will be crucial to the future of the currency.  The current biggest downside to the currency is the fact that there is no possible remediation if you get scammed in a trade or purchase.  Every address can be a unique string, and there is no possible way to trace who owned that address.  Without some way to create a contract, there is no way to avoid this issue.

By being able to create a contract that is enforced by the network itself, allows for very complicated forms of behavior with a very minimal chance of being cheated.  Unless the buyer or seller are actively colluding with the mediator, there is no way to actively scam.  However, without some kind of mechanism to insure the mediators stay honest, there is no way to stop that from happening.  Unless the cost to become a mediator is greater than the profits derived from scamming, scammers will simply become a mediator on an alternate ID, and steal every transaction they take part in.

If both buyer and seller have to agree on the escrow agent, then there are less chances of either side being screwed in the event of shenanigans, but having to individually negotiate that for every purchase takes a lot of time and limits the ability of the seller to make automatic sales.  If the seller has a list of preferred mediators, then the onus for mediator selection is on the buyer, and that lessens the cost of the seller's side, but the buyer might end up running into an elaborate scam.  Many mediation firms have a very strong incentive to side with the company that paid/referred to them, in the interests of repeat business.

In order to assure fairness, or at least limit fly-by-night mediation sites with fancy web pages and no real there needs to be a mediator escrow fee, such that the total value of the outstanding contracts they are acting as a mediating agent on is less than some value they have in escrow in the network.  It could be a proportional model, like fractional banking, but there needs to be some strong financial incentive to not be a jerk.



Potential Attack Vectors (that I can think of now):
Respected Mediator is corrupt, buys tons of stuff from online guys using a 30 day contract with himself as the mediator.  Voids all the contracts after the goods arrive.  Seller is screwed.
Mediation site is hacked, and the private keys it used for mediation are stolen.  Now the hackers are able to buy tons of online merchandise from people that use that service, and void the contracts once the merchandise is delivered.
Seller only allows one mediation service, which will collude with them on some contracts.  Seller takes money, never sends package, and the mediator validates the contract without any input from the buyer.

You might want to include a mechanism for voiding a set of keys used in a transaction.  If the mediator notices the intrusion, there needs to be a way to tell the network 'These keys are invalid, never ever use them, ever.'  There should also be a way to freeze contracts that used those keys in such a way that is fair to both the buyer and seller.  I'm not sure how you'd do that with a compromised mediation agent, but it is possible to use any odd number of mediators such that the buyer or seller, plus the majority of the mediation agents concur in order to void or enforce the contract.

Now that I think about it, having multiple mediators, as long as the keys all don't end up in the hands of one of the two parties, would eliminate most of the mediator related attacks.

[Mike Hearn]

I think it's worth remembering that anonymity in Bitcoin is optional, not mandatory. Nothing stops a dispute mediator incorporating and being a real legal entity. Indeed, I wouldn't want to use one that wasn't!

The goal of the escrow transactions is really to grease the wheels by making it easier to become a mediator. You don't have to trust the mediator with your money, you just have to trust that they'll do a professional job of resolving the dispute. There will still be eBay style moderated markets in the Bitcoin world.

A possible other advantage is lower fees. If the trade executes successfully you don't need to get the mediator involved. Having thought about it more though, it seems that they could still charge fees even on successful transactions because otherwise they might refuse to mediate the dispute at all unless agreed up front. I guess it'd depend on what the most sensible business model is.

Yes, the protocol for setting up such trades would probably involve the merchant giving you a list of acceptable mediators and then you picking one. Alternatively a meet-in-the-middle protocol could work better where both merchants and buyers swap sorted lists of acceptable mediators and then the first item in the intersected list is used. It has the advantage that merchants can easily see if there is demand to use a new mediator they don't currently support. As long as the protocols are reasonably standardized adding support would be easy and low cost.

Implementing this system would require, as a first step, a decently written design doc. After that's done and agreed on somebody (maybe somebody different) could implement the design in the official software. There isn't much point in doing this until some dependencies are finished though. Like, the ability to invoke a bitcoin: URL from the browser.

The bets idea is an interesting one. I think it might be possible to encode the bet itself into the chain so you don't need a mediator, just an oracle.

[Latregetic]

Yeah, the anonymity of the mediator would run counter to the mediator's ability to prove he's trustworthy to the community.

I see the escrow transactions as a way to make transactions that are not self-reinforcing, basically any transaction that requires any kind of trust between the parties, work out for the parties involved.  When there is no way for any reasonable person to trust the other part, there needs to be a mechanism to stop cheating on both sides of the deal.

There will always be exchanges and markets that have their own internal methods of dealing with fraud and arbitrating disputes, but having a mechanism built into the block chain that allows a transaction to take place that does not involve only BTC transfers is a very powerful tool.

The meet in the middle protocol would work best, but some method of fairly assigning a mediator would be necessary.  If it just picks the first one on the list, then there is an incentive for mediators to spend huge quantities of time generating addresses with a very high number of leading zeros, such that they are always first in line to collect that 0.002 BTC fee. 

Is it possible to have multiple mediating parties involved in the transaction, such that a majority of the parties have to agree with one course of action in order for that action to be seen as valid by the network?  If you could choose 3 mediation agents from a list of agents with a positive reputation, practically any attack requires compromising too many agents for it to be viable.

How would you be able to invoke a fair oracle without the ability for one party or the other to influence or abuse the thing?  I guess there are a lot of services you could poll gribble style to see what MtGox closed at last night to officiate the bet.  Hell, having some kind of limited oracle support would be a very handy thing to allow for automatic and automated short sells of BTC on the market.

How hard would it be to develop a working design document that could be presented to one of the developers? 

[Mike Hearn]

Yeah, the anonymity of the mediator would run counter to the mediator's ability to prove he's trustworthy to the community.

Well, anonymity is a complex topic. Everyone has at least one identity they are given at birth which stays with them for their whole life. The internet and cryptography now allows people to create alternative identities and build their reputations independently, but it was of limited use because the only things you could do on the internet are speech and creative works, pretty much.

Bitcoin now allows you to trade under these pseudonyms too, but it's still tough to build up trust in an alternative identity because they are free to discard. As a result people tend to drop them whenever convenient. Real, legal identities can't be so easily discarded and there's serious accountability: you can be sued or sent to jail, so it's still much easier to Get Things Done and build trust under that ID.

The next stage of evolution in crypto-anarchism would be pseudonymous companies. The trust an individual can build is always limited just because there's a limited amount an individual can achieve. Big companies have much more to lose and have much bigger impact.

Lots of tricky problems to solve there and, frankly, not that many people interested in doing it. So I think dispute mediators along with most other Bitcoin-related service companies will be strongly identified for the foreseeable future.

The meet in the middle protocol would work best, but some method of fairly assigning a mediator would be necessary.

I think I didn't clearly explain the protocol. Both buyer and seller compile an ordered list of strongly identified mediators, eg, the list might be a list of domain names that have EV SSL certs. The list is intersected and the one that is highest on both lists is selected. Thus, both parties automatically find agreement on which mediator to use, but if buyers keep ranking some new guy higher than the merchants preferred mediator that can be noticed by the software and the merchant informed. It's an easy way to improve his business.

Is it possible to have multiple mediating parties involved in the transaction.

Yes, I think so. It involves an addition to the multi-pay protocol, which is already quite complex. I doubt it would be a very popular feature. This type of escrow is useful for the little guys who just want to buy some alpaca socks. Cases where the risk of corruption is so high you need 3 mediators are almost certainly high-value transactions between legally accountable organizations, so if it goes wrong you can just go to court.

How would you be able to invoke a fair oracle without the ability for one party or the other to influence or abuse the thing?

The oracle can be checked at any point to ensure its answers are correct. As long as there's some reasonable flow of transactions that rely on it, that should make cheating difficult or un-interesting.

I don't know all the details. I'm still pondering how to do it. I think the oracle would have to vend partially signed transactions on demand that match an output script checking the answer. It might be possible to settle bets that can be represented numerically this way.

[Latregetic]

Lots of tricky problems to solve there and, frankly, not that many people interested in doing it. So I think dispute mediators along with most other Bitcoin-related service companies will be strongly identified for the foreseeable future.

That's my guess as well.  An address associated with the company, and publicly shown on the website is all a mediation agency would really need to do.  Still technically anonymous from the perspective of someone trying to find a name and address, but to the community, they can build substantial reputation, so long as they use that address.

Is it possible to have multiple mediating parties involved in the transaction.

Yes, I think so. It involves an addition to the multi-pay protocol, which is already quite complex. I doubt it would be a very popular feature. This type of escrow is useful for the little guys who just want to buy some alpaca socks. Cases where the risk of corruption is so high you need 3 mediators are almost certainly high-value transactions between legally accountable organizations, so if it goes wrong you can just go to court.

My major concern is high value arbitrage and hedging between major parties.  Both parties would need to be legal entities in a position to sue each other with a reasonable chance of recovering losses.  A hedge fund in the cayman islands isn't going to give two shits about a suit someone sends them from China.  And many hedge and arbitrage transactions could be in the tens of thousands of dollars.  Being able to compromise the mediator for even one of these transactions could be worth the effort of breaking into his or her systems.  If the client is able to offer a high security 3 mediator transaction for these people, you'll probably see a lot more capital influx, because most of the attack vectors associated with a single mediator would fail misserably with 3.

How would you be able to invoke a fair oracle without the ability for one party or the other to influence or abuse the thing?

The oracle can be checked at any point to ensure its answers are correct. As long as there's some reasonable flow of transactions that rely on it, that should make cheating difficult or un-interesting.

I don't know all the details. I'm still pondering how to do it. I think the oracle would have to vend partially signed transactions on demand that match an output script checking the answer. It might be possible to settle bets that can be represented numerically this way.

Yeah, I could see a gribble style oracle script that would give you MtGox price quotes if you feed it the right bit of script.  As long as there is some 3rd party tool that allows for the bet/script to be made into plain English for the purposes of the bet, that kind of oracle could act as an impartial arbitrator of short sells. 

[Mike Hearn]

I was thinking actually that the bets would be programmatically enforced.

I just remembered that online betting is illegal in the USA. It's probably best to not have direct technical support for it in the block chain unless that situation changes. It wouldn't add very much beyond what can already be done with multi-pay transactions, anyway.

[Latregetic]

I was thinking actually that the bets would be programmatically enforced.

I just remembered that online betting is illegal in the USA. It's probably best to not have direct technical support for it in the block chain unless that situation changes. It wouldn't add very much beyond what can already be done with multi-pay transactions, anyway.

It's not just the bets, anything that you could use an impartial oracle to arbitrate are potentially up for contract.  Mostly short sells and price hedges.  These are technically gambling, but since it's a futures market, it's such a grey area that I don't think anyone would give a shit.  

Also, if the US government actually notices Bitcoin, we're probably going to get hit with a lot of laundering charges, not online gambling charges.


Also, I see this as the ability for the network to have an internal method of creating enforceable transactions for potentially large sums of money.  When the only thing you have is a Bitcoin address and possibly an IP, even with a 3rd party community they have a reputation with, there is an incentive to cheat.  Having a neutral 3rd party able to reverse the transaction after arbitration removes that ability to cheat, or at least makes it much harder to do.

[mcqueenorama]

Is anybody actually working on this?  Let's talk.  I want to get in on this too.

[bji]

Sorry, I would have posted this in the forum discussion directly, but as a newbie I am not allowed.

I think the Contracts section of the bitcoin wiki site is just awesome.  It kind of warps my brain to try to think about the fantastical ways that contracts can be drawn up using bitcoin scripts.

Anyway, I had one question about the 'Escrow and dispute mediation' section:

Wouldn't it make more sense in the last paragraph to define the transaction as spending the output to the mediator with an nLockTime of a month from now, instead of the same but spending the output to the merchant?  It seems to me that one would rather that, in the case of inactivity on the part of the spender, have the money go to the mediator than directly to the merchant.  This would protect the spender in case they were, e.g. incapacitated or something and could not for some reason verify that the goods were received, but the mediator might be able to investigate and hold the funds until the spender is dis-incapacitated and able to verify or challenge the transaction.

It would also deter the merchant from being the one to incapacitate the sender and wait for the transaction to default out to sending the coin to the merchant (assuming that the merchant knows who the sender is).

It's a minor correction but if it is agreed to then it verifies that my understanding of bitcoin contracts is valid, and if the wiki is then updated it may help someone who in future wants to create such a contract.

[Nefario]

Where is the original thread you are refering to?