* [Bitcoin-development] Scaling Bitcoin with Subchains
@ 2015-05-20 2:55 Andrew
2015-05-25 18:15 ` Mike Hearn
2015-06-13 14:39 ` Pieter Wuille
0 siblings, 2 replies; 17+ messages in thread
From: Andrew @ 2015-05-20 2:55 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 7300 bytes --]
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 system gives you the ability
to fine tune your storage needs to the level of "things" you want to keep
track of). Also, note that there may likely be duplication of transactions,
since transactions can include addresses that are associated with different
silbling chains, but this effect shouldn't make a big difference, and again
will depend on the complexity of the transactions you want to keep track of.
So how can this work? I propose that we keep the current chain as the top
chain, and then create 10 level 2 chains that also store Bitcoin and the
Bitcoin can be transferred between chains (I think this is the idea of
sidechains). How can we incentivize people to keep mining on the level 1
chain? Perhaps force it into the (soft fork) protocol that anyone mining on
level 2, has to also mine on level 1, and in general, anyone mining on
level n+1 has to also mine on levels n,n-1,...,1. Also, level 1 will have
the best decentralization, so there should be enough people paying fees to
get transactions there for their large transactions that require a high
level of security and trust. Even if people stop using level 1, any bitcoin
you own in the level 1 chain, can be transferred to level 2, and still you
have 1 MB blocks due to the partitioning scheme. How to prevent
transactions from clustering on one or a few sibling chains in a
particular level? Well the more empty chains should have lower fees, so
that should incentivize people... Note: This system also allows for the
fine tuning of the transaction size to security ratio. Yes the lower chains
will be less secure, but a lower sized transaction does not need as much
security.
For instant transactions, there can also be Lightning channels linked to
whatever level of chain you want.
OK so it seems to me that this can work and would only require a soft fork.
But, as I said, I only have a high level understanding of the Bitcoin
protocol, so it feels kind of too good to be true, and I am ready for heavy
criticism. I am only writing this because I care about Bitcoin and I want
it to remain decentralized and become the best that it can be. I think it
is important to do the right thing rather than (as most people naturally
do) the most convenient thing.
Thanks
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
[-- Attachment #2: Type: text/html, Size: 7756 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-05-20 2:55 [Bitcoin-development] Scaling Bitcoin with Subchains Andrew
@ 2015-05-25 18:15 ` Mike Hearn
2015-05-28 2:16 ` Andrew
2015-06-13 14:39 ` Pieter Wuille
1 sibling, 1 reply; 17+ messages in thread
From: Mike Hearn @ 2015-05-25 18:15 UTC (permalink / raw)
To: Andrew; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 982 bytes --]
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.
[-- Attachment #2: Type: text/html, Size: 1319 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-05-25 18:15 ` Mike Hearn
@ 2015-05-28 2:16 ` Andrew
2015-05-28 2:34 ` Bryan Bishop
0 siblings, 1 reply; 17+ messages in thread
From: Andrew @ 2015-05-28 2:16 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 7396 bytes --]
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
it a combination of both things? You should disclose this to the people
following your words because they trust you as an experienced professional
with a good reputation, and it would be dishonest to not disclose this to
them. (same goes for Gavin)
Overall, I think this system is the only system that I heard of that can
scale decentralization without a block size increase. Lightning by itself,
for example, requires a block size increase that depends on how many such
Lightning contracts are being made, so relies on people changing the
protocol, which is obviously less secure and robust than a fixed protocol.
But I am not ruling out any other possibilities, so other things should
also be considered. But eventually, we may have to decide how to scale
without knowing for sure whether the chosen scaling method is the ultimate
scaling method. And I think this is a good candidate for that, and also,
can be reversed later on without changing the original protocol before the
softfork. Actually, we can just make nodes advertise whether they support
the soft fork or not, and if a better scaling protocol comes along, those
nodes can switch to advertise the better one. So it is quite a harmless
soft fork to make, in my opinion.
On Mon, May 25, 2015 at 6:15 PM, Mike Hearn <mike@plan99•net> wrote:
> 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.
>
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
[-- Attachment #2: Type: text/html, Size: 8310 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-05-28 2:16 ` Andrew
@ 2015-05-28 2:34 ` Bryan Bishop
0 siblings, 0 replies; 17+ messages in thread
From: Bryan Bishop @ 2015-05-28 2:34 UTC (permalink / raw)
To: Andrew, Bryan Bishop; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3027 bytes --]
On Wed, May 27, 2015 at 9:16 PM, Andrew <onelineproof@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
[-- Attachment #2: Type: text/html, Size: 5480 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-05-20 2:55 [Bitcoin-development] Scaling Bitcoin with Subchains Andrew
2015-05-25 18:15 ` Mike Hearn
@ 2015-06-13 14:39 ` Pieter Wuille
2015-06-13 17:55 ` Andrew
2015-06-14 6:55 ` Martin Schwarz
1 sibling, 2 replies; 17+ messages in thread
From: Pieter Wuille @ 2015-06-13 14:39 UTC (permalink / raw)
To: Andrew; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2775 bytes --]
On Wed, May 20, 2015 at 4:55 AM, Andrew <onelineproof@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
[-- Attachment #2: Type: text/html, Size: 3394 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-13 14:39 ` Pieter Wuille
@ 2015-06-13 17:55 ` Andrew
2015-06-14 6:55 ` Martin Schwarz
1 sibling, 0 replies; 17+ messages in thread
From: Andrew @ 2015-06-13 17:55 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 6590 bytes --]
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.wuille@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 since not all the
transactions in those blocks may be of interest to them, they just need
proof that any output used in their blocks of interest are valid, so that's
why the header-only SPV proof is sufficient. But yeah, typically a user
will have the full blocks of the parent and grandparent chains of the
chains they are interested in tracking, but it is not always necessary.
Also, in the bitcointalk forum I explain in more detail the mining
procedure and how to limit the extra traffic that may be caused on the
network in case this does get added as a soft fork and then later a new
better scaling method is invented that supercedes this.
But basically, for the mining, I think it should be merge-mined between
parent and direct children only. If all the chains are merge mining the
same root chain, then it would be bad for decentralization, right? But with
only direct parent and children merge mining, you can have smaller miners
on the lower (grand children) level chains and since they will need to
solve another hash problem than their grand parent chains, the grandparents
cannot solve blocks in the grand children chains (only the direct children).
So I still didn't hear a good argument against my proposal. I know Adam
Back's form of extension blocks is problematic because it still has the big
blocks, just at another level of chain, but just by partitioning his one 10
MB chain into 10 pieces, you get my idea, which I think solves the
scalability problem as well.
Cheers
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
[-- Attachment #2: Type: text/html, Size: 7807 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-13 14:39 ` Pieter Wuille
2015-06-13 17:55 ` Andrew
@ 2015-06-14 6:55 ` Martin Schwarz
2015-06-15 17:05 ` Andrew
1 sibling, 1 reply; 17+ messages in thread
From: Martin Schwarz @ 2015-06-14 6:55 UTC (permalink / raw)
To: Pieter Wuille; +Cc: bitcoin-development
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-14 6:55 ` Martin Schwarz
@ 2015-06-15 17:05 ` Andrew
2015-06-15 17:09 ` Pieter Wuille
0 siblings, 1 reply; 17+ messages in thread
From: Andrew @ 2015-06-15 17:05 UTC (permalink / raw)
To: Martin Schwarz; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 7065 bytes --]
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 fundamentally wrong with it.
Cheers
On Sun, Jun 14, 2015 at 6:55 AM, Martin Schwarz <martin.schwarz@gmail•com>
wrote:
> 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
>
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
[-- Attachment #2: Type: text/html, Size: 8187 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:05 ` Andrew
@ 2015-06-15 17:09 ` Pieter Wuille
2015-06-15 17:15 ` Jeff Garzik
2015-06-15 17:18 ` Mike Hearn
0 siblings, 2 replies; 17+ messages in thread
From: Pieter Wuille @ 2015-06-15 17:09 UTC (permalink / raw)
To: Andrew; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 8004 bytes --]
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" <onelineproof@gmail•com> 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/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 fundamentally wrong with it.
>
> Cheers
>
> On Sun, Jun 14, 2015 at 6:55 AM, Martin Schwarz <martin.schwarz@gmail•com>
> wrote:
>
>> 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
>>
>
>
>
> --
> PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
>
[-- Attachment #2: Type: text/html, Size: 9155 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:09 ` Pieter Wuille
@ 2015-06-15 17:15 ` Jeff Garzik
2015-06-16 18:17 ` Peter Todd
2015-06-15 17:18 ` Mike Hearn
1 sibling, 1 reply; 17+ messages in thread
From: Jeff Garzik @ 2015-06-15 17:15 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 861 bytes --]
On Mon, Jun 15, 2015 at 1:09 PM, Pieter Wuille <pieter.wuille@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.
--
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc. https://bitpay.com/
[-- Attachment #2: Type: text/html, Size: 1411 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:09 ` Pieter Wuille
2015-06-15 17:15 ` Jeff Garzik
@ 2015-06-15 17:18 ` Mike Hearn
2015-06-15 18:00 ` Andrew
2015-06-15 18:01 ` Jeff Garzik
1 sibling, 2 replies; 17+ messages in thread
From: Mike Hearn @ 2015-06-15 17:18 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 523 bytes --]
>
> 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.
[-- Attachment #2: Type: text/html, Size: 783 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:18 ` Mike Hearn
@ 2015-06-15 18:00 ` Andrew
2015-06-16 15:23 ` Andrew
2015-06-15 18:01 ` Jeff Garzik
1 sibling, 1 reply; 17+ messages in thread
From: Andrew @ 2015-06-15 18:00 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2550 bytes --]
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 <mike@plan99•net> 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
[-- Attachment #2: Type: text/html, Size: 3192 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:18 ` Mike Hearn
2015-06-15 18:00 ` Andrew
@ 2015-06-15 18:01 ` Jeff Garzik
1 sibling, 0 replies; 17+ messages in thread
From: Jeff Garzik @ 2015-06-15 18:01 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1371 bytes --]
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 <mike@plan99•net> 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/
[-- Attachment #2: Type: text/html, Size: 2316 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 18:00 ` Andrew
@ 2015-06-16 15:23 ` Andrew
0 siblings, 0 replies; 17+ messages in thread
From: Andrew @ 2015-06-16 15:23 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 4034 bytes --]
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 <onelineproof@gmail•com> 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 <mike@plan99•net> 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
[-- Attachment #2: Type: text/html, Size: 5011 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-15 17:15 ` Jeff Garzik
@ 2015-06-16 18:17 ` Peter Todd
2015-06-16 18:43 ` Andrew
0 siblings, 1 reply; 17+ messages in thread
From: Peter Todd @ 2015-06-16 18:17 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1913 bytes --]
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.wuille@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
0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-16 18:17 ` Peter Todd
@ 2015-06-16 18:43 ` Andrew
2015-06-16 19:04 ` Andrew
0 siblings, 1 reply; 17+ messages in thread
From: Andrew @ 2015-06-16 18:43 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1834 bytes --]
On Tue, Jun 16, 2015 at 6:17 PM, Peter Todd <pete@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
[-- Attachment #2: Type: text/html, Size: 2356 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [Bitcoin-development] Scaling Bitcoin with Subchains
2015-06-16 18:43 ` Andrew
@ 2015-06-16 19:04 ` Andrew
0 siblings, 0 replies; 17+ messages in thread
From: Andrew @ 2015-06-16 19:04 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2589 bytes --]
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 <onelineproof@gmail•com> wrote:
>
>
> On Tue, Jun 16, 2015 at 6:17 PM, Peter Todd <pete@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
>
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
[-- Attachment #2: Type: text/html, Size: 3422 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2015-06-16 19:04 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-05-20 2:55 [Bitcoin-development] Scaling Bitcoin with Subchains Andrew
2015-05-25 18:15 ` Mike Hearn
2015-05-28 2:16 ` Andrew
2015-05-28 2:34 ` Bryan Bishop
2015-06-13 14:39 ` Pieter Wuille
2015-06-13 17:55 ` Andrew
2015-06-14 6:55 ` Martin Schwarz
2015-06-15 17:05 ` Andrew
2015-06-15 17:09 ` Pieter Wuille
2015-06-15 17:15 ` Jeff Garzik
2015-06-16 18:17 ` Peter Todd
2015-06-16 18:43 ` Andrew
2015-06-16 19:04 ` Andrew
2015-06-15 17:18 ` Mike Hearn
2015-06-15 18:00 ` Andrew
2015-06-16 15:23 ` Andrew
2015-06-15 18:01 ` Jeff Garzik
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox