Cryptography with Cellular Automata (1985) [pdf] | Hacker News Reader

Cryptography with Cellular Automata (1985) [pdf]

stephenwolfram.com

67 pointsCieplak15 comments

Anyone wanting to tinker with Cellular Automata may be interested in Golly [1], an open source cellular automata simulator which allows you to play with different neighborhoods and rules and see the results.

[1]. http://golly.sourceforge.net/

Can anybody explain concepts of Cellular Automata?

I am familiar with DFA, NFAs. But I always had problem understanding Cellular Automata and it’s usage.

It means that a set of rules (generally small) governs how "cells" live or die in their universe. Conway's game of life is a cellular automaton in 2d board, with cells being either alive or dead. Woflram's automaton has a single dimension with the rules being encoded over 8 bits.

Here's some literature for Wolfram's automaton:

* https://www.wolframscience.com/nks/p24--how-do-simple-progra...

* http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere...

And my F# implementation:

https://github.com/msarilar/CellularAutomaton/blob/master/in...

Usage is tricky; as far as I'm aware there are no real uses of cellular automata in the wild. Here Wolfram is using the fact that the future state of a CA is difficult to predict or reverse, which is a good property for a cryptographic hash function, but as far as I'm aware, this has not been adopted into any modern cryptosystems. There are a couple of articles that follow up on this, including [1], which seems to indicate that the system is vulnerable to chosen-plaintext attacks.

http://jsfiddle.net/yxz4su0r/ illustrates the calculation of the 1d cellular automaton that Wolfram discusses in his article.

[1] https://dl.acm.org/citation.cfm?id=1025039&CFID=998930375&CF...

CA is a pretty broad topic with a lot of work having been done on it. I've had a tangential interest in it since I was young and have read a bit (but only a bit) of the research. In terms of practical applications, I know CAs are used in simulation of various types. The earliest I recall hearing about was use of CA to simulate the spread of wildfires taking geography and plant growth into account. I've also seen multiple attempts at using CA to simulate dynamic flows, sort of an alternative to Navier-Stokes solving, but I don't think that's used commercially.

Just recently I came across a paper using CAs for both image compression and data encryption. The image compression worked a lot like fractal image compression, relying on the fact that any contractive mapping has an eventual fixed point under repeated iteration. The paper was a difficult read and felt like nothing more than an attempt by the author to get people to buy his book, not giving any detail about hardly anything.

Wolfram's A New Kind of Science describes cellular automata in detail. The online version is free, https://www.wolframscience.com/nks/ A used copy is typically inexpensive and worth reading in my opinion, though other people have substantially different opinions and express them willingly.

How about this:

If your left neighbor is on, then turn on only if your right neighbor is off.

http://mathworld.wolfram.com/ElementaryCellularAutomaton.htm...

Each cell can be thought of as its own finite automaton in the DFA/NFA sense. A cell has some properties: current state, set of states, set of transition functions, input alphabet. Like how a typical FA receives inputs from somewhere (for example, with regular expressions, an input string), your cells in a CA will also receive input: the states of the (usually immediate) neighbors.

Consider a simple 1d cellular automata. It's either dead (0) or alive (1). It has a simple set of rules:

If both neighbors are dead, it will become dead.

If both neighbors are alive and it is dead, it will become alive.

If both neighbors are alive and it is alive, it will become dead.

If one neighbor is alive and the other dead, its state is unchanged.

So there are 2 states (dead/0, alive/1), and 2 sources of input which can be put into a 2-tuple in {0,1}x{0,1}, becoming a single input.

Putting this into a typical tabular format since diagrams are hard in ascii:

       | dead | alive |
  =====================
  (0,0)| dead | dead  |
  (0,1)| dead | alive |
  (1,0)| dead | alive |
  (1,1)| alive| dead  |

So at the basic level (you can add more complexity) a cellular automata is a collection of finite automata operating on the same rules and transitioning simultaneously, but using each other's states as their inputs.

The Game of Life rules are a roughly the same but extends the automata to 2d so that each has 8 neighbors, resulting in an input being an 8-tuple. Becoming alive, staying alive, and dying change in the number of neighbors required for each.

Great explanation and examples! But to be pedantic, a cell only has one property: its current state. The set of states, transition rules, etc are properties of the rule itself.

The point you made about transitioning simultaneously is very important: "So at the basic level (you can add more complexity) a cellular automata is a collection of finite automata operating on the same rules and transitioning simultaneously, but using each other's states as their inputs."

That means you can't serially apply the rule to the cells "in place" -- each cell needs to know the value of its neighbors at the same point in time, so if you serially scan top/bottom left/right over the cells, and change each of their values according to the values of their adjacent cells in memory at the time, the inputs to the rule will be incorrect, straddling values from the previous time step (below and to the right) and the current time step (above and to the left). So you have to double buffer the cells, and read ALL the rule inputs of each cell from the previous time step buffer, then write them into the next time step buffer.

If you implement in-place Life without double buffering, it will look and behave kind of like Life, but strangely mutated, and none of the gliders or other patterns will work properly, because the rule inputs are skewed in time.

The Moveable Feast Machine I described in another posting is not technically a cellular automata, because it's asynchronous, and relaxes the requirement that all cells transition simultaneously, and it only requires that no two overlapping neighborhoods may be computed at the same time.

So with MFMs, double buffering is not necessary, and you don't have to pay for synchronization (which is extremely expensive) if you don't need it (or you can just pay for as much as you need, a la carte). The point of Moveable Feast is robust computing on massively parallel unreliable hardware, which is practically impossible with Cellular Automata's strict synchronization requirements.

There are different ways of classifying Cellular Automata rules, and defining one kind in terms of another kind.

For example, Life and Anneal (a "twisted majority rule") are both "Counting Rules" because they can be reduced to simply counting the number of neighbors, then using a look-up table or logic to determine the next state based purely on the sum of the number of neighbors (which may or may not include the center cell). Not all CA rules are counting rules, though.

https://en.wikipedia.org/wiki/Life-like_cellular_automaton

You can enumerate all possible rules (for a given set of inputs or "neighborhood") and refer to them by their rule number, an index into all possible rules of that type (the value of the lookup table as a binary number). That's what Wolfram means when he refers to "Rule 30", which is a particularly interesting two-dimensional "elementary cellular automaton". Golly has some formats for compactly enumerating and specifying rules.

http://mathworld.wolfram.com/Rule30.html

https://imgur.com/a/lKAbP

https://en.wikipedia.org/wiki/Elementary_cellular_automaton

https://en.wikipedia.org/wiki/Golly_(program)

https://github.com/gollygang/ruletablerepository/wiki/TheRul...

Each rule is defined in terms of a certain "neighborhood" of inputs.

A "neighborhood" is the set of adjacent cells that the rule may depend on. It's like a "kernel" from signal processing.

Classic 2D neighborhoods include the 9-neighbor (including center) 8-connected Moore Neighborhood (NW N NE W C E SW S E), used by Life for example:

https://en.wikipedia.org/wiki/Moore_neighborhood

The 5-neighbor 4-connected von Neumann neighborhood (N W C E S), used by John von Neumann's 29 state cellular automata rule for example:

https://en.wikipedia.org/wiki/Von_Neumann_neighborhood

The 4-neighbor rotationally symmetrical Margolus Neighborhood (C OPP CW CCW), use by billiard ball and reversible rules for example:

https://en.wikipedia.org/wiki/Block_cellular_automaton

Rules may also depend on additional inputs like the temporal phase (alternating 0/1 over two steps for two-phase rules, repeating 00/01/10/11 over four steps for four phase rules, etc), the spatial phase (low bit(s) of the x and y cell coordinates), and even corresponding cells from other rules run in parallel or video input.

For example, you can define the Margolus neighborhood in terms of the Moore neighborhood by using the temporal, horizontal and vertical phase to determine which cell is "opposite", "clockwise" or "counter clockwise". You use the time phase to alternate between two overlapping checkerboards of 2x2 cell blocks. Within each checkerboard you use the horizontal and vertical phase to determine whether to look left, right, up or down or diagonally to get the clockwise, counter clockwise or opposite cell in the 2x2 block.

https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

A "Moveable Feast Machine" is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture.

It's similar to a Cellular Automata, but it different in several important ways, for the sake of "Robust First Computing". These differences give some insight into what CA really are, and what their limitations are.

Cellular Automata are synchronous and deterministic, and can only modify the current cell: all cells are evaluated at once (so the evaluation order doesn't matter), so it's necessary to double buffer the "before" and "after" cells, and the rule can only change the value of the current (center) cell. Moveable Feast Machines are like asynchronous non-deterministic cellular automata with large windows that can modify adjacent cells.

Here's a great example with an amazing demo and explanation, and some stuff I posted about it earlier:

https://news.ycombinator.com/item?id=14236973

Robust-first Computing: Distributed City Generation:

https://www.youtube.com/watch?v=XkSXERxucPc

A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture.

The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters!

The paper "Local Routing in a new Indefinitely Scalable Architecture" [2] by Trent Small explains how those rules work, how the city streets adaptively learn how to route the cars to nearby buildings they desire to find, and illustrated the advantages of "Robust First" computing:

Abstract: Local routing is a problem which most of us face on a daily basis as we move around the cities we live in. This study proposes several routing methods based on road signs in a procedurally generated city which does not assume knowledge of global city structure and shows its overall efficiency in a variety of dense city environments. We show that techniques such as Intersection-Canalization allow for this method to be feasible for routing information arbitrarily on an architecture with limited resources.

This talk "Robust-first computing: Demon Horde Sort" [4] by Dave Ackley describes an inherently robust sorting machine, like "sorting gas", implemented with the open source Movable Feast Machine simulator, available on github [5].

A Movable Feast Machine is similar in many ways to traditional cellular automata, except for a few important differences that are necessary for infinitely scalable, robust first computing.

First, the rules are applied to cells in random order, instead of all at once sequentially (which requires double buffering). Many rule application events may execute in parallel, as long as their "light cones" or cells visible to the executing rules do not overlap.

Second, the "light cone" of a rules, aka the "neighborhood" in cellular automata terms, is larger than typical cellular automata, so the rule can see other cells several steps away.

Third, the rules have write access to all of the cells in the light cone, not just the one in the center like cellular automata rules. So they can swap cells around to enable mobile machines, which is quite difficult in cellular automata rules like John von Neumann's classic 29 state CA. [6] [7]

Forth, diffusion is built in. A rule may move the particle to another empty cell, or swap it with another particle in a different cell. And most rules automatically move the particle into a randomly chosen adjacent cell, by default. So the particles behave like gas moving with brownian motion, unless biased by "smart" rules like Maxwell's Demon, like the "sorting gas" described in the Demon Hoard Sort video.

In this video "Robust-first computing: Announcing ULAM at ECAL 2015" [8], David Ackley explains why "Robust First" computing and computing architectures like Movable Feast Machines are so incredibly important for scaling up incredibly parallel hardware.

I think this is incredibly important stuff in the long term, because we've hit the wall with determinism, and the demos are so mind blowing and visually breathtaking, that I want to try programming some of my own Movable Feast Machine systems!

[1] http://movablefeastmachine.org/

[2] https://www.youtube.com/watch?v=XkSXERxucPc

[3] http://www.cs.unm.edu/~ackley/papers/paper_tsmall1_11_24.pdf

[4] https://www.youtube.com/watch?v=helScS3coAE

[5] https://github.com/DaveAckley/MFM

[6] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton

[7] https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...

[8] https://www.youtube.com/watch?v=aR7o8GPgSLk

If you like Wolfram's state transition diagrams in figure 2, you'll love Andrew Wuensche and Mike Lesser published a gorgeous coffee table book entitled "The Global Dynamics of Cellular Automata".

I wrote some stuff in an earlier discussion about how the state transition diagrams in that book illustrate "Garden of Eden" configurations and "Basins of Attraction", to which I'll link and repeat here:

https://news.ycombinator.com/item?id=14468707

There's a thing called a "Garden of Eden" configuration that has no predecessors, which is impossible to get to from any other possible state.

For a rule like Life, there are many possible configurations that must have been created by God or somebody with a bitmap editor (or somebody who thinks he's God and uses Mathematica as a bitmap editor, like Stephen Wolfram ;), because it would have been impossible for the Life rule to evolve into those states. For example, with the "Life" rule, no possible configuration of cells could ever evolve into all cells with the value "1".

https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...

For a rule that simply sets the cell value to zero, all configurations other than pure zeros are garden of eden states, and they all lead directly into a one step attractor of all zeros which always evolves back into itself, all zeros again and again (the shortest possible attractor loop that leads directly to itself).

There is a way of graphically visualizing that global rule state space, which gives insight into the behavior of the rule and the texture and complexity of its state space!

Andrew Wuensche and Mike Lesser published a gorgeous coffee table book entitled "The Global Dynamics of Cellular Automata" that plots out the possible "Garden of Eden" states and the "Basins of Attraction" they lead into of many different one-dimensional cellular automata like rule 30.

http://uncomp.uwe.ac.uk/wuensche/gdca.html

The beautiful color plates begin on page 79 in the free pdf file:

http://uncomp.uwe.ac.uk/wuensche/downloads/papers/global_dyn...

I've uploaded the money shots to imgur:

http://imgur.com/gallery/s3dhz

Those are not pictures of 1-d cellular automata rule cell states on a grid themselves, but they are actually graphs of the abstract global state space, showing merging and looping trajectories (but not branching since the rules are deterministic -- time flows from the garden of eden leaf tips around the perimeter into (then around) the basin of attractor loops in the center, merging like springs (GOE) into tributaries into rivers into the ocean (BOA)).

The rest of the book is an atlas of all possible 1-d rules of a particular rule numbering system (like rule 30, etc), and the last image is the legend.

He developed a technique of computing and plotting the topology network of all possible states a CA can get into -- tips are "garden of eden" states that no other states can lead to, and loops are "basins of attraction".

Here is the illustration of "rule 30" from page 144 (the legend explaining it is the last photo in the above album). [I am presuming it's using the same rule numbering system as Wolfram but I'm not sure -- EDIT: I visually checked the "space time pattern from a singleton seed" thumbnail against the illustration in the article, and yes it matches rule 30!]

http://imgur.com/a/lKAbP

"The Global Dynamics of Cellular Automata introduces a powerful new perspective for the study of discrete dynamical systems. After first looking at the unique trajectory of a system's future, an algoritm is presented that directly computes the multiple merging trajectories of the systems past. A given cellular automaton will "crystallize" state space into a set of basins of attraction that typically have a topology of trees rooted on attractor cycles. Portraits of these objects are made accessible through computer generated graphics. The "Atlas" presents a complete class of such objects, and is inteded , with the accompanying software, as an aid to navigation into the vast reaches of rule behaviour space. The book will appeal to students and researchers interested in cellular automata, complex systems, computational theory, artificial life, neural networks, and aspects of genetics."

https://en.wikipedia.org/wiki/Attractor

"Basins of attraction in cellular automata", by Andrew Wuensche:

http://onlinelibrary.wiley.com/doi/10.1002/1099-0526(200007/...

"To achieve the global perspective. I devised a general method for running CA backwards in time to compute a state's predecessors with a direct reverse algorithm. So the predecessors of predecessors, and so on, can be computed, revealing the complete subtree including the "leaves," states without predecessors, the so-called “garden-of-Eden" states.

Trajectories must lead to attractors in a finite CA, so a basin of attraction is composed of merging trajectories, trees, rooted on the states making up the attractor cycle with a period of one or more. State-space is organized by the "physics" underlying the dynamic behavior into a number of these basins of attraction, making up the basin of attraction field."

If you like the book, you'll love the code!

http://www.ddlab.com/

http://www.ddlab.com/screensave3.png

http://uncomp.uwe.ac.uk/wuensche/2006_ddlab_slides1.pdf

http://uncomp.uwe.ac.uk/wuensche/meta.html

http://uncomp.uwe.ac.uk/wuensche/boa_idea.html

http://uncomp.uwe.ac.uk/wuensche/downloads/papers/2008_dd_ov...

The subjective similarity between the randomness generated by CA and the distribution of prime numbers is uncanny. There's got to be some CA that generates them.

Prime number calculator in Game of Life: https://www.youtube.com/watch?v=68nEX5CEmZE

There is, actually: http://ieeexplore.ieee.org/document/5645858/ .

Is there a use here for blockchains? Could you link block to block with a CA function or would that be weaker than the current approach that bitcoin uses?

Reply on news.ycombinator.com