R1CS constraint system with access to Fiat-Shamir

[weikengchen]

Summary

This is somehow related to verifying matrix multiplications, a use case of verifying matrix multiplications using generic SNARK. (Note: if you have a use case of this, it should be done using https://eprint.iacr.org/2021/730.pdf if noninteractive is not needed.)

Problem Definition

Consider the same case where we do A * B = C where A, B, C are all matrices of size n * n.

With the help of Fiat-Shamir, checking matrix multiplications can be done in O(n) constraints instead of O(n^3) constraints. There might be even more saving in weight.

See Section 3.3 of https://eprint.iacr.org/2021/730.pdf.

Proposal

It somehow means that we need an extension to R1CS where, in addition to the inputs and witnesses, R1CS can also commit some witnesses (not all) on the fly. This is like splitting the witnesses into smaller chunks and commits some of the witnesses first. The commitment will be part of the proof and a random challenge via Fiat-Shamir will be fed back to the R1CS as an input, which serves as the base of random testing.

---

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned