path: root/6b/23d2dbc9bcd7d9b4b4e21ba30d2a0b2b03c5d2

Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <mh.in.england@gmail.com>) id 1UzQrN-0005v9-Gk
	for bitcoin-development@lists.sourceforge.net;
	Wed, 17 Jul 2013 12:29:33 +0000
Received-SPF: pass (sog-mx-2.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-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1UzQrL-0006d8-Lv
	for bitcoin-development@lists.sourceforge.net;
	Wed, 17 Jul 2013 12:29:33 +0000
Received: by mail-ob0-f181.google.com with SMTP id 16so2160753obc.26
	for <bitcoin-development@lists.sourceforge.net>;
	Wed, 17 Jul 2013 05:29:26 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.60.79.131 with SMTP id j3mr7820358oex.96.1374064166216; Wed,
	17 Jul 2013 05:29:26 -0700 (PDT)
Sender: mh.in.england@gmail.com
Received: by 10.76.23.36 with HTTP; Wed, 17 Jul 2013 05:29:26 -0700 (PDT)
In-Reply-To: <20130717105853.GA10083@savin>
References: <CANEZrP0_H9+prDSF92q8a4QzP=fzDM6cTDv0+KcfV9NF9thkmw@mail.gmail.com>
	<3E7894A0-06F3-453D-87F8-975A244EBACF@include7.ch>
	<CANEZrP2jmWkDbpJEm0vd2CKF-prFNbz_ZeNJfDWtSCKb8k5ZXA@mail.gmail.com>
	<2BDA0943-22BB-4405-9AF0-86FB41FD04A6@include7.ch>
	<CANEZrP0McSrVzwv=-qimPyX41EEDmyQdYW5QjPr_i+KWyJZSZw@mail.gmail.com>
	<2F20A509-13A9-4C84-86D7-A15C21BACD53@include7.ch>
	<CANEZrP2yQvmvwP_ZULdS2i+X6L9MeZ+DfidiuZPD2EHwLsN2MA@mail.gmail.com>
	<2A1C412D-414E-4C41-8E20-F0D21F801328@grabhive.com>
	<CANEZrP12V_5Ak0f91RsMziuqXysde102rGeSko=qPBjefy3AeA@mail.gmail.com>
	<8EE501AA-1601-4C28-A32E-80F17D219D3A@grabhive.com>
	<20130717105853.GA10083@savin>
Date: Wed, 17 Jul 2013 14:29:26 +0200
X-Google-Sender-Auth: DpRhbLbYeJyKFmw_gnQoFqEPXPI
Message-ID: <CANEZrP02oQ7GqJfLbEeD+khSGCyFz3eiynPkhARniEWr1ikmPQ@mail.gmail.com>
From: Mike Hearn <mike@plan99.net>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=047d7b67812686ae5304e1b43e88
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: 1UzQrL-0006d8-Lv
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] SPV bitcoind? (was: Introducing
	BitcoinKit.framework)
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 17 Jul 2013 12:29:33 -0000

--047d7b67812686ae5304e1b43e88
Content-Type: text/plain; charset=UTF-8

Partial UTXO sets is a neat idea. Unfortunately my intuition is that many
SPV wallets only remain open for <1 minute at a time because the user wants
to see they received money, or to send it. It'd be neat to get some
telemetry from the Android wallet for this - I will ask Andreas to let
users opt in to usage statistics.

So for anti-DoS I think smart prioritisation heuristics are the way to go
again. Perhaps by letting clients have an "identity" that they provide to a
node when it's load shedding. Clients that have been seen before, have a
track record of not being abusive etc get priority and new clients that
were never seen before get dropped. Coming up with a way to do that whilst
preserving privacy sounds like an interesting cryptographic challenge.


On Wed, Jul 17, 2013 at 12:58 PM, Peter Todd <pete@petertodd.org> wrote:

> On Tue, Jul 16, 2013 at 04:16:23PM +0200, Wendell wrote:
> > Hello everyone,
> >
> > In the previous thread, I expressed interest in seeing an SPV bitcoind,
> further stating that I would fund such work. Mike Hearn followed up with
> some of Satoshi's old code for this, which is now quite broken. The offer
> and interest on my side still stand, as more diversity in SPV options seems
> like the right way to go.
> >
> > Time-permitting, I would really appreciate feedback from knowledgable
> parties about the possible approaches to an SPV bitcoind. We at Hive
> ideally want to see something that could one be merge into master, rather
> than a fork.
>
> Keep in mind that SPV mode is newer than many realize: bloom filters are
> a 0.8 feature, itself released only last Febuary. As John Dillon posted
> earlier this week in "Protecting Bitcoin against network-wide DoS
> attack" the Bitcoin codebase will have to implement much better anti-DoS
> attack defences soon, and in a decentralized system there aren't any
> options other than requiring peers to either do work (useful or not) or
> sacrifice something of value. SPV peers can't do useful work, leaving
> only sacrifice - to what extent and how much is unknown. In addition SPV
> nodes have serious privacy issues because their peers know that any
> transaction sent to them by the SPV node is guaranteed to be from the
> node rather than relayed; bloom filters are only really helpful with
> payment protocols that don't exist yet and don't apply to merchants.
> Then you have MITM problems, vulnerability to fake blocks etc.
>
> It'll be awhile before we know how serious these issues are in practice,
> and we're likely to find new issues we didn't think of too. In any case
> Bitcoin is far better off if we make it easy to run a full node,
> donating whatever resources you can. Fortunately there's a whole
> continuum between SPV and full nodes.
>
> The way you do this is by maintaining partial UTXO sets. The trick is
> that if you have verified every block in some range i to j, every time
> you see a txout created by a transaction, and not subsequently spent,
> you can be sure that at height j the txout existed. If height j is the
> current block, you can be sure the txout exists provided that the chain
> itself is valid. Any transaction that only spends txouts in this partial
> set is a transaction you can fully verify and safely relay; for other
> transactions you just don't know and have to wait until you see them in
> a block.
>
> So what's useful about that? Basically it means your node starts with
> the same security level, and usefulness to the network, as a SPV node.
> But over time you keep downloading blocks as they are created, and with
> whatever bandwidth you have left (out of some user-configurable
> allocation) you download additional blocks going further and further
> back in time. Gradually your UTXO set becomes more complete, and over
> time you can verify a higher and higher % of all valid transactions.
> Eventually your node becomes a full node, but in the meantime it was
> still useful for the user, and still contributed to the network by
> relaying blocks and an increasingly large subset of all transactions.
> (optionally you can store a subset of the chain history too for other
> nodes to bootstrap from) You've also got better security because you
> *are* validating blocks, starting off incompletely, and increasingly
> completely until your finally validating fully. Privacy is improved, for
> both you and others, by mixing your transactions with others and adding
> to the overall anonymity set.
>
> In the future we'll have miners commit a hash of the UTXO set, and that
> gives us even more options to, for instance, have relayed transactions
> include proof that their inputs were valid, allowing all nodes to relay
> them safely.
>
>
> As for specifics, you need to maintain a UTXO set, and in addition a set
> of spent txouts (the STXO set) for which you haven't seen the
> transaction that created the txout. As download newer blocks you update
> the UTXO set; as you download older blocks you update the UTXO set and
> STXO set.
>
> Nodes now advertise this new variable to their peers:
>
> nOldestBlock - The oldest block that we've validated. (and all
> subsequent blocks)
>
> We'll also want the ability to advertise what sub-ranges of the
> blockchain data we have on hand:
>
> listArchivedBlockRanges - lists of (begin, end pairs)
>
> Nodes should drop all but the largest n pairs, say 5 or something. The
> index -1 is reserved to indicate the last block to make it easy to
> advertise that you have every block starting at some height to the most
> recent. (reserving -n with n as the last block might be a better choice
> to show intent, but still allow for specific proofs when we get node
> identities)
>
> We probably want to define a NODE_PARTIAL service bit or something; I'll
> have to re-read Pieter Wuille's proposal and think about it. Nodes
> should NOT advertize NODE_NETWORK unless they have the full chain and
> have verified it.
>
> Nodes with partial peers should only relay transactions to those peers
> if the transactions spend inputs the peers know about - remember how
> even an SPV node has that information if it's not spending unconfirmed
> inputs it didn't create. Nodes will have to update their peers
> periodically as nOldestBlock changes. That said it may also be
> worthwhile to simply relay all transactions in some cases too - a
> reasonable way to approach this might be to set a bloom filter for tx's
> that you *definitely* want, and if you are interested in everything,
> just set the filter to all 1's. If someone comes up with a reasonable
> micropayment or proof-of-work system even relaying txs that you haven't
> validated is fine - the proof-of-work and prioritization will prevent
> DoS attacks just fine.
>
> Remember that if you're running a partial node, it can get new blocks
> from any partial node, and it can retrieve historic blockchain data from
> any partial node that has archived the sequence of blocks you need next.
> On a large scale this is similar to how in BitTorrent you can serve data
> to your peers the moment you get it - a significant scalability
> improvement for the network as a whole. Even if a large % of the network
> was partial nodes running for just a few hours a day the whole system
> would work fine due to how partial nodes can serve each other the data
> they need.
>
> On startup you can act as a SPV node temporarily, grabbing asking for
> filtered blocks matching your wallet, and then go back and get the full
> blocks, or just download the full blocks right away. That's a tradeoff
> on how long the node has been off.
>
> Anyway, it's a bit more code compared to pure-SPV, but it results in a
> much more scalable Bitcoin, and if you can spare the modest bandwidth
> requirements to keep up with the blockchain it'll result in much better
> robustness against DoS attacks for you and Bitcoin in general.
>
> --
> 'peter'[:-1]@petertodd.org
>
>
> ------------------------------------------------------------------------------
> See everything from the browser to the database with AppDynamics
> Get end-to-end visibility with application monitoring from AppDynamics
> Isolate bottlenecks and diagnose root cause in seconds.
> Start your free trial of AppDynamics Pro today!
> http://pubads.g.doubleclick.net/gampad/clk?id=48808831&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

--047d7b67812686ae5304e1b43e88
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Partial UTXO sets is a neat idea. Unfortunately my intuiti=
on is that many SPV wallets only remain open for &lt;1 minute at a time bec=
ause the user wants to see they received money, or to send it. It&#39;d be =
neat to get some telemetry from the Android wallet for this - I will ask An=
dreas to let users opt in to usage statistics.<div>
<br></div><div>So for anti-DoS I think smart prioritisation heuristics are =
the way to go again. Perhaps by letting clients have an &quot;identity&quot=
; that they provide to a node when it&#39;s load shedding. Clients that hav=
e been seen before, have a track record of not being abusive etc get priori=
ty and new clients that were never seen before get dropped. Coming up with =
a way to do that whilst preserving privacy sounds like an interesting crypt=
ographic challenge.</div>
</div><div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Wed,=
 Jul 17, 2013 at 12:58 PM, Peter Todd <span dir=3D"ltr">&lt;<a href=3D"mail=
to:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>&gt;</span> =
wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">On Tue, Jul 16, 2013 at 04=
:16:23PM +0200, Wendell wrote:<br>
&gt; Hello everyone,<br>
&gt;<br>
&gt; In the previous thread, I expressed interest in seeing an SPV bitcoind=
, further stating that I would fund such work. Mike Hearn followed up with =
some of Satoshi&#39;s old code for this, which is now quite broken. The off=
er and interest on my side still stand, as more diversity in SPV options se=
ems like the right way to go.<br>

&gt;<br>
&gt; Time-permitting, I would really appreciate feedback from knowledgable =
parties about the possible approaches to an SPV bitcoind. We at Hive ideall=
y want to see something that could one be merge into master, rather than a =
fork.<br>

<br>
</div>Keep in mind that SPV mode is newer than many realize: bloom filters =
are<br>
a 0.8 feature, itself released only last Febuary. As John Dillon posted<br>
earlier this week in &quot;Protecting Bitcoin against network-wide DoS<br>
attack&quot; the Bitcoin codebase will have to implement much better anti-D=
oS<br>
attack defences soon, and in a decentralized system there aren&#39;t any<br=
>
options other than requiring peers to either do work (useful or not) or<br>
sacrifice something of value. SPV peers can&#39;t do useful work, leaving<b=
r>
only sacrifice - to what extent and how much is unknown. In addition SPV<br=
>
nodes have serious privacy issues because their peers know that any<br>
transaction sent to them by the SPV node is guaranteed to be from the<br>
node rather than relayed; bloom filters are only really helpful with<br>
payment protocols that don&#39;t exist yet and don&#39;t apply to merchants=
.<br>
Then you have MITM problems, vulnerability to fake blocks etc.<br>
<br>
It&#39;ll be awhile before we know how serious these issues are in practice=
,<br>
and we&#39;re likely to find new issues we didn&#39;t think of too. In any =
case<br>
Bitcoin is far better off if we make it easy to run a full node,<br>
donating whatever resources you can. Fortunately there&#39;s a whole<br>
continuum between SPV and full nodes.<br>
<br>
The way you do this is by maintaining partial UTXO sets. The trick is<br>
that if you have verified every block in some range i to j, every time<br>
you see a txout created by a transaction, and not subsequently spent,<br>
you can be sure that at height j the txout existed. If height j is the<br>
current block, you can be sure the txout exists provided that the chain<br>
itself is valid. Any transaction that only spends txouts in this partial<br=
>
set is a transaction you can fully verify and safely relay; for other<br>
transactions you just don&#39;t know and have to wait until you see them in=
<br>
a block.<br>
<br>
So what&#39;s useful about that? Basically it means your node starts with<b=
r>
the same security level, and usefulness to the network, as a SPV node.<br>
But over time you keep downloading blocks as they are created, and with<br>
whatever bandwidth you have left (out of some user-configurable<br>
allocation) you download additional blocks going further and further<br>
back in time. Gradually your UTXO set becomes more complete, and over<br>
time you can verify a higher and higher % of all valid transactions.<br>
Eventually your node becomes a full node, but in the meantime it was<br>
still useful for the user, and still contributed to the network by<br>
relaying blocks and an increasingly large subset of all transactions.<br>
(optionally you can store a subset of the chain history too for other<br>
nodes to bootstrap from) You&#39;ve also got better security because you<br=
>
*are* validating blocks, starting off incompletely, and increasingly<br>
completely until your finally validating fully. Privacy is improved, for<br=
>
both you and others, by mixing your transactions with others and adding<br>
to the overall anonymity set.<br>
<br>
In the future we&#39;ll have miners commit a hash of the UTXO set, and that=
<br>
gives us even more options to, for instance, have relayed transactions<br>
include proof that their inputs were valid, allowing all nodes to relay<br>
them safely.<br>
<br>
<br>
As for specifics, you need to maintain a UTXO set, and in addition a set<br=
>
of spent txouts (the STXO set) for which you haven&#39;t seen the<br>
transaction that created the txout. As download newer blocks you update<br>
the UTXO set; as you download older blocks you update the UTXO set and<br>
STXO set.<br>
<br>
Nodes now advertise this new variable to their peers:<br>
<br>
nOldestBlock - The oldest block that we&#39;ve validated. (and all<br>
subsequent blocks)<br>
<br>
We&#39;ll also want the ability to advertise what sub-ranges of the<br>
blockchain data we have on hand:<br>
<br>
listArchivedBlockRanges - lists of (begin, end pairs)<br>
<br>
Nodes should drop all but the largest n pairs, say 5 or something. The<br>
index -1 is reserved to indicate the last block to make it easy to<br>
advertise that you have every block starting at some height to the most<br>
recent. (reserving -n with n as the last block might be a better choice<br>
to show intent, but still allow for specific proofs when we get node<br>
identities)<br>
<br>
We probably want to define a NODE_PARTIAL service bit or something; I&#39;l=
l<br>
have to re-read Pieter Wuille&#39;s proposal and think about it. Nodes<br>
should NOT advertize NODE_NETWORK unless they have the full chain and<br>
have verified it.<br>
<br>
Nodes with partial peers should only relay transactions to those peers<br>
if the transactions spend inputs the peers know about - remember how<br>
even an SPV node has that information if it&#39;s not spending unconfirmed<=
br>
inputs it didn&#39;t create. Nodes will have to update their peers<br>
periodically as nOldestBlock changes. That said it may also be<br>
worthwhile to simply relay all transactions in some cases too - a<br>
reasonable way to approach this might be to set a bloom filter for tx&#39;s=
<br>
that you *definitely* want, and if you are interested in everything,<br>
just set the filter to all 1&#39;s. If someone comes up with a reasonable<b=
r>
micropayment or proof-of-work system even relaying txs that you haven&#39;t=
<br>
validated is fine - the proof-of-work and prioritization will prevent<br>
DoS attacks just fine.<br>
<br>
Remember that if you&#39;re running a partial node, it can get new blocks<b=
r>
from any partial node, and it can retrieve historic blockchain data from<br=
>
any partial node that has archived the sequence of blocks you need next.<br=
>
On a large scale this is similar to how in BitTorrent you can serve data<br=
>
to your peers the moment you get it - a significant scalability<br>
improvement for the network as a whole. Even if a large % of the network<br=
>
was partial nodes running for just a few hours a day the whole system<br>
would work fine due to how partial nodes can serve each other the data<br>
they need.<br>
<br>
On startup you can act as a SPV node temporarily, grabbing asking for<br>
filtered blocks matching your wallet, and then go back and get the full<br>
blocks, or just download the full blocks right away. That&#39;s a tradeoff<=
br>
on how long the node has been off.<br>
<br>
Anyway, it&#39;s a bit more code compared to pure-SPV, but it results in a<=
br>
much more scalable Bitcoin, and if you can spare the modest bandwidth<br>
requirements to keep up with the blockchain it&#39;ll result in much better=
<br>
robustness against DoS attacks for you and Bitcoin in general.<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
--<br>
&#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org" target=3D"_blank">pet=
ertodd.org</a><br>
</font></span><br>---------------------------------------------------------=
---------------------<br>
See everything from the browser to the database with AppDynamics<br>
Get end-to-end visibility with application monitoring from AppDynamics<br>
Isolate bottlenecks and diagnose root cause in seconds.<br>
Start your free trial of AppDynamics Pro today!<br>
<a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D48808831&amp;iu=
=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D48808831&amp;iu=3D/4140/ostg.clktrk</a><br>___________________=
____________________________<br>

Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
<br></blockquote></div><br></div>

--047d7b67812686ae5304e1b43e88--