Also called Proof of Human work (PoHW)

This idea was sparked by the great and succinct riddle that monsterer2 proposed on this BitcoinTalk thread:

This idea was sparked by the great and succinct riddle that monsterer2 proposed on this BitcoinTalk thread:

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

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.

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

Traveling 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

This topic, using conway's game of life as a PoW problem, fits into this definition I have given of Proof of Thought:

https://bitcointalk.org/index.php?topic=2977765.0

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

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

This topic, using conway's game of life as a PoW problem, fits into this definition I have given of Proof of Thought:

https://bitcointalk.org/index.php?topic=2977765.0

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