Bitcoin Wiki - User contributions [en]

OP CHECKSIG

2014-07-29T21:50:05Z

Amiller: typo

OP_CHECKSIG is [[Script|script]] opcode used to verify that the signature for a tx input is valid. OP_CHECKSIG expects two values to be on the stack, these are, in order of stack depth, the public key and the signature of the script. These two values are normally obtained by running the scriptSig script of the transaction input we are attempting to validate. After the scriptSig script is run the script is deleted but the stack is left as is, and then the scriptPubKey script from the previous transaction output that is now being spent is run, generally concluding in an OP_CHECKSIG.

The standard scriptPubKey checks that the public key (actually a hash of) is a particular value, and that OP_CHECKSIG passes.

For normal transaction inputs if the creator of the current transaction can successfully create a ScriptSig signature that uses the right public key for the ScriptPubKey of the transaction output they are attempting to spend, that transaction input is considered valid.

== Parameters ==

In addition to the script code itself and the stack parameters, to operate OP_CHECKSIG needs to know the current transaction and the index of current transaction input.

== How it works ==
Firstly always this (the default) procedure is applied:
[[File:Bitcoin_OpCheckSig_InDetail.png|thumb|right|Signature verification process of the default procedure]]
# the public key and the signature are popped from the stack, in that order. If the hash-type value is 0, then it is replaced by the last_byte of the signature. Then the last byte of the signature is always deleted.
# A new subscript is created from the instruction from the most recently parsed OP_CODESEPARATOR (last one in script) to the end of the script. If there is no OP_CODESEPARATOR the entire script becomes the subscript (hereby referred to as subScript)
# The sig is deleted from subScript.
# All OP_CODESEPARATORS are removed from subScript
# The hashtype is removed from the last byte of the sig and stored
# A copy is made of the current transaction (hereby referred to txCopy)
# The scripts for all transaction inputs in txCopy are set to empty scripts (exactly 1 byte 0x00)
# The script for the current transaction input in txCopy is set to subScript (lead in by its length as a var-integer encoded!)

Now depending on the hashtype various things can happen to txCopy, these will be discussed individually.

'''Hashtype Values (from script.h):'''
{|class="wikitable"
! Name !! Value
|-
| SIGHASH_ALL || 0x00000001
|-
| SIGHASH_NONE || 0x00000002
|-
| SIGHASH_SINGLE || 0x00000003
|-
| SIGHASH_ANYONECANPAY || 0x00000080
|}

<ol>
<li> If (hashtype&31) = SIGHASH_NONE then apply the SIGHASH_NONE-procedure
<li> If (hashtype&31) = SIGHASH_SINGLE then apply the SIGHASH_SINGLE-procedure
<li> If hashtype & SIGHASH_ANYONECANPAY then apply the SIGHASH_ANYONECANPAY-procedure
</ol>
Hence, hashtype SIGHASH_ANYONECANPAY may be applied also after any other hashtype-procedure<ref>[http://sourceforge.net/projects/bitcoin/files/Bitcoin/bitcoin-0.7.1/bitcoin-0.7.1-linux.tar.gz file src/src/script.cpp in bitcoin-0.7.1]</ref>. Besides the four listed hashtypes only a hashtype of value 0 appears a few times in the (main) block chain (and is handled like SIGHASH_ALL).

=== Hashtype SIGHASH_ALL (default) ===

No special further handling occurs in the default case. Think of this as "sign '''all''' of the outputs." Which is already done by the default procedure.

=== Procedure for Hashtype SIGHASH_NONE ===

# The output of txCopy is set to a vector of zero size.
# All other inputs aside from the current input in txCopy have their nSequence index set to zero

Think of this as "sign '''none''' of the outputs-- I don't care where the bitcoins go."

=== Procedure for Hashtype SIGHASH_SINGLE ===

# The output of txCopy is resized to the size of the current input index+1.
# All other txCopy outputs aside from the output that is the same as the current input index are set to a blank script and a value of (long) -1.
# All other txCopy inputs aside from the current input are set to have an nSequence index of zero.

Think of this as "sign '''one''' of the outputs-- I don't care where the other outputs go".

Note: The transaction that uses SIGHASH_SINGLE type of signature should not have more inputs than outputs.
However if it does (because of the pre-existing implementation), it shall not be rejected, but instead for every "illegal" input (meaning: an input that has an index bigger than the maximum output index) the node should still verify it, though assuming the hash of 0000000000000000000000000000000000000000000000000000000000000001 [https://bitcointalk.org/index.php?topic=260595.0]

=== Procedure for Hashtype SIGHASH_ANYONECANPAY ===

# The txCopy input vector is resized to a length of one.
# The subScript (lead in by its length as a var-integer encoded!) is set as the first and only member of this vector.

Think of this as "Let other people add inputs to this transaction, I don't care where the rest of the bitcoins come from."

===Final signature check===

An array of bytes is constructed from the serialized txCopy appended by four bytes for the hash type. This array is sha256 hashed twice, then the public key is used to check the supplied signature against the hash.
The secp256k1 elliptic curve is used for the verification with the given public key.

== Return values ==

OP_CHECKSIG will push true to the stack if the check passed, false otherwise.
OP_CHECKSIG_VERIFY leaves nothing on the stack but will cause the script eval to fail immediately if the check does not pass.

== Code samples and raw dumps ==

Taking the first transaction in Bitcoin which is in block number 170, we would get after serialising the transaction but before we hash+sign (or verify) it:

* http://blockexplorer.com/block/00000000d1145790a8694403d4063f323d499e655c83426834d4ce2f8dd4a2ee
* http://blockexplorer.com/tx/f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

See also [https://gitorious.org/libbitcoin/libbitcoin libbitcoin] for code samples.

<pre>
01 00 00 00 version
01 number of inputs (var_uint)

input 0:
c9 97 a5 e5 6e 10 41 02 input address hash
fa 20 9c 6a 85 2d d9 06
60 a2 0b 2d 9c 35 24 23
ed ce 25 85 7f cd 37 04
00 00 00 00 input index

48 size of script (var_uint)
47 push 71 bytes to stack
30 44 02 20 4e 45 e1 69
32 b8 af 51 49 61 a1 d3
a1 a2 5f df 3f 4f 77 32
e9 d6 24 c6 c6 15 48 ab
5f b8 cd 41 02 20 18 15
22 ec 8e ca 07 de 48 60
a4 ac dd 12 90 9d 83 1c
c5 6c bb ac 46 22 08 22
21 a8 76 8d 1d 09 01
ff ff ff ff sequence

02 number of outputs (var_uint)

output 0:
00 ca 9a 3b 00 00 00 00 amount = 10.00000000
43 size of script (var_uint)
script for output 0:
41 push 65 bytes to stack
04 ae 1a 62 fe 09 c5 f5
1b 13 90 5f 07 f0 6b 99
a2 f7 15 9b 22 25 f3 74
cd 37 8d 71 30 2f a2 84
14 e7 aa b3 73 97 f5 54
a7 df 5f 14 2c 21 c1 b7
30 3b 8a 06 26 f1 ba de
d5 c7 2a 70 4f 7e 6c d8
4c
ac OP_CHECKSIG

output 1:
00 28 6b ee 00 00 00 00 amount = 40.00000000
43 size of script (var_uint)
script for output 1:
41 push 65 bytes to stack
04 11 db 93 e1 dc db 8a
01 6b 49 84 0f 8c 53 bc
1e b6 8a 38 2e 97 b1 48
2e ca d7 b1 48 a6 90 9a
5c b2 e0 ea dd fb 84 cc
f9 74 44 64 f8 2e 16 0b
fa 9b 8b 64 f9 d4 c0 3f
99 9b 86 43 f6 56 b4 12
a3
ac OP_CHECKSIG

00 00 00 00 locktime
01 00 00 00 hash_code_type (added on)

result =
01 00 00 00 01 c9 97 a5 e5 6e 10 41 02 fa 20 9c 6a 85 2d d9 06 60 a2 0b 2d 9c 35
24 23 ed ce 25 85 7f cd 37 04 00 00 00 00 43 41 04 11 db 93 e1 dc db 8a 01 6b 49
84 0f 8c 53 bc 1e b6 8a 38 2e 97 b1 48 2e ca d7 b1 48 a6 90 9a 5c b2 e0 ea dd fb
84 cc f9 74 44 64 f8 2e 16 0b fa 9b 8b 64 f9 d4 c0 3f 99 9b 86 43 f6 56 b4 12 a3
ac ff ff ff ff 02 00 ca 9a 3b 00 00 00 00 43 41 04 ae 1a 62 fe 09 c5 f5 1b 13 90
5f 07 f0 6b 99 a2 f7 15 9b 22 25 f3 74 cd 37 8d 71 30 2f a2 84 14 e7 aa b3 73 97
f5 54 a7 df 5f 14 2c 21 c1 b7 30 3b 8a 06 26 f1 ba de d5 c7 2a 70 4f 7e 6c d8 4c
ac 00 28 6b ee 00 00 00 00 43 41 04 11 db 93 e1 dc db 8a 01 6b 49 84 0f 8c 53 bc
1e b6 8a 38 2e 97 b1 48 2e ca d7 b1 48 a6 90 9a 5c b2 e0 ea dd fb 84 cc f9 74 44
64 f8 2e 16 0b fa 9b 8b 64 f9 d4 c0 3f 99 9b 86 43 f6 56 b4 12 a3 ac 00 00 00 00
01 00 00 00
</pre>

To understand where that raw dump has come from, it may be useful to examine tests/ec-key.cpp in [https://gitorious.org/libbitcoin/libbitcoin libbitcoin],

[https://gitorious.org/libbitcoin/libbitcoin libbitcoin] has a unit test under tests/ec-key.cpp (make ec-key && ./bin/tests/ec-key). There is also a working OP_CHECKSIG implementation in src/script.cpp under script::op_checksig(). See also the unit test: tests/script-test.cpp

<source lang="cpp">
#include <iostream>
#include <iomanip>
#include <bitcoin/util/serializer.hpp>
#include <bitcoin/util/elliptic_curve_key.hpp>
#include <bitcoin/util/sha256.hpp>
#include <bitcoin/util/assert.hpp>
#include <bitcoin/util/logger.hpp>
#include <bitcoin/types.hpp>
#include <openssl/ecdsa.h>
#include <openssl/obj_mac.h>
using libbitcoin::elliptic_curve_key;
using libbitcoin::serializer;
using libbitcoin::hash_digest;
using libbitcoin::data_chunk;
using libbitcoin::log_info;
using libbitcoin::log_fatal;

int main()
{
serializer ss;
// blk number 170, tx 1, input 0
// version = 1
ss.write_4_bytes(1);
// 1 inputs
ss.write_var_uint(1);

// input 0
// prevout hash
ss.write_hash(hash_digest{0x04, 0x37, 0xcd, 0x7f, 0x85, 0x25, 0xce, 0xed, 0x23, 0x24, 0x35, 0x9c, 0x2d, 0x0b, 0xa2, 0x60, 0x06, 0xd9, 0x2d, 0x85, 0x6a, 0x9c, 0x20, 0xfa, 0x02, 0x41, 0x10, 0x6e, 0xe5, 0xa5, 0x97, 0xc9});
// prevout index
ss.write_4_bytes(0);

// input script after running OP_CHECKSIG for this tx is a single
// OP_CHECKSIG opcode
data_chunk raw_data;
raw_data = {0x04, 0x11, 0xdb, 0x93, 0xe1, 0xdc, 0xdb, 0x8a, 0x01, 0x6b, 0x49, 0x84, 0x0f, 0x8c, 0x53, 0xbc, 0x1e, 0xb6, 0x8a, 0x38, 0x2e, 0x97, 0xb1, 0x48, 0x2e, 0xca, 0xd7, 0xb1, 0x48, 0xa6, 0x90, 0x9a, 0x5c, 0xb2, 0xe0, 0xea, 0xdd, 0xfb, 0x84, 0xcc, 0xf9, 0x74, 0x44, 0x64, 0xf8, 0x2e, 0x16, 0x0b, 0xfa, 0x9b, 0x8b, 0x64, 0xf9, 0xd4, 0xc0, 0x3f, 0x99, 0x9b, 0x86, 0x43, 0xf6, 0x56, 0xb4, 0x12, 0xa3};
data_chunk raw_script;
raw_script = data_chunk();
raw_script.push_back(raw_data.size());
libbitcoin::extend_data(raw_script, raw_data);
raw_script.push_back(172);
ss.write_var_uint(raw_script.size());
ss.write_data(raw_script);
// sequence
ss.write_4_bytes(0xffffffff);

// 2 outputs for this tx
ss.write_var_uint(2);

// output 0
ss.write_8_bytes(1000000000);
// script for output 0
raw_data = {0x04, 0xae, 0x1a, 0x62, 0xfe, 0x09, 0xc5, 0xf5, 0x1b, 0x13, 0x90, 0x5f, 0x07, 0xf0, 0x6b, 0x99, 0xa2, 0xf7, 0x15, 0x9b, 0x22, 0x25, 0xf3, 0x74, 0xcd, 0x37, 0x8d, 0x71, 0x30, 0x2f, 0xa2, 0x84, 0x14, 0xe7, 0xaa, 0xb3, 0x73, 0x97, 0xf5, 0x54, 0xa7, 0xdf, 0x5f, 0x14, 0x2c, 0x21, 0xc1, 0xb7, 0x30, 0x3b, 0x8a, 0x06, 0x26, 0xf1, 0xba, 0xde, 0xd5, 0xc7, 0x2a, 0x70, 0x4f, 0x7e, 0x6c, 0xd8, 0x4c};
// when data < 75, we can just write it's length as a single byte ('special'
// opcodes)
raw_script = data_chunk();
raw_script.push_back(raw_data.size());
libbitcoin::extend_data(raw_script, raw_data);
// OP_CHECKSIG
raw_script.push_back(172);
// now actually write the script
ss.write_var_uint(raw_script.size());
ss.write_data(raw_script);

// output 1
ss.write_8_bytes(4000000000);
// script for output 0
raw_data = {0x04, 0x11, 0xdb, 0x93, 0xe1, 0xdc, 0xdb, 0x8a, 0x01, 0x6b, 0x49, 0x84, 0x0f, 0x8c, 0x53, 0xbc, 0x1e, 0xb6, 0x8a, 0x38, 0x2e, 0x97, 0xb1, 0x48, 0x2e, 0xca, 0xd7, 0xb1, 0x48, 0xa6, 0x90, 0x9a, 0x5c, 0xb2, 0xe0, 0xea, 0xdd, 0xfb, 0x84, 0xcc, 0xf9, 0x74, 0x44, 0x64, 0xf8, 0x2e, 0x16, 0x0b, 0xfa, 0x9b, 0x8b, 0x64, 0xf9, 0xd4, 0xc0, 0x3f, 0x99, 0x9b, 0x86, 0x43, 0xf6, 0x56, 0xb4, 0x12, 0xa3};
// when data < 75, we can just write it's length as a single byte ('special'
raw_script.push_back(raw_data.size());
libbitcoin::extend_data(raw_script, raw_data);
// OP_CHECKSIG
raw_script.push_back(172);
// now actually write the script
ss.write_var_uint(raw_script.size());
ss.write_data(raw_script);

// End of 2 outputs

// locktime
ss.write_4_bytes(0);

// write hash_type_code
ss.write_4_bytes(1);

// Dump hex to screen
log_info() << "hashing:";
{
auto log_obj = log_info();
log_obj << std::hex;
for (int val: ss.get_data())
log_obj << std::setfill('0') << std::setw(2) << val << ' ';
}
log_info();

data_chunk raw_tx = {0x01, 0x00, 0x00, 0x00, 0x01, 0xc9, 0x97, 0xa5, 0xe5, 0x6e, 0x10, 0x41, 0x02, 0xfa, 0x20, 0x9c, 0x6a, 0x85, 0x2d, 0xd9, 0x06, 0x60, 0xa2, 0x0b, 0x2d, 0x9c, 0x35, 0x24, 0x23, 0xed, 0xce, 0x25, 0x85, 0x7f, 0xcd, 0x37, 0x04, 0x00, 0x00, 0x00, 0x00, 0x43, 0x41, 0x04, 0x11, 0xdb, 0x93, 0xe1, 0xdc, 0xdb, 0x8a, 0x01, 0x6b, 0x49, 0x84, 0x0f, 0x8c, 0x53, 0xbc, 0x1e, 0xb6, 0x8a, 0x38, 0x2e, 0x97, 0xb1, 0x48, 0x2e, 0xca, 0xd7, 0xb1, 0x48, 0xa6, 0x90, 0x9a, 0x5c, 0xb2, 0xe0, 0xea, 0xdd, 0xfb, 0x84, 0xcc, 0xf9, 0x74, 0x44, 0x64, 0xf8, 0x2e, 0x16, 0x0b, 0xfa, 0x9b, 0x8b, 0x64, 0xf9, 0xd4, 0xc0, 0x3f, 0x99, 0x9b, 0x86, 0x43, 0xf6, 0x56, 0xb4, 0x12, 0xa3, 0xac, 0xff, 0xff, 0xff, 0xff, 0x02, 0x00, 0xca, 0x9a, 0x3b, 0x00, 0x00, 0x00, 0x00, 0x43, 0x41, 0x04, 0xae, 0x1a, 0x62, 0xfe, 0x09, 0xc5, 0xf5, 0x1b, 0x13, 0x90, 0x5f, 0x07, 0xf0, 0x6b, 0x99, 0xa2, 0xf7, 0x15, 0x9b, 0x22, 0x25, 0xf3, 0x74, 0xcd, 0x37, 0x8d, 0x71, 0x30, 0x2f, 0xa2, 0x84, 0x14, 0xe7, 0xaa, 0xb3, 0x73, 0x97, 0xf5, 0x54, 0xa7, 0xdf, 0x5f, 0x14, 0x2c, 0x21, 0xc1, 0xb7, 0x30, 0x3b, 0x8a, 0x06, 0x26, 0xf1, 0xba, 0xde, 0xd5, 0xc7, 0x2a, 0x70, 0x4f, 0x7e, 0x6c, 0xd8, 0x4c, 0xac, 0x00, 0x28, 0x6b, 0xee, 0x00, 0x00, 0x00, 0x00, 0x43, 0x41, 0x04, 0x11, 0xdb, 0x93, 0xe1, 0xdc, 0xdb, 0x8a, 0x01, 0x6b, 0x49, 0x84, 0x0f, 0x8c, 0x53, 0xbc, 0x1e, 0xb6, 0x8a, 0x38, 0x2e, 0x97, 0xb1, 0x48, 0x2e, 0xca, 0xd7, 0xb1, 0x48, 0xa6, 0x90, 0x9a, 0x5c, 0xb2, 0xe0, 0xea, 0xdd, 0xfb, 0x84, 0xcc, 0xf9, 0x74, 0x44, 0x64, 0xf8, 0x2e, 0x16, 0x0b, 0xfa, 0x9b, 0x8b, 0x64, 0xf9, 0xd4, 0xc0, 0x3f, 0x99, 0x9b, 0x86, 0x43, 0xf6, 0x56, 0xb4, 0x12, 0xa3, 0xac, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00};
BITCOIN_ASSERT(raw_tx == ss.get_data());

hash_digest tx_hash = libbitcoin::generate_sha256_hash(ss.get_data());

data_chunk pubkey{0x04, 0x11, 0xdb, 0x93, 0xe1, 0xdc, 0xdb, 0x8a, 0x01, 0x6b, 0x49, 0x84, 0x0f, 0x8c, 0x53, 0xbc, 0x1e, 0xb6, 0x8a, 0x38, 0x2e, 0x97, 0xb1, 0x48, 0x2e, 0xca, 0xd7, 0xb1, 0x48, 0xa6, 0x90, 0x9a, 0x5c, 0xb2, 0xe0, 0xea, 0xdd, 0xfb, 0x84, 0xcc, 0xf9, 0x74, 0x44, 0x64, 0xf8, 0x2e, 0x16, 0x0b, 0xfa, 0x9b, 0x8b, 0x64, 0xf9, 0xd4, 0xc0, 0x3f, 0x99, 0x9b, 0x86, 0x43, 0xf6, 0x56, 0xb4, 0x12, 0xa3};
// Leave out last byte since that's the hash_type_code (SIGHASH_ALL in this
// case)
data_chunk signature{0x30, 0x44, 0x02, 0x20, 0x4e, 0x45, 0xe1, 0x69, 0x32, 0xb8, 0xaf, 0x51, 0x49, 0x61, 0xa1, 0xd3, 0xa1, 0xa2, 0x5f, 0xdf, 0x3f, 0x4f, 0x77, 0x32, 0xe9, 0xd6, 0x24, 0xc6, 0xc6, 0x15, 0x48, 0xab, 0x5f, 0xb8, 0xcd, 0x41, 0x02, 0x20, 0x18, 0x15, 0x22, 0xec, 0x8e, 0xca, 0x07, 0xde, 0x48, 0x60, 0xa4, 0xac, 0xdd, 0x12, 0x90, 0x9d, 0x83, 0x1c, 0xc5, 0x6c, 0xbb, 0xac, 0x46, 0x22, 0x08, 0x22, 0x21, 0xa8, 0x76, 0x8d, 0x1d, 0x09};
BITCOIN_ASSERT(signature.size() == 70);

elliptic_curve_key key;
if (!key.set_public_key(pubkey))
{
log_fatal() << "unable to set EC public key";
return -1;
}

log_info() << "checksig returns: " << (key.verify(tx_hash, signature) ? "true" : "false");
return 0;
}

</source>

==References==
<references/>

[[Category:Technical]]
[[Category:Developer]]

Discouraged block

2013-10-17T02:56:12Z

Amiller:

The idea of "discouraging" a block is to not mine on top of that block, instead mining on top of some other block in an attempt to orphan the discouraged block. Bitcoin does not currently implement block discouraging in any form.

Block discouragement is discussed in a forum post, [https://bitcointalk.org/index.php?topic=312668.0 "Feather-forks: enforcing a blacklist with sub-50% hash power"], although the idea predates this.

Research

2013-10-13T13:05:36Z

Amiller:

Publications including research and analysis of Bitcoin or related areas.

{| class="wikitable sortable"
! Title
! Author
! Type
! Year
! Links
|-
| Bitcoin: A Peer-to-Peer Electronic Cash System
| Satoshi Nakamoto
| Research paper
| 2009
| [http://bitcoin.org/bitcoin.pdf Download] [[Bitcoin_paper |wiki page]]
|-
| Triple Entry Accounting
| Ian Grigg
| Research paper
| 2005
| [http://iang.org/papers/triple_entry.html Download]
|-
| Cyberlaundering: Anonymous Digital Cash and Money Laundering
| R. Mark Bortner
| Research paper
| 1996
| [http://osaka.law.miami.edu/~froomkin/seminar/papers/bortner.htm Download]
|-
| Shadowy Figures: Tracking Illicit Financial Transactions in the Murky World of Digital Currencies, Peer–to–Peer Networks, and Mobile Device Payments
| John Villasenor, Cody Monk, Christopher Bronk
| Research paper
| 2011
| [http://www.bakerinstitute.org/publications/ITP-pub-FinancialTransactions-082911.pdf Download]
|-
| An Analysis of Anonymity in the Bitcoin System
| Fergal Reid, Martin Harrigan
| Research paper
| 2011
| [http://arxiv.org/abs/1107.4524 Download], [http://bitcointalk.org/index.php?topic=31539.0 discussion]
|-
| Bitcoin: An Innovative Alternative Digital Currency
| Reuben Grinberg
| Research paper
| 2011
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1817857 Download], [http://www.bitcointalk.org/index.php?topic=6247.0 discussion]
|-
| Bitcoin NFC
| David Allen Bronleewe
| Master's report
| 2011
| [http://repositories.lib.utexas.edu/bitstream/handle/2152/ETD-UT-2011-08-4150/BRONLEEWE-MASTERS-REPORT.pdf?sequence=1 Download], [http://code.google.com/p/bitcoin-nfc source code]
|-
| Optimal pool abuse strategy
| Raulo
| Research paper
| 2011
| [http://bitcoin.atspace.com/poolcheating.pdf Download], [http://www.bitcointalk.org/index.php?topic=3165.0 discussion]
|-
| Abusing Bitcoin cooperative mining pools: strategies for egoistical but honest miners
| Nakamoto Ryo
| Research paper
| 2011
| [http://www.bitcoinservice.co.uk/files/111 Download], [http://www.bitcointalk.org/index.php?topic=2941.0 discussion]
|-
| Analysis of Bitcoin Pooled Mining Reward Systems
| Meni Rosenfeld
| Research paper
| 2011
| [https://bitcoil.co.il/pool_analysis.pdf Download], [http://bitcointalk.org/index.php?topic=32814.0 discussion]
|-
| Bitcoin Exchange system
| Tomáš Jiříček
| Research paper
| 2012
| [https://dip.felk.cvut.cz/browse/pdfcache/jiricto2_2012bach.pdf Download]
|-
| On Bitcoin and Red Balloons
| Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
| Publication article
| 2012
| [http://research.microsoft.com/pubs/156072/bitcoin.pdf Download]
|-
| 2011 Observations on the Digital Currency Industry
| Mark Herpel
| Publication article
| 2011
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1721076 Download]
|-
| MAVE, New Lightweight Digital Signature Protocols for Massive Verifications
| Sergio Demian Lerner
| Research paper
| 2012 (preliminary)
| [http://bitslog.files.wordpress.com/2012/04/mave1.pdf Download]
|-
| MAVEPAY, a New Lightweight Payment Scheme for Peer to Peer Currency Networks
| Sergio Demian Lerner
| Research paper
| 2012 (preliminary)
| [http://bitslog.files.wordpress.com/2012/04/mavepay1.pdf Download]
|-
| Bitcoin: Eine erste Einordnung (an initial classification)
| Christoph Sorge, Artus Krohn-Grimberghe
| Research paper
| 2012
| [http://www.springerlink.com/content/cw1v762571tr4462/ Download], [http://bitcointalk.org/index.php?topic=90233.0 discussion]
|-
| Bitcoin - an introduction to the workings and a preliminary analysis and understanding of potential legal issues
| Jean-Daniel Schmid, Alexander Schmid
| Article
| 2012
| [http://ef-r.ch/images/publications/1338882576_Bitcoin.pdf Download]
|-
| Secure multiparty Bitcoin anonymization
| Edward Z. Yang
| Article
| 2012
| [http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/ Download], [http://www.reddit.com/r/Bitcoin/comments/wvm2w/secure_multiparty_bitcoin_anonymization/ discussion]
|-
| Bitcoin & Gresham's Law - the economic inevitability of Collapse
| Philipp Güring, Ian Grigg
| Article
| 2011
| [http://iang.org/papers/BitcoinBreachesGreshamsLaw.pdf Download]
|-
| Today Techies, Tomorrow the World? Bitcoin.
| Reuben Grinberg
| Article
| 2012
| [http://www.milkeninstitute.org/publications/review/2012_1/22-31MR53.pdf Download]
|-
| Traveling the Silk Road: A measurement analysis of a large anonymous online marketplace
| Nicolas Christin
| Research paper
| 2012
| [http://www.cylab.cmu.edu/files/pdfs/tech_reports/CMUCyLab12018.pdf Download]
|-
| CommitCoin: Carbon Dating Commitments with Bitcoin
| Jeremy Clark and Aleksander Essex
| Research paper
| 2012
| [http://people.scs.carleton.ca/~clark/papers/2012_fc.pdf Download extended abstract]<br />[http://eprint.iacr.org/2011/677.pdf Download technical report]
|-
| Quantitative Analysis of the Full Bitcoin Transaction Graph
| Dorit Ron and Adi Shamir
| Research paper
| 2012
| [http://eprint.iacr.org/2012/584.pdf Download]
|-
| Design and security analysis of Bitcoin infrastructure using application deployed on Google Apps Engine
| Piotr "ThePiachu" Piasecki
| Master's thesis
| 2012
| [https://dl.dropbox.com/u/3658181/PiotrPiasecki-BitcoinMasterThesis.pdf Download], [https://bitcointalk.org/index.php?topic=88149.0 discussion]
|-
| The Production of Freedom: Value Production in the US- dominated Financial System, and Possible Alternatives
| Jeremy Kirshbaum
| Master's thesis
| 2012 (preliminary)
| [https://docs.google.com/document/d/1JIyMWIibqH8x20vGBTMBZ2yqM7Xbp54UpWBh0o2H7WI/edit?pli=1 Download], [https://bitcointalk.org/index.php?topic=87404.0 discussion]
|-
| COIN: a distributed accounting system for peer to peer networks
| Fabio Varesano
| Bachelor's thesis
| 2012
| [http://www.varesano.net/contents/projects/coin%20distributed%20accounting%20system%20peer%20peer%20networks Download]
|-
| BITCOIN CLIENTS
| Rostislav Skudnov
| Bachelor's thesis
| 2012
| [http://publications.theseus.fi/bitstream/handle/10024/47166/Skudnov_Rostislav.pdf?sequence=1 Download]
|-
| Bitter to Better—How to Make Bitcoin a Better Currency
| Simon Barber, Xavier Boyen, Elaine Shi, Ersin Uzun
| Research paper
| 2012
| [http://crypto.stanford.edu/~xb/fc12/bitcoin.pdf Download]
|-
| NooShare: A decentralized ledger of shared computational resources
| Alex Coventry
| Research paper
| 2012
| [http://mit.edu/alex_c/www/nooshare.pdf Download]
|-
| Bits and Bets. Information, Price Volatility, and Demand for Bitcoin
| Martis Buchholz, Jess Delaney, Joseph Warren
| Final project
| 2012
| [http://academic.reed.edu/economics/parker/s12/312/finalproj/Bitcoin.pdf Download], [http://www.reddit.com/r/Bitcoin/comments/x7kop/economic_analysis_of_the_demand_for_bitcoin discussion], [https://bitcointalk.org/index.php?topic=96003.0 discussion]
|-
| Two Bitcoins at the Price of One? Double Spending attacks on Fast Payments in Bitcoin
| Ghassan O. Karame, Elli Androulaki, Srdjan Cap-kun
| Research paper
| 2012
| [http://eprint.iacr.org/2012/248 Download]
|-
| Nerdy Money: Bitcoin, the Private Digital Currency, and the Case Against Its Regulation
| Nikolei M. Kaplanov
| Research paper
| 2012
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2115203 Abstract]
|-
| Analysis of hashrate-based double-spending
| Meni Rosenfeld
| Research paper
| 2012
| [https://bitcoil.co.il/Doublespend.pdf Download]
|-
| Homomorphic Payment Addresses and the Pay-to-Contract Protocol
| Ilja Gerhardt, Timo Hanke
| Research Paper
| 2012
| [http://arxiv.org/pdf/1212.3257v1 Download] ([http://docs.google.com/viewer?url=http%3A%2F%2Farxiv.org%2Fpdf%2F1212.3257v1 via web viewer])
|-
| Quasi-Commodity Money (February 6, 2012). "This paper considers reform possibilities posed by a type of base money that has heretofore been overlooked in the literature on monetary economics."
| George Selgin
| Working Papers Series
| 2012
| [http://ssrn.com/abstract=2000118 Download]
|-
| Virtual currency schemes - "This report is a first attempt to provide the basis for a discussion on virtual currency schemes."
| European Central Bank
| Paper
| 2012
| [http://www.ecb.europa.eu/pub/pdf/other/virtualcurrencyschemes201210en.pdf Download]
|-
| Evaluating User Privacy in Bitcoin
| Elli Androulaki, Ghassan Karame, Marc Roeschlin, Tobias Scherer and Srdjan Capkun
| Paper
| 2013
| [http://fc13.ifca.ai/proc/1-3.pdf Download] ([http://fc13.ifca.ai/slide/1-3.pdf Slides])
|-
| Beware the Middleman: Empirical Analysis of Bitcoin-Exchange Risk
| Tyler Moore and Nicolas Christin
| Short Paper
| 2013
| [http://fc13.ifca.ai/proc/1-2.pdf Download] ([http://fc13.ifca.ai/slide/1-2.pdf Slides])
|-
| Bitcoin, Regulating Fraud In The E-Conomy Of Hacker-Cash
| Derek A. Dion
| Paper
| 2013
| [http://illinoisjltp.com/journal/wp-content/uploads/2013/05/Dion.pdf Download]
|-
| The practical materiality of Bitcoin
| Bill Maurera, Taylor C. Nelmsa & Lana Swartz
| Paper
| 2013
| [http://www.tandfonline.com/doi/full/10.1080/10350330.2013.777594#.UbbTVaD_6b4 Download]
|-
| Regulating Digital Currencies: Bringing Bitcoin within the Reach of the IMF
| Nicholas Plassaras
| Paper
| 2013
| [https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2248419 Download]
|-
| Bitcoin is Memory
| William J. Luther, Josiah Olson
| Paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2275730 Download]
|-
| The Economics of Bitcoin Mining or, Bitcoin in the Presence of Adversaries
| Joshua A. Kroll, Ian C. Davey, and Edward W. Felten
| Paper
| 2013
| [http://www.weis2013.econinfosec.org/papers/KrollDaveyFeltenWEIS2013.pdf Download]
|-
| Bitcoin: A Primer for Policymakers
| Jerry Brito, Andrea Castillo
| Research paper
| 2013
| [http://mercatus.org/publication/bitcoin-primer-policymakers Abstract] [http://mercatus.org/sites/default/files/Brito_BitcoinPrimer.pdf Download]
|-
| Whack-a-Mole: Prosecuting Digital Currency Exchanges
| Catherine Martin Christopher
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2312787 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2312787_code1372021.pdf?abstractid=2312787&mirid=2 Download]
|-
| Are Cryptocurrencies 'Super' Tax Havens?
| Omri Y. Marian
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2305863 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2316499_code592645.pdf?abstractid=2305863&mirid=1 Download]
|-
| Collective Emergent Institutional Entrepreneurship Through Bitcoin
| Robin Teigland, Zeynep Yetis and Tomas Olov Larsson
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2263707 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2263707_code2053543.pdf?abstractid=2263707&mirid=1 Download]
|}

==See Also==

* [http://people.scs.carleton.ca/~clark/biblio.html Jeremy Clark's Bitcoin Bibliography]
* [[:Category:Economics|Economic]]
* [[:Category:Technical|Technical]]
* [[Press]]

[[Category:Research]]

Research

2013-10-13T13:05:05Z

Amiller:

Publications including research and analysis of Bitcoin or related areas.

{| class="wikitable sortable"
! Title
! Author
! Type
! Year
! Links
|-
| Bitcoin: A Peer-to-Peer Electronic Cash System
| Satoshi Nakamoto
| Research paper
| 2009
| [http://bitcoin.org/bitcoin.pdf Download] [[Bitcoin_paper |wiki page]]
|-
| Triple Entry Accounting
| Ian Grigg
| Research paper
| 2005
| [http://iang.org/papers/triple_entry.html Download]
|-
| Cyberlaundering: Anonymous Digital Cash and Money Laundering
| R. Mark Bortner
| Research paper
| 1996
| [http://osaka.law.miami.edu/~froomkin/seminar/papers/bortner.htm Download]
|-
| Shadowy Figures: Tracking Illicit Financial Transactions in the Murky World of Digital Currencies, Peer–to–Peer Networks, and Mobile Device Payments
| John Villasenor, Cody Monk, Christopher Bronk
| Research paper
| 2011
| [http://www.bakerinstitute.org/publications/ITP-pub-FinancialTransactions-082911.pdf Download]
|-
| An Analysis of Anonymity in the Bitcoin System
| Fergal Reid, Martin Harrigan
| Research paper
| 2011
| [http://arxiv.org/abs/1107.4524 Download], [http://bitcointalk.org/index.php?topic=31539.0 discussion]
|-
| Bitcoin: An Innovative Alternative Digital Currency
| Reuben Grinberg
| Research paper
| 2011
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1817857 Download], [http://www.bitcointalk.org/index.php?topic=6247.0 discussion]
|-
| Bitcoin NFC
| David Allen Bronleewe
| Master's report
| 2011
| [http://repositories.lib.utexas.edu/bitstream/handle/2152/ETD-UT-2011-08-4150/BRONLEEWE-MASTERS-REPORT.pdf?sequence=1 Download], [http://code.google.com/p/bitcoin-nfc source code]
|-
| Optimal pool abuse strategy
| Raulo
| Research paper
| 2011
| [http://bitcoin.atspace.com/poolcheating.pdf Download], [http://www.bitcointalk.org/index.php?topic=3165.0 discussion]
|-
| Abusing Bitcoin cooperative mining pools: strategies for egoistical but honest miners
| Nakamoto Ryo
| Research paper
| 2011
| [http://www.bitcoinservice.co.uk/files/111 Download], [http://www.bitcointalk.org/index.php?topic=2941.0 discussion]
|-
| Analysis of Bitcoin Pooled Mining Reward Systems
| Meni Rosenfeld
| Research paper
| 2011
| [https://bitcoil.co.il/pool_analysis.pdf Download], [http://bitcointalk.org/index.php?topic=32814.0 discussion]
|-
| Bitcoin Exchange system
| Tomáš Jiříček
| Research paper
| 2012
| [https://dip.felk.cvut.cz/browse/pdfcache/jiricto2_2012bach.pdf Download]
|-
| On Bitcoin and Red Balloons
| Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
| Publication article
| 2012
| [http://research.microsoft.com/pubs/156072/bitcoin.pdf Download]
|-
| 2011 Observations on the Digital Currency Industry
| Mark Herpel
| Publication article
| 2011
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1721076 Download]
|-
| MAVE, New Lightweight Digital Signature Protocols for Massive Verifications
| Sergio Demian Lerner
| Research paper
| 2012 (preliminary)
| [http://bitslog.files.wordpress.com/2012/04/mave1.pdf Download]
|-
| MAVEPAY, a New Lightweight Payment Scheme for Peer to Peer Currency Networks
| Sergio Demian Lerner
| Research paper
| 2012 (preliminary)
| [http://bitslog.files.wordpress.com/2012/04/mavepay1.pdf Download]
|-
| Bitcoin: Eine erste Einordnung (an initial classification)
| Christoph Sorge, Artus Krohn-Grimberghe
| Research paper
| 2012
| [http://www.springerlink.com/content/cw1v762571tr4462/ Download], [http://bitcointalk.org/index.php?topic=90233.0 discussion]
|-
| Bitcoin - an introduction to the workings and a preliminary analysis and understanding of potential legal issues
| Jean-Daniel Schmid, Alexander Schmid
| Article
| 2012
| [http://ef-r.ch/images/publications/1338882576_Bitcoin.pdf Download]
|-
| Secure multiparty Bitcoin anonymization
| Edward Z. Yang
| Article
| 2012
| [http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/ Download], [http://www.reddit.com/r/Bitcoin/comments/wvm2w/secure_multiparty_bitcoin_anonymization/ discussion]
|-
| Bitcoin & Gresham's Law - the economic inevitability of Collapse
| Philipp Güring, Ian Grigg
| Article
| 2011
| [http://iang.org/papers/BitcoinBreachesGreshamsLaw.pdf Download]
|-
| Today Techies, Tomorrow the World? Bitcoin.
| Reuben Grinberg
| Article
| 2012
| [http://www.milkeninstitute.org/publications/review/2012_1/22-31MR53.pdf Download]
|-
| Traveling the Silk Road: A measurement analysis of a large anonymous online marketplace
| Nicolas Christin
| Research paper
| 2012
| [http://www.cylab.cmu.edu/files/pdfs/tech_reports/CMUCyLab12018.pdf Download]
|-
| CommitCoin: Carbon Dating Commitments with Bitcoin
| Jeremy Clark and Aleksander Essex
| Research paper
| 2012
| [http://people.scs.carleton.ca/~clark/papers/2012_fc.pdf Download extended abstract]<br />[http://eprint.iacr.org/2011/677.pdf Download technical report]
|-
| Quantitative Analysis of the Full Bitcoin Transaction Graph
| Dorit Ron and Adi Shamir
| Research paper
| 2012
| [http://eprint.iacr.org/2012/584.pdf Download]
|-
| Design and security analysis of Bitcoin infrastructure using application deployed on Google Apps Engine
| Piotr "ThePiachu" Piasecki
| Master's thesis
| 2012
| [https://dl.dropbox.com/u/3658181/PiotrPiasecki-BitcoinMasterThesis.pdf Download], [https://bitcointalk.org/index.php?topic=88149.0 discussion]
|-
| The Production of Freedom: Value Production in the US- dominated Financial System, and Possible Alternatives
| Jeremy Kirshbaum
| Master's thesis
| 2012 (preliminary)
| [https://docs.google.com/document/d/1JIyMWIibqH8x20vGBTMBZ2yqM7Xbp54UpWBh0o2H7WI/edit?pli=1 Download], [https://bitcointalk.org/index.php?topic=87404.0 discussion]
|-
| COIN: a distributed accounting system for peer to peer networks
| Fabio Varesano
| Bachelor's thesis
| 2012
| [http://www.varesano.net/contents/projects/coin%20distributed%20accounting%20system%20peer%20peer%20networks Download]
|-
| BITCOIN CLIENTS
| Rostislav Skudnov
| Bachelor's thesis
| 2012
| [http://publications.theseus.fi/bitstream/handle/10024/47166/Skudnov_Rostislav.pdf?sequence=1 Download]
|-
| Bitter to Better—How to Make Bitcoin a Better Currency
| Simon Barber, Xavier Boyen, Elaine Shi, Ersin Uzun
| Research paper
| 2012
| [http://crypto.stanford.edu/~xb/fc12/bitcoin.pdf Download]
|-
| NooShare: A decentralized ledger of shared computational resources
| Alex Coventry
| Research paper
| 2012
| [http://mit.edu/alex_c/www/nooshare.pdf Download]
|-
| Bits and Bets. Information, Price Volatility, and Demand for Bitcoin
| Martis Buchholz, Jess Delaney, Joseph Warren
| Final project
| 2012
| [http://academic.reed.edu/economics/parker/s12/312/finalproj/Bitcoin.pdf Download], [http://www.reddit.com/r/Bitcoin/comments/x7kop/economic_analysis_of_the_demand_for_bitcoin discussion], [https://bitcointalk.org/index.php?topic=96003.0 discussion]
|-
| Two Bitcoins at the Price of One? Double Spending attacks on Fast Payments in Bitcoin
| Ghassan O. Karame, Elli Androulaki, Srdjan Cap-kun
| Research paper
| 2012
| [http://eprint.iacr.org/2012/248 Download]
|-
| Nerdy Money: Bitcoin, the Private Digital Currency, and the Case Against Its Regulation
| Nikolei M. Kaplanov
| Research paper
| 2012
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2115203 Abstract]
|-
| Analysis of hashrate-based double-spending
| Meni Rosenfeld
| Research paper
| 2012
| [https://bitcoil.co.il/Doublespend.pdf Download]
|-
| Homomorphic Payment Addresses and the Pay-to-Contract Protocol
| Ilja Gerhardt, Timo Hanke
| Research Paper
| 2012
| [http://arxiv.org/pdf/1212.3257v1 Download] ([http://docs.google.com/viewer?url=http%3A%2F%2Farxiv.org%2Fpdf%2F1212.3257v1 via web viewer])
|-
| Quasi-Commodity Money (February 6, 2012). "This paper considers reform possibilities posed by a type of base money that has heretofore been overlooked in the literature on monetary economics."
| George Selgin
| Working Papers Series
| 2012
| [http://ssrn.com/abstract=2000118 Download]
|-
| Virtual currency schemes - "This report is a first attempt to provide the basis for a discussion on virtual currency schemes."
| European Central Bank
| Paper
| 2012
| [http://www.ecb.europa.eu/pub/pdf/other/virtualcurrencyschemes201210en.pdf Download]
|-
| Evaluating User Privacy in Bitcoin
| Elli Androulaki, Ghassan Karame, Marc Roeschlin, Tobias Scherer and Srdjan Capkun
| Paper
| 2013
| [http://fc13.ifca.ai/proc/1-3.pdf Download] ([http://fc13.ifca.ai/slide/1-3.pdf Slides])
|-
| Beware the Middleman: Empirical Analysis of Bitcoin-Exchange Risk
| Tyler Moore and Nicolas Christin
| Short Paper
| 2013
| [http://fc13.ifca.ai/proc/1-2.pdf Download] ([http://fc13.ifca.ai/slide/1-2.pdf Slides])
|-
| Bitcoin, Regulating Fraud In The E-Conomy Of Hacker-Cash
| Derek A. Dion
| Paper
| 2013
| [http://illinoisjltp.com/journal/wp-content/uploads/2013/05/Dion.pdf Download]
|-
| The practical materiality of Bitcoin
| Bill Maurera, Taylor C. Nelmsa & Lana Swartz
| Paper
| 2013
| [http://www.tandfonline.com/doi/full/10.1080/10350330.2013.777594#.UbbTVaD_6b4 Download]
|-
| Regulating Digital Currencies: Bringing Bitcoin within the Reach of the IMF
| Nicholas Plassaras
| Paper
| 2013
| [https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2248419 Download]
|-
| Bitcoin is Memory
| William J. Luther, Josiah Olson
| Paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2275730 Download]
|-
| The Economics of Bitcoin Mining or, Bitcoin in the Presence of Adversaries
| Joshua A. Kroll, Ian C. Davey, and Edward W. Felten
| Paper
| 2013
| [http://www.weis2013.econinfosec.org/papers/KrollDaveyFeltenWEIS2013.pdf Download]
|-
| Bitcoin: A Primer for Policymakers
| Jerry Brito, Andrea Castillo
| Research paper
| 2013
| [http://mercatus.org/publication/bitcoin-primer-policymakers Abstract] [http://mercatus.org/sites/default/files/Brito_BitcoinPrimer.pdf Download]
|-
| Whack-a-Mole: Prosecuting Digital Currency Exchanges
| Catherine Martin Christopher
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2312787 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2312787_code1372021.pdf?abstractid=2312787&mirid=2 Download]
|-
| Are Cryptocurrencies 'Super' Tax Havens?
| Omri Y. Marian
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2305863 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2316499_code592645.pdf?abstractid=2305863&mirid=1 Download]
|-
| Collective Emergent Institutional Entrepreneurship Through Bitcoin
| Robin Teigland, Zeynep Yetis and Tomas Olov Larsson
| Research paper
| 2013
| [http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2263707 Abstract]
[http://papers.ssrn.com/sol3/Delivery.cfm/SSRN_ID2263707_code2053543.pdf?abstractid=2263707&mirid=1 Download]
|-
| Authenticated Data Structures, Generically
| Andrew Miller, Michael Hicks, Jonathan Katz, and Elaine Shi
| Research Paper
| 2014
| [http://www.cs.umd.edu/~mwh/papers/miller14gpads.html Abstract]
[http://www.cs.umd.edu/~mwh/papers/gpads.pdf Download]
|}

==See Also==

* [http://people.scs.carleton.ca/~clark/biblio.html Jeremy Clark's Bitcoin Bibliography]
* [[:Category:Economics|Economic]]
* [[:Category:Technical|Technical]]
* [[Press]]

[[Category:Research]]

Contract

2013-10-10T21:39:29Z

Amiller: Updated to include TierNolan's protocol.

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.

By building low trust protocols that interact with Bitcoin, entirely new products can be created:

* [[Smart Property|Smart property]] is property that can be atomically traded and loaned via the block chain.
* [[Transferable virtual property]] are digital items that can be traded but not duplicated.
* [[Agents]] are autonomous programs that maintain their own wallet, which they use to buy server time. Money is obtained by the agent selling services. If demand exceeds supply the agents can spawn children that either survive or die depending on whether they can get enough business.
* [[Distributed markets]] are a way to implement peer to peer bond and stock trading, allowing Bitcoin to be evolve into a full competitor to the international financial system.
* The [[Ripple currency exchange]] is a way to implement a distributed currency exchange based on social networks.

This page also lists some smaller examples.

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]. These pages were written by [mailto:mike@plan99.net Mike Hearn]. Contact him if you have an idea for a new type of contract. You can watch '''[https://www.youtube.com/watch?feature=player_embedded&v=mD4L7xDNCmA a video of a talk on contracts]''' that was presented at the Bitcoin 2012 conference in London.

==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 the hash of 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.

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.

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include applications where frequent, small pledges need to be made automatically, for instance internet radio station funding and [https://bitcointalk.org/index.php?topic=67255.msg788110#msg788110 web page translation]. 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.

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 for '''[[Funding network security|funding network security]]''' for the next block. In this way, mining can be funded even if block space is not scarce.

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. What's more, the scripting language is extremely limited in what it can do. Fortunately, 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:

<hash> OP_DROP 2 <sons pubkey> <oracle pubkey> CHECKMULTISIG

This is the oracle script. It has an unusual form - it pushes data to the stack then immediately deletes it again. 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 (10.0, 1JxgRXEHBi86zYzHN2U4KMyRCg4LvwNUrp);

This little language is hypothetical, it'd be defined by the oracle and could be anything. The return value is an output: an amount of value and 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 returns the signature to the user. 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 user accepts the new signature, inserts it into the scriptSig and broadcasts the transaction.

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.

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.

As of May 2013 work on implementing this protocol has begun. Please contact Mike if you would like to work on this, so you can be put in touch with the people who are already implementing it.

===Minimizing trust in the oracle===

There are various ways to reduce the level of required trust in the oracle.

Going back to our first example, the oracle has not seen the transaction the grandson is trying to unlock, as it was never broadcast, thus, it 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. How to challenge the oracle with conditions that are not yet true is however an open research question.

The number of keys in the CHECKMULTISIG can be increased to allow for '''n-of-m''' oracles if need be.

Using commodity hardware, you can use '''trusted computing''' in the form of Intel TXT or the AMD equivalent (SKINIT) to set up a sealed hardware environment and then use the TPM chip to attest that fact to a third party. That third party can verify the hardware was in the required state. Defeating this requires someone to be able to interfere with the execution of a program that may run entirely on the CPU, even in extreme cases without any data traversing the memory bus (you can run entirely using on-die cache if the program is small enough).

Cryptographers have recently been making excellent progress in the field of '''verifiable computation'''. This allows an untrusted server to execute a pure function in which some inputs can be private, and produce a proof that it was executed correctly. If the oracle program can be expressed as a pure function, then this technique can be powerfully applied. However there are performance limits. The current state of the art as of summer 2013 is [http://research.microsoft.com/pubs/180286/pinocchio.pdf Pinnochio], an open source system from Microsoft Research. For some classes of functions checking the proof can be faster than executing the program itself, for others it is still slower - however, quite within the realms of feasibility. Because the programs are pure functions, they cannot do any I/O, therefore no access to the internet. This is quite restrictive as often the point of an oracle program is to measure external state. We can work around this restriction by providing signed data to the program and have the program itself check the signatures - to make it as easy as possible to get signed data from as many sources as possible, an extension to the SSL/TLS protocol that allows for signing of arbitrary sessions may be appropriate.

==Example 5: Trading across chains==

The Bitcoin technology can be adapted to create [[Alternative chain|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 with limited 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 [https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949 protocol proposed by TierNolan] can be used:

# Party 'A' generates some random data, x (the secret).
# 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 'x', 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.
# '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. The lock time for 'B' should be much larger than the lock time for 'A'. Both sides of the trade are now pending but incomplete.
# Since 'A' knows the secret, 'A' can claim his coins immediately. However, 'A', in the process of claiming his coin, reveals the secret 'x' to 'B', who then uses it to finish the other side of the trade with ('x', key 'B').

This protocol makes it 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 x> EQUALVERIFY
ENDIF

The contract input script looks like either:

<sig A> <sig B> 1

or

<secret x> <sig B> 0

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

See [[Atomic cross-chain trading]] for details.

Note that whilst EURcoins is a natural idea, there are other ways to implement peer-to-peer currency exchange (Bitcoin to fiat and vice versa), see the [[Ripple currency exchange]] article for more information.

Sergio Demian-Lerner proposed [https://bitcointalk.org/index.php?topic=91843.0 P2PTradeX], a solution requiring the validation rules for one blockchain to be effectively encoded into the validation rules for the other.

==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, the following protocol can be used. This protocol relies upon a '''different''' behavior of nLockTime to the original design. Starting around 2013 time-locked transactions were made non standard and no longer enter the memory pool, thus cannot be broadcast before the timelock expires. When the behaviour of nLockTime is restored to the original design from Satoshi, a variant of this protocol is required which is discussed below.

We define the client to be the party sending value, and the server to be the party receiving it. This is written from the clients perspective.

# Create a public key (K1). Request a public key from the server (K2).
# Create and sign but do not broadcast a transaction (T1) that sets up a payment of (for example) 10 BTC to an output requiring both the server's public key and one of your own to be used. A good way to do this is use OP_CHECKMULTISIG. The value to be used is chosen as an efficiency tradeoff.
# Create a refund transaction (T2) that is connected to the output of T1 which sends all the money back to yourself. It has a time lock set for some time in the future, for instance a few hours. Don't sign it, and provide the unsigned transaction to the server. By convention, the output script is "2 K1 K2 2 CHECKMULTISIG"
# The server signs T2 using its public key K2 and returns the signature to the client. Note that it has not seen T1 at this point, just the hash (which is in the unsigned T2).
# The client verifies the servers signature is correct and aborts if not.
# The client signs T1 and passes the signature to the server, which now broadcasts the transaction (either party can do this if they both have connectivity). This locks in the money.
# The client then creates a new transaction, T3, which connects to T1 like the refund transaction does and has two outputs. One goes to K1 and the other goes to K2. It starts out with all value allocated to the first output (K1), ie, it does the same thing as the refund transaction but is not time locked. The client signs T3 and provides the transaction and signature to the server.
# The server verifies the output to itself is of the expected size and verifies the client's provided signature is correct.
# When the client wishes to pay the server, it adjusts its copy of T3 to allocate more value to the server's output and less to its ow. It then re-signs the new T3 and sends the signature to the server. It does not have to send the whole transaction, just the signature and the amount to increment by is sufficient. The server adjusts its copy of T3 to match the new amounts, verifies the signature and continues.

This continues until the session ends, or the 1-day period is getting close to expiry. The AP then signs and broadcasts the last transaction it saw, allocating the final amount to itself. The refund transaction is needed to handle the case where the server disappears or halts at any point, leaving the allocated value in limbo. If this happens then once the time lock has expired the client can broadcast the refund transaction and get back all the money.

Mike Hearn is working on an implementation of this protocol in bitcoinj. Please [mailto:mike@plan99.net contact him] for more information.

When nLockTime'd transactions are able to enter the memory pool (once more) and transaction replacement has been re-enabled, a variant on the protocol must be used. In this case, no refund transaction is used. Instead each T3 has a sequence number one higher than the previous and all T3's have a time lock set to the same period as above. Each time a payment is made the sequence number is incremented, ensuring that the last version will take precedence. If the channel protocol is not closed cleanly, this means the value transfer won't commit until the time lock expires. To avoid this both parties can cooperate by signing a T3 that has a sequence number of 0xFFFFFFFF resulting in immediate confirmation regardless of the value of nLockTime.

The lock time and sequence numbers avoid an attack in which the AP provides connectivity, and then the user [[double-spending|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.

The latter protocol that relies on transaction replacement is more flexible because it allows the value allocated to go down as well as up during the lifetime of the channel as long as the client receives signatures from the server, but for many use cases this functionality is not required. Replacement also allows for more complex configurations of channels that involve more than two parties. Elaboration on such use cases is a left as an exercise for the reader.

==See Also==

* [[Script]]

[[Category:Technical]]

Contract

2013-03-01T20:44:11Z

Amiller: Undo revision 35836 by Amiller (talk)

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.

By building low trust protocols that interact with Bitcoin, entirely new products can be created:

* [[Smart Property|Smart property]] is property that can be atomically traded and loaned via the block chain.
* [[Transferable virtual property]] are digital items that can be traded but not duplicated.
* [[Agents]] are autonomous programs that maintain their own wallet, which they use to buy server time. Money is obtained by the agent selling services. If demand exceeds supply the agents can spawn children that either survive or die depending on whether they can get enough business.
* [[Distributed markets]] are a way to implement peer to peer bond and stock trading, allowing Bitcoin to be evolve into a full competitor to the international financial system.
* The [[Ripple currency exchange]] is a way to implement a distributed currency exchange based on social networks.

This page also lists some smaller examples.

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]. These pages were written by [mailto:mike@plan99.net Mike Hearn]. Contact him if you have an idea for a new type of contract. You can watch '''[https://www.youtube.com/watch?feature=player_embedded&v=mD4L7xDNCmA a video of a talk on contracts]''' that was presented at the Bitcoin 2012 conference in London.

==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 the hash of 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.

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.

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include applications where frequent, small pledges need to be made automatically, for instance internet radio station funding and [https://bitcointalk.org/index.php?topic=67255.msg788110#msg788110 web page translation]. 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.

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 chain|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 with limited trust. However, because distinct blockchains have different views of time, currently known proposals are susceptible to either a) a loss of funds if one party fails to complete the protocol; or, b) if timeouts are used, a race condition whereby one party could take all the funds. [https://bitcointalk.org/index.php?topic=91843 This was first pointed out] by Sergio Demian-Lerner, who proposed a solution requiring the validation rules for one blockchain to be effectively encoded into the validation rules for the other.

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.

This protocol makes it 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.

Note that whilst EURcoins is a natural idea, there are other ways to implement peer-to-peer currency exchange (Bitcoin to fiat and vice versa), see the [[Ripple currency exchange]] article for more information.

==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-spending|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]]

Contract

2013-03-01T20:24:32Z

Amiller:

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.

By building low trust protocols that interact with Bitcoin, entirely new products can be created:

* [[Smart Property|Smart property]] is property that can be atomically traded and loaned via the block chain.
* [[Transferable virtual property]] are digital items that can be traded but not duplicated.
* [[Agents]] are autonomous programs that maintain their own wallet, which they use to buy server time. Money is obtained by the agent selling services. If demand exceeds supply the agents can spawn children that either survive or die depending on whether they can get enough business.
* [[Distributed markets]] are a way to implement peer to peer bond and stock trading, allowing Bitcoin to be evolve into a full competitor to the international financial system.
* The [[Ripple currency exchange]] is a way to implement a distributed currency exchange based on social networks.

This page also lists some smaller examples.

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]. These pages were written by [mailto:mike@plan99.net Mike Hearn]. Contact him if you have an idea for a new type of contract. You can watch '''[https://www.youtube.com/watch?feature=player_embedded&v=mD4L7xDNCmA a video of a talk on contracts]''' that was presented at the Bitcoin 2012 conference in London.

==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 the hash of 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.

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.

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include applications where frequent, small pledges need to be made automatically, for instance internet radio station funding and [https://bitcointalk.org/index.php?topic=67255.msg788110#msg788110 web page translation]. 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.

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 chain|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 through the use of a trusted intermediary. However, zero-trust trades between different blockchains are not known to be possible. A protocol was proposed by luxgladius (see also: GMAX), but because the distinct chains are not temporally synchronized, trades is vulnerable to either a) funds being frozen indefinitely if one party fails to complete the protocol; or, if timeouts are used, b) a race condition allowing one party to receive all the funds. [https://bitcointalk.org/index.php?topic=91843.0 This was first pointed out] by Sergio Lerner, who also proposed a solution to this problem that involves encoding the validation rules for one chain into the validation rules for the other. This would require a significant architectural change to the validation script.

==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-spending|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]]

Hardfork Wishlist

2012-08-19T11:11:16Z

Amiller: fixed a typo I caused earlier

This page is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is *not* for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

====Changes to hard-coded limits====
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

====Major structural changes====
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

====Transaction behavior changes====
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone elses transaction, or to take fees from a transaction without outputs set aside for that putpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions

====Cryptographic changes====
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for a post-quantum signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.

====Currency changes====
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

====Navel gazing / Protocol housekeeping====
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

====Bug fixes====
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking')
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Talk:Agent

2012-08-18T06:48:02Z

Amiller:

== Impossibility of Program Obfuscation ==

As exciting as this idea is, it brushes up against a known impossibility result in theoretical cryptography. In order to pay for itself, the agent would need to be capable of producing digitally signed messages (e.g., bitcoin transactions). In order to safely spawn new instances on rental servers, it would have to function even if the the server host is untrusted. What you would want is a way of embedding the private key in the agent's code, such that the agent is able to sign messages but the host cannot extract the key and steal the agent's endowment. This idea is known as program obfuscation, and unfortunately, it is generally impossible. See [1] "On the Impossibility of Program Obfuscation" by Boaz Barak, et al., or [2] an informal description of the proof.

This is not a problem with StorJ as it was originally described. The "agent" is a program that runs on a trusted host, and it rents untrusted "storage" or "bandwidth" services (e.g., Amazon S3). That's fine. What it can't do is rent "execution" services (e.g., Amazon EC2) in order to spawn new instances of itself. The "artificial lifeform" language is misleading, and leads to confusion (e.g., [3]). This page should be removed or heavily reworded to make this distinction clear.

[1] http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf B. Barak, O. Goldreich R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, CRYPTO 2001

[2] http://www.cs.princeton.edu/~boaz/Papers/obf_informal.html

[3] http://www.reddit.com/r/Bitcoin/comments/yf0ww/

--[[User:Amiller|Amiller]] ([[User talk:Amiller|talk]]) 06:48, 18 August 2012 (GMT)

Talk:Agent

2012-08-18T06:47:19Z

Amiller: The strong version of "self replicating agents" is known to be impossible.

As exciting as this idea is, it brushes up against a known impossibility result in theoretical cryptography. In order to pay for itself, the agent would need to be capable of producing digitally signed messages (e.g., bitcoin transactions). In order to safely spawn new instances on rental servers, it would have to function even if the the server host is untrusted. What you would want is a way of embedding the private key in the agent's code, such that the agent is able to sign messages but the host cannot extract the key and steal the agent's endowment. This idea is known as program obfuscation, and unfortunately, it is generally impossible. See [1] "On the Impossibility of Program Obfuscation" by Boaz Barak, et al., or [2] an informal description of the proof.

This is not a problem with StorJ as it was originally described. The "agent" is a program that runs on a trusted host, and it rents untrusted "storage" or "bandwidth" services (e.g., Amazon S3). That's fine. What it can't do is rent "execution" services (e.g., Amazon EC2) in order to spawn new instances of itself. The "artificial lifeform" language is misleading, and leads to confusion (e.g., [3]). This page should be removed or heavily reworded to make this distinction clear.

[1] http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf B. Barak, O. Goldreich R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, CRYPTO 2001

[2] http://www.cs.princeton.edu/~boaz/Papers/obf_informal.html

[3] http://www.reddit.com/r/Bitcoin/comments/yf0ww/

Talk:Hardfork Wishlist

2012-08-09T08:46:59Z

Amiller: /* Proposals which reduce security */

==Proposals which reduce security==
"Difficulty adjustment should adapt to sudden hashrate loss"

It's really hard to construct ''general'' proofs, but I believe that _all_ such schemes substantially reduce the cost of performing forged chain attacks against isolated nodes. I gave an argument of this here, assuming a particular decrease handling improvement: [https://bitcointalk.org/index.php?topic=46498.msg556137#msg556137]

Beyond those problems schemes with asymmetric difficulty creates non-linearities which make it profitable for miners as a group to game the system: e.g. turn off until it falls fast, then turn on until it catches back up. The current mostly linear system doesn't enable this even if the miners conspire.

One of my concerns about this page is that lots of ideas sound just fantastic until you consider their costs, or sound great so long as you don't mind their particular costs. Because these changes must be adopted by consensus and because people evaluate costs differently it's hard to find things that win the cost/benefit analysis for almost everyone.

In my opinion, the drop risk is inconsequential: Having the average txn time go to 20 minutes for a month isn't really a big deal... and if there is a bigger drop then the slow txn processing time will be the least of our problems. The costs here are not speculative, altchains with "improved" difficulty adjustments have been exploited several times. The benefit is purely speculative and primarily matters only if bitcoin is already failing.

Perhaps we should change the page to tabular layout so that we can link to for and against arguments for features where ones exist? --[[User:Gmaxwell|Gmaxwell]] 19:59, 4 January 2012 (GMT)

:And yet another variant of this: * Replace the 10 minute block finding target with a dynamic target decided by the market [https://bitcointalk.org/index.php?topic=79837.0]. This one misses that the interblock time is important for convergence, also a naive implementation would change the payout schedule. --[[User:Gmaxwell|Gmaxwell]] ([[User talk:Gmaxwell|talk]]) 03:03, 28 July 2012 (GMT)

Trying to eliminate hard-coded time parameters means working in the "Partially Synchronous" communications model [http://www.podc.org/dijkstra/2007.html]. It's also equivalent to building a "partition tolerant" system in the sense of P in the CAP theorem. This is a difficult problem, and most proposed solutions to it are going to be broken. Still it's a fundamental goal, and it deserves its own section in the wishlist.
--[[User:Amiller|Amiller]] ([[User talk:Amiller|talk]]) 08:46, 9 August 2012 (GMT)

===OP_FAIL FAILS===

I've removed this suggestion:

<blockquote>
'''Futureproofing'''
* Add a few new opcodes called OP_FAIL''n'' or repurpose them from OP_NOP''n''. These would immediately fail a transaction, and like OP_NOP''n'', would be available as new opcodes for future purposes, but without the burden of old clients dangerously understanding them as "do nothing".
</blockquote>

Because it's idiotic. You could already use undefined opcodes for this— but even that is stupid, the reason the the OP_NOPs are useful for futureproofing is specifically because they pass. The fact that they pass is what enables you to run a mixed network. If you use an opcode that always fails for old nodes as an extension mechanism the instant that it gets mined the network forks. --[[User:Gmaxwell|Gmaxwell]] 17:13, 19 February 2012 (GMT)

== Removed 'Proof of Stake' ==

I've removed:
* Augment [[Proof of work]] with [[Proof of Stake]] as the mechanism for generating blocks.

As non-viable due to being economically significant. --[[User:Gmaxwell|Gmaxwell]] 14:42, 12 March 2012 (GMT)

Economic theory unambiguously indicates that the current protocol will fail eventually. It will need to be changed either before or when this happens.
A proof-of-stake system is likely the only viable long-term solution. Preparing for a forseeable problem is only prudent. --[[User:Cunicula|Cunicula]] 7 April 2012

== Merkle trees, lite clients, coinbase commitments, UTXOs ==

There have been at least four generations now of essentially the same proposal. I just added etotheipi's and DiThi's. The language for them has changed has many times. Should this be consolidated somewhere else? For what it's worth, I now prefer "hash graph" as the general term including chains, trees, and skiplists.
--[[User:Amiller|Amiller]] ([[User talk:Amiller|talk]]) 08:37, 9 August 2012 (GMT)

Talk:Hardfork Wishlist

2012-08-09T08:37:45Z

Amiller: /* Merkle trees, lite clients, coinbase commitments, UTXOs */ new section

==Proposals which reduce security==
"Difficulty adjustment should adapt to sudden hashrate loss"

It's really hard to construct ''general'' proofs, but I believe that _all_ such schemes substantially reduce the cost of performing forged chain attacks against isolated nodes. I gave an argument of this here, assuming a particular decrease handling improvement: [https://bitcointalk.org/index.php?topic=46498.msg556137#msg556137]

Beyond those problems schemes with asymmetric difficulty creates non-linearities which make it profitable for miners as a group to game the system: e.g. turn off until it falls fast, then turn on until it catches back up. The current mostly linear system doesn't enable this even if the miners conspire.

One of my concerns about this page is that lots of ideas sound just fantastic until you consider their costs, or sound great so long as you don't mind their particular costs. Because these changes must be adopted by consensus and because people evaluate costs differently it's hard to find things that win the cost/benefit analysis for almost everyone.

In my opinion, the drop risk is inconsequential: Having the average txn time go to 20 minutes for a month isn't really a big deal... and if there is a bigger drop then the slow txn processing time will be the least of our problems. The costs here are not speculative, altchains with "improved" difficulty adjustments have been exploited several times. The benefit is purely speculative and primarily matters only if bitcoin is already failing.

Perhaps we should change the page to tabular layout so that we can link to for and against arguments for features where ones exist? --[[User:Gmaxwell|Gmaxwell]] 19:59, 4 January 2012 (GMT)

:And yet another variant of this: * Replace the 10 minute block finding target with a dynamic target decided by the market [https://bitcointalk.org/index.php?topic=79837.0]. This one misses that the interblock time is important for convergence, also a naive implementation would change the payout schedule. --[[User:Gmaxwell|Gmaxwell]] ([[User talk:Gmaxwell|talk]]) 03:03, 28 July 2012 (GMT)

===OP_FAIL FAILS===

I've removed this suggestion:

<blockquote>
'''Futureproofing'''
* Add a few new opcodes called OP_FAIL''n'' or repurpose them from OP_NOP''n''. These would immediately fail a transaction, and like OP_NOP''n'', would be available as new opcodes for future purposes, but without the burden of old clients dangerously understanding them as "do nothing".
</blockquote>

Because it's idiotic. You could already use undefined opcodes for this— but even that is stupid, the reason the the OP_NOPs are useful for futureproofing is specifically because they pass. The fact that they pass is what enables you to run a mixed network. If you use an opcode that always fails for old nodes as an extension mechanism the instant that it gets mined the network forks. --[[User:Gmaxwell|Gmaxwell]] 17:13, 19 February 2012 (GMT)

== Removed 'Proof of Stake' ==

I've removed:
* Augment [[Proof of work]] with [[Proof of Stake]] as the mechanism for generating blocks.

As non-viable due to being economically significant. --[[User:Gmaxwell|Gmaxwell]] 14:42, 12 March 2012 (GMT)

Economic theory unambiguously indicates that the current protocol will fail eventually. It will need to be changed either before or when this happens.
A proof-of-stake system is likely the only viable long-term solution. Preparing for a forseeable problem is only prudent. --[[User:Cunicula|Cunicula]] 7 April 2012

== Merkle trees, lite clients, coinbase commitments, UTXOs ==

There have been at least four generations now of essentially the same proposal. I just added etotheipi's and DiThi's. The language for them has changed has many times. Should this be consolidated somewhere else? For what it's worth, I now prefer "hash graph" as the general term including chains, trees, and skiplists.
--[[User:Amiller|Amiller]] ([[User talk:Amiller|talk]]) 08:37, 9 August 2012 (GMT)

Hardfork Wishlist

2012-08-09T08:34:29Z

Amiller:

This page is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is *not* for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

====Changes to hard-coded limits====
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

====Major structural changes====
* , instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

====Transaction behavior changes====
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone elses transaction, or to take fees from a transaction without outputs set aside for that putpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions

====Cryptographic changes====
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for a post-quantum signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.

====Currency changes====
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

====Navel gazing / Protocol housekeeping====
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

====Bug fixes====
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking')
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2012-08-09T08:26:39Z

Amiller:

This page is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is *not* for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

====Changes to hard-coded limits====
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

====Major structural changes====
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

====Transaction behavior changes====
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone elses transaction, or to take fees from a transaction without outputs set aside for that putpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions

====Cryptographic changes====
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for a post-quantum signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.

====Currency changes====
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

====Navel gazing / Protocol housekeeping====
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

====Bug fixes====
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking')
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]