AirScript: language for defining zk-STARKs

Yep! That looks correct to me.

As I was writing this, another potential optimization idea came to mind:

I’ve thought of this myself, and didn’t do it because it would make the code too complex and I was deliberately making mimc_stark.py an educational implementation rather than something crazy optimized. I have no idea whether or not this is secure; I’d recommend asking Eli.

Another thing worth exploring is playing around with making the FRI skip-down degree 8 instead of 4. The reason why this could be an optimization is that the Merkle tree (at least in mimc_stark.py) is designed in such a way that the FRI check values are right beside each other, so you only pay an O(1) cost for each value, plus O(log(N)) per sample for the branch. Making the skip-down degree 8 cuts down the number of sampling rounds by a factor of log(4)/log(8) (ie. by a third), at the cost of 2x more chunks, but that still seems like a net improvement.

I am wondering, would it make more sense to use a VDF instead of adding proof-of-work to Merkle roots? It could work like this:

  1. Build a Merkle tree.
  2. Compute seed = VDF(root, steps).
  3. Generated indexes using the seed and PRNG.

The reasoning is as follows:

  • 2^{20} proof-of-work takes about 1 second to compute on my computer. But someone with a modern ASIC could compute thousands (or even millions) 2^{20} proof-of-works per second.
  • At the same time, running something like a reverse MiMC on my computer for 2^{16} steps takes about a second as well. But running thousands (or millions) of reverse MiMC calculations per second would take orders of magnitude more resources than buying an ASIC.

Are there any drawbacks of the VDF approach described above that I’m not seeing?

1 Like

The problem is that you’re not really taking advantage of the VDF’s non-parallelizability, because the VDF could be calculated in parallel for many different choices of root. So it reduces to just being a hash function.