zk-FOAKs with Recursion

In zk-FOAKs Algorithm, we shows the novel protocol of zk-FOAKS. You may notice that we left something unspecified: we apply another zero-knowledge argument protocol ZK in our protocol and we didn't mentioned what it is.

In fact, we repeatedly apply zk-FOAKS until the proof is small enough (i.e. smaller than a threshold), than we apply a simple SNARK to finish the proof. We call this technique "proof recursion".

Notice that in other projects, people also use the word "recursion" in other ZKPs like Halo2 or Stark. However, here in FOAKS, "recursion" is not the same deal, the proof recursion (which is realized by code-switching) help us to greatly reduce the size of a single proof while only cause a small overhead in the proof time, which is the greatest advantage of our algorithm.

In Halo2 or Stark, they use the phrase "proof recursion" to describe the idea of turning two or more proofs into one proof. Here, we call this idea "proof aggregation". Proof aggregation is an important feature in zk-rollups, it help the system to be more scaleable. It is also worth mention that proof aggregation is also viable in zk-FOAKS-based schemes.

To sum up, with the recursion technique, our originally designed zk-FOAKS is the perfect fit for a zk-rollup considering its following features: - O(|C|) (linear) prove time (the theoretical lower bound of any ZKPs). - O(log^2|C|) level proof size (same level as Stark). - O(log|C|) level verification time (shorter than Halo2 and Stark).

If you still don't get what it means... it means zk-FOAKS will make FOX super FAST, and super CHEAP!