Re: [Bitcoin-development] Scaling Bitcoin with Subchains
On Tue, Jun 16, 2015 at 6:17 PM, Peter Todd p...@petertodd.org wrote: Merge-mined sidechains are not a scaling solution any more than SPV is a scaling solution because they don't solve the scaling problem for miners. Some kind of treechain like sidechain / subchains where what part of the tree miners can mine is constrained to preserve fairness could be both a scaling solution, and decentralized, but no-one has come up with a solid design yet that's ready for production. (my treechains don't qualify for transactions yet; maybe for other proof-of-publication uses) Well doesn't my proposal solve the miner decentralization problem. Only the direct parent and children chains are merge mined. To be more clear, let the top chain to have level 1. Each chain that is a child of a chain of level n has level n+1. For any chain C, a block is accepted if the hash of its header has an appropriate number of trailing zeros (as usual). It can also be accepted with special transactions as I will explain. Let C be a chain of level n. Let C0,C1,,C9 be its children (each of level n+1). For any i in {0,1,...,9}, any solution to the mining problem of C can be inserted as a special transaction inside Ci and this enables the block to be accepted in Ci (so C and C0,C1,...,C9 are merge mined. But, for any i in {0,1,...,9} and any j in {0,1,...,9}, any solution to the mining problem of C cannot be inserted as a special transaction inside of child Cij of Ci. So that means all of the chains are not merge mined, only localised parts, right? By the way, we can eventually get rid of the block size 1 MB limit by requiring more than just the header to be hashed, but that can be done in the future as soft fork with sidechains, and is a side topic. -- PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647 -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
On Mon, Jun 15, 2015 at 01:15:14PM -0400, Jeff Garzik wrote: On Mon, Jun 15, 2015 at 1:09 PM, Pieter Wuille pieter.wui...@gmail.com wrote: It's simple: either you care about validation, and you must validate everything, or you don't, and you don't validate anything. Sidechains do not offer you a useful compromise here, as well as adding huge delays and conplexity. As noted to Adam last night - although I agree it adds complexity - side chains are one solution that will indeed help with scaling long term. Similar to the graph you see with git repos and merges, having aggregation chains that arbitrarily fork and then rejoin the main chain are both feasible and useful. That code future is a ways away from production, so doesn't help us here. Still, let's not dismiss it as a solution either. To be clear, it depends on what kind of sidechain. My off-chain transaction notions are federated sidechains with an economic incentive to not commit fraud using fidelity bonds; they were definitely proposed as a scaling solution. Merge-mined sidechains are not a scaling solution any more than SPV is a scaling solution because they don't solve the scaling problem for miners. Some kind of treechain like sidechain / subchains where what part of the tree miners can mine is constrained to preserve fairness could be both a scaling solution, and decentralized, but no-one has come up with a solid design yet that's ready for production. (my treechains don't qualify for transactions yet; maybe for other proof-of-publication uses) Keep in mind that other than preserving mining decentralization/resisting censorship, we've known how to scale up blockchains for ages w/ things like (U)TXO commitments and fraud proofs. -- 'peter'[:-1]@petertodd.org 127ab1d576dc851f374424f1269c4700ccaba2c42d97e778 signature.asc Description: Digital signature -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
Pieter, Am 13.06.2015 um 16:39 schrieb Pieter Wuille: We can reasonably assume that different people's wallet will tend to be distributed uniformly over several sidechains to hold their transactions (if they're not, there is no scaling benefit anyway...). That means that for an average transaction, you will need a cross-chain transfer in order to get the money to the recipient (as their wallet will usually be associated to a chain that is different from your own). I think we should set the right incentives to invalidate these assumptions. If the fees as well as the security guarantees on the main chain are highest and fees are dropping with the distance from the main chain on each level of side chains, wouldn't communities with many internal transactions create their own side chain with low fees? I'd expect geographic as well as virtual communities to be forming enjoying cheap fees on their 'local' chains and expensive but comparabily rare 'long distance' fees. One would expect geographic chains (e.g. continents) as well as virtual ones (e.g. the Open Bazaar users' chain) to form. To save fees, a typical user would maintain a wallet in each of her communities which are loaded and drained with rare expensive transacations, whereas daily business with many transactions is done cheaply within each community chain. So, indeed, I would argue that side chains equipped with the right cost incentives for cross-chain transactions would lead to a scalable and efficiently self-organizing network of side chains. best regards, Martin -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
On Wed, May 20, 2015 at 4:55 AM, Andrew onelinepr...@gmail.com wrote: Hi I briefly mentioned something about this on the bitcoin-dev IRC room. In general, it seems experts (like sipa i.e. Pieter) are against using sidechains as a way of scaling. As I only have a high level understanding of the Bitcoin protocol, I cannot be sure if what I want to do is actually defined as a side chain, but let me just propose it, and please let me know whether it can work, and if not why not (I'm not scared of digging into more technical resources in order to fully understand). I do have a good academic/practical background for Bitcoin, and I'm ready to contribute code if needed (one of my contributions includes a paper wallet creator written in C). In your proposal, transactions go to a chain based the addresses involved. We can reasonably assume that different people's wallet will tend to be distributed uniformly over several sidechains to hold their transactions (if they're not, there is no scaling benefit anyway...). That means that for an average transaction, you will need a cross-chain transfer in order to get the money to the recipient (as their wallet will usually be associated to a chain that is different from your own). Either you use an atomic swap (which actually means you end up briefly with coins in the destination chain, and require multiple transactions and a medium delay), or you use the 2way peg transfer mechanism (which is very slow, and reduces the security the recipient has to SPV). Whatever you do, the result will be that most transactions are: * Slower (a bit, or a lot, depending on what mechanism you use). * More complex, with more failure modes. * Require more and larger transactions (causing a total net extra load on all verifiers together). And either: * Less secure (because you rely on a third party to do an atomic swap with, or because of the 2 way peg transfer mechanism which has SPV security) * Doesn't offer any scaling benefit (because the recipient needs to fully validate both his own and the receiver chain). In short, you have not added any scaling at all, or reduced the security of the system significantly, as well as made it significantly less convenient to use. So no, sidechains are not a direct means for solving any of the scaling problems Bitcoin has. What they offer is a mechanism for easier experimentation, so that new technology can be built and tested without needing to introduce a new currency first (with the related speculative and network effect problems). That experimentation could eventually lead us to discover mechanisms for better scaling, or for more scalability/security tradeoffs (see for example the Witness Segregation that Elements Alpha has). -- Pieter -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
First of all, I added more info to bitcointalk.org: https://bitcointalk.org/index.php?topic=1083345.0 On Sat, Jun 13, 2015 at 2:39 PM, Pieter Wuille pieter.wui...@gmail.com wrote: In your proposal, transactions go to a chain based the addresses involved. We can reasonably assume that different people's wallet will tend to be distributed uniformly over several sidechains to hold their transactions (if they're not, there is no scaling benefit anyway...). That means that for an average transaction, you will need a cross-chain transfer in order to get the money to the recipient (as their wallet will usually be associated to a chain that is different from your own). Either you use an atomic swap (which actually means you end up briefly with coins in the destination chain, and require multiple transactions and a medium delay), or you use the 2way peg transfer mechanism (which is very slow, and reduces the security the recipient has to SPV). Whatever you do, the result will be that most transactions are: * Slower (a bit, or a lot, depending on what mechanism you use). * More complex, with more failure modes. * Require more and larger transactions (causing a total net extra load on all verifiers together). And either: * Less secure (because you rely on a third party to do an atomic swap with, or because of the 2 way peg transfer mechanism which has SPV security) * Doesn't offer any scaling benefit (because the recipient needs to fully validate both his own and the receiver chain). In short, you have not added any scaling at all, or reduced the security of the system significantly, as well as made it significantly less convenient to use. So no, sidechains are not a direct means for solving any of the scaling problems Bitcoin has. What they offer is a mechanism for easier experimentation, so that new technology can be built and tested without needing to introduce a new currency first (with the related speculative and network effect problems). That experimentation could eventually lead us to discover mechanisms for better scaling, or for more scalability/security tradeoffs (see for example the Witness Segregation that Elements Alpha has). Thanks Pieter for your reply. The chain the transaction goes to does not have to be based on the address (there can be a way for the protocol to choose), but ya, the address scheme can be a good default. As I said, there will be an incentive for empty chains to fill up since they will require less fees (so the scaling benefit isn't dependent on a uniform distribution of addresses). The rule I mentioned is that at most 2 different chains can be involved in one transaction. From a chain to itself is easy. From a parent or grandparent chain to its child or grandchild chain, is also easy since the child/grandchild always trusts its parent/grandparent. From a child/grandchild to parent/grandparent, is also easy (no delay) since the parent/grandparent will commit to its children (which recursively commit to their children). As mentioned I am just doing a form of block extensions as Adam Back described; the chains are not independent. From one chain to another chain at the same level (sibling chains), the transaction is recorded on both sibling chains (yes there is some duplication but this is limited by requiring at most 2 sibling chains participating in a transaction). They both have to be consistent and this will be ensured by the miners of their parent chain (those miners will commit to their blocks). So no, I don't see how it's slower, except that there needs to be some delay for communication between children/grandchildren and parents/grandparents, of time O(log n) where n is the number of levels. Even a small number of levels corresponds to a large transaction volume: n = 5 corresponds to the equivalent of 625 MB blocks. Security-wise, it is true that the top level chain will likely have higher security (more hash power), but at least you can fine tune the fees you pay according to what level of security is acceptable to you, and as Bitcoin grows, level 2,3,4 chains can be regarded as almost as secure as the level 1 chain, since there will still be a lot of hash power on them. And anyone can run a full node on their chains of interest, so there is no SPV level security here, it is full level security. Transactions are not significantly different. Miners just have to deal with child chains, but if there is a scaling benefit, we should not be scared of complexity. It is probably the simplest way I can think of scaling. The recipient will validate their own chain fully and will just need the headers of the relevant parent chains to see whether an output from the other chain involved in a transaction is really valid. They can also get the headers of the sibling chain involved in the transaction if they want to validate the work of the miners on these parent chains. They don't need the full blocks of the parent and sibling chains involved
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
On Wed, May 27, 2015 at 9:16 PM, Andrew onelinepr...@gmail.com wrote: You should also keep in mind the big picture when it comes to decentralization. If the hard drives (or tapes) can only be produced by a small number of large companies like Western Digital or Seagate, then you can't really count those for a decentralized system. A truly decentralized system would have the devices needed to participate in (and verify) the system be easily created by a regular user of the system without relying on a central power. So for example, the hard drives needed to store the bitcoin transaction records should be able to be produced at a regular person's home on a 3D printer starting from just the raw materials. I don't know how close we are to this ideal, but just pointing out that it needs to be considered. This is also a reason why I like that Bitcoin uses the simple SHA sum for mining instead of a more complicated function such as scrypt. It makes it easier for small scale entities to understand and to produce the ASIC miners. I am a huge fan of do-it-yourself at-home ASIC manufacturing. The original 4004 and earlier devices are within the scope of what could be accomplished in a home environment. The homecmos project is an interesting glimpse at these possibilities. Relevant-scale mining will most likely never be an option for home manufacturing, but bitcoin wallets and other devices can definitely be etched by hand or using maskless projector lithography. Here's what the homecmos group was up to: https://code.google.com/p/homecmos/ http://homecmos.drawersteak.com/wiki/ http://diyhpl.us/~bryan/papers2/optics/photolithography/DIY%20fabrication%20of%20microstructures%20by%20projection%20photolithography.pdf LCD projection lithography: http://diyhpl.us/~bryan/papers2/optics/photolithography/Cell%20micropatterning%20using%20photopolymerization%20with%20a%20liquid%20crystal%20device%20(LCD)%20commercial%20projector%20-%20Itoga%20-%202003.pdf http://diyhpl.us/~bryan/papers2/optics/photolithography/Development%20of%20microfabrication%20technology%20with%20maskless%20photolithography%20device%20using%20LCD%20projector%20-%20Itoga%20-%202010.pdf http://diyhpl.us/~bryan/papers2/optics/photolithography/Second-generation%20maskless%20photolithography%20device%20for%20surface%20micropatterning%20and%20microfluidic%20channel%20fabrication%20(using%20an%20LCD%20projector).pdf DMD lithography: http://diyhpl.us/~bryan/papers2/optics/photolithography/Maskless%20microscopic%20lithography%20through%20shaping%20ultraviolet%20(UV)%20laser%20with%20digital%20micromirror%20device%20(DMD)%20-%202013.pdf http://diyhpl.us/~bryan/papers2/optics/photolithography/A%20maskless%20photolithographic%20prototyping%20system%20using%20a%20low-cost%20consumer%20projector%20and%20a%20microscope.pdf There's actually a method of doing this with conventional camera roll film: https://groups.google.com/d/msg/diybio/5hpQXZ6hFKY/baGNfY_-Wx8J - Bryan http://heybryan.org/ 1 512 203 0507 -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
Hi All I discussed this idea with some other core developers (on IRC) and they generally seem to agree that it can be done. It may be equivalent to an idea called blockchain extensions but when I looked it up on bitcointalk.org I didn't see exactly the same proposal I am making. One person suggested I should replace the address to chain function with a protocol addition that allows one to specify the target chain. Yes, this can also be done without changing the key properties. One person said that the main problem is that I am not saying anything specific, and I should address the sidechain problems written about in the sidechains paper. Well, actually, there is one quite specific thing I am saying, in case you didn't notice: With this system, the network can achieve effectively 5^{n-1} MB blocks with each participant only storing n MB blocks. So for example, you can have effectively a block size of 625 MB (= 5^4) with each participant only storing 3 MB blocks; or 3.125 GB blocks with each participant only storing 4 MB blocks. For these calculations, I am assuming that only two separate sibling chains are involved in a transaction, so there is a duplication effect that divides in two the effective size of a given level of blocks (that's why it's 5 instead of 10 as would be without duplication). If you want to involve multiple sibling chains in one transaction, you can effectively achieve this by performing multiple transactions involving 2 of the multiple chains. Yes, the fees would be higher since you have more transactions to make, but it is reasonable to expect more fees for more complicated transactions, and I don't think it will result in people clustering on one chain (people who do these kinds of transactions would probably track multiple chain paths). As for the problems with sidechains, I think they would be eliminated due to the child-parent dependence I specified. I also propose the following additional rule: In case of conflict between parent and child chains (due to reorganizations), the child chain must choose the consensus of the parent chain. Also, for transferring from child to parent, the miners on the parent have the final say, but to make it more clear, they can use the relative difference of difficulty between their chain and the child chain to decide how many blocks deep a transaction in the child chain has to be to be accepted in the parent chain. Gavin was the only one who disapproved of this, but I am not sure if he actually read the whole thing that I wrote. He said something along the line of the outputs will span the subchains and when I asked for an explanation he just said that I need to learn more about things. I stated to him my willingness to learn, but have yet to get a response from him. Mike: You should also keep in mind the big picture when it comes to decentralization. If the hard drives (or tapes) can only be produced by a small number of large companies like Western Digital or Seagate, then you can't really count those for a decentralized system. A truly decentralized system would have the devices needed to participate in (and verify) the system be easily created by a regular user of the system without relying on a central power. So for example, the hard drives needed to store the bitcoin transaction records should be able to be produced at a regular person's home on a 3D printer starting from just the raw materials. I don't know how close we are to this ideal, but just pointing out that it needs to be considered. This is also a reason why I like that Bitcoin uses the simple SHA sum for mining instead of a more complicated function such as scrypt. It makes it easier for small scale entities to understand and to produce the ASIC miners. Also, in addition to the centralization of storage device manufacturing, one should also consider what would happen if everyone wanted to have a 5 TB drive at home. What would happen to the price of hard drives? Keep in mind also that the human population is likely increasing, so there are less real resources per person... Yes maybe in the future we can solve these problems, but we still haven't, so let's not assume they are solved. Also, you mentioned sharing the costs of a hard drive with other people. Do you mean trusting that others did not compromise the hard drives? If you want you can do so, but not every participant should be forced to trust others, a point I think I made already. And finally, this is all a discussion on the costs of running a Bitcoin node. Bitcoin is not all that people will use hard drives and computers for; we need to leave room for other things. So Mike, I have a question for you. Are you supporting a block size increase partly due to philosophical reasons (i.e. you believe that regular people shouldn't have such strong freedom as I want) or do you just not care so much about the long term future and you just want to get your Bitcoin related projects up and running with minimal complications? Or is
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
Hi Andrew, Your belief that Bitcoin has to be constrained by the belief that hardware will never improve is extremist, but regardless, your concerns are easy to assuage: there is no requirement that the block chain be stored on hard disks. As you note yourself the block chain is used for building/auditing the ledger. Random access to it is not required, if all you care about is running a full node. Luckily this makes it a great fit for tape backup. Technology that can store 185 terabytes *per cartridge* has already been developed: http://www.itworld.com/article/2693369/sony-develops-tape-tech-that-could-lead-to-185-tb-cartridges.html As you could certainly share costs of a block chain archive with other people, the cost would not be a major concern even today. And it's virtually guaranteed that humanity will not hit a storage technology wall in 2015. If your computer is compromised then all bets are off. Validating the chain on a compromised host is meaningless. -- One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development