Designing distributed contracts

[bji]

Where is the original thread you are refering to?

Sorry to have omitted the link, here it is:

http://forum.bitcoin.org/index.php?topic=8821.0

The discussion in the forum is relevant, but more relevant is the contents of the bitcoin wiki under the Contracts section:

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

which looked to be the results of that discussion and is what I would like to see changed if my comments make sense.

[ByteCoin]

Mike, thanks for the explanation. I appreciate the effort you spent to write it up. Could you please add a section to the Wiki explaining "lock time", "sequence number" and "transaction replacement" since these seem to be prerequisites for understanding the Contracts article you wrote.

In particular, could you clarify exactly what is compared with the LockTime value to prevent it being replaced and a little word on how LockTime interacts with block chain reorgs in a way that makes it superior to OP_BLOCKNUMBER.

You imply in your post that it could either be a time or a blocknumber. How is this distinction managed?

What is the significance of the sequence number applying to each input instead of the transaction as a whole?

"HashType" such as SIGHASH_NONE, SIGHASH_SINGLE and SIGHASH_ALL could do with being explained.

How does CODESEPARATOR work?

Example 1: Providing a deposit
We can solve this problem with a contract:

• The user and website send each other a newly generated public key.
• The user creates transaction Tx1 (the payment) putting 10 BTC into an output which requires both user and website to sign, but does not broadcast it. They use the key from the previous step for the site.
• User sends the hash of Tx1 to the website.

Doesn't the user also have to send the index of the relevant TxOut if Tx1 produced change?

• The sequence numbers on the inputs are set to zero instead of the default which is UINT_MAX.

...

• Because the sequence numbers are zero the contract can be amended in future if both parties agree.
  

"Inputs" and "sequence numbers". I thought there was only one input, Tx1.

ByteCoin

[joan]

You imply in your post that it could either be a time or a blocknumber. How is this distinction managed?

I might be wrong but this should be clear from the value. When read as a time, the current blocknumber get only as far as january 2nd 1970.
If we agree that every value before 1231006505 (genesis time) is a blocknumber, and considering blocks being added at 10 minutes interval, it would give us about 23404 years before the trouble starts 

[Mike Hearn]

From the code:

Code:

    bool IsFinal(int nBlockHeight=0, int64 nBlockTime=0) const
    {
        // Time based nLockTime implemented in 0.1.6
        if (nLockTime == 0)
            return true;
        if (nBlockHeight == 0)
            nBlockHeight = nBestHeight;
        if (nBlockTime == 0)
            nBlockTime = GetAdjustedTime();
        if ((int64)nLockTime < (nLockTime < 500000000 ? (int64)nBlockHeight : nBlockTime))
            return true;
        BOOST_FOREACH(const CTxIn& txin, vin)
            if (!txin.IsFinal())
                return false;
        return true;
    }

So the boundary value is 500,000,000 blocks. Not a problem.

Hash types are explained in the OP_CHECKSIG article. But I will try and add some of the explanations to the contracts article as well.

Somebody has implemented escrow transactions:

   https://github.com/bitcoin/bitcoin/pull/319

Sequence numbers apply to inputs rather than transactions to allow for multi-party signing by passing around partially signed transactions. Changing the sequence number on your input allows for a new version to appear without invalidating other parties signatures (see IsNewerThan and SignatureHash).

I would take things written in the Contracts article with a pinch of salt. This stuff is very complex and I haven't tried implementing it. It's based purely on my reading of the code, thinking about it and a few discussions with Satoshi. Some of the details are certainly wrong. For instance I got an email querying my usage of CODESEPARATOR. I think I agree the article is wrong on this point and I'll try to fix it.

[killerstorm]

I have an alternative idea for escrows which has some overlap with this.

Basic idea is to have time-sensitive transaction scripts.

A very small protocol extension is needed -- new script opcode, say, OP_CUR_BLOCK_NUMBER which pushes current block's serial number (height, or however you call it) on stack. (By current block I mean one which tries to spend an output, of course.)
Or OP_CUR_TIME which pushes current time.

This can be used in a number of situations:

1. Just as in "Providing a deposit", a web site wants you to put some coins aside for a few month. You can broadcast txn with script like this:

Code:

if (cur_block_number > 123456) {
   checksig(your_key);
} else fail;

This way you will be able to get your money back, but only after some time passes.

To prove it is really your txn you can either use unique amount provided by site (e.g. 1.013890123) OR embed a proving number into a txn in some other way.

2. Use 3rd party for escrow and mediation:

Code:

if (cur_block_number < 123000) {
   checkmultisig(counterparty's pubkey, escrow service's pubkey);
} else if (cur_block_number > 123100) {
   checsig(your pubkey);
} else fail;

What this means:

Your counter-party needs both his signature and mediator signature to unlock funds.
Thus if mediator service finds that contract requirements are met he will either provide his signature or his private key.

But if mediator service dies, or counter-party dies and they are unable to spend locked money then you will be able to get it back.

This way if something goes awry money doesn't hang there indefinitely.

3. Particularly, case number 2 might be useful for betting service. For example, A and B decide to make a bet: if event E happens some time in future A pays B 10 BTC, otherwise B pays A 10 BTC. They use a betting service S to ensure that this agreement is fulfilled.

So A sends B 10 BTC with script as above and B sends A 10 BTC.

Then, in the future, if event E happens S provides his signature to B and B is able to unlock his prize. But it does not provide signature to A, so B's money eventually return to B.

Again, if betting service dies money returns to users. And betting service cannot steal money (unless it conspires with one of users).

[Mike Hearn]

What you suggest is what nLockTime does. OP_BLOCKNUMBER has been discussed before, but it can't be implemented because if it's evaluated "in context" it can be used to make a transaction valid for some time, then invalid (causing attacker controlled chain splits). If it's converted into a constant before being placed in a block the signatures over the transactions can break.

[ByteCoin]

Mike's concern is valid. The solution suggested in the OP_BLOCKNUMBER threads is to reduce the risk to the same level as the invalidation of coinbase transactions. Coinbase transactions take a long time to mature because reorgs that invalidate transactions spending coinbases must be thrown away after the reorg. OP_BLOCKNUMBER transactions could take a very long time to mature, proportional to their value.

nLockTime, sequence numbers and scripting are powerful. There seems to be no way however using scripting, nLockTime etc to send bitcoins to an address and to have them revert back to you if they are unspent for a very long time which seems to be a keenly desirable feature. I will take this back and discard OP_BLOCKNUMBER if someone demonstrates that equivalent functionality can be gained without it.

If there were an OP_DIFFICULTY as well then the futures and bonds suggested by cunicula might be possible.

ByteCoin

[Mike Hearn]

You can already do that (well, if the features were re-enabled).

Send coins to a recipient as usual. The recipient creates a tx with a nLockTime in the future that sends them back to you, but doesn't broadcast it, instead they just give it to you out of band (eg via email).

Now wait. If after the time period is nearly up the coins weren't spent, broadcast your reclamation tx. Once nLockTime passes the coins are yours once again.

Broadcasting the reclamation tx prevents the owner spending the coins (it'd be a double spend so will be rejected). But the reclamation was created by the owner of the coins, not you. If you broadcast it before the time is up, the real owner can create a new version of the tx with a higher sequence number and broadcast it to claim the coins for good, overriding your reclamation tx.

In this way there's no point trying to reclaim the coins unless the recipient has really gone away for good and won't block your reclaim attempt.

[Mike Hearn]

ByteCoin and a few others asked for more detail on the SIGHASH flags.

I added a brief description of what they are for to the top. Also, because it's quite hard to understand all the parts without illustration, I added a third example that describes how to implement assurance contracts via script.

Note that beyond lacking a GUI and RPCs for the general protocol, the lock time feature is disabled today and there's no way to mark coins as temporarily unspendable. Without the latter feature it'd be possible to accidentally spend pledged coins without meaning to, invalidating your pledge.

[killerstorm]

Hmm, latest message I can find on OP_BLOCKNUMBER is of May 03 http://forum.bitcoin.org/index.php?topic=6900.20
and Mike says "I don't know.". Is there a new information, like, a concrete attack scenario?

If all nodes are required to validate scripts then yes, it is problematic because blocknumber might be different.

But if only miners check these complex scripts at time they are included into a block then I see no problem -- OP_BLOCKNUMBER is fixed in context of block being made. The only problem is reorg, but this can fixed too through maturation time, as ByteCoin says.

Solutions which use OP_BLOCKNUMBER seem to be orders of magnitude simpler than ones which use nLockTime, so why dismiss it just because there _might_ be problems, i.e. in absence of concrete attack scenarios? I would guess that if nLockTime looks more complex then it can have well-hidden security problems.

If there were an OP_DIFFICULTY as well then the futures and bonds suggested by cunicula might be possible.

Yep, and with OP_BLOCKTIMESTAMP you can also check for hashrate growth before difficulty updates. (I.e. if hashrate went up blocks will be generated faster and so timestamp will be lower than you would expect otherwise.)

[Mike Hearn]

I thought about it more since I wrote that post.

Something like OP_BLOCKNUMBER is probably 'possible', but would require serious surgery on the codebase. Having explored the system in more depth, I understand why Satoshi chose to implement this as a property of the transaction rather than in script.

Currently, script evaluation is independent of context. If OP_BLOCKNUMBER is defined to be the block the transaction appears in, it has no meaning outside the block chain (eg in the memory pool), so is a script containing it valid or invalid? If it's defined to be the current best height, it's possible to fork the chain when it's included (so this isn't an acceptable definition).

It's important to note that nLockTime is a property of the whole transaction, not an input. You could potentially write a transaction in which different inputs used the current block number in different ways, resulting in a lot of weird edge cases and bugs.

The design of Bitcoin is quite subtle and changing it in big ways isn't to be taken lightly. So far nLockTime seems to offer enough power to achieve many different things, most proposed uses for OP_BLOCKNUMBER can be rephrased to use the existing facilities.

[Mike Hearn]

OK, I'm going to be busy for a few days so I added a final fourth example of how to lock coins to arbitrary external state using an oracle. Minor adaptations should make things like network-enforced futures contracts possible, for those who are interested in that.

[kjj]

You can already do that (well, if the features were re-enabled).

Send coins to a recipient as usual. The recipient creates a tx with a nLockTime in the future that sends them back to you, but doesn't broadcast it, instead they just give it to you out of band (eg via email).

Now wait. If after the time period is nearly up the coins weren't spent, broadcast your reclamation tx. Once nLockTime passes the coins are yours once again.

Broadcasting the reclamation tx prevents the owner spending the coins (it'd be a double spend so will be rejected). But the reclamation was created by the owner of the coins, not you. If you broadcast it before the time is up, the real owner can create a new version of the tx with a higher sequence number and broadcast it to claim the coins for good, overriding your reclamation tx.

In this way there's no point trying to reclaim the coins unless the recipient has really gone away for good and won't block your reclaim attempt.

The transaction of your coins for their promise to return your coins is not atomic.

And thank you for the other part.  I had been wondering about nLockTime and sequences for a while now, but hadn't dug into them.  But now I know.  Another nifty gem hidden in the bitcoin design.

[Mike Hearn]

If you want the operation to be atomic you can create the initial send, hash it, send the hash to the recipient and then wait for them to reply with the reclamation tx. Once you have the reclamation tx, broadcast the send.

[kjj]

If you want the operation to be atomic you can create the initial send, hash it, send the hash to the recipient and then wait for them to reply with the reclamation tx. Once you have the reclamation tx, broadcast the send.

I think I'm missing an implied step in there.  How is the hash useful as security to them?  Couldn't you just fail to broadcast the send after you get the reclaim?

But we could just skip that step entirely and end up in the same place.  They give you the reclamation transaction first, and then invalidate it (as described earlier) if you fail to send.

[Mike Hearn]

You can't construct the reclamation tx without the hash of the transaction it's reclaiming.

[killerstorm]

Currently, script evaluation is independent of context. If OP_BLOCKNUMBER is defined to be the block the transaction appears in, it has no meaning outside the block chain (eg in the memory pool), so is a script containing it valid or invalid? If it's defined to be the current best height, it's possible to fork the chain when it's included (so this isn't an acceptable definition).

Here is how I would define OP_BLOCKNUMBER:

1. If transaction input is verified in context of AcceptToMemoryPool it is defined as current best height + 1. (I.e. next block's index.)
2. If transaction input is verified in context of ConnectBlock it is defined as this block's index, i.e. height of block chain at time block was created + 1.
3. If transaction input is verified in context of CreateNewBlock it is defined as current best height + 1 (i.e. index of block which is in process of being mined).

These contexts already do exist as different flags to ConnectInputs(), but they are not passed to VerifySignature() and VerifyScript(). But it is trivial either to pass an additional parameter or record this info in state of transaction. I don't think this qualifies as a serious surgery, if you're concerned about code complexity I can try to make a patch which implements it and we'll see...

Now if it is defined this way I don't see how bad things you talk about can happen.

Once txn is in block its input is well-defined and so all nodes will agree on its validity. So this cannot be used to cause block chain splits. If blocks are reorganized then new transaction might have problems getting into next block, but it is also the case with double-spend scenarios, so it's nothing new. Impact can be minimized by requiring transactions with inputs which use OP_BLOCKNUMBER to mature for some time.

For transactions which are in pool validity might change over time, so different nodes with different chain heights might disagree, but this is not a problem because transactions are re-checked once they appear in blocks. It will only have effect on transaction relaying, and if transaction is not relayed then it hurts only one who made it.

[Mike Hearn]

But what's the justification for such a complicated opcode and set of changes? And yes, an opcode whose result changes depending on the context in which it's verified counts as 'complex' to me, relative to most of the other opcodes.

I haven't seen any use case for such a thing yet, given that it'd require a forced global upgrade.

[garyrowe]

I'm very interested in the bitcoin contract creation.
Is it possible for the standard client to do this, or is it only available through an API?
Are there any code examples of it in use?

[Mike Hearn]

Contracts are only of interest to people willing to modify the core Bitcoin code, currently (or significantly extend another implementation like BitCoinJ). There's no API for generic crafting of contracts and it doesn't make much sense to create one, imo.