Bitcoin Wiki - User contributions [en]

Off-Chain Betting

2014-02-25T21:19:27Z

Aakselrod: Created page with "This work builds on the scheme for off-chain payments with two-phase commit. == Example == Alice and Bob would like to make a bet about whether a bi..."

This work builds on the scheme for [[User:Aakselrod/Draft|off-chain payments with two-phase commit]].

== Example ==

Alice and Bob would like to make a bet about whether a bitcoin is worth more or less than $500 in two weeks. Carole commits to announcing the result of the event: she signs and publishes a statement that if a bitcoin is worth at least $500 in two weeks, she'll reveal the preimage to HashA and if it's worth less than $500 in two weeks, she'll reveal the preimage to HashB.

Alice and Bob create a "bet channel" output together: let's say each contributes .5 BTC to the output, which must be signed by both Alice and Bob to be spent. The refund transaction, signed by both of them, has an nLockTime of one year in the future.

Alice would like to bet .1 BTC that a bitcoin will be worth at least $500, and Bob would like to bet .1 BTC that a bitcoin will be worth less than $500 in 2 weeks. Alice and Bob sign two versions of a transaction with nLockTime earlier (say, by a day) than the most recent bet (or the refund transaction, if there's no bets on this channel) with outputs as follows:

Version I.
1. .6 BTC to SHA256 HashA EQUALVERIFY PubkeyAlice CHECKSIG
2. .4 BTC to SHA256 HashA EQUALVERIFY PubkeyBob CHECKSIG

Version II.
1. .4 BTC to SHA256 HashB EQUALVERIFY PubkeyAlice CHECKSIG
2. .6 BTC to SHA256 HashB EQUALVERIFY PubkeyBob CHECKSIG

If a bitcoin is worth at least $500 in two weeks, Carole reveals the preimage to HashA. The only transaction version from which it's possible for Alice and Bob to get their money back is I. If a bitcoin is worth less than $500, the opposite is true.

If Alice wins the bet, Bob's only choice is to concede. If Bob were to try to publish transaction version II, he won't be able to redeem his output as he doesn't know the preimage to HashB. Cheating by Carole is easily proven publicly by publishing the preimages of both HashA and HashB.

After the winning preimage is published, the channel can be reused for another bet.

There are multiple variations on this theme: for example, you can make do with only one transaction, you can have bets with more than two outcomes, etc. You can also adjust the amount of the bet as time goes on, as long as you're betting on the same event and in the same direction, in the same way as you can adjust payment channel allocations back and forth.

This construct can be used for bets on any subject providing there's an oracle or arbitrator willing to perform Carole's job. The oracle would need to publish all events it's willing to adjudicate, and upon the event's conclusion, to reveal the preimage corresponding with the event's outcome.

In a friend-to-friend network, it becomes possible to hedge exchange risk (or any other risk). As an example, Overstock.com would like to hedge the risk that Bitcoin prices will go down before they can pay their suppliers for merchandise. Overstock would offer several counterparties similar bets based on Coindesk's price index.

Coindesk could publish on their website or via an API, daily, signed sets of preimages for future announcements. For example, they publish a set of preimages for two weeks in advance:

* If a bitcoin is worth between $0 and $100, reveal the preimage to HashA
* If a bitcoin is worth between $100 and $200, reveal the preimage to HashB
* If a bitcoin is worth between $200 and $300, reveal the preimage to HashC
* And so on

Overstock would make bets with its counterparties similar to above that the price will be lower (like being long a binary put option or short a binary call option). Its counterparties, each with its own internal order book, could then hedge that risk with other counterparties, which maybe would like to get money if bitcoin prices go up (like being short a binary put option or long a binary call option). The end result is a distributed derivatives market based on Coindesk's price index. Competing price indexes such as the Winkdex could also be used.

User:Aakselrod/Draft

2013-03-12T17:18:30Z

Aakselrod:

== Proposal Background and Summary ==

The basic concept of a peer-to-peer payment network which allows nodes to transact off the blockchain has been proposed before. Proponents see multiple advantages such as instant payments which require no additional confirmations, higher scalability due to individual payments taking place off the blockchain, and feasibility of widespread micropayments. The proposals use [[Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party|micropayment channels]]<ref>https://bitcointalk.org/index.php?topic=91732.0</ref> or other multi-signature transaction-based shared property<ref>https://bitcointalk.org/index.php?topic=94674.0</ref> schemes between payers, payees, and intermediaries in order to allow such transactions.

For example, if Alice is a customer and Bob is a merchant, Alice may have a micropayment channel open to Carol, her payment processor, who may have a channel open to Dan, Bob's payment processor, which also has a channel open to Bob. Alice would increment the allocation going to Carol through her channel by the amount she wants to pay Bob, and Carol and Dan would do the same down the line. Bob would then be paid instantly, and none of this would hit the blockchain except as part of aggregate settlement transactions closing the micropayment channels.

This proposal aims to bring closer the realization of such a network by discussing the following solutions:

* Additional scalability of micropayment channel setup transactions by having intermediaries combine them.
* Two-phase commit through multiple chained micropayment channels, reducing the risk that an intermediary will accept a payment but not forward it on and enabling two-party escrowed payments through the payment network.
* Extraction of routing and reputation information from the blockchain and memory pool as a side effect of the way micropayment channels are opened and closed.

The proposal will also discuss possible side effects of its adoption, both positive and negative.

Other potential off-chain payment solutions have also been proposed<ref>https://bitcointalk.org/index.php?topic=146307.0</ref> using different mechanisms. These potential solutions are out of scope for this proposal, which focuses on chained micropayment channels between payers, payees and intermediaries. Other types of solutions may have the potential to be combined with the solution detailed in this proposal.

== Micropayment Channels ==

The original concept of the micropayment channel is explained well on the [[Contracts]] page in example 7, referenced above. Unlike the concept of shared property, these micropayment channels are unidirectional and must be created in pairs for bidirectional payment flow.

Transaction replacement is used in this scheme to prevent denial of service (locking up money, potentially permanently depending on whether it's for ransom or not) by the receiving side of a micropayment channel. Nodes running 0.8 and above treat non-final transactions as non-standard. This allows the recipient a high degree of confidence that a non-final timelocked transaction won't be stuck in the memory pool of most nodes and a final transaction meant to replace it will be mined first. While this is not the original design for transaction replacement, it should work similarly for many use cases.

To work with the current state of the network, the format of the T2 transaction defined in the scheme above must be changed slightly. The initial version of T2 would still be created the same way (potentially with a longer lifetime than just one day); however, subsequent versions of T2 would not have nLockTime set and would have a sequence number of UINT_MAX. The micropayment channel recipient does not sign or broadcast any intermediate versions of T2 until the channel is ready to be closed.

Two other types of proposals have been suggested to discourage and/or make expensive such denial of service attacks by either side of a micropayment channel: risk deposits<ref>https://bitcointalk.org/index.php?topic=118418.msg1271858#msg1271858</ref><ref>https://bitcointalk.org/index.php?topic=75481.0</ref> and reputation systems<ref>https://bitcointalk.org/index.php?topic=134827.0</ref>. This proposal can use both techniques to help reduce the risk.

== Two-Phase Commit ==

In order to allow two-phase commit for chained micropayment channels, the original scheme for is modified slightly again with a construct similar to the [[Contracts#Example_5:_Trading_across_chains|trading across chains]] scheme. Specifically, the two T2 outputs would be in a format similar to the following:

1. SHA256 Hashm EQUALVERIFY Pubkeysender CHECKSIGVERIFY
2. SHA256 Hashm EQUALVERIFY Pubkeyrecipient CHECKSIGVERIFY

and the input scripts redeeming those outputs would be in a format similar to the following:

1. SIGsender m
2. SIGrecipient m

where <code>m</code> is a number of at least 256 bits agreed to by a payer and payee in a payment which is chained through multiple micropayment channels. <code>Hashm</code> is then called the commit hash for the off-chain payment which goes through this chain of micropayment channels. An example follows:

Alice would like to pay Bob 10 mBTC. Alice does not have a micropayment channel to Bob. However, Alice has a micropayment channel to Carol, and Carol has a micropayment channel to Bob.

Bob generates a 256-bit number <code>m</code> and gives its SHA256 hash, the commit hash for the payment, to Alice. Alice has previously signed and sent to Carol a transaction T2AC which contains an input from her and Carol's T1AC and two outputs:

1. 90 BTC to: SHA256 h EQUALVERIFY PubkeyAlice CHECKSIGVERIFY
2. 10 BTC to: SHA256 h EQUALVERIFY PubkeyCarol CHECKSIGVERIFY

where <code>h</code> is a hash from a previous payment which has gone through a similar process. Similarly, Carol has previously signed and sent to Bob a transaction T2CB which contains an input from her and Bob's T1CB and two outputs:

1. 900 BTC to: SHA256 h EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
2. 100 BTC to: SHA256 h EQUALVERIFY PubkeyBob CHECKSIGVERIFY

where, again, <code>h</code> is a hash from a previous payment, which could be different than the <code>h</code> in T2AC.

Alice requests for Carol to send 10 mBTC to Bob on her behalf. When she requests this, she also signs and sends to Carol a new version of T2AC as follows:

1. 89.99 BTC to: SHA256 Hashm EQUALVERIFY PubkeyAlice CHECKSIGVERIFY
2. 10.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY

Carol will then notify Bob of an incoming payment and signs/sends to Bob a new version of T2CB as follows:

1. 899.99 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
2. 100.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyBob CHECKSIGVERIFY

When Bob sees that a payment has come through, he broadcasts <code>m</code>, the preimage of the payment's commit hash, to Alice and Carol, committing the payment. Bob can't redeem his output without revealing <code>m</code>, so he has incentive not to keep it from the other parties. Risk deposits can be structured in such a way that the incentive to broadcast <code>m</code> in a successful transaction should outweigh the incentive not to broadcast.

Additional applications can be considered as well. For an escrow transaction, as an example, Bob can generate a signed invoice for Alice to pay and its hash is <code>h</code>. Alice would generate a cryptographically strong random number <code>r</code>. Alice would then concatenate the two, <code>m = h . r</code>, and hash <code>m</code>. Then <code>Hashm</code> is the commit hash for the transaction which Alice would give to Bob so he knows what payment to expect for the invoice. Alice can send the payment's first phase, which would lock in funds through a chain of micropayment channels, wait for Bob to deliver the goods, and give Bob <code>r</code>. In this way, the payment is linked to the invoice.

For a gambling transaction similar to SatoshiDice, where Bob is a SatoshiDice-like gambling site, Alice can create a cryptographically strong random <code>r</code>, which is the preimage to the commit hash. Alice would send a payment to Bob and immediately commits it by broadcasting <code>r</code>. Bob would then concatenate <code>w . r</code>, where <code>w</code> is the hash/string/etc. for the time period during which the transaction occurs, and hash it to get the number used to determine whether the play wins or not.

The preimage to the commit hash can be used to carry all sorts of varied information; however, in the event of large amounts of data, the preimage should itself be a hash of that data, potentially concatenated with a random number as above. This reduces the amount of data to transmit across the payment channel and the amount of data potentially committed to the block chain should one of the recipients in the chain of micropayment channels decide to settle the channel with that commit hash.

Alice, Bob and Carol are nodes in a directional graph, while the micropayment channels between them are edges. It's easy to see how to extend such a chain to more than two micropayment channels by adding more intermediaries. Regardless of the number of intermediaries between the payer and payee, the payment can be proposed and committed almost instantly with no impact on the block chain and no possibility of double spend.

Fees could be charged for two separate actions: establishment of a micropayment channel, in order to offset the transaction fees for getting the contract in the block chain, and each payment, in order to offset operating costs and cost of capital to lock up money in a payment flow until it's committed or rolled back.

One can also imagine a long chain in which, for some reason (possibly malice), a payment is committed and an intermediary node X doesn't receive the broadcast of the preimage of that payment's commitment hash. If that occurs and another node Y broadcasts a T2Y transaction with that payment's commitment hash in an output to the Bitcoin network, node X can immediately broadcast its T2X transaction with the same commitment hash. Then, when node Y or the peer node for its micropayment channel redeems their output from the T2Y transaction, or X's peer node redeems its output from the T2X transaction, X can redeem its output.

== Routing and Reputation in the Block Chain ==

In the micropayment channel scheme, T1 is broadcast and committed to the block chain to create the channel. In this proposal's modified scheme, T2, which redeems T1's only output, is not broadcast until the channel is to be closed and settled. Thus, routing and reputation information exists on the block chain. It is prunable as all transaction outputs are redeemable and should be redeemed; however, intermediate nodes which need to route payments through the network should keep the entire block chain in order to be able to extract routing and especially reputation information from it.

There would exist a set of participant public keys which have participated in micropayment channels before. Any transactions in the format of T1 that are not yet redeemed by a transaction of format T2 may be considered open channels. In most cases, the directionality of the micropayment channel should be identifiable by the amounts contributed by each key: the key which contributes more is likely to be the sender, and the key which contributes less is likely to be the recipient. This should be the case even when risk deposits are used between sender and recipient.

In addition, T1 transactions whose outputs haven't been redeemed for too long, or T2 transactions committed to the block chain whose outputs haven't been redeemed could be considered negative reputation information. Successful transactions can be considered positive reputation information. A PageRank-style iterative convergence algorithm can establish both a web of trust and a routing graph showing trust/channel relationships between various intermediaries.

When deciding to find a new peer with which to maintain open micropayment channels, various strategies can be considered based on both the reputation and routing information presented in the block chain. A node could choose to peer with more central intermediaries to make it cheap to send funds through that node; a node could also choose to peer with underserved parts of the graph (detectable by frequency of establishment/closure of channels to that part of the graph) in order to make money by making transmission to that part more efficient.

Using the block chain for extracting routing and reputation information does not preclude using external sources of routing and reputation information or using other methods of storing/extracting such information from the block chain.

== Potential Optimizations and Side Effects ==

It is possible to make most users' nodes on such a peer-to-peer network function similarly to SPV nodes on the main Bitcoin network. The end user nodes would manually decide to establish a channel with a small set of intermediaries. There would be no or minimal trust involved due to the structure of the micropayment channel and the ability to withhold commitment of a payment until the payer is sure it has been routed correctly to the payee. Such users would benefit from having an SPV-style connection to the peer-to-peer network in order to open and close micropayment channels with the manually chosen set of intermediary nodes.

Intermediary nodes could be run by hobbyists/enthusiasts who want to make money by supporting the network, as well as businesses which desire reduced transaction costs on their own inbound and outbound payments and profit from processing others' payment flow. Such intermediaries would be well-served by running full nodes on the Bitcoin network in order to keep up-to-date track of routing information, as well as to have access to all historical information for optimization and reputation purposes.

Intermediaries on the receiving side can combine T1 transactions from multiple micropayment channels' senders in order to reduce transaction fees. For example, if Alice and multiple parties like her would each like to establish a micropayment channel to Carol, each would use one of her unspent transaction outputs to sign an output using <code>SIGHASH_SINGLE | SIGHASH_ANYONECANPAY</code>. Alice's output would be the value of Alice's input PLUS the value of whatever risk deposit Carol is willing to put in. Carol would then combine all of the inputs and outputs, add her own inputs to make up the value of the risk deposits plus fees to get the transaction included in a block, and broadcast it. Once the transaction has enough confirmations, Carol can begin allowing payments to flow through the newly established channels.

A functioning network would serve to balance costs, efficiency and decentralization. The longer a chain of micropayment channels a payment must go through, the more funds it locks up on its way temporarily and the more fees it would need to pay. For escrow transactions where the funds are locked up for a longer time, it may be more cost-effective to perform the transaction on the block chain, depending on the transaction fees. However, longer micropayment channel chains mean more decentralization. One can imagine a network graph with well-capitalized, well-connected nodes run by large corporations providing cheaper, more centralized payment flow while niche and local nodes provide less centralized payment flow which trades cost or distant node reachability for decentralization and privacy.

A network such as this may encourage intermediaries and businesses to run full nodes on the Bitcoin network, and allows them to collect fees for processing payments without having to mine. This may help fund full nodes on the Bitcoin network by allowing them to charge off-chain clearing fees, whereas miners charge settlement fees for committing transactions to the block chain.

A network such as this may increase the exchange rate of bitcoins against other currencies as it would lock up bitcoins in micropayment channels in order to provide payment flow, thus reducing the number of available bitcoins to sell for other currencies. Early adopters can additionally profit by using their bitcoin capital to provide payment flow. Merchants using existing transaction processors would be able to benefit from the network without needing to make any changes, as long as the transaction processors establish a connection to the network.

As proposed by cjp<ref>http://www.ultimatestunts.nl/bitcoin/ripple_bitcoin_draft_2.pdf</ref>, path splitting is a viable option to make more efficient use of micropayment channels that are too narrow to allow large payments through them. However, this may increase Bitcoin transaction fees for intermediary micropayment channel re-establishment, making large payments more economical to send using Bitcoin directly. The decision should be made by the payer and payee based on cost and whether instant payment is required or waiting for confirmations is acceptable.

Widespread use of a network such as this would reduce, but not eliminate, the need to increase the Bitcoin block size. For example, assume a billion users of such a network, being paid directly on the block chain bi-weekly, each of whom immediately commits the entire payment to a micropayment channel to their preferred, centralized intermediate node. Each year, there would be 26 billion outputs added to the block chain for payroll, 26 billion T1 outputs and 52 billion T2 outputs for the micropayment channels. That's 104 billion outputs per year, or on average 1,978,691 outputs per block, or 3,298 transactions per second, not counting setup and teardown of intermediary micropayment channels and the uneven time distribution of payroll transactions.

== Privacy and Centralized Control ==

One can imagine a future in which Bitcoin is widely adopted and a network based on this proposal to be widely used for clearing instant payments. It's possible that a governmental entity could regulate part of a network by mandating the following whitelist conditions:

# Merchants, end users and intermediaries within the jurisdiction MUST use a key signed by the government's CA, providing identifying information for such a signature
# Merchants, end users and intermediaries within the jurisdiction MUST establish micropayment channels with ONLY other nodes using keys signed by the government's CA
# Merchants and intermediaries within the jurisdiction MUST track the initial source, final destination and possibly entire path of payment flow

One can also imagine a somewhat separate but similar network, where:

# Most nodes live on Tor or in jurisdictions friendly to financial freedom and privacy.
# Many end users and local/niche businesses run intermediary nodes for the benefit of their friends, family and community with a commitment not to log information.
# All or some keys on the network are ephemeral, and each time a micropayment channel closes and settles on the block chain, the output of the settlement transaction is sent at least once through a network providing 3-party mixing transactions<ref>https://bitcointalk.org/index.php?topic=54266.0</ref>. This may necessitate additional routing information outside the block chain as well as additional anti-DoS risk management solutions. This also provides for the potential of intermediaries having multiple keys at the same time, allowing them to create "hidden" links in micropayment channel chains and further improving privacy.

It would be difficult to move bitcoins directly between the two networks without being tracked; however, one can imagine that a market would develop in helping to facilitate and hide such movement. The fact that such a market would develop and be difficult if not impossible to stop would hopefully prevent most governments from attempting to establish rules such as above. In a worst-case scenario, "free" bitcoins will be worth more than "government-controlled" bitcoins and the market would be mostly one-way, laundering "government-controlled" bitcoins into the free network until the values equalize.

== Conclusions ==

This proposal details the synthesis of several ideas described by hashcoin, Meni Rosenfeld, Mike Hearn, cjp, retep, and additional individuals into a mechanism for two-phase commits across chains of micropayment channels, allowing for instant clearing and settlement on the block chain. A decentralized peer-to-peer micropayment network utilizing the side effect of routing and reputation information stored in the block chain is also described. Its scaling properties in the real world may make it viable for micropayments currently, and with increased block size, may make it viable for wide-scale everyday use in retail commerce. Potential points of control and monitoring, as well as countermeasures thereto, are briefly explored. Potential side effects on the Bitcoin network are also explored.

== References ==
<references/>

User:Aakselrod/Draft

2013-03-11T21:03:08Z

Aakselrod:

User:Aakselrod/Draft

2013-02-02T05:22:01Z

Aakselrod: Draft proposal of a decentralized, peer-to-peer payment clearing network which uses Bitcoin for settlement and bitcoins as a unit of account

== Proposal Background and Summary ==

The basic concept of a peer-to-peer payment network which allows nodes to transact off the blockchain has been proposed before<ref>https://bitcointalk.org/index.php?topic=91732.0</ref>. Proponents see multiple advantages such as instant transactions which require no additional confirmations, higher scalability due to individual transactions taking place off the blockchain, and feasibility of widespread micropayments. The proposals use [[Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party|micropayment channels]] between payers, payees, and intermediaries in order to allow such transactions.

For example, if Alice is a customer and Bob is a merchant, Alice may have a micropayment channel open to Carol, her payment processor, who may have a channel open to Dan, Bob's payment processor, which also has a channel open to Bob. Alice would increment the allocation going to Carol through her channel by the amount she wants to pay Bob, and Carol and Dan would do the same down the line. Bob would then be paid, and none of this would hit the blockchain except as part of aggregate settlement transactions closing the micropayment channels.

This proposal aims to bring closer the realization of such a network by discussing the following solutions:

* Additional scalability of micropayment channel setup transactions by having intermediaries combine them
* Two-step commit through multiple chained micropayment channels, reducing the risk that an intermediary will accept a payment but not forward it on and enabling two-party escrow transactions through the payment network
* Extraction of routing and reputation information from the blockchain and memory pool as a side effect of the way micropayment channels are open and closed

The proposal will also discuss possible side effects of its adoption, both positive and negative.

== Micropayment Channels ==

The original concept of the micropayment channel is explained well on the [[Contracts]] page. One issue for current attempts at implementation of these proposal is that transaction replacement is not currently enabled on the Bitcoin network. This makes it more difficult to prevent denial of service (locking up money, potentially permanently depending on whether it's for ransom or not) by an intermediary or a party to a 2-of-2 escrow transaction.

This proposal is designed to work around the current lack of transaction replacement on the network. It can likely be made simpler and more effective against such DoS attacks when transaction replacement is enabled. A future version of this proposal may include the changes that would be necessary to improve the design by the use of transaction replacement.

Two types of proposals have been suggested to discourage and/or make expensive denial of service attacks: risk deposits<ref>https://bitcointalk.org/index.php?topic=118418.msg1271858#msg1271858</ref> and reputation systems<ref>https://bitcointalk.org/index.php?topic=134827.0</ref>. This proposal uses both techniques to help reduce the risk.

Risk deposits are designed to make it unprofitable to blackmail or ransom a micropayment channel peer to pay
<references/>

Contract

2012-03-08T15:23:33Z

Aakselrod: Add Mike Hearn's examples of places where ACs/DACs with Bitcoin would be useful, and link to DAC scheme (formerly exercise for the reader).

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. Minimal trust often makes things more convenient by allowing human judgements to be taken out of the loop, thus allowing complete automation.

Many of the ideas underlying Bitcoin contracts were first described by Nick Szabó in his seminal paper,
[http://szabo.best.vwh.net/formalize.html Formalizing and Securing Relationships on Public Networks].

This page was written by [mailto:mike@plan99.net Mike Hearn]. Contact him if you have an idea for a new type of contract.

==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 transaction's 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, e.g., 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 constructed 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:

# 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 that are not. Intuitively, it means "I agree to put my money in, if everyone puts their money in and the outputs are this".
# 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.
# 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:

# Transactions are passed around outside of the P2P network, in partially-complete or invalid forms.
# 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 that 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 that you open an account on a website (eg, a forum or wiki) and wish to establish your trustworthiness 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 that 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:

# 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 that 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 Tx1 to the website.
# The website creates a transaction Tx2 (the contract). Tx2 spends Tx1 and pays it back to the user via 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 date in the future (eg, six months). The sequence number on the input is set to zero.
# 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; there are only zeros where the user's signature should be. He fixes that by signing the contract and putting the new signature in the appropriate spot.
# The user broadcasts Tx1, then broadcasts Tx2.

At this stage, 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 he 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 (i.e., 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==

A buyer wants to trade with somebody he doesn't know or trust. In the common case where the transaction goes well, the client doesn't want any third parties involved. If something goes wrong though, he'd like a third party to decide who gets the money - perhaps a professional dispute mediation service. Note that this concept can apply to either buyer or seller. The mediator might request proof of postage from the merchant, for example.

In other words, one wants to lock up some coins so a third party has to agree in order for them to be spent:

# Agree with the merchant on a dispute mediator (e.g., ClearCoin).
# Ask the merchant for a public key (K1). Ask the mediator for a public key (K2). Create a new key for yourself (K3).
# 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 merchant.
# 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 only be spent by the following methods:

# Client and the merchant agree (either a successful trade, or merchant agrees to reimburse client without mediation)
# Client and the mediator agree (failed trade, mediator sides with client, like a charge-back)
# The mediator and the merchant agree (goods delivered, merchant gets client's coins despite the dispute)

When signing an input, the contents are set to the connected output. Thus, to redeem this transaction, the client creates a scriptSig containing zeros where the other signature should be, signs it, and then sets one of the slots to his new signature. The partially-complete transaction can then be sent to the merchant or mediator for the second signature.

==Example 3: Assurance contracts==

An [http://en.wikipedia.org/wiki/Assurance_contract assurance contract] is a way of funding the creation of a [http://www.auburn.edu/~johnspm/gloss/public_goods public good], that is, a good that, 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.

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include Internet radio station funding and [https://bitcointalk.org/index.php?topic=67255.msg788110#msg788110 web page translation]. "For example, consider a browser extension that you send a bit of money to. It detects the current language of the page and broadcasts a pledge for a translation into your language to be prepared. If enough users with the extension land on the same page at the same time (eg, it was linked to from somewhere high traffic), then enough pledges are broadcast to trigger a payment to a company who prepares a high quality translation. When complete it automatically loads in your browser."

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:

# An entrepreneur creates a new address and announces that the good will be created if at least 1000 BTC is raised. Anyone can contribute.
# 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 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.
# The transaction is uploaded to the entrepreneur's server, which saves it to disk and updates its count of how many coins have been pledged.
# Once the server has enough coins, it merges the separate transactions together into a new transaction. The new transaction has a single output that 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.
# 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 are 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 inputs 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 that 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, i.e., 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 is prepared that do nothing other than incentivize mining in a series of blocks.

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. [[Dominant Assurance Contracts|A scheme for dominant assurance contracts]] in Bitcoin has been proposed.

==Example 4: Using external state==

Scripts are, by design, pure functions. They cannot poll external servers or import any state that may change as it would allow an attacker to outrun the block chain. But we can make transactions connected to the world in other ways.

Consider the example of an old man who wishes to give an inheritance to his grandson, either on the grandson's 18th birthday or when the man dies, whichever comes first.

To solve this, the man first sends the amount of the inheritance to himself so there is a single output of the right amount. Then he creates a transaction with a lock time of the grandson's 18th birthday that pays the coins to another key owned by the grandson, signs it, and gives it to him - but does not broadcast it. This takes care of the 18th birthday condition. If the date passes, the grandson broadcasts the transaction and claims the coins. He could do it before then, but it doesn't let him get the coins any earlier, and some nodes may choose to drop transactions in the memory pool with lock times far in the future.

The death condition is harder. As Bitcoin nodes cannot measure arbitrary conditions, we must rely on an ''oracle''. An oracle is a server that has a keypair, and signs transactions on request when a user-provided expression evaluates to true.

Here is an example. The man creates a transaction spending his output, and sets the output to:

<sons pubkey> CHECKSIGVERIFY <oracle pubkey> CHECKSIGVERIFY <hash> OP_TRUE

This is the oracle script. It has an unusual form - after signature checking it pushes data to the stack then does not use it. The pubkey is published on the oracle's website and is well-known. The hash is set to be the hash of the user-provided expression stating that he has died, written in a form the oracle knows how to evaluate. For example, it could be the hash of the string:

if (has_died('john smith', born_on=1950/01/02)) return 1JxgRXEHBi86zYzHN2U4KMyRCg4LvwNUrp;

This little language is hypothetical, it'd be defined by the oracle and could be anything. The return value is an address owned by the grandson.

Once more, the man creates this transaction but gives it directly to his grandson instead of broadcasting it. He also provides the expression that is hashed into the transaction and the name of the oracle that can unlock it.

It is used in the following algorithm:

# The oracle accepts a measurement request. The request contains the user-provided expression, a copy of the output script, and a partially complete transaction provided by the user. Everything in this transaction is finished except for the scriptSig, which contains just one signature (the grandson's) - not enough to unlock the output.
# The oracle checks the user-provided expression hashes to the value in the provided output script. If it doesn't, it returns an error.
# The oracle evaluates the expression. If the result is not the destination address of the output, it returns an error.
# Otherwise the oracle signs the transaction and inserts the signature into the scriptSig. Note that when signing a Bitcoin transaction, the input script is set to the connected output script. The reason is that when OP_CHECKSIG runs, the script containing the opcode is put in the input being evaluated, _not_ the script containing the signature itself. The oracle has never seen the full output it is being asked to sign, but it doesn't have to. It knows the output script, its own public key, and the hash of the user-provided expression, which is everything it needs to check the output script and finish the transaction.
# The oracle returns the newly signed, unbroadcast transaction to the user.

If, and only if, the oracle agrees that the man is dead, the grandson can broadcast the two transactions (the contract and the claim) and take the coins.

The oracle does not need to be highly trusted. It has not seen the transaction the grandson is trying to unlock, as it was never broadcast, thus, the oracle cannot hold the grandson to ransom because it does not know whether the transaction it's signing for even exists. People can, and should, regularly challenge the oracle in an automated fashion to ensure it always outputs what is expected. The challenges can be done without spending any coins because the tx to be signed can be invalid (ie, connected to transactions that don't exist). The oracle has no way to know whether a request to be signed is random or real. CHECKSIGVERIFY can be replaced with CHECKMULTISIGVERIFY to allow for n-of-m oracles if need be.

Oracles can potentially evaluate anything, yet the output script form in the block chain can always be the same. Consider the following possibilities:

today() == 2011/09/25 && exchange_rate(mtgoxUSD) >= 12.5 && exchange_rate(mtgoxUSD) <= 13.5
Require exchange rate to be between two values on a given date

google_results_count(site:www.google.com/hostednews 'Mike Hearn' olympic gold medal) > 0
A bet on me doing something that I will never actually do

// Choose between one of two winners of a bet on the outcome of the Eurovision song contest.
if (eurovision_winner() == 'Azerbaijan')
return 1Lj9udBVDwptFffGSJSC2sohCfudQgSTPD;
else
return 1JxgRXEHBi86zYzHN2U4KMyRCg4LvwNUrp;

The conditions that control whether the oracle signs can be arbitrarily complex, but the block chain never needs to contain more than a single hash.

==Example 5: Trading across chains==

The Bitcoin technology can be adapted to create [[Alternative Chains|multiple, independent currencies]]. NameCoin is an example of one such currency that operates under a slightly different set of rules, and can also be used to rent names in a namespace. Currencies that implement the same ideas as Bitcoin can be traded freely against each other without trust. For example, imagine a consortium of companies that issue EURcoins, a crypto-currency that is backed 1:1 by deposits in the consortium's bank accounts. Such a currency would have a different set of tradeoffs to Bitcoin: more centralized, but without FX risk. People might wish to trade Bitcoins for EURcoins back and forth, with the companies only getting involved when cashing in/out of the regular banking system.

To implement this, a protocol proposed by luxgladius can be used:

# Both parties generate a new key and some random data (the secret).
# Party 'B' sends a hash of his secret to 'A' along with his public key.
# Party 'A' generates Tx1 (the payment) containing an output with the chain-trade script in it. See below for this script and a discussion of it. It allows coin release either by signing with the two keys (key 'A' and key 'B') or with (secret 'A', secret 'B', key 'B'). This transaction is not broadcast. The chain release script contains hashes, not the actual secrets themselves.
# Party 'A' generates Tx2 (the contract), which spends Tx1 and has an output going back to key 'A'. It has a lock time in the future and the input has a sequence number of zero, so it can be replaced. 'A' signs Tx2 and sends it to 'B', who also signs it and sends it back. Alternatively, they can simply agree on what form the contract takes, e.g., by using the same software, and then 'A' can simply send 'B' the hash of Tx1 and receive back a signature.
# 'A' broadcasts Tx1 and Tx2. Party 'B' can now see the coins but cannot spend them because it does not have an output going to him, and the tx is not finalized anyway.
# 'B' performs the same scheme in reverse on the alternative chain. Both sides of the trade are now pending but incomplete.
# 'A' sends his secret (random data) to 'B', who then uses it to re-issue the now-finalized contract using (secret 'A', secret 'B', key 'B') and an output of his choice. 'B' now owns the coins, but in the process of claiming them, revealed his secret, allowing 'A' to claim the other side of the trade.

Because the protocol is trust-free, it would be feasible to do trades automatically in an entirely peer-to-peer manner, which should ensure good liquidity.

The chain-trade script could look like this:

IF
2 <key A> <key B> 2 CHECKMULTISIGVERIFY
ELSE
<key B> CHECKSIGVERIFY SHA256 <hash of secret A> EQUALVERIFY <hash of secret B> EQUALVERIFY
ENDIF

The contract input script looks like either:

<sig A> <sig B> 1

or

<secret B> <secret A> <sig B> 0

i.e., the first data element selects which phase is being used.

==Example 6: Smart property==

It's possible to make physical property, like houses, cars or phones, be atomically tradeable and lendable via the block chain. This topic has its own article: learn more about [[Smart Property|smart property]].

==Example 7: Rapidly-adjusted (micro)payments to a pre-determined party==

Bitcoin transactions are very cheap relative to traditional payment systems, but still have a cost due to the need for it to be mined and stored. There are some cases in which you want to rapidly and cheaply adjust the amount of money sent to a particular recipient without incurring the cost of a broadcast transaction.

For example, consider an untrusted internet access point, like a WiFi hotspot in a cafe you never visited before. You'd like to pay 0.001 BTC per 10 kilobytes of usage, without opening an account with the cafe. A zero-trust solution means it could be fully automatic, so you could just pre-allocate a budget on your phone's mobile wallet at the start of the month, and then your device automatically negotiates and pays for internet access on demand. The cafe also wants to allow anyone to pay them without the fear of being ripped off.

To do this, a protocol similar to one proposed by hashcoin can be used:

# Request a public key from the access point.
# Create, but do not sign, a transaction (T1) that sets up a payment of (for example) 10 BTC to an output requiring both the access point's public key and one of your own to be used. The value to be used is chosen as an efficiency tradeoff.
# Create, but do not sign, another transaction (T2) that has two outputs, one to the access point's key and another that goes back to you. The initial value is 0.001 BTC to the access point and the rest back to you. Use a sequence number of zero on the input and a lock time in the future (e.g., 1 day).
# Send both unsigned transactions to the access point. It sees that T1 and T2 are of the expected form and signs T2. It hands T2 back to you.
# Check that T2 is signed correctly, sign T1 and T2. Send them to the access point, which broadcasts them, thus locking in the agreement. Note that T2 won't get included into a block for at least one day, unless it's replaced by a newer transaction, as determined by the sequence numbers.
# Each time you want 10kb of data quota, sign a new version of T2 with a higher sequence number, the same lock time, and adjust the outputs so more value is allocated to the access point, and send it. The AP sees that the output sizes are correct, signs it, and keeps it (does not broadcast).

This continues until the session ends, or the 1-day period is getting close to expiry. The AP broadcasts the last transaction it saw, replacing the original that was pending. Once the lock time passes, the value transfer is committed. Alternatively, if the session end is negotiated cleanly, the user can sign a transaction that's final (sequence number of UINT_MAX), which signals that no more data quota will be purchased, allowing instant commitment of the transaction.

The lock time and sequence numbers avoid an attack in which the AP provides connectivity, and then the user double-spends the output back to themselves using the first version of TX2, thus preventing the cafe from claiming the bill. If the user does try this, the TX won't be included right away, giving the access point a window of time in which it can observe the TX broadcast, and then broadcast the last version it saw, overriding the user's attempted double-spend.

==See Also==

* [[Script]]

[[Category:Technical]]

User:Aakselrod

2012-03-07T15:01:56Z

Aakselrod:

My name is Alex Akselrod. [http://bitcoin-otc.com/viewgpg.php?nick=aakselrod Here] is my OTC identity. [https://bitcointalk.org/index.php?action=profile;u=38311 Here] is my BitcoinTalk forum profile. I'm particularly interested in using Bitcoin as a transaction/contract vehicle in other peer-to-peer networks for allocation of resources. This makes me interested in various forms of contract schemes possible in Bitcoin.

Dominant Assurance Contracts

2012-03-06T18:32:07Z

Aakselrod: Created page with "This scheme is an attempt at Mike Hearn's exercise for the reader: an implementation of dominant assurance contract..."

This scheme is an attempt at [[User:Mike|Mike Hearn]]'s [[Contracts#Example_3:_Assurance_contracts|exercise for the reader]]: an implementation of dominant assurance contracts. The scheme requires the use of multisignature transactions, nLockTime and transaction replacement which means it won't work until these features are available on the Bitcoin network.

# A vendor agrees to produce a good if X BTC are raised by date D and to pay Y BTC to each of n contributors if X BTC are not raised by date D, or to pay nY BTC if X BTC are raised and the vendor fails to produce the good to the satisfaction of 2 of 3 independent arbitrators picked through a fair process
# The arbitrators specify a 2-of-3 multisignature script to use as an output for the fundraiser with a public key from each arbitrator, which will allow them to judge the performance on actually producing the good
# For each contributor:
## The vendor and the contributor exchange public keys
## They create a 2-of-2 multisignature output from those public keys
## With no change, they create but do not sign a transaction with an input of X/n BTC from the contributor and an input of Y BTC from the vendor, with X/n+Y going to the output created in 3.2
## The contributor creates a transaction where the output is X+nY to the address created in step 2 and the input is the output of the transaction in 3.3, signs it using SIGHASH_ALL | SIGHASH_ANYONECANPAY, with version = UINT_MAX and gives it to the vendor
## The vendor creates a transaction of the entire balance of the transaction in 3.3 to the contributor with nLockTime of D and version < UINT_MAX, signs it and gives it to the contributor
## The vendor and contributor then both sign the transaction in 3.3 and broadcast it to the network, making the transaction in 3.4 valid when enough contributors participate and the transaction in 3.5 valid when nLockTime expires
# As date D nears, nLockTime comes close to expiration.
## If enough (n) people contribute, all of the inputs from 3.4 can combine to make the output valid when signed by the vendor, creating a valid transaction sending that money to the arbitrators, which only agree to release the funds when the vendor produces a satisfactory output
## If not enough people (<n) contribute, nLockTime expires on the transaction in 3.5, meaning each contributor can sign and redeem her transaction containing X/n + Y BTC from 3c
## Note that there is a limit at which it can be more profitable for the vendor to make the remaining contributions when D approaches
# Now the arbitrators have control of X (the payment from the contributors) + nY (the performance bond from the vendor) BTC and pay the vendor only when the vendor performs satisfactorily

Such contracts can be used for crowdfunding. Notable examples from Mike Hearn include:

* Funding Internet radio stations which don't want to play ads: donations are the only viable revenue source as pay-for-streaming models allow undercutting by subscribers who relay the stream to their own subscribers
* Automatically contributing to the human translation of web pages

User:Aakselrod

2012-03-06T17:17:52Z

Aakselrod: Created page with "My name is Alex Akselrod and I don't know what to write here."

My name is Alex Akselrod and I don't know what to write here.