search

filecoin-project / bellperson

zk-SNARK library
Other
190 stars 120 forks source link

Add WitnessCS, SizedWitness, and related ConstraintSystem methods. #309

Closed porcuquine closed 1 year ago

porcuquine commented 1 year ago

This PR adds some new ConstraintSystem methods. These methods are intended to only be implemented by or called on ConstraintSystems that are also designated as witness generators. Such ConstraintSystems will signal this by implementing and returning true from is_witness_generator().

A minimal WitnessCS suitable for this purpose is also provided, as is a SizedWitness trait which should be implemented by objects (for example, implementers of Circuit) that choose to offer efficient witness-generation.

In this context, 'efficient witness generation' likely bypasses the usual, flexible mechanism used to specify bellperson circuits. Although convenient, this mechanism conflates synthesis and witness generation in ways that can add significant overhead.

Initial synthesis benchmarks in Neptune, although imperfect, showed 15x speedup when using this method, and this PR's immediate purpose is to support that use case.

porcuquine commented 1 year ago

@huitseeker Thanks for the fantastically detailed response. What you wrote makes sense, and I've added the missing methods. It's not obvious to me how extend() should (or maybe even can) work, given its signature, so I made it explicitly unimplemented to avoid perverse behavior. If you have thoughts or a better solution, please let me know.

huitseeker commented 1 year ago

@porcuquine I agree extend is impossible to proxy in this context. The problem is actually in ec_gpu_gen, I opened the following PR to suggest a fix: https://github.com/filecoin-project/ec-gpu/pull/53

For future reference, the following branch: https://github.com/huitseeker/bellperson/tree/witness-cs-with-extend-api and in particular its latest commit https://github.com/huitseeker/bellperson/commit/174612dd417f6f8e57bb0908f328d6a7b5fbfa74 show this is enough to make the signature of extend more sensible.

In the context of this PR, this just means the convenience instance of ConstraintSystem cannot have a sensible implementation of extend, which I would fix (after the upstream fixes are in) by deprecating ConstraintSystem::extend, and implementing an ConstraintSystem::extend_all with a by-reference argument (which can then be proxied). If that makes sense to you, we can perhaps just open an issue using the "Reference in new issue" link of the present comment.