|
| 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