More details on treechains by pter todd
1 http://www.mail-archive.com/[email protected]/msg04388.html
2 http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg03307.html
Topic: Sidechains, Treechains, the TL;DR, welcome to join discussion. - page 2. (Read 4688 times)
welcome to join discussion.
Sidechains, Treechains, the TL;DR
（i am not the author of this article, here is the source: http://blog.greenaddress.it/2014/06/13/sidechains-treechains-the-tldr/）
This document is aimed at technical readers and is simply a brief explanation of sidechains and treechains as far as I understand them, based on public information. Both are obviously still in very preliminary development, but this document is just to introduce the broad concepts, and their consequences. Some people have been asking for something like this, might as well see if this helps.
With GHash is getting nearly 50% of hashing power of the network, this discussion is more timely than ever.
I’ll start with sidechains, since treechains are essentially a specific form of sidechains.
Sidechains:
In the most general, sidechains will use “SPV Proofs” to send satoshis from the regular Bitcoin chain to the sidechain, and allows the sidechain to eventually send the satoshis back to the main chain once the owner of said coin is finished utilizing the sidechain. While in the sidechain, the main chain knows nothing of what’s happening to the coin, the sidechain is the one tracking who owns what at what time.
The side chain can basically have any rules it likes for what a valid block is, block times, etc. Typically the idea is that these chains will be merge mined with the Bitcoin network, to ensure that a reasonable amount of hashing power is protecting the sidechain network from DoS, and outright theft of coins by miners which is possible due to the limitations of the SPV proofs. It’s important to note however, that it has been suggested that the outright theft of coins by miners may be protected against using zk-SNARKs.(https://eprint.iacr.org/2013/507.pdf)
The pros of sidechains appear to be:
1 You don’t need permission to start a new chain with new validation rules, block times, whatever. You could fairly trivially add Zerocash, Ethereum rules, and still have them pegged in satoshis. Also would be a great way to test out new opcodes/communication protocols for the base protocol and codebase.
2 The sidechains would be backed by the hashing power of the Bitcoin network, so given certain conditions(detailed below) it can’t be trivially attacked.
The cons are as far as we know(not counting new zk-SNARK moon math that hasn’t been given to the public):
1 Merge mining also means two things: There is no inherent block reward. Security will most likely be only be from transaction fees. more importantly, you need to convince the large pools to manually activate the merged mining of these chains, otherwise a 51% attack is essentially free. You also have to trust the pools aren’t faking downtime, while secretly mining the chain.
2 Long-term it can contribute to centralization of mining, just in the same way that increasing the block size would. It would be optional to mine these sidechains yes, but if it becomes a sizeable fraction of transaction fees, the economics work in the favor of more centralization.
3 Sending satoshis back and forth between chains will take days, to ensure that satoshis aren’t being stolen by miners, again due to the aforementioned SPV proofs, which is something that simply can’t happen in vanilla Bitcoin. Most going back and forth will be done using atomic swaps in between users to reduce this waiting period.
Treechains:
I think of treechains as tighter-coupled sidechains. The difference in chain structure is larger than between sidechains and the vanilla Bitcoin protocol, so I’m tackling them in broad brush-strokes.
1 Miners are not required to validate blocks, outside of the PoW difficulty being low enough, and being a proper hash of the block+previous block. If the block header looks legit, miners can start to build on top of this.
2 Starting from the main Bitcoin chain, each chain will have a left and right descendant chain. This builds a binary tree of chains, hence “treechains”. Each chain level has 2^(numlevels-1) chains, doubling the number of the previous level. Each difficulty threshold is also halved. Based on the hash of the transactions, they can only be mined in in specific paths of the tree structure(starting from the first bit of the hash from the root of the tree, ‘0’ means left subtree, ‘1’ means right). Each time satoshis are spent, it will get sent to another chain in the same level based on the previous transaction’s hash(ignoring up/down movement for clarity).
In addition, each path is merge mined, allowing miners to mine one and only one path of the tree using the same hashing work. So for example, 3 layers down, there should on average only be an 8th of the total transactions on any specific chain, as well as only an 8th of the total mining power, resulting in roughly the same block time as higher chains!
3 The chains are linked together more strongly than sidechains to enforce a total ordering of transactions. Every time a miner gets a PoW high enough for a certain level, it “links” that block with all the blocks being mined below together. This enforces the total ordering we want. Transactions on let’s say level 16 will have a higher chance of getting orphaned, but eventually once they “percolate” up to the main chain, they are just as secure as the main chain. The linking also determines when you can spend your satoshis, meaning lower chains will take longer to spend the same outputs again compared to higher chains. To spend your satoshis from chain A to chain B at level C, the previously mined transaction’s block in A must be linked to B’s nearest common ancestor chain, with the only valid paths being forward/up the chains, not backwards.
4 Last important thing to note about the tree structure: Parent chain always wins. If the child chain is in conflict with the parent chain(the links are inconsistent, making total ordering inconsistent), those blocks child blocks are orphaned. Therefore, re-organizations at higher chains can cause reorganizations at lower chains, but not vice versa.
And their consequences/caveats:
1 Since miners aren’t required to validate anything outside of basic PoW, this breaks the need to beg miners for protocol changes. Granted, there will be a base BTC layer that allows things like “miner gets block reward” and “pay .0001 BTC to miner for transaction fee” to incentivize the mining, but outside of this, it allows fairly arbitrary protocols. One could even imagine paying a miner colored coins to get it included in a block, if the miner wanted equity! One thing this can’t do versus sidechains is initialize chains with arbitrary block times. However you might be able to get away with much faster block times than vanilla Bitcoin due to #2. Overall, this will let innovation at the edges happen, without having to agree on everything with Core Devs, or mining pools, or industry, etc. SPV clients won’t be possible, at least in their current form, due to SPV’s assumption that mined blocks are validated by the miners.
2 Proving who owns what when will be more complicated for the client, as they can’t assume miners are validating a certain protocol. Clients will have to hold data outside of their private keys, proving to the payee that these coins exist and control them. This will be more complicated than our SPV clients we have today, but will make running a node with “full node” security tractable, as you don’t care what the contents of most blocks are, just the blocks that prove to you that you own the satoshis you own(a small sample of blocks compared to the whole tree of chains). These proofs will be “compact”, although it remains to be seen how much more compact than linear in block sizes we can get(insert zk-SNARK moon math for sublinear performance?).
3 Combining with consequences from #1, miners will be able to mine as little or as much as they like, with only paying attention to block headers, and block payloads that again, prove to him that they’re actually being paid to mine by fees. A miner could simply keep track of all headers in the treechains, which is trivial, and solo mine 16 levels down, where their variance is 2^(-16) less than the vanilla blockchain mining, due to the sparsity of miners that far down in a branch. If a user is willing to wait a while for the ability to re-spend their outputs, they can approach a solo miner, pay a smaller fee than usual, and wait for the block to get linked higher in the tree.This opens up a true marketplace for fees, as well as allows small pools/solo miners to make a real difference when it comes to block creation. Lastly, this system appears to scale to an infinite amount of transactions, without hurting decentralization.
4 The linking scheme ultimately means that orphan rates will be higher at lower levels, and re-spending outputs will take longer, and will be based on where the next transaction will end up in the tree structure. However, for your coffee money, it enables you to get in a block, and for the merchant to not worry too much that you’ll try and 51% attack 5 levels down as it won’t make economic sense.
In summary(TL;DR’s TL;DR):
A Sidechain, at its most general, is a loosely coupled chain that, in general, uses merged mining to protect the network. These chains are “backed” by BTC from the Bitcoin network, rather than minting their own coin and diluting scarcity. There are some questions about security guarantees versus the Bitcoin network.
A Treechain is a structure of more-tightly coupled sidechains. This structure, in theory, allows miners to mine at arbitrary variance without pooling, scaling of the system far beyond 7tps without asking permission, and other innovation at the edges, all with the same protections of the main Bitcoin network. With the huge caveat that the idea is still half-baked, has no known SPV client support, and is much more complicated than a vanilla blockchain.
Both ideas are interesting ways of tackling some of the important problems that all cryptocurrencies face. We should know more about the actual implementation of sidechains within 3 months, as the company Blockstream will be releasing a white paper and source code. Many of these ideas that aren’t published will be directly applicable to treechains, as they are kin in many ways, including how they will be rolled out initially.
I’m personally biased towards treechains in that I believe the de-coupling of miners and policy is a huge step forward, even just for new fancy opcodes without permission. It may also enable us to be free of begging MegaPool#9 not to 51% attack us, which is already happening. I for one would like to solo-mine on a USB ASIC!
Unfortunately due to its complexity and fundamental difference with Bitcoin proper, it will almost certainly take more time to flesh out and convince others that radical steps need to be taken to keep cryptocurrency decentralized. I look forward to its development.
If you have time on your hands to check out more of the details of treechains,
here is Peter Todd’s initial writeup of many of the ideas: http://www.mail-archive.com/[email protected]/msg04388.html
As well as the Let’s Talk Bitcoin podcast where he goes into much of this detail: here:http://letstalkbitcoin.com/ltb104-tree-chains-with-peter-todd/
(thanks to /u/_Mr_e)
Hope someone finds this helpful,
Greg Sanders
Contributor to Bitcoin.org’s Bitcoin Developer Guide
[email protected]
Peter Todd (https://twitter.com/petertoddbtc)sent us the following:
FWIW there are some concerns raised re: how tree chains handles data
loss at the lowest levels; I’m not sure yet that those concerns can be
resolved. Also Adam Back raised some potential issues re: incentives in
some edge cases. Of course, you did quite correctly describe the idea as
half baked.
（i am not the author of this article, here is the source: http://blog.greenaddress.it/2014/06/13/sidechains-treechains-the-tldr/）
This document is aimed at technical readers and is simply a brief explanation of sidechains and treechains as far as I understand them, based on public information. Both are obviously still in very preliminary development, but this document is just to introduce the broad concepts, and their consequences. Some people have been asking for something like this, might as well see if this helps.
With GHash is getting nearly 50% of hashing power of the network, this discussion is more timely than ever.
I’ll start with sidechains, since treechains are essentially a specific form of sidechains.
Sidechains:
In the most general, sidechains will use “SPV Proofs” to send satoshis from the regular Bitcoin chain to the sidechain, and allows the sidechain to eventually send the satoshis back to the main chain once the owner of said coin is finished utilizing the sidechain. While in the sidechain, the main chain knows nothing of what’s happening to the coin, the sidechain is the one tracking who owns what at what time.
The side chain can basically have any rules it likes for what a valid block is, block times, etc. Typically the idea is that these chains will be merge mined with the Bitcoin network, to ensure that a reasonable amount of hashing power is protecting the sidechain network from DoS, and outright theft of coins by miners which is possible due to the limitations of the SPV proofs. It’s important to note however, that it has been suggested that the outright theft of coins by miners may be protected against using zk-SNARKs.(https://eprint.iacr.org/2013/507.pdf)
The pros of sidechains appear to be:
1 You don’t need permission to start a new chain with new validation rules, block times, whatever. You could fairly trivially add Zerocash, Ethereum rules, and still have them pegged in satoshis. Also would be a great way to test out new opcodes/communication protocols for the base protocol and codebase.
2 The sidechains would be backed by the hashing power of the Bitcoin network, so given certain conditions(detailed below) it can’t be trivially attacked.
The cons are as far as we know(not counting new zk-SNARK moon math that hasn’t been given to the public):
1 Merge mining also means two things: There is no inherent block reward. Security will most likely be only be from transaction fees. more importantly, you need to convince the large pools to manually activate the merged mining of these chains, otherwise a 51% attack is essentially free. You also have to trust the pools aren’t faking downtime, while secretly mining the chain.
2 Long-term it can contribute to centralization of mining, just in the same way that increasing the block size would. It would be optional to mine these sidechains yes, but if it becomes a sizeable fraction of transaction fees, the economics work in the favor of more centralization.
3 Sending satoshis back and forth between chains will take days, to ensure that satoshis aren’t being stolen by miners, again due to the aforementioned SPV proofs, which is something that simply can’t happen in vanilla Bitcoin. Most going back and forth will be done using atomic swaps in between users to reduce this waiting period.
Treechains:
I think of treechains as tighter-coupled sidechains. The difference in chain structure is larger than between sidechains and the vanilla Bitcoin protocol, so I’m tackling them in broad brush-strokes.
1 Miners are not required to validate blocks, outside of the PoW difficulty being low enough, and being a proper hash of the block+previous block. If the block header looks legit, miners can start to build on top of this.
2 Starting from the main Bitcoin chain, each chain will have a left and right descendant chain. This builds a binary tree of chains, hence “treechains”. Each chain level has 2^(numlevels-1) chains, doubling the number of the previous level. Each difficulty threshold is also halved. Based on the hash of the transactions, they can only be mined in in specific paths of the tree structure(starting from the first bit of the hash from the root of the tree, ‘0’ means left subtree, ‘1’ means right). Each time satoshis are spent, it will get sent to another chain in the same level based on the previous transaction’s hash(ignoring up/down movement for clarity).
In addition, each path is merge mined, allowing miners to mine one and only one path of the tree using the same hashing work. So for example, 3 layers down, there should on average only be an 8th of the total transactions on any specific chain, as well as only an 8th of the total mining power, resulting in roughly the same block time as higher chains!
3 The chains are linked together more strongly than sidechains to enforce a total ordering of transactions. Every time a miner gets a PoW high enough for a certain level, it “links” that block with all the blocks being mined below together. This enforces the total ordering we want. Transactions on let’s say level 16 will have a higher chance of getting orphaned, but eventually once they “percolate” up to the main chain, they are just as secure as the main chain. The linking also determines when you can spend your satoshis, meaning lower chains will take longer to spend the same outputs again compared to higher chains. To spend your satoshis from chain A to chain B at level C, the previously mined transaction’s block in A must be linked to B’s nearest common ancestor chain, with the only valid paths being forward/up the chains, not backwards.
4 Last important thing to note about the tree structure: Parent chain always wins. If the child chain is in conflict with the parent chain(the links are inconsistent, making total ordering inconsistent), those blocks child blocks are orphaned. Therefore, re-organizations at higher chains can cause reorganizations at lower chains, but not vice versa.
And their consequences/caveats:
1 Since miners aren’t required to validate anything outside of basic PoW, this breaks the need to beg miners for protocol changes. Granted, there will be a base BTC layer that allows things like “miner gets block reward” and “pay .0001 BTC to miner for transaction fee” to incentivize the mining, but outside of this, it allows fairly arbitrary protocols. One could even imagine paying a miner colored coins to get it included in a block, if the miner wanted equity! One thing this can’t do versus sidechains is initialize chains with arbitrary block times. However you might be able to get away with much faster block times than vanilla Bitcoin due to #2. Overall, this will let innovation at the edges happen, without having to agree on everything with Core Devs, or mining pools, or industry, etc. SPV clients won’t be possible, at least in their current form, due to SPV’s assumption that mined blocks are validated by the miners.
2 Proving who owns what when will be more complicated for the client, as they can’t assume miners are validating a certain protocol. Clients will have to hold data outside of their private keys, proving to the payee that these coins exist and control them. This will be more complicated than our SPV clients we have today, but will make running a node with “full node” security tractable, as you don’t care what the contents of most blocks are, just the blocks that prove to you that you own the satoshis you own(a small sample of blocks compared to the whole tree of chains). These proofs will be “compact”, although it remains to be seen how much more compact than linear in block sizes we can get(insert zk-SNARK moon math for sublinear performance?).
3 Combining with consequences from #1, miners will be able to mine as little or as much as they like, with only paying attention to block headers, and block payloads that again, prove to him that they’re actually being paid to mine by fees. A miner could simply keep track of all headers in the treechains, which is trivial, and solo mine 16 levels down, where their variance is 2^(-16) less than the vanilla blockchain mining, due to the sparsity of miners that far down in a branch. If a user is willing to wait a while for the ability to re-spend their outputs, they can approach a solo miner, pay a smaller fee than usual, and wait for the block to get linked higher in the tree.This opens up a true marketplace for fees, as well as allows small pools/solo miners to make a real difference when it comes to block creation. Lastly, this system appears to scale to an infinite amount of transactions, without hurting decentralization.
4 The linking scheme ultimately means that orphan rates will be higher at lower levels, and re-spending outputs will take longer, and will be based on where the next transaction will end up in the tree structure. However, for your coffee money, it enables you to get in a block, and for the merchant to not worry too much that you’ll try and 51% attack 5 levels down as it won’t make economic sense.
In summary(TL;DR’s TL;DR):
A Sidechain, at its most general, is a loosely coupled chain that, in general, uses merged mining to protect the network. These chains are “backed” by BTC from the Bitcoin network, rather than minting their own coin and diluting scarcity. There are some questions about security guarantees versus the Bitcoin network.
A Treechain is a structure of more-tightly coupled sidechains. This structure, in theory, allows miners to mine at arbitrary variance without pooling, scaling of the system far beyond 7tps without asking permission, and other innovation at the edges, all with the same protections of the main Bitcoin network. With the huge caveat that the idea is still half-baked, has no known SPV client support, and is much more complicated than a vanilla blockchain.
Both ideas are interesting ways of tackling some of the important problems that all cryptocurrencies face. We should know more about the actual implementation of sidechains within 3 months, as the company Blockstream will be releasing a white paper and source code. Many of these ideas that aren’t published will be directly applicable to treechains, as they are kin in many ways, including how they will be rolled out initially.
I’m personally biased towards treechains in that I believe the de-coupling of miners and policy is a huge step forward, even just for new fancy opcodes without permission. It may also enable us to be free of begging MegaPool#9 not to 51% attack us, which is already happening. I for one would like to solo-mine on a USB ASIC!
Unfortunately due to its complexity and fundamental difference with Bitcoin proper, it will almost certainly take more time to flesh out and convince others that radical steps need to be taken to keep cryptocurrency decentralized. I look forward to its development.
If you have time on your hands to check out more of the details of treechains,
here is Peter Todd’s initial writeup of many of the ideas: http://www.mail-archive.com/[email protected]/msg04388.html
As well as the Let’s Talk Bitcoin podcast where he goes into much of this detail: here:http://letstalkbitcoin.com/ltb104-tree-chains-with-peter-todd/
(thanks to /u/_Mr_e)
Hope someone finds this helpful,
Greg Sanders
Contributor to Bitcoin.org’s Bitcoin Developer Guide
[email protected]
Peter Todd (https://twitter.com/petertoddbtc)sent us the following:
FWIW there are some concerns raised re: how tree chains handles data
loss at the lowest levels; I’m not sure yet that those concerns can be
resolved. Also Adam Back raised some potential issues re: incentives in
some edge cases. Of course, you did quite correctly describe the idea as
half baked.
Jump to: