Elementary Cellular Automata as Non-Cryptographic Hash Functions

Daniel McKinley

REVIEW 4 major objections 4 minor 7 references

Elementary Cellular Automata as Non-Cryptographic Hash Functions

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ten elementary cellular automata rules form a collision-free, invertible hash over wrapped 4x4 neighborhoods.

desk verdict A reproducible 4x4 exhaustive-search nugget, but the collision-free/invertible hash claims do not survive contact with the paper's own lossy inverse and 4:1 compression mode. read the letter →

arxiv 2506.06551 v1 pith:6O6PTKYD submitted 2025-06-06 nlin.CG cs.FL

Daniel McKinley This is my paper

classification nlin.CGcs.FL MSC 37B15

keywords elementarycellularautomatanon-cryptographichashcodewordtruthtablelossycompressionretroactivehashingedgedetectionFastWalsh-Hadamardstructurecollision-free

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper presents ten of the 256 elementary cellular automata rules as a non-cryptographic hash function. The central claim is that, when each wrapped 4x4 neighborhood is replaced by a 4-bit codeword chosen by an error-minimizing or error-maximizing score, every one of the 65,536 possible neighborhoods has a unique codeword and the codewords are distributed evenly. From that local uniqueness the author concludes that any input of any size has a unique hash and that collisions do not happen for a given size. The construction also offers a deterministic but lossy inverse, operations that can be applied inside the hashed state, and a powers-of-two neighborhood structure that parallels the Fast Fourier and Fast Walsh-Hadamard transforms. The paper supports these properties with code experiments and visual tests rather than a mathematical proof, and it describes the inverse-error rates as ranging from 0.02 to 0.7 errors per bit.

What carries the argument

The load-bearing object is the codeword truth table produced by the error-scoring rule. For a fixed elementary cellular automaton rule, each of the 65,536 possible 4x4 grids is set up with row 0 as the input and rows 1-3 as the automaton's output; the 16 candidate row-0 patterns are scored by summing discrepancies between the original input and the generated output, weighted by $2^r$ (row weighting) or $2^c$ (column weighting). The best and worst scores form a 4-bit minimizing/maximizing codeword pair, and collecting the pairs over all 4x4 inputs gives the truth table that subsequent hashing looks up. Iteration compares neighborhoods at distances $2^d$, the same powers-of-two spacing as the FFT and fast Walsh-Hadamard transform, and the claim is that composing these lookups preserves uniqueness and even distribution. The same table also stores the logic-gate transforms that make retroactive hashing work.

What would settle it

Take the row-weighted rule set, hash every distinct binary grid of a modest larger size (for example every 8x4 or two-iteration 8x8 grid) and check whether any two different inputs produce the same hash; one collision would refute the Section 3.4 claim. A complementary check is to run the voting inverse on a large sample of hashed outputs and ask whether two different inputs ever invert to the same original, which would contradict the claimed one-to-one behavior.

Watch

Extended reading notes

Core claim

The discovery the paper wants to establish is that a small family of elementary cellular automata rules, applied to wrapped 4x4 binary neighborhoods, acts as a collision-free non-cryptographic hash with unusual extra capabilities. Two overlapping sets of eight rules are identified, one weighted by $2^r$ (rules 0, 15, 51, 85, 170, 204, 240, 255) and one weighted by $2^c$ (rules 0, 15, 85, 90, 165, 170, 240, 255). For both sets the paper reports unique codeword solutions for every 4x4 input and perfectly even codeword distribution across the full 65,536-entry truth table, and it takes this local uniqueness to imply that every input of any size has a unique hash with no collisions for a fixed size. On top of that, the hash is invertible by a voting procedure, reversible enough to reconstruct approximate originals, and supports retroactive hashing, meaning two hashed values can be logic-combined with a transformed gate so that watermarks or bitmasks can be applied without restoring the original data. The same iteration scheme, with neighbor distances doubling each round, is the nested powers-of-two pattern of the FFT, with hash lookups replacing sums.

Load-bearing premise

The load-bearing premise is that the unique, evenly distributed codeword behavior verified exhaustively on the 4x4 truth table continues to hold when codeword outputs are re-hashed at deeper iterations, so that no two inputs of the same larger size ever collide.

Editorial extensions

If this is right

Binary data of any size can be hashed to a fixed output size, either by hashing in place or by compressing so the data quarters in size each iteration, with the paper's claim that collisions do not happen for a given size.
Hashed values can be logically combined without inversion, which would allow watermarks, IP-address bitmasks, or similar updates to be applied directly to a hashed image.
A deterministic voting-based inverse reconstructs an approximation of the original input, with measured losses of 0.02 to 0.7 errors per bit depending on parameters.
At shallow depths the hash acts as an edge detector: flat man-made surfaces merge toward a single color while natural texture stays chaotic, with sharp transitions at edges and corners.
The algorithm can be organized like an FFT butterfly network, suggesting an $O(N \log N)$-style structure where each tile is a lookup into the precomputed codeword table.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A reader should treat the global no-collisions statement as an open conjecture: exhaustive uniqueness on every 4x4 neighborhood does not by itself prove that repeated hashing of larger grids remains injective, since the paper only samples 8x8 tiles and does not bound collision probabilities.
If the retroactive logic-gate transforms are as uniform as reported for the row-weighted rules, the construction gives a lightweight, non-cryptographic analogue of computing on encrypted data, with the caveat that its minimal avalanche and linear rules are not secure by cryptographic standards.
The reported lossy inverse error rates (0.02 to 0.7 errors per bit) sit in tension with the collision-free claim; a direct experiment relating inverse reconstruction error to injectivity would clarify whether the two properties can both hold.
A natural next test is to move from 4x4 to 8x8 tiles, where each tile has 256 possible codewords and exhaustive enumeration of all $2^{64}$ inputs is infeasible; proving uniqueness there would require a symmetry argument rather than a truth-table sweep.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

Read this one if you want a clear example of a local truth-table result being over-extrapolated to global claims. The genuinely new thing is the construction: running ECA rules through a wrapped 4x4 error-scoring codeword lookup, and the exhaustive identification of 10 rules whose 32-codeword sets are unique and evenly distributed across all 65536 inputs. That is a concrete, checkable result, and the author's code appears to support it. The retroactive logic-gate transform in Section 3.2 is also a real observation, though only verified on the row-weighted set and randomly at size 8.

The soft spots are load-bearing, not cosmetic. Section 3.4 claims 'any given input of any size or shape is unique and collisions don't happen for a given size' on the strength of every 4x4 neighborhood having a unique solution. That inference is invalid: injectivity of an overlapping, iterated local map is not guaranteed by local uniqueness of non-overlapping tiles, and Section 4.2 admits only 4x4 was exhaustively tested, with random sampling at 8x8. Meanwhile Section 3.3 reports a lossy inverse with 0.02 to 0.7 errors per bit. If the forward map were injective on arrays of fixed size, the inverse of an image would recover the input exactly. Persistent reconstruction error means many-to-one. And compression mode, which maps 16-bit tiles to 4-bit codewords, is impossible by pigeonhole. These are not nitpicks; they invalidate the central claims as stated.

What is not wrong: the author is transparent about the exploratory status, repeatedly noting active development and explicitly limiting exhaustive verification to 4x4. The paper does not hide its own limitations; it just fails to connect them to the abstract's findings. The trigintaduonion paragraph and the FFT analogy are ornamental and could be cut without loss.

Who gets value: someone working on non-cryptographic image hashing might mine the 4x4 rule set and the gate-transform tables as a starting point. But the paper as written is a project report, not a result.

Recommendation: I would send it to a serious referee, but only because the exhaustive 4x4 statistics are real and the overclaims are fixable. The referee should require the authors to either prove or drop the global injectivity claim, acknowledge the pigeonhole limit on compression, and compare against existing non-cryptographic hashes. With that revision it could become a modest but honest tool report. As is, it should not be published as a claim of a collision-free hash.

Best,

Referee Report

4 major / 4 minor

Summary. The paper proposes ten elementary cellular automata rules as the basis of a non-cryptographic hash. The hash operates by partitioning input into wrapped 4x4 neighborhoods, using an error-minimization/maximization search to associate each neighborhood with 4-bit codewords, and then iterating at power-of-two neighbor distances. The author claims that several of these rules yield unique codewords, perfectly even codeword distributions, no collisions for inputs of a given size, a deterministic lossy inverse, retroactive logic operations on hashed data, and an application to edge detection. The paper reports exhaustive enumeration of all 65536 4x4 inputs for the rule-selection truth tables, random testing at 8x8, and visual results on bitmap images.

Significance. The paper's main value is empirical: it identifies explicit rule sets with notable local behavior on 4x4 neighborhoods and demonstrates a plausible image-hashing application. The exhaustive 65536-entry verification for 4x4 tiles and the explicit lists of rules are strengths that would be useful if the global claims were properly substantiated. However, the central advertised property—that arbitrary-size inputs have unique hashes with no collisions—is not established and is in tension with other reported properties, notably the lossy inverse and the compression mode. If the global injectivity claim were replaced by a more modest claim about local uniqueness and observed behavior, the contribution would be an exploratory application note rather than a rigorous hash-function construction.

major comments (4)

[Sections 3.1 and 3.4] The inference from local 4x4 codeword uniqueness to global injectivity is invalid. Section 3.1 establishes a truth-table statistic: for each of the 65536 4x4 inputs, the recorded codeword set is distinct. Section 3.4 then states that 'any given input of any size or shape is unique and collisions don't happen for a given size' because every neighborhood has a unique solution. This does not follow. The hash-in-place operation uses overlapping 4x4 neighborhoods and iterates at doubled distances (Section 2); injectivity of a local map on non-overlapping tiles does not compose under overlapping updates. Section 4.2 explicitly states that 8x8 behavior is only randomly tested, not exhaustively verified. A proof, invariant, or exhaustive check bridging the local-to-global step is required, but none is provided.
[Section 3.3 vs. Section 3.4] The reported lossy inverse directly contradicts the no-collision claim for the stored hash representation. Section 3.3 reports a deterministic inverse producing 0.02 to 0.7 errors per bit. If the forward hash were injective on arrays of a given size, the inverse of any hash value would be the unique preimage and would recover the input exactly. Persistent reconstruction error implies that the forward map is many-to-one on the representation actually hashed. The response in Section 3.4 that uniqueness resides in the full 32-codeword set does not resolve this, because the hash-in-place and compression modes described in Section 3.5 do not store all 32 codewords per input tile.
[Section 3.5] The compression mode cannot be injective. Section 3.5 states that the data size quarters each iteration in compression mode, meaning a 16-bit 4x4 tile is mapped to a 4-bit codeword. By the pigeonhole principle, any such map from a larger domain to a smaller codeword space must have collisions. This contradicts the blanket statement in Section 3.4 that 'collisions don't happen for a given size.' Unless the hash output is defined to include all codewords for every tile, which is not the description of the implemented modes, the no-collision claim is false for compression.
[Section 3.2] The retroactive-hashing claim is overgeneralized relative to the evidence. The paper states that the shift of logic operations is 'uniform within an ECA rule hash and extends to any depth of iteration,' but the supporting evidence is a row-weighted truth table and the statement that equivalences 'appear to carry over to size 8 in random testing.' The column-weighted table contains many entries marked '77' (no valid operation), so the claim cannot hold for the full advertised rule set. A proof or at least an exhaustive small-size verification for the relevant operations and iterations is needed before claiming a general property.

minor comments (4)

[Section 1.1] The word 'determinine' should be 'determine'.
[Section 4.1] The word 'avalailable' should be 'available'.
[Section 3.1] The sentence about trigintaduonions is not self-contained: the claim that a complete codeword set 'can be encoded as trigintaduonions' and that 'no negative members' exist because the sixteenth's place is the negative bit is unexplained and appears unrelated to the hash's functionality.
[Section 4.2] The phrase 'maxxed or minned' is informal and should be rephrased as 'maximized or minimized'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the claimed local uniqueness/even-distribution properties are outputs of an exhaustive 4x4 enumeration, and the global-injectivity extension is an unsupported inference, not a self-referential derivation.

full rationale

The paper's load-bearing local properties are produced by enumerating all 65536 wrapped 4x4 inputs, computing, for each, the 4-bit codewords minimizing and maximizing a weighted error score, and then checking uniqueness and even distribution (Sections 2 and 3.1). These properties are outputs of that computation, not inputs: the error-minimization search does not assume uniqueness or even distribution, so reporting them is not definitional. The step that comes closest to a circular pattern is Section 3.4's claim that 'Since every neighborhood has a unique solution, any size of any given input has a unique hash if hashing in place and not compressing.' This is an extrapolation from the 4x4 truth table to arbitrary-size inputs; the paper itself limits exhaustive verification to 4x4 and uses only random testing at 8x8 (Section 4.2). That inference is logically unsupported and may conflict with the lossy inverse (Section 3.3), but it is not circular: the premise (local uniqueness) is independently computed and does not contain the global-injectivity conclusion by construction. No parameter is fitted to a subset of data and then reported as a prediction of a closely related quantity; the rule selection from all 256 ECA rules is a search, not a fit, and the uniqueness property is verified after selection rather than enforced as the selection criterion in a way that would manufacture the result. The only self-link is reference [2], the author's website, which is used for code and images and is not load-bearing for the mathematical claims; no cited uniqueness theorem from the author's prior work is invoked. Concerns about the validity of the global claim, the absence of external benchmarks, and the inverse error rates are correctness and evidence concerns, not circularity. A zero circularity score is therefore appropriate.

Assumptions & free parameters 3 free parameters · 4 assumptions · 1 invented entities

The construction's claims rest on an exhaustive search over chosen scoring parameters and on unproven composition assumptions rather than on fitted predictions, so the ledger is dominated by design choices and domain assumptions. The genuinely invented entity (trigintaduonions) is decorative. No parameter is fitted to optimize a benchmark; the hand choices (4x4 tiles, 2^row and 2^column weights, min and max selection) determine which rules land in the claimed special subsets.

free parameters (3)

error weights 2^row / 2^column = 2^r and 2^c weight per bit position
The scoring scheme that defines the minimizing and maximizing codewords is hand-chosen; the set of 10 rules that exhibit the claimed uniqueness and balance depends entirely on this weighting choice (Sections 2 and 3.1).
tile size 4x4 (wrapped) = 4
The neighborhood size is chosen by hand; uniqueness and balance are only exhaustively verified at this size (Section 4.2).
avalanche depth threshold = log2 of the larger image dimension
The paper defines the iteration count after which every bit has influenced every other bit; this is a definitional choice, but the claimed propagation behavior is assessed relative to it (Section 2).

assumptions (4)

domain assumption Wolfram's elementary cellular automata update rule applies to wrapped 3-bit neighborhoods (rows 1-3 of each 4x4 tile), with no interaction between tiles beyond the 4x4 window.
The whole construction rests on treating the ECA as a local transition on wrapped 4x4 windows (Section 2).
domain assumption Each 16-bit input has a unique tie-free minimizing and maximizing codeword pair; no ties in the error score.
Stated as exhaustively verified at size 4, but the global claims require this at every tile at every depth; the paper gives no argument against ties for re-hashed codeword states (Sections 3.1 and 4.2).
ad hoc to paper Local injectivity (balanced, unique codeword selection per tile) composes across tiles and across iterations to global uniqueness of the whole-array hash.
The paper asserts 'Since every neighborhood has a unique solution, any size of any given input has a unique hash if hashing in place and not compressing' (Section 3.1); the composition step is never proven and only randomly sampled at size 8.
domain assumption The retroactive-hashing gate equivalences (logicGate(A) after hashing equals logicGate(B) before hashing) persist to all depths of iteration.
Verified experimentally on truth tables and said to 'appear to carry over to size 8 in random testing' (Section 3.2); the column-weighted set is explicitly incomplete, with 77 entries for no valid operation.

invented entities (1)

trigintaduonions (32-element hypercomplex ring) as an encoding of the codeword set
purpose: Offered as a structure that can encode the 32 min/max 4-bit codewords with no negative members, claimed to aid physical interpretations, orthonormal data structures, and GF(2^m) integration.
Introduced in Section 3.1 without definition, construction, or consequence; it plays no role in the hash algorithm or its verification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Elementary Cellular Automata as Non-Cryptographic Hash Functions." pith.science (2026). https://pith.science/paper/6O6PTKYD

@misc{pith2026250606551,
  author       = {Pith},
  title        = {Pith review of: Elementary Cellular Automata as Non-Cryptographic Hash Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6O6PTKYD}},
  note         = {Machine review of arXiv:2506.06551}
}

read the original abstract

A subset of 10 of the 256 elementary cellular automata (ECA) are implemented as a hash function using an error minimization lossy compression algorithm operating on wrapped 4x4 neighborhood cells. All 256 rules are processed and 10 rules in two subsets of 8 are found to have properties that include both error minimization and maximization, unique solutions, a lossy inverse, efficient retroactive hashing, and an application to edge detection. The algorithm parallels the nested powers-of-two structure of the Fast Fourier Transform and Fast Walsh-Hadamard Transform, is implemented in Java, and is built to hash any 2 byte RGB code bitmap.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

A novel hybrid elementary cellular automata and its application in a stream cipher.Applied Sciences, 14(21), 2024

Peng Du, Youheng Dong, Qi Cui, and Hui Li. A novel hybrid elementary cellular automata and its application in a stream cipher.Applied Sciences, 14(21), 2024

work page 2024
[2]

https://www.danielmckinley.com, 2025

Daniel McKinley. https://www.danielmckinley.com, 2025

work page 2025
[3]

Kartik Rajeshwaran and Kakelli Anil Kumar. Cellular automata based hashing algorithm (cabha) for strong cryptographic hash function.2019 IEEE International Conference on Elec- trical, Computer and Communication Technologies (ICECCT), pages 1–6, 2019

work page 2019
[4]

Weisstein

Todd Rowland and Eric W. Weisstein. Additive cellular automaton

work page
[5]

A design of a new hash function based on cellular automata

Youssef Sbaytri and Saiida Lazaar. A design of a new hash function based on cellular automata. Journal of Theoretical and Applied Information Technology, 99:2280–2289, 05 2021

work page 2021
[6]

Fast walsh–algorithmcode.hadamard transform — Wikipedia, the free encyclopedia, 2024

Wikipedia contributors. Fast walsh–algorithmcode.hadamard transform — Wikipedia, the free encyclopedia, 2024. [Online; accessed 4-April-2025]

work page 2024
[7]

Wolfram Media, 2002

Stephen Wolfram.A New Kind of Science. Wolfram Media, 2002. 10

work page 2002

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

A novel hybrid elementary cellular automata and its application in a stream cipher.Applied Sciences, 14(21), 2024

Peng Du, Youheng Dong, Qi Cui, and Hui Li. A novel hybrid elementary cellular automata and its application in a stream cipher.Applied Sciences, 14(21), 2024

work page 2024

[2] [2]

https://www.danielmckinley.com, 2025

Daniel McKinley. https://www.danielmckinley.com, 2025

work page 2025

[3] [3]

Kartik Rajeshwaran and Kakelli Anil Kumar. Cellular automata based hashing algorithm (cabha) for strong cryptographic hash function.2019 IEEE International Conference on Elec- trical, Computer and Communication Technologies (ICECCT), pages 1–6, 2019

work page 2019

[4] [4]

Weisstein

Todd Rowland and Eric W. Weisstein. Additive cellular automaton

work page

[5] [5]

A design of a new hash function based on cellular automata

Youssef Sbaytri and Saiida Lazaar. A design of a new hash function based on cellular automata. Journal of Theoretical and Applied Information Technology, 99:2280–2289, 05 2021

work page 2021

[6] [6]

Fast walsh–algorithmcode.hadamard transform — Wikipedia, the free encyclopedia, 2024

Wikipedia contributors. Fast walsh–algorithmcode.hadamard transform — Wikipedia, the free encyclopedia, 2024. [Online; accessed 4-April-2025]

work page 2024

[7] [7]

Wolfram Media, 2002

Stephen Wolfram.A New Kind of Science. Wolfram Media, 2002. 10

work page 2002