theory of base gadgets

[porcuquine]

From #55 (comment):

If we are establishing a new set of gadgets, it may be worth taking a moment to consider unification of similar alternate approaches for two reasons:

• This may lead to the most coherent/efficient foundation.
• This may simplify achieving the goal of migrating downstream projects to use a common base.

To that end, let's take a moment to make an active decision. The current function (alloc_num_is_zero) can be implemented in terms of the (also important) alloc_equal_const (https://github.com/lurk-lab/lurk-rs/blob/dae0d6c478a83c80e3b3753c29f89e4ecd2a6313/src/circuit/gadgets/constraints.rs#L495) [UPDATE: actually alloc_num_is_zero operates on a Num — so my points here are not quite germane to this work. The general point stands as something we should sort out as part of a 'base gadgets' project, though.].

Arecibo, for path-dependent reasons associated with its own internal consistency has the slightly-differently-named alloc_num_equals_const: https://github.com/lurk-lab/arecibo/blob/6a9e8707e868068abf8c6b8da999443c3f3d0895/src/gadgets/utils.rs#L200-L237.

In addition to the slight naming difference, that function has a more concise (arguably simpler — if also less didactic) definition, itself derived from its alloc_num_equals (https://github.com/lurk-lab/arecibo/blob/6a9e8707e868068abf8c6b8da999443c3f3d0895/src/gadgets/utils.rs#L156-L197), which has a similar relationship to Lurk's equivalent alloc_num_equal (https://github.com/lurk-lab/lurk-rs/blob/dae0d6c478a83c80e3b3753c29f89e4ecd2a6313/src/circuit/gadgets/constraints.rs#L440-L492C2).

The point of this comment is to suggest we take a moment to actively decide:

• About names, do we want to use:
  • the lurk-rs names;
  • the nova/arecibo names;
  • some (potentially) more lexically-consistent names considered from the ground up to solve the larger design problem now faced.
• About implementations, do we want to use:
  • the lurk-rs implementations;
  • the nova/arecibo implementations;
  • fresh implementations [note: probably not a good idea in this work]

The reason this is worth considering is that any refactoring of both arecibo (which implies the hope for an eventual change in nova) and lurk-rs will have audit/correctness implications for at least one of those projects. We should seek to minimize global cost and maximize eventual global confidence in correctness with whatever we do here.

I don't think we need to overthink this, just make an active decision. I suggest there are only four reasonable choices, and all are more-or-less acceptable with the right argument:

• lurk-rs names and implementations (status quo of this PR)
• arecibo names and implementations (status quo if we had started from the premise of refactoring arecibo)
• lurk-rs names and arecibo implementations (possible lessening of the lower-level crypto's auditing burden as a matter of policy, or in deference to the lowest-level's cryptographic weight).
• arecibo names and lurk-rs implementations (in deference to lurk-rs and many of the gadgets in question more broadly than just this PR having undergone one round of audit).

I would say that the last option probably makes little sense. If the logic for lurk-rs implementations is strong, we should probably also use lurk-rs names. This is because lurk-rs names are probably the better choice anyway, and changes of naming for purpose of gadget standardization should be non-threatening to arecibo/nova.

In the end, I think my vote is for lurk-rs names and either implementation. If we know we will prefer one implementation over the other, it's probably best to initialize this work with that choice so we can follow a policy of not gratuitously changing implementations of gadgets — since this has a substantive effect on any circuit depending on them; making it a deeply breaking change in ways that are not instantly obvious.

cc: @adr1anh @gabriel-barrett @huitseeker

Originally posted by @porcuquine in #55 (comment)