Bootle's paper on sublinear ZK arguments from 2016 has a nice explanation of how you can do the following: commit to a polynomial of large degree upfront with only ~ sqrt(degree) curve points. Then, when an evaluation is needed, you can prove that the value you claim is correct by using the linearity of the commitments, and you transfer ~sqrt(d) scalars. This is really only the very start of the paper :) I wrote a demonstration of how it works in Python:

· · Web · 1 · 1 · 0


As noted this is *not* the zero knowledge form of the protocol; the openings of the commitments leak info about the coefficients. There might be use cases where that doesn't matter, but in any case, one can make this ZK by simply extending the entries in the rows of the matrix with random 'blinders'.

Btw for the approximately zero people who would like to work through the reasoning for this in the paper, note that there is at least one typo in Section 3: in "Main idea for standard polynomials", the double sum on the third line has t_(i,j)(X) but the `(X)` should not be there.

Sign in to participate in the conversation
unidentified instance

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!