3 ms·
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
by 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 agoindeed: you're typically not interested in the optimum, but only in something that's good enough.
- hansvm 5y agoWhich is often still expensive (not the case here) -- iirc even approximating a Bayesian network is NP-complete.
- whatshisface 5y agoAn 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 agoSo they turned it into the knapsack problem.
- j_walter 5y agoEssentially the knapsack problem or any other TSP problem where greedy algos get you the optimal or near optimal solution.
- jonreiter 5y agonearly 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."