Bitcoin Forum

I was intrigued by Mike Hearn's idea for Oracle Contracts (https://en.bitcoin.it/wiki/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.

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

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.

http://s21.postimg.org/mrfs96gbb/Oracle_Contracts_1.png

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.

http://s21.postimg.org/53xzaz6dz/Oracle_Contracts_2.png

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.

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


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.

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.

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)?

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.

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.



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.

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?

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?

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...).

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?

The ones you list here:


So the oracle can solve the issue you listed:
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.

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.

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 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?
 

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?

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.


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

Which parts of a tx are signed is covered in the theory section of the contracts page:

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

Let me know if you find that unclear.

Mike, in Example 1: Providing a deposit,  it is unclear when and where/what (i.e., input or output) is to be signed. I've deduced that in step #2, the user is not suppose to sign the input or the output except with zeros; making it impossible for the website to broadcast it. And in step#4, the website is suppose to sign the output of Tx1 and input & output of Tx2. And in step #5, the user replaces the zeros on both the input and output in Tx1.

Or did I miss something?

You sign a previous output when you spend it.  An output from Tx1 is an input in Tx2.  You need to sign it in Tx2.  Signing an output in Tx1 is not a concept that exists.

Step 2 reads:
"The user creates transaction Tx1 (the payment) putting 10 BTC into an output that requires both user and website to sign, but does not broadcast it. They use the key from the previous step for the site."

Regarding oracles there is a much simpler way to implement them that doesn't even need to require interaction with the oracle or signatures.

Suppose I'm an oracle who will attest to whether or not the Steelers won the 2014 Superbowl. I say that if they do win, I'll make public some nonce, nSteelersLose, and if they win, I'll provide another nonce, nSteelersWin. In the meantime I make public the values of H(nSteelersLose) and H(nSteelersWin) upfront. (where H(d) is some cryptographic hash function)

Now Alice can make a bet with her friend Bob as to whether or not the Steelers win. (Alice and Bob are such committed Steelers fan's that they are sure they'll make it to the playoffs) They jointly author a transaction with two inputs, one from Alice, and one from Bob, and a single output. That output has the following scriptPubKey:

HASH160 H(nSteelersWin) EQUAL
IF
    <alice-pubkey> CHECKSIG
ELSE
    HASH160 <nSteelersLose> EQUALVERIFY
    <bob-pubkey> CHECKSIG
ENDIF

If the Steelers win, the oracle will publish nSteelersWin and Alice can spend the output with the following scriptSig:

signature nSteelersWin

If the Steelers lose on the other hand, only Bob can spend the output:

signature nSteelersLose 0

What's really nice about using hashes rather than signatures is that it's scalable: there could be a million Alice's and Bob's making these bets, and the oracle doesn't have to even know. The oracle can also attest to as many different teams or conditions as required, or there could even be multiple oracles. For instance I could also bet that the Steelers will win and the Democrats win the next election and Canada is invaded by the United States:

HASH160 H(nSteelersWin) EQUAL
HASH160 H(nDemocratsWin) EQUAL
AND
HASH160 H(nCanadaInvaded) EQUAL
AND
HASH160 H(nSteelersLose) EQUAL
OR
HASH160 H(nDemocratsLose) EQUAL
OR
HASH160 H(nCanadaNotInvaded) EQUAL
OR

Of course, Alice and Bob might also want to be protected in case the oracle fails. For instance the oracle might go out of business and stop publishing. But they can modify their script so that Alice and Bob can also mutually agree to a different set of conditions at any time:

HASH160 H(nSteelersWin) EQUAL
IF
    <alice-pubkey> CHECKSIG
ELSE
    HASH160 <nSteelersLose> EQUAL
    IF
        <bob-pubkey> CHECKSIG
    ELSE
        0
    ENDIF
ENDIF
IF
    1
ELSE
    2 <alice-pubkey> <bob-pubkey> 2 CHECKMULTISIG
ENDIF

(FWIW there's lots of ways to make these scripts shorter)

They can sign a transaction in advance that is timelocked so that even if one or the other party is unavailable, if a month after the Superbowl is supposed to happen the oracle still hasn't published either one can trigger the backup condition and cancel the bet and return the money. It's even possible to handle the oracle revealing both values, either accidentally or maliciously, by setting up inputs spent by timelocked transactions to effectively cancel the bet, but that gets complex...

Finally if the oracle can be directly involved in your transaction you can simplify all of this by asking the oracle to commit to a contract. Basically the contract just outlines exactly what the oracle is attesting too, whatever that is, and the oracle promises to reveal specific nonces for specific outcomes. The oracle does not need to sign transactions and the oracle can simple publish the correct nonces in a public place when the event is triggered.

This also means that the problem of making sure the oracle is honest with challenges is irrelevant. Honest is just a matter of what values the oracle publishes and has nothing to do with transactions at all. For that matter, the oracle doesn't even have to know anything about Bitcoin at all: all the oracle does is make promises to make public certain short bits of data if certain events happen.

I need to look at this closer but I had a similar thought when looking at this, and dismissed it thinking it couldn't protect against the losing party using the signed nonce condition against him, but it really looks like your scripts are better for this.  I may try playing around with this and see if I can get it to work and what the implications are.

Thanks for your contribution!

Obviously the nonce would have to be a pretty large data set, as you could just hash over all possible values and figure out how to spend it.  That seems like the only concern I can think of- someone could just brute force this to figure out what the nonce was.  I'm not sure if scripting allows for checking that a signature matches on some arbitrary set of data, but it seems like you could have an issue there where someone could brute force attack until he finds one that matches, then cashes out the bet prematurely.

Your questions are coming from fundamentally not understanding how transactions work.  If you are interested in that, start a new thread, ask questions or read the link Mike sent.  Once you are up to speed, apply that knowledge to the topic at hand.

outputs are future inputs.  That's the simplest thing.  Outputs can be spent by inputs that sign transactions.  Read the transactions wiki page, read it again, then read it a third time.  Then start a new thread if anything is unclear.

Glad to help.

EDIT: Keep in mind that all the transactions I outlined above are considered non-standard and thus are hard to actually create or spend on mainnet. (testnet disables the IsStandard() test) For something that can actually be used right now you'll need to use the CHECKMULTISIG version of the protocol and make the oracle be interactive. The wiki for some reason has a <digest> OP_DROP in the scriptPubKey; use the following instead:

2 <alice> <bob> <oracle * H(contract)> 3 CHECKMULTISIG

The * represents ECC multiplication, and deterministically derives a pubkey from the oracles main one; read about Timo Hanke's pay-to-contract (https://www.youtube.com/watch?v=qwyALGlG33Q) stuff for how that derivation works. I'm sure he'd be interested in an implementation of his work, he might even have code for it.

You'll also want to use P2SH (https://en.bitcoin.it/wiki/BIP_0016) so that the money is sent to an actual address and the protocol is compatible with any wallet software, and hardware wallets. (or I should say, will be compatible as multi-sig wallet software is developed) Most of the Bitcoin developers are of the opinion that non-P2SH scriptPubKeys should be eventually banned so take that into account; P2SH works with the pure hash-based versions of all of the above too.


Well this is a basic cryptography question actually: How big should your digest be?

If you don't already know the answer you probably should read more on cryptography; I recommend the book Practical Cryptography (https://www.schneier.com/book-practical.html).

The short answer to your question is use a nonce as big as the digest produced by the hash function, and a 160bit nonce, or 20 bytes, is fine; that's a big enough nonce to make these transactions just as secure as any standard transaction. But really you read that book so you understand why I'm right.

I didn't ask a question. I simply quoted the wiki (i.e., I am trying to identify my area of confusion). Thanks for the feedback though. Sorry about the thread diversion. It seems you're getting some good feedback now.

retep - Thanks for the post.  I'll need some time to digest to see how to modify my approach based on this.

This should simplify how oracles work quite a bit (and give them some plausible deniability if an oracle service just published nonces for various events).

I'm going to toy around with things a bit and see if I can implement what you proposed.  It is quite promising.

The standard/non-standard transaction stuff is something I am aware of, I've been working with non-standard transactions on testnet, so this is not terribly new for me.  I'd like to see if I can find something general purpose and simple enough to get traction to be added as a standard transaction if needed, but a good case would have to be made.  The <data> OP_DROP <standard tx> proposal already exists, so it was easy to piggy back on that.  My first implementation had a complex script similar to what you described in your first post, and Mike suggested I move to the other script.  A standard transaction that would work would be far superior, of course, because I wouldn't have to convince anyone, or wait on nodes to upgrade.

Can you explain in slight more detail where I would use P2SH?  In particular, which transactions would need to be modified for that to work?  I presume the contract transaction.  The redemption transaction is already a standard output, so that wouldn't be needed.

When you say the oracle needs to be interactive, I presume that means the oracle needs to sign the transaction because we would have to make a non-standard transaction otherwise?  And the benefit of using the Multisig here (compared to drop) is its standard?  And we basically need to compute a public key for the oracle based on a contract expression?  Then we sign the redemption contract ourselves, and have the oracle sign it (assuming he agrees with the contract and its payout).

I'm looking pretty long term, so I'd like to design for the best architecture long term and push for those features to be standardized and relayed.  I'm not in a hurry to make this work on anything other than testnet for some time.

Indeed... "If <politician> dies, I will make public n such that H(n)==0x4a5e1e4baab89f3a32518a88c31bc8"

Incidentally, keep in mind you can do "multisignature" oracles easily:

HASH160 <H(nonce1)> EQUAL
HASH160 <H(nonce2)> EQUAL
ADD
HASH160 <H(nonce3)> EQUAL
ADD
1
GREATERTHAN


Actually they're both considered non-standard - spending a non-standard transaction makes the transaction non-standard too, see AreInputsStandard()

P2SH is very general: basically the idea is that for any transaction output rather than storing the scriptPubKey itself, store the hash of that script and provide the script when you spend the transaction. This keeps the UTXO set size small - very important - and in this case provides even more plausible deniability for the oracles because they can't see the scripts making use of their service at all until they're spent. For that reason alone I'd strongly recommend you only use P2SH outputs. bitcoinj doesn't support P2SH fully (Mike's been against the idea for ages) but the part that was left out, calculating addresses and the like, is just a few lines of code.

There is one disadvantage to P2SH: your scriptPubKey must fit in 520 bytes due to the limit on the size of any individual PUSHDATA payload. Probably not a big deal - that's a lot of conditions.

In the future we'll probably eventually implement an even more advanced version of P2SH known as merkelized abstract syntax trees. (MAST) Basically the idea is to take the AST of your script, and hash every node, very similar to what is done in a merkle tree. Then when your script is executed, rather than provide the full script, replace branches that aren't executed with the digest of that part of the tree. It'll make stuff like this much more efficient because even if you have a crazy complex script with tonnes of possible branches, you only have to include the code that actually runs when you spend the txout.


That's all correct. The reason you'd want to compute a derivative pubkey is to make it clear exactly what contract is being committed too; it's optional but a good idea.


Yeah, I wouldn't shy away from non-standard transactions myself. You've got an application where the scripting system has very real advantages, and it's also not important for those transactions to be mined immediately. Non-standard just means that nodes using the reference implementation won't relay the transactions, and won't mine them; non-standard doesn't ban such transactions entirely. Eligius will mine non-standard txs for instance. (although lately something seems to be wrong with the submission process) Instructions here: https://en.bitcoin.it/wiki/Free_transaction_relay_policy Patch your bitcoind with Luke's nonstdtxn patch: https://github.com/luke-jr/bitcoin/tree/accept_nonstdtxn

Did you have to use that example?  ::)  Disclaimer: Bitcoin leaks a lot of information, don't do these.

Heh, of course even just being an oracle for stock prices is probably enough to raise interesting legal questions...

MASTs make a lot of sense.

bitcoinj lacks all the code to do P2SH, it's not even partially implemented. You need to be able to store the scripts in the wallet, the wallet needs to add them to the bloom filter, etc.

The original oracle proposal used scripts that resulted in signing transactions for a few reasons. One is that way you can split up the output values in fractional way rather than it being a binary claim/not claim on an output. For the "when a grandfather dies" use case it makes no difference of course, but for things like bets on currency movements it probably does.

Another reason is that you want to be able to process arbitrary data, like by downloading a web page. Otherwise your oracle has to be specifically programmed to know about every possible kind of event, which sucks. Now, what the hash-checking scripts design does is let you have an arbitrary program structured like this:


and then your oracle script API knows how to manage the hashed nonces behind the scenes.

Oh, a final reason is that the signing based design lets the oracle be basically stateless. Done the above way, the oracle needs to store the nonces and not lose them. It's a relatively minor thing, I think.

The wiki protocol was written years ago, before I knew about the point multiplication trick. I think it does indeed make more sense to do that than use OP_DROP.

This is a nice set of improvements. Does someone want to refresh the wiki article, or shall I do it?

Mike,

If you could update the wiki, it would be great, I bet it is more clear what needs to be changed to you than me.

One thing about the oracle being stateless, I am considering that right now, where the oracle is split into two entities.  One that will provide external state, and one that will validate it.  The desire for a stateless oracle is nice, but somewhere a state is needed to be maintained (obviously this could be google, a sports website, etc...), I'm just not sure it's as convincing of a use-case and maintaining the nonces seems like a trivial problem.  There's a security risk, but keeping the nonces offline and only transferring when needed could at least give some security.  Splitting the oracle into a "news service" and a signing service shifts the problem around, and it could make the script simplify to "go check this news service with this event and go get its nonce.".  Oracles can be dumb and maintain no state, although the burden just shifts.  But in this case, you pretty much eliminate for the oracle, since you program the hashes of the nonce right into the script.  Maybe there's a use case for both?  When you can easily automate it into a script, the script method, for simple events that will be published in a known way that publishes nonces, use this other way.

retep,

Re: the derivative pubkey, I assume this is mechanism serves a similar purpose to the expression hash in the original proposal?  The oracle doesn't want to sign a transaction unless he agrees it should be paid out, and he has no idea what the contract was if he doesn't have a derivative pubkey to use.  He can validate that the derivative key was in fact the one that should be generated by the original contract.  But if we go with the nonce idea, this all isn't important because oracles become naive to transactions.  Do I understand this correct?

I'll update my proposal based on Mike's changes to the Wiki and make sure I have everything correct before working any more on the code.

Mike: good point about the escrow version of the oracle being able to change output amounts; it's yet another reason why a future scripting system upgrade should allow for spending transactions to be constrained by the script itself. Go ahead and update the wiki.

re: state a nice trick with these oracles is to have a master secret key and use HMAC to calculate the nonces. For instance if I promise to release nonces for the statements "The Steelers won the 2014 Superbowl" and "The Steelers did not win the 2014 Superbowl" I can calculate those nonces with H(master-key, H(statement)), which means I only have to backup one key safely with high security, the backups for the statements aren't as sensitive. It'd be ideal to make all of this into an easy to use standalone app so the oracle could have a dedicated off-line laptop where they type in their statements and nonces and H(nonce)'s are generated securely as needed. Overkill for some applications, but for important stuff that kind of security is worthwhile.

Maps quite nicely to the scripting case too:


where reveal() returns H(secret + H(H(script) + H(statement))) - add a second layer of indirection to what reveal does make it easy to calculate H(nonce)'s in advance with some kind of statement table or something attached to the script.

Note that if the oracle needs to make money for their service, the statements can just as easily be "Alice and Bob: The Steelers won the 2014 Superbowl".


alp: Yup. Listen to Timo's talk on contracts, it's a very clever mechanism and he's done a good job of fleshing out all the details. That said at this point I really think the hash-based mechanism is the most interesting one in that the infrastructure on the oracle's side can be incredibly simple and robust - just what you want to make people confident enough to take on that role. I'd be a lot more hesitant to be setting up an exploitable automated signature signing thing myself until the code was validated much more carefully.

Regarding non-standard transactions you can dodge the problem: have Alice and Bob first jointly create a standard 2 <alice> <bob> 2 CHECKMULTISIG txout. Then jointly spend that txout to the oracle scriptPubKey with a second transaction, but don't broadcast it. (optionally set nLockTime so it can't be broadcast until closer to the date the oracle will release their nonce)

Now when the oracle does release the nonce, if Alice and Bob are willing to co-operate they can just spend that first tx to whomever won the bet. (might as well give whomever party lost the small amount that would have had to be spent on transaction fees to get the larger oracle tx mined as a token of thanks) If either party isn't willing to co-operate, or can't, then use the already signed oracle script as the backup method to complete the transaction.

You only need the non-standard transaction as a backup basically - usually Alice and Bob might as well co-operate given who will get the funds in the end is a foregone conclusion anyway. The advantage is that now even after the transaction has concluded the oracle can't know if their nonce was used at all unless the backup tx has to be used, and it means you can reasonably implement the system now even though the transactions are non-standard.

Another way to process arbitrary data is to regularly publish a list of questions
and ask miners to act as arbiter by encoding a few extra bits per block. Vanitygen abuse perhaps?

Assuming it's about typical general interest prediction market stuff like
Dems win/Reps win, BTCUSD higher/lower than last year, major city nuked/not nuked, etc.

What percentage of pools, and miners voting by proxy, would participate?
Can be a small minority, just significantly more than those who would actively sabotage it
and you have your oracle built directly into the client with no need to access outside data sources.

I had a similar idea, might even be an alt-coin with this type of thing, but there needs to be an incentive to give the right answer.  Kenneth Massey (he has a ranking system used in the BCS for college football), has a weighted ranking system where he takes inputs from anyone, and if they don't correlate well to everyone else, they are not weighted as heavily.  Perhaps you cold have a system where pick what event actually happened, and if they answer with the majority, they get rewarded from any saboteurs and any fees that people betting might pay for arbitration.  Still not sure how it would work, maybe some alt-coin just for answering events whether they occur or not?  Might be a lofty goal for down the road, I'm sure someone smart can come up with a way for this to actually work if its possible.

Alp: This work looks really interesting. I'm also excited how Peter figured out how to use the nonce-based way of implementing it to protect savings accounts in wallets (http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02601.html), really nice work!

Between these two uses, and existing uses for multiple CHECK(MULTI)SIG's in a scriptPubKey, I think it makes sense to create a whitelist for opcodes least likely to cause us problems and allow them in serialized scripts for use with P2SH. That removes the UTXO bloat problem of allowing anything, and limits the risk from opcodes we haven't implemented correctly. (I left out arithmetic from my initial whitelist, just boolean AND and OR for now) I posted my full proposal to the bitcoin-development email list: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02606.html

You should post your thoughts to the list, especially to figure out if the restriction to just boolean opcodes is ok for the first trials. I think it is, we can always extend it later, but if you have a really good argument for arithmetic make your case. Just remember that there have been some serious bugs found related to arithmetic before, so IMO playing it safe initially is a good idea.

I was able to switch to using the nonce-hash script and it so far has gone very well.

I had some questions about P2SH, though.  Here is the example used for it:
scriptSig: [signature] {[pubkey] OP_CHECKSIG}
scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

If I understand how the script processing works, you push all of the scriptSig onto the hash, then start processing the scriptPubKey.  I presume that the {[pubkey] OP_CHECKSIG} in this example is a single piece of data that is pushed onto the stack, and not the actual operations.  It's a bit unclear to me.  So assume its just data.

We end up with the stack as:
{[pubkey] OP_CHECKSIG}
[signature]

Then we get the hash operation, which will replace the top item on the stack with the 20-byte-hash of that data.  So the stack is now:

[hash]
[signature]

We add another hash that should match:

[hash]
[hash]
[signature]

Then we get OP_EQUAL, and the top two items are equal, so we have
1
[signature]

on the stack, and it's valid.

This makes it seem like the signature is not needed at all.  I must be missing something.  What is evaluating the script that's part of the scriptSig?

P2SH is implemented as a special case in the VerifyScript() routine:

// Additional validation for spend-to-script-hash transactions:
if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
{
    if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
        return false;            // or validation fails

    // stackCopy cannot be empty here, because if it was the
    // P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
    // an empty stack and the EvalScript above would return false.
    assert(!stackCopy.empty());

    const valtype& pubKeySerialized = stackCopy.back();
    CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
    popstack(stackCopy);

    if (!EvalScript(stackCopy, pubKey2, txTo, nIn, flags, nHashType))
        return false;
    if (stackCopy.empty())
        return false;
    return CastToBool(stackCopy.back());
}

So what that does is if the scriptPubKey has the exact magic P2SH format, there are actually two scripts that run, three if you include the scriptSig: first the scriptSig is evaluated as it normally would be, creating a stack. A copy of this stack is made, called stackCopy. Then the scriptPubKey is evaluated using that stack. Up to this point everything is as normally happens.

However if the scriptPubKey matches the magic P2SH format exactly the top item of the stackCopy is removed and deserialized. This is called the pubKey2, basically scriptPubKey #2. It's evaluated with what remains on the stack and if it also returns true, the whole script is considered a success.

The key that I think you missed is that P2SH is handled specially; the second round of validation logic isn't expressed in the script itself. Way back when P2SH was being designed an alternate proposal to this whole mechanism was called OP_EVAL which would have simply executed a serialized script, but it was found that OP_EVAL allowed for recursive evaluation, and loops, and people got scared enough that the code review had missed that so the decision was made to use the much more limited P2SH mechanism instead. There was also Luke-Jr's OP_CHECKHASHVERIFY proposal around that time, but that's a story in of itself.

Thanks for the quick reply.

I was digging through the bitcoinJ code and had it mostly figured out.

From my understanding, the new clients (that know about this special rule) will do an extra check, but old clients that don't treat it specially will not do the extra check, thus making a situation where an invalid scriptSig evaluation occurs would validate as correct?  And anyone trying to spend them will only end up in blocks that are mined by old clients, and those blocks will be orphaned since the majority of the network will do the extra validation.  Is this correct?

That's exactly the idea. The general idea is called a soft-fork because only miners need to upgrade to add additional validation rules making formerly valid transactions invalid; the opposite is called a hard-fork where a formerly invalid transactions or blocks are made valid, thus requiring all clients to upgrade at once. Soft-forks are much easier and safer to implement than hard-forks.

Of course P2SH is now supported by 100% of the mining hashing power now, so you won't find invalid P2SH transactions in the blockchain except in historic blocks from about a year and a half ago.

I was able to make quite a bit of progress on this and completed all the main test cases.  I need to start creating a test app and a protocol for communicating for users.

I had to make some very basic changes to the script to get it to work.  Here is a quick summary of the process that is used:

Each user drafts a funding transaction that goes to a 2 of 2 mulitisig output, but does not sign or broadcast it.

Each user sends the draft to each other along with a refund transaction that spends each funding transaction by sending it back to its owner.  The other user signs this transaction and sends back the signature so each user has a way to get their money out of the 2 of 2 multisig output in case the other user never signs and broadcasts his funding transaction.  The refund transactions have a sequence number of 0 and a lock time of 1 hour after the current time.

One of the users also creates a contract transaction that uses a P2SH output that spends the two funding transactions.  He sends it to the other user to sign.  This transaction has a higher sequence number for its inputs and a final lock time, so it should replace the refunds once it is signed and valid.  After both signatures are added, this transaction can be broadcast.  The script for the output is as follows:

OP_RIPEMD160 OP_DUP [trueNonceHash] OP_EQUAL
OP_IF
 OP_DROP [trueUserPubKey] OP_CHECKSIG
OP_ELSE
 [falseNonceHash] OP_EQUAL
 OP_IF
  [falseUserPubKey] OP_CHECKSIG
 OP_ELSE
  2 [trueUserPubKey] [falseUserPubKey] 2 OP_CHECKMULTISIG
 OP_ENDIF
OP_ENDIF

It's a slight modification of the one retep suggested.  To spend it, you have a few options.  If you can cash it in alone because you know the nonce values, need to add the nonce and your signature to the scriptSig.  If you want to redeem it with the mulitisig option (for example, if the oracle disappears or you wish to have an early buy-out), you need to add a scriptsig of 0 [trueUserSig] [falseUserSig] 0.  The first 0 is there to get hashed by the RIPEMD160 function and not be equal so we get to the final else case.  The last zero is there to account for a bug in checkmultisig that pops an extra item off of the stack.

Users can automatically create the "no oracle refund" ahead of time as well, and set a lockTime on the transaction of well past the event (say a week) in case the oracle cannot be found, and set it with a 0 sequence number on the input.  Then the transaction is replaced by anyone who can redeem it.

I've only run basic unit tests on this code so far, need to clean it up a bit before publishing, but plan to start making a very basic app for testnet to actually start publishing some transactions and seeing if this works.  If it does, I'll try to start working on the protocol and possibly some demo websites that anyone can use (on testnet for now).

Recall that transaction replacement doesn't work. Sequence numbers are essentially useless on todays networks.

I need to understand exactly what the limitation is.  My understanding is the network won't even relay anything that has a timelock < currenttime.  In this case, the sequence number doesn't cause any issues, as the transactions are ignored, since every sequence 0 is timelocked.  The sequence number is used just in case the network starts relaying these transactions (and supports replacement).

Unless I am way off on how what the limitations are.

No, your understanding is correct. You were talking about replacements and so on without mentioning that, so just wanted to double check.

FWIW if you happen to be in Toronto tonight I'm giving a talk about one-time-password wallet protection which will also include information about the oracle application. My apologies for the 2.5 hour notice; it's rather last minute because I was called in to substitute for a different speaker.

http://www.meetup.com/Bitcoin-Toronto/events/130155842/

alp: I'll look at your design more later. In the meantime replace your use of RIPEMD160 with HASH160 - you want these scripts to have the same security as standard scripts, and HASH160 adds an additional SHA256 step which makes a flaw in RIPEMD160 less likely to cause problems. More importantly, you are using P2SH which already depends on HASH160, so there is no reason to use a mechanism that could have a different flaw thus making you vulnerable to two types of flaws rather than just one.

I am agnostic to the hashing algorithm used, so I can easily switch.  The only reason I used RIPEMD160 is I had some test cases that I ran through an online hash webpage that used RIPEMD160 and it let me calculate the hash values independently.

I'll change the code when I get home, but I just need to calculate the nonce hashes using that algorithm, which I believe should be pretty easy to do using the same webpage I used to calculate the nonce hashes.

If you have any notes from the presentation, I'd be interested in seeing how it applies to the oracle application.  I'll likely try to present something to our local meetup group in the future.  It's a tough balance to tread between being overly technical and simplistic with these audiences.  I think it would be a lot better to have a sample app that people could use to play with and really touch and feel.  In the mean time, I might try to put together some type of youtube video that shows how it might work in action.

I probably should have mentioned it.  I'm glad I understood it correctly, it's one of those things I was a bit shaky on.  From my understanding, everything should work as expected with both the way everything is currently set up and should continue to work even if transaction replacement is enabled in the future.

Cool, just don't forget to change it prior to releasing your beta!


Will do.

One reason I wanted to present sooner rather than later was to hear from people who might actually use the software, both oracle and wallet protection. It'll also help get a feel for what explanations work; I've actually got a fine arts degree and used to make electronics-based art so I've got years of experience explaining technical ideas to the public and really enjoy doing it. I want to use the wallet-protection application as a way to lead into explaining the oracle application.

I'd really like to make some type of youtube video animated presentation on it with voiceovers and all, but that is completely new territory for me, so I may have to settle for something basic.  Although the test app is much more important to have for people to play with.  I've made a lot of progress quickly with the prototyping, but making a real app, even if a bit clunky and ugly, will be more work, especially since I'm just working on this stuff only a few hours a week in my free time.

I have updated my repository with the latest updates, including using OP_HASH160 instead of OP_RIPEMD160:
https://code.google.com/r/allenpiscitello-oracle2/

I still have a substantial effort to clean up the code and actually put most of the contract and redemption creation as part of the standard library rather than as a test case, but I expect to start on that shortly and actually integrate it.  Then on to the protocol and test application!

One drawback with this approach is the lack of ability to have a proportional payout (e.g. a Bitcoin mining difficulty contract that pays out proportionally based on how close to 100M difficulty the next difficulty will be), but I thought about it a bit more and it at least is possible through having multiple outputs on the contract that kick in at different conditions. It's not entirely as flexible as a purely proportional payout, but you could have it in steps and get virtually the same effect:

For example, rather than betting if the next difficulty increase will be over 80,000,000, you could have a contract that pays proportionally at 10,000,000 increments.

You collect 1BTC from 2 people betting, and then make 10 outputs for example.  Each output will pay to Party A if the difficulty is above 10M*(N+1) (where N is the output number).  If the difficulty ended up being 92M, then the first 9 outputs would pay to Party A, and the last one would pay to Party B.  So you get a close-enough proportional contract in this.  The downside of this is you have 5x as many fees for redeeming as a pure proportional, and it's still got some big chunks.  I'm not sure that's a big enough concern, and of course, a transaction aware oracle could be introduced to handle such cases.  I'm a fan of keeping it simple, and until that becomes unfeasible, or there becomes demand for it, stick with the simple case.

I am starting to test throwing some basic external state contracts into the testnet blockchain.  I ran into a minor issue with testing, but I think it's due to sequence number not working quite like I thought.

I have TX1, TX1Refund, TX2, TX2Refund, and ContractTX.  TX1 comes from user 1, TX2 comes from user 2.  TXRefund spends with a timelock of currenttime+60 minutes and has a sequencenumber of 1 for the input it is associated with.  ContractTX takes TX1 and TX2 as inputs, but with a MAX sequence number and no timelock.

I have not been using bitcoinJ to propogate transactions, but instead sending them through the bitcoin-qt console using "sendrawtransaction".  If I send the refunds, I cannot submit the contract.  Once sequence number is fully supported, I should be able to do this.

What my understanding of the situation, without getting into the bitcoin-qt code, is that the timelocked transactions (refunds) are held in the mempool (I can see this with getrawmempool), and since sequence number is not being honored, it sees it as a double spend if I try to submit the ContractTx, so it rejects the transaction and does not relay it.  The timelocked transactions are held in the mempool but not relayed.  I likely could send a raw transaction of the contract on another client that has not seen the refunds, since they aren't being relayed (until lock time).

This is unfortunate, but not a roadblock.  I can just make the app not submit refunds until after the lock time, thus not making it look like a double-spend.

Is my understanding of what is happening correct?

The worst I can think of that will happen is someone will somehow get the contract refund tx (which expires some time after the nonces should have been published) and gets that transaction into the mempool of a lot of miners, and it blocks the correct user from redeeming the transaction.  Probably not a concern.

BTW, here are some sample transactions in the chain if anyone is curious:

Funding Transaction 1 (http://"http://blockexplorer.com/testnet/tx/95afe351496b28d7c4bc8167157506a0f9cc5cc14ace8da1b05439403ec48d47#o0") - Funds from wallet 1 into multisig address
Funding Transaction 2 (http://"http://blockexplorer.com/testnet/tx/10b433a227ca8f7b75c98d3df7e1cbd529cbec613a1546bc09cc67461e0500f0#o0")  - Funds from wallet 2 into multisig address
Contract Transaction (http://"http://blockexplorer.com/testnet/tx/313897799b1e37e9ecae15010e56156dddde4e683c96b0e713af95272c38aee0#o0") - Spends funding inputs to a redeemable location by either a) wallet 1 once nonce1 is known, b) wallet 2 ocne nonce2 is known, or c) wallet 1 + wallet2 at any time.
Contract Refund TX (http://"http://blockexplorer.com/testnet/tx/d3d77d63709e47d9ef58f0b557800115a6b676c6a423012fbb96f45d8fcef830#o1") - I made a mistake on this one and accidentally divided the fee wrong and ended up paying a huge fee and only refunding half the funding amounts, oops!  This has been fixed.  This is an example of spending with both signatures.

I suspect the issue is you're bypassing the standard logic that fails to relay timelocked transactions by using sendrawtransaction. If you used bitcoinj to send the tx, it wouldn't enter the mempools at all.

I haven't tested this theory (having two different bitcoin-qt apps could do this), but what I suspect is the problem is it's staying in my local mempool only, which will reject any transactions that it thinks are a double spend.  Since my local client doesn't understand sequence number, it assumes it's a double spend and rejects it without ever accepting it into the mempool on the local machine even before relaying it.  I'm not sure if the timelocked refund transactions ever get relayed (it's my suspicion they are not relayed until the timelock expires).

They aren't.

You have to remember that relaying timelocked transactions enables DoS attacks by just relaying a ton of transactions that will never get mined, either due to the lock being far in the future, or because you mine a conflicting block before the lock expires; to use up 1GiB of RAM on un-mined mempool tx's only requires the attacker to have ~$30k worth of Bitcoins with the current codebase. Sequence numbers have similar problems because you have to make increasing the sequence be accompanies by a higher fee for the exact same anti-DoS reasons.

Testnet however *does* relay timelocked transactions right now because that test was implemented in the IsStandard() code, which is turned off on testnet. I think it's time we change that and make relaying a timelocked tx fail on testnet too; it'll never be possible to relay timelocked transactions on the network directly due to the DoS attack risk, so we shouldn't confuse developers.

So a summary of what is happening on testnet and what would happen on mainnet:

1)  Funding transactions will be relayed and immediately* included in blocks in both networks.
2)  Refund transactions, which have a timelock and zero sequence number, are relayed in testnet, but not in mainnet.
3)  Contract transactions are relayed and immediately* included in blocks in both networks, but if a refund transaction has been relayed already, this transaction is marked as invalid since it thinks its a double spend.  Currently only a problem in testnet, since mainnet will not even relay the refund transactions.

Is my understanding correct?  If so, it seems like I only have a testnet issue, since stopping relaying of timelock transactions solves the problem of the nodes not understanding sequence number replacement (at least in my use case, where I don't have a timelock on the overriding transaction).

This can be easily solved in client software that stores transactions and only relays at appropriate times (and worst case scenario, you end up with a refund when someone submits a refund before the timelock expires, and only on testnet).

Yup, long story short: don't relay transactions you don't want mined.

Regarding sequence number replacement, it's a very flawed idea that just another variant of zero-conf transactions. It's been suggested to re-use sequence numbers for something totally different, such as gmaxwell's transaction checkpoints (https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas), so it'd be helpful if you only used the sequence numbers 0xFFFFFFFF for final transactions, and 0xFFFFFFFE for ones that are timelocked. A re-use might also include a bump in transaction version number, but it'll simplify things all the same.

On the other hand there is another version of transaction replacement called replace-by-fee. There you simply make the conflicting replacement transaction pay a higher fee, both absolute as well as in terms of fees-per-KB. Any miner has an economic incentive to include the second transaction instead of the first one provided the fee bump is high enough to account for the higher orphan risk. (may or may not be small - complex question) Counter-intuitively this can also be used to make zero-conf transactions fairly safe: https://bitcointalk.org/index.php?topic=251233.msg2669189#msg2669189

In your case it's not totally obvious if you want the refund tx to take priority over the contract one; maybe you don't? Or maybe you want the contract to take priority over the refund? I suspect the latter, in that if the contract is in a state where it can be completed, that's probably what the users want to get mined.

The refund should not take priority, in fact, it should be the other way around.  A contract should override the refund, provided the contract was submitted in the appropriate timeframe (before the refund locktime).  This is to protect users from holding a contract that has been signed by everyone but him until after the external event is known (or significant information changes), then deciding to discard it or not.  Once the contract has been signed and relayed, it should take priority, unless a refund already occurred.  Submitting the refund is an "escape" so you don't have money locked up at a multisig output that the other party might not ever free up.

Malicious users can submit a refund now before the timelock and mess things up on testnet, but that's not a big concern, because it doesn't really cause much harm for users and can be avoided in most cases.  On the main network it should be fine.  The design for this is contracts that are much longer term, so they will be stored in the blockchain and prevent double spends that way, and users will know if they need to refund or the contract went through fairly easily.

BTW your links to your transactions are broken...


Right, so make the fees paid by the refund transaction to be less than the fees paid by the contract. It's actually perfectly safe to make the refund tx pay zero fees as in the long run child transactions will be able to pay fees for their parents - at worst you'd create a second fee paying tx to get the refund mined, or just wait until you need to spend the money. (the tx can't be double-spend after all without the consent of both parties)


I noticed there were two transactions paying into the contract - you actually can have both parties create a single transaction with inputs from both and a single multisig output.

This is worth considering as a future optimization.  I'll need to look into this a bit more, and as long as what I have mostly works, I'm ready to try to fill in the major holes rather than optimize.  Unless you see some reason what I'm doing is problematic.


I'm trying to think why I didn't go that way.  I really wanted to.  I think there were two main reasons I didn't do this.  Constructing the contract was the first problem from what I remember, mainly it would have taken a major effort to refactor the bitcionJ code to be able to only partially fund a transaction.  I hadn't looked at the code that closely, so I could have missed an easier way to do this, and I certainly understand it better now, so it might be worth revisiting.  But the second reason is that I couldn't find a way so that one party had a signed copy without the other party having it.  With the refund transactions idea, it might be possible to use doublespend to prevent this from happening.  This again could be a shortfall of me being creative enough to come up with a good handshaking scheme.  I tried quite a lot of different schemes with anyone-can-pay signing, SIGHASH_SINGLE, etc... but always fell short.

The basic scenario is this:
Party A constructs the TX with his input and an output and funds it (but doesn't sign it).  Party B needs to add his input, sign it, send it back to A to sign, then relay it.  Party B does this, then A doesn't sign until the event occurs, then he decides to discard or not.  In this case, Party B could just double-spend the input to get his money back since A didn't publish fast enough.  So I think the double-spend solution is the way out of it, which is pretty similar to above, so that means I must have chosen to do it this way since it was hard to work with the wallet to figure out what outputs to use, and to only fund to a certain amount.  That probably is the way to go in the future, I just need to refactor some of the bitcoinJ code to handle this use case.  If there is a way to do this that I couldn't find, I'd love to know about it.  Otherwise, it's at least functional as a proof of concept while I go work on other parts of this (network protocol and wallet extensions to save these transactions and relay after lock time is the next biggest chunk).  I can always revisit these areas once I have something functional.  My goal is to have a sample app ready within a month or two that I can have a way for peers to interact and lock up transactions this way.

Just an update, I got the redemption transactions into the blockchain:

This is one that went to the 2nd person:
2nd party redeems contract (http://"http://blockexplorer.com/testnet/tx/9b04a657a189a31e76073d0b35868060f13399bb8074d28d80730a7648decdfc#o0")

1st party redeems contract (http://"http://blockexplorer.com/testnet/tx/3da75972766f0ad13319b0b461fd16823a731e44f6e9de4eb3c52d6a6fb6c8ae#o0")

You'll see I used the ever-so-creative nonce's of 1 and 2 to create the nonce hash values, and redeemed them with the correct value.  the signature is [sigwinner] [nonce] [script].

You know, I just realized something: for every one of these cases it's better if the oracle reveals a seckey to a pubkey than if the oracle reveals a nonce. First of all, it means the oracle can prove they really do have the seckey by just signing a message, and secondly the two participants can take the oracles pubkey, and do an ECC multiplication with another pubkey that the two participants jointly agree on. Now they have a pubkey for which the seckey can only be found if the oracle reveals the oracles seckey, but looking at the blockchain there's no way to know what pubkey from what oracle was used to create the missing seckey, or even to know if the oracle had anything to do with it at all.

For instance, Alice and Bob are placing their bet on the 2013 superbowl. Oscar the oracle says if the Giants win, he will reveal seckey A' which corresponds to pubkey A, and if they lose, he'll reveal seckey B', which corresponds to pubkey B.

Now Alice and Bob jointly agree on a pubkey with a seckey that they both know, C. Then they pay their funds to the following scriptPubKey:

IF
    <A*C> CHECKSIGVERIFY
    <Alice's pubkey> CHECKSIG
ELSE
    <B*C> CHECKSIGVERIFY
    <Bob's pubkey> CHECKSIG
ENDIF

All the other steps are pretty much as above. Note how you don't even need to bother with any privacy stuff. You can also do it with 100% standard transactions with multisig:

2 <alice*A> <alice> <bob*B> <bob> 4 CHECKMULTISIG

Note that while only x-of-3 CHECKMULTISIG is valid as a bare scriptPubKey, you can have more pubkeys if you enclose it in a P2SH scriptPubKey. The only restriction is you have to be able to spend it with a scriptSig of no more than 500 bytes.

Sorry, I should have figured this out earlier!

Thanks for the update.  I've been chugging away, but this kind of change seems reasonable.  There's another else case I have which is a 2 of 2 Multisig "Oracle disappear" clause, but the same idea applies.

I'll need to look up more on ECC Multiplication.  There was a presentation someone recommended a while back (I'll have to dig through this thread), where a guy basically was able to do some kind of transform on signatures to basically create an invoice at order time as part of the transaction, that seems like it might have some application here as well.

The only downside with this nonce approach is it's an all-or-nothing payout.  For a lot of contracts, that makes a lot of sense, but you also have some cases where you have a proportional payout (say you have something that pays out at a linear value, such as you get 1/435th of the value of the contract for each seat in the House the Republicans win, or you have a formula to try to offset difficulty increases where every time the difficulty doubles, you get 50% more payout out of the contract, etc...).  Mike was somewhat concerned in having a lack of flexibility in the payouts early on, and while this use case works very well in a huge number of cases, I think there will be a place for both in the end.  But I need to start somewhere and this seems simpler, so I start here.  I really like this idea, just need to research a bit more on implementation.

Thanks again for your contributions, I am making far more progress with help than I would have been able to do alone.

For ECC multiplication there's Python code for it here: https://github.com/richardkiss/pycoin (look at the BIP32 support)

There's probably some BIP32 support written for bitcoinj as well; ask around.

I believe I've seen some branches of bitcoinJ related to BIP32, so that sounds like the place to look.

This was the talk I was thinking of - Pay to Contract. https://www.youtube.com/watch?v=qwyALGlG33Q

An implementation of BIP32 is in the latest bitcoinj release, it's just not integrated with the rest of the code yet (so - same state as bitcoind)

Excuse the thread necromancy but I think this will interest people in this discussion. I'm just putting the finishing touches to Reality Keys, which is pretty close to being an External State Oracle as Mike Hearn and others here have discussed before, but with a few twists.

We provide data from various APIs for free, with an extra, optional layer of human confirmation available for a fee. Having the human confirmation layer allows you to use APIs that are less than 100% reliable, and also provides some protection against people interfering with the original information sources. Among other things this allows us to use data from Freebase, which means we can provide information about pretty much anything in the known universe.

Rather than signing contracts that people bring to us, we're providing pairs of public keys when you set up an event ("Hillary Clinton to be US president in 2016" or "BTC to hit $2000 by June, 2014" or "Address XYZ to have received 10 BTC by Friday"), and releasing one or other private key when we settle the outcome. Peter Todd mentioned this approach up-thread - it's very simple and flexible, and gives people and their software a lot of options for how to structure their transactions. It also puts a bit of distance between us and the transaction, which helps reduce our regulatory surface: We just report facts about the world as we find them and provide keys to prove what we found, so we don't need to know anything about what transactions people may or may not be making with them, and we can leave it up to them to work out if there are regulations in their jurisdiction that they need to comply with to be allowed to do what they're doing.

The keys are currently independently-generated random keypairs - we're literally using public keys from addresses generated with bitcoind, storing the private keys until the specified date then releasing one of the private keys when the event occurs and throwing the other one away. There are cleverer, deterministic ways to do this that we might switch to in future, if I can convince myself that we're not going to screw it up in some subtle way.

We currently monitor blockchain.info for blockchain transactions, various APIs for exchange rates and Freebase for everything else in the known universe. It's fairly straightforward to add additional information sources if people ask for them. We don't currently support generic "Hit a URL, see if it matches this regex" events, but we're thinking about it.

Let me know if anyone wants a pre-release password so they can take a peek. I expect to release next week unless somebody here says something earth-shattering that sends me back to the drawing board.

Just tinkering with this one:

2 <alice*A> <alice> <bob*B> <bob> 4 CHECKMULTISIG

When Alice says to Bob, "I made <alice*A>, here it is, let's use this in our transaction", is there a way for Bob to verify she's really made it with A instead of substituting some other key? IIUC <alice> is the seckey that's still known only to Alice, so Bob can't just repeat the same operation and compare the result, because he only knows A, not <alice>.

You should double-check with someone more familiar with the underlying math, but my understanding is that is public derivation, so neither the "alice" nor "A" pubkeys needs to be kept secret. Alice simply gives Bob both and he checks the computation himself.

Essentially we have four keypairs, Alice's (d_a, Q_a=d_a*G), Bob's (d_b, Q_b=d_b*G) and the two possible oracle values for true or false, (d_t, Q_t=d_t*G) and (d_f, Q_f=d_f*G). Alice and Bob need to derive pubkeys Q_{ta} and Q_{fb} such that Bob and Alice respectively can verify that Q_{ta} and Q_{fb} can only be spent with knowledge of d_t and d_a, and d_f and d_b respectively. (among other things, we don't want to accidentally make it possible for the oracle to spend the txout!)

My understanding of ECC math is that they can be computed as follows using ECC addition:

Q_{ta} = d_{ta}*G = (d_t + d_a)*G = d_t*G + d_a*G = Q_t + Q_a

But again, run this by someone who actually knows what they're doing like Adam Back, Pieter Wuille or Gregory Maxwell!

Ah, thanks - what threw me was that you were talking about multiplication up-thread, but when I looked at things like pybitcointool they seemed to have multiplication as an operation that took a private key and a public key, but addition an operation that took two public keys. Not understanding the difference between those I then started fretting that addition would somehow not be the right thing to do here (although I've tried combining keys like that with pybitcointool and it works fine, producing a serviceable key-pair.)

Anyhow I guess I'll finish up making a little demo script putting all this together and we can see if any of those people can poke any holes in it.

Yeah, up-thread my understanding of the details was a bit off, though multiplication can be used too IIUC.

Looking forward to trying it out when you're done!

OK, here's my first attempt at this, using vbuterin's pybitcointools (https://github.com/vbuterin/pybitcointools). This is intended to be the simplest thing I could make that would allow you to make a Reality Key contract, and have the winner collect.

https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py (https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py)

The flow for this is:

1) Alice and Bob agree on an event and get its ID, <fact_id> off the Reality Keys website. Alice will win if the outcome is "yes" and the Bob will win if it's "no".

2) They each run
...which creates a seed to make a private key and stores it, and tells them their public key and the address for that public key.

3) They exchange public keys, and they each fund their own address from some other wallet for the amount they intend to stake, plus half the transaction fee each. (Bear with me on this...)

4) Alice runs
 
This makes two public keys, one for "yes" (alice+rk-yes) and one for "no" (bob+rk-no"), and sticks them in a 1/2 P2SH address. (We'll really want to give them the option to unlock the funds with alice+bob and no Reality Keys, but this is intended as the simplest possible thing.)

It then checks both the temporary addresses, finds the inputs containing the stake and uses it as the input for a transaction. She signs her input using a regular SIGHASH_ALL. (You read that right, Alice adds Bob's input as well as her own, since she knows the temporary address it's coming from so she knows which outputs he'll want to spend. In non-toy implementations you probably want Bob to choose his own inputs and cut out the step with the temporary address, in which case presumably she'd sign with SIGHASH_ANYONECANPAY and leave Bob to add his own inputs.)

Finally it outputs a half-signed transaction, which Alice sends to Bob.

5) Bob runs the same thing Alice did, only with the transaction tacked on the end:
The script checks that the transaction Alice gave him has the same outputs that it would have created itself, and signs Bob's input, then broadcasts it.

6) Time passes.

7) The winner runs
...which grabs the private key of the winning outcome from Reality Keys, tries to combine it with the private key of the person running it, recreates the P2SH address and spends the contents to <some_address>.

Anyhow this seems to work, the contract transaction is atomic with no tinkering with refund transactions  and potentially mutable transaction IDs and things, it's all done with standard transactions.

The bit that scares me is here:
https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py#L241 (https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py#L241)
...where I'm meddling with forces that I don't fully understand. In particular what I'm wondering is whether, already knowing the Reality Key that his key is going to be combined with, there's something Bob could do with his own public key that would intentionally weaken the resulting bob+rk-no key.

I'm still trying to understand the practical differences between this and a regular escrow.
Unlike the escrow, the oracle doesn't need to know anything about the transaction.
Bob could still collude with the oracle, but it is supposed to be harder because anyone (for example, Alice) can ask the same question to the oracle many times without identifying herself.
Is this it? Or did I missed or misunderstood anything?

Like Peter Todd pointed out on irc, you could take advantages the similarities the other way around: you could build an escrow from an oracle without sending it the actual transaction for it to sign. Although I'm not sure how advantageous would that be.

 

edmundedgar: Mind re-posting this to the bitcoin-development list? I think it'd get more attention there, and the discussion would be archived more widely. It's also a fundamental question to a lot of protocols.

I'm not sure if d_{ta}*G = (d_t + d_a)*G is correct,
using your notation I think
d_{ta}*G = d_t*Q_a

Right. A bit of philosophical background: I like to think of Reality Keys as a certificate authority for propositions. We perform the same role for facts that Verisign performs for identities: We take information that's widely available to humans, and issue a cryptographic witness statement for it that can be understood by computers. Based on that, people can get their computers to do all kinds of useful things, one of which is creating a contract with a crypto-currency.

Traditionally an escrow agent would be someone who is informed about contracts, looks after funds and releases the funds either at the request of the parties or, in case of dispute, by evaluating the contract. With crypto-currencies there's a new kind of agent we could call an m-of-n escrow agent, who doesn't hold the funds, but uses a key to release the funds if required to evaluate the contract.

So onto the specifics:


You should be able to get a similar effect in theory with a transaction-signing oracle or m-of-n escrow agent by asking them to sign many transactions, and not telling them which is the real one. That's the suggestion here:
https://en.bitcoin.it/wiki/Contracts#Trust_minimization:_challenges

But I think the proposition-CA approach is cleaner and simpler: Everything anybody asks us is public. Not only do we not need to know about your contract, we don't even know how many contracts there are out there using a particular key. Everybody can easily check all of our judgements, even the ones they're not party to, and we can't release the wrong key as a favour to one person without risking messing up a bunch of contracts (or other, non-contract uses) that we don't know about.


Right. So the m-of-n escrow agent would probably still issue a pair of keys per user-agreement. (If they were issuing a pair of keys per proposition then on my definition they'd be a proposition-CA like Reality Keys not an m-of-n escrow agent like the guys on bitrated.) But they wouldn't need to see the actual transaction. One practical advantage of doing it that way would be that they wouldn't need to know how to sign any particular transaction, so their customers could use some non-bitcoin technology that they didn't know about, or somehow structure a bitcoin transaction in a way that they hadn't thought of and didn't know how to sign.

Makes sense, will do.

Interesting concept. I think the word contract is currently being misused though, in various contexts. What I'm missing is a good understanding of the actual things that we want to do with these kinds of systems. For example say I want to create a weather derivative or insurance contract. These will behave quite differently. I'm trying to think where these external state measurements best apply. Prediction markets never took off really, volume on intrade for instance was always quite low. On the other hand the insurance business is 10-20% or more of world GDP. there you want to observe states which are inherently private.