Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1X5FLf-000250-Gm for bitcoin-development@lists.sourceforge.net; Thu, 10 Jul 2014 14:29:23 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.214.181 as permitted sender) client-ip=209.85.214.181; envelope-from=mh.in.england@gmail.com; helo=mail-ob0-f181.google.com; Received: from mail-ob0-f181.google.com ([209.85.214.181]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1X5FLa-0004jT-4V for bitcoin-development@lists.sourceforge.net; Thu, 10 Jul 2014 14:29:23 +0000 Received: by mail-ob0-f181.google.com with SMTP id wp4so9595048obc.26 for ; Thu, 10 Jul 2014 07:29:12 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.63.3 with SMTP id c3mr54592112oes.16.1405002552619; Thu, 10 Jul 2014 07:29:12 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.35.234 with HTTP; Thu, 10 Jul 2014 07:29:12 -0700 (PDT) Date: Thu, 10 Jul 2014 16:29:12 +0200 X-Google-Sender-Auth: QrFjhJl1sOsIHQnHQHZSK5w5eCs Message-ID: From: Mike Hearn To: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a11c1d2420eb93004fdd7a60a X-Spam-Score: -0.5 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (mh.in.england[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1X5FLa-0004jT-4V Subject: [Bitcoin-development] Draft BIP for geutxos message X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Jul 2014 14:29:23 -0000 --001a11c1d2420eb93004fdd7a60a Content-Type: text/plain; charset=UTF-8 I opened up a pull req for a draft BIP for getutxo. https://github.com/bitcoin/bips/pull/88 I include a rendering below for your reading convenience. If you'd like to comment on design/security/etc then please first familiarise yourself with the long discussions that were already had here: https://github.com/bitcoin/bitcoin/pull/4351 BIP: 45 Title: getutxo message Author: Mike Hearn Status: Draft Type: Standards Track Created: 2014-06-10 Table of Contents - Abstract - Motivation - Specification - Backward compatibility - Authentication - Implementation Abstract This document describes a small P2P protocol extension that performs UTXO lookups given a set of outpoints. Motivation All full Bitcoin nodes maintain a database called the unspent transaction output set. This set is how double spending is checked for: to be valid a transaction must identify unspent outputs in this set using an identifier called an "outpoint", which is merely the hash of the output's containing transaction plus an index. The ability to query this can sometimes be useful for a lightweight/SPV client which does not have the full UTXO set at hand. For example, it can be useful in applications implementing assurance contracts to do a quick check when a new pledge becomes visible to test whether that pledge was already revoked via a double spend. Although this message is not strictly necessary because e.g. such an app could be implemented by fully downloading and storing the block chain, it is useful for obtaining acceptable performance and resolving various UI cases. Another example of when this data can be useful is for performing floating fee calculations in an SPV wallet. This use case requires some other changes to the Bitcoin protocol however, so we will not dwell on it here. Specification Two new messages are defined. The "getutxos" message has the following structure: Field SizeDescriptionData typeComments1check mempoolboolWhether to apply mempool transactions during the calculation, thus exposing their UTXOs and removing outputs that they spend.?outpointsvectorThe list of outpoints to be queried. Each outpoint is serialized in the same way it is in a tx message. The response message "utxos" has the following structure: Field SizeDescriptionData typeComments4chain heightuint32The height of the chain at the moment the result was calculated.32chain tip hashuint256Block hash of the top of the chain at the moment the result was calculated.?hit bitmapbyte[]An array of bytes encoding one bit for each outpoint queried. Each bit indicates whether the queried outpoint was found in the UTXO set or not.?result utxosresult[]A list of result objects (defined below), one for each outpoint that is unspent (i.e. has a bit set in the bitmap). The result object is defined as: Field SizeDescriptionData typeComments4tx versionuint32The version number of the transaction the UTXO was found in.4heightuint256The height of the block containing the defining transaction, or 0x7FFFFFFF if the tx is in the mempool.?outputCTxOutThe output itself, serialized in the same way as in a tx message. Backward compatibility Nodes indicate support by advertising a protocol version above 70003 and by setting a new NODE_GETUTXO flag in their nServices field, which has a value of 2 (1 Authentication The UTXO set is not currently authenticated by anything. There are proposals to resolve this by introducing a new consensus rule that commits to a root hash of the UTXO set in blocks, however this feature is not presently available in the Bitcoin protocol. Once it is, the utxos message could be upgraded to include Merkle branches showing inclusion of the UTXOs in the committed sets. If the requesting client is looking up outputs for a signed transaction that they have locally, the client can partly verify the returned output by running the input scripts with it. Currently this verifies only that the script is correct. A future version of the Bitcoin protocol is likely to also allow the value to be checked in this way. It does not show that the output is really unspent or was ever actually created in the block chain however. If the requesting client has a mapping of chain heights to block hashes in the best chain e.g. obtained via getheaders, then they can obtain a proof that the output did at one point exist by requesting the block and searching for the output within it. When combined with Bloom filtering this can be reasonably efficient. Note that even when the outputs are being checked against something this protocol has the same security model as Bloom filtering: a remote node can lie through omission by claiming the requested UTXO does not exist / was already spent (they are the same, from the perspective of a full node). Querying multiple nodes and combining their answers can be a partial solution to this, although as nothing authenticates the Bitcoin P2P network a man in the middle could still yield incorrect results. Implementation https://github.com/bitcoin/bitcoin/pull/4351/files --001a11c1d2420eb93004fdd7a60a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I opened up a pull req for a draft BIP for getutxo.

=C2=A0 =C2=A0https://github.com/bitcoin/bips/pull/88

I include a rendering below for your reading convenience. If you'd lik= e to comment on design/security/etc then please first familiarise yourself = with the long discussions that were already had here:



  BIP: 45
  Title: getutxo message
  Author: Mike Hearn <hearn@vinum=
eris.com>
  Status: Draft
  Type: Standards Track
  Created: 2014-06-10

Table of Contents

Abstract

This d= ocument describes a small P2P protocol extension that performs UTXO lookups= given a set of outpoints.

= Motivation

All fu= ll Bitcoin nodes maintain a database called the unspent transaction output = set. This set is how double spending is checked for: to be valid a transact= ion must identify unspent outputs in this set using an identifier called an= "outpoint", which is merely the hash of the output's contain= ing transaction plus an index.

The ab= ility to query this can sometimes be useful for a lightweight/SPV client wh= ich does not have the full UTXO set at hand. For example, it can be useful = in applications implementing assurance contracts to do a quick check when a= new pledge becomes visible to test whether that pledge was already revoked= via a double spend. Although this message is not strictly necessary becaus= e e.g. such an app could be implemented by fully downloading and storing th= e block chain, it is useful for obtaining acceptable performance and resolv= ing various UI cases.

Anothe= r example of when this data can be useful is for performing floating fee ca= lculations in an SPV wallet. This use case requires some other changes to t= he Bitcoin protocol however, so we will not dwell on it here.

Specification

Two ne= w messages are defined. The "getutxos" message has the following = structure:

=
Field Size DescriptionData typeComments
1check mempool<= /td>bool Whether to= apply mempool transactions during the calculation, thus exposing their UTX= Os and removing outputs that they spend.
?outpointsvector The list of outpoints to be queried. Each outpoint is serialized in the sam= e way it is in a tx message.

The response message "utxos" has the following structure:

chain tip has= h=
Field Size DescriptionData typeComments
4chain heightuint32<= /td> The height= of the chain at the moment the result was calculated.
32uint= 256 Block hash= of the top of the chain at the moment the result was calculated.
?hit bitmapbyte[] An array o= f bytes encoding one bit for each outpoint queried. Each bit indicates whet= her the queried outpoint was found in the UTXO set or not.
?result utxosresult[= ] A list of = result objects (defined below), one for each outpoint that is unspent (i.e.= has a bit set in the bitmap).

The result object is defined as:

4uint256<= td style=3D"padding:6px 13px;border:1px solid rgb(221,221,221)"> The height of the block containing the defining transaction, or 0x7FFFFFFF = if the tx is in the mempool.CTxOut The output itself, serialized in the same way as in a tx message.=
Field Size DescriptionData typeComments
4tx versionuint32 The versio= n number of the transaction the UTXO was found in.
height
?output

Backward compatibility<= /a>

Nodes = indicate support by advertising a protocol version above 70003 and by setti= ng a new NODE_GETUTXO flag in their nServices field, which has a value of 2= (1

Authentication

The UT= XO set is not currently authenticated by anything. There are proposals to r= esolve this by introducing a new consensus rule that commits to a root hash= of the UTXO set in blocks, however this feature is not presently available= in the Bitcoin protocol. Once it is, the utxos message could be upgraded t= o include Merkle branches showing inclusion of the UTXOs in the committed s= ets.

If the= requesting client is looking up outputs for a signed transaction that they= have locally, the client can partly verify the returned output by running = the input scripts with it. Currently this verifies only that the script is = correct. A future version of the Bitcoin protocol is likely to also allow t= he value to be checked in this way. It does not show that the output is rea= lly unspent or was ever actually created in the block chain however.

If the= requesting client has a mapping of chain heights to block hashes in the be= st chain e.g. obtained via getheaders, then they can obtain a proof that th= e output did at one point exist by requesting the block and searching for t= he output within it. When combined with Bloom filtering this can be reasona= bly efficient.

Note t= hat even when the outputs are being checked against something this protocol= has the same security model as Bloom filtering: a remote node can lie thro= ugh omission by claiming the requested UTXO does not exist / was already sp= ent (they are the same, from the perspective of a full node). Querying mult= iple nodes and combining their answers can be a partial solution to this, a= lthough as nothing authenticates the Bitcoin P2P network a man in the middl= e could still yield incorrect results.

Implementation

https://github.co= m/bitcoin/bitcoin/pull/4351/files

--001a11c1d2420eb93004fdd7a60a--