Contract: Difference between revisions

From Bitcoin Wiki
Jump to navigation Jump to search
Mike (talk | contribs)
Mike (talk | contribs)
Add a description of locking coins to arbitrary external state
Line 101: Line 101:


An elaboration of this concept is described by Tabarrok in  his paper, [http://mason.gmu.edu/~atabarro/PrivateProvision.pdf “The private provision of public goods via dominant assurance contracts”]. In a dominant assurance contract, if a contract fails (not enough pledges within a set time window) the entrepreneur pays a fee to those who pledged so far. This type of contract attempts to arrange incentives such that taking part is always the right strategy. The implementation of dominant assurance contracts is left as an exercise for the reader.
An elaboration of this concept is described by Tabarrok in  his paper, [http://mason.gmu.edu/~atabarro/PrivateProvision.pdf “The private provision of public goods via dominant assurance contracts”]. In a dominant assurance contract, if a contract fails (not enough pledges within a set time window) the entrepreneur pays a fee to those who pledged so far. This type of contract attempts to arrange incentives such that taking part is always the right strategy. The implementation of dominant assurance contracts is left as an exercise for the reader.
==Example 4: Connecting transactions to the outside world==
It may sometimes be useful to lock up coins such that they become available based on arbitrary conditions. This is a specialization of the general case of dispute mediation - connections to the outside world can always be viewed as a mediated dispute between two parties (see example 2), but trust can be further minimized by exploiting Bitcoins capabilities.
Scripts are pure functions: by design they cannot directly access any external state because if they could it would be possible for an attacker to outrun the block chain. However, we can import external state in another way.
Because the condition we wish to measure is arbitrary, Bitcoin nodes don’t know how to do it themselves. Thus we need an ‘’oracle’’ - a third party who will conduct the measurements for us. This third party must be trusted to measure accurately, but there are ways to minimize the level of trust required. The oracles job is to vend transactions on demand that contain a measurement and a signature (thus proving the measurement did indeed come from the oracle).
Consider a contrived example: an old man wishes to give his grandson a large sum of money, but only when one of two conditions occurs: the grandson turns 18, or the man dies, whichever comes first.
The first condition is easy to encode using nLockTime: a transaction can be given (not broadcast) which sends the coins to the grandson on the date of his birthday. The second condition requires an organization that mechanically translates the obituraries section of the local newspaper into Bitcoin transactions.
To encode this, the grandson is given a transaction that spends the mans money to an output containing the following script:
<oracle pubkey> OP_CHECKSIGVERIFY “John Smith” OP_EQUALVERIFY
The first part of this script verifies that the spending transaction is actually generated by the oracle. The second part checks that the mans name appears in the transaction. If both conditions are true, the coins can be spent.
The oracle maintains a website where a list of people who recently died appears. Clicking their name vends a transaction containing a single input with a user-specified connected input and the following scriptSig:
“Name” <sig>
The signature uses the SIGHASH_NONE flag, thus the recipient can be anyone (the oracle does not care). If the man dies, the son can claim the funds by taking this transaction, adding an output to one of his own addresses, and then broadcasting it.
Trust in the oracle can be minimized by taking some basic precautions. One is to routinely cross-check the oracles results against observable reality, ie, ensure it really is vending what it claims it will vend. Another is to hide what the output condition is, so the oracle cannot know what its vended transactions might be used to claim. In the example above, the mans name could be encoded in hashed form rather than directly. A final technique is to use multiple independent oracles.
The scheme can be trivially extended to support numeric conditions, eg, if you wish to gate an output on a variable being between a particular range:
<oracle pubkey> OP_CHECKSIGVERIFY 5 10 OP_WITHIN OP_VERIFY
then the oracle can vend
<numeric value> <sig>
Note that OP_WITHIN implements left-wise inclusion, ie the acceptable values would be 5,6,7,8,9.


==See Also==
==See Also==

Revision as of 22:18, 23 June 2011

A distributed contract is a method of using Bitcoin to form agreements with people via the block chain. Contracts don't make anything possible that was previously impossible, but rather they allow you to solve common problems in a way that minimizes trust.

Theory

Every transaction in Bitcoin has one or more inputs and outputs. Each input/output has a small pure function associated with it called a script. Scripts can contain signatures over simplified forms of the transaction itself.

Every transaction can have a lock time associated with it. This allows the transaction to be pending and replaceable until an agreed upon future time, specified either as a block index or as a timestamp (the same field is used for both, but values less than 500 million are interpreted as a block index). If a transactions lock time has been reached we say it is final.

Each transaction input has a sequence number. In a normal transaction that just moves value around, the sequence numbers are all UINT_MAX and the lock time is zero. If the lock time has not yet been reached, but all the sequence numbers are UINT_MAX, the transaction is also considered final. Sequence numbers can be used to issue new versions of a transaction without invalidating other inputs signatures, eg, in the case where each input on a transaction comes from a different party each input may start with a sequence number of zero, and those numbers can be incremented independently.

Signature checking is flexible because the form of transaction that is signed can be controlled through the use of SIGHASH flags, which are stuck on the end of a signature. In this way contracts can be built in which each party signs only a part of it, allowing other parts to be changed without their involvement. The SIGHASH flags have two parts, a mode and the ANYONECANPAY modifier:

  1. SIGHASH_ALL: This is the default. It indicates that everything about the transaction is signed, except for the input scripts. Signing the input scripts as well would obviously make it impossible to construct a transaction, so they are always blanked out. Note though that other properties of the input, like the connected output and sequence numbers, are signed: it's only the scripts which are not. Intuitively it means "I agree to put my money in, if everyone puts their money in and the outputs are this".
  2. SIGHASH_NONE: The outputs are not signed and can be anything. Use this to indicate "I agree to put my money in, as long as everyone puts their money in, but I don't care what's done with the output". This mode allows others to update the transaction by changing their inputs sequence numbers.
  3. SIGHASH_SINGLE: Like SIGHASH_NONE the inputs are signed but the sequence numbers are blanked so others can create new versions of the transaction. However the only output that is signed is the one at the same position as the input. Use this to indicate "I agree, as long as my output is what I want, I don't care about the others".

The SIGHASH_ANYONECANPAY modifier can be combined with the above three modes. When set, only that input is signed, and the other inputs can be anything.

Scripts can contain the CHECKMULTISIG opcode. This opcode provides n-of-m checking: you provide multiple public keys, and specify the number of valid signatures that must be present. The number of signatures can be less than the number of public keys. An output can require two signatures to be spent by setting it to something like this:

2 <pubkey1> <pubkey2> 2 CHECKMULTISIGVERIFY

There are two general patterns for safely creating contracts:

  1. Transactions are passed around outside of the P2P network, in partially complete or invalid forms.
  2. Two transactions are used: one (the contract) is created and signed but not broadcast right away. Instead the other transaction (the payment) is broadcast after the contract is agreed to lock in the money, and then the contract is broadcast.

This is to ensure people always know what they are agreeing to.

Together these features let us build interesting new financial tools on top of the block chain.

Example 1: Providing a deposit

Imagine you open an account on a website (eg, a forum or wiki) and wish to establish your trustworthyness with the operators, but you don't have any pre-existing reputation to leverage. One solution is to buy trust by paying the website some money. But if at some point you close your account you'd probably like that money back. You may not trust the site enough to give them a deposit which they are tempted to spend. Another risk is that the site might just disappear one day.

The goal is to prove that you made a sacrifice of some kind so the site knows you're not a spambot, but you don't want them to be able to spend the money. And if the operators disappear you'd eventually like the coins back without needing anything from them.

We can solve this problem with a contract:

  1. The user and website send each other a newly generated public key.
  2. 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.
  3. User sends Tx1 to the website.
  4. The website creates a transaction Tx2 (the contract). Tx2 spends Tx1 and pays it back to the user using the address he provided in the first step. Note that Tx1 requires two signatures, so this transaction can't be complete. nLockTime is set to some point in the future (eg, six months). The sequence number on the input is set to zero.
  5. Finally the incomplete (half signed) transaction is sent back to the user. The user checks that the contract is as expected ... that the coins will eventually come back to him but, unless things are changed, only after six months. Because the sequence number is zero the contract can be amended in future if both parties agree. The script in the input isn't finished though - where there should be the users signature is only zeros. He fixes that by signing the contract and putting the new signature in the appropriate spot.
  6. The user broadcasts Tx1, then broadcasts Tx2.

At this point, the 10 BTC are in a state where neither the user nor the website can spend them independently. After six months the contract will complete and the user will get the coins back even if the website disappears.

What if the user wishes to close his account early? The website creates a new version of Tx2 with nLockTime set to zero and the input sequence number set to UINT_MAX, then re-signs it. The site hands the tx back to the user who signs it as well. The user then broadcasts the transaction, terminating the contract early and releasing the coins.

What if the six months is nearly up and the user wishes to keep his account? The same thing applies: the contract can be resigned with a newer nLockTime, a sequence number 1 higher than the previous and rebroadcast 2^32 times. No matter what happens, both parties must agree for the contract to change.

Obviously, if the user turns out to be abusive (ie a spammer), the website will not allow an early close of the contract. If too much abuse is getting through, the size of the deposit can be raised or the length of the contract can be increased.

Example 2: Escrow and dispute mediation

You want to trade with somebody you don't know or trust. In the common case where the transaction goes well, you don't want any third parties involved. If something goes wrong though, you'd like the money to go to a third party - perhaps a professional dispute mediation service. Note that "you" in that sentence can refer to either buyer or seller. The mediator might request proof of postage from the merchant for example.

In other words, you want to lock up some coins so you can send them to one of two addresses. There's no way to write an output script such that it checks the outputs of the spending transaction. Scripts don't have access to that data. Fortunately, we can do it another way:

  1. Agree with the merchant on a dispute mediator (eg, ClearCoin).
  2. Ask the merchant for a public key (K1). Ask the mediator for a public key (K2). Create a new key for yourself (K3).
  3. Send the merchant K2. The merchant challenges the mediator with a random nonce, the mediator signs the nonce with the private form of K2 thus proving it really belongs to them.
  4. Create a transaction (Tx1) with an output script as follows and broadcast it:
2 <K1> <K2> <K3> 3 CHECKMULTISIGVERIFY

Now the coins are locked in such a way that they can be only spent by the following methods:

  1. You and the merchant agree (either a successful trade, or merchant agrees to reimburse you without mediation)
  2. You and the mediator agree (failed trade, mediator sides with you, like a chargeback)
  3. The mediator and the merchant agree (goods delivered, merchant gets your coins despite the dispute)

When signing an input, the contents is set to the connected output. Thus, to redeem this transaction, you create a scriptSig containing zeros where the other signature should be, sign it, and then set one of the slots to your new signature. The partially complete transaction can then be sent to the merchant or mediator for the second signature.

Example 3: Assurance contracts

An assurance contract is a way of funding the creation of a public good, that is, a good which once created anyone can benefit from for free. The standard example is a lighthouse: whilst everyone may agree that one should be built, it’s too expensive for an individual sailor to justify building one given that it will also benefit all his competitors.

One solution is for everyone to pledge money towards the creation of the public good, such that the pledges are only committed if the total value of all pledges is above the cost of creation. If not enough people contribute, nobody has to pay anything.

We can model this in Bitcoin as follows:

  1. An entrepreneur creates a new address and announces that the good will be created if at least 1000 BTC is raised. Anyone can contribute.
  2. Each party wishing to pledge creates a new transaction spending some of their coins to the announced address, but they do not broadcast it. The transaction is the similar to a regular transaction except for three differences. Firstly, there cannot be any change. If you don’t have any outputs of the right size, you must create one first by spending to one of your own addresses. Secondly the input script signature is signed with SIGHASH_ALL | SIGHASH_ANYONECANPAY. Finally, the output value is set to 1000 BTC. Note that this is not a valid transaction because the output value is larger than the input value.
  3. The transaction is uploaded to the entrepreneurs server, which saves it to disk and updates its count of how many coins have been pledged.
  4. Once the server has enough coins, it merges the separate transactions together into a new transaction. The new transaction has a single output which simply spends to the announced address - it is the same as the outputs on each contributed transaction. The inputs to the transaction are collected from the contributed pledges.
  5. The finished transaction is broadcast, sending the pledged coins to the announced address.

This scheme relies on several aspects of the protocol. The first is the SIGHASH flags used. SIGHASH_ALL is the default and means the entire contents of the transaction is signed, except for the input scripts. SIGHASH_ANYONECANPAY is an additional modifier that means the signature only covers the input it’s found in - the other inputs are not signed and thus can be anything.

By combining these flags together, we are able to create a signature that is valid even when other inputs are added, but breaks if the outputs or other properties of the transaction are changed.

The second aspect we exploit is the fact that a transaction in which the output values are larger than the input values is invalid (for obvious reasons). This means it’s safe to send the entrepreneur a transaction that spends such coins - it’s impossible for him to claim the coins unless he has other transactions that sum to the output value or more.

It's possible to create assurance contracts without using SIGHASH_ANYONECANPAY. Instead a two step process is used in which pledges are collected without transactions, and once the total value is reached, a transaction with an input for each pledger is created and passed around until all signatures are collected. However, using SIGHASH_ANYONECANPAY and then merging is probably more convenient.

An assurance contract can be prepared that funds network security. Instead of a single announced address for everyone to contribute to, the entrepreneur provides a set of outputs which are signed by each party in their pledge. The entrepreneur also prepares a number of transactions equivalent to the number of outputs, each one spending a single contract output to a null output of zero value and an OP_FALSE script, ie the entire value is consumed as fees. The lock time of each transaction is set to N+M, where N is a pre-agreed time at which the contract becomes valid (measured in block numbers) and M is the index of a contract output. In this way an array of transactions are prepared that do nothing but incentivize mining in a series of blocks.

The incentive transactions are broadcast before the assurance contract. They are considered to be orphan transactions because their referenced input (the contract) hasn’t been seen yet by the network, but pre-broadcasting them lets pledgers know what they are signing for and prevents the entrepreneur stealing the coins. Once the contract is broadcast, the orphan transactions become valid and can be claimed by miners once their block number is reached.

An elaboration of this concept is described by Tabarrok in his paper, “The private provision of public goods via dominant assurance contracts”. In a dominant assurance contract, if a contract fails (not enough pledges within a set time window) the entrepreneur pays a fee to those who pledged so far. This type of contract attempts to arrange incentives such that taking part is always the right strategy. The implementation of dominant assurance contracts is left as an exercise for the reader.

Example 4: Connecting transactions to the outside world

It may sometimes be useful to lock up coins such that they become available based on arbitrary conditions. This is a specialization of the general case of dispute mediation - connections to the outside world can always be viewed as a mediated dispute between two parties (see example 2), but trust can be further minimized by exploiting Bitcoins capabilities.

Scripts are pure functions: by design they cannot directly access any external state because if they could it would be possible for an attacker to outrun the block chain. However, we can import external state in another way.

Because the condition we wish to measure is arbitrary, Bitcoin nodes don’t know how to do it themselves. Thus we need an ‘’oracle’’ - a third party who will conduct the measurements for us. This third party must be trusted to measure accurately, but there are ways to minimize the level of trust required. The oracles job is to vend transactions on demand that contain a measurement and a signature (thus proving the measurement did indeed come from the oracle).

Consider a contrived example: an old man wishes to give his grandson a large sum of money, but only when one of two conditions occurs: the grandson turns 18, or the man dies, whichever comes first.

The first condition is easy to encode using nLockTime: a transaction can be given (not broadcast) which sends the coins to the grandson on the date of his birthday. The second condition requires an organization that mechanically translates the obituraries section of the local newspaper into Bitcoin transactions.

To encode this, the grandson is given a transaction that spends the mans money to an output containing the following script:

<oracle pubkey> OP_CHECKSIGVERIFY “John Smith” OP_EQUALVERIFY

The first part of this script verifies that the spending transaction is actually generated by the oracle. The second part checks that the mans name appears in the transaction. If both conditions are true, the coins can be spent.

The oracle maintains a website where a list of people who recently died appears. Clicking their name vends a transaction containing a single input with a user-specified connected input and the following scriptSig:

“Name” <sig>

The signature uses the SIGHASH_NONE flag, thus the recipient can be anyone (the oracle does not care). If the man dies, the son can claim the funds by taking this transaction, adding an output to one of his own addresses, and then broadcasting it.

Trust in the oracle can be minimized by taking some basic precautions. One is to routinely cross-check the oracles results against observable reality, ie, ensure it really is vending what it claims it will vend. Another is to hide what the output condition is, so the oracle cannot know what its vended transactions might be used to claim. In the example above, the mans name could be encoded in hashed form rather than directly. A final technique is to use multiple independent oracles.

The scheme can be trivially extended to support numeric conditions, eg, if you wish to gate an output on a variable being between a particular range:

<oracle pubkey> OP_CHECKSIGVERIFY 5 10 OP_WITHIN OP_VERIFY

then the oracle can vend

<numeric value> <sig>

Note that OP_WITHIN implements left-wise inclusion, ie the acceptable values would be 5,6,7,8,9.

See Also