Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit 0536436

Browse files
committedNov 30, 2014
New post.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
1 parent 4193e6e commit 0536436

File tree

1 file changed

+117
-0
lines changed

1 file changed

+117
-0
lines changed
 
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
---
2+
layout: post
3+
commentIssueId: 39
4+
---
5+
Since blockstream released their fascinating [sidechains paper](http://www.blockstream.com/sidechains.pdf)
6+
I've been discussing related ideas with Gregory Maxwell. Sidechains
7+
are a method of automating the 1:1 bitcoin pegging (which pettycoin
8+
uses); it will require a soft-fork of the bitcoin protocol, which is
9+
why I never persued such a direction. The interest in side-chains
10+
suggests it's a medium-term possibility, however.
11+
12+
More interesting to pettycoin directly is
13+
[this writeup](https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs)
14+
on how to change bitcoin to allow partial knowledge. Much of this
15+
(particularly the idea of transmitting proofs of incorrect behavior)
16+
pettycoin already does; the proof of spending a non-existing input,
17+
however, uses a completely different approach which is worth spelling
18+
out here.
19+
20+
## The Problem ##
21+
22+
In bitcoin, every node knows everything, so it's easy to spot a
23+
transaction which says "this transfers 100 bitcoins from <made up
24+
transaction>". Without that full knowledge, however, you can't be
25+
sure the transaction is really made up, and you can't prove it
26+
compactly to someone who doesn't know every transaction: "you can't
27+
prove a negative".
28+
29+
### Pettycoin's Solution ###
30+
31+
The miner inserts an index for each input into the block alongside the
32+
transaction: this says where the input transaction is. This
33+
"input_refs" array is hashed into the merkle hash tree (it's every
34+
second leaf node).
35+
36+
You can prove a miner made up an input transaction by presenting the
37+
transaction, the input refs (both with proof that they're in the
38+
block), and the transaction where the input ref said it would be (with proof).
39+
You still need to detect double-spends in the traditional way, though.
40+
41+
### The UTXO Committment Solution ###
42+
43+
This is a bit more complicated, but it does more. The scheme has
44+
several parts, the first of which is UTXO Committments; a seemingly
45+
standard part of bitcoin-wizard lore which has several variants
46+
(Andrew Miller provided a wealth of links:
47+
[Andrew Miller's proposal and implementation](https://bitcointalk.org/index.php?topic=101734.0),
48+
[Alan Reiner's proposal](https://bitcointalk.org/index.php?topic=88208.0),
49+
[Mark Friedenbach worked on one](https://bitcointalk.org/index.php?topic=204283.0)
50+
and
51+
[Peter Todd has an implementation](https://github.com/petertodd/python-merbinnertree)).
52+
53+
#### Background: UTXO Commitments in A Nutshell ####
54+
55+
The important part of bitcoin is the Unspent Transaction Outputs
56+
(UTXO): stuff which can still be used. As you go through the blocks,
57+
you naturally have to track these, so you know whether a new
58+
transaction is spending only valid, unspent outputs.
59+
60+
The twist is that you formalize this structure into a UTXO tree; the
61+
specific species of tree doesn't really matter for the idea. This
62+
tree maps "transaction id, output number" to "version, height,
63+
coinbase flag, scriptpubkey, value" (ie. everything you need to know
64+
about a transaction output to use it).
65+
66+
This tree then gets merkled together so you can describe the state of
67+
the tree with a single hash: this hash gets published in the block (and
68+
if it's wrong, the block is invalid and rejected by the other miners).
69+
You can also compactly prove any part of the tree using a merkle proof,
70+
thus proving that a particular transaction is valid (hey, see, here
71+
are the unspent outputs in the last block, with proofs!).
72+
73+
The original motivation for this was to make light-weight clients more
74+
secure; without this, someone can prove to me that their transaction's
75+
inputs are valid, but they can't prove they're not already spent.
76+
77+
### Using UTXO Commitments for Proving Non-Existent Inputs ###
78+
79+
In this model, every transaction in the block is accompanied by a
80+
proof that the inputs are in the UTXO tree; depending on how the UTXO
81+
tree is implemented, this may be sufficient to determine the new UTXO
82+
tree hash after the input is consumed (if not, proof of extra UTXO
83+
tree nodes is required). Similarly, you can provide the proof of the
84+
locations in the UTXO tree sufficient to determine the UTXO tree hash
85+
after the outputs are inserted.
86+
87+
This way, you can verify the inputs are correct and unspent for any
88+
random transaction. You can also verify that the UTXO tree is
89+
correct: if it's not, some transaction must have updated it
90+
incorrectly and that can be proven.
91+
92+
## Partial-Knowledge Mining? ##
93+
94+
The UTXO commitment scheme opens the door to "assisted transactions"
95+
where you supply a transaction along with UTXO proofs that all its
96+
inputs are unspent as of the last block. A recipient which knows
97+
only the block headers[^utxo-not-in-hdrs] can confidently accept this as an
98+
unconfirmed transaction.
99+
100+
In fact, a miner can actually mine this without any extra checks:
101+
opening the door to partial-knowledge mining, which is a bar I decided
102+
was too high for pettycoin.
103+
104+
## Summary ##
105+
106+
The UTXO solution is more complete: it provides both proof that the
107+
inputs exist, *and* that they're unspent. This definitely wins.
108+
109+
Corollaries of this include (1) Gregory Maxwell is smarter than I am,
110+
and (2) if you can get the attention of the right bitcoin wizards,
111+
your own sidechain project will be greatly improved :)
112+
113+
[^utxo-not-in-hdrs] Bitcoin is unlikely to add the UTXO hash to the
114+
80-byte header. Instead, it would become a compulsory part of the
115+
coinbase, is the order of 100 bytes long, and you need
116+
log2(num-transactions) 32 byte hashes to attach it to the header. But
117+
that's still well under 1k per 10 minutes for a light-weight node.

0 commit comments

Comments
 (0)
Please sign in to comment.