Pufferfish article

[calcyman]

Ivan Fomichev has written an article on the pufferfish, its discovery, and applications:

http://translate.google.co.uk/translate ... st/253809/

It appears that Google Translate corrupted the meaning of the original Russian text:

The very idea of such a program is not new, but Adam failed, firstly, to create an efficient algorithm census objects, and, secondly, to make the program convenient and accessible, thanks to the implementation of a Python-script for Golly , the most popular and advanced programs for today for the game "Life".

Anyway, it generated lots of traffic to Catagolue (costing the princely sum of 0.11 USD):



Unfortunately, it did not result in new people actually contributing CPU cycles to the project.

[flipper77]

Unfortunately, it did not result in new people actually contributing CPU cycles to the project.

This is indeed unfortunate, but it's still great that catagolue and CGoL have gained some attention from this, and hopefully won't be the last.

[codeholic]

Unfortunately, it did not result in new people actually contributing CPU cycles to the project.

That was my intent, inspired by your own suggestion (you mentioned Hacker News, and Habrahabr is one of the most famous hubs in Russian IT community). Unfortunately I didn't come up with any idea, how to achieve it without adding extra cost on you as the maintainer.

And yes, "удалось" means something quite opposite from "failed".

EDIT: I also hoped to attract new members to conwaylife.com community, but it seems I failed even in that. I'm looking forward to write another article on the weekender distaff with more technical details, that would hopefully ignite more interest.

[dvgrn]

I'm looking forward to write another article on the weekender distaff with more technical details, that would hopefully ignite more interest.

Best of luck! I used to try to get Slashdot interested in things like this, but it's hard to make something go viral when you want it to.

Still, it does seem like a decent fraction of the Slashdot crowd (a tiny percentage but still a large number) _would_ take an interest. But is it even a good idea to invite a Slashdotting of Catagolue?

There's potential there for an order of magnitude increase in the number of soups contributed, basically overnight. Not sure exactly how much that would cost our fearless Ash Pattern Generator, though-- maybe a Kickstarter campaign should be run in parallel with any attempts to get this kind of attention.

[calcyman]

There's potential there for an order of magnitude increase in the number of soups contributed, basically overnight.

Catagolue should be able to withstand about 20 or 30 times its current daily load before reaching the imposed safety limit of 1.00 USD per day. I can increase the limit if necessary (at the moment I'm one-quarter of the way through a 60-day free trial with a maximum of 300.00 USD, only 0.14 USD of which has been used).

I'm more worried about one malevolent person hacking apgsearch to post a false haul, or run a denial-of-service attack (there's a very thin layer of protection offered by payosha256), or any manner of other malicious acts. I mean, we might be okay on Hacker News, or even Slashdot, but sites such as Reddit or 4chan should probably be avoided.

Does anyone have an idea how I could improve the security of the (quite valuable, now that it's had about 20000 CPU-hours of work invested) b3s23/C1 census? I've thought of the following ideas:

• Perform a server-side chi-squared test on reported soup objects versus existing Catagolue objects and discount any clearly outlandish claims (reasonably easy to implement, and will stop pure-garbage attacks).
• Make other instances of the apgsearch client spend a small proportion of their time checking the reported soups in uncommitted Catagolue hauls before 'confirming' it as being genuine. This would take more effort to implement, but will completely circumvent false claims of rare objects.
• Create a periodic backup of the Catagolue.

I'll also need to fix the server-side code to catch unhandled NumberFormatExceptions if someone sadistically decides it would be amusing to submit a haul which reports there have been 354cabbage78 instances of the pulsar.

[rowett]

Make other instances of the apgsearch client spend a small proportion of their time checking the reported soups in uncommitted Catagolue hauls before 'confirming' it as being genuine. This would take more effort to implement, but will completely circumvent false claims of rare objects.

In some of the Grid computing projects they took a similar approach. The server would hand out work units to the distributed clients and on receiving a response to a particular work unit would not put it in the catalogue until another client from a different user had processed the same work unit and given the same response. In their case it was easy since the allocation of work units was server controlled. In this case the work units are picked at random by the clients.
So basically the verification has to happen somewhere, do you do it all server side or distribute it?

[biggiemac]

Yeah, I remember reading that BOINC uses redundancy as an error check, and the difference here is that the code is run independently. And as my own experience shows, it is straightforward to add a symmetry option and send the results to catagolue without there being any support for it - even a well-meaning hacker could really add problematic levels of unpredictability to the system. Not to mention that people could change the hashsoup() function to simply place the loafer in bit-for-bit plus external sparks, and any individual soup couldn't be proven unrandom, rather disproof would come by a server-side chi-squared test. EDIT: I see that this was wrong, thanks for the reminder.

Deveolping and releasing a single executable (that runs without Golly, perhaps?) and communicates with Catagolue's server via some secure encrypted protocol would be the ideal way to increase the CPU hours here. This would lower the activation energy to contribute while making the activation energy to tamper much much higher.

[calcyman]

And as my own experience shows, it is straightforward to add a symmetry option and send the results to catagolue without there being any support for it

That's a good point; I should add this to my to-do list.

Not to mention that people could change the hashsoup() function to simply place the loafer in bit-for-bit plus external sparks, and any individual soup couldn't be proven unrandom

No, because apgsearch doesn't upload the soups; it uploads the strings which are hashed to give the soups*. And it's intractable** to reverse-engineer SHA-256 to find a preimage of your favourite sub-16-by-16 object (e.g. a loafer).

* which you should already know, since that's precisely why your 25pct and 75pct soups weren't interpreted correctly until I changed the server-side hashsoup() function to accommodate the new symmetry types.

** that is to say, the computational difficulty of getting the top-left 9-by-9 box to be a particular configuration (in this case, a loafer and nothing else) is 2^81 hashes, which is roughly the total amount of hashpower dedicated to Bitcoin since its conception.

On the subject of cryptocurrencies, implementing Lifecoin is quite low on my deque of programming projects and my free time is rather limited, so don't expect it to come to fruition this year. (Incidentally, please don't attempt to get me rusticated, sacked or dumped in order to increase my amount of free time; even Niccolo Machiavelli would consider that to be a step too far.)

I did, however, have enough free time this evening to implement a new b3s23/C1-specific 'statistics' page on Catagolue to summarise our favourite census:

http://catagolue.appspot.com/statistics

This is similar to the homepages of Achim and Andrzej, but dynamically created by the server. As such, please don't DDoS it; each /statistics request costs about 50 datastore read operations and there's no caching. The same situation occurs with /textcensus, so that infernal Python script which sequentially examines all symmetries has a huge carbon footprint (probably 1000 reads or so).

[flipper77]

... so that infernal Python script which sequentially examines all symmetries has a huge carbon footprint (probably 1000 reads or so).

That's good to know, I'll do my best to use that script sparingly. I'm really liking the statistics page, and it's also good that the help page describes the markdown formatting as well as how canonical representations work, which I'll give a reading soon.

[towerator]

I would have a suggestion for agpsearch/catagolue:
If catagolue is unreachable, can you make agpsearch store the data on the computer, then transmit it (and erase it) when internet comes back? I've lost something like 20 million soups because of this.

[calcyman]

If catagolue is unreachable, can you make agpsearch store the data on the computer, then transmit it (and erase it) when internet comes back?

It already does precisely what you describe.

[towerator]

Ah.
Well, I just learned something.
Sorry for posting something pointless!

[gameoflifeboy]

Can someone please explain how the apgcode for a linearly-growing object gets constructed? The description of the canonical pattern codes page didn't explain that and all I know is that it starts with yl and then a factor of the LCM of the period of the front and back.