4 ms·

Sharding Is Also NP-Complete

40 points by jonreiter 5y ago

arka2147483647 5y ago
What is blockchain sharding? What does it do? Why do you need it?
- deleted 5y ago
  [deleted]
- isaacimagine 5y ago
  A single Blockchain is pretty slow. Sharing is processing transactions in parallel (potentially on different chains), while maintaining consistency between shared chains. Or something.
CJefferson 5y ago
I don't understand the aim of article at all, and I research NP-complete problems for a living. I am not however an expert in blockchains. Yes, sharing is NP-complete, but that's not, as far as I understand, a problem. Efficient scheduling of parcel delivery is NP-complete, the postal service runs fine, if probably slightly suboptimally. Why does it matter if we do what everyone had always done in this type of situation, and just have everyone love in the shard they choose, moving when they feel like it?
- polynomial 5y ago
  I wouldn't say "fine" but your point still stands.
tromp 5y ago
These articles are somewhat misleading. For instance, the earlier one claiming blockchain scaling to be NP complete, is based on the following notion of scaling: > The property we are going to look at is: reshuffling lists of ok-on-their-own transactions with a no-negative-balance requirement into a single merged list where the maximum number of possible transactions go through. They key word being "maximum". So they just equated scaling with an optimization problem. It's well known and not surprising that optimization problems are NP hard. I wouldn't even call this a scaling problem, since scaling is not about how to order things, but how to support higher transaction rates with fewer resources. Sharding is similarly defined as some assignment problem that is divorced from sharding practice by requiring that all of a given list of transactions is assigned to shards while satisfying certain constraints. It would be more appropriate to title these articles as "Optimal Scaling is NP-hard" / "Optimal Sharding is NP-hard". In practice, one just uses some efficient, usually greedy, algorithm to find near optimal solutions.
- toolslive 5y ago
  indeed: you're typically not interested in the optimum, but only in something that's good enough.
  - hansvm 5y ago
    Which is often still expensive (not the case here) -- iirc even approximating a Bayesian network is NP-complete.
    - whatshisface 5y ago
      An interesting subtle distinction is the one between problems that stay in the same complexity class as you loosen the approximation requirements and problems that drop to lower ones.
- hinkley 5y ago
  So they turned it into the knapsack problem.
  - j_walter 5y ago
    Essentially the knapsack problem or any other TSP problem where greedy algos get you the optimal or near optimal solution.
- jonreiter 5y ago
  nearly entirely agreed. the one quirk is if you are going to run arbitrary anonymous smart contract code and aim to support high-value transactions. because you can only get "nearly optimal" it's always possible to rig the system into a worst case. and if you promise low-low fees all the time that isn't expensive to do. here an attack against the approximation algorithm is an economic attack. you cannot attack approximations in a normal scheduling system like this of course. all of this is resolved if you do something as you say and add a defense mechanism (i.e. rapidly escalating fees or brownouts) when "near optimal"!="good enough."
woah 5y ago
> Earlier I said this would be a “general type of sharding” so let’s be clear about that. There are a bunch of shards. We make no assumptions about how the shards are connected or any use of proofs or anything like that. Our sharding coordinator can instantly move user’s balances across shards. It can also instantly assign trades to shards. The only thing that takes any time for this coordinator is deciding which balances and trades go where at the start of a block. Once it makes that decision the system runs. This should cover anything properly called a “sharding.” Odd statement. The system the author describes is decidedly not general. It is in fact a very specific and nuanced system.

40 points by jonreiter 5y ago

arka2147483647 5y ago

What is blockchain sharding? What does it do? Why do you need it?

deleted 5y ago
[deleted]
isaacimagine 5y ago
A single Blockchain is pretty slow. Sharing is processing transactions in parallel (potentially on different chains), while maintaining consistency between shared chains. Or something.

CJefferson 5y ago

I don't understand the aim of article at all, and I research NP-complete problems for a living. I am not however an expert in blockchains. Yes, sharing is NP-complete, but that's not, as far as I understand, a problem. Efficient scheduling of parcel delivery is NP-complete, the postal service runs fine, if probably slightly suboptimally. Why does it matter if we do what everyone had always done in this type of situation, and just have everyone love in the shard they choose, moving when they feel like it?

polynomial 5y ago
I wouldn't say "fine" but your point still stands.

tromp 5y ago

These articles are somewhat misleading. For instance, the earlier one claiming blockchain scaling to be NP complete, is based on the following notion of scaling: > The property we are going to look at is: reshuffling lists of ok-on-their-own transactions with a no-negative-balance requirement into a single merged list where the maximum number of possible transactions go through. They key word being "maximum". So they just equated scaling with an optimization problem. It's well known and not surprising that optimization problems are NP hard. I wouldn't even call this a scaling problem, since scaling is not about how to order things, but how to support higher transaction rates with fewer resources. Sharding is similarly defined as some assignment problem that is divorced from sharding practice by requiring that all of a given list of transactions is assigned to shards while satisfying certain constraints. It would be more appropriate to title these articles as "Optimal Scaling is NP-hard" / "Optimal Sharding is NP-hard". In practice, one just uses some efficient, usually greedy, algorithm to find near optimal solutions.

toolslive 5y ago
indeed: you're typically not interested in the optimum, but only in something that's good enough.
- hansvm 5y ago
  Which is often still expensive (not the case here) -- iirc even approximating a Bayesian network is NP-complete.
  - whatshisface 5y ago
    An interesting subtle distinction is the one between problems that stay in the same complexity class as you loosen the approximation requirements and problems that drop to lower ones.
hinkley 5y ago
So they turned it into the knapsack problem.
- j_walter 5y ago
  Essentially the knapsack problem or any other TSP problem where greedy algos get you the optimal or near optimal solution.
jonreiter 5y ago
nearly entirely agreed. the one quirk is if you are going to run arbitrary anonymous smart contract code and aim to support high-value transactions. because you can only get "nearly optimal" it's always possible to rig the system into a worst case. and if you promise low-low fees all the time that isn't expensive to do. here an attack against the approximation algorithm is an economic attack. you cannot attack approximations in a normal scheduling system like this of course. all of this is resolved if you do something as you say and add a defense mechanism (i.e. rapidly escalating fees or brownouts) when "near optimal"!="good enough."

woah 5y ago

> Earlier I said this would be a “general type of sharding” so let’s be clear about that. There are a bunch of shards. We make no assumptions about how the shards are connected or any use of proofs or anything like that. Our sharding coordinator can instantly move user’s balances across shards. It can also instantly assign trades to shards. The only thing that takes any time for this coordinator is deciding which balances and trades go where at the start of a block. Once it makes that decision the system runs. This should cover anything properly called a “sharding.” Odd statement. The system the author describes is decidedly not general. It is in fact a very specific and nuanced system.