Hacker News Reader

Comment by tradedash | Hacker News Reader

Serious question: if the processing problems are classified as NP, then couldn't that processing be outsourced to a blockchain? Why have miners solve for useless problems that have no long lasting impact like "number of zeros in a SHA string" instead of processing data such as this? I can easily see it being the case that the mining problem in a given blockchain could be based on real scientific problems that needs solving.

I'm looking for someone to help me understand why the above isn't possible.

View on HN

Seeing this genuinely suprised me. I have been working on exactly the same topic that you have mentioned. Coinami[0], Coin-Application Mediator Interface is a blockchain application where scientific problems are distributed like grid and solvers are awarded by cryptocurrency. I will not go into detail but our first prototype was distributing read mapping to volunteers.

Now, I will list the problems we have encountered along the way.

First, you need problem suppliers. Blockchain does not need a problem supplier, hash puzzle is adjustable.

Second, proof-of-whatever must be very easy to verify. I mean the ratio between solving proof-of-whatever and verifying it must be really high. Unfortunately, read mapping is not a problem like that. Yes it is still NPC but verification takes way longer time than what is required.

Finally, privacy concerns. You must use encrypted, anonymized and distributed data. Current read mapping techniques do not accommodate to such needs. There are proposals[1] to satisfy these requirements but they do focus on hybrid cloud techniques which means network bandwidth is not a concern for them. However, blockchain applications are greatly concerned with network bandwidth.

*edit: references

[0] https://arxiv.org/abs/1602.03031

[1] https://www.nature.com/articles/ncomms15311#

Thank you for posting this. I learned a lot about Coinami that I didn’t know.

Awesome! thanks for the reading material :D

1) The problem supply can be tackled in many many ways.

2) The verification problem is exactly why I stated NP as a problem class where the verification process is often relatively simple and straight forward. Obviously if that isn't the case then perhaps the problem isn't that well suited for this kind of environment.

3) The bandwidth issue is not something that I had considered. Makes absolute sense when you put it that way.

> The verification problem is exactly why I stated NP as a problem class where the verification process is often relatively simple and straight forward

Just for reference, don't forget that NP behaviour is displayed asymptotically. Checking a solution can still be pretty costly.

A blockchain is a data structure, it doesn't have processing power.

Miners solve for nonsense problems because that's the simplest kind that you could solve in order to make the proposition work, anything on top of that requires more complexity.

So it's not that it isn't possible, it's just that it would be charity from the point of view of the developers of the software to spend brain cycles on something they don't strictly speaking need to achieve their goals. I'm pretty sure that at some point there will be 'green' crypto currencies, let's call them 'greencoins' that make a play at avoiding the waste of energy that digital currencies are becoming associated with.

The same happened in other industries, I don't see why digital currencies would not be able to follow a similar path.

I think it’s clear what he meant and you’re being purposefully obtuse. If I said I was going to put a problem “on the internet” you would know I didn’t mean the netowrking infrastructure was going to produce a solution.

When Ethereum implements Proof of Stake it will be quite green. In my opinion this will be the death knell for wasteful PoW like bitcoin.

I thought about this as well before, but the problem is that you don't want just ANY NP-problem: You want an NP problem (it doesn't even have to be NP-complete) that you can easily adjust the difficulty.

How do you adjust the difficulty on something like this?

Also, you always have to calculate the "hashes" of the blocks. I guess you could encode a block as a graph and it's "hash" could be the smallest path that visited all the edges, but how useful would that be?

When I looked into this in the past, I stumbled into Gridcoin[1], but I don't know how they deal with the difficulty/usefulness of the solutions.

[1]: https://www.gridcoin.us/

Thanks for the link. I'll look into it!

> you can easily adjust the difficulty.

For Prime Factorization for instance, which like you say, isn't even NP-complete. You can easily adjust the difficulty by increasing the size of the number in question.

I'm not sure if that's completely true for prime factorization. There are numbers that are larger, yet easier to factorize.

For example, I think that a power of two, like 1024, is much faster to factorize than, let's say, 1001 (71113). (I'm not quite sure this example is true)

Here's a more detailed description: https://mathoverflow.net/questions/249266/classes-of-numbers...

Gridcoin relies on BOINC for the work distribution, essentially you get credit based on how long it took you to complete the task (to prevent cheating most projects rely on a quorum of results being the same (each task is sent to several users)).

This is not used as a direct mining mechanism, the blockchain is secured using Proof of Stake rather than Proof of Work.

One fundamental problem is that the problem you solve must in some way "sign" or validate the set of transactions you want to add to the Blockchain. You can't just solve anything and say "I did some work".

So while we could hypothetically use NP complete problems (although there are several issues which arise to do with consistent difficulty), it's hard to do useful work, because we need the input to be fundamentally linked to the transactions in the block (and the hash of the previous block too)

This answers my question. Thanks :D

It's difficult to generate hard instances of problems. Many (all?) NP complete problems are easy on average. For example almost all uniform random SAT instances can be solved quite easily.

That's not my understanding of the NP domain. Take Prime Factorization for example. Which isn't even NP-complete, or Sudoku which is NP-complete. Both of these problems can be made really hard by changing 1 small variable, size.

Edit: I understand that your argument is about the average case and not the worst case.

If you pick a random number the chances are really good that it has many small factors and hence is a lot easier to factorize than its number of bits might suggest. Half of all numbers are divisible by two, two thirds of all numbers are divisible by two or three.

Regarding Sudoku, my hunch is that there is a critical density of numbers where random problems are harder than average. That's the case for SAT, there is a phase transition on the number of variables per clause where above a critical value almost all instances are not satisfiable and below the threshold almost all instances are. Instances right at the threshold tend to be hard for our current solvers.

One argument is that the blockchain problem coincides with a "real scientific problem" that needs solving and if the scientific problem leads to some application, which can yield a monetary reward (may be big "if"), this would make it cheaper to launch a 51% attack against this blockchain. The attacker could subsidize their attack by being paid to do science.

Not so serious answer: Hurray for that? :D

Serious answer: Things would obviously have to be designed differently. This isn't about distribution of "economic power to the hands of the people" or some other Satoshi notion. The thought I have is more along the lines of Folding@Home

http://folding.stanford.edu/

If this isn't about some "Satoshi notion", then what does blockchain have to do with it? Just do something like Folding@Home. There are several projects like that.

What makes the attacker different? If there was a possibility to subsidize mining by being paid to do science, why would other miners not take advantage of this also?

Generally, blockchain "mining" requires a problem that is hard to solve, easy to verify. If I understand it correctly, the genome sequencing problem is hard to solve, hard to verify.

What you just said is the "definition" of NP problems which is why I had it in my question to begin with. Even if genome sequencing is not a good problem for mining. There are plenty of other scientific problems that are. Yet mining today is not tackling any of them :/

The miner's identity (more or less) has to be one of the inputs to the problem, so that everyone is actually working on a different problem and you can't "steal" a block just by broadcasting another person's solution faster and wider.

Maybe there could be useful problems with this property, but it's not trivial to find them.

No, a given assembly is easy to verify. The complexity in actual application comes from the fact that performing the sequencing part (the biological/mechanical part) again will yield a different assembly due to biological and technical variability. Another complexity comes from the fact that you can define different measures of “goodness” (and hence optimality), depending on which errors you model.

But from a computational standpoint, sequence assembly (using a given error metric) is simply NP-hard.

Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes? Is checking that the solution is valid a very fast operation? Are we sure that there is no "final" answer which would make the calculation unusable at some point? (Those are the three main factors for choosing what kind of work to do, as far as I can see)

> Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes

I am fairly certain you can design your problem to behave in a similar manner or in some manner that increases the complexity based on some criteria

> Is checking that the solution is valid a very fast operation?

That's the NP part in my question. Plenty of scientific problems out there that are fast to verify hard to compute. Ex. Prime Factorization

> Are we sure that there is no "final" answer which would make the calculation unusable at some point?

I would argue, and I might be wrong due to my ignorance on the subject here, that we can never "know" that. That's why P=NP is still an open question

There are droves of the distributed computational projects, mostly based on Boinc [1]. There are projects whose goal is biochemistry applications too [2].

[1]. https://boinc.berkeley.edu/

[2]. https://boinc.berkeley.edu/projects.php

Reply on news.ycombinator.com