Knots of Knowledge Proofs — A Journey into Recursive Proofs

Gokul B Alex
3 min readAug 1, 2021

Ever since I came across the engineering side of zero knowledge proof constructions like zkSNARKS, zkSTARKS, holographic proofs and bullet proofs, I was quite fascinated by the metamorphic and isomorphic lifecycle of proof creation and proof verification in various zero knowledge proof systems.

The locus and lineage of zero knowledge proofs are quite complex, covariant and convergent in nature. The fundamental property of zero knowledge proofs are quite simple to narrate — completeness, soundness, and zero — knowledge. It stems from the demonstration of knowledge of a satisfying witness to some NP statement.

If these proofs also do not reveal anything about the witness it is denoted as zero-knowledge proofs of knowledge. At the outset, the feasibility and firmness of ZKP may sound very counter intuitive. A lot of question may arise in the minds of someone who is new to these constructions.

We should know that there are two major ( Prover and Verifier ) and other minor actors ( Witness Actor, Source of Randomness, etc. ) in a zero knowledge proof setting.

How can a prover construct probabilistic proofs that are completely convincing the verifier about the knowledge of prover without disclosing the knowledge?

It is a method of generating arithmetic expressions such that they map the arguments of knowledge in succinct and seamless manner.

How can a prover construct probabilistic proofs that are false and convincing of their falsehood to the verifier?

It is all about the fluidity of the falsifiable arguments of knowledge.

How can we construct proofs that are not leaky in its fulness and finesse?

It is important to generate bounded arguments such that there is no information loss to the initial conditions of circuit construction.

Ability to obfuscate , ability to falsify, ability to transpose, ability to transpile, and ability to nullify are at the core of a zero knowledge proof construction. The realisation of non interactive systems of zero knowledge proofs have been a great milestone in the evolution of ZKP as it made them efficient. These constructions are known as zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKS). A direct consequence of a succinct argument is the concept of incrementally verifiable computation which is an important feature required for recursive and reflexive proof systems.

Philosophers like Karl Popper and others have worked on the openness of knowledge systems and reflexive relativity of economic systems. It is very interesting to find contours between the openness of knowledge and probabilistic proofs of knowledge.

Internet as a semantic and semiotic web is a manifestation of cryptographic rigor and vigor from its inception. If internet was not there, we would have really struggled to realise zero knowledge proof systems in its current format.

Taking a deep dive into zero knowledge proofs systems and their current innovative and inventive variants, we can see that the workflow and actors of ZKP systems are becoming more and more diverse.

The key focus of this article is to explore a convergence of recursive and recurrent proof systems to address the advanced attacks on DeFi systems.

There has been active research on recursive proof systems ever since 2014 when Ben-Sasson, E., Chiesa, A., Tromer, E., and Virza, M have presented a seminal paper on Scalable Zero Knowledge via Cycles of Elliptic Curves.

According to a research paper by Sean Bowe, Jack Grigg and Daira Hopwood, the possibility to reduce the verification time and communication complexity in a sub-linear mode has been one of the key factors making recursive proofs possible. Early recursive proof systems were constructed using trusted setups and cycles of expensive pairing-friendly elliptic curves.

Inductive logic based iterative expressions and proof carrying data are two interesting constituents of recursive proof systems.

Halo by ZCash is the first practical example of recursive proof composition without a trusted setup. It uses the discrete log assumption over normal cycles of elliptic curves. In the current roadmap of Ethereum and many other protocols, incrementally verifiable computation becomes an important imperative. Hence we can anticipate that the applications of recursive and recurrent proof systems will rise up in the coming days!