Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1X5Fa7-0005MT-GG for bitcoin-development@lists.sourceforge.net; Thu, 10 Jul 2014 14:44:19 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.219.52 as permitted sender) client-ip=209.85.219.52; envelope-from=mh.in.england@gmail.com; helo=mail-oa0-f52.google.com; Received: from mail-oa0-f52.google.com ([209.85.219.52]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1X5Fa5-0000Jf-Ja for bitcoin-development@lists.sourceforge.net; Thu, 10 Jul 2014 14:44:19 +0000 Received: by mail-oa0-f52.google.com with SMTP id j17so9992929oag.11 for ; Thu, 10 Jul 2014 07:44:12 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.182.133.69 with SMTP id pa5mr33074924obb.2.1405003452115; Thu, 10 Jul 2014 07:44:12 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.35.234 with HTTP; Thu, 10 Jul 2014 07:44:11 -0700 (PDT) In-Reply-To: References: Date: Thu, 10 Jul 2014 16:44:11 +0200 X-Google-Sender-Auth: MeoDwwKDuak-ELBXAKGPPwqyW7g Message-ID: From: Mike Hearn To: Bitcoin Dev Content-Type: multipart/alternative; boundary=e89a8ff1ce12abf25804fdd7db7b 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: 1X5Fa5-0000Jf-Ja Subject: Re: [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:44:19 -0000 --e89a8ff1ce12abf25804fdd7db7b Content-Type: text/plain; charset=UTF-8 I took the number out, it is now just "the getutxo bip" until a number is assigned. On Thu, Jul 10, 2014 at 4:29 PM, Mike Hearn wrote: > 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 Size DescriptionData typeComments 1check mempoolbool Whether to > apply mempool transactions during the calculation, thus exposing their > UTXOs and removing outputs that they spend. ?outpointsvector The 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 Size DescriptionData typeComments 4chain heightuint32 The height > of the chain at the moment the result was calculated. 32chain tip hash > uint256 Block 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 Size DescriptionData typeComments 4tx versionuint32 The version > number of the transaction the UTXO was found in. 4heightuint256 The > height of the block containing the defining transaction, or 0x7FFFFFFF if > the tx is in the mempool. ?outputCTxOut The 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 > --e89a8ff1ce12abf25804fdd7db7b Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I took the number out, it is now just "the getutxo bi= p" until a number is assigned.

On Thu, Jul 10, 2014 at 4:29 PM, Mike Hearn <mik= e@plan99.net> wrote:
I opened up a pull req= for a draft BIP for getutxo.

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

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



  BIP: 45
  Title: getutxo message
  Author: Mike Hearn <hearn@vinumeris.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.

Specifica= tion

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

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

Authen= tication

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.

Implem= entation

https://github.com/bitcoin/bitcoin/pull/4351/files


--e89a8ff1ce12abf25804fdd7db7b--