Re: [Bitcoin-development] Scaling Bitcoin with Subchains
Actually, I have to think about this merge-mining thing a bit more. I'm
starting to think it's better to do without merge-mining at all. As I
explained in the forum post, the parent will put the hashes of its children
headers as transactions inside its blocks. Thus parents will have an
incentive to validate the children not by merge mining, but by collecting
fees from the children for putting those transactions inside (fees that can
be spent at the children chains). So, ya no merge mining needed for my
proposal. But I will think about it a bit more :)
On Tue, Jun 16, 2015 at 6:43 PM, Andrew wrote:
>
>
> On Tue, Jun 16, 2015 at 6:17 PM, Peter Todd 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
>
--
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 Tue, Jun 16, 2015 at 6:17 PM, Peter Todd 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 > 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
Let me ask a simpler question. How do you prove the state of the UTXO database corresponding to your wallet? With my subchain method, all the addresses in a wallet can be constrained to a path of subchains, so the proof is O(log n). Yes, I know some people will say that it is not really a proof because I didn't verify the transactions involving sibling chains outside my path of chains. But the protocol is "parent chain always decides in case of conflict". And the parent chains will have an incentive to be careful with what child blocks they commit to as they will be merge mining the (direct) child chains. Yes, the parents can make a mistake with some really deep children chain transactions, but the deeper you go, the less value the transactions, and the less important. Also, the children of the parents are parents themselves so they will have incentive to be careful with what child chains they commit to. So recursively, the system takes care of itself. I challenge anyone to come up with a <= O(log n) proof that each address (output) they have in their wallet really has the balance they think it has. If someone can do this, then maybe I will drop this idea. Actually, rusty asked this on #bitcoin-wizards last night and no one was able to answer it. On Mon, Jun 15, 2015 at 6:00 PM, Andrew wrote: > Pieter: I kind of see your point (but I think you're missing some key > points). You mean just download all the headers and then just verify the > transactions you filter out by using their corresponding merkle trees, > right? But still, I don't think that would scale as well as with the tree > structure I propose. Because, firstly, you don't really need the headers of > the sibling chains. You just need the headers of the parent chains since > the parent verifies all the siblings. All you really need in a typical > (non-mining) situation is the headers or full blocks in one path going down > the tree starting from the root chain. So that means O(log n) needs to be > stored (headers or blocks) (n the number of transaction on the network). > With big blocks, you still need O(n) headers. I know headers are small, but > still they take up space and verification time. Also, since you are storing > the full blocks on the chains you want, you are validating the headers of > those blocks and you are sure that you are seeing all transactions on those > blocks. And if certain addresses must stay on those blocks, you will know > that you are catching all of the transactions corresponding to those > blocks. If you just filter out based on addresses or other criteria, you > can be denied some of those transactions by full nodes, and you may not > know about it. Say for example, your government representative publishes on > of his public addresses that is used for paying for expenses. Then with my > system, you can be sure to catch every transaction being spent from that > address (or UTXO or whatever you want to call it). If you just filter on > any transaction that includes that address, you may not catch all of those > transactions. Same with incoming funds. > > There are also advantages for mining decentralization as I have explained > in my previous posts. So still not sure you are right here... > > Thanks > > On Mon, Jun 15, 2015 at 5:18 PM, Mike Hearn wrote: > >> It's simple: either you care about validation, and you must validate >>> everything, or you don't, and you don't validate anything. >>> >> Pedantically: you could validate a random subset of all scripts, to give >> yourself probabilistic verification rather than full vs SPV. If enough >> people do it with a large enough subset the probability of a problem being >> detected goes up a lot. You still pay the cost of the database updates. >> >> But your main point is of course completely right, that side chains are >> not a way to scale up. >> > > > > -- > PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647 > -- 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
Side chains are a way to scale and shard horizontally while still retaining primary security parameters of the main chain. The future is an Internet of chains, a forest of chains with bitcoin as the root chain for: factom / proofofexistence, ChainDB, Blockstream side chains, merge mined side chains, and more. A multi-chain design is much more scalable in general. On Mon, Jun 15, 2015 at 1:18 PM, Mike Hearn wrote: > It's simple: either you care about validation, and you must validate >> everything, or you don't, and you don't validate anything. >> > Pedantically: you could validate a random subset of all scripts, to give > yourself probabilistic verification rather than full vs SPV. If enough > people do it with a large enough subset the probability of a problem being > detected goes up a lot. You still pay the cost of the database updates. > > But your main point is of course completely right, that side chains are > not a way to scale up. > > > -- > > ___ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- ___ 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: I kind of see your point (but I think you're missing some key points). You mean just download all the headers and then just verify the transactions you filter out by using their corresponding merkle trees, right? But still, I don't think that would scale as well as with the tree structure I propose. Because, firstly, you don't really need the headers of the sibling chains. You just need the headers of the parent chains since the parent verifies all the siblings. All you really need in a typical (non-mining) situation is the headers or full blocks in one path going down the tree starting from the root chain. So that means O(log n) needs to be stored (headers or blocks) (n the number of transaction on the network). With big blocks, you still need O(n) headers. I know headers are small, but still they take up space and verification time. Also, since you are storing the full blocks on the chains you want, you are validating the headers of those blocks and you are sure that you are seeing all transactions on those blocks. And if certain addresses must stay on those blocks, you will know that you are catching all of the transactions corresponding to those blocks. If you just filter out based on addresses or other criteria, you can be denied some of those transactions by full nodes, and you may not know about it. Say for example, your government representative publishes on of his public addresses that is used for paying for expenses. Then with my system, you can be sure to catch every transaction being spent from that address (or UTXO or whatever you want to call it). If you just filter on any transaction that includes that address, you may not catch all of those transactions. Same with incoming funds. There are also advantages for mining decentralization as I have explained in my previous posts. So still not sure you are right here... Thanks On Mon, Jun 15, 2015 at 5:18 PM, Mike Hearn wrote: > It's simple: either you care about validation, and you must validate >> everything, or you don't, and you don't validate anything. >> > Pedantically: you could validate a random subset of all scripts, to give > yourself probabilistic verification rather than full vs SPV. If enough > people do it with a large enough subset the probability of a problem being > detected goes up a lot. You still pay the cost of the database updates. > > But your main point is of course completely right, that side chains are > not a way to scale up. > -- 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
> > It's simple: either you care about validation, and you must validate > everything, or you don't, and you don't validate anything. > Pedantically: you could validate a random subset of all scripts, to give yourself probabilistic verification rather than full vs SPV. If enough people do it with a large enough subset the probability of a problem being detected goes up a lot. You still pay the cost of the database updates. But your main point is of course completely right, that side chains are not a way to scale up. -- ___ 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 1:09 PM, Pieter Wuille 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. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
If you are fine with the SPV security model, you are much better off by just increasing the Bitcoin block size and using an SPV client, as those do not care or even see the full block size by only downloading transactions they care about. Infinite scalability! The problem with scaling is that ultimately even SPV security relies on others being able to validate. Both sidechains and larger block sizes make that harder. 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. On Jun 15, 2015 7:05 PM, "Andrew" wrote: > Hi All, > > I talked with Pieter off-list. And I guess the main opposition is that > coins that are coming from chains that you are not directly validating are > not fully validated by you in the sense that you only get an SPV type proof > to prove that miners have accepted those coins. Yes, it's true, but once > blocks have been mined, there is nothing you can really do about it. > Splitting up the transactions into multiple chains doesn't stop someone > from validating all chains, which results in the same validation workload > as a full node with one chain and big blocks that store the same number of > transactions per second. So there is no disadvantage from using this method > compared with having big blocks, and there are clear advantages. The only > excuse is laziness to create a proper system. > > Martin: I'm not sure if random independent chains would be so useful since > there are delays with cross chain transfers and you would not be sure if > those chains will be maintained in the future. My idea is more the idea of > extension blocks, i.e. synchronised chains. > > Also, some people think that CPU speed and memory size are the only > limitations to running a full node, and they think that it is ok to just > run a heavily pruned node. Pruned nodes (nodes that have less than 10 years > of transactions on their hard drives) are bad for the network. Reasons why > you would want the long term history of transactions on your hard drive: > > 1) Your computer could have been compromised when you did the initial > validation, so you may want to validate and see all the old transactions > again. > > 2) You don't have to spend much time to download transactions that you > want to analyze but have already pruned. > > 3) Risk of denial of service attack from the "archival" nodes. > > 4) There is less of an inequality between the big data centers and regular > people. We can analyze the history of the transactions that are relevant to > us just as effectively as the data centers. With the pruning model, it will > be more like NSA-style nodes watching our transaction history, while > regular people can only see "snapshots". Remember how the Bitcoin community > was analysing the old Mt Gox transactions using the blockchain? This kind > of stuff will no longer be possible if most people can only run pruned > nodes. > > 5) The data is more distributed thus more easy for others to download > (think torrent downloads vs downloading from a central server). > > 6) Again being distributed, more eyes will be looking at the long term > data, thus people can more easily investigate scandals and things like that. > > 7) Without the full history of blocks people cannot really give a proof to > others that what they noticed with their pruned nodes is actually what > happened (if they spot something interesting). > > 8) The time for a new user to start fresh and sync a full node with a long > term history of transactions is much more accessible (17 days for 100 years > of transactions with 1 MB blocks on high-end computers). Same with the time > needed to perform any kind of analysis on the old transactions. And > remember, any new transactions likely depend on old transactions, so yes > they are very relevant. > > This is not paranoia. These are real security risks. So don't tell me that > you are really running a full node with the same level of security when you > are pruning it. Also, don't tell me that the security of running a full > node remains the same when centralization is increased (like with bigger > block sizes). Centralisation is a security risk. > > Some people think that decentralisation means you have to run a possibly > noisy desktop in a possible space restricted home, which can be annoying. > No, you don't have to. You can run a full node (or an almost full node on > the chains you are interested in) in a shack in the middle of nowhere and > you can monitor it remotely with cameras or whatever. The point is that it > is easy for a regular person to run one and they can do so without causing > attention and without anyone's permission. That is decentralisation. Even > 10 MB blocks are too much to enable this definition of decentralisation > (according to my calculations). > > If there are people who choose to run Gavin/Mi
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
Hi All, I talked with Pieter off-list. And I guess the main opposition is that coins that are coming from chains that you are not directly validating are not fully validated by you in the sense that you only get an SPV type proof to prove that miners have accepted those coins. Yes, it's true, but once blocks have been mined, there is nothing you can really do about it. Splitting up the transactions into multiple chains doesn't stop someone from validating all chains, which results in the same validation workload as a full node with one chain and big blocks that store the same number of transactions per second. So there is no disadvantage from using this method compared with having big blocks, and there are clear advantages. The only excuse is laziness to create a proper system. Martin: I'm not sure if random independent chains would be so useful since there are delays with cross chain transfers and you would not be sure if those chains will be maintained in the future. My idea is more the idea of extension blocks, i.e. synchronised chains. Also, some people think that CPU speed and memory size are the only limitations to running a full node, and they think that it is ok to just run a heavily pruned node. Pruned nodes (nodes that have less than 10 years of transactions on their hard drives) are bad for the network. Reasons why you would want the long term history of transactions on your hard drive: 1) Your computer could have been compromised when you did the initial validation, so you may want to validate and see all the old transactions again. 2) You don't have to spend much time to download transactions that you want to analyze but have already pruned. 3) Risk of denial of service attack from the "archival" nodes. 4) There is less of an inequality between the big data centers and regular people. We can analyze the history of the transactions that are relevant to us just as effectively as the data centers. With the pruning model, it will be more like NSA-style nodes watching our transaction history, while regular people can only see "snapshots". Remember how the Bitcoin community was analysing the old Mt Gox transactions using the blockchain? This kind of stuff will no longer be possible if most people can only run pruned nodes. 5) The data is more distributed thus more easy for others to download (think torrent downloads vs downloading from a central server). 6) Again being distributed, more eyes will be looking at the long term data, thus people can more easily investigate scandals and things like that. 7) Without the full history of blocks people cannot really give a proof to others that what they noticed with their pruned nodes is actually what happened (if they spot something interesting). 8) The time for a new user to start fresh and sync a full node with a long term history of transactions is much more accessible (17 days for 100 years of transactions with 1 MB blocks on high-end computers). Same with the time needed to perform any kind of analysis on the old transactions. And remember, any new transactions likely depend on old transactions, so yes they are very relevant. This is not paranoia. These are real security risks. So don't tell me that you are really running a full node with the same level of security when you are pruning it. Also, don't tell me that the security of running a full node remains the same when centralization is increased (like with bigger block sizes). Centralisation is a security risk. Some people think that decentralisation means you have to run a possibly noisy desktop in a possible space restricted home, which can be annoying. No, you don't have to. You can run a full node (or an almost full node on the chains you are interested in) in a shack in the middle of nowhere and you can monitor it remotely with cameras or whatever. The point is that it is easy for a regular person to run one and they can do so without causing attention and without anyone's permission. That is decentralisation. Even 10 MB blocks are too much to enable this definition of decentralisation (according to my calculations). If there are people who choose to run Gavin/Mike's hard fork of Bitcoin because they are uniformed or mentally challenged or have bad intentions, then there is not much I can do (I try to inform but I don't have such a high popularity level to be effective there), but I will surely not accept any bitcoin that is only valid on blocks with size greater than 1 million bytes. Such coins will have 0 or even negative value to me, and I expect others to do the same. In the meantime, I will start the development process of my proposed scaling methods using bitcoin-core and possibly the sidechains code from Blockstream as a base. I don't have much free time, so progress will likely be slow, but if I believe in something, I will keep working on it. I'm still seeking more criticism of my proposal, because you know, I don't want to waste my time if there's something fundamentall
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
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 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
Re: [Bitcoin-development] Scaling Bitcoin with Subchains
On Wed, May 20, 2015 at 4:55 AM, Andrew 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
On Wed, May 27, 2015 at 9:16 PM, Andrew 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
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
[Bitcoin-development] Scaling Bitcoin with Subchains
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). The main problem I see with increasing the block size limit is that it increases the amount of storage required to fully validate all transactions for say 100 years (a person's life). With 1 MB blocks, you can store all lifetime transactions on a 5 TB drive, which basically any regular user can do. With 10 MB blocks, you need a 50 TB drive, not accessible for regular users. Yes, it's possible that in the future hard drive technology will get cheaper and smaller, but this still didn't happen, so we can't just say "it should be doable at the rate of Moore's law etc...", we need to know that it is accessible for everyone, now. Also, don't forget that human life expectancy can increase with time as well. I know, it sounds silly to use a human lifetime as a measurement of how far back each user should be able to store transactions for, but what is a better measurement? This is a technology made for people i.e. humans, right, and the important part is that it is for regular people and not just well privileged people. You can search my last four emails for some more calculations. What sipa told me on the IRC channel is that Bitcoin Core does not care about old transactions. It only looks at the current blocks. Yes, that makes sense, but how do you know that your machine wasn't compromised when validating the previous blocks? And what if you want to check some old transactions (assuming you didn't index everything)? What if some of your old transaction data was lost or corrupted? I think it is clear that it is useful to be able to validate all blocks (since 100 years) rather than just a pruned part. It empowers people to have as much information about Bitcoin transactions as do large data centers; transactions that may include government or corporate corruption. This is the key to how Bitcoin enables transparency for those who should be transparent (individual users with private addresses can still remain anonymous). Also, 5 TB takes about 20 days to sync starting fresh, on a regular computer, so it allows easy entry into the system. So assuming we agree that people should be able to store ~ a lifetime of transactions, then we need 1 MB blocks. But of course, this leads to huge transaction costs, and small purchases will be out of limits. So to fix this, I propose adding a 10 1 MB chains below the main chain (sorry on the IRC room I said 10 10 MB chains by mistake), so effectively, you have a new 10 MB chain that is partitioned into 10 parts. You can also add a third level: 100 1 MB chains, and keep going like that. The idea is that when you make a large transaction, you put it through the top chain; when you make a medium sized transaction, you put it through one of the middle chains, which will be verified (mined) by the middle chain, and the top chain will verify the aggregate transactions of the middle chain. If you have a small sized transaction, you put it through one of the bottom chains, the bottom chain verifies it, the middle chain verifies the aggregate transactions of the bottom chain, and the top chain verifies the aggregate transactions of the middle chain. By aggregate transaction, I mean the net result of multiple transactions, and I suppose it can be 20 transactions belonging only to one "sibling" chain for level 2, or 200 transactions for level 3, etc... Now, how does the system decide to which of the 10 chains the middle sized transaction goes to? I propose just taking some simple function of the input addresses mod 10, so that you can just keep randomly generating a wallet until you get one with only addresses that map to only one of the 10 chains (even distribution), so that someone can choose one of the 10 chains, and store only the transactions that belong to that chain. They should also choose a chain from level 3, etc... So in effect, they will be storing a chain with block size O(n) where n is the number of levels. They may store multiple sibling chains at one level, if they want to track of other people's transactions, such as those of their government MP, or perhaps, they want to have a separate identity that would be more anonymous with a separate series of sibling chains. This will increase the storage size, but the increase will be proportional to the number of things you want to keep track of (at least this kind of sys
