Non interactive zero knowledge proof in CGOL

[simsim314]

Zero knowledge proof is a way to reveal a proof that you have something "valid" in your hands, which impossible to fake while not revealing the thing itself. I was thinking about CGOL implementation for this kind of application.

An almost very simple result: lets take a 16x16 initial state and toggle each time a single cell, and evolve up to stabilization. The 256 resulting patterns are impossible to fake if you reveal your answer i.e. you can use those 256 states as proof when you reveal the answer, but you can't use it as a proof without revealing.

We can use some statistical analysis how probable that a single cell will change emitting glider, or final SL. As we don't know how many different statistical validation we can make, it would be improbable to fake without eventually finding out. Yet every specific statistics might be faken. I thought of training a network (each node can validate by training it's own network) or asking for catalysts which are much harder to fake - but yet still it's not a real proof that we initially had a valid CGOL state.