bitcoin/bitcoin — pull request #4351 by mikehearn (2014-06-16 16:40:35+00:00)
Title: Add a getutxos command to the p2p protocol

# Introduction

The getutxo command allows querying of the UTXO set given a set of of outpoints. It has a simple implementation and the results are not authenticated in any way. Despite this, there are times when it is a useful capability to have. I believe @jgarzik also has a use case for this, though I don't know what it is.

As a motivating example I present Lighthouse, an app I'm writing that implements assurance contracts:

http://blog.vinumeris.com/2014/05/17/lighthouse/

Lighthouse works by collecting _pledges_, which contain an invalid transaction signed with SIGHASH_ANYONECANPAY. Once sufficient pledges are collected to make the combination valid, we say the contract is complete and it can be broadcast onto the network, spending the pledged outputs. Before that occurs however, a pledge can be _revoked_ and the pledged money redeemed by double spending the pledged output. For instance you might want to do this if it becomes clear not enough people care about the assurance contract for it to reach its goal in a timely manner, or if you simply need the money back due to some kind of cashflow crunch.

It is convenient to be able to see when a pledge has been revoked, so the user interface can be updated, and so when the final contract is created revoked pledges can be left out. For this purpose "getutxos" is used.

# Protocol

The getutxos message takes a boolean which controls whether outputs in the memory pool are considered, and a vector of COutPoint structures. It returns a bitmap with the same number of bits as outputs specified rounded up to the nearest 8 bits, and then a list of CTxOut structures, one for each set bit in the bitmap. The bitmap encodes whether the UTXO was found (i.e. is indeed unspent).

# Authentication

The results of getutxos is not authenticated. This is because the obvious way to do this requires the work maaku has been doing on UTXO commitments to be merged, activated by default, miners to upgrade and a forking change made to enforce their accuracy. All this is a big project that may or may not ever come to fruition.

For the Lighthouse security model however, this doesn't matter much. The reason is that the pledge transactions you're getting (which may be malicious) don't come from the P2P network. They come in the form of files either from a simple rendezvous server, or e.g. a shared folder or email attachments. The people sending these files have no way to influence the choice of peers made by the app. Once the outputs are returned, they are used to check the signatures on the pledge, thus verifying that the pledge spends the UTXO returned by the P2P network.

So we can be attacked in the following ways:

* The pledge may be attempting to pledge non-existent outputs, but this will be detected if the majority of peers are honest.
* The peers may be malicious and return a wrong or bogus output, but this will be detected when the signature is checked, except for the value (!) but we want to fix this by including the value into the sighash at some point anyway because we need it to make the TREZOR efficient/faster.
* The peers may bogusly claim no such UTXO exists when it does, but this would result in the pledge being seen as invalid. When the project creator asks the pledgor why they revoked their money, and learns that in fact they never did, the bogus peers will be detected. No money is at risk as the pledges cannot be spent.
* If the pledgor AND all the peers collaborate (i.e. the pledgor controls your internet connection) then they can make you believe you have a valid pledge when you don't. This would result in the app getting "jammed" and attempting to close an uncloseable contract. No money is at risk and the user will eventually wonder why their contract is not confirming. Once they get to a working internet connection the subterfuge will be discovered.

There is a final issue: the answer to getutxos can of course change the instant the result is generated, thus leading you to construct an uncloseable transaction if the process of revocation races with the construction. The app can detect this by watching for either a reject message, or an inv requesting one of the inputs that is supposed to be in the UTXO set (i.e. the remote peer thinks it's an orphan). This can then cause the app to re-request the UTXO set and drop the raced pledge.

In practice I do not anticipate such attacks are likely to occur, as they're complicated to pull off and it's not obvious what the gain is.

There may be other apps that wish to use getutxos, with different security models. They may find this useful despite the lack of UTXO commitments, and the fact that the answer can change a moment later, if:

* They are connecting to a trusted peer, i.e. localhost.
* They trust their internet connection and peer selection, i.e. because they don't believe their datacenter or ISP will commit financial fraud against them, or they are tunnelling via endpoints they trust like a randomly chosen Tor exit.
* They are not using the response for anything important or worth attacking, like some kind of visualisation.

# Upgrade

If enforced UTXO commitments are added to the block chain in future, it would make sense to rev the P2P protocol to add the proofs (merkle branches) to the response.

# Testing

I attempted to write unit tests for this, but Core has no infrastructure for building test chains .... the miner_tests.cpp code does it but at the cost of not allowing any other unit test to do so, as it doesn't reset or clean up the global state afterwards! I tried to fix this and ended up down a giant rabbit hole.

So instead I've tested it with a local test app I wrote, which also exercises the client side part in bitcoinj.

# BIP

If the code is ACKd then I will write a short BIP explaining the new message.

# Philosophy

On IRC I have discussed this patch a little bit before. One objection that was raised is that we shouldn't add anything to the P2P protocol unless it's unattackable, because otherwise it's a sharp knife that people might use to cut themselves.

I personally disagree with this notion for the following reasons.

Firstly, many parts of the P2P protocol are not completely unattackable: malicious remote nodes can withhold broadcast transactions, invent fictional ones (you'd think they're orphans), miss out Bloom filter responses, send addr messages for IP's that were never announced, etc. We shouldn't hold new messages to a standard existing messages don't meet.

Secondly, even with UTXO commitments in the block chain, given the sick state of mining this only requires a collaboration of two people to undo, although that failure would be publicly detectable which is at least something. But anyway, there's a clean upgrade path if/when UTXO authentication becomes available.

Thirdly, we have a valid use case that's actually implemented. This isn't some academic pie in the sky project.

Finally, Bitcoin is already the sharpest knife imaginable. I don't think we should start rejecting useful features on the grounds that someone else might screw up with them.

If the above analysis ends up not holding for some reason, and people do get attacked due to the lack of authentication, then Lighthouse and other apps can always fall back to connecting to trusted nodes (perhaps over SSL). But I would like to optimistically assume success up front and see what happens, than pessimistically assume the worst and centralise things up front.