Add hint registry

[ivokub]

Added hint registry for registering hint functions used in gadgets. Improved the documentation to help explain the usage of hints.

Todo:

• Prover should define all registered hint functions.
• Find usages of hint functions and document a bit more.

[gbotrel]

One thought, currently, nothing prevents the following workflow;
in one "binary", ccs, _ = frontend.Compile(circuit) --> circuit.go imports component.go which has a

func init() {
hint.Register(myHint)
}

in another binary, groth16.Prove(ccs, witness, pk, ...) --> this binary doesn't import component.go, the CompiledConstraintSystem is 100% independent from the user-defined circuit.

[ivokub]

One thought, currently, nothing prevents the following workflow; in one "binary", ccs, _ = frontend.Compile(circuit) --> circuit.go imports component.go which has a

func init() {
hint.Register(myHint)
}

in another binary, groth16.Prove(ccs, witness, pk, ...) --> this binary doesn't import component.go, the CompiledConstraintSystem is 100% independent from the user-defined circuit.

I do not follow completely - wouldn't witness import component.go?

[gbotrel]

Not necessary; if it's done in a Go codebase yes. But, say, random example ( :) ) a zkRollum built in Rust, can build a serialize a witness in rust, and have a Go micro service call groth16.ReadAndProve without having any direct dependency on the circuit definition.

That being said, the current pattern where we have to explicitly set the hint functions as Prover options is still not ideal for this type of "prover service", but, well, if a user-defined circuit has hints, then since they are some kind of solver plugin, it makes sense to have to recompile the "solver binary".

[ivokub]

Not necessary; if it's done in a Go codebase yes. But, say, random example ( :) ) a zkRollum built in Rust, can build a serialize a witness in rust, and have a Go micro service call groth16.ReadAndProve without having any direct dependency on the circuit definition.

That being said, the current pattern where we have to explicitly set the hint functions as Prover options is still not ideal for this type of "prover service", but, well, if a user-defined circuit has hints, then since they are some kind of solver plugin, it makes sense to have to recompile the "solver binary".

I see - if the both CCS and witness are both obtained by deserializing some input, then they do not import the gadgets and the hints are not registered. If serializing the proofs which use hints, then are the hint variables also serialized, or are they created only in runtime?

I do not see right now how it could be improved - for me it seems that hint functions are specific to particular implementation. I guess the hint variables should also be serialized to be implementation-independent?

[gbotrel]

What do you mean by "hint variables"?
Say you do:

v := api.NewHint(myHint, a, 12)

What happens is v is an internal variable, like any other and can now be referenced in future constraints (we're still at the Define stage).

a and 12 are stored in the CompiledConstraintSystem and will be resolved at Solve time (ie when creating the proof). But what the solver needs, is to find myHint when it does so to call the correct callback.

[ivokub]

What do you mean by "hint variables"? Say you do:

v := api.NewHint(myHint, a, 12)

What happens is v is an internal variable, like any other and can now be referenced in future constraints (we're still at the Define stage).

Yes, I was thinking about internal variables. But at least for me there is a small difference compared to other (non-hint) internal variables as it is necessary to additionally constraint the internal variables.

a and 12 are stored in the CompiledConstraintSystem and will be resolved at Solve time (ie when creating the proof). But what the solver needs, is to find myHint when it does so to call the correct callback.

I see. Definitely, when the user circuit needs a hint, then right now the binary needs to be recompiled to have the corresponding hint as a prover option. There may be ways around it (e.g. maybe the prover service can accept the hint function as an executable script etc.), but I do not quickly see a nice way around it.

Slightly going off-topic - I realized that allowing hints in the user-defined circuits may have security implications. See https://gist.github.com/ivokub/99ec89246f251e9b53f3803135bf316a. Here - the keys are set up for GoodCircuit. However, the malicious prover constructs proof for another circuit BadCircuit (using a different hint function). From verifier point of view - the proof verification succeeds for GoodCircuit and the public witness, but the prover actually didn't have the secret witness for it.

Maybe I do not yet fully understand the security model and this is not a problem?

[gbotrel]

Behavior of hints is a bit subtle; it's not a constraint, but a "off-circuit" computation.

So in this example:

func (sc *BadCircuit) Define(api frontend.API) error {
	c := api.Mul(sc.X, sc.Y)
	zz := api.NewHint(badHint, c, 12)
	api.AssertIsEqual(zz, sc.Z)
	return nil
}

The only constraint on zz is the AssertIsEqual. But the subtlety is, c doesn't appear in any constraint. So, effictively, c is NOT constrained, from a prover point of view, it can take any value.