Topic: Implementing External State Contracts - Feedback Requested (Read 11232 times)

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.

Makes sense, will do.

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.

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

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

 

OK, here's my first attempt at this, using vbuterin's 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

The flow for this is:

1) Alice and Bob agree on an event and get its 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

Code:

./realitykeysdemo.py makekeys

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

Code:

./realitykeysdemo.py setup     

 
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:

Code:

./realitykeysdemo.py setup      

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

Code:

./realitykeysdemo.py claim    

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

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

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!

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.

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!

Just tinkering with this one:

2 4 CHECKMULTISIG

When Alice says to Bob, "I made , 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 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 .

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.

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)

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

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

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.

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.

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
     CHECKSIGVERIFY
     CHECKSIG
ELSE
     CHECKSIGVERIFY
     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 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!

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

This is one that went to the 2nd person:
2nd party redeems contract

1st party redeems contract

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

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.