Jul 23, 2017 · 1 min read
I’m aware how old this post is. I also don’t know much about zk-SNARK, but the stages up through generating the QAP are quite easy to understand. I do a lot of work with automatic differentiation and the similarities really struck me, particularly in the “flattening” process. It got me thinking about more efficient alternatives to Lagrange interpolation. Newton polynomials are generally considered to be less efficient than the Lagrange form, but if one were to use exact derivatives rather than difference quotients it seems this could be sped up significantly without any FFT algorithms.