Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Darwin: a genomics co-processor provides up to 15,000x acceleration

blog.acolyer.org

Post reply on HN
Print view View original

11–20 of 51 posts

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#11

Post by tradedash »

AndrewDucker wrote: post #6
tradedash wrote: post #5

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 s…

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

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#12

Post by tradedash »

adrianN wrote: post #10
tradedash wrote: post #5

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 s…

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.

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#13

Post by tradedash »

JD557 wrote: post #8
tradedash wrote: post #5

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 s…

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 visi…

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.

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#14

Post by ctchocula »

tradedash wrote: post #5

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 s…

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.

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#16

Post by tradedash »

ctchocula wrote: post #14
tradedash wrote: post #5

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 s…

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/

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#17

Post by jacquesm »

tradedash wrote: post #5

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 s…

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.

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#18

Post by crispweed »

ctchocula wrote: post #14
tradedash wrote: post #5

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 s…

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.

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?

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#19

Post by JD557 »

tradedash wrote: post #13
JD557 wrote: post #8

Earlier quoted context omitted.

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 visi…

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

Re: Darwin: a genomics co-processor provides up to 15,000x acceleration

#20

Post by Geforce8472 »

JD557 wrote: post #8
tradedash wrote: post #5

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 s…

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 visi…

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.

Post reply on HN