What is sharding, and will sharding scale Bitcoin?

[Wind_FURY]

Correct me if I post something wrong.

Sharding, in theory, is to increase transaction throughput on-chain, by splitting up the blockchain without sacrificing "node centralization".

But how can this be if each shard, added up together, will still be more than the sum total of the whole blockchain as if it wasn't "sharded"? It will increase on-chain transactions per second, but it will scale the network in, instead of scaling out.

[1714133791]

1714133791

[1714133791]

1714133791

[1714133791]

1714133791

[Pmalek]

Have you read this paper by Peter Todd about the difficulties of scaling bitcoin with sharding? Not sure but maybe it will give you the answers you seek.
https://petertodd.org/2015/why-scaling-bitcoin-with-sharding-is-very-hard

[HeRetiK]

Correct me if I post something wrong.

Sharding, in theory, is to increase transaction throughput on-chain, by splitting up the blockchain without sacrificing "node centralization".

But how can this be if each shard, added up together, will still be more than the sum total of the whole blockchain as if it wasn't "sharded"? It will increase on-chain transactions per second, but it will scale the network in, instead of scaling out.

I think the main case for blockchain sharding is the implicit assumption that the workload reduction of individual nodes would lead to a wider distribution of the dataset as a whole.

For example, let's assume a blockchain of 500GB is so resource intensive that the network now consists of only 1,000 nodes. The argument for sharding would be that if you split the blockchain into 50GB shards each, you will now not only have 10 times as many nodes (ie. 10,000) but, say, 100,000 nodes, because running a node becomes that much cheaper and easier. Voilá, you just increased the redundancy and presumably decentralization by an order of magnitude.

Obviously it's not that easy though. Using sharding to scale a database in a non-adverserial environment is a whole different beast from attempting the same with a public blockchain.

It not only comes at the cost of significant added complexity but to some extend also at the cost of security and permissionlessness. While the complexity cost seems undisputed, there are varying opinions on how big the impact on security and permissionless really is (the implications for PoW based coins being more severe than for PoS based coins from what I've gathered); however I haven't followed that discourse all that much so I don't dare to go into any specifics.

[Wind_FURY]

Plus this shower thought. Will a sharded Bitcoin blockchain maintain the average 10 minute interval between transactions on the network as a whole, or will it be a 10 minute interval on each shard?

ETFbitcoin, Pmalek thanks.

[monsterer2]

The problem with sharding is that if you want miners to work separately in each shard (as you must), then the hashrate of the network is divided up by N shards, meaning a double spend attack just got N times easier within each shard.

[d5000]

The problem with sharding is that if you want miners to work separately in each shard (as you must), then the hashrate of the network is divided up by N shards, meaning a double spend attack just got N times easier within each shard.

I just read a bit about Peter Todd's "treechains" (which are described in the text linked by Pmalek) and this proposal doesn't seem to suffer from the problem as miners contribute all to a "timestamp chain" or "main chain", while transactions are collected in sub-chains. However I'll have to read further as I've still not fully understood the proposal. It seems, however, that it needs much deeper changes to Bitcoin's code than "sidechain" proposals.

Merged mined sidechains/shards may also be a solution for that issue, however, the 2 way peg problem needed is still unsolved (with the drivechain proposal as a "contender"), and it may not be really considered "sharding".

[Wind_FURY]

Can anyone in the forum, who knows sharding, share their thoughts? I believe there are posters, some of who are coders, who comment about sharding, but truly might not deeply know anything about it. All they are saying is "it will work".

Plus what need does Bitcoin have for sharding if blocks remain small, and a 2nd layer is available?

[aliashraf]

Have you read this paper by Peter Todd about the difficulties of scaling bitcoin with sharding? Not sure but maybe it will give you the answers you seek.
https://petertodd.org/2015/why-scaling-bitcoin-with-sharding-is-very-hard

Todd's article is based on the common assumption about sharding: shards are vulnerable to 51% attack and not secure as much as the legacy monolithic blockchains.
Thereafter he discusses a range of problems and hypothetical solutions:

• fraud proof ideas and their infeasibility, because there is no guarantee for the fraud to be detected and more importantly a definite possibility for it to get rid of punishment and escaping away with stolen funds
• End-to-end proof between the two parties involved in a transaction (actually their wallets), besides conventional confirmations in the chain, Alice sends additional proofs directly to Bob to convince him about the validity of her inputs. Todd discusses a series of scenarios including z-SNARK (zero-knowledge Succinct Non-interactive ARgument of Knowledge) which he suspects for its vulnerability to implementation bugs and being "bleeding edge crypto" scheme and not supporting recursion (which is not exactly true tho, for instance this is an updated version of a 2013 paper introducing a computationally complete version of zk-SNARK) plus an idea of his own: treechain which for some unknown reason he insist to take advantage of such a technique (end-to-end proof) to consolidate transactions in such a scheme (instead of conventional top-down hash commitments);
  
• He asserts that the most important issue with sharding is its complexity and resulting fragility.

Regarding his treechain idea, Todd concludes:

Ultimately though this isn’t magic: like it or not lower subchains in such a system are inherently weaker and more dangerous than higher ones, and this is equally true of any sharded system. However a hierarchically sharded system like treechains can give users options: higher subchains are safer, but transactions will [be] expensive.

I have reasonable doubts regarding "low-security" assumption about shards, most importantly I denounce the abstract idea of security applicability in the context of blockchains in which we need to  use incentives against costs trade-offs in security assessments.
Todd has given up with sharding, possibly because of his abstract understanding of security,  still there are some crucial contributions from his side to be appreciated:
1) Infeasibility of fraud-proofs and Slasher-like algorithms.
2)Introducing the concept of End-To-End proofs to sharding technical field.
3)Introducing hierarchical multi-level schemes in sharding and mentioning its relevance to security requirements.

Putting these all together, I've come to a solution for sharding which will share with the community asap but for the time being, let's discuss an interesting point:

If a hypothetical multi-layer sharding strategy is supposed to have weak security in the most bottom level of the tree, wouldn't it be feasible to have micro payments with very low security requirements to be handled on such supposedly "weak" sub-chains?

[Wind_FURY]

Todd's article is based on the common assumption about sharding: shards are vulnerable to 51% attack and not secure as much as the legacy monolithic blockchains.

But if miners split up to mine the different shards, then isn't it a common-sense, and logical statement?

I believe this previous topics might be of help to you,
Shardcoin - A Blockchain Partitioning / Sharding proposal
Can Bitcoin blocks be organized into shards?

Nothing in the links you shared is what I am looking for. Shardcoin? Hahaha.

[mda]

Miners don't need to mine different shards, they can form pools that have enough resources to mine a big block. But users download and verify only their own shard, this is the whole point of sharding.

[aliashraf]

Todd's article is based on the common assumption about sharding: shards are vulnerable to 51% attack and not secure as much as the legacy monolithic blockchains.

But if miners split up to mine the different shards, then isn't it a common-sense, and logical statement?

common sense is what one should get rid of to start logical reasoning, imo.  

Sharding means less hashpower for each shard but less hashpower does not mean less security necessarily. Security is not an abstract concept, as I've mentioned above. There should be an ugly trade-off between incentives and costs of attacks, to be worried about the security of a network.

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

 

[Wind_FURY]

Todd's article is based on the common assumption about sharding: shards are vulnerable to 51% attack and not secure as much as the legacy monolithic blockchains.

But if miners split up to mine the different shards, then isn't it a common-sense, and logical statement?

common sense is what one should get rid of to start logical reasoning, imo.  

What? Haha.

Sharding means less hashpower for each shard but less hashpower does not mean less security necessarily. Security is not an abstract concept, as I've mentioned above. There should be an ugly trade-off between incentives and costs of attacks, to be worried about the security of a network.

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

For micropayments, it might be. Then what about all the other transactions that are not micropayments? Is your proposal going to separate micropayments from larger payments?

[d5000]

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

In my opinion, it depends. If all what an attacker can do is double-spend the payments, then it is secure enough.

But there may be scenarios or configurations where an attacker can create coins out of thin air (e.g. in a shard modelled after the sidechain model, where he imposes a soft-fork to get higher block rewards) or even manipulate a two-way-peg between shards/sub-chains.

In these cases, or in cases of continuous attacks on low-hierarchy chains, the attack could probably affect the value of the currency, too: The value proposition of the currency (e.g. Bitcoin) would depend, among other factors, on scalability; so if attackers continuously attack lower-hierarchy shards, then it becomes obvious that low-hierarchy chains are not really viable, and thus that would affect the "scalability proposition". However, if there are other alternatives - like LN - then the effect may be negligible. This is also an argument, imo, to try different scaling strategies and not only one.

[aliashraf]

Sharding means less hashpower for each shard but less hashpower does not mean less security necessarily. Security is not an abstract concept, as I've mentioned above. There should be an ugly trade-off between incentives and costs of attacks, to be worried about the security of a network.

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

For micropayments, it might be. Then what about all the other transactions that are not micropayments? Is your proposal going to separate micropayments from larger payments?

Let's approach it one by one. So, micropayments could be handled by small shards despite such shards are commonly considered insecure, right? It's what I mean about not relying on common sense, it tells us small shards are insecure but still we've found a use-case for them: micropayments.

Now suppose at a given height, based on tx hash being odd or even we split current bitcoin network to three shards:
1) The parent:

• Nodes that maintain this shard are just ordinary full node with complete history and state database.
• Blocks in this are committing to blocks with same height in the two lower shards.

2,3)The leafs (odd and even):

• Each leef node supports just odd or even half of the state.
• Transactions are to be odd (having odd id) to spend odd utxos and even to spend even ones (no intrashard txn at all)
• Miners generate odd/even blocks (having odd/even coinbase transaction) with odd/even transactions.

We would impose other rules as well:
- Leaf nodes are spvs for the parent and their sibling.
- Block interval of leaf shards is half of parent's block time.
- By committing to leaf chains, Blocks in parent shard use their sub-shards difficulty as part of their difficulty calculation to compete in the mainchain.
- Being a spv for other shards, every shard is aware of its difficulty ratio and the amount of inflation its blocks should allocate to the miner.
- Leaf blocks are chained by committing to either a) previous block , b)latest parent block.
- A leaf block, pointing to an old parent block not being committed by a later parent block is considered orphan.
- Leaf shards validate parent blocks one step further than a simple spv: they validate the part of block that is committed to their shard.

And there is more to add, in the above scheme a high profile txn should be treated by the receiver as confirmed when parent shard has confirmed it. I'm not trying to present this scheme completely here, just making a simple point: Security is not an abstract binary concept: secure/insecure. In a hierarchical sharding schema you are free to wait for higher level chains to confirm enough if you are paranoid or doing a high stake business with some one and at the same time feel free to accept few satoshis for a cup of coffee as soon as it appears on the lowest level subshard.

What i explained above is an example to show how feasible sharding would be.

[aliashraf]

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

In my opinion, it depends. If all what an attacker can do is double-spend the payments, then it is secure enough.

But there may be scenarios or configurations where an attacker can create coins out of thin air (e.g. in a shard modelled after the sidechain model, where he imposes a soft-fork to get higher block rewards) or even manipulate a two-way-peg between shards/sub-chains.

1- In my model there is no intra-shard transaction ever:
State is partitioned by means of  transaction id and new transactions are supposed to use utxns from a same shard and (by adding a nonce) should stay on the same shard as their inputs.

2- There is almost nothing an attacker would be able to do other than double-spending because higher level shards commit to the lower shards eventually.

In these cases, or in cases of continuous attacks on low-hierarchy chains, the attack could probably affect the value of the currency, too: The value proposition of the currency (e.g. Bitcoin) would depend, among other factors, on scalability; so if attackers continuously attack lower-hierarchy shards, then it becomes obvious that low-hierarchy chains are not really viable, and thus that would affect the "scalability proposition". However, if there are other alternatives - like LN - then the effect may be negligible. This is also an argument, imo, to try different scaling strategies and not only one.

What I'm thinking of is a top-down commitment (the parent finalizes childs, childs light-check the parent) from root to sub-chains. that makes any low cost attack totally void. What I'm working on is a good incentive mechanism for distributing hashpower in all depths of hierarchy. It wouldn't be enough to distribute rewards according to the ratio of difficulty of each shard against total network difficulty because fees are collected by miners in the leaf level but higher levels consume more resources to maintain larger state shards and validate bigger blocks.

[mda]

I don't see the point of this complexity. Why not just squeeze these two leaves in the same block. User downloads and verifies his leaf up to Merkle root because in Merkle tree transactions are arranged by shard. There is some overhead because Merkle paths are required to verify atomic swaps between shards but this can be reduced by grouping atomic swap transactions by shard as well. This overhead is actually the only restraint otherwise the scaling would be limitless.

Edit:
There is an additional small problem to consider. When we split a shard in two by transaction id to scale further, amounts of coins in two children will be different. Atomic swap rate between them will be nowhere near 1:1 leading to rampant speculation. Therefore users will have to anticipate these splits and divide their coins in advance to hedge value.

[aliashraf]

@mda,
I'm strongly against the necessity of any kind of intra-shard transactions and have proposed a solution to avoid such transactions:
Rule #1 : Any transaction should use inputs from same shard.
Rule  #2: Any transaction Id should fall in the same shard as of its inputs.

For a network consisted of 1024 leaf shards, a wallet could satisfy second condition by flipping a nonce in few microseconds for commodity mobile devices.

As of grouping transactions in blocks according to their shards, it is what exactly happens when a parent commits to child blocks by merging their hashes. In my proposed model,  leaf shards have their own chain which is usable for micropayments with low security requirements, upper level shards only commit to this chains (no ultra-shard transactions) for  consolidation and security purposes. The root chain consists of blocks that have the same structure as you are talking about: each block has a Merkle path partitioned recursively. Any node in any level can verify the subset of Merkle path it maintains necessary data for.

We are so close in our thoughts, mine is more complicated because I offer a gradual security level and give users freedom to wait for any level of security they wish. I can Imagine a root chain with few hours block time and leafs with 10 seconds. A multi million dollars transaction should wait to find its way to root chain and get 6 confirmations (like in 12 hours) but a 5 bucks payment for a cup of coffee is secured in few seconds.

[Wind_FURY]

In the last paragraph of above post, i've returned to this issue by asking a simple question: isn't a shard with very low hashrate secure enough for micropayments?

In my opinion, it depends. If all what an attacker can do is double-spend the payments, then it is secure enough.

But there may be scenarios or configurations where an attacker can create coins out of thin air (e.g. in a shard modelled after the sidechain model, where he imposes a soft-fork to get higher block rewards) or even manipulate a two-way-peg between shards/sub-chains.

In these cases, or in cases of continuous attacks on low-hierarchy chains, the attack could probably affect the value of the currency, too: The value proposition of the currency (e.g. Bitcoin) would depend, among other factors, on scalability; so if attackers continuously attack lower-hierarchy shards, then it becomes obvious that low-hierarchy chains are not really viable, and thus that would affect the "scalability proposition". However, if there are other alternatives - like LN - then the effect may be negligible. This is also an argument, imo, to try different scaling strategies and not only one.

Crypto-politics might also come into play. Because sharding has widened Bitcoin's attack surface, then it will be attacked, maybe by Bitcoin Cash supporters, Core haters, or state-sponsored attackers. It would also be profitable to do it because the attackers can create doubt, and short sell Bitcoin.

[aliashraf]

Crypto-politics might also come into play. Because sharding has widened Bitcoin's attack surface, then it will be attacked, maybe by Bitcoin Cash supporters, Core haters, or state-sponsored attackers. It would also be profitable to do it because the attackers can create doubt, and short sell Bitcoin.

َAlthough I do agree with you and @d5000 to have such factors considered, it is worth mentioning that basics come first in the context of discussing fundamental issues like sharding.

For instance, in my hierarchical sharding proposal, we deliberately "widen the surface" to let both utilities (micropayments) and attacks become reasonably cheap, users enjoy instant micropayments as long as the shard is not attacked and when an attacker with like 1/1000 hashpower (which is still huge) for political reasons takes over a shard, users start to wait for upper level confirmations now the attacker need to undertake multiple times of more costs to dominate upper level shard and forcing users to wait even more (by committing to higher level shards). The safety measure is always the same: wait more to be safe more.

The interesting point in this scenario is built-in damage control: to cause a serious damage attackers need to undertake orders of magnitude higher costs. From a game theoretic  point of view such a system is considered secure. Actually in this regard my proposal is much safer than what bitcoin is now because with current topology a reckless trader may commit to a high stake transaction with less than secure confirmation numbers and remain exposed to a short-range chain rewrite attack because unlike what most people think you don't need  50%+1 hashrate for double-spending in bitcoin:
an attacker with 10% hashrate has a rough 20% chance to commit a one block rewrite attack! i.e. If an attacker with 10% power could convince traders to release funds with 1 confirmation after few trades he would be able defraud some of them by making the last block orphan and double-spending the funds.

[Wind_FURY]

Crypto-politics might also come into play. Because sharding has widened Bitcoin's attack surface, then it will be attacked, maybe by Bitcoin Cash supporters, Core haters, or state-sponsored attackers. It would also be profitable to do it because the attackers can create doubt, and short sell Bitcoin.

َAlthough I do agree with you and @d5000 to have such factors considered, it is worth mentioning that basics come first in the context of discussing fundamental issues like sharding.

For instance, in my hierarchical sharding proposal, we deliberately "widen the surface" to let both utilities (micropayments) and attacks become reasonably cheap, users enjoy instant micropayments as long as the shard is not attacked and when an attacker with like 1/1000 hashpower (which is still huge) for political reasons takes over a shard, users start to wait for upper level confirmations now the attacker need to undertake multiple times of more costs to dominate upper level shard and forcing users to wait even more (by committing to higher level shards). The safety measure is always the same: wait more to be safe more.

The interesting point in this scenario is built-in damage control: to cause a serious damage attackers need to undertake orders of magnitude higher costs. From a game theoretic  point of view such a system is considered secure. Actually in this regard my proposal is much safer than what bitcoin is now because with current topology a reckless trader may commit to a high stake transaction with less than secure confirmation numbers and remain exposed to a short-range chain rewrite attack because unlike what most people think you don't need  50%+1 hashrate for double-spending in bitcoin:
an attacker with 10% hashrate has a rough 20% chance to commit a one block rewrite attack! i.e. If an attacker with 10% power could convince traders to release funds with 1 confirmation after few trades he would be able defraud some of them by making the last block orphan and double-spending the funds.

But instead of "micro-payment shards", why not a micro-payment, off-chain layer developed, and built on top of the Bitcoin blockchain?

I believe there is already one, called the Lightning Network.