Bitcoin Forum

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.

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

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!

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.

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 (http://https://hackernoon.com/trump-wont-kill-america-bitcoin-will-a2be67247969).  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.

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:


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.

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

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!

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

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.

Very interesting thought experiment. Really like it :)


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?

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.

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.

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.

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.

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.

I am against this proposal as a framework for blockchain technology. But I do appreciate, op's dedication and the motivations behind this, kudos!

As I've briefly discussed this subject before (in the thread which has inspired @ir.hn for  starting this topic), the problem of one-human-one-vote approach to blockchains, besides the slavery threat, is its political nature in the extent that can't be applied to socioeconomic games directly.

IOW, you can not fetch/change the ledger's state by means of a nothing at stake, voting system, because voters can easily commit to a zero cost attack and confirm illegal double spend transactions.

This proposal is mostly focused on normalizing the distribution of wealth (generation of money/block reward) and not exchanging it (cash transfer).

Op has missed the simple fact that the blocks to be generated by the person (being either a freelance/solo participant or a pool/slavery center) does not only encompass a coinbase transaction (that specifies who has won the reward and its amount) but also a set of ordinary transactions that the miner asserts they are valid.

The problem begins here, suppose Alice transfers all of her wallet balance to Bob via tr1 which is normally confirmed,  then she attempts a double spend by means of a new transaction that sends the already spent money to another person or another wallet of her.

Alice is a celebrity and Bob is an infamous Wall Street broker, hated by 99% of people. Alice asks help from her followers to rewrite the blockchain and confirm the double spend transaction because 'Bob is fraud and has done something bad to me' , she asserts. When it comes to voting for this rewrite (being of any range) Alice has a good chance to revoke her funds because of the public opinion being biased  in favor of her.

It could be even worse if it was about a national crisis and financial disaster where populists can easily manipulate public opinions.

Such a monetary system, could hardly be called a monetary system. Money is a privilege people hold in their deposits/accounts against the public interest and in favor of their personal interests, it can not be put under the influence of public by letting them to 'vote' about it.

So, the main problem of this proposal, would be the lack of support by game theory, instead op tries to fill the gap with computing theory, I'm a fan of the latter (having educational back ground in computer science) but, this is an unfortunate, money and monetary systems are territories being ruled by the first one,  I can't imagine how without game theory, approaching to a blockchain based public ledger  would be possible.

As I said, it is totally an unfortunate for me, not just because of my passion for computing theory but also because I love decentralization and distribution of power and hate Wall Street, belonging to 99%  ;)

You really, really, don't get this idea at all do you? Its not PoS, it's PoW.

I guess I get the idea and i know it is Proof of Work, actually op has termed his proposal as Proof of Human work already, never said otherwise.

Imo, it is of vital importance to be more specific when it comes to discussing such ideas. Accusing me of not getting the idea (implying kinda ingenuity)  won't void my technical objection above.

As of similarities between this idea and PoS, I can confirm that I think there is a similarity between the two as they in share a  same vulnerability to zero cost attack.

Anyway, if you can show me how this proposed algorithm could mitigate the attack I described in my reply, I would be fine with dropping my objection.

Any attack you can level at this proposal you can level at any PoW blockchain since all miners are controlled by humans - they are vulnerable in exactly the same way, there is nothing special about whether a human or a machine under the control of a human solves a PoW.

Well, not exactly true.
Proof of Work, implies consuming a lot of resources. To manage a 50%+1 attack an adversary has trade-offs to make (comparing incentives and costs) as of this proposal , Humans just use their free talent, zero or negligible costs are involved, so voting is free and we are left with only incentives that rule in favor of evil behavior, mostly.

Humans expend the most valuable resource on the planet: time. This is ultimately more valuable than anything else in the universe.

The puzzles are created such than no man/machine can perform them faster than a human, therefore this represents the ultimate PoW.

Saying that 'time' is valuable or 'the most valuable resource in the universe' the way you put it, as a metaphor is acceptable but it is not concrete.

For example air is one of the most important things ever but it worth nothing in the market and barely can be called a resource.

For a thing to be categorized as a resource, it should be both rare and in demand of work, mostly hard work, to become available.

Time is not a resource, people got  lot of free time and if they could find an incentive tempting enough, they would trade it easily and cheaply.

On the other hand you can't keep people busy solving a NP-Complete problem for hours, this leads to a very unscalable solution unless the solution finding procedure can be spanned in multiple rounds, this will produce new attack vectors and will detach the problem solving procedure from confirming transactions, again money transfer features are missed here, just an alternative system for replacing central banks without interfering with  commercial banks.  

I'm afraid you are utterly incorrect. The only reason PoW exists in the first place is to provide an unforgeable proxy for elapsed time.

I know this is a thought experiment and unlikely to be realized (although ... I would like to see it as a testnet ... as a kind of "gambling" thing ;) ).

Thinking a bit about it, there may be a problem: As far as I understood the posts and the description of NP-complete problems, there is a fast way to prove that a solution fulfills the task, but no way to know in advance which one is the "perfect" one (Correct me if I'm wrong). So, for example, in the problem of the traveling salesman, maybe one human finds a route through the cities which is e.g. 1000 km long but there may exist one with 995 km, but the system can't tell that this route exists.

But wouldn't that mean that the first valid solution would be very likely the one to win? If there is no way to prove that an answer is the "perfect" one, then all valid answers could be used as a starting point for the next block. Obviously it's possible that another human, shortly afterwards, finds a better solution. But it seems that a computer brute-forcing simple valid solutions and then trying instantly to build the next block continuing to brute-forcing would be at advantage. Eventually he would get the longest chain.

I don't know if there is a subset of NP-complete problems where a human can guess a valid, but not near-optimal solution faster than a computer, but I doubt that.

But maybe that problem can be solved? For example, I could imagine an algorithm where a linear increase in "quality" of the solution could exponentially (e.g. quadratically) increase block weight. Then computers with a low-quality solution would have a hard time to compete with a human with a near-optimal solution.

You misunderstood. NP is the class of problems for which one can efficiently verify solutions.
Complete means that a problem is in some sense as hard as any other NP problem.

The Traveling Salesman Problem asks whether there is a route of at most a certain length.
This is clearly in NP.

It does not ask for the optimal route. Such a problem would generally NOT be in NP, precisely because answers cannot be efficiently verified.

If we consider OptimalTSP as the problem whose instances are a pair of a distance matrix and an optimal route, then this problem is in fact in co-NP, complements of NP problems.

Actually, the travelling salesman problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem) does indeed ask for the shortest possible (=optimal) route and therefore is an NP-hard problem.

---

You seem to missunderstand the idea.
The idea is to have a PoW which can not be performed by a machine. In this case they are not vulnerable the same way. A human is not vulnerable to any kind of digital attacks/spoofing/.. the same way as a machine.

Quoting from that Wikipedia page:

"In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems."

OK, thanks. I admit I'm not an expert on this topic.

But in this case, is it mandatory that a solution (with a shorter route than the original graph) exists? Can the computer know that before someone submits a possible solution? Because if there doesn't exist a shorter route, then the blockchain would become stuck. You can resolve that with fallback tasks, but a certain probability may exist that none of them has a solution.

And the computer maybe could be at advantage trying to brute-force slight variations from the original route.

But overall, I would love to see a test implementation.

Tyranny of the algorithm? Lol
But algorithm works according to rules. We should rather be worried about very advanced Artificial Intelligence going rogue in the future.

Your idea is very interesting though. But what stops a greedy miner from outsourcing the problems to other people?

I have always wondered whether Mining Centralization can be solved with Biometrics.. . By combining different Biometrics with passwords for every miner. The Biometrics will be hashed/encrypted and stored on Blockchain so that no one (not even "govts") except the owners have access to them.

Have you looked at Motocoin?  That basically does exactly what you propose - mining through a puzzle game.  Unfortunately, it turned out to be bot-able in the end.

You're just providing yet another example of a failed solution to find this Proof of Human holy grail.

As I said above, and as others seem to agree (sorry for speaking for the rest), the basic challenge and the essence of the solution is yet to be overcome: how do we create or find a task that a computer cannot complete, neither by learning nor by brute force?

Puzzles seems to be just the one way but it's always going to end up bot-able. Riddles maybe? Psychic tasks maybe? ;)

The fatal flaw is this.

HUMANS DO NOT THINK...THEY CAN NOT THINK. THEY HAVE NEVER THOUGHT...THEY WILL NEVER THINK.

Most of mankind has no idea what thinking is.
What Mankind calls thought is but "Sense Based Reasoning" This is not thinking..it is simple plagiarism from programming of the SENSES.
For further reading on the topic READ Mark Twain's Essay, "What is Man".

Mankind is infantile,ignorant,arrogant and negligent.

MIND alone thinks.
MIND ALONE IS.
MIND ALONE KNOWS.

MIND KNOWING is NOT SENSE BASED REASONING.
For further illumination on this concept.
Read "A New Concept of The Universe" By Walter Russell

And remember... comment without investigation is the epitome of ignorance..self imposed and self deceived.

You know, we started with CPU/GPU mining and then some clever people designed ASIC chips and this completely changed the

mining scene, because only a selective few people with enough capital to invest, was able to afford these chips and they

started to dominate the mining scene. Now you want to introduce something that only a few people would be able to do and

they will once again dominate and centralize this scene.  ::)  Rather develop something that more people will be able to do.

the idea is amazing, not applicable, not applied..


at first, you may need to check the good ability of Genetic Algorithm in solving TSP.. this could entirely fail the idea in utilizing human brain as a source for PoW with NP-Hard problems:

https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

===============

introducing the idea as another version of PoW has a major flaw in event of "flood of common optimized answers get broadcast to the network".. this may be another kind of sibyl attack, or others hijack of the best answer.. this happens because TIMESTAMPING has missed in this proof model.

===============


and getting back to the main idea, I could say, the common problem around these sort of ideas is that the algorithm dose not involve in CHAINING process of BLOCKS - they do not work on data of block header, so relationship among blocks remains unproved..

===============

BUT, getting humans involve in the PoW is valuable and needs to be something close to the nature of human commerce..  I personally have chosen Marketing Knowledge for mining. in my model miners need to market their ability of mining and then accept job from users. now miners could improve their marketing skills to receive more job, then do mine transactions the way that PoW shows us. as we could see, now relationship among blocks and getting humans involve in the process, both satisfies.

By Marketing Knowledge you mean marketing and sales power which is a matter of investment, how is it related to any human characteristics?

Miners engaged in marketing their services, is not a good idea. I'm afraid that you are somehow poisoned by corporate oriented sales discourses that are not adequate for crypto ecosystem.

this is not necessarily about human characteristics, it is about getting humans involve in the process. and I mean Marketing as a knowledge in this post, because there are several point of views in bringing a definition for marketing - but this is what I use in this idea, from wikipedia:

"Marketing practice tended to be seen as a creative industry in the past, which included advertising, distribution and selling. However, because the academic study of marketing makes extensive use of social sciences, psychology, sociology, mathematics, economics, anthropology and neuroscience, the profession is now widely recognized as a science.."


in the future, I really need people do not TURN-OFF their mining hardware just because of prices, instead think about the benefits that they could bring to the society.. anyways we all are doing investment in this ecosystem. even we both by discussing these ideas are spending our invested-time for it..


on contrary, this is exactly what I try to break down by this idea. sales-orientation marketing approach is harmful for the ecosystem. entities just involve in activities that bring them short-term profits, and sacrifice the long-term benefits for the customers and the whole society. pools already do that. they also do marketing for their nodes too, so this is not a weird subject to the crypto.

BUT, all we need now is a transformation from sales-orientation to market-orientation model, which sacrifices short-term profits in order to build a lasting relationship with customers. from study.com:

"Companies that use a sales-oriented marketing strategy focus on selling what the company makes, not necessarily what the customer wants. Companies that use a sales-oriented marketing strategy also pay very little attention to the changing needs of their customers or to the changes that take place in the marketplace."

====================

by bringing and change the sales-orientation marketing from pools level to the miners level (market-orientation), now we have a dynamic puzzle of "how do I market for my mining hardware?" for each transaction, that only humans could solve it - and once solved, computers could check the miners Proof-of-Work_after_Marketing.. (I need to stop myself to call it Proof-of-Marketing, but if this could help to express the meaning, why not!?)


UPDATE:

you know, I really believe in Hobby Miners. these guys finally support the ecosystem through in its all good and bad days.. so this should be their right to benefit from the process, not those rich owners of industrial farms. if in PoW this is all about "who is rich, has the priority", then what is the difference with PoS?

@mixoftix

I'm pretty sure we are both getting off-topic and I hate it. I made my point about your idea being sort of institutional investment and not what OP is trying to achieve, this is it.

I'll come to your thread and discuss it and other points in details asap, as I've promised. I need to free like a full working day to review your work and it is your fault, you make everything more complicated with each post.  ;D

not yet, but close  :o :o


if I get it correctly, I should say in my point of view, the PoT (which represents the topic) or any other proof model that try to get humans directly involve in the process, should design based on the principles of freelancing.. freelancing is also welcome by the governments and tax laws.

P.S.:
so, as you noticed about getting off the topic, I think we need to find enough time to have this business aspect of the idea (getting humans directly involve) in other section of the bitcointalk that is dedicated for economical angles of proof models.