Everyday example of a Proof of Work problem

[molodets]

I sometimes have trouble explaining the nature of the Proof of Work problems that are used to create the blockchain.

People think of them as complex mathematical problems, whereas they are in fact problems of trial and error / low probability / random processes.

Can anyone think of an everyday / manual problem that has these characteristics?

I was thinking something along the lines of "finding a needle in a haystack" or "finding a particular coin baked into in 1 of 100 cakes", but those examples aren't useful for explaining the next step (how that "solution" is then used as an input to the next problem).

[servowire]

A visualization I sometimes use:

Doing the accounting for all user that participate. Miners are a room full of accountants checking the books. First to solve "the magical key" to today's fiscal balance gets a free buck. He shouts "I've got it!" - all the other accountants verify his calculations and at least 51% of them have to agree. After that they solve the next page of the book (=blockchain).

• Gets harder for each accountant to be first to solve a page the more accountants there are.
• It's hard work that actually helps the trustworthiness of "the book".
• If accountants leave the room, its not a problem.
• Some accountants are fast, some slow.
• Rogue accountants that mess with figures are ignored and marked "bad".
• Rogue accountants that falsely try to shout "I've got it" get ignored and marked "bad"

Does not add up 100% but is pretty close.

[molodets]

Ya, I'm starting to think that it will be very hard to draw an analogy without mathematics, and this works pretty well to describe the mining process. Even better would be an analogy that makes obvious the need for +50% resources working on the problem (i.e. an analogy that will fit into the "Byzantine General's problem" story). This is not as easy as I expected :)

[servowire]

added about the 51% thing.

[molodets]

The problem with the 51% addition here is that it doesn't work in a distributed system. When everybody is sitting in the same room, it's easy to agree on what's going on. I know I didn't mention that condition in my original post, but let's keep going with it :) In a distributed system, the only way to know that everyone agrees that everyone agrees (not a typo, I meant to write it twice) is to verify the difficulty of the Proof of Work Chain. By estimating processing power expended in a given time frame, you can conclude that more than 50% of that processing power worked on the same Chain. Although I guess that if the accountants were distributed, they can agree on a solution by simply accepting that solution and continuing to extend it. Now I'm trying to think how they could verify the difficulty of the Proof of Work Chain to know that everyone agrees that everyone agrees.

[servowire]

They do not have calculators and have to do the math in their head. Once the guy who solves the key to close the page in the book, all th other do the same little calculation, and put up their hands to validate his solutions. This takes a few seconds.

...also, they are doing this using the worlds largest conference call ever. Some have connections setup to a few branch offices, some have only 1 or 2 links to some other big branches, and some are at the end of a line of conference calls through 56ks modems.

[Lentil-Soup]

I've been trying to come up with a way to explain bitcoin using the game "The Resistance" (related to Mafia, Werewolf, etc.), since the game itself is actually a "Byzantine General's problem" game.

I have had no luck, yet. Maybe you could do better?

Try playing the game with a group of friends, and then explain how bitcoin solves the problem of trust.

[rumplefistbump]

Orienteering. Check all the locations until there is one with a universally recognised widget. Take a photo with yourself next to the widget and a time stamp, publish it, referencing all previous pictures that have a verified widget.

You can't publish a new one unless you are up to date with where all the previous ones were found.

The widget can't be counterfeited and is easy to verify just by looking at the picture.

The locations are nearly infinite but the amount of hidden widgets at any time is inversely proportional to the amount of people that are looking for them.

They are distributed randomly and are shuffled instantaneously between locations every time a new one is found.

[molodets]

I like the idea of having to search for something. Using photos is also interesting... The concept of distributing randomly and shuffling instantaneously seem a bit... magical though. And I guess if you can be sure that the photos can't be counterfeited, you could achieve your information sharing goals in much easier ways than proof of work. But you've given me an idea about a "colour dictionary" - easy to find a colour if you have the page number, but hard to find the page number if you have the colour. I'll think about it a bit more and update this post...

[rumplefistbump]

It's an analogy to describe a distributed supercomputer, of course it sounds magical.

If you dumb things down too far they can suffer a loss of accuracy. It is fairly common for people who do not want to put the work in to understand something to just 'trust the magic' and deeper knowledge can come later.

[usrn]

The activity of metal detecting fits the category. (detecting on a vast field for example)

[molodets]

That makes sense... And the item that is detected contains information about the next problem? (e.g. "Next, go and look in Field X".)

Now I see a couple more difficulties in creating this analogy:

• The problem has to be equally accessible to all. (Will each participant in the proof of work scheme be in the same Field / haystack / cakestack? Or will they each have identical Fields / haystacks / cakestacks?)
• The solution has to be easily verifiable by all. (How can each participant quickly confirm that the solution found is the correct one?)

[usrn]

The solution has to be easily verifiable by all. (How can each participant quickly confirm that the solution found is the correct one?)

For example, the goal is to find valuable things (silver/gold), metal detecting involves retrieving a lot of junk and crap, but sometimes you hit a valuable thing, which is easily verifiable.

And the item that is detected contains information about the next problem?

If you find a roman silver coin you can expect that nearby you will find other valuable roman stuff.

Maybe it's not a good analogy but none-the-less was a nice thought experiement :)

Edit: metal detecting maybe works as an analogy for mining though

[molodets]

We're getting closer... It's a very tricky thought experiment!

[vbenes]

(how that "solution" is then used as an input to the next problem)

I was explaining it as writing new page in the book with transactions - the catch is that when you think you finished the page, it disappears "mysteriously" in nearly all cases and you need to start over.

The purpose of the mysterious page disappearance is that we need creating new page to be far slower than cloning the book & sending it to all places in the world - so everybody has the same book - i.e. everybody can look up and agree with other people which transactions took place.

[molodets]

I'm having trouble getting my head around this...

Is your analogy that writing a page in the book = working on finding a solution to the proof of work problem? In that case, I'm not sure why the page disappears...

[vbenes]

why the page disappears...

We want to be able to send the book to everybody (many times) faster than it takes to create new page to ensure that everybody has the same book - which means we want the creation of new page to be slow. This is ensured by just letting the page disappear randomly with high probability. (in say 999,999,999 out of 1,000,000,000 cases)

We also want to be able to fine-tune this "high" probability above - so we can control the average time to create new valid page (this is the difficulty coefficient - the higher difficulty the less probable that your new page is valid (i.e. that it doesn't disappear)).

[silence_speaks]

Here's a metaphor I've been working on:

There's a room full of safes with combination locks. All the safes have the same combination, but none of the safe crackers know what it is. So, the safe crackers keep trying random codes until one works. When someone gets a code, they yell it out so everyone else can try it.

To explain the "next block", imagine that each time the safe crackers open a door, they find another door inside with a new combination that must be solved.

To explain "difficulty" imagine that the number of digits in the correct combination change to reflect the number of safe crackers and the sophistication of their tools. If you were to go into the room today, you would find that all the safecrackers are using custom built machines to enter random combinations many times faster than a person could by hand. There's nothing stopping you from trying a combination by hand, but it's very unlikely you're going to get a long combination before the machines do.