* [Bitcoin-development] Chain pruning
@ 2014-04-10 11:37 Mike Hearn
2014-04-10 11:57 ` Wladimir
0 siblings, 1 reply; 21+ messages in thread
From: Mike Hearn @ 2014-04-10 11:37 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 731 bytes --]
Chain pruning is probably a separate thread, changing subject.
> Reason is that the actual blocks available are likely to change frequently
> (if
> you keep the last week of blocks
I doubt anyone would specify blocks to keep in terms of time. More likely
it'd be in terms of megabytes, as that's the actual resource constraint on
nodes. Given a block size average it's easy to go from megabytes to
num_blocks, so I had imagined it'd be a new addr field that specifies how
many blocks from the chain head are stored. Then you'd connect to some
nodes and if they indicate their chain head - num_blocks_stored is higher
than your current chain height, you'd do a getaddr and go looking for nodes
that are storing far enough back.
[-- Attachment #2: Type: text/html, Size: 1032 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 11:37 [Bitcoin-development] Chain pruning Mike Hearn
@ 2014-04-10 11:57 ` Wladimir
2014-04-10 12:10 ` Gregory Maxwell
0 siblings, 1 reply; 21+ messages in thread
From: Wladimir @ 2014-04-10 11:57 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1419 bytes --]
On Thu, Apr 10, 2014 at 1:37 PM, Mike Hearn <mike@plan99•net> wrote:
> Chain pruning is probably a separate thread, changing subject.
>
>
>> Reason is that the actual blocks available are likely to change
>> frequently (if
>> you keep the last week of blocks
>
>
> I doubt anyone would specify blocks to keep in terms of time. More likely
> it'd be in terms of megabytes, as that's the actual resource constraint on
> nodes.
>
Well with bitcoin, (average) time, number of blocks and (maximum) size are
all related to each other so it doesn't matter how it is specified, it's
always possible to give estimates of all three.
As for implementation it indeed makes most sense to work with block ranges.
> Given a block size average it's easy to go from megabytes to num_blocks,
> so I had imagined it'd be a new addr field that specifies how many blocks
> from the chain head are stored. Then you'd connect to some nodes and if
> they indicate their chain head - num_blocks_stored is higher than your
> current chain height, you'd do a getaddr and go looking for nodes that are
> storing far enough back.
>
This assumes that nodes will always be storing the latest blocks. For
dynamic nodes that take part in the consensus this makes sense.
Just wondering: Would there be a use for a [static] node that, say, always
serves only the first 100000 blocks? Or, even, a static range like block
100000 - 200000?
Wladimir
[-- Attachment #2: Type: text/html, Size: 2296 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 11:57 ` Wladimir
@ 2014-04-10 12:10 ` Gregory Maxwell
2014-04-10 14:19 ` Wladimir
0 siblings, 1 reply; 21+ messages in thread
From: Gregory Maxwell @ 2014-04-10 12:10 UTC (permalink / raw)
To: Wladimir; +Cc: Bitcoin Dev
On Thu, Apr 10, 2014 at 4:57 AM, Wladimir <laanwj@gmail•com> wrote:
> Just wondering: Would there be a use for a [static] node that, say, always
> serves only the first 100000 blocks? Or, even, a static range like block
> 100000 - 200000?
The last time we discussed this sipa collected data based on how often
blocks were feteched as a function of their depth and there was a huge
increase for recent blocks that didn't really level out until 2000
blocks or so— presumably its not uncommon for nodes to be offline for
a week or two at a time.
But sure I could see a fixed range as also being a useful contribution
though I'm struggling to figure out what set of constraints would
leave a node without following the consensus? Obviously it has
bandwidth if you're expecting to contribute much in serving those
historic blocks... and verifying is reasonably cpu cheap with fast
ecdsa code. Maybe it has a lot of read only storage?
I think it should be possible to express and use such a thing in the
protocol even if I'm currently unsure as to why you wouldn't do 100000
- 200000 _plus_ the most recent 144 that you were already keeping
around for reorgs.
In terms of peer selection, if the blocks you need aren't covered by
the nodes you're currently connected to I think you'd prefer to seek
node nodes which have the least rare-ness in the ranges they offer.
E.g. if you're looking for a block 50 from the tip, you're should
probably not prefer to fetch it from someone with blocks 100000-150000
if its one of only 100 nodes that has that range.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 12:10 ` Gregory Maxwell
@ 2014-04-10 14:19 ` Wladimir
2014-04-10 16:23 ` Brian Hoffman
0 siblings, 1 reply; 21+ messages in thread
From: Wladimir @ 2014-04-10 14:19 UTC (permalink / raw)
To: Gregory Maxwell; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1979 bytes --]
On Thu, Apr 10, 2014 at 2:10 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
> But sure I could see a fixed range as also being a useful contribution
> though I'm struggling to figure out what set of constraints would
> leave a node without following the consensus? Obviously it has
> bandwidth if you're expecting to contribute much in serving those
> historic blocks... and verifying is reasonably cpu cheap with fast
> ecdsa code. Maybe it has a lot of read only storage?
>
The use case is that you could burn the node implementation + block data +
a live operating system on a read-only medium. This could be set in stone
for a long time.
There would be no consensus code to keep up to date with protocol
developments, because it doesn't take active part in it.
I don't think it would be terribly useful right now, but it could be useful
when nodes that host all history become rare. It'd allow distributing
'pieces of history' in a self-contained form.
> I think it should be possible to express and use such a thing in the
> protocol even if I'm currently unsure as to why you wouldn't do 100000
> - 200000 _plus_ the most recent 144 that you were already keeping
> around for reorgs.
>
Yes, it would be nice to at least be able to express it, if it doesn't make
the protocol too finicky.
In terms of peer selection, if the blocks you need aren't covered by
> the nodes you're currently connected to I think you'd prefer to seek
> node nodes which have the least rare-ness in the ranges they offer.
> E.g. if you're looking for a block 50 from the tip, you're should
> probably not prefer to fetch it from someone with blocks 100000-150000
> if its one of only 100 nodes that has that range.
>
That makes sense.
In general, if you want a block 50 from the tip, it would be best to
request it from a node that only serves the last N (N>~50) blocks, and not
a history node that could use the same bandwidth to serve earlier, rarer
blocks to others.
Wladimir
[-- Attachment #2: Type: text/html, Size: 2795 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 14:19 ` Wladimir
@ 2014-04-10 16:23 ` Brian Hoffman
2014-04-10 16:28 ` Mike Hearn
0 siblings, 1 reply; 21+ messages in thread
From: Brian Hoffman @ 2014-04-10 16:23 UTC (permalink / raw)
To: Wladimir; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3678 bytes --]
This is probably just noise, but what if nodes could compress and store
earlier transaction sets (archive sets) and serve them up conditionally. So
if there were let's say 100 archive sets of (10,000 blocks) you might have
5 open at any time when you're an active archive node while the others sit
on your disk compressed and unavailable to the network. This would allow
nodes to have all full transactions but conserve disk space and network
activity since they wouldn't ever respond about every possible transaction.
This could be based on a rotational request period, based on request count
or done periodically. Once their considered active they would be expected
to uncompress a set and make it available to the network. Clients would
have to piece together archive sets from different nodes, but if there
weren't enough archive nodes to cover the chain they could ratchet up the
amount of required open archive sets when your node was active.
I fully expect to have my idea trashed, but I'm dipping toes in the waters
of contribution.
On Thu, Apr 10, 2014 at 10:19 AM, Wladimir <laanwj@gmail•com> wrote:
>
> On Thu, Apr 10, 2014 at 2:10 PM, Gregory Maxwell <gmaxwell@gmail•com>wrote:
>
>> But sure I could see a fixed range as also being a useful contribution
>> though I'm struggling to figure out what set of constraints would
>> leave a node without following the consensus? Obviously it has
>> bandwidth if you're expecting to contribute much in serving those
>> historic blocks... and verifying is reasonably cpu cheap with fast
>> ecdsa code. Maybe it has a lot of read only storage?
>>
>
> The use case is that you could burn the node implementation + block data +
> a live operating system on a read-only medium. This could be set in stone
> for a long time.
>
> There would be no consensus code to keep up to date with protocol
> developments, because it doesn't take active part in it.
>
> I don't think it would be terribly useful right now, but it could be
> useful when nodes that host all history become rare. It'd allow
> distributing 'pieces of history' in a self-contained form.
>
>
>> I think it should be possible to express and use such a thing in the
>> protocol even if I'm currently unsure as to why you wouldn't do 100000
>> - 200000 _plus_ the most recent 144 that you were already keeping
>> around for reorgs.
>>
>
> Yes, it would be nice to at least be able to express it, if it doesn't
> make the protocol too finicky.
>
> In terms of peer selection, if the blocks you need aren't covered by
>> the nodes you're currently connected to I think you'd prefer to seek
>> node nodes which have the least rare-ness in the ranges they offer.
>> E.g. if you're looking for a block 50 from the tip, you're should
>> probably not prefer to fetch it from someone with blocks 100000-150000
>> if its one of only 100 nodes that has that range.
>>
>
> That makes sense.
>
> In general, if you want a block 50 from the tip, it would be best to
> request it from a node that only serves the last N (N>~50) blocks, and not
> a history node that could use the same bandwidth to serve earlier, rarer
> blocks to others.
>
> Wladimir
>
>
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
[-- Attachment #2: Type: text/html, Size: 5202 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:23 ` Brian Hoffman
@ 2014-04-10 16:28 ` Mike Hearn
2014-04-10 16:47 ` Brian Hoffman
2014-04-10 16:52 ` Ricardo Filipe
0 siblings, 2 replies; 21+ messages in thread
From: Mike Hearn @ 2014-04-10 16:28 UTC (permalink / raw)
To: Brian Hoffman; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 531 bytes --]
Suggestions always welcome!
The main problem with this is that the block chain is mostly random bytes
(hashes, keys) so it doesn't compress that well. It compresses a bit, but
not enough to change the fundamental physics.
However, that does not mean the entire chain has to be stored on expensive
rotating platters. I've suggested that in some star trek future where the
chain really is gigantic, it could be stored on tape and spooled off at
high speed. Literally a direct DMA from tape drive to NIC. But we're not
there yet :)
[-- Attachment #2: Type: text/html, Size: 617 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:28 ` Mike Hearn
@ 2014-04-10 16:47 ` Brian Hoffman
2014-04-10 16:54 ` Ricardo Filipe
2014-04-10 16:59 ` Pieter Wuille
2014-04-10 16:52 ` Ricardo Filipe
1 sibling, 2 replies; 21+ messages in thread
From: Brian Hoffman @ 2014-04-10 16:47 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1067 bytes --]
Looks like only about ~30% disk space savings so I see your point. Is there
a critical reason why blocks couldn't be formed into "superblocks" that are
chained together and nodes could serve a specific superblock, which could
be pieced together from different nodes to get the full blockchain? This
would allow participants with limited resources to serve full portions of
the blockchain rather than limited pieces of the entire blockchain.
On Thu, Apr 10, 2014 at 12:28 PM, Mike Hearn <mike@plan99•net> wrote:
> Suggestions always welcome!
>
> The main problem with this is that the block chain is mostly random bytes
> (hashes, keys) so it doesn't compress that well. It compresses a bit, but
> not enough to change the fundamental physics.
>
> However, that does not mean the entire chain has to be stored on expensive
> rotating platters. I've suggested that in some star trek future where the
> chain really is gigantic, it could be stored on tape and spooled off at
> high speed. Literally a direct DMA from tape drive to NIC. But we're not
> there yet :)
>
[-- Attachment #2: Type: text/html, Size: 1446 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:28 ` Mike Hearn
2014-04-10 16:47 ` Brian Hoffman
@ 2014-04-10 16:52 ` Ricardo Filipe
1 sibling, 0 replies; 21+ messages in thread
From: Ricardo Filipe @ 2014-04-10 16:52 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
anyway, any kind of compression that comes to the blockchain is
orthogonal to pruning.
I agree that you will probably want some kind of replication on more
recent nodes than on older ones. However, nodes with older blocks
don't need to be "static", get the block distribution algorithm to
sort it out.
2014-04-10 17:28 GMT+01:00 Mike Hearn <mike@plan99•net>:
> Suggestions always welcome!
>
> The main problem with this is that the block chain is mostly random bytes
> (hashes, keys) so it doesn't compress that well. It compresses a bit, but
> not enough to change the fundamental physics.
>
> However, that does not mean the entire chain has to be stored on expensive
> rotating platters. I've suggested that in some star trek future where the
> chain really is gigantic, it could be stored on tape and spooled off at high
> speed. Literally a direct DMA from tape drive to NIC. But we're not there
> yet :)
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:47 ` Brian Hoffman
@ 2014-04-10 16:54 ` Ricardo Filipe
2014-04-10 16:56 ` Brian Hoffman
2014-04-10 16:59 ` Pieter Wuille
1 sibling, 1 reply; 21+ messages in thread
From: Ricardo Filipe @ 2014-04-10 16:54 UTC (permalink / raw)
To: Brian Hoffman; +Cc: Bitcoin Dev
that's what blockchain pruning is all about :)
2014-04-10 17:47 GMT+01:00 Brian Hoffman <brianchoffman@gmail•com>:
> Looks like only about ~30% disk space savings so I see your point. Is there
> a critical reason why blocks couldn't be formed into "superblocks" that are
> chained together and nodes could serve a specific superblock, which could be
> pieced together from different nodes to get the full blockchain? This would
> allow participants with limited resources to serve full portions of the
> blockchain rather than limited pieces of the entire blockchain.
>
>
> On Thu, Apr 10, 2014 at 12:28 PM, Mike Hearn <mike@plan99•net> wrote:
>>
>> Suggestions always welcome!
>>
>> The main problem with this is that the block chain is mostly random bytes
>> (hashes, keys) so it doesn't compress that well. It compresses a bit, but
>> not enough to change the fundamental physics.
>>
>> However, that does not mean the entire chain has to be stored on expensive
>> rotating platters. I've suggested that in some star trek future where the
>> chain really is gigantic, it could be stored on tape and spooled off at high
>> speed. Literally a direct DMA from tape drive to NIC. But we're not there
>> yet :)
>
>
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:54 ` Ricardo Filipe
@ 2014-04-10 16:56 ` Brian Hoffman
0 siblings, 0 replies; 21+ messages in thread
From: Brian Hoffman @ 2014-04-10 16:56 UTC (permalink / raw)
To: Ricardo Filipe; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1943 bytes --]
Okay...will let myself out now ;P
On Thu, Apr 10, 2014 at 12:54 PM, Ricardo Filipe
<ricardojdfilipe@gmail•com>wrote:
> that's what blockchain pruning is all about :)
>
> 2014-04-10 17:47 GMT+01:00 Brian Hoffman <brianchoffman@gmail•com>:
> > Looks like only about ~30% disk space savings so I see your point. Is
> there
> > a critical reason why blocks couldn't be formed into "superblocks" that
> are
> > chained together and nodes could serve a specific superblock, which
> could be
> > pieced together from different nodes to get the full blockchain? This
> would
> > allow participants with limited resources to serve full portions of the
> > blockchain rather than limited pieces of the entire blockchain.
> >
> >
> > On Thu, Apr 10, 2014 at 12:28 PM, Mike Hearn <mike@plan99•net> wrote:
> >>
> >> Suggestions always welcome!
> >>
> >> The main problem with this is that the block chain is mostly random
> bytes
> >> (hashes, keys) so it doesn't compress that well. It compresses a bit,
> but
> >> not enough to change the fundamental physics.
> >>
> >> However, that does not mean the entire chain has to be stored on
> expensive
> >> rotating platters. I've suggested that in some star trek future where
> the
> >> chain really is gigantic, it could be stored on tape and spooled off at
> high
> >> speed. Literally a direct DMA from tape drive to NIC. But we're not
> there
> >> yet :)
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Put Bad Developers to Shame
> > Dominate Development with Jenkins Continuous Integration
> > Continuously Automate Build, Test & Deployment
> > Start a new project now. Try Jenkins in the cloud.
> > http://p.sf.net/sfu/13600_Cloudbees
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development@lists•sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> >
>
[-- Attachment #2: Type: text/html, Size: 2833 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:47 ` Brian Hoffman
2014-04-10 16:54 ` Ricardo Filipe
@ 2014-04-10 16:59 ` Pieter Wuille
2014-04-10 17:06 ` Brian Hoffman
` (2 more replies)
1 sibling, 3 replies; 21+ messages in thread
From: Pieter Wuille @ 2014-04-10 16:59 UTC (permalink / raw)
To: Brian Hoffman; +Cc: Bitcoin Dev
On Thu, Apr 10, 2014 at 6:47 PM, Brian Hoffman <brianchoffman@gmail•com> wrote:
> Looks like only about ~30% disk space savings so I see your point. Is there
> a critical reason why blocks couldn't be formed into "superblocks" that are
> chained together and nodes could serve a specific superblock, which could be
> pieced together from different nodes to get the full blockchain? This would
> allow participants with limited resources to serve full portions of the
> blockchain rather than limited pieces of the entire blockchain.
As this is a suggestion that I think I've seen come up once a month
for the past 3 years, let's try to answer it thoroughly.
The actual "state" of the blockchain is the UTXO set (stored in
chainstate/ by the reference client). It's the set of all unspent
transaction outputs at the currently active point in the block chain.
It is all you need for validating future blocks.
The problem is, you can't just give someone the UTXO set and expect
them to trust it, as there is no way to prove that it was the result
of processing the actual blocks.
As Bitcoin's full node uses a "zero trust" model, where (apart from
one detail: the order of otherwise valid transactions) it never
assumes any data received from the outside it valid, it HAS to see the
previous blocks in order to establish the validity of the current UTXO
set. This is what initial block syncing does. Nothing but the actual
blocks can provide this data, and it is why the actual blocks need to
be available. It does not require everyone to have all blocks, though
- they just need to have seen them during processing.
A related, but not identical evolution is merkle UTXO commitments.
This means that we shape the UTXO set as a merkle tree, compute its
root after every block, and require that the block commits to this
root hash (by putting it in the coinbase, for example). This means a
full node can copy the chain state from someone else, and check that
its hash matches what the block chain commits to. It's important to
note that this is a strict reduction in security: we're now trusting
that the longest chain (with most proof of work) commits to a valid
UTXO set (at some point in the past).
In essence, combining both ideas means you get "superblocks" (the UTXO
set is essentially the summary of the result of all past blocks), in a
way that is less-than-currently-but-perhaps-still-acceptably-validated.
--
Pieter
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:59 ` Pieter Wuille
@ 2014-04-10 17:06 ` Brian Hoffman
2014-04-10 18:19 ` Paul Rabahy
2014-04-10 21:34 ` Jesus Cea
2 siblings, 0 replies; 21+ messages in thread
From: Brian Hoffman @ 2014-04-10 17:06 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2931 bytes --]
Ok I think I've got a good understanding of where we're at now. I can
promise that the next person to waste your time in 30 days will not be me.
I'm pleasantly surprised to see a community that doesn't kickban newcomers
and takes the time to explain (re-explain) concepts.
Hoping to add *beneficial* thoughts in the future!
On Thu, Apr 10, 2014 at 12:59 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:
> On Thu, Apr 10, 2014 at 6:47 PM, Brian Hoffman <brianchoffman@gmail•com>
> wrote:
> > Looks like only about ~30% disk space savings so I see your point. Is
> there
> > a critical reason why blocks couldn't be formed into "superblocks" that
> are
> > chained together and nodes could serve a specific superblock, which
> could be
> > pieced together from different nodes to get the full blockchain? This
> would
> > allow participants with limited resources to serve full portions of the
> > blockchain rather than limited pieces of the entire blockchain.
>
> As this is a suggestion that I think I've seen come up once a month
> for the past 3 years, let's try to answer it thoroughly.
>
> The actual "state" of the blockchain is the UTXO set (stored in
> chainstate/ by the reference client). It's the set of all unspent
> transaction outputs at the currently active point in the block chain.
> It is all you need for validating future blocks.
>
> The problem is, you can't just give someone the UTXO set and expect
> them to trust it, as there is no way to prove that it was the result
> of processing the actual blocks.
>
> As Bitcoin's full node uses a "zero trust" model, where (apart from
> one detail: the order of otherwise valid transactions) it never
> assumes any data received from the outside it valid, it HAS to see the
> previous blocks in order to establish the validity of the current UTXO
> set. This is what initial block syncing does. Nothing but the actual
> blocks can provide this data, and it is why the actual blocks need to
> be available. It does not require everyone to have all blocks, though
> - they just need to have seen them during processing.
>
> A related, but not identical evolution is merkle UTXO commitments.
> This means that we shape the UTXO set as a merkle tree, compute its
> root after every block, and require that the block commits to this
> root hash (by putting it in the coinbase, for example). This means a
> full node can copy the chain state from someone else, and check that
> its hash matches what the block chain commits to. It's important to
> note that this is a strict reduction in security: we're now trusting
> that the longest chain (with most proof of work) commits to a valid
> UTXO set (at some point in the past).
>
> In essence, combining both ideas means you get "superblocks" (the UTXO
> set is essentially the summary of the result of all past blocks), in a
> way that is less-than-currently-but-perhaps-still-acceptably-validated.
>
> --
> Pieter
>
[-- Attachment #2: Type: text/html, Size: 3609 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:59 ` Pieter Wuille
2014-04-10 17:06 ` Brian Hoffman
@ 2014-04-10 18:19 ` Paul Rabahy
2014-04-10 18:32 ` Pieter Wuille
2014-04-10 19:36 ` Mark Friedenbach
2014-04-10 21:34 ` Jesus Cea
2 siblings, 2 replies; 21+ messages in thread
From: Paul Rabahy @ 2014-04-10 18:19 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3876 bytes --]
You say UTXO commitments is "a strict reduction in security". If UTXO
commitments were rolled in as a soft fork, I do not see any new attacks
that could happen to a person trusting the committed UTXO + any remaining
blocks to catch up to the head.
I would imagine the soft fork to proceed similar to the following.
1. Miners begin including UTXO commitments.
2. Miners begin rejecting blocks with invalid UTXO commitments.
3. Miners begin rejecting blocks with no UTXO commitments.
To start up a fresh client it would follow the following.
1. Sync headers.
2. Pick a committed UTXO that is deep enough to not get orphaned.
3. Sync blocks from commitment to head.
I would argue that a client following this methodology is strictly more
secure than SPV, and I don't see any attacks that make it less secure than
a full client. It is obviously still susceptible to a 51% attack, but so is
the traditional block chain. I also do not see any sybil attacks that are
strengthened by this change because it is not modifying the networking code.
I guess if the soft fork happened, then miners began to not include the
UTXO commitment anymore, it would lower the overall network hash rate, but
this would be self-harming to the miners so they have an incentive to not
do it.
Please let me know if I have missed something.
On Thu, Apr 10, 2014 at 12:59 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:
>
> As this is a suggestion that I think I've seen come up once a month
> for the past 3 years, let's try to answer it thoroughly.
>
> The actual "state" of the blockchain is the UTXO set (stored in
> chainstate/ by the reference client). It's the set of all unspent
> transaction outputs at the currently active point in the block chain.
> It is all you need for validating future blocks.
>
> The problem is, you can't just give someone the UTXO set and expect
> them to trust it, as there is no way to prove that it was the result
> of processing the actual blocks.
>
> As Bitcoin's full node uses a "zero trust" model, where (apart from
> one detail: the order of otherwise valid transactions) it never
> assumes any data received from the outside it valid, it HAS to see the
> previous blocks in order to establish the validity of the current UTXO
> set. This is what initial block syncing does. Nothing but the actual
> blocks can provide this data, and it is why the actual blocks need to
> be available. It does not require everyone to have all blocks, though
> - they just need to have seen them during processing.
>
> A related, but not identical evolution is merkle UTXO commitments.
> This means that we shape the UTXO set as a merkle tree, compute its
> root after every block, and require that the block commits to this
> root hash (by putting it in the coinbase, for example). This means a
> full node can copy the chain state from someone else, and check that
> its hash matches what the block chain commits to. It's important to
> note that this is a strict reduction in security: we're now trusting
> that the longest chain (with most proof of work) commits to a valid
> UTXO set (at some point in the past).
>
> In essence, combining both ideas means you get "superblocks" (the UTXO
> set is essentially the summary of the result of all past blocks), in a
> way that is less-than-currently-but-perhaps-still-acceptably-validated.
>
> --
> Pieter
>
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
[-- Attachment #2: Type: text/html, Size: 4975 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 18:19 ` Paul Rabahy
@ 2014-04-10 18:32 ` Pieter Wuille
2014-04-10 20:12 ` Tier Nolan
2014-04-10 19:36 ` Mark Friedenbach
1 sibling, 1 reply; 21+ messages in thread
From: Pieter Wuille @ 2014-04-10 18:32 UTC (permalink / raw)
To: Paul Rabahy; +Cc: Bitcoin Dev
On Thu, Apr 10, 2014 at 8:19 PM, Paul Rabahy <prabahy@gmail•com> wrote:
> Please let me know if I have missed something.
A 51% attack can make you believe you were paid, while you weren't.
Full node security right now validates everything - there is no way
you can ever be made to believe something invalid. The only attacks
against it are about which version of valid history eventually gets
chosen.
If you trust hashrate for determining which UTXO set is valid, a 51%
attack becomes worse in that you can be made to believe a version of
history which is in fact invalid.
--
Pieter
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 18:19 ` Paul Rabahy
2014-04-10 18:32 ` Pieter Wuille
@ 2014-04-10 19:36 ` Mark Friedenbach
1 sibling, 0 replies; 21+ messages in thread
From: Mark Friedenbach @ 2014-04-10 19:36 UTC (permalink / raw)
To: bitcoin-development
You took the quote out of context:
"a full node can copy the chain state from someone else, and check that
its hash matches what the block chain commits to. It's important to
note that this is a strict reduction in security: we're now trusting
that the longest chain (with most proof of work) commits to a valid
UTXO set (at some point in the past)."
The described synchronization mechanism would be to determine the
most-work block header (SPV level of security!), and then sync the UTXO
set committed to within that block. This is strictly less security than
building the UTXO set yourself because it is susceptible to a 51% attack
which violates protocol rules.
On 04/10/2014 11:19 AM, Paul Rabahy wrote:
> You say UTXO commitments is "a strict reduction in security". If UTXO
> commitments were rolled in as a soft fork, I do not see any new attacks
> that could happen to a person trusting the committed UTXO + any
> remaining blocks to catch up to the head.
>
> I would imagine the soft fork to proceed similar to the following.
> 1. Miners begin including UTXO commitments.
> 2. Miners begin rejecting blocks with invalid UTXO commitments.
> 3. Miners begin rejecting blocks with no UTXO commitments.
>
> To start up a fresh client it would follow the following.
> 1. Sync headers.
> 2. Pick a committed UTXO that is deep enough to not get orphaned.
> 3. Sync blocks from commitment to head.
>
> I would argue that a client following this methodology is strictly more
> secure than SPV, and I don't see any attacks that make it less secure
> than a full client. It is obviously still susceptible to a 51% attack,
> but so is the traditional block chain. I also do not see any sybil
> attacks that are strengthened by this change because it is not modifying
> the networking code.
>
> I guess if the soft fork happened, then miners began to not include the
> UTXO commitment anymore, it would lower the overall network hash rate,
> but this would be self-harming to the miners so they have an incentive
> to not do it.
>
> Please let me know if I have missed something.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 18:32 ` Pieter Wuille
@ 2014-04-10 20:12 ` Tier Nolan
2014-04-10 20:29 ` Pieter Wuille
0 siblings, 1 reply; 21+ messages in thread
From: Tier Nolan @ 2014-04-10 20:12 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev, Paul Rabahy
[-- Attachment #1: Type: text/plain, Size: 1775 bytes --]
On Thu, Apr 10, 2014 at 7:32 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:
> If you trust hashrate for determining which UTXO set is valid, a 51%
> attack becomes worse in that you can be made to believe a version of
> history which is in fact invalid.
>
If there are invalidation proofs, then this isn't strictly true.
If you are connected to 10 nodes and only 1 is honest, it can send you the
proof that your main chain is invalid.
For bad scripts, it shows you the input transaction for the invalid input
along with the merkle path to prove it is in a previous block.
For double spends, it could show the transaction which spent the output.
Double spends are pretty much the same as trying to spend non-existent
outputs anyway.
If the UTXO set commit was actually a merkle tree, then all updates could
be included.
Blocks could have extra data with the proofs that the UTXO set is being
updated correctly.
To update the UTXO set, you need the paths for all spent inputs.
It puts a large load on miners to keep things working, since they have to
run a full node.
If they commit the data to the chain, then SPV nodes can do local checking.
One of them will find invalid blocks eventually (even if one of the other
miners don't).
>
> --
> Pieter
>
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
[-- Attachment #2: Type: text/html, Size: 2742 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 20:12 ` Tier Nolan
@ 2014-04-10 20:29 ` Pieter Wuille
0 siblings, 0 replies; 21+ messages in thread
From: Pieter Wuille @ 2014-04-10 20:29 UTC (permalink / raw)
To: Tier Nolan; +Cc: Bitcoin Dev, Paul Rabahy
On Thu, Apr 10, 2014 at 10:12 PM, Tier Nolan <tier.nolan@gmail•com> wrote:
> On Thu, Apr 10, 2014 at 7:32 PM, Pieter Wuille <pieter.wuille@gmail•com>
> wrote:
>>
>> If you trust hashrate for determining which UTXO set is valid, a 51%
>> attack becomes worse in that you can be made to believe a version of
>> history which is in fact invalid.
>
>
> If there are invalidation proofs, then this isn't strictly true.
I'm aware of fraud proofs, and they're a very cool idea. They allow
you to leverage some "herd immunity" in the system (assuming you'll be
told about invalid data you received without actually validating it).
However, they are certainly not the same thing as zero trust security
a fully validating node offers.
For example, a sybil attack that hides the actual best chain + fraud
proofs from you, plus being fed a chain that commits to an invalid
UTXO set.
There are many ideas that make attacks harder, and they're probably
good ideas to deploy, but there is little that achieves the security
of a full node. (well, perhaps a zero-knowledge proof of having run
the validation code against the claimed chain tip to produce the known
UTXO set...).
--
Pieter
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 16:59 ` Pieter Wuille
2014-04-10 17:06 ` Brian Hoffman
2014-04-10 18:19 ` Paul Rabahy
@ 2014-04-10 21:34 ` Jesus Cea
2014-04-10 22:15 ` Mark Friedenbach
2 siblings, 1 reply; 21+ messages in thread
From: Jesus Cea @ 2014-04-10 21:34 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1391 bytes --]
On 10/04/14 18:59, Pieter Wuille wrote:
> It's important to
> note that this is a strict reduction in security: we're now trusting
> that the longest chain (with most proof of work) commits to a valid
> UTXO set (at some point in the past).
AFAIK, current bitcoin code code already set blockchain checkpoints from
time to time. It is a garanteed that a longer chain starting before the
checkpoint is not going to be accepted suddently. See
<https://bitcointalk.org/index.php?topic=194078.0>.
Could be perfectly valid to store only unspend wallets before last
checkpoint, if during the blockchain download the node did all the checks.
Would be interesting, of course, to be able to verify "unspend wallet
accounting" having only that checkpoint data (the merkle tree can do
that, I guess). So you could detect a data corruption or manipulation in
your local harddisk.
--
Jesús Cea Avión _/_/ _/_/_/ _/_/_/
jcea@jcea•es - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/
Twitter: @jcea _/_/ _/_/ _/_/_/_/_/
jabber / xmpp:jcea@jabber•org _/_/ _/_/ _/_/ _/_/ _/_/
"Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/
"My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 538 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 21:34 ` Jesus Cea
@ 2014-04-10 22:15 ` Mark Friedenbach
2014-04-10 22:24 ` Jesus Cea
0 siblings, 1 reply; 21+ messages in thread
From: Mark Friedenbach @ 2014-04-10 22:15 UTC (permalink / raw)
To: bitcoin-development
Checkpoints will go away, eventually.
On 04/10/2014 02:34 PM, Jesus Cea wrote:
> On 10/04/14 18:59, Pieter Wuille wrote:
>> It's important to
>> note that this is a strict reduction in security: we're now trusting
>> that the longest chain (with most proof of work) commits to a valid
>> UTXO set (at some point in the past).
>
> AFAIK, current bitcoin code code already set blockchain checkpoints from
> time to time. It is a garanteed that a longer chain starting before the
> checkpoint is not going to be accepted suddently. See
> <https://bitcointalk.org/index.php?topic=194078.0>.
>
> Could be perfectly valid to store only unspend wallets before last
> checkpoint, if during the blockchain download the node did all the checks.
>
> Would be interesting, of course, to be able to verify "unspend wallet
> accounting" having only that checkpoint data (the merkle tree can do
> that, I guess). So you could detect a data corruption or manipulation in
> your local harddisk.
>
>
>
> ------------------------------------------------------------------------------
> Put Bad Developers to Shame
> Dominate Development with Jenkins Continuous Integration
> Continuously Automate Build, Test & Deployment
> Start a new project now. Try Jenkins in the cloud.
> http://p.sf.net/sfu/13600_Cloudbees
>
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 22:15 ` Mark Friedenbach
@ 2014-04-10 22:24 ` Jesus Cea
2014-04-10 22:33 ` Gregory Maxwell
0 siblings, 1 reply; 21+ messages in thread
From: Jesus Cea @ 2014-04-10 22:24 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 650 bytes --]
On 11/04/14 00:15, Mark Friedenbach wrote:
> Checkpoints will go away, eventually.
Why?. The points in the forum thread seem pretty sensible.
--
Jesús Cea Avión _/_/ _/_/_/ _/_/_/
jcea@jcea•es - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/
Twitter: @jcea _/_/ _/_/ _/_/_/_/_/
jabber / xmpp:jcea@jabber•org _/_/ _/_/ _/_/ _/_/ _/_/
"Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/
"My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 538 bytes --]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Bitcoin-development] Chain pruning
2014-04-10 22:24 ` Jesus Cea
@ 2014-04-10 22:33 ` Gregory Maxwell
0 siblings, 0 replies; 21+ messages in thread
From: Gregory Maxwell @ 2014-04-10 22:33 UTC (permalink / raw)
To: Jesus Cea; +Cc: Bitcoin Development
On Thu, Apr 10, 2014 at 3:24 PM, Jesus Cea <jcea@jcea•es> wrote:
> On 11/04/14 00:15, Mark Friedenbach wrote:
>> Checkpoints will go away, eventually.
> Why?. The points in the forum thread seem pretty sensible.
Because with headers first synchronization the major problems that
they solve— e.g. block flooding DOS attacks, weak chain isolation, and
checking shortcutting can be addressed in other more efficient ways
that don't result in putting trust in third parties.
They also cause really severe confusion about the security model.
Instead you can embed in software knoweldge that the longest chain is
"at least this long" to prevent isolation attacks, which is a lot
simpler and less trusting. You can also do randomized validation of
the deeply burried old history for performance, instead of constantly
depending on 'trusted parties' to update software or it gets slower
over time, and locally save your own validation fingerprints so if you
need to reinitilize data you can remember what you've check so far by
hash.
^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2014-04-10 22:33 UTC | newest]
Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-04-10 11:37 [Bitcoin-development] Chain pruning Mike Hearn
2014-04-10 11:57 ` Wladimir
2014-04-10 12:10 ` Gregory Maxwell
2014-04-10 14:19 ` Wladimir
2014-04-10 16:23 ` Brian Hoffman
2014-04-10 16:28 ` Mike Hearn
2014-04-10 16:47 ` Brian Hoffman
2014-04-10 16:54 ` Ricardo Filipe
2014-04-10 16:56 ` Brian Hoffman
2014-04-10 16:59 ` Pieter Wuille
2014-04-10 17:06 ` Brian Hoffman
2014-04-10 18:19 ` Paul Rabahy
2014-04-10 18:32 ` Pieter Wuille
2014-04-10 20:12 ` Tier Nolan
2014-04-10 20:29 ` Pieter Wuille
2014-04-10 19:36 ` Mark Friedenbach
2014-04-10 21:34 ` Jesus Cea
2014-04-10 22:15 ` Mark Friedenbach
2014-04-10 22:24 ` Jesus Cea
2014-04-10 22:33 ` Gregory Maxwell
2014-04-10 16:52 ` Ricardo Filipe
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox