Add preprocessing to challenge API.

[levs57]

Right now, we have a challenge API, but it does not allow to use black-box operations on it.

For example, if I generate the challenge, I can produce a primitive expression, using Expression::Challenge(challenge), which produces a public constant usable after the phase this challenge is generated in. After this, I can only apply polynomial operations to it.

It is desirable to be able to use any black-box public function and produce a new expression (still "public constant", degree 0, etc) - one particularly important case that comes to mind is hashing the challenge to curve.

It is possible to do - one way is done in my fork here: https://github.com/levs57/halo2 ; though it is a bit lazy as it does some checks runtime - ideally we need a wrapper struct with private field expr : Expression<F>, which can only be generated from "public constant" expressions - i.e. from constant, challenges, and other Expression::Postprocess. Currently this is just checked on runtime.

I think it is a desirable feature. One particular concern is that it (sort of) breaks on-chain verifier - as it now must somehow know how to compute blackbox functions that we use.

In case of hashing to curve, an optimization is desirable anyways - i.e. reasonably in most cases verifier should just check smth like (A.x-challenge) < 128; (A.x-challenge) >= 0, where A is a challenge point - this gives malicious prover an ability to choose point but very limited (out of expected ~64 options), which works in most cases.

[ed255]

Hi @levs57 !
I think the biggest challenge for this feature is what you mention about an on-chain verifier; and more generally, any kind of verifier that is not rust native (for example, a circuit verifier). We would lose the opportunity to automatically generate a circuit verifier when such a feature is used.

We also recently re-architectured halo2 so that it has a clean split between frontend (responsible of offering an API to describe a circuit, compile it and generate a low level plonkish circuit description; and do witness generation) and backend (responsible for setup, proof generation and proof verification). I imagine this black box would be defined in the frontend but would need to be passed to the backend, which will add some complexity in the middleware.

So I would say from our part we don't plan to implement this feature.

If you'd be interested in implementing this, as a feature that can be disabled, let us know!