Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
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 signature.asc Description: Digital signature -- 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
[Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
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 -- 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
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
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 signature.asc Description: Digital signature -- 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
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
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 p...@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
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite nodes
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 Toddp...@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
