* [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
@ 2012-06-17 18:39 Alan Reiner
2012-06-17 19:05 ` Peter Todd
0 siblings, 1 reply; 5+ messages in thread
From: Alan Reiner @ 2012-06-17 18:39 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1483 bytes --]
All,
With the flurry of discussion about blockchain compression, I thought it
was time to put forward my final, most-advanced idea, into a single,
well-thought-out, *illustrated*, forum post. Please check it out:
https://bitcointalk.org/index.php?topic=88208.0
This is a huge undertaking, but it has some pretty huge benefits. And
it's actually feasible because it can be implemented without disrupting
the main network. I'm sure there's lots of issues with it, but I'm
putting it out there to see how it might be improved and actually executed.
----
*Summary:
*/Use a special tree data structure to organize all unspent-TxOuts on
the network, and use the root of this tree to communicate its
"signature" between nodes. The leaves of this tree actually correspond
to addresses/scripts, and the data at the leaf is actually a root of the
unspent-TxOut list for that address/script. To maintain security of the
tree signatures, it will be included in the header of an alternate
blockchain, which will be secured by merged mining.
This provides the same compression as the simpler unspent-TxOut merkle
tree, but also gives nodes a way to download just the unspent-TxOut list
for each address in their wallet, and verify that list directly against
the blockheaders. Therefore, even lightweight nodes can get full
address information, from any untrusted peer, and with only a tiny
amount of downloaded data (a few kB). /*
*----
Alright, tear it up!
-Alan
[-- Attachment #2: Type: text/html, Size: 2206 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
2012-06-17 18:39 [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes Alan Reiner
@ 2012-06-17 19:05 ` Peter Todd
2012-06-17 22:46 ` Alberto Torres
0 siblings, 1 reply; 5+ messages in thread
From: Peter Todd @ 2012-06-17 19:05 UTC (permalink / raw)
To: Alan Reiner; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2631 bytes --]
On Sun, Jun 17, 2012 at 02:39:28PM -0400, Alan Reiner wrote:
> All,
>
> With the flurry of discussion about blockchain compression, I
> thought it was time to put forward my final, most-advanced idea,
> into a single, well-thought-out, *illustrated*, forum post.
> Please check it out: https://bitcointalk.org/index.php?topic=88208.0
>
> This is a huge undertaking, but it has some pretty huge benefits.
> And it's actually feasible because it can be implemented without
> disrupting the main network. I'm sure there's lots of issues with
> it, but I'm putting it out there to see how it might be improved and
> actually executed.
>
> ----
> *Summary:
>
> */Use a special tree data structure to organize all unspent-TxOuts
> on the network, and use the root of this tree to communicate its
> "signature" between nodes. The leaves of this tree actually
> correspond to addresses/scripts, and the data at the leaf is
> actually a root of the unspent-TxOut list for that address/script.
> To maintain security of the tree signatures, it will be included in
> the header of an alternate blockchain, which will be secured by
> merged mining.
>
> This provides the same compression as the simpler unspent-TxOut
> merkle tree, but also gives nodes a way to download just the
> unspent-TxOut list for each address in their wallet, and verify that
> list directly against the blockheaders. Therefore, even lightweight
> nodes can get full address information, from any untrusted peer, and
> with only a tiny amount of downloaded data (a few kB). /*
How are you going to prevent people from delibrately unbalancing the
tree with addresses with chosen hashes?
One idea that comes to mind, which unfortunately would make for a
pseudo-network rule, is to simply say that any *new* address whose hash
happens to be deeper in the tree than, say, 10*log(n), indicating it was
probably chosen to be unbalanced, gets discarded. The "new address" part
of the rule would be required, or else you could use the rule to get
other people's addresses discarded.
Having said that, such a rule just means that anyone playing games will
find they can't spend *their* money, and only with pruning clients.
Unrelated people will not be effected. The coins can also always be
spent with a non-pruning client to an acceptable address, which can
later re-spend on a pruning client.
It also comes to mind is that with the popularity of firstbits it may be
a good idea to use a comparison function that works last bit first...
It's merkles all the way down...
--
'peter'[:-1]@petertodd.org
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
2012-06-17 19:05 ` Peter Todd
@ 2012-06-17 22:46 ` Alberto Torres
2012-06-17 23:17 ` Alan Reiner
2012-06-18 10:14 ` Peter Todd
0 siblings, 2 replies; 5+ messages in thread
From: Alberto Torres @ 2012-06-17 22:46 UTC (permalink / raw)
To: bitcoin-development
Hi,
I did describe a very similar thing back in January (also illustrated,
and, if I'm not mistaken, more simple and efficient to recalculate),
and I wanted to do a prototype, but I have been very busy with other
projects since then.
https://en.bitcoin.it/wiki/User:DiThi/MTUT
I just saw Gavin left a comment in the talk page, I'm sorry I haven't
seen it earlier.
I think armory is the perfect client to implement such an idea. I sort
of waited it to be able to run in my laptop with 2 GB of RAM before
being sucked into other projects. I even lost track of its
development.
I hope this gets developed. I will be able to help after summer if
this is still not done.
DiThi
P.S: Sorry Peter, I've sent you the message privately by mistake.
Also, I don't quite understand your concern of "unbalancing" the tree.
2012/6/17 Peter Todd <pete@petertodd•org>:
> On Sun, Jun 17, 2012 at 02:39:28PM -0400, Alan Reiner wrote:
>> All,
>>
>> With the flurry of discussion about blockchain compression, I
>> thought it was time to put forward my final, most-advanced idea,
>> into a single, well-thought-out, *illustrated*, forum post.
>> Please check it out: https://bitcointalk.org/index.php?topic=88208.0
>>
>> This is a huge undertaking, but it has some pretty huge benefits.
>> And it's actually feasible because it can be implemented without
>> disrupting the main network. I'm sure there's lots of issues with
>> it, but I'm putting it out there to see how it might be improved and
>> actually executed.
>>
>> ----
>> *Summary:
>>
>> */Use a special tree data structure to organize all unspent-TxOuts
>> on the network, and use the root of this tree to communicate its
>> "signature" between nodes. The leaves of this tree actually
>> correspond to addresses/scripts, and the data at the leaf is
>> actually a root of the unspent-TxOut list for that address/script.
>> To maintain security of the tree signatures, it will be included in
>> the header of an alternate blockchain, which will be secured by
>> merged mining.
>>
>> This provides the same compression as the simpler unspent-TxOut
>> merkle tree, but also gives nodes a way to download just the
>> unspent-TxOut list for each address in their wallet, and verify that
>> list directly against the blockheaders. Therefore, even lightweight
>> nodes can get full address information, from any untrusted peer, and
>> with only a tiny amount of downloaded data (a few kB). /*
>
> How are you going to prevent people from delibrately unbalancing the
> tree with addresses with chosen hashes?
>
> One idea that comes to mind, which unfortunately would make for a
> pseudo-network rule, is to simply say that any *new* address whose hash
> happens to be deeper in the tree than, say, 10*log(n), indicating it was
> probably chosen to be unbalanced, gets discarded. The "new address" part
> of the rule would be required, or else you could use the rule to get
> other people's addresses discarded.
>
> Having said that, such a rule just means that anyone playing games will
> find they can't spend *their* money, and only with pruning clients.
> Unrelated people will not be effected. The coins can also always be
> spent with a non-pruning client to an acceptable address, which can
> later re-spend on a pruning client.
>
>
> It also comes to mind is that with the popularity of firstbits it may be
> a good idea to use a comparison function that works last bit first...
>
>
> It's merkles all the way down...
>
> --
> 'peter'[:-1]@petertodd.org
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
2012-06-17 22:46 ` Alberto Torres
@ 2012-06-17 23:17 ` Alan Reiner
2012-06-18 10:14 ` Peter Todd
1 sibling, 0 replies; 5+ messages in thread
From: Alan Reiner @ 2012-06-17 23:17 UTC (permalink / raw)
To: bitcoin-development
Hi Alberto,
Your thread was part of the inspiration for the idea that I proposed.
But as I read it more, I see that I originally misunderstood it
(mistaking it for a simpler unspent-TxOut tree idea). Even after
reading it, I'm not entirely clear how your proposal would work, but I
see that you proposed something very similar. I just want to clarify
that there are two, major orthogonal pieces to both proposals:
(1) The method for creating unspent-TxOut-tree roots/fingerprints for
verification
(2) Using an alternate blockchain to maintain and distribute those
fingerprints
There are multiple ways to do both of those. You proposed a different
tree structure (which I haven't entirely figured out, yet), and putting
those "fingerprints" in the main chain header.
In my proposal, (2) is to avoid inducing a blockchain fork, or even
changing the protocol at all. By using a separate blockchain, it can be
done non-disruptively, and could even be thrown out and re-worked if we
were to find an issue with it later. The availability of merged mining
makes it possible to get [almost] the same security as changing the
protocol, but without the disruption of hard-forking. (I expect that if
there's not too much computational overhead and the software is already
written, most miners would sign on)
I'll read into your page a little more. I don't want to take credit
away from you, since you clearly had a comparable idea developed long
before me :)
-Alan
On 06/17/2012 06:46 PM, Alberto Torres wrote:
> Hi,
>
> I did describe a very similar thing back in January (also illustrated,
> and, if I'm not mistaken, more simple and efficient to recalculate),
> and I wanted to do a prototype, but I have been very busy with other
> projects since then.
>
> https://en.bitcoin.it/wiki/User:DiThi/MTUT
>
> I just saw Gavin left a comment in the talk page, I'm sorry I haven't
> seen it earlier.
>
> I think armory is the perfect client to implement such an idea. I sort
> of waited it to be able to run in my laptop with 2 GB of RAM before
> being sucked into other projects. I even lost track of its
> development.
>
> I hope this gets developed. I will be able to help after summer if
> this is still not done.
>
> DiThi
>
> P.S: Sorry Peter, I've sent you the message privately by mistake.
> Also, I don't quite understand your concern of "unbalancing" the tree.
>
> 2012/6/17 Peter Todd<pete@petertodd•org>:
>> On Sun, Jun 17, 2012 at 02:39:28PM -0400, Alan Reiner wrote:
>>> All,
>>>
>>> With the flurry of discussion about blockchain compression, I
>>> thought it was time to put forward my final, most-advanced idea,
>>> into a single, well-thought-out, *illustrated*, forum post.
>>> Please check it out: https://bitcointalk.org/index.php?topic=88208.0
>>>
>>> This is a huge undertaking, but it has some pretty huge benefits.
>>> And it's actually feasible because it can be implemented without
>>> disrupting the main network. I'm sure there's lots of issues with
>>> it, but I'm putting it out there to see how it might be improved and
>>> actually executed.
>>>
>>> ----
>>> *Summary:
>>>
>>> */Use a special tree data structure to organize all unspent-TxOuts
>>> on the network, and use the root of this tree to communicate its
>>> "signature" between nodes. The leaves of this tree actually
>>> correspond to addresses/scripts, and the data at the leaf is
>>> actually a root of the unspent-TxOut list for that address/script.
>>> To maintain security of the tree signatures, it will be included in
>>> the header of an alternate blockchain, which will be secured by
>>> merged mining.
>>>
>>> This provides the same compression as the simpler unspent-TxOut
>>> merkle tree, but also gives nodes a way to download just the
>>> unspent-TxOut list for each address in their wallet, and verify that
>>> list directly against the blockheaders. Therefore, even lightweight
>>> nodes can get full address information, from any untrusted peer, and
>>> with only a tiny amount of downloaded data (a few kB). /*
>> How are you going to prevent people from delibrately unbalancing the
>> tree with addresses with chosen hashes?
>>
>> One idea that comes to mind, which unfortunately would make for a
>> pseudo-network rule, is to simply say that any *new* address whose hash
>> happens to be deeper in the tree than, say, 10*log(n), indicating it was
>> probably chosen to be unbalanced, gets discarded. The "new address" part
>> of the rule would be required, or else you could use the rule to get
>> other people's addresses discarded.
>>
>> Having said that, such a rule just means that anyone playing games will
>> find they can't spend *their* money, and only with pruning clients.
>> Unrelated people will not be effected. The coins can also always be
>> spent with a non-pruning client to an acceptable address, which can
>> later re-spend on a pruning client.
>>
>>
>> It also comes to mind is that with the popularity of firstbits it may be
>> a good idea to use a comparison function that works last bit first...
>>
>>
>> It's merkles all the way down...
>>
>> --
>> 'peter'[:-1]@petertodd.org
>>
>> ------------------------------------------------------------------------------
>> Live Security Virtual Conference
>> Exclusive live event will cover all the ways today's security and
>> threat landscape has changed and how IT managers can respond. Discussions
>> will include endpoint security, mobile security and the latest in malware
>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists•sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
2012-06-17 22:46 ` Alberto Torres
2012-06-17 23:17 ` Alan Reiner
@ 2012-06-18 10:14 ` Peter Todd
1 sibling, 0 replies; 5+ messages in thread
From: Peter Todd @ 2012-06-18 10:14 UTC (permalink / raw)
To: Alberto Torres; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3501 bytes --]
On Mon, Jun 18, 2012 at 12:46:47AM +0200, Alberto Torres wrote:
> Hi,
>
> I did describe a very similar thing back in January (also illustrated,
> and, if I'm not mistaken, more simple and efficient to recalculate),
> and I wanted to do a prototype, but I have been very busy with other
> projects since then.
>
> https://en.bitcoin.it/wiki/User:DiThi/MTUT
>
> I just saw Gavin left a comment in the talk page, I'm sorry I haven't
> seen it earlier.
>
> I think armory is the perfect client to implement such an idea. I sort
> of waited it to be able to run in my laptop with 2 GB of RAM before
> being sucked into other projects. I even lost track of its
> development.
I strongly disagree on that point. What you're proposing needs miner
support to work, and miners generally run either the satoshi client as a
daemon, or some other custom code. Implementing the idea in armory
doesn't give those miners a nice upgrade path.
That said, *using* the hash tree is something that can be implemented in
any client, but a lot of the code will be shared between calculating it
and using it anyway, so again implementing in the satoshi client makes
sense.
> I hope this gets developed. I will be able to help after summer if
> this is still not done.
>
> DiThi
>
> P.S: Sorry Peter, I've sent you the message privately by mistake.
> Also, I don't quite understand your concern of "unbalancing" the tree.
Lets suppose we're trying to make a tree consisting of real numbers:
/\
/ \
* \
/ \ \
/ \ \
* * *
/ \ / \ / \
1 2 3 4 5 6
If the numbers are evenly distributed, as will happen with hashes of
arbitrary data, any number will be at most log(n) steps away from the
head of the tree.
Suppose though some malicious actor adds the following numbers to that
tree: 3.001 3.002 3.003
/\
/ \
* \
/ \ \
/ \ \
* * *
/ \ / \ / \
1 2 * 4 5 6
/ \
| \
* *
/ \ / \
0 1 2 3 <- (3.000 to 3.003)
Ooops, the tree suddenly became a lot higher, with an associated
decrease in retrieval performance and an increase in memory usage.
Of course the exact details depend on what rules there are for
constructing the tree, but essentially the attacker can either force the
a big increase in the depth of the tree, or a large number of vertexes
to be re-organizationed to create the tree, or both.
Now, to be exact, since the key of each vertex is a transaction hash,
this malicious actor will need to brute chosen prefix hash collisions,
but this is bitcoin: the whole system is about efficiently brute forcing
chosen prefix hash collisions. Besides, you would only need something
like k*n collisions to product an n increase in tree depth, with some
small k.
My solution was to simply state that vertexes that happened to cause the
tree to be unbalanced would be discarded, and set the depth of inbalance
such that this would be extremely unlikely to happen by accident. I'd
rather see someone come up with something better though.
Another naive option would be to hash each vertex key (the transaction
hash) with a nonce known only to the creator of that particular merkle
tree, but then the whole tree has to be recreatred from scratch each
time, which is worse than the problem... Interestingly in a
*non-distributed* system this idea is actually quite feasible feasible,
as the nonce could be kept secret.
--
'peter'[:-1]@petertodd.org
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2012-06-18 10:14 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-06-17 18:39 [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes Alan Reiner
2012-06-17 19:05 ` Peter Todd
2012-06-17 22:46 ` Alberto Torres
2012-06-17 23:17 ` Alan Reiner
2012-06-18 10:14 ` Peter Todd
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox