Sharding strategy held together by atomic swaps

[fatca]

I wonder if the following sharding strategy would make sense?

Imagine that we split the bitcoin network in 256 subnetworks (shards), depending on the second byte of the address in the unspent output (the first byte is already in use for other purposes).

Addresses in network 0 can only be spent to other addresses in network 0. Same for network 1,2, 3, ... 255.

Miners keep mining in each of the sub-networks for the current coinbase divided by 256. They will receive the transaction fees for just the block in sub-network.

This sub-network affinity of funds sounds annoying, but it is probably less annoying than it looks like.

If you hold funds on network 47, and you need to pay to network 12, it means that there needs to be an atomic swap network, with atomic swap servers, where you can automatically swap network-47 funds for network-12 funds. You will have to pay an atomic-swap fee to the swapping server, but since it is a free trade, this fee should be rather minimal. The swapping can be completely automated between your wallet and the swapping server. After swapping for funds in network 12, the wallet can proceed automatically with making the actual payment.

Hence, you will potentially need to make three blockchain operations: an atomic swap (=two operations) and a normal payment. This will take twice as long as usual.

Still, your wallet can also indicate in what sub-network you have the largest amount of funds. From there, you can notify your payee your preferred sub-network for making payments and let the payee generate a payment address in exactly that sub-network. That will spare you the wait for the atomic swap and the swapping fee.

The advantage of using shards, is that it scales pretty much infinitely.

You just need to shard by one more byte, to multiply capacity again by 2⁸=256. So, sharding by two bytes, results in 65536 sub-networks. Sharding by three bytes, in 16777216 sub-networks. There should always be enough online, atomic swapping-server capacity available, because swap servers will find themselves attracted to growing swapping fees, in case of shortage. Your wallet will automatically pick the cheapest swapping fee.

Concerning instantaneous payments (lightning network), lightning nodes should be able to rout payments from your fund commitment in one sub-network to recipients in another sub-network. The existing contracting system should therefore remain the same. In fact, all existing smart contracts will continue to work. The only requirement is that the addresses involved in a smart contract must be valid for the sub-network in which the smart contract is being entered. It will just create a principle of "smart contract sub-network affinity".

Do you think that a sharding strategy for bitcoin could be viable? If not, let me know your objections!

[darosior]

You just need to shard by one more byte, to multiply capacity again by 2⁸=256. So, sharding by two bytes, results in 65536 sub-networks. Sharding by three bytes, in 16777216 sub-networks. There should always be enough online, atomic swapping-server capacity available, because swap servers will find themselves attracted to growing swapping fees, in case of shortage. Your wallet will automatically pick the cheapest swapping fee.

[...]

Do you think that a sharding strategy for bitcoin could be viable? If not, let me know your objections!

Hi,

This would divide the mining power by n (with n the numbers of sub networks), thus reduce the resilience of the network (how hard it would be for an attacker to modify the ledger) by a factor of n. Hence having "16777216 sub-networks" is not viable at all (and that's why Ethereum won't implement sharding before using PoS).

[fatca]

There are few flaws, especially on sharding (which you probably already know). But my biggest concern are :
1. How do we categorize address to different network?

You can add a header to the tx (for efficiency). However, you can already see it from looking at the first (few) byte(s) of any address involved in the unspent outputs and/or source tx. Mixing shard prefix would not be allowed. A single miner can mine for any of the sub-networks. To that effect, he needs to keep multiple blockchain databases (one for each sub-network).

2. How will it works when you have addresses on different network and you plan to make payment to multiple address from different network?

The wallet will have to split the tx (automatically and transparently) in one tx per sub-network you are paying to. So, if you are paying to three addresses on three sub-networks, the wallet will broadcast three tx. You will need enough unspent output on each sub-network, but the initial swap will have to make sure of that.

Additionally, IMO this sounds like we have n different bitcoin coins.

Technically, yes, but in all practical terms, most probably not.
The atomic swap network would have to treat sub-networks differently, and e.g. charge different swapping fees per sub-network. Why would they do that?
Concerning the user, the user would need to have a preference for a particular sub-network, while they are indistinguishable.

Edit : adding reference and similar proposal
https://github.com/ethereum/wiki/wiki/Sharding-FAQs
https://bitcointalk.org/index.php?topic=5060909.0

> A UTXO can be spent to any other zone or region within the network by signing a new transaction  that  relocates  it  to  a  new  zone.

I propose to let the atomic-swap network handle this for a fee.

> the zones which users aggregate into will be based on a combination of geography, network topology, and  existing economic relationships.

It looks complicated. Why would that even be needed?

> The network incentives need to be modified to incentivize the regions and zones needed for BlockReduce.

In my proposal, the servers on the atomic-swap network can set their own fees and let market competition determine how much those should be.

> ... any excess transaction fees could be sequestered into an escrow account ...

... and who will be sitting on the corresponding private keys?

It is otherwise, indeed, a very similar proposal. I do not see the need, however, for a PRIME network or regional networks, or any other hierarchy. I think that it can be done with just one atomic-swap network.

[fatca]

This would divide the mining power by n (with n the numbers of sub networks), thus reduce the resilience of the network (how hard it would be for an attacker to modify the ledger) by a factor of n.

Yes. However, there is no requirement to have more sub-networks than desired. E.g. it could start out with just 5 sub-networks. All addresses in the tx would then all have to have the same (mod 5) modulo. There is not even a need to roll out all 256 sub-networks afforded by sharding the first byte.

Hence having "16777216 sub-networks" is not viable at all (and that's why Ethereum won't implement sharding before using PoS).

Yes, of course, indeed. It was just an indication as to how many sub-networks would be possible by sharding 3 bytes. I also do not believe that we would ever need to scale that far. It is rather that the principle allows for unlimited scaling.

There is obviously a need to figure out how to start sharding and with how many shards initially, and how to (automatically?) increase the number of shards when needed, but I assume that this problem does not need to be solved already. The deployment could cause a fork in the network. Therefore, allowing for the existing and the new situation to correctly co-exist will be a very real problem to solve, with a lot of nitty-gritty details to take into account. If I tried to dream up such details right now, on the spot, they would undoubtedly be grossly wrong.

[d5000]

This looks basically like a "sidechain world" without main chain.

An advantage could be the easier handling of addresses. But all other problems and challenges of sidechains would also be present in that model.

For example, as ETFBitcoin already wrote, there is a danger that the different "shard tokens" could not be entirely fungible and instead convert into several different "coins". This could happen, for example, if one chain becomes notably weaker (has less support by miners) than the others, is thus less secure, and people (above all those waiting for high BTC amounts) could then desist to accept coins from addresses of that shard.

To avoid that, you would need a two-way peg mechanism that ensures that you always can change one coin of one shard to another shard. That could be more difficult than in a sidechain world, because an active coin in a sidechain has to be blocked in the main chain to avoid the supply being diluted, and thus there is always a main chain coin available for people wanting to exchange sidechain coins for it. In this proposal, however, this is not the case - you would have to force atomic swap servers to accept an 1:1 rate (and if they don't accept then they may simply reject swaps coming from shards they don't like).

In my opinion, if I understood the proposal correctly, then the drivechain proposal is less difficult to implement, and is also more flexible.

[fatca]

This looks basically like a "sidechain world" without main chain.

Yes, but also without the "merge mining". I propose to make sure that the protocol gives convenient access to an atomic-swap market. In my impression, that should be enough to make the different sidechains look like one. As long as the wallet software does the hard work for you, of looking for atomic swaps, carrying them out, and then making the payments within the various sidechains, almost nothing changes for the user. The "send payment" button triggers more actions under the hood, but that's also about it.

But all other problems and challenges of sidechains would also be present in that model. For example, as ETFBitcoin already wrote, there is a danger that the different "shard tokens" could not be entirely fungible and instead convert into several different "coins". This could happen, for example, if one chain becomes notably weaker (has less support by miners) than the others, is thus less secure, and people (above all those waiting for high BTC amounts) could then desist to accept coins from addresses of that shard.

For the miners, not much will change either.

Instead of mining one block in one chain, they will mine 256 blocks in 256 subchains. Of course, they have the option of not mining for one subchain and only to mine for other ones, but why would they do that? Why would a miner mine in subchain 56 and not in subchain 89? It is equally difficult. The payoff is exactly the same. So, for all practical purposes, subchain 56 and subchain 89 are the same thing.

To avoid that, you would need a two-way peg mechanism that ensures that you always can change one coin of one shard to another shard. That could be more difficult than in a sidechain world, because an active coin in a sidechain has to be blocked in the main chain to avoid the supply being diluted, and thus there is always a main chain coin available for people wanting to exchange sidechain coins for it. In this proposal, however, this is not the case - you would have to force atomic swap servers to accept an 1:1 rate (and if they don't accept then they may simply reject swaps coming from shards they don't like).

The atomic-swap servers do not accept a 1:1 rate. As an atomic-swap server, you can buy at 0.90 from subchain 67 and sell at 1.15 in subchain 112. Nothing prevents you from doing that.

However, it is a free market, and there are other atomic-swap servers. Hence, in an open market, you are quite unlikely to find counter-parties for your 0.90/1.15 offer. It looks expensive. If you can make that much money by swapping, I will compete with you with my 0.95/1.10 offer, which is obviously still a lot of profit. So, don't be surprised that the market price will eventually turn out to be something like 0.9999999999/1.0000001.

Furthermore, if you are an atomic-swap server, you had better watch out for offering irrational prices or discriminate against arbitrary sub-chains, because automated arbitrage bots will not hesitate to take you to the cleaners. For example, if you accidentally happen to offer something like 0.98/0.99 or like 1.01/1.02, that will go wrong within seconds. You will find your coin buffers depleted almost immediately. Arbitrage bots are merciless. If they smell blood, you will be gone very fast. That is the same phenomenon as on any exchange market.

Atomic-swap servers provide liquidity. Hence, the size of the swapping fees will make sure to attract the liquidity for which the users will want to pay, by matching supply and demand. I suspect, however, that these fees will be very reasonable. Still, if you put 10 BTC on one subchain and 10 BTC on another, you obviously expect to get paid for keeping your money available for atomic-swap market takers. Otherwise, why would you do it?

In my opinion, if I understood the proposal correctly, then the drivechain proposal is less difficult to implement, and is also more flexible.

I think drivechain is an interesting idea. Still, it requires "blind merged mining". In this proposal, we do not need that. Tried and true atomic-swap smart contracts are enough to achieve the same. It is simply "time-locked payment against preimage" all over again.

Even though Tier Nolan introduced his multi-billion dollar idea of atomic swaps in this very forum in 2013 already, it still took until 2017 for someone to actually write the first prototype. In my impression, Tier Nolan's atomic-swap idea is much, much bigger than just trustless trading of altcoins. His idea will undoubtedly turn out to be gigantic. In my impression, atomic swaps can almost trivially solve the pernicious problem of sharding and allow for infinite scalability.

[aliashraf]

Do you think that a sharding strategy for bitcoin could be viable? If not, let me know your objections!

A sharding strategy works, but not yours ...

If you hold funds on network 47, and you need to pay to network 12, it means that there needs to be an atomic swap network,

It is the problem you are apparently trying to solve. But why this problem does ever exist? Because of your bad sharding strategy.

Firstly it is impractical:

• We have P2SH and segwit transactions that doesn't include RIPEMD-160 hash of a public key (a bitcoin address)
• We have m of n type utxos with multiple addresses included
• We have other non-standard transaction types as well.

.
Generally speaking, Utxos are not about addresses that receive money they are output scripts that may or may not contain one or more bitcoin addresses, hence it is not feasible to partition them with an address base strategy.

Secondly it causes the intra-shard problem (you try to solve by atomic swaps between shards) which is not solvable anyway unless for very simple use cases and with higher fees and it disturbs user experience and destroys seamless monolithic behavior of the network.

Thirdly your proposal is silent about the most important sharding problem: sharding of the state

Alternatively I support sharding based on transaction hash i.e. state sharding.
It would be easy to avoid intra-shard transactions (instead of dealing with them) by requiring wallets to follow simple rules that guarantees two key points:
1- Always spend from same shard in each transaction.
2- Make transaction to fall in the same shard as inputs by using a small entropy(nonce).

See? No intra-shard transactions, no need to swaps, no headaches. There is more to discuss about this scheme but I'm really busy with more urgent problems in bitcoin, so accept my apologies for not contributing actively.

[fatca]

Thirdly your proposal is silent about the most important sharding problem: sharding of the state
Alternatively I support sharding based on transaction hash i.e. state sharding.
It would be easy to avoid intra-shard transactions (instead of dealing with them) by requiring wallets to follow simple rules that guarantees two key points:
1- Always spend from same shard in each transaction.
2- Make transaction to fall in the same shard as inputs by using a small entropy(nonce).

Thinking of it. Yes.

It would indeed be possible to shard based on transaction hash instead of address, and guarantee shard affinity by using a small nonce. In that case, it would indeed be sub-network 12 because the tx hash starts with a 12 and not because the address starts with a 12. Sounds good to me. Adding the nonce is also a good idea (without which tx sharding would obviously not work).

See? No intra-shard transactions, no need to swaps, no headaches.

True. Your approach would be even simpler. I certainly like your simplification.

[aliashraf]

OP, appreciate your honesty and self-effacing. 

[d5000]

Yes, but also without the "merge mining". I propose to make sure that the protocol gives convenient access to an atomic-swap market. In my impression, that should be enough to make the different sidechains look like one. As long as the wallet software does the hard work for you, of looking for atomic swaps, carrying them out, and then making the payments within the various sidechains, almost nothing changes for the user.

This is an approach which could also be achieved with a main chain. Apart from that, your proposal looks a lot like "merged mining" if we consider the "shards" to be independent chains.

For the miners, not much will change either. Instead of mining one block in one chain, they will mine 256 blocks in 256 subchains. Of course, they have the option of not mining for one subchain and only to mine for other ones, but why would they do that?

For that to happen, the shards/sub-chains would have to be totally synchronized and the difficulty of all chains would have to be identic at all times. In all other cases, there will be times where it's more profitable to mine on a sub-group of sub-chains or even on one single sub-chain.

I think it's highly unlikely that the synchronicity of the sub-chains will be stable enough to not lead to some fluctuations in sub-chain difficulty. If the difficulty is forced to be equal in all sub-chains by the protocol, the risk emerges that one of the sub-chains still eventually could receive less mining power and then have longer block times. This chain would then become unattractive and the value of the "sub-chain coins" would fall.

Furthermore, if you are an atomic-swap server, you had better watch out for offering irrational prices or discriminate against arbitrary sub-chains, because automated arbitrage bots will not hesitate to take you to the cleaners.

Now imagine an attack on the atomic swap market by a big whale who could profit from it, driving the price of one of the sub-chains down for a longer time and create a loss for arbitrageurs who cannot sell their "cheap coins" for a higher price anymore (and taking also mining power away as the sub-chain coins aren't worth the same, creating a "domino effect").

There must be a strong peg mechanism, otherwise the peg eventually will be lost. NuBits, an early "stablecoin", for example, relied almost entirely on arbitrage bots, but the peg was lost in 2016 for the first time. It recovered (mainly because the coin developers injected lots of money) but now the coin has collapsed.

So the path to solve that would be a two-way peg like in the Drivechain proposal. I think it could be achieved, but without a main chain it would be much more complicated as all sub-chains would need the capacity to block coins when they're to be created on other chains.

Even though Tier Nolan introduced his multi-billion dollar idea of atomic swaps in this very forum in 2013 already, it still took until 2017 for someone to actually write the first prototype. In my impression, Tier Nolan's atomic-swap idea is much, much bigger than just trustless trading of altcoins. His idea will undoubtedly turn out to be gigantic. In my impression, atomic swaps can almost trivially solve the pernicious problem of sharding and allow for infinite scalability.

There was an implementation in 2014, but not for Bitcoin.

The problem of your proposal is mainly that your rely totally on market forces to achieve price pegs between the sub-chains. That can work, but it's not guaranteed at all and the system could collapse very fast (like NuBits). Perhaps there is a solution for that, a new form of two-way-peg mechanism, and then you could have found an interesting technology (although I think @aliashraf is right with his criticisms, too). But this problem has to be solved.

[fatca]

I think it's highly unlikely that the synchronicity of the sub-chains will be stable enough to not lead to some fluctuations in sub-chain difficulty. If the difficulty is forced to be equal in all sub-chains by the protocol, the risk emerges that one of the sub-chains still eventually could receive less mining power and then have longer block times. This chain would then become unattractive and the value of the "sub-chain coins" would fall.

I think you are right about the difficulty. It should certainly not be forced to be equal. Each shard must have its own.

There was an implementation in 2014, but not for Bitcoin.

Looks like an interesting application of the original atomic-swap idea!

The problem of your proposal is mainly that your rely totally on market forces to achieve price pegs between the sub-chains. That can work, but it's not guaranteed at all and the system could collapse very fast (like NuBits). Perhaps there is a solution for that, a new form of two-way-peg mechanism, and then you could have found an interesting technology (although I think @aliashraf is right with his criticisms, too). But this problem has to be solved.

I personally think that @aliashraf's alternative is actually better than my original proposal.

Sharding along tx hash bytes removes the need for an atomic-swap server network, which then becomes completely optional.

It also makes the question of price pegs between sub-chains moot.

The user may still want this network service for the occasional defragmentation of his bitcoin holdings. If the user's bitcoin holdings are too much spread out over different shards, then a typical payment may require sending a potentially large set of sub-txs, each to its own shard. Therefore, the user may, at times, still want to use the atomic-swap server network to regroup his bitcoin holdings to fewer shards.

[mda]

So miners get their fees with n shard transactions and block reward goes to a shard of their choosing (the most valuable one). All inter-shard transfers are done with atomic swaps. This way gigabyte blocks are no longer a problem.