Conway's Game of Life as PoW problem

[ArsenyP]

There is a problem in programming that has all the necessary properties of a problem for PoW. Namely Conway's Game of Life: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
The idea is that given a set incoming parameters (a distribution of "cells" on a 2D-board) you can quite easily calculate the next step. But it is very hard to get the previous step and there are multiple solutions to the problem (many initial distributions can lead to a certain final distribution). There is no certain algorithm to reverse a step (this statement can be proven).
One does not have to use the classical game of life as is. There are numerous variations of it. In more than two dimensions, in hexagonal grid, multicolored etc.
The sequence might be as follows (I am using classical Conway's Game of Life as an example):
1. We start with an empty plane.
2. A miner picks a block and projects it on the plane in some predetermined way (like a long string of alternating 1/0).
3. Now he races with other miners to solve the problem: find any distribution that would include the block and would lead to an empty plane on the next step.
4. Whoever succeeds adds his distribution as a new default state.
5. Next miner adds the next block and he is solving a problem of finding a distribution that would include his block and would lead to the default distribution. It is easier to imagine if you add a rule that the miner's part of distribution has to be above the line of bytes that represents a block. In that case every next block will be added below whatever has evolved above.
6. Repeat with every block.

If one wants to check the chain on the block N he just plays the current distribution forward N steps and he will have to get to an empty plane.

You can change difficulty by using extra restrictions, like "The solution has to use less than X new cells" or "The solution has to be less then Y rows high" or any other.

The advantages of this PoW problem:
1. You can visualize the process. As long as you stay in 2 or 3 dimensions.
2. There is a potential for evolution of some very complex structures. One can build Turing machines in 2d classical  Game of Life. So there is no theoretical obstacles for full-scale life forms (things that reproduce and evolve) or even self-aware life forms in this perfect mathematical world. It just has to be big enough and will require a lot of computational power.
3. Mass scale computing of this kind of problems has real life applications. Lets say we make all the miners play some kind of a 3d game of life. Then we watch how it unravels until we see a part that behaves in a particular way (for example it pulses with a given period) than we can replicate this solution in a hardware where each little part is following the rules of the game. Increasing the density of small-parts that follow the rules of our game like we did with transistors we can create a lot of neat stuff.
4. Anything is better then mindless hash-calculations.

Comments are welcome.

[tromp]

4. Anything is better then mindless hash-calculations.

There’s more to mining than hashing:

http://cryptorials.io/beyond-hashcash-proof-work-theres-mining-hashing/

[ArsenyP]

There’s more to mining than hashing:

http://cryptorials.io/beyond-hashcash-proof-work-theres-mining-hashing/

There is a number of PoW problems. But it seems that their creators mostly focus on the restrictions on hardware that can be used for mining. I like the Game of Life because its mining can actually be useful for humanity.

[DannyHamilton]

Two issues come immediately to mind...

1.  While it might be possible to make the next step in the process more difficult or less difficult than the previous step, I don't see a way to have enough control over how much more or less difficult it is.  Can you suggest a reliable way that can make any given step exactly 3% more difficult? 18% more difficult? 31% less difficult? 205% more difficult? Keep in mind that ALL the future rules of difficulty adjustment need to be decided before the software is ever released and need to take into account every possible allowed adjustment.  That way each node can calculate the new difficulty for themselves without any input from anyone else. Any change to difficulty adjustment that happens after the first block is mined would require a hard fork.

2. I think that it may be possible to have some arrangements that are unsolvable. This would kill the blockchain, since it would be impossible to create a new block that progresses to the previous state in a single step.

[ArsenyP]

1.  While it might be possible to make the next step in the process more difficult or less difficult than the previous step, I don't see a way to have enough control over how much more or less difficult it is.  Can you suggest a reliable way that can make any given step exactly 3% more difficult? 18% more difficult? 31% less difficult? 205% more difficult? Keep in mind that ALL the future rules of difficulty adjustment need to be decided before the software is ever released and need to take into account every possible allowed adjustment.  That way each node can calculate the new difficulty for themselves without any input from anyone else. Any change to difficulty adjustment that happens after the first block is mined would require a hard fork.

I do not have a proof that you can steadily change the difficulty via border conditions as proposed in the topic. But here is an even better solution.
Since every next step has to contain all the information from all the previous steps the difficulty infinitely increases with time. And you have to set the number of steps to be followed. Like "you only need a solution good enough to yield the correct blocks for 10 steps". If at some point it becomes too difficult or too easy to find solutions - the system increases or decreases the number of steps to be followed. This adjustment in the difficulty should be reliable enough.

2. I think that it may be possible to have some arrangements that are unsolvable. This would kill the blockchain, since it would be impossible to create a new block that progresses to the previous state in a single step.

True. Not every distribution is reachable in the Conway's Game of Life but I was only using it as an example. There are games where every distribution is reachable or at least there is a set class of distributions that are reachable (for instance it is not hard to prove that all checkerboard distributions are reachable in the Conway's Game) and you can make miners work within that class. The main idea is not to stick with a rather simple and pointless Conway's Game of Life but to find a kind of game that is easy to build in hardware, that allows for complexity (i.e. at least allows a Turing machine to be built), and behaves similarly to Conway's Game in that it can not be reversed without some kind of Mote Carlo search. I know of at least one such a "game" that is being played right now by some unknown computer - our universe. It has simple rules that are strictly followed. Every distribution in it is reachable. It is probably played in reverse since quantum mechanics do not allow it to be solved forward. It has border conditions to reduce complexity (black holes that erase information). We are not gods (yet) but why not try to run a similar experiment with the entire humanity computing power.


The simplest example I could come up with

Imagine the following set of rules on a 2d square grid:
1. Every turn every cell checks if the cell above it is a 1. If so it becomes 1. Otherwise it becomes 0.
2. If the cell is in the row number 0 or below, then it becomes 0.

New blocks in this example will be added at row number 1.

Suppose the first block has to be 1010

A lucky miner comes up with a solution:

Code:

4 ....
3 ....
2 ....
1 *.*.
0 ....

You can check it playing forward according to our rules:

Code:

4 .... > ....
3 .... > ....
2 .... > ....
1 *.*. > ....
0 .... > ....

The solution does include our block at row 1 and it does end with an empty plane on the next step.

Now the default state becomes

Code:

4 ....
3 ....
2 ....
1 *.*.
0 ....

Suppose the next block shold be 0001. Another miner solves this one:

Code:

4 ....
3 ....
2 *.*.
1 ...*
0 ....

Lets test it out:

Code:

4 .... > .... > ....
3 .... > .... > ....
2 *.*. > .... > ....
1 ...* > *.*. > ....
0 .... > .... > ....

It works because it contains the desired block in the distribution and it plays toward the default distribution.

Now lets suppose that figuring out a solution for the next block (1100):

Code:

4 ....
3 *.*.
2 ...*
1 **..
0 ....

took way too long because one had to calculate three steps forward (or replicate the previous solution on the entire plane which is the same thing). Then the system automatically decreases the difficulty to "2 steps are enough". Next block is 1000 and the system will settle with:

Code:

4 ....
3 ...*
2 **..
1 *...
0 ....

It does not play toward the entire default distribution at the moment, but it gives the correct blocks in the row #1 for long enough (for two steps) which is enough with the current difficulty

[monsterer2]

Now lets suppose that figuring out a solution for the next block (1100):

Code:

4 ....
3 *.*.
2 ...*
1 **..
0 ....

took way too long because one had to calculate three steps forward (or replicate the previous solution on the entire plane which is the same thing). Then the system automatically decreases the difficulty to "2 steps are enough". Next block is 1000 and the system will settle with:

Code:

4 ....
3 ...*
2 **..
1 *...
0 ....

It does not play toward the entire default distribution at the moment, but it gives the correct blocks in the row #1 for long enough (for two steps) which is enough with the current difficulty

It's not totally clear from this quoted example - it looks like 1 was 'replaced', but actually the original '1' still needs to make it into the blockchain in order for the system to decide to adjust the difficulty downwards.

I love the idea, though.

Cheers, Paul.

edit: scratch that, I now see its just the numbering that was throwing me.