Proof-of-work (PoW) blockchains expend energy solely for network security. Proof of Useful Work (PoUW) aims to reclaim this cost, but stateful proving (e.g., multi-phase STARKs) breaks the memoryless property required for Nakamoto consensus. ZK-SPoW (Zero-Knowledge Symbiotic Proof of Work) inverts the relationship: instead of making PoW useful, useful STARK Merkle hashing naturally produces PoW tickets as a cryptographic byproduct of every Poseidon2 permutation. Under the pseudorandom permutation (PRP) assumption, each permutation is computationally indistinguishable from an independent Bernoulli trial at nanosecond granularity — restoring computational memorylessness at the permutation level without sacrificing useful computation. We instantiate with Width-24 Poseidon2 over M31: each permutation simultaneously produces a Merkle parent (ZK output) and three PoW tickets. Usefulness is not protocol-enforced but market-driven — miners select which ZK proofs to generate or fall back to Pure PoW, guided by proof demand. Statistical validation via the full NIST SP 800-22 test suite (15/15 tests pass) confirms the pseudorandom quality of the Poseidon2-based mining output.
Mitsuru Kurosu (Fri,) studied this question.