Implementing External State Contracts - Feedback Requested

[alp]

I was intrigued by Mike Hearn's idea for Oracle Contracts and wanted to begin implementation.  I was able to prototype quite a bit, but wanted to get feedback to see if there was anything I was overlooking or anything that could be improved.

Oracle Contracts
An Oracle Contract is a set of Bitcoin transactions that allows multiple parties to enter an agreement based on the outcome of an event with minimal trust.  The multiple parties each spend Bitcoins that are combined into a single output.  This output can only be redeemed by a subset of the parties based on the outcome of the event.  For example, two parties might want to wager if the Royal Baby will be a boy or a girl.  Each bet 1 Bitcoin.  If the baby is born a boy, then the first party will get the output (2 Bitcoins minus fees), and if the baby is a girl, then the second party will get the output.  A third party, called an oracle, is responsible for deciding the outcome of the event and allowing the winning party to redeem the transaction.

Basic Bitcoin Transaction Overview
Transactions are the basis of the Bitcoin ledger.  A transaction consists of a set of inputs and outputs.  The outputs must add up to less than or equal to the inputs.  Each input is an output of a previous transaction.  Each output is a script that takes a set of data as inputs.  When you spend Bitcoins, you must give data that correctly executes the script.  Typically, the script requires that you prove you have access to a private key.  However, the script can have many other formats that are considered non-standard.

Definitions
Event - Something that occurs in the future with many possible outcomes.
Contract Transaction - A transaction that contains inputs that come from some or all of the parties involved in the contract.  The transaction contains a single output that describes what conditions will allow redemption by the parties involved.
Redemption Transaction - a transaction that spends the Contract Transaction’s input.
Oracle - A third party that agrees to decide whether an event occurs or not.  The oracle will allow the Redemption Contract to be created.
Refund Transaction - a transaction that will automatically refund the output of the Contract Transaction in the event that the Oracle cannot be contacted by a specified date.
Event Expression - a string that contains defines what event determines the payout for an event, along with who should get the payout for each outcome.
Change - when an input is provided that is larger than the intended output, an additional output is added to receive “change”.  For example, if you are spending a 1 BTC input, and wish to send .75 BTC to an address, you will want to receive .25 BTC back as change.  This is done by creating an additional output to an address you control and adding a value of .25 BTC to it.

Basic Overview
Two parties wish to be paid based on the outcome of an event.  If the event occurs with Outcome A, then party 1 should be paid.  If the event occurs with Outcome B, then party 2 should be paid.  To determine the outcome of the event, a third party, called the Oracle, is enlisted.  An oracle simply determines if an event has occurred and what the outcome is.  If the outcome is A, then he will allow Party 1 to be paid.  If the outcome is B, then he will allow Party 2 to be paid.  If the event did not occur yet, then neither party can be paid.

Preparing for the Contract
An oracle creates a set of events it is willing to adjudicate.  An event is something that will happen in the future and each event will have a set of outcomes.  Here are some examples of events and outcomes:

• England 2016 World Cup
  
  • England Will Win
  • England Will Not Win
• 2016 World Cup Winner
  
  • England Will Win
  • France Will Win
  • Brazil Will Win
  • Anyone Else will win
• 2016 World Cup Qualifier USA vs. Costa Rica
  
  • United States Will Win
  • Costa Rica Will Win
  • Draw

• At Least One Country will Leave the EU by Jan 1, 2015
  
  • Yes
  • No

The simplest type of event is a binary event.  While other types of contracts are possible, the initial implementation of contracts will focus on these binary events.  In the above examples, “England winning the 2016 World Cup” and “At Least One Country Will Leave the EU”.  For the rest of this document, only binary contracts are considered.

Once an oracle publishes a list of events and outcomes it will adjudicate, two parties must agree to take opposite sides of the event outcomes.  Parties must negotiate the price each are willing to pay and the total amount of the bet.  This matching can occur manually (I want to make a contract with a friend), or could even be automated through a matching service (each party submits to a willingness to pay a certain amount for one outcome of an event, and if any two parties could create a matching bet, a contract is generated and given to the parties to sign).

Matching services could be run by the oracle or be separate and handle multiple oracles.  Matching services could also be run as a P2P service where oracles and users could register with the network.

Funding the Contract
Once a contract is ready to be created, it must be funded.  This process can be done in multiple ways, such as the following:
Each party can add an input to a contract transaction and an output for change
Each party can submit funds to a trusted entity who keeps a balance for each account, then the trusted party will fund the contract’s inputs.
A shared address can be used, such that each party can submit a payment that can only be spent if both parties agree.

This document focuses on the third method - using a shared address.  Here is an example transaction where Party 1 has a 2 BTC unspent output and wishes to contribute 1.5 BTC to the contract, and Party 2 has a 3 BTC unspent output and wishes to contribute 0.5 BTC.  At the end of this set of transactions, there are 2 BTC ready to fund the contract.



There are still issues with this type of funding.  Both parties have no guarantee that the other will fund their transaction.  Similarly, once the funds arrive, there is no guarantee that the other party won’t hold the Bitcoins hostage, since both parties must agree to spend them out of the shared address.  There are less sinister problems that could exist, such as the other party losing their private key to the shared address or just becoming unreachable.

One way to avoid this is to have a chained transaction that will automatically spend the outputs of the shared address before funding.  The Micropayments Channel implementation does this similar type of chaining. While it is vulnerable to transaction malleability, this problem is not likely to occur with the current network as such changes are non-standard and will not be relayed.

The most obvious solution to this is to have both parties share a hash of their funding transactions such that the contract can be generated.  However, this is still vulnerable to another exploit where one party refuses to submit their funding transaction after the other submits, making the contract transaction invalid and leaving the coins unspendable (the inputs will contain a transaction that does not exist).

To avoid this, a refund transaction containing each input should be created to return to the address that funded it.  That transaction will contain an input sequence value of 0 so that it could be replaced at a later time, and a lock time some small amount of time in the future, such the contract can be created after both parties have funded the shared address.

A contract transaction is also generated with a higher sequence value (1) that spends both inputs with a single output.  That output is spendable when two of the three parties involved (the oracle and the two funding the transaction) agree the conditions have been met to spend it.



In this scenario, if the contract transaction is not created within 30 minutes, the refund transactions may be published to the blockchain.  If a contract transaction is created and signed, it will replace the refund transaction and be added to the blockchain.  Both parties are protected from each other and do not have to trust the other will comply and are only at risk for the transaction fee for the refund.  It is also possible to set the lock time to be after the event, such that the contract transaction need not be published until after the event, thus the oracle cannot know if the transaction is real or not.

Contract Transaction Output Structure
The contract will consist of the inputs from the shared address and a single output.  The contents of the script for this output are as follows for a two party contract:
<expression hash> OP_DROP 2 <OraclePubKey> <Party1PubKey> <Party2PubKey> 3 OP_CHECKMULTISIG

The expression hash is the hash160(x) of the expression string.  The expression is a string in the following format: “<EVENTID>?<Outcome1Address>:<Outcome2Address>”.   The <EVENTID> parameter is a string identifier representing an event that the oracle knows about.

It is possible to have a different expression language that supports more complicated contracts.  For contracts with multiple parties, a different syntax would have to be used.  The script would also have to be modified since an N of M multisignature check would no longer work, since the parties who lose could collaborate against the winner.  In this case, it would require a script that requires the oracle plus the winner to sign.  It also is possible to have contracts that require N of M oracles to agree before it can be paid out, but a different script would be needed.

It is possible the oracle may not be available to adjudicate the event, may refuse to sign a transaction, or may hold the funds hostage.  In this case, a refund transaction can be created on the contract output to return funds.  The lock time can be set to a few days after the event should be completed, and the sequence of the input set to 0.  When the event occurs, a new transaction can be created with a sequence of 1 on the input and a lock time of final.



There are two possible redemption contracts, one for each outcome of the event.  Since the oracle will only sign one of these, only one can be valid, and published to the block chain.

Possible Problems
The main exploit that exists is that there is no guarantee that an oracle will also take positions in contracts, and always side with himself for those transactions.  The reputation of the oracle will still be important and oracle transactions will be visible in the blockchain.  Users who are exploited can report this and prove their claim by showing the expression that matches the hash.  If this becomes an issue, a more advanced use case of having multiple oracles required may prevent this problem (requiring 3 of 5 signatures, for example, and having 3 oracles involved).

More Than Two Parties
The expression language does not support more than two parties, although this could be extended.  A case structure syntax could be used for outcomes.  The contract signature would have to be modified so that losing parties could not collaborate to claim the contract.  An example of a script to do this would require one of the parties (1 of N signature) AND n of m oracles to redeem.  Such scripts get more complicated, but are possible.

Multiple Oracles
Multiple oracles can reduce the risk of having one oracle enter a contract as a party and always adjudicating in his favor if he is involved.  There still is a risk that multiple oracles could collude or even be the same entity.  There would also have to be a coordination of oracles to agree to the same event identifiers and outcomes such that the contracts could be processed.

Transferring Contracts
A party may want to buy the rights to a contract from one of the parties who currently own it.  This could be done by creating a transaction that takes two inputs- one from the new party and the contract transaction, and one output (an updated contract with Party 3’s address and public key in place of Party 1).  The oracle could allow this to occur because Party 2’s rights do not change in this case and sign the original contract’s output along with Party 1.  A new transaction would have to be given to Part 2, who now would be unable to redeem the original contract transaction since it would be spent.

[jadair10]

I was able to prototype quite a bit

I would like to see (i.e., code), if you have any.

There are still issues with this type of funding.  Both parties have no guarantee that the other will fund their transaction.  Similarly, once the funds arrive, there is no guarantee that the other party won’t hold the Bitcoins hostage, since both parties must agree to spend them out of the shared address.  There are less sinister problems that could exist, such as the other party losing their private key to the shared address or just becoming unreachable.

The sequence of events having to do with the creation of transactions is very important in solving the trust issues you mention.

Just because a transaction is created, and even if it is signed, it needs to be broadcast. It seems obvious, but my point is that a transaction can be started by one party, say with the inputs that are then signed by party1, then sent to the second party (i.e., not published), additional inputs can be added by party2, signed by party2, and sent back to party1 to be broadcast. Or do I have this wrong?

[alp]

I was able to prototype quite a bit

I would like to see (i.e., code), if you have any.

There are still issues with this type of funding.  Both parties have no guarantee that the other will fund their transaction.  Similarly, once the funds arrive, there is no guarantee that the other party won’t hold the Bitcoins hostage, since both parties must agree to spend them out of the shared address.  There are less sinister problems that could exist, such as the other party losing their private key to the shared address or just becoming unreachable.

The sequence of events having to do with the creation of transactions is very important in solving the trust issues you mention.

Just because a transaction is created, and even if it is signed, it needs to be broadcast. It seems obvious, but my point is that a transaction can be started by one party, say with the inputs that are then signed by party1, then sent to the second party (i.e., not published), additional inputs can be added by party2, signed by party2, and sent back to party1 to be broadcast. Or do I have this wrong?

The first prototype I made was very thrown together to generate hardcoded transactions just to prove it would work.  I shifted to a slightly different model.  I need to pull a little bit more work into actually getting redemption working, but I'm close.  Here is the depot: https://code.google.com/r/allenpiscitello-oracle2/  I'm building on top of bitcoinj.  I haven't had a huge amount of time to take my prototype (scattered through a big mess of stuff on my machine, not suitable for publishing), but this should at least show some of the ideas.

As for your question about sequence of events.  Transactions do eventually need to be broadcast.  Different transactions can be broadcast at different times, so it depends which exact transaction you are referring to. You generally have it correct, you can construct the transactions and pass them around as they get funded.   This is exactly how I expect the redemption contract to work.  Oracle signs it, gives it to Party 1, then Party 1 signs it and broadcasts.  For constructing the contract itself, that's a trickier issue since there can be some exploits that Party 2 could employ to get an advantage.  For example, let's say Party 2 has a signed funding contract for the transaction.  Rather than signing and broadcasting it, he simply holds it.  He waits until the event happens (or more information is known), then he decides to fund it or discard the transaction.  If the event will go in his favor, he signs it and broadcasts for a sure win.  If it goes against his way, he simply never funds it.  Party 1's only option is, after a set amount of time, he gives up that Party 2 will ever sign it, and makes a new transaction that spends it.

I could have misunderstood your concern, but let me know if I missed the mark.

[jadair10]

Referencing the Example 1: Providing a deposit @ https://en.bitcoin.it/wiki/Contracts#Example_1:_Providing_a_deposit

Why after step#3, can't the website just sign Tx1 and broadcast it and keep the users payment?

[alp]

Referencing the Example 1: Providing a deposit @ https://en.bitcoin.it/wiki/Contracts#Example_1:_Providing_a_deposit

Why after step#3, can't the website just sign Tx1 and broadcast it and keep the users payment?

Step 3, the website does not have the transaction, they only have a hash of the transaction.  There is nothing to broadcast.  However, with the hash, he can create a chained transaction that is signed, and is only valid once Tx1 is broadcast.  But the user won't broadcast it until he gets the refund transaction back from the website and confirms its valid.

[jadair10]

For example, let's say Party 2 has a signed funding contract for the transaction.

Can't you structure your transaction in a similar fashion so that Party 2 is receiving a incomplete signed funding contract transaction (i.e., a hash)?

[jadair10]

I am confused though in the Providing a deposit example. Doesn't in step 5, "signing the contract and putting the new signature in the appropriate spot" mess up the hash that was given to the website and used in Tx2? Therefore making Tx2 invalid.

[alp]

For example, let's say Party 2 has a signed funding contract for the transaction.

Can't you structure your transaction in a similar fashion so that Party 2 is receiving a incomplete signed funding contract transaction (i.e., a hash)?

Not in that case becasue it's not chained.  Both parties would need to provide inputs to the transaction.  There might be a way to do a more complicated merged transaction with ANYONE_CAN_PAY options, I haven't looked into it much.

I am confused though in the Providing a deposit example. Doesn't in step 5, "signing the contract and putting the new signature in the appropriate spot" mess up the hash that was given to the website and used in Tx2? Therefore making Tx2 invalid.

No, because Tx1 is final and ready to go, just unbroadcast.  Signing Tx2 might mess up the hash of Tx2, but no one cares, since it isn't required for anything yet.  Only if you want to chain on the end of it ahead of time.

[jadair10]

Why can't you chain it?

[alp]

Why can't you chain it?

I am not sure how you would propose doing such a thing, or what benefit it would provide.  Can you elaborate on what you have in mind?

[jadair10]

Reading between the lines I have come to the conclusion that to "broadcast" means to broadcast the transaction, not the hash of the transaction. Let me think.

Why is Tx1 signed twice? And correct me if I am wrong, by the same user. Is it just to make it so that the website doesn't broadcast it?

[alp]

Reading between the lines I have come to the conclusion that to "broadcast" means to broadcast the transaction, not the hash of the transaction. Let me think more.

Yes, broadcasting a transaction will generally mean sending it to the entire bitcoin network, not broadcasting to a single member.  Hashes are useless for the network, but a transaction will be relayed if valid (and standard usually is a requirement with the satoshi client), and discarded if invalid (not enough inputs, not signed properly, etc...).

[jadair10]

It is possible the oracle may not be available to adjudicate the event, may refuse to sign a transaction, or may hold the funds hostage.  In this case, a refund transaction can be created on the contract output to return funds.  The lock time can be set to a few days after the event should be completed, and the sequence of the input set to 0.  When the event occurs, a new transaction can be created with a sequence of 1 on the input and a lock time of final.

Why do you say this (i.e., "it is possible the oracle may not be available to adjudicate the event, may refuse to sign a transaction, or may hold the funds hostage")? My understanding of an "oracle" is that it will make a decision one way or another in an automated way, an application.

Also, why can't the oracle see if both parties actually did fund their respecting funding transactions? It is an oracle.

[alp]

It is possible the oracle may not be available to adjudicate the event, may refuse to sign a transaction, or may hold the funds hostage.  In this case, a refund transaction can be created on the contract output to return funds.  The lock time can be set to a few days after the event should be completed, and the sequence of the input set to 0.  When the event occurs, a new transaction can be created with a sequence of 1 on the input and a lock time of final.

Why do you say this (i.e., "it is possible the oracle may not be available to adjudicate the event, may refuse to sign a transaction, or may hold the funds hostage")? My understanding of an "oracle" is that it will make a decision one way or another in an automated way, an application.

Also, why can't the oracle see if both parties actually did fund their respecting funding transactions? It is an oracle.

You are correct the oracle will automatically sign transactions based on external states.  I don't follow what you mean by "see if both parties did fund their funding transactions".  What funding transactions do you mean?  Why does the oracle care?

[jadair10]

What funding transactions do you mean?

The ones you list here:

http://s21.postimg.org/ezz2amc5z/Oracle_Contracts.png

Why does the oracle care?

So the oracle can solve the issue you listed:

However, this is still vulnerable to another exploit where one party refuses to submit their funding transaction after the other submits, making the contract transaction invalid and leaving the coins unspendable (the inputs will contain a transaction that does not exist).

At least I think.

Rather than tossing the funding transactions into a "shared address" why not keep them separate? I am thinking chained oracle transactions if you know what I mean.

[alp]

Party 1 needs a way to ensure that Party 2 will actually fund a contract.  The reverse is true as well.  The exploit is, one party could fund it, the other could sit and wait until he knew the result, and then decide to fund it then.  The shared address is a way of locking up the funds so that they cannot be double spent without both parties consent.

What do you mean by keep them separate?  Party 1 and 2 send the proper funds to an address that each controls respectively (and possibly does not broadcast it).  They share the hash of each transaction, allowing a contract transaction to be created and signed.  The oracle has zero involvement up to this point.  Party 1 only wants to sign that contract if it knows that Party 2 will broadcast his funding transaction in the immediate future.  Party 2 wants the same from Party 1.

So pretend Party 1 is devious.  He has a transaction hash ready, he creates the contract transaction with the proper input from party 2, the proper output, and he gives it to Party 2 to sign.  Someone must sign first.  It *may* be possible to find a trusted third party that can merge a transaction.  I do not know if this is technically possible (it's a bit unclear to me which parts of a transaction are actually signed, but I believe the input signatures are *not* included.  That's something that might be improved upon).  You still need a trusted third party to take half-signed transactions and merge them together.  The method I describe reduces the need for that.


You have the following procedure:
1)  Party 1 and Party 2 each create a funding transaction to the shared address.  They can tell each other the hashes of each transaction so that a contract transaction can be formed.  The contract transaction is only valid if both parties actually broadcast their funding transaction.
2)  Once the contract is created and signed, so long as the funding transactions are broadcast and included in the blockchain, the contract is valid.  But party 1 and party 2 cannot trust each other to carry this out.  Which is why the refund is needed.  If either party fails to fund their transaction by a specific time or block number, the contract is cancelled and funds are returned.  This prevents either party from being able to back out of the bet in case of a loss, but enter the bet if he will win.  There is a small delay here, so this is not ideal for things that can change very rapidly (faster than blocks are confirmed and transactions added).
3)  Each party gets a refund transaction with a lock time and a low sequence number.  This transaction is intended to be replaced by the contract transaction.  The purpose of this is to ensure that if either party tries to delay entering the contract, he is automatically refunded and the contract is cancelled.  If either party does not fund the contract in time, the refund is broadcast, and the contract now is invalid and cannot replace the refund transaction.  If the contract is funded before the lock time of the refund, either party can then broadcast the contract.  If a party tries to issue the refund before the lock time and the other party broadcasts the valid signed and funded transaction, the higher sequence number of the contract will win.

I'm not sure how the oracle would be involved here.  The oracle can certainly know a contract was funded properly (although he doesn't have to, because this lets you test the oracle to sign bogus transactions).  But it won't know if either party pulled an exploit on the other where he tried to fund only after having a sure win.

[jadair10]

The method I describe reduces the need for that.

but your method has flaws as you admit. I am just trying to help you find away around the flaw by asking questions and thinking differently about the problem.

I'm not sure how the oracle would be involved here.  The oracle can certainly know a contract was funded properly (although he doesn't have to, because this lets you test the oracle to sign bogus transactions).  But it won't know if either party pulled an exploit on the other where he tried to fund only after having a sure win.

I just joined a tennis league. And at each match each player brings a can of unopened balls. So there is two cans of unopened balls; these represent the two (2) funding transactions in your case. We open and subsequently play with one can of balls and the loser of the match gets to keep the used balls and the winner gets to keep the unopened can of balls.

We do not open both cans and mix them up and try to decide later who gets which balls. Because what if both players brought cans of balls and player1 removes the pops his can open and then finds out that player2 brought a can, but the can was already opened. Sounds kinda like your dilemma. Well this is easy to solve. Check the cans before you play. If the cans aren't up to code, then everyone takes the can they brought and goes home. This is what I am suggesting to you.

Inside each of the funding transactions, add an oracle script to go and check that the other persons funding transaction exists and is as expected. If not, then return funds. If an oracle can check who the 2016 World Cup Winner is, it can certainly check to see if a certain set of transaction took place. Yes?
 

[alp]

I don't really understand how your mechanism would work.  Perhaps you might want to go into detail in what you are proposing.  What are the inputs and outputs of each transaction in your scenario?  What are the contents of the scripts that are non-standard?

[Mike Hearn]

I think it's important to have a good understanding of the Bitcoin protocol before trying to understand contracts. jadair, I suggest you read up on it so you aren't confused by things like the distinction between transaction hashes and transactions themselves. Then the scheme may become clearer.

[jadair10]

I think it's important to have a good understanding of the Bitcoin protocol before trying to understand contracts. jadair, I suggest you read up on it so you aren't confused by things like the distinction between transaction hashes and transactions themselves. Then the scheme may become clearer.

Will do.

Mike, can you shed some light on alp's statement listed below specifically as to which parts of the transaction are signed. I believe the answer can be found in the image below.

So pretend Party 1 is devious.  He has a transaction hash ready, he creates the contract transaction with the proper input from party 2, the proper output, and he gives it to Party 2 to sign.  Someone must sign first.  It *may* be possible to find a trusted third party that can merge a transaction.  I do not know if this is technically possible (it's a bit unclear to me which parts of a transaction are actually signed, but I believe the input signatures are *not* included.  That's something that might be improved upon).  You still need a trusted third party to take half-signed transactions and merge them together.  The method I describe reduces the need for that.

https://en.bitcoin.it/w/images/en/e/e1/TxBinaryMap.png