Bitcoin Forum

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.

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

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.

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.

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".

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?

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 (https://eprint.iacr.org/2013/879.pdf)) 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:
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?

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


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

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.

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?

 

What? Haha.


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?

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.

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.

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.

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.

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 (https://bitcointalk.org/index.php?topic=5102652.0) 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.

@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.

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. 8)

Because it is not bitcoin, and bitcoin is the only monetary system that is truly decentralized and censorship resistant. It is very easy to have 2nd layer applications that do excellent job on top of bitcoin but they involve either trust-->centralization or liquidity-->centralization just like LN.

It is more than obvious that an onchain solution is superior to any 2nd layer one no matter how fancy it would be. It is no magic, LN, you deposit some coins and bitcoin acts as an escrow thanks to its HTLC feature, the LN node does the same and you both now have a channel. When it comes to arbitrary trades the LN node needs to deposit even more with other nodes to act as a router and it escalates liquidity problem and puts people with more deposits in a central hub position eventually, it resembles traditional banking systems rather than cryptocurrency.

I understand LN now looks like an adventure but it is not bitcoin and it is very important to keep investigating onchain scalability solutions instead of saying:
"hey, LN solves everything why should we bother even thinking about improvements? Isn't it just more sensible to keep bitcoin safe and uncompromised and focus on LN?"
It is what they say, by the way, and it is where they are diverging from bitcoin without even being aware of their divergence! And it is sad. A decade of experiments and discussions and debates is just going to be denied because some guys are not good in strategy in spite of their expertise in math or coding.

Stop. Why is it "not Bitcoin", in your opinion? Because Bitcoins in Lightning channels are Bitcoins under multi-sig escrow, with transactions stored locally, that can be broadcasted on-chain at a later date, or time.

I think the nice thing about LN is though that it improves scalability without making any sacrifices on the lower layer.

That is, it does leave room for alternative scalability approaches as well. So while there's a lot of focus on LN right now I don't think that in practice it detracts that much attention from possible alternatives. There will be dev teams dedicated to other approaches just like dev teams are dedicated to LN right now. Maybe these approaches will end up as part of Bitcoin, maybe they won't. Point being, while many people may see LN as the scaling solution to end all scaling problems, many people don't. And those will still keep working on other ways to improve crypto.

Thank you for sharing your invaluable opinion. But what's your opinion on aliashraf's proposal of a low-security shard for Bitcoin micro-payments?

Plus in the context of that, wouldn't an off-chain layer for micro-payments be a more feasible solution?

The way Sharding is being 'attempted' on ETH only works for POS.  It does not work for POW.

The Reason :

They use sub-sampling of the POS stake holders to limit which accounts can mine which shard. It is impossible for more than the the allocated POS miners to mine a shard than the percentage allocated.

So 10% of the pos holders can mine each 10% shard. This changes every block. So you are randomly allocated a different shard to work on.

You can't do this in POW as there is no way of preventing a POW miner from adding his hash-rate to the shard of his choice. Subjective vs Objective miners.

I think this is a clever trick! But it does not fix the numerous other outstanding issues.

Clearly you MUST be allowed to perform transactions cross shard - or you destroy fungibilty. I have looked at the cross sharding communication algo.. err.. LOL! It's very complicated and messy. I still need to be shown _proof_  that this will in fact reduce traffic and not increase it.

The Security of the Shard-POS chain running the original ETH algo can be copied _exactly_. (As with ANY POS chain) In fact I can increase the security by simply increasing the distribution of stake. I can also charge less for gas.  Why would a new user choose a more expensive less secure chain ?  (You can't do this with POW)

Anyone who thinks this Hierarchical Tree Structure doesn't centralise faster than Usain Bolt - Is missing something.

I wish them Luck! I love seeing cool teck _attempted_ :)

..

(I'm way way down the rabbit hole myself at the moment..)

I don't think so. On the contrary cross shard transaction is exactly what you should prohibit to avoid complexities.
In my scheme, we keep any segment of the state self-contained and to resist state take-over attacks we have higher level shards in charge.
Keeping coins on same shard and avoiding cross-shard transactions would be easy by applying the two rules I've proposed before:
1- Transactions should use inputs from same shard.
2- Using a light nonce, wallets should guarantee the transactions they generate falling in the same shard with their inputs (which follow rule #1 any way).

Belonging to different shards do not make two utxos any different because they all belong to and are maintained by the root shard eventually. You can think of the root shard as a very slow, yet heavy blockchain with gigabyte blocks (like 4 GB) and long blocktimes (like 1-2 hours). Bitcoin using such a scheme scales up to 1500 tps and more.

Although the name hierarchical resembles such thing, it is not what it looks like in the first glance:
It is absolutely possible to make it hard enough for upper shards (maintained by fewer full nodes because of the costs) to do anything bad against the network by applying a new technique: collaborative proof of work. In my model, upper level shards are free to accumulate works done in their subshards as part of their proof.

To commit any sort of misbehavior ( intentional chain rewrites for double-spending, censorship attempts, ... ) they need to collide with their subshards or ignore the work they have encapsulated in their blocks.
Any miner in any shard has to provide a block with a total T work. To do this, the miner needs a nonce for the block header with T/2 difficulty and the Merkle root of the header should refer to two blocks from its left and right subshards with a total difficulty of at least T/2.
It is a bit more complicated and yes, it is really, really going down the rabbit hole. For instance it is not just about a subshard's single block difficulty, it is about a chain of blocks with unknown length that are being committed to an upper level block, and it is obviously recursive process, ...

Sharding is not simple problem but the solution should be kept as simple as possible it is why I don't like what they are doing in Ethereum, for now I'm becoming convinced that tree chain and hierarchical sharding is the most go direction.

Increasing the TPS means can be a security threat and we see sharding can be a solution but will sharding also be a security threat to a blockchain?

I think it was vitalik that said blockchain is meant to be slow like 300K transaction. If a blockchain can process more than 10K per second, it may have some security issues.

Hello Ali!


This is already done using altcoins. And for POS chains the security is stronger the wider the distribution of coins. I see no Security benefit to pooling POS coins. (POW chains are a different matter)

If you can't communicate cross chain, I would say it is preferable to have them separate - they can already communicate using smart contracts / HTLC / Layer2 etc.

Hi bro, we miss you here, why shouldn't you visit more frequently?

I know, thinking of altcoins as shards with no cross-shard transactions is so common but I think it is not just like that. Altcoins (and I'm talking about PoW coins) are different coins and as you've reminded above they are not fungible like a huge ultra coin. Fungibility is not a technical challenge to be solved by any means e.g. Atomic Swaps, it is about different values.

A PoW coin's value is basically determined by the average social work necessary to produce it (the costs of mining each unit). Labour Theory of Value (https://en.wikipedia.org/wiki/Labor_theory_of_value), proposed by Karl Marx more than a century and half ago, clearly describes why and how a Pow coin is valuable (and a PoS coin is not by the way  :P) and fungibility essentially is about coins to be of same value,

The beauty of a hierarchical scheme is its potential to take care of difficulty and fair generation of coins hence keeping the value of coins in any shard absolutely the same at any given time and making it irrelevant and a matter of protocol and not users' concern that a utxo belongs to which shard. What a user wants is the mere transfer of funds.

To be honest I haven't looked deep enough into blockchain sharding yet to give an educated opinion on aliashraf's proposal or any other sharding proposal for that matter. Additionally given the conservative nature of Bitcoin's development I have my doubts that Bitcoin will ever see a sharding implementation to begin with (for better or worse; except for hard forks by alternative dev teams, I suppose). In that regard I guess the closest that Bitcoin will ever come to a sharding-like approach is via sidechains.

In general I believe that 2nd layer solutions stand to scale way better than sharding. Main reason being that everything else being equal sharding only scales linearly with the amount of shards (ie. to increase transaction throughput tenfold you need 10 shards, to increase transaction throughput by n you need n shards) while in theory LN is only limited by the respective nodes' underlying internet connection and the laws of physics.

That being said, I also believe that on-chain transactions offer a better user experience than LN transactions due to the almost-always-online requirement of the latter. Whether on-chain transaction throughput can be sufficiently increased via sharding without significant sacrifices is a different matter however (and one where I still have a lot of reading to do).

Bitcoin will never see any sharding proposal implemented. Not especially a proposal that allows a part of the blockchain to be less secure for micro-transactions.

I made this topic more as an inquiry to learn more about "sharding", and to memefy sharding in Bitcoin once we truly understand what it is.

Regardless of that and my own personal doubts about sharding as a scaling approach I'm looking forward to see it in the wild. It seems to be quite an enormous task though, seeing how Ethereum's roadmap is currently placing sharding support at 2021 [1], but that might be mostly due to the challenges of upgrading a running system. That is, it might be different for a currency starting with sharding from scratch.

Anyone aware of any alts that use sharding?


[1] https://www.mangoresearch.co/ethereum-roadmap-update/

I only know of Ziliqa's sharding (https://cryptobriefing.com/zilliqa-mainnet-launch-sharding/) efforts already on mainnet. I've a soft spot for projects in my region, even if only to keep up with them on a cursory level. In fact, it was by some work circumstance I'd heard of it even before I'd heard about Ethereum's plans or even plasma... whether or not either implementation will ever be comparable to what may ever be considered for Bitcoin, I couldn't say.

Warning: that article's a bit of a shill but I suppose this is as good as it gets for a mature-ish implementation. Ziliqa's all about payments (almost all hot projects out of Singapore are now!) so let's see.

Me too, and especially in Ethereum. They have been promoting it as "scaling out", but with Ethereum's block size depending on gas limits, it might actually be scaling in.

I believe sharding is only a temporary solution for the inevitability of centralization of blockchains that utilizes big blocks.