ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

CAcoin

For general discussion about Conway's Game of Life.

CAcoin

Postby eaglgenes101 » June 7th, 2014, 5:51 pm

In cryptocurrencies, proof of work is based on problems that are hard to answer but easy to verify the answer for. Bitcoin uses SHA-256, litecoin uses scrypt, and primecoin uses finding chains of primes.

It occured to me that finding interesting CA patterns is one of these problems. Even with people seeking interesting interesting patterns around the world and computers to back them up, we still have yet to find period 19 oscillators, light speed wick benders, period 7 rakes, and various other things. Incentivizing their discoveries could help, and certainly wouldn't hurt.

So anyone with me for a pattern search based cryptocurrency? Any suggestions?
    When will a 2x2 gun be discovered...?
    Guess what Chuck Norris did when he heard about Conway's game of life? He built a replicator.
    Does LongLife have spaceships?
eaglgenes101
 
Posts: 14
Joined: June 3rd, 2011, 3:16 pm

Re: CAcoin

Postby simsim314 » June 9th, 2014, 12:30 pm

Well considering that long time search is actually translated into a value of a coin, I think most search time in GOL went into spaceships search. So having some new p7 and higher period spaceships could be considered as a cryptocoin.

---

Something more similar to bit coin: minimal cell configuration for quadratic growth of any totalistic rule (there is around 256K totalistic rules, each one of them has minimal configuration for quadratic growth, some of the totally not trivial like in GOL).
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CAcoin

Postby dvgrn » June 9th, 2014, 10:13 pm

simsim314 wrote:Something more similar to bit coin: minimal cell configuration for quadratic growth of any totalistic rule (there is around 256K totalistic rules, each one of them has minimal configuration for quadratic growth, some of the totally not trivial like in GOL).

Unfortunately it's fairly difficult to define really interesting CA problems where a reasonably predictable amount of computation time is required to find an answer. Take the case of a true p14 glider gun in Conway's Life, for example, or a c/8 spaceship, or a p19 oscillator. It's true that these objects, once found, can be verified very quickly, so that sounds good so far... but there's no known way to define a search for any of these objects that is guaranteed to terminate before the sun burns out.

We can't really award Bitcoin-like points to incremental negative results, like "there is no p19 oscillator inside an 8x8 bounding box", because _that_ result can't be verified without doing exactly the same amount of work again, independently... and it seems to me that that would open the door for sending in false negative results as a claim for work accomplished.

So... you could offer a CAcoin for various goals in a series, such as a spaceship of each new slower speed c/8, c/9, c/10, and so on. But problems like that get exponentially harder with every speed, not just incrementally harder. Just a few CAcoins down the chain it's just not worth anyone's time to hunt for the next one in the series, because the odds are that the search will take decades if not millennia.

I think the recent experience with quadratic-growth patterns in Serizawa seems to indicate that even finding the smallest quadratic-growth pattern in a wide range of rules might run up against all kinds of open-ended problems -- proving that there's no possibility of quadratic growth in some rules, and proving (with a reasonable-length calculation) that quadratic growth will inevitably continue, in smallest-case candidates in other rules.
dvgrn
Moderator
 
Posts: 4021
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CAcoin

Postby simsim314 » June 10th, 2014, 6:31 am

Well one of the advantages of Bitcoin is that people who search for new coins, cause the existing coin price, jump up.

But say in CG art, people can sell their art works for a price. As a possibility, I guess that something like Gemini or Pi-Calculator would cost a tremendous time effort, so it can be estimated in money as well. The problem is that the CA community is not that big, and there is no obvious way to use CA designs in any profitable way (unlike CG art, that can be used in commercial movies etc.).

Thinking in this direction, the main "challenge" for the CA community, is to attract attention in some way that will attract a large audience, even if it's to some sort of end products. For example, maybe some games that will have "CA mind" in it, so the game "AI" will be CA based.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CAcoin

Postby calcyman » June 13th, 2014, 7:01 am

There's a fairly easy way to create a proof-of-work protocol based on GoL:

"Find a string S beginning with a prefix T such that the final ash census of the QR code of S contains a pentadecathlon."

Replace `pentadecathlon' with your favourite oscillator, the natural frequency of which determines the difficulty of the proof-of-work. You could even have more open-ended problems, such as `23-bit still-life', `period-19 oscillator' or `thing that doesn't belong to the list of common objects', rather than asking merely for a specific object such as a pentadecathlon.

I propose calling this system AshCash. And yes, if you can design a popular cryptocurrency based on this protocol, then Nathaniel Johnston's soup search will become redundant.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: CAcoin

Postby dvgrn » June 13th, 2014, 7:28 am

calcyman wrote:There's a fairly easy way to create a proof-of-work protocol based on GoL:

"Find a string S beginning with a prefix T such that the final ash census of the QR code of S contains a pentadecathlon."

Hmm. Yes, that looks like a good start!

I'm not entirely sure that there isn't a way to game that system using a very very long string that predisposes some section of the QR code to stabilize quickly into, for example, a pentadecathlon surrounded by a sparse field of guard blocks. Large sections of QR codes can remain invariant as you add more data. So, while you certainly couldn't guarantee a particular object in the final census, just possibly you could improve the odds significantly with an engineered data string.

-- That's clearly why you specified a prefix T: changing a prefix, and especially changing the length of a prefix, should shuffle the QR encoding fairly thoroughly. The Life-rule butterfly effect should take care of the rest. Adding some reasonable upper boundary on the length of S might also improve the robustness of the QR-GoL protocol...!
dvgrn
Moderator
 
Posts: 4021
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CAcoin

Postby calcyman » June 13th, 2014, 8:51 am

Large sections of QR codes can remain invariant as you add more data.


Then do a SHA-1 hash before producing the QR code. That `messes things up' sufficiently.

Incidentally, I specified a prefix T for analogy with HashCash, which is the proof-of-work used by Bitcoin. I seem to recall that T includes the date and time inter alia.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: CAcoin

Postby Extrementhusiast » June 13th, 2014, 4:27 pm

calcyman wrote:I propose calling this system AshCash. And yes, if you can design a popular cryptocurrency based on this protocol, then Nathaniel Johnston's soup search will become redundant.


And not CAsh? It's a threefold reference!
I Like My Heisenburps! (and others)
User avatar
Extrementhusiast
 
Posts: 1650
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: CAcoin

Postby simsim314 » June 15th, 2014, 12:19 pm

calcyman wrote:"Find a string S beginning with a prefix T such that the final ash census of the QR code of S contains a pentadecathlon."


Let me explain what I think you mean.

Say we have 10x10 initial space. Now we also chose some 10 (or any other number) random cells that will be always live or always dead, the other cells we can set any state we want. We know that we have exactly 2^90 initial options. We also know the statistical frequency of pentadecathlon in random ash, or any other pretty rare object. So we can roughly estimate the frequency at which the pentadecathlon appears from the random initial state, and so the time it takes to search for a new object.

Obviously if we have N potential objects, and we've found N/2 it makes it twice harder to find the rest N/2 objects. So the currency will go up automatically as more coins we find.

----

The only problem I see here, is that this search will yield totally useless results. I mean if we already encourage people to search inside life space for something, wouldn't it be better to encourage them to search for something useful for GOL community? Maybe we should give bonuses for something like p19. Anyway it's a good start.

Another problem I can think of, is the existence of some shortcuts. Say if we found pentadecathlon predecessor in 5x5 box, so adding some fast exterminating objects (like single cell), in the nearby area can give some extra cheating result. But This can be removed by a better "prefix", if we for example turn on and off 50% of the cells, it would be very hard to "cheat". On the other hand it will make the coin much more random, than it already is.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CAcoin

Postby calcyman » June 16th, 2014, 9:35 am

It would be useful inasmuch as the soup search is useful, i.e. finding predecessors and glider syntheses of objects.

Also, the use of a SHA-1 hash and QR code together renders it impossible to `cheat' in the way you describe.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: CAcoin

Postby calcyman » September 30th, 2017, 12:09 pm

Over three years ago, I wrote:You could even have more open-ended problems, such as `23-bit still-life', `period-19 oscillator' or `thing that doesn't belong to the list of common objects', rather than asking merely for a specific object such as a pentadecathlon.


Now that we have over 200 trillion objects censused in b3s23/C1, I can now state more clearly how I would do this:

  • Firstly, restrict ourselves to the xp, xq, and yl tabulations.
  • For each tabulation, we look for the least common object which has at least 10 more occurrences than all of the objects below it combined. In the case of xp3, I think it's xp3_025qz32qq1. Now combine all of the rarer objects (including all undiscovered objects) in this category into a meta-object, xp3_rare, and place it below xp3_025qz32qq1 in the tabulation. This makes every tabulation reasonably short.
  • Combine all of the tabulations into a single list, sorted into descending order of occurrences.
  • Calculate the reverse cumulative sum of the number of occurrences. Divide this by 10^8 to get the 'difficulty' associated with a particular object.
  • For a specified difficulty target D, the 'interesting' objects are those whose difficulty exceeds D. Note that any xp3 rarer than xp3_025qz32qq1 is clumped into 'xp3_rare', so if D exceeds the difficulty of xp3_rare, then no xp3 will be considered interesting.

Since a moderately good CPU can process about 10^8 objects (~5 million soups) per hour, D can be interpreted as the expected number of CPU-hours before you find an object whose difficulty exceeds D.

A desirable property is that a blockchain using this proof-of-work would bootstrap itself: it would use the soups submitted as proofs-of-work in order to update its internal list of rare objects. The current Catagolue census should be used as the prior estimate of rare object frequencies; the blockchain will continually update the posterior distribution each time a new block is mined.

Apart from the proof-of-work system (which interprets the SHA-256 as a b3s23/C1 soup, runs it, and checks whether it contains at least one object of difficulty at least D), the blockchain could operate identically to the Bitcoin implementation. I mentioned this as an answer to a MathOverflow question: https://mathoverflow.net/a/277668/39521
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: CAcoin

Postby Macbi » September 30th, 2017, 12:29 pm

dvgrn wrote:We can't really award Bitcoin-like points to incremental negative results, like "there is no p19 oscillator inside an 8x8 bounding box", because _that_ result can't be verified without doing exactly the same amount of work again, independently... and it seems to me that that would open the door for sending in false negative results as a claim for work accomplished.


Most SAT solvers now produce "UNSAT certificates" for negative results. Indeed they are now required for the main SAT competition. So proof-of-work for this sort of thing shouldn't be too hard.
User avatar
Macbi
 
Posts: 170
Joined: March 29th, 2009, 4:58 am

Re: CAcoin

Postby Apple Bottom » September 30th, 2017, 2:07 pm

calcyman wrote:I mentioned this as an answer to a MathOverflow question: https://mathoverflow.net/a/277668/39521


Oh, I just have to ask. Does this:

Calcyman on MathOverflow wrote:Discussion of the prospect of a cryptocurrency based on cellular automata prompted me to start developing the Catagolue project in the summer of 2014. The proof-of-work system was deliberately chosen to enable a cryptocurrency to be built upon it:


mean that the entire raison d'être of Catagolue in general, and the B3/S23/C1 census in particular, has actually always been to enable a new cryptocurrency, rather than (say) to provide a clearer image of how commonly objects are found in soup ash, to collect sample soups allowing for new and/or improved glider syntheses, or to find new objects (such as Rich's p16)?

(Please excuse me, I gotta let my mind boggle for a while.)
Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 761
Joined: July 27th, 2015, 2:06 pm

Re: CAcoin

Postby calcyman » September 30th, 2017, 4:40 pm

Apple Bottom wrote:
calcyman wrote:I mentioned this as an answer to a MathOverflow question: https://mathoverflow.net/a/277668/39521


Oh, I just have to ask. Does this:

Calcyman on MathOverflow wrote:Discussion of the prospect of a cryptocurrency based on cellular automata prompted me to start developing the Catagolue project in the summer of 2014. The proof-of-work system was deliberately chosen to enable a cryptocurrency to be built upon it:


mean that the entire raison d'être of Catagolue in general, and the B3/S23/C1 census in particular, has actually always been to enable a new cryptocurrency, rather than (say) to provide a clearer image of how commonly objects are found in soup ash, to collect sample soups allowing for new and/or improved glider syntheses, or to find new objects (such as Rich's p16)?

(Please excuse me, I gotta let my mind boggle for a while.)


Quite the reverse. I noticed how much computing power was wasted on mining Bitcoin, and (as a Lifenthusiast) instinctively wondered whether I could create a cryptocurrency whereby everyone is incentivised to find interesting objects in GoL. That is to say, I hoped that I could ultimately make Catagolue self-sustaining, whereby people uninterested in cellular automata would still end up 'mining Lifecoin' and contribute to our collective knowledge of GoL as a wonderful side-effect.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: CAcoin

Postby Apple Bottom » September 30th, 2017, 4:43 pm

calcyman wrote:Quite the reverse. I noticed how much computing power was wasted on mining Bitcoin, and (as a Lifenthusiast) instinctively wondered whether I could create a cryptocurrency whereby everyone is incentivised to find interesting objects in GoL. That is to say, I hoped that I could ultimately make Catagolue self-sustaining, whereby people uninterested in cellular automata would still end up 'mining Lifecoin' and contribute to our collective knowledge of GoL as a wonderful side-effect.


Ah, thanks for the clarification! It really shouldn't matter, since the end result is the same one way or another, but that's a relief.

I do hope that AshCash / Lifecoin / ... will take off, if it is ever created! (And I'm not just saying that as a likely early miner. :))
Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 761
Joined: July 27th, 2015, 2:06 pm

Re: CAcoin

Postby Ajoub » October 7th, 2017, 12:51 pm

That makes a lot of sense Calcyman.
Ajoub
 
Posts: 1
Joined: September 26th, 2017, 11:14 am


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests