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.

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