Mapping finite state machines to zk-SNARKS Using Category Theory
This addresses the challenge of efficiently verifying paths in graphs for cryptographic applications like zero-knowledge proofs, though it appears incremental as it builds on existing boolean circuit methods.
The paper tackles the problem of converting finite state machines into zk-SNARKs by developing a categorical procedure that maps state space graphs to boolean circuits, which are then generalized to arbitrary graphs, with proofs of pseudofunctorial correspondences.
We provide a categorical procedure to turn graphs corresponding to state spaces of finite state machines into boolean circuits, leveraging on the fact that boolean circuits can be easily turned into zk-SNARKS. Our circuits verify that a given sequence of edges and nodes is indeed a path in the graph they represent. We then generalize to circuits verifying paths in arbitrary graphs. We prove that all of our correspondences are pseudofunctorial, and behave nicely with respect to each other.