Implementing External State Contracts - Feedback Requested

[alp]

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

[1714160628]

1714160628

[1714160628]

1714160628

[1714160628]

1714160628

[Peter Todd]

BTW your links to your transactions are broken...

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.

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)

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.

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.

[alp]

BTW your links to your transactions are broken...

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.

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)

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.

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.

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.

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.

[alp]

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

[Peter Todd]

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!

[alp]

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.

[Peter Todd]

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.

[alp]

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.

[alp]

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

[Mike Hearn]

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)

[edmundedgar]

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.

[edmundedgar]

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!

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

[Peter Todd]

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!

[edmundedgar]

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.

[Peter Todd]

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!

[edmundedgar]

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

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 <fact_id> <yes_winner_pubkey> <yes_winner_stake> <no_winner_pubkey> <no_winner_stake>

 
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 <fact_id> <yes_winner_pubkey> <yes_winner_stake> <no_winner_pubkey> <no_winner_stake> <tx_from_alice>

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 <fact_id> <yes_winner_pubkey> <no_winner_pubkey> <some_address>

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

[jtimon]

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.

 

[Peter Todd]

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.

[Crowex]

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

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]

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.

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:

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?

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.

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.

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.