* [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
@ 2012-01-02 5:04 Elden Tyrell
2012-01-02 13:31 ` Christian Decker
0 siblings, 1 reply; 6+ messages in thread
From: Elden Tyrell @ 2012-01-02 5:04 UTC (permalink / raw)
To: bitcoin-development
Satoshi's paper mentions that storage requirements for the blockchain
can be reduced by deleting transactions whose outputs have been spent.
If I understand correctly, this technique can only be used for reducing
*storage* requirements, not *bandwidth* needed for the initial chain
download by a high-security client that doesn't trust any of its peers
-- right?
The rule is "trust the longest valid chain of blocks". Part of a block
being "valid" is that each transaction's inputs are unspent and their
sum exceeds the transaction's outputs unless it is a coinbase. This
cannot be verified for "stubbed out" transactions -- they have outputs
but no inputs, and aren't coinbases. So a paranoid client booting up
for the first time needs to be given an un-stubbed chain, right?
Of course, if a client decided to accept a stubbed blocks only when the
sum of the difficulties in the blocks after it exceeds some number N,
then attacking it could be made very expensive by picking a large
enough N.
Please let me know if I have misunderstood something.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
2012-01-02 5:04 [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth? Elden Tyrell
@ 2012-01-02 13:31 ` Christian Decker
2012-01-02 22:23 ` Elden Tyrell
0 siblings, 1 reply; 6+ messages in thread
From: Christian Decker @ 2012-01-02 13:31 UTC (permalink / raw)
To: Elden Tyrell; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 2368 bytes --]
It can speed up the initial chain download. A newly created wallet will
have only new key-pairs, hence no incoming transactions (unless we have a
key collision, which is unlikely). So there is no need for a bootstrapping
node to download the chain with transactions. The chain itself can be
verified without the transactions. Later full blocks would be required to
detect usable inputs for future outgoing transactions. As long as you
verify the very last blocks in the chain you can be sure that all
preceeding blocks were also valid.
HTH,
Chris
On Mon, Jan 2, 2012 at 6:04 AM, Elden Tyrell <tyrell.elden@gmail•com> wrote:
> Satoshi's paper mentions that storage requirements for the blockchain
> can be reduced by deleting transactions whose outputs have been spent.
>
> If I understand correctly, this technique can only be used for reducing
> *storage* requirements, not *bandwidth* needed for the initial chain
> download by a high-security client that doesn't trust any of its peers
> -- right?
>
> The rule is "trust the longest valid chain of blocks". Part of a block
> being "valid" is that each transaction's inputs are unspent and their
> sum exceeds the transaction's outputs unless it is a coinbase. This
> cannot be verified for "stubbed out" transactions -- they have outputs
> but no inputs, and aren't coinbases. So a paranoid client booting up
> for the first time needs to be given an un-stubbed chain, right?
>
> Of course, if a client decided to accept a stubbed blocks only when the
> sum of the difficulties in the blocks after it exceeds some number N,
> then attacking it could be made very expensive by picking a large
> enough N.
>
> Please let me know if I have misunderstood something.
>
>
>
>
> ------------------------------------------------------------------------------
> Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don't need a complex
> infrastructure or vast IT resources to deliver seamless, secure access to
> virtual desktops. With this all-in-one solution, easily deploy virtual
> desktops for less than the cost of PCs and save 60% on VDI infrastructure
> costs. Try it free! http://p.sf.net/sfu/Citrix-VDIinabox
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
[-- Attachment #2: Type: text/html, Size: 3002 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
2012-01-02 13:31 ` Christian Decker
@ 2012-01-02 22:23 ` Elden Tyrell
2012-01-02 22:41 ` Gregory Maxwell
0 siblings, 1 reply; 6+ messages in thread
From: Elden Tyrell @ 2012-01-02 22:23 UTC (permalink / raw)
To: bitcoin-development
On 2012-01-02 05:31:19 -0800, Christian Decker said:
> Later full blocks would be required to detect usable inputs for future
> outgoing transactions.
Er, yes, this is what I meant; I guess I should have been more specific.
So, a paranoid client cannot confirm reciept of coins until it has an
unstubbed copy of the entire chain. It can do other things (like send
coins) using a stubbed chain, but it needs the whole unstubbed chain in
order to be sure that incoming coins haven't already been spent.
Thanks for confirming this.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
2012-01-02 22:23 ` Elden Tyrell
@ 2012-01-02 22:41 ` Gregory Maxwell
2012-01-03 1:39 ` Elden Tyrell
0 siblings, 1 reply; 6+ messages in thread
From: Gregory Maxwell @ 2012-01-02 22:41 UTC (permalink / raw)
To: Elden Tyrell; +Cc: bitcoin-development
On Mon, Jan 2, 2012 at 5:23 PM, Elden Tyrell <tyrell.elden@gmail•com> wrote:
> On 2012-01-02 05:31:19 -0800, Christian Decker said:
>> Later full blocks would be required to detect usable inputs for future
>> outgoing transactions.
>
> Er, yes, this is what I meant; I guess I should have been more specific.
>
> So, a paranoid client cannot confirm reciept of coins until it has an
> unstubbed copy of the entire chain. It can do other things (like send
> coins) using a stubbed chain, but it needs the whole unstubbed chain in
> order to be sure that incoming coins haven't already been spent.
>
> Thanks for confirming this.
Er, no— if a node controls the private keys for a transaction, and
that transaction makes it into the chain then it can safely assume
that its unspent (at least once its buried a few blocks into the
chain). This is the essence of a SPV node.
What it can't do is perform this function for txn which aren't its
own. Though the system could be extended in a compatible manner to
make this possible: https://bitcointalk.org/index.php?topic=21995.0
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
2012-01-02 22:41 ` Gregory Maxwell
@ 2012-01-03 1:39 ` Elden Tyrell
2012-01-05 23:30 ` Mike Hearn
0 siblings, 1 reply; 6+ messages in thread
From: Elden Tyrell @ 2012-01-03 1:39 UTC (permalink / raw)
To: bitcoin-development
On 2012-01-02 14:41:10 -0800, Gregory Maxwell said:
> make this possible: https://bitcointalk.org/index.php?topic=21995.0
Neat! I had a similar idea but you've clearly beat me to [a big part of] it.
> Er, no— if a node controls the private keys for a transaction, and
> that transaction makes it into the chain then it can safely assume
> that its unspent (at least once its buried a few blocks into the
> chain).
I'm not so sure about that. If you accept X successor blocks as proof
that none of the transactions in a block re-used an output, then the
cost of attacking is X*50BTC since the hashpower needed for the attack
could have earned that much reward.
However, an attacker could use the same faked X-block sequence to
attack multiple clients by putting several double-spend transactions in
the first faked block. This would spread out the cost over more than
one attack. So simply checking that the value of the transaction is
less than X*50 isn't necessarily enough, although the logistics of the
attack aren't exactly easy.
There's also the question of knowing what the difficulty for those X
blocks ought to be. If the attacker controls your network connection
(e.g. your ISP attacks you) you wouldn't be able to get a second
opinion on how high the difficulty ought to be, and might get fooled by
X very-low-difficulty blocks that were each produced with a lot less
than 50BTC worth of hashpower.
- e
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth?
2012-01-03 1:39 ` Elden Tyrell
@ 2012-01-05 23:30 ` Mike Hearn
0 siblings, 0 replies; 6+ messages in thread
From: Mike Hearn @ 2012-01-05 23:30 UTC (permalink / raw)
To: Elden Tyrell; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1852 bytes --]
This thread is discussing two unrelated things.
Your first email asked about transaction pruning ("stubbing"). You're
correct. This doesn't do anything for initial chain download bandwidth or
time. In fact it makes it slower because you have the overhead of deleting
the old transactions. It exists purely to save disk space.
Christians reply is about simplified payment verification (SPV) mode. It is
unrelated to transaction pruning. SPV clients can download only the chain
headers with no bodies all the way from the genesis block until the
creation time of their youngest key. This does reduce initial setup time
and in fact is now implemented in BitCoinJ, but it's still linear in the
length of Bitcoins life, so that's ultimately unsustainable. You need a
regular series of checkpoints signed by a trusted developer and a circular
block store to have truly bounded overheads. The merkle tree is still
useful because it allows for SPV clients to receive only the transactions
of interest yet have nearly the same assurances that downloading full
blocks would give - remote nodes can now hide transactions from you (dos)
but not invent new ones.
SPV clients do not use "number of blocks on top" as a way to decide
validity. They look for the best chain they can find, same as a regular
node does. As Satoshis paper says, if an SPV node has access to the P2P
network and is also talking to you, you can defraud it for as long as you
can dominate the networks hash power (51% attack) because you can create a
harder chain than everyone else can. However your invalid blocks won't be
accepted by the rest of the network regardless of how many there are or how
much work they represent, so as soon as you stop dominating the network the
correct chain will catch up and replace yours, resulting in the fraud being
detected and shown to the SPV user.
[-- Attachment #2: Type: text/html, Size: 1919 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2012-01-05 23:30 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-01-02 5:04 [Bitcoin-development] does "stubbing" off Merkle trees reduce initial download bandwidth? Elden Tyrell
2012-01-02 13:31 ` Christian Decker
2012-01-02 22:23 ` Elden Tyrell
2012-01-02 22:41 ` Gregory Maxwell
2012-01-03 1:39 ` Elden Tyrell
2012-01-05 23:30 ` Mike Hearn
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox