Shardcoin - A Blockchain Partitioning / Sharding proposal

[ripper234]

When I saw this question about sharding, my initial reaction was "No, the blockchain can't be split into shards".

But, on second and third thought - the major problem that I see is that you have to be able to send funds between the different shards. What if you could just trade, via an easy API, coins from one shards into coins of another shard, and then send those to the recipient?

Let's call this hypothetical concept Shardcoin. We would launch 10,000 new blockchains, and miners could choose randomly which chain they want to work on at any given time, reducing their bandwidth/memory footprint by a factor of 10,000.

Now, each of these miners, and other players in the market, would create exchanges between the different chains. I'm suggesting miners may double as exchanges because they're always-on servers ... no reason not to bundle an exchange there too (it won't be obligatory of course).

In order to send money:
 - Suppose I have 100 coins on Shard 17, and I want to send them to some address on Shard 9971.
 - I generate a new address for myself on Shard 9971.
 - Suppose the current exchange rate between these shards is 1 Shard17Coin = 0.8 Shard9971Coin.
 - I find someone willing to trade, and in one atomic tx, send him my 100 Shard17Coins, in exchange for 80 Shard9971Coins, minus his commision. Again, this is done atomically, so I don't really need to trust him to "hold my money" or anything like that.
 - I now am the proud owner of 79 Shard9971Coins, which I can send to my original target.

I'm not following the other scalability suggestions, so this all might be redundant if a better solution is proposed & implemented. But at least as a thought experiment, I rather like it. I see two major issues:

 - Fluctuation in the relative values of the different ShardCoins.
 - Adoption/network effect. Since there is effectively zero change Bitcoin will be dropped in favor of ShardCoin, this will never pick up enough steam to be successful. Bitcoin is already Too Big to Fail IMO.

A major point that's important to get across is that this is 100% compatible with the Bitcoin protocol - no changes whatsoever are needed. In fact, this proposal can work across crypto-currencies - so we could have p2p exchanges of Bitcoin, Litecoin & ShardCoins all working seamlessly together.

[1715273177]

1715273177

[1715273177]

1715273177

[1715273177]

1715273177

[1715273177]

1715273177

[1715273177]

1715273177

[jojkaart]

I think the design needs to be able to transfer coins between the shards to work. 10000 exchange rates is a bit too much. Even a very slow transfer between different chains would work.

[BoardGameCoin]

No exchange rate necessary: Simply make an address on each shard and send to yourself.

For me, this is on the critical path for wide bitcoin adoption. There are many different possible approaches, but it will become necessary in order to support even modest transaction volume.

-bgc

[ripper234]

No exchange rate necessary: Simply make an address on each shard and send to yourself.

I don't see how this works. You create an address for yourself on each shard. Now, you get your first coins from somewhere. These coins are on one specific shards, because you don't want to broadcast each action on each shard - that would be pointless.

So now, you only have Shard17Coins, but have zero Shard9971Coins. How do you get Shard9971Coins without exchanging them? Remember, the chains are completely separate.

[BoardGameCoin]

I should clarify: The way I view this is a hierarchical sharding where exchanges between shards occur at the next level in the hierarchy. Only the top level shard generates coins, but it also hashes in its view of the next lower shards' blockchains so a doublespend is just as hard as the highest level's hash rate. I'll write/code this up at some point...

-bgc

[BoardGameCoin]

You would probably get some value-drift between shards in the same way that 1EUR doesn't buy the same amount in different countries, so there would probably be a secondary exchange market. Also, it would take ~log(n) extra confirms so moving money between shards would take sometime without a secondary exchange.

-bgc

[ripper234]

I should clarify: The way I view this is a hierarchical sharding where exchanges between shards occur at the next level in the hierarchy. Only the top level shard generates coins, but it also hashes in its view of the next lower shards' blockchains so a doublespend is just as hard as the highest level's hash rate. I'll write/code this up at some point...

-bgc

This requires a more precise stating.
What I suggest is different - a complete, symmetrical sharding without hierarchies.

[Meni Rosenfeld]

If the shards are designed in advance to recognize each other, you don't need to mess with exchange rates and finding someone to trade with you.

All you need is a modification that new coins can be created in a shard, if there is a transaction that destroys coins in another shard and encodes information about the receiving shard and address. So to send coins from shard 1 to shard 2 you destroy them on shard 1, and broadcast a transaction on shard 2 where the input is a reference to the transaction from shard 1, together with its entire Merkle branch.

Nodes will need the entire blockchain of their shard, as well as block headers of all shards, and Merkle branches of every transaction from another shard to theirs. So instead of all transactions, they need (1/N) of transactions plus branches of (1/N) of the transactions. If a transaction is 500B and a Merkle branch is 1.5KB this can be an improvement even without N too large. But they also need N times the block headers.

All shards will be merge-mined with each other.

As a further optimization, instead of all block headers you could have headers of only X% of the shards. Then to send a transaction you need to find someone in the target shard which has the headers for the source shard.

I think I like this idea. And I wonder if the above ideas can be integrated into a more seamless way to shard the blockchain.

Another idea: Maybe it will be good to recommend to people to choose a shard based on geographical location. So local transactions can be done with the least latency and without crossing shards.

[ripper234]

If the shards are designed in advance to recognize each other, you don't need to mess with exchange rates and finding someone to trade with you.

All you need is a modification that new coins can be created in a shard, if there is a transaction that destroys coins in another shard and encodes information about the receiving shard and address. So to send coins from shard 1 to shard 2 you destroy them on shard 1, and broadcast a transaction on shard 2 where the input is a reference to the transaction from shard 1, together with its entire Merkle branch.

Nodes will need the entire blockchain of their shard, as well as block headers of all shards, and Merkle branches of every transaction from another shard to theirs. So instead of all transactions, they need (1/N) of transactions plus branches of (1/N) of the transactions. If a transaction is 500B and a Merkle branch is 1.5KB this can be an improvement even without N too large. But they also need N times the block headers.

All shards will be merge-mined with each other.

As a further optimization, instead of all block headers you could have headers of only X% of the shards. Then to send a transaction you need to find someone in the target shard which has the headers for the source shard.

I think I like this idea. And I wonder if the above ideas can be integrated into a more seamless way to shard the blockchain.

Another idea: Maybe it will be good to recommend to people to choose a shard based on geographical location. So local transactions can be done with the least latency and without crossing shards.

I think shard recommendation is not that useful. The overhead of communicating to a miner far away isn't that large.
I wonder if your idea is feasible, I'm not that versed in the details. Perhaps it could use some more formalization, and I would like some other Bitcoin devs to give feedback. If it works, then it might be the best solution to scalability.

[BoardGameCoin]

My belief is that we need both tx-out summaries and sharding in the long term. How we will get these and when (if ever) is the subject of quite a few threads at the moment =)

-bgc

[Realpra]

Shards

Your solution would work.

In fact its probably a much simpler swarm client proposal than mine, there is just a few issues:

You also split the miners hashing power which makes each shard less safe.
Anyone could make a new shard.
Confusion
Low adoption rate.
(You mentioned some of this yourself)


My proposal has the same idea as yours, but nodes trade tx data instead of exchanging coins and block-branches are split instead of the entire chain. That way there is no fork etc..

[casascius]

If there was partitioning to be done, I think a more sensible way to partition would be based on rough transaction size, rather than geographical location.  Different policies could then be applied to different partitions.

An illustrative example:

Micropayments ought to be partitioned away from transactions that are more like bankwires (funding loans for houses, cars, buying bulk shipments of goods for resale, etc.)

On micropayments you value speed and convenience and low transaction cost over the risk of fraud and double spending.  On bankwires you value irreversibility over confirmation speed and perhaps transaction cost.

[Meni Rosenfeld]

You also split the miners hashing power which makes each shard less safe.

Merged mining.

Anyone could make a new shard.

With my proposal all shards have to recognize each other, so someone can't single-sidedly start a shard.

Low adoption rate.

There can be a direct upgrade path from the current Bitcoin.

[casascius]

Here is one fundamental problem I could think of with respect to shard chains, and that's the possibility of a chain reorg on one shard invalidating transactions that have been spent on another shard.

Assuming shards are merge mined, there are two possibilities: either merged mining all shards is not mandatory (like today), or it is mandatory.

If mining all shards is not mandatory, then a chain reorg is possible, and so would the possibility of cascading invalidations of transactions on other shards.  One would need to track all the shards in order to exclude that as possible.

If mining all shards is mandatory, then the shards aren't offering any real benefit.  Rather, the only benefit is that non-miners can function with no block chain or a subset of the block chain.  But these benefits can already be realized with the simple "meta tree" proposal already being discussed on another thread, without needing to actually move coins between chains; to the extent this is true, the shards would offer no further benefit.

[Meni Rosenfeld]

If mining all shards is mandatory, then the shards aren't offering any real benefit.  Rather, the only benefit is that non-miners can function with no block chain or a subset of the block chain.

Can you explain? I'm not an expert on MM but the way I see it everyone will have all the block headers of all shards, and Merkle branches of special transactions that have to do with MM. If there's a reorg they know about it from the block headers. They don't need to store all transactions of all shards.

[casascius]

If mining all shards is mandatory, then the shards aren't offering any real benefit.  Rather, the only benefit is that non-miners can function with no block chain or a subset of the block chain.

Can you explain? I'm not an expert on MM but the way I see it everyone will have all the block headers of all shards, and Merkle branches of special transactions that have to do with MM. If there's a reorg they know about it from the block headers. They don't need to store all transactions of all shards.

Mining a chain requires a comprehensive and conclusive ability to validate transactions on the chain. One cannot mine a chain with just the headers (unless they are getting them from somewhere else e.g. centralized pool mining).   So, to merge mine all shards, one must be tracking them all - negating the benefit of separating them.

[Meni Rosenfeld]

If mining all shards is mandatory, then the shards aren't offering any real benefit.  Rather, the only benefit is that non-miners can function with no block chain or a subset of the block chain.

Can you explain? I'm not an expert on MM but the way I see it everyone will have all the block headers of all shards, and Merkle branches of special transactions that have to do with MM. If there's a reorg they know about it from the block headers. They don't need to store all transactions of all shards.

Mining a chain requires a comprehensive and conclusive ability to validate transactions on the chain. One cannot mine a chain with just the headers (unless they are getting them from somewhere else e.g. centralized pool mining).   So, to merge mine all shards, one must be tracking them all - negating the benefit of separating them.

Does a Bitcoin node merged-mining Namecoin need to know all Namecoin transactions? I was under the impression that no, he needs only to know the Namecoin block header, and to include a Bitcoin transaction acknowledging it. If that's true, then a miner of a shard doesn't need to know all transactions of other shards to MM them.

[casascius]

Does a Bitcoin node merged-mining Namecoin need to know all Namecoin transactions? I was under the impression that no, he needs only to know the Namecoin block header, and to include a Bitcoin transaction acknowledging it. If that's true, then a miner of a shard doesn't need to know all transactions of other shards to MM them.

If he knows only the Namecoin block header, then at best he can mine empty namecoin blocks.  That might help him get some namecoins, but it won't help the network confirm any new namecoin transactions.  Mining from a block header would be the cryptocurrency equivalent of rubberstamping whatever transactions were already there without making any efforts to confirm their validity, which is dangerous for the network if it becomes popular.  Somebody has actually got to be validating the transactions so new transactions will confirm, and if that somebody is only one or two or a few people and the rest are rubberstamping the work of a few, then you have the equivalent of deepbit.  May as well just start up a mining pool.

[vamdor]

And what is the incentive to keep these shards alive? It seems to me that eventually everyone would end up on the same shard, as that makes life much easier, allowing to avoid the extra "exchanges". Without a monetary incentive encouraging people to move to the lesser utilized shards, I don't think this could work on the long term.

[ribuck]

And what is the incentive to keep these shards alive? It seems to me that eventually everyone would end up on the same shard, as that makes life much easier, allowing to avoid the extra "exchanges".

I think it would be desirable to specialize the shards. I do like the idea that there could be a micropayments shard. The incentive to keep it alive would be that the fees are lower. And the fees would be lower because the design would be more lightweight than the main shard. Perhaps, on the micropayment shard, unspent balances would need to be carried forwards every 30 days so that the micropayment shard remains compact.

[crazy_rabbit]

I think the question is what problem does this really solve? One reason Bitcoin gains value is because it becomes a more and more scarce over time. Opening up new "shards" to mine might *seem* like it gives a new wave of people a chance to get rich in the future, but it's no different then an alt-chain really. If you can send "shard" coins to the main blockchain, it's just another chain hence, coin. One of the fundamental basics of Bitcoin is that the inflation is predetermined and limited. "Shards" just opens the chain to hyperinflation. The idea is contrary to the whole point, IMHO.

 

[BoardGameCoin]

The problem that it solves would be ONLY transaction volume handling. If bitcoin grows much more, miners will have a lot of churn updating blocks to include the new transactions from the last few seconds. We're not too far off from the max size of a block. The way I envision this happening does not include any new coins for the miners of the shard, and so financing it is one of the problems to solve.

-bgc

[ripper234]

I think the question is what problem does this really solve? One reason Bitcoin gains value is because it becomes a more and more scarce over time. Opening up new "shards" to mine might *seem* like it gives a new wave of people a chance to get rich in the future, but it's no different then an alt-chain really. If you can send "shard" coins to the main blockchain, it's just another chain hence, coin. One of the fundamental basics of Bitcoin is that the inflation is predetermined and limited. "Shards" just opens the chain to hyperinflation. The idea is contrary to the whole point, IMHO.

The problem being attacked is how to scale the blockchain to world scale.

If it could be implemented like a stock split somehow, that would be ideal. Stocks split don't devalue the stocks, they just play with the numbers a bit - owner of $10,000 worth of Apple stocks will remain in possession of $10,000 worth of the stocks after a split.

[edmundedgar]

When I saw this question about sharding, my initial reaction was "No, the blockchain can't be split into shards".

But, on second and third thought - the major problem that I see is that you have to be able to send funds between the different shards. What if you could just trade, via an easy API, coins from one shards into coins of another shard, and then send those to the recipient?

Let's call this hypothetical concept Shardcoin. We would launch 10,000 new blockchains, and miners could choose randomly which chain they want to work on at any given time, reducing their bandwidth/memory footprint by a factor of 10,000.

Now, each of these miners, and other players in the market, would create exchanges between the different chains. I'm suggesting miners may double as exchanges because they're always-on servers ... no reason not to bundle an exchange there too (it won't be obligatory of course).

In order to send money:
 - Suppose I have 100 coins on Shard 17, and I want to send them to some address on Shard 9971.
 - I generate a new address for myself on Shard 9971.
 - Suppose the current exchange rate between these shards is 1 Shard17Coin = 0.8 Shard9971Coin.
 - I find someone willing to trade, and in one atomic tx, send him my 100 Shard17Coins, in exchange for 80 Shard9971Coins, minus his commision. Again, this is done atomically, so I don't really need to trust him to "hold my money" or anything like that.
 - I now am the proud owner of 79 Shard9971Coins, which I can send to my original target.

I'm not following the other scalability suggestions, so this all might be redundant if a better solution is proposed & implemented. But at least as a thought experiment, I rather like it. I see two major issues:

 - Fluctuation in the relative values of the different ShardCoins.
 - Adoption/network effect. Since there is effectively zero change Bitcoin will be dropped in favor of ShardCoin, this will never pick up enough steam to be successful. Bitcoin is already Too Big to Fail IMO.

A major point that's important to get across is that this is 100% compatible with the Bitcoin protocol - no changes whatsoever are needed. In fact, this proposal can work across crypto-currencies - so we could have p2p exchanges of Bitcoin, Litecoin & ShardCoins all working seamlessly together.

If I've got this right, since addresses are basically just key pairs, you wouldn't need to send your coins to an _address_ on Shard 9971. All addresses would work on all the shards. That reduces the risk that different shards will have different values, because the vendor asks you to pay X coins to address xyz, they wouldn't know which shard the money would be coming in on. If all the coins on all the shards buy the same amount of stuff, they all have the same value.

So if you had 100 coins on Shard 17, you could just send them to a vendor's address on Shard 17. When the vendor wanted to spend them, they would also send those coins on Shard 17. Most of the time you wouldn't need to make atomic transactions across chains or anything difficult like that. Obviously everybody's client would need access to enough data to do SPV on all the shards it had coins on.

The fact that the money was split into different Shards could mostly be hidden from the end-user, in the same way that it currently hides the fact that your coins are made up of different amounts in different outputs. The only time you'd have a problem would be when you wanted to send 100 coins at once, but you had 40 coins on Shard 17 and 60 coins on Shard 9971. In that case you'd have two options:
1) Send two transactions, one on Shard 17 and the other on Shard 9971. The vendor will give you your stuff when they get both. (Again the client could take care of this without bothering you about it.)
2) If you need the whole payment in one transaction for some reason (maybe it's a fancy escrow contract or something), _then_ you have to swap with somebody on one of the other shards.

(2) may not turn out to be too important if (1) works well, but trading between shards wouldn't _necessarily_ have to be a clever atomic p2p thing. It could just be the equivalent of the current mixing operations - you send someone with a good reputation some coins on Shard 9971, and they send you some back on Shard 17. You might also have the client set to do these operations in the background to defragment itself and consolidate your coins among a smaller number of shards. Obviously having lots of people routinely taking part in mixing operations for routine, non-illegal purposes has some anonymity benefits, too...

Clearly there's a bit of inconvenience there compared to the current arrangement, but the advantage is that it would allow Bitcoin (or ShardCoin, if Bitcoin didn't want to do this) to scale unto infinity. Whereas right now everyone seems to think there's a point _somewhere_  where you can't scale because blocks get too big to transmit fast enough, or you run into some other limitation and fees go up to choke off demand. (People disagree about where this point is, and whether the community should decide by fiat or just let the miners figure it out.)

PS Scuse the thread necromancy.

[ripper234]

If I've got this right, since addresses are basically just key pairs, you wouldn't need to send your coins to an _address_ on Shard 9971. All addresses would work on all the shards. That reduces the risk that different shards will have different values, because the vendor asks you to pay X coins to address xyz, they wouldn't know which shard the money would be coming in on. If all the coins on all the shards buy the same amount of stuff, they all have the same value.

So if you had 100 coins on Shard 17, you could just send them to a vendor's address on Shard 17. When the vendor wanted to spend them, they would also send those coins on Shard 17. Most of the time you wouldn't need to make atomic transactions across chains or anything difficult like that. Obviously everybody's client would need access to enough data to do SPV on all the shards it had coins on.

It's a good question how the coins will behave economics wise. I mean it's possible some shards will have different kinds of activity - perhaps SatoshiDice like services would only work on a few shards, while other will be reserved for different activities. Or perhaps the shards will mostly just behave the same. Perhaps more coins will be lost on some shards than in others, thus increasing the value of the remaining cords from those shards.

There is no way to guarantee the same value for all shards, I think it's an interesting experiment to perform. If I were into launching altcoins I would perhaps do that myself - it's a simple matter to launch 1000 different shards, all equivalent to bitcoin except the starting nonce.

[edmundedgar]

If I've got this right, since addresses are basically just key pairs, you wouldn't need to send your coins to an _address_ on Shard 9971. All addresses would work on all the shards. That reduces the risk that different shards will have different values, because the vendor asks you to pay X coins to address xyz, they wouldn't know which shard the money would be coming in on. If all the coins on all the shards buy the same amount of stuff, they all have the same value.

So if you had 100 coins on Shard 17, you could just send them to a vendor's address on Shard 17. When the vendor wanted to spend them, they would also send those coins on Shard 17. Most of the time you wouldn't need to make atomic transactions across chains or anything difficult like that. Obviously everybody's client would need access to enough data to do SPV on all the shards it had coins on.

It's a good question how the coins will behave economics wise. I mean it's possible some shards will have different kinds of activity - perhaps SatoshiDice like services would only work on a few shards, while other will be reserved for different activities. Or perhaps the shards will mostly just behave the same. Perhaps more coins will be lost on some shards than in others, thus increasing the value of the remaining cords from those shards.

There is no way to guarantee the same value for all shards, I think it's an interesting experiment to perform. If I were into launching altcoins I would perhaps do that myself - it's a simple matter to launch 1000 different shards, all equivalent to bitcoin except the starting nonce.

I suppose it would be possible that some services would actually ask people to use particular shards, but it's not really clear they'd have much advantage from making their users jump through the extra hoop. I suppose it's possible that people would somehow decide that some shards were worth less than others, and that would become a self-fulfilling prophecy; I remember in Central Asia in the mid-90s people had somehow decided that older US dollars were worth less than new ones, so they were.

But to fend that kind of thing off I think you'd have to design it with the goal of making distribution of coins among the shards as arbitrary as possible. If you were starting with Bitcoin, you'd split the chain when it got too big and assign outputs to one or the other at random, rather than doing what people on this thread suggested and having different shards for different purposes.

[TierNolan]

- I find someone willing to trade, and in one atomic tx, send him my 100 Shard17Coins, in exchange for 80 Shard9971Coins, minus his commision. Again, this is done atomically, so I don't really need to trust him to "hold my money" or anything like that.

How do you do it atomically, if miners aren't monitoring all chains?

[ripper234]

- I find someone willing to trade, and in one atomic tx, send him my 100 Shard17Coins, in exchange for 80 Shard9971Coins, minus his commision. Again, this is done atomically, so I don't really need to trust him to "hold my money" or anything like that.

How do you do it atomically, if miners aren't monitoring all chains?

Atomic cross-chain trading is solvable for entirely different alt chains, so cross-shard trading is just a private case.

I must admit I do not fully understand Mike Hearns' explanation as presented, I suggest we use the wiki page to develop and clarify the solution as needed.