Skip to content

reduce constraint generated with api.AssertIsEqual(...) #555

Description

@gbotrel

In particular, starting with plonk (scs) since when we have a call to
api.AssertIsEqual(a, b)

we have the following cases;

  1. a, b are both constants. (skip this case)
  2. a (or a and b) are input variables. (skip this case)
  3. a, b are both internal variables
  4. a, b is a tuple of internal variable + something.

Currently we encode that as a - b == 0 . But really, what we are saying is that these could be the same wire. So:
3. if a is used appears in n constraints, and b appears in m constraints, with n > m, we kill b. we replace all the occurences of wire b with a. This saves one constraint (the a-b==0 and one wire).
4. same logic here; if it's (internal variable, public/secret variable) we replace the internal variable with the input. If it's a constant same. A cascading effect would be to simplify the impacted constraints since we would propagate a constant, but our compiler architecture will not allow that painlessly.

A naive way would require O(m) memory and O(n) post-processing (i.e we store the assert is equal pairs; then when compile is called we replace the wireID in the constraints AND (more painful) we .. shift the internal wire ids for the others.

Would like to find a way to do this on the fly during the compilation to avoid a large perf impact..

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions