Proof of Thought (PoT): The Holy Grail has arrived! Only Humans can mine

[ir.hn]

Also called Proof of Human work (PoHW)

This idea was sparked by the great and succinct riddle that monsterer2 proposed on this BitcoinTalk thread:
https://bitcointalk.org/index.php?topic=4447123.20

"A truly decentralised consensus mechanism is one where humans perform the PoW. The trouble is, finding a problem that only a human can solve that is also easily verifiable by a machine is unsolved.

The person who solves this problem will be very rich indeed. "

Ask and you shall receive.

While I do not expect to get rich ( I have solved many of the worlds biggest problems; but if it doesn't make someone else rich then no one cares) from this idea. Actually I think the opposite, people will hate this idea because they would actually have to work for their money instead of having a computer doing it for them.

I have termed this idea Proof of Human Work (PoHW). I do not claim that no computers or AI will be able to mine this. However I do claim that humans will have a fair shake at least until an algorithm can be developed to solve it (which likely will take a good number of years at the very least since these problems have been known and researchers trying to solve them for decades at least). I think the biggest risk to this proposal is the training of AI to use skills humans have developed to solve these problems.

It would probably find form in "puzzle video games". They can likely be done with paper or pencil but doing it on a computer in a program or app would be the best way to go for mining purposes.

The idea is simply this: Use NP-complete problems as a proof of work. NP complete problems are Non-deterministic polynomial time problems. An NP Hard problem means in essence that they cannot be sped up with computers. The larger the problem, the worse computers (algorithms) are at solving them. Np-complete are a subset of NP-hard problems. What NP-complete means is that a computer can easily verify a proposed solution is correct, but cannot "know how to" solve the problem. This even works if you believe P=NP (which I do), as you can create a new coin using a new NP-complete problem that has not been cracked (or change the algorithm of your coin but I always advise against this where possible).  P=NP hypothesis means that every problem that can be easily verified can eventually be solved quickly too.

Now the problems shouldn't be just NP-complete, all hashing functions are designed to also be NP-complete.  But the problems should also benefit from heuristics.  This means that you can find ways to improve your ability to solve the problem.  You likely won't be able to find any heuristics for SHA256 for example but you can find heuristics for the traveling salesman problem or minesweeper for example.

This is exactly what we want; a problem whose proposed solution can be quickly verified by computer and yet the computer would be "bad" at finding solutions itself. Perfect.

Some example problems to solve could be the traveling salesman problem and/or minesweeper, and/or any other NP-complete problem or combinations of problems. Any implementation and/or mining methods or programs or suggestions can be used. This idea can be used by itself or in conjunction with computer mineable problems like using this idea in conjunction with other PoW algorithms.

For example you could have a 100x100 minesweeper or any size or size dictated by automated difficulty adjustment and the first one to solve it win's the block in mining. A program could disseminate this to people around the world to work on it and could pool the individuals and split the reward or give the individual who wins it first the whole block reward. Also some programs can have collaboration where everyone can work on the same minesweeper problem together. There are many challenges minesweeper would pose (such as needing a trusted 3rd party to create the minefield or obfuscating their ability to see it) in this context which we won't go into, it is just an example of how this human mining could be set up.

Minesweeper is np-complete
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

Traveling salesman problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem

Drawbacks: People have to do work. Slavery could result from this. People may need more food because thinking takes energy.

Benefits: Mining centralization will be a smaller problem. Anyone with a brain and a communication method can contribute and earn money. Even animals like bees may be able to be used to solve these (search: bees traveling salesman). No specialized hardware or even computer is needed. Energy problem will be nonexistent. Just like we don't tell people not to exercise, this will be exercising peoples brains. The whole global network would use negligible extra energy, and even if the people ate more, exercising the brain will make them healthier. It may help reduce the risk of dementia and other degenerative brain diseases. This is our liberation from the coming "tyranny of the algorithm".

Here is another whitepaper that uses the term proof of human work however it uses CAPTCHA's and not NP-complete problems.  I think our idea is better and is more veritably NP Hard.
https://eprint.iacr.org/2016/145.pdf

Can also be called Proof of Neural Work or Proof of biological work or proof of thought.

[keelperu]

all is good myself in crypt o currency

bitcoin , ethereum , bitcoin cash ....and much more crypto currency

all are rich get rich and poorer get always poorer only concept, then how the crypto currency future of the world currency, and also the currency used for many illegal underground market , and it not pay a tax to government, and yours whom intelligent in math they get rich, then the inventor , farmers and others, what they do , if your rich you get 1000 for less work - others get 1 for very hard work , is this equal

based on money

human != human

rich human (crypto currency intelligent)  != average human

when it equal develop like this

[buwaytress]

This reminds me of Nano (the rebranded xrai or mrai, can't remember honestly now). Everything was mined via captcha.

Point is, I also recall the number of threads specifically dedicated to collecting people to help solve those captchas, paying what I would say were amounts only significantly better than collecting faucets. Since this could still result in tens of dollars for a day's work, it meant a lot of willing workers - I come from a country where minimum wage is less than $200 and my neighbours in other countries generally don't even meet their much lower minimum wages. So you'd see legions of these workers mining for a handful of people.

Towards the end of last year, it got even more organised. People integrated it into faucets, drawing even more people (faucet hunters) mining for them.

That demonstrates a bad-case slavery scenario for your idea, and ensured most of the mined coins belonged to the very few with resources to organise.

I theorise that it would also still be possible for computing power to randomly attempt to solve these NP puzzles (keep changing IP and just randomly select answers) and achieve low rates of correct answers, and yet still outperform productivity of a slower human over time. I know randomly clicking captchas or always selecting the same images sometimes still solves it!

[monsterer2]

Minesweeper is np-complete
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

Traveling salesman problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem

I like that it got you thinking! The trouble is, we need puzzles that are solvable faster by humans than machines. Just because something is NP complete doesn't mean a human can solve it quicker than a machine, it just means it's tough to solve for.

edit: that's not to say this idea itself doesn't have merit. Indeed the finest example of this idea I've seen proposed so far is PoW using conway's game of life: https://bitcointalk.org/index.php?topic=2977765.0

[ir.hn]

Minesweeper is np-complete
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

Traveling salesman problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem

I like that it got you thinking! The trouble is, we need puzzles that are solvable faster by humans than machines. Just because something is NP complete doesn't mean a human can solve it quicker than a machine, it just means it's tough to solve for.

edit: that's not to say this idea itself doesn't have merit. Indeed the finest example of this idea I've seen proposed so far is PoW using conway's game of life: https://bitcointalk.org/index.php?topic=2977765.0

That's true, I failed to connect those dot's initially but another requirement to NP-complete would be that it is able to benefit from heuristics.  Scientific studies have been done with traveling salesman and humans with no practice have an 11% advantage over machines.  Just imagine how it will be when people practice it a lot.

I don't believe Conway's game of life is classified as NP-complete but even so predicting what Conway's game of life will do next would probably be NP-complete and benefited by heuristics so yes that would fit into this definition.

[ir.hn]

This reminds me of Nano (the rebranded xrai or mrai, can't remember honestly now). Everything was mined via captcha.

Point is, I also recall the number of threads specifically dedicated to collecting people to help solve those captchas, paying what I would say were amounts only significantly better than collecting faucets. Since this could still result in tens of dollars for a day's work, it meant a lot of willing workers - I come from a country where minimum wage is less than $200 and my neighbours in other countries generally don't even meet their much lower minimum wages. So you'd see legions of these workers mining for a handful of people.

Towards the end of last year, it got even more organised. People integrated it into faucets, drawing even more people (faucet hunters) mining for them.

That demonstrates a bad-case slavery scenario for your idea, and ensured most of the mined coins belonged to the very few with resources to organise.

I theorise that it would also still be possible for computing power to randomly attempt to solve these NP puzzles (keep changing IP and just randomly select answers) and achieve low rates of correct answers, and yet still outperform productivity of a slower human over time. I know randomly clicking captchas or always selecting the same images sometimes still solves it!

Yes but this is better than humans not being needed at all - and instead of being slaves - we starve to death.  

Nationalistic countries, if they understood crypto, would fight crypto's adoption.  This is the whole reason we have national currencies...if you have currencies that can cross borders easily and can be earned anywhere equally you will see the result is the destruction of the Nation-State.  This just goes with the territory and PoT is no more or less apt than any crypto to do this.  However PoT is much much less likely to burn out all our natural resources doing so.  Bitcoin, in it's current form, will lead to an "Easter Island" scenario with our planet.

[monsterer2]

That's true, I failed to connect those dot's initially but another requirement to NP-complete would be that it is able to benefit from heuristics.  Scientific studies have been done with traveling salesman and humans with no practice have an 11% advantage over machines.  Just imagine how it will be when people practice it a lot.

I don't believe Conway's game of life is classified as NP-complete but even so predicting what Conway's game of life will do next would probably be NP-complete and benefited by heuristics so yes that would fit into this definition.

Got a reference for the first claim? I can only find a reference for human performance being within 11% of the optimal solution rather than solution time being faster than optimum machine performance.

[ir.hn]

That's true, I failed to connect those dot's initially but another requirement to NP-complete would be that it is able to benefit from heuristics.  Scientific studies have been done with traveling salesman and humans with no practice have an 11% advantage over machines.  Just imagine how it will be when people practice it a lot.

I don't believe Conway's game of life is classified as NP-complete but even so predicting what Conway's game of life will do next would probably be NP-complete and benefited by heuristics so yes that would fit into this definition.

Got a reference for the first claim? I can only find a reference for human performance being within 11% of the optimal solution rather than solution time being faster than optimum machine performance.

Right from the wiki article on traveling salesman problem:

Human performance on TSP

The TSP, in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% more efficient for graphs with 120 nodes.[47][48] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.[49][50][51] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to impact performance in the task.[52][53][54] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems, and have also led to new insights into the mechanisms of human thought.[55] The first issue of the Journal of Problem Solving was devoted to the topic of human performance on TSP,[56] and a 2011 review listed dozens of papers on the subject.[55]

I was assuming the highlighted sentence implied efficiency versus computers, but I see how that assumption could have been wrong.  Here is the full paper, I don't have time to look through it now but here it is:
https://link.springer.com/content/pdf/10.3758%2FBF03213088.pdf

[monsterer2]

Right from the wiki article on traveling salesman problem:

Human performance on TSP

The TSP, in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% more efficient for graphs with 120 nodes.[47][48] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.[49][50][51] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to impact performance in the task.[52][53][54] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems, and have also led to new insights into the mechanisms of human thought.[55] The first issue of the Journal of Problem Solving was devoted to the topic of human performance on TSP,[56] and a 2011 review listed dozens of papers on the subject.[55]

I was assuming the highlighted sentence implied efficiency versus computers, but I see how that assumption could have been wrong.  Here is the full paper, I don't have time to look through it now but here it is:
https://link.springer.com/content/pdf/10.3758%2FBF03213088.pdf

I think you're confusing the meaning of 'efficiency' here. They're talking about solution efficiency, rather than solution speed.

[ir.hn]

Regardless, I will read the full paper, but we can at least conclude for now that humans can complete the task with near optimal solutions quickly.  This is good because humans would be able to guess right answers better than machines presumably in some cases, and therefore a human would have a good chance at winning the block in this sort of proof of work system.

[monsterer2]

Regardless, I will read the full paper, but we can at least conclude for now that humans can complete the task with near optimal solutions quickly.  This is good because humans would be able to guess right answers better than machines presumably in some cases, and therefore a human would have a good chance at winning the block in this sort of proof of work system.

I look forward to reading your conclusion; this line of thinking shows promise.

edit: this paper claims to present an algorithm for computing the optimum route order O(n^3.322) https://arxiv.org/ftp/cs/papers/0702/0702133.pdf

[ir.hn]

Just as some food for thought,  I just remembered that I developed an algorithm that may produce near optimal results.  It probably isn't going to give exact solutions all the time but can probably beat nearly any human if in fact it works (hasn't been tested).

https://archive.fo/OGyoH

The cool thing bieng this algorithm may favor CPU mining over GPU's and ASIC's since it uses complex calculations and therefore lots of random memory accesses.

In general I think if we use PoT systems, they will be able to b mined with any hardware, but certain hardware would be optimized for certain algorithms where the more genrral hardware the better guesses they can make but the slower they run.  Therefore humans, cpu's, gpu's and asics can all live together in harmony!

[monsterer2]

This is truly interesting idea since there's no "effective" algorithm to solve NP-complete based problem, but there are 3 major problem which are :
1. How would the nodes/protocol system generate the problem without rely on 3rd/trusted party?
2. How to verify the given answer is the best/most efficient answer, since AFAIK there's no way to verify it besides try all possible combination?
3. Since PoT rely on human's ability/speed to solve the, that would mean the block generation time would be unreliable and lead to long waiting time.

1. Some randomness is basically all that's required
2. "Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place"*
3. Block generation time would have a variance in a similar way to the bitcoin block time. On average it would even out.


*) https://en.wikipedia.org/wiki/NP-completeness

[bob123]

~snip~
This is exactly what we want; a problem whose proposed solution can be quickly verified by computer and yet the computer would be "bad" at finding solutions itself. Perfect.
~snip~
For example you could have a 100x100 minesweeper or any size or size dictated by automated difficulty adjustment and the first one to solve it win's the block in mining.
~snip~

Regardless of NP-completeness, a computer will always be able to bruteforce a minesweeper field faster than a human can solve it.
Even without optimized algorithms or logic (which would decrease the time it takes to solve further) a machine will be faster at guessing or calculating.

For your approach to work, you would need to find a task a computer can not accomplish at all.

[d5000]

Very interesting thought experiment. Really like it

3. Since PoT rely on human's ability/speed to solve the, that would mean the block generation time would be unreliable and lead to long waiting time.

One could use a hybrid system: a "less secure, but not-energy-consuming" algorithm like Proof of Stake for "microblocks" with small block intervals - good enough for micropayments, but not secure enough for big ones  - and use the "Proof of Thought" blocks as checkpoints. People or businesses waiting for payments big enough to attack PoS could wait without problems until the first "human" confirmation.

What I wonder is - could an algorithm that creates NP-complete problems create "unsolvable" problems which would stuck the chain forever? Could this be prevented? Or is the "best solution" enough to win a block reward?

[monsterer2]

1. I understand what you mean, but i doubt some "randomness" is enough.
2. Then people could submit block with more efficient answer and could redo the block with less efficient answer.
3. True, but surely the block generation time invertal would be more sparse than other consensus method.

1. It may not be so simple, I agree.
2. I think this is analogous to how bitcoin works? Miners can generate a 'better' hash of the same block (i.e. hash with lower numerical value). The winner is the one who's block gets built upon.
3. Perhaps. Depends on the solution complexity, though, so with difficulty adjustment, it ought to self regulate.

[alko89]

How about something like a postal service, where the system calculates a reward for the giver relation and when the dispatcher delivers the package, the system pays out a reward.

In this case the dispatchers would be essentially miners.

[buwaytress]

~snip~
This is exactly what we want; a problem whose proposed solution can be quickly verified by computer and yet the computer would be "bad" at finding solutions itself. Perfect.
~snip~
For example you could have a 100x100 minesweeper or any size or size dictated by automated difficulty adjustment and the first one to solve it win's the block in mining.
~snip~

Regardless of NP-completeness, a computer will always be able to bruteforce a minesweeper field faster than a human can solve it.
Even without optimized algorithms or logic (which would decrease the time it takes to solve further) a machine will be faster at guessing or calculating.

For your approach to work, you would need to find a task a computer can not accomplish at all.

This was the point I brought up earlier - a computer will always be able to outperform a human by sheer brute force guessing. It may not have happened with the example I used (Nano) but if we're talking about a blockchain that could get popular and more valuable with time, you bet the computer arms race would win against normal human adopters. If all the NLP AI being developed have even a fraction of the capabilities they're touted to have, we'd see NP quickly becoming obsolete.

Also, Nano was entirely pre-mined by captcha (it doesn't use blockchain, but DAG) and that itself was also a recognition of limitations in Proof of Human algo in terms of consistent and predictable block times.

So I'd agree. Finding a task a computer simply cannot do is STILL the holy grail of Proof of Human.

[shield132]

It reminds me captcha at some point. Overally like the idea but I can't imagine how your PoHW will work, I mean what kins of job will we have to do.
Looks things differently, computer does job automatically but at the same time human made this computer and tries his/her best to develop it, it's again PoHW for me.
Also when you do something, you get reward. What you say is just something like blockchain system of our work/reward, that's how I understood it.

[TCraver]

An approach I've proposed in another posting was to have a distributed application that gives people 'tasks'. 

A task would be to walk a few minutes to meet another randomly selected person at a specific nearby location (GPS or land-mark based, so you can find each other) within a certain time limit, and exchange keys you were given to prove that you met that person at that time and place.

After meeting maybe 3 people (with a few fall-back opportunities if the person you were supposed to meet is a no-show), your task is complete and a solution can be generated that includes the collected keys and other information needed to verify that the work was done.