Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Tamas Blummer]

[-- Attachment #1: Type: text/plain, Size: 292 bytes --]

Would not an SPV bitcoind transfer all control on validation rules to miner?

A majority coalition of miner (pool operator) might even decide to change block reward
rules if the rest of the network only verifies POW.

Regards,

Tamás Blummer
Founder, CEO

http://bitsofproof.com


[-- Attachment #2.1: Type: text/html, Size: 4392 bytes --]

[-- Attachment #2.2: email.png --]
[-- Type: image/png, Size: 7120 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 585 bytes --]

On Wed, Jul 17, 2013 at 02:37:11PM +0200, Tamas Blummer wrote:
> Would not an SPV bitcoind transfer all control on validation rules to miner?

Yes

> A majority coalition of miner (pool operator) might even decide to change block reward
> rules if the rest of the network only verifies POW.

Widespread dependence on SPV mode is very dangerous for Bitcoin in
general due to that reason. Fraud proofs may help, but they're also
another layer of never-before-tested crypto on top of an already poorly
understood technology, bitcoin itself.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 946 bytes --]

On Wed, Jul 17, 2013 at 2:37 PM, Tamas Blummer <tamas@bitsofproof.com>wrote:

> A majority coalition of miner (pool operator) might even decide to change
> block reward
> rules if the rest of the network only verifies POW.
>

Which is why it's still vital that any "important" node in the economy uses
full validation.

A majority miner coalition could change the block reward and award
themselves money which SPV clients would accept, however, the moment
somebody tried to cash that money out via an exchange, or use it to
purchase something from an online shop, or just see if it propagated across
the P2P network effectively, they'd notice something had gone wrong. Of
course it'd be in the news long before this happened ....

SPV is really meant for nodes that go away and come back a lot, i.e. end
user wallets. If you're a merchant it'd be dumb to run one unless you're on
such a tight budget that your server resembles a powerful tablet.

[-- Attachment #2: Type: text/html, Size: 1409 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1558 bytes --]

On Thu, Jul 18, 2013 at 06:46:16PM +0200, Wendell wrote:
> Heh, will do. If you have less confidence in your programming skills perhaps its best if you write documentation and we bring in someone else to do the heavy lifting? Maybe Eric Lombrozo would be interested in this, for example...

I have plenty of confidence in my programming skills, I just don't have
very much evidence in the Bitcoin git history to convince you my
confidence is well placed. :)

I do have a day job I love, so it will certainly get done faster if you
can get someone else to do the actual coding; I'd be willing to write
the specifications and supervise/audit/advise for a few hours a week.

> -wendell
> 
> grabhive.com | twitter.com/grabhive
> 
> On Jul 18, 2013, at 6:22 PM, Peter Todd wrote:
> 
> > I've got one or two orders of magnitude more good ideas than I have time
> > to implement, but I will say this one would have a pretty big impact -
> > I'm considering it.
> > 
> > Of course, I would accept bribes. :) But in all seriousness I also
> > accepted funds from John Dillon to implement replace-by-fee, although
> > he's been good in understanding that the scope of the project was quite
> > a bit bigger than originally thought. (it turned out replace-by-fee can
> > enable very safe zero-conf transactions, but only with mempool and
> > relaying changes) I'd suggest looking at my git commit track record
> > before you offer anything FWIW; I've been much more of an academic than
> > a programmer.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Wendell]

[-- Attachment #1: Type: text/plain, Size: 1040 bytes --]

Heh, will do. If you have less confidence in your programming skills perhaps its best if you write documentation and we bring in someone else to do the heavy lifting? Maybe Eric Lombrozo would be interested in this, for example...

-wendell

grabhive.com | twitter.com/grabhive

On Jul 18, 2013, at 6:22 PM, Peter Todd wrote:

> I've got one or two orders of magnitude more good ideas than I have time
> to implement, but I will say this one would have a pretty big impact -
> I'm considering it.
> 
> Of course, I would accept bribes. :) But in all seriousness I also
> accepted funds from John Dillon to implement replace-by-fee, although
> he's been good in understanding that the scope of the project was quite
> a bit bigger than originally thought. (it turned out replace-by-fee can
> enable very safe zero-conf transactions, but only with mempool and
> relaying changes) I'd suggest looking at my git commit track record
> before you offer anything FWIW; I've been much more of an academic than
> a programmer.


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 841 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1076 bytes --]

On Wed, Jul 17, 2013 at 03:37:41PM +0200, Wendell wrote:
> Peter,
> 
> This sounds like a _very_ good idea for a desktop client, and probably acceptable to users so long as we take available disk space into consideration, and only ever use a fraction of it.
> 
> Will you implement this?

I've got one or two orders of magnitude more good ideas than I have time
to implement, but I will say this one would have a pretty big impact -
I'm considering it.

Of course, I would accept bribes. :) But in all seriousness I also
accepted funds from John Dillon to implement replace-by-fee, although
he's been good in understanding that the scope of the project was quite
a bit bigger than originally thought. (it turned out replace-by-fee can
enable very safe zero-conf transactions, but only with mempool and
relaying changes) I'd suggest looking at my git commit track record
before you offer anything FWIW; I've been much more of an academic than
a programmer.

-- 
'peter'[:-1]@petertodd.org
0000000000000013030f49fe3eed5e7f9388c4ecc237b7a847ca93255836bc3b

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1336 bytes --]

> SPV clients behaving normally are highly abusive: they use up maximum
> node resources with minimum cost to themselves.
>

This must be a new use of the word "abuse" I haven't come across before :)

At any rate, some of these assumptions are incorrect. Botnets of
compromised web servers are quite common, and asymmetry in node resources
is obviously biased against the kinds of devices people increasingly have
(phones, tablets) where extremely limited memory bandwidth is common and
apps routinely have just 16 or 32mb of memory to do everything including
the GUI.

A good anti-DoS strategy looks much the same as a good load shedding
strategy. There's little reason to treat them separately. Perhaps instead
of talking about DoS we should instead talk about what happens if Bitcoin
suddenly gets too popular. Now there are suddenly lots of good users all
wanting to use the network, and not enough nodes to support them all. What
do we do?

Some rules seem obvious - try to prioritise existing users over new users,
old coins over new coins (dPriority already does this) etc. If you run out
of TCP sockets prefer to disconnect recent connections (probably new users)
to long lived connections (probably high powered backbone peers). If you
run out of disk seeks prefer processing new blocks to serving old parts of
the chain, etc.

[-- Attachment #2: Type: text/html, Size: 1664 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2038 bytes --]

On Thu, Jul 18, 2013 at 08:13:08AM -0400, Peter Todd wrote:
> A more sophisticated approach would be possible if there existed a
> version of H() with a computational trap-door - that is if there existed
> H'(s, i)=H(i) where H' had significantly faster running time than H(),
> but required knowledge of a secret. Our peers would then be able to
> answer our challenges quickly only if they stored the intermediate
> results in a lookup table, while we could check those challenges cheaply
> without that table.
> 
> Adam: you're our local crypto-expert, what can we use for H'? Seems that
> maybe some kind of asymmetric crypto system would work by requiring the
> peer to crack weak secret keys that we generate deterministicly.

Actually, come to think of it a really easy way to create H' is for the
node to create some expensive to compute set of data associated with
their identity. The data set is then stored once by the node, cheap, but
the clients have to store one set for every unique node they connect
too, expensive. A set of the function scrypt(k | i) for i in 0..n is an
obvious way to do it.

This can equally be used as a proof-of-work to make creating lots of
nodes expensive given a cheap way to verify the POW; easily done with a
non-interactive zero-knowledge proofs. It'd be nice if that POW could
incorporate blockchain data, showing that the identity had access to
that data and thus could have computed the UTXO set honestly. (the POW
should be incrementally extendable as new data becomes available)
However that is back to using a bunch of bandwidth at startup if our
peer doesn't have access to blockchain data, so both mechanisms would
probably have to be done independently. Note how we also make MITM
attacks on encrypted P2P connections expensive this way too even without
any form of authentication. (works best when the proof-of-work is
dependent on your IP addresses)

-- 
'peter'[:-1]@petertodd.org
00000000000000762784b647ede3678f172d73dd0c72c2180ab451b00d756959

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Michael Gronager]

Hi Bazyli,

Just did a fresh build based on git (Xcode) - had one issue: the paillier and account tests were missing - please comment them out in tests/CMakeLists.txt, then coinexplorer should build nicely.

Note I did a git push as well, so you need to do a git pull first.

/Michael

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Michael Gronager]

Hi Bazyli,

I actually do my main development on Mac OSX, so it surprises me to hear - I build Xcode projects with libcoin daily on Mac OSX and linux, on Windows it is agreeable more of a fight to build. QT is really not needed, I kept it there for BitcoinQT, that was once part of the tree too, will remove it as the qt part got split out.

Building clean on Mac requires OpenSSL, BDB and Boost - all can be installed using homebrew, also remember to use the latest cmake, and a normal cmake xcode call: cmake -GXcode should do the job. Otherwise pls send me the debug output. 

A few quick notes for building stuff there:
 - try with coinexplorer, it is the base code I am using - it splits out the wallet from the server, nice if you e.g. want to build a webcoin like server.
 - The wallet parts from bitcoind I don't use personally, so if you have problems with these I need to have a closer look.

Also note that as the first version of libcoin was a direct refactorization of bitcoin, the current one add a lot of different features and handles things quite differently - you can e.g. lookup any unspent output by script (bitcoin address) in milliseconds (nice for web wallets).

Finally: 

> 	Because of the templates that bitcoind is actually using that's not gonna work ever. That's why BitcoinKit is a separate dynamic library that's compiled with gcc (or at least llvm pretending to be gcc ;P)

As I mentioned it also compiles on Linux (gcc) - gcc is quite savvy when it comes to templates - I agree that the template stuff from Database.h is quite involved, but as I mentioned before try with coinexplorer.

- I will try to do a from scratch recompilation to see if I experience similar issues...

Also - if you are good at creating frameworks on Mac OSX using cmake, help would be appreciated! I think that libcoin by defaults build using shared libs, this configurable from ccmake using the dynamic library option.

Thanks,

Michael

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4155 bytes --]

On Wed, Jul 17, 2013 at 02:29:26PM +0200, Mike Hearn wrote:
> 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.

Good idea.

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

SPV clients behaving normally are highly abusive: they use up maximum
node resources with minimum cost to themselves. (nodes doing an initial
block download are similar now, although with partial mode they can
contribute back to the network sooner)

We can't win if the attacker has more upstream bandwidth than we have
downstream, but fortunately botnets are generally comprised of computers
on asymetric residential connections. Thus our goal is to prevent the
attacker from using lots of downstream bandwidth, and more importantly,
from consuming more memory and similar resources than we posess.
Annoyingly the raw # of TCP connections is very much a limited resource
due to constraints on the # of ports a process can handle, and
constraints imposed by stateful firewalls, and memory used by kernel
buffers.

Anything that allows for more incoming connections with less memory
usage is a good thing - bloom filters are limited to 32KiB and the
per-peer test if a INV item needs to be relayed to a peer is fairly
cheap, but we also have other buffers like pending INV messages and so
on. EC2 micro instances, as an example, often need -maxconnections
limited or they run out of memory - we've probably got room for
improvement; removing mapRelay and just grabbing relayed txs from the
mempool comes to mind.


More generally a good thing to do would be to force incoming peers to
use up RAM to make a connection. We can do that with a proof-of-data
posession engineered such that unless you store the data in high-speed
memory you will have your connection dropped. Per peer a node can pick a
nonce k and define j_i=H(k+i), sending the peer a set J=(j_0...j_n) to
store in RAM. With f(k, n, i) as a pseudo-random sequence generator we
create nonce x and ask our peer to compute J'(x, m) = j_f(x, n, 0) ^ ...
^ j_f(x, n, m)) and give us the result. (^ as the XOR operator) Because
we know the nonce k we can do that cheaply, calculating it on the fly,
but our peers have no choice but to store J and retrieve it on demand.
If they store J in RAM they can do so quickly; if they store J on disk
they can't. We then prioritize peers by how fast they respond to these
requests, both measuring ping times, and forcing attackers trying to
connect to large numbers of peers to posess large amounts of relatively
expensive RAM. This is particularly nice because we've can make it
significantly more expensive for anyone to peer to every node in the
Bitcoin network simultaneously to do things like watch transaction
propagation in real-time.

A more sophisticated approach would be possible if there existed a
version of H() with a computational trap-door - that is if there existed
H'(s, i)=H(i) where H' had significantly faster running time than H(),
but required knowledge of a secret. Our peers would then be able to
answer our challenges quickly only if they stored the intermediate
results in a lookup table, while we could check those challenges cheaply
without that table.

Adam: you're our local crypto-expert, what can we use for H'? Seems that
maybe some kind of asymmetric crypto system would work by requiring the
peer to crack weak secret keys that we generate deterministicly.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Bazyli Zygan]

[-- Attachment #1: Type: text/plain, Size: 1151 bytes --]

Hi!

I should introduce myself. I am the BitcoinKit developer. If you can call that way a dude that wrapped up already existing code for Mac developers easier to understand and use :-)

I'm replying mostly because libcoin is something that I would like to have a closer look at.
Problems I've encountered with it so far are as follows:

1. It uses QT.
Well. It's a lib. Or at least I've thought it was. But it seems that I really need it to compile it. Dunno why yet.

2. Steps to create xcodeproject doesn't work
For some reason when I've tried to follow steps to create an xcodeproject from the cmake, it failed.

3. It doesn't compile at all
Even after installing QT libs and using cmake to compile it from the terminal… it fails on bitcoind.cpp. My assumtion is that cmake or not - it uses llvm to compile the stuff.
Because of the templates that bitcoind is actually using that's not gonna work ever. That's why BitcoinKit is a separate dynamic library that's compiled with gcc (or at least llvm pretending to be gcc ;P)

Michael, have you tried to use your sources on Mac OS X recently? It seems to be a bit… outdated.

/b

[-- Attachment #2: Type: text/html, Size: 2598 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 539 bytes --]

> The 90 minutes is not - the blockchain has grown quite a lot since last
> year, and as for the 3.5 speed, I havn't tested it since Pieter's
> ultraprune - libcoin also has something similar to ultraprune, done
> directly in the sqlite database backend, but I should run a head to head
> again - could be fun. I would assume, though, that the result would be
> similar timings.
>

ultraprune made a huge difference. I think it's very likely that this claim
is no longer true. Bitcoin got a lot more optimised since you first did
libcoin.

[-- Attachment #2: Type: text/html, Size: 770 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Gregory Maxwell]

On Wed, Jul 17, 2013 at 3:26 PM, Michael Gronager <gronager@mac.com> wrote:
> However, by having a merkle tree hash of all UTXOs they become downloadable in a trusted manner from any other client - something that enables bootstrap in minutes, so the old numbers becomes less relevant in this setting.

This, however, reduces the node to SPV security of the past history.
Particularly for a wallet client— as opposed to a miner or what have
you— if you are willing to accept SPV security you could simply be an
SPV client.

(I like committed UTXO trees, and I believe I was the first person to
suggest them— but I think it's good to not over-hype what they do!)

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Michael Gronager]

> Is that still accurate Michael?
> 

The 90 minutes is not - the blockchain has grown quite a lot since last year, and as for the 3.5 speed, I havn't tested it since Pieter's ultraprune - libcoin also has something similar to ultraprune, done directly in the sqlite database backend, but I should run a head to head again - could be fun. I would assume, though, that the result would be similar timings.

However, by having a merkle tree hash of all UTXOs they become downloadable in a trusted manner from any other client - something that enables bootstrap in minutes, so the old numbers becomes less relevant in this setting.

> 
> On Wed, Jul 17, 2013 at 4:58 PM, Wendell <w@grabhive.com> wrote:
> "The libcoin/bitcoind client downloads the entire block chain 3.5 times faster than the bitcoin/bitcoind client. This is less than 90 minutes on a modern laptop!"
> 
> 

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1845 bytes --]

Is that still accurate Michael?


On Wed, Jul 17, 2013 at 4:58 PM, Wendell <w@grabhive.com> wrote:

> "The libcoin/bitcoind client downloads the entire block chain 3.5 times
> faster than the bitcoin/bitcoind client. This is less than 90 minutes on a
> modern laptop!"
>
> Good lord Michael, I wish we had known about libcoin a month ago!
>
> -wendell
>
> grabhive.com | twitter.com/grabhive
>
> On Jul 17, 2013, at 4:31 PM, Michael Gronager wrote:
>
> > Hi Wendell,
> >
> > What Peter describes (a hash of the current set of UTXOs as part of the
> coinbase) is already implemented in libcoin, on which you can easily build
> both a bitcoind and any client. Libcoin is a library originally based on
> the satoshi client, and as such it is compatible/replacable with "master".
> >
> > Have a look at github.com/libcoin/libcoin and look in the
> BlockChain.h/cpp and the MerkleTrie classes then you can see how it works.
> >
> > What is missing from libcoin is a scheme to bootstrap the hash of UTXOs,
> there is some stub code for a p2pool like mining scheme ensuring several
> UTXO hashes every 10 minutes, but I will not have time to finalize it the
> first few months - anyone are of course welcome to help out ;)
> >
> > Michael
>
>
>
> ------------------------------------------------------------------------------
> 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
>
>

[-- Attachment #2: Type: text/html, Size: 2762 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Wendell]

[-- Attachment #1: Type: text/plain, Size: 1107 bytes --]

"The libcoin/bitcoind client downloads the entire block chain 3.5 times faster than the bitcoin/bitcoind client. This is less than 90 minutes on a modern laptop!"

Good lord Michael, I wish we had known about libcoin a month ago!

-wendell

grabhive.com | twitter.com/grabhive

On Jul 17, 2013, at 4:31 PM, Michael Gronager wrote:

> Hi Wendell,
> 
> What Peter describes (a hash of the current set of UTXOs as part of the coinbase) is already implemented in libcoin, on which you can easily build both a bitcoind and any client. Libcoin is a library originally based on the satoshi client, and as such it is compatible/replacable with "master". 
> 
> Have a look at github.com/libcoin/libcoin and look in the BlockChain.h/cpp and the MerkleTrie classes then you can see how it works.
> 
> What is missing from libcoin is a scheme to bootstrap the hash of UTXOs, there is some stub code for a p2pool like mining scheme ensuring several UTXO hashes every 10 minutes, but I will not have time to finalize it the first few months - anyone are of course welcome to help out ;)
> 
> Michael


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 841 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Michael Gronager]

[-- Attachment #1: Type: text/plain, Size: 3165 bytes --]

Hi Wendell,

What Peter describes (a hash of the current set of UTXOs as part of the coinbase) is already implemented in libcoin, on which you can easily build both a bitcoind and any client. Libcoin is a library originally based on the satoshi client, and as such it is compatible/replacable with "master". 

Have a look at github.com/libcoin/libcoin and look in the BlockChain.h/cpp and the MerkleTrie classes then you can see how it works.

What is missing from libcoin is a scheme to bootstrap the hash of UTXOs, there is some stub code for a p2pool like mining scheme ensuring several UTXO hashes every 10 minutes, but I will not have time to finalize it the first few months - anyone are of course welcome to help out ;)

Michael


On 17/07/2013, at 09:37, Wendell <w@grabhive.com> wrote:

> Peter,
> 
> This sounds like a _very_ good idea for a desktop client, and probably acceptable to users so long as we take available disk space into consideration, and only ever use a fraction of it.
> 
> Will you implement this?
> 
> -wendell
> 
> grabhive.com | twitter.com/grabhive
> 
> On Jul 17, 2013, at 12:58 PM, Peter Todd wrote:
> 
>> 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.
> 
> ------------------------------------------------------------------------------
> 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


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 495 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Wendell]

[-- Attachment #1: Type: text/plain, Size: 1698 bytes --]

Peter,

This sounds like a _very_ good idea for a desktop client, and probably acceptable to users so long as we take available disk space into consideration, and only ever use a fraction of it.

Will you implement this?

-wendell

grabhive.com | twitter.com/grabhive

On Jul 17, 2013, at 12:58 PM, Peter Todd wrote:

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


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 841 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 8519 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 9816 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 6951 bytes --]

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 4796 bytes --]

You'd want to create and get merged patches in the following order:

1) Be able to store just block headers in the blkXXXX.dat files instead of
full block contents. At this point you are still *downloading* full blocks,
but they are not being stored. The contents are still sent to the wallet
for extracting relevant transactions though (see SyncWithWallets).  You
also need to disable listening and addr announcements to the P2P network at
this point. You need to be able to re-org and do all the usual things
without storing block contents. You also need to short-circuit the leveldbs
so they aren't created or used. All that needs to be unit tested. You need
to also rewrite the mempool logic so it throws out irrelevant transactions.
The RPC interface needs to adjust itself so you can't try to start mining,
query the utxo set, etc.

At this point you have an SPV node, albeit one that still downloads the
entire block chain. However total disk storage used will be much lower.
Getting this written and reviewed is a big chunk of work but is the hardest
part. Once it's done you can breath easy.

2) Next step, use getheaders to catch up with the chain until the
min(wallet birthdays) is reached. You can see in Satoshi's patch where he
adds support for receiving "headers" messages. Because key times are
recorded as dates and you don't know the dates of blocks in advance, you
need to download headers until you see one that goes past the key birthday
minus some slack period, then throw out the headers you downloaded and
switch to downloading full blocks again from that point onwards.

3) Next step, implement client side support for Bloom filtering. Switch
from downloading full blocks to filteredblocks, verify the Merkle branches
then apply them to the wallet. Watch out for accidental re-orderings of
transactions here from block order (e.g. if you accidentally insert them
into a std::map or other unordered collection it can lead to bugs). Come up
with some way to decide on a FP rate. Probably you want a fairly high FP
rate for desktop wallets.

4) Next step (optional), implement monitoring of broadcast propagation for
transactions that are received. SPV clients cannot verify unconfirmed
transactions so you can either just give up entirely and accept any old
garbage, or assume a non-MITMd internet connection and use network
propagation as a rough proxy for "likely to be valid and mined upon".

4) Optimize!

How much you need to optimize really depends on a lot of things. I found
that to be competitive with Electrum/blockchain.info I had to do a ton of
optimizations including very aggressive checkpointing so new users don't
have to download more than a month or twos worth of headers, as downloading
all the headers was becoming a bottleneck. You'd need to download about
16mb+ of data at the moment to grab all the headers and on a weakass mobile
phone with a weak Dalvik VM and 3G internet this was way too much. I also
had to spend some time profiling to ensure we weren't accidentally
thrashing the UI due to too-fast updates, we weren't bottlenecking on
updating last seen block data in the wallet, we weren't accidentally
de/reserializing messages redundantly etc.

After about 3-4 evenings of non-stop profiling and optimising I ended up
with a relatively flat profile whilst doing initial catchup and chain sync.
On a desktop I bet you can get away with much less optimisation because
your CPUs, network and disk tend to be much stronger.



On Tue, Jul 16, 2013 at 4:16 PM, Wendell <w@grabhive.com> 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.
>
> -wendell
>
> grabhive.com | twitter.com/grabhive
>
>
>
> ------------------------------------------------------------------------------
> 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
>

[-- Attachment #2: Type: text/html, Size: 5851 bytes --]

[Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)

[Wendell]

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.

-wendell

grabhive.com | twitter.com/grabhive