Demystifying Fractal

Background of Demystification Series
In the past years, there have been many academic publications on zero-knowledge proofs of argument schemes (zkPoKs, aka “ZKPs”). One of our goals at Metastate (aka Cryptium Labs) is to stay up-to-date with the latest developments in academia on the subject, in order to be able to be able to assess their properties and evaluate potential applications or features that leverage them. The Demystification Series is composed by blogposts that share in-depth analysis of novel zkPoK protocols, such as Supersonic, Fractal, and many more.

Demystifying Fractal Part I
Fractal is a new general-purpose zero-knowledge proof system (and no, it doesn’t have anything to do with the fractals you’re probably thinking of). While new advances in SNARKs are being made almost daily, a couple of things make Fractal stand out:

  • Transparent setup. There is no trapdoor in the setup; it’s based entirely on public randomness.
  • Recursive composability. Verification can be written as an R1CS instance, allowing Fractal to verify another Fractal proof.
  • Security against quantum adversaries. Whereas some constructions are secure under classical intractability assumptions that don’t hold for quantum computers, Fractal is based on hash functions, for which we don’t have any truly feasible quantum attacks. This actually makes Fractal the first plausibly quantum-secure recursively composable proof system.
  • It uses only lightweight cryptography. Another benefit to avoiding the intractability assumptions is that the algebraic operations involved, such as (cryptographic sized) elliptic curve point addition, are computationally expensive compared to evaluating classical hash functions.

We’ll assume that this isn’t your first exposure to interactive proofs, ZKPs, or maybe even SNARKs. At the same time, we’ll provide a high-level overview of the general structure of SNARKs before diving into the particulars of Fractal. The first post will give a higher-level overview, and in the second we’ll get into the gritty mathematical details.

Demystifying Fractal Part II

Related Threads & Articles


In the previous post, we went over Fʀᴀᴄᴛᴀʟ at a very high level, describing its features and what kind of subprotocols we would need to make it work. Part 2 details Fʀᴀᴄᴛᴀʟ’s subprotocols, such as Univariate Sumcheck for rational functions, Holographic Lincheck, Sparse Matrix Arithmetization or the Verifier.

1 Like