NonNative should automatically internally use NonNativeMulResultVar to avoid reductions

[Pratyush]

As pointed out by @daira in #79 (comment), we should have NonNativeFieldVar automatically track when a reduction is needed, and only reduce when necessary (eg: when converting to bytes/bits). What do you think, @weikengchen?

[weikengchen]

There is a challenge associated with this idea.

Let us say we have an unreduced emulated field element a, which is the result of a multiplication. After this step, the user is going to perform several operations related to a.

c = a + b  // where b has been reduced
e = a * d
f = a.to_bytes()
h = a + g // where g is also unreduced

Unless "+", "*", and "to_bytes" all have a mutable access to a, otherwise, they can reduce, but they do not save the reduction result.

The last line is special case. Now, when we add a with an unreduced element,

• should a be reduced? if so, should h = a + g be reduced? should we reduce g and then do the addition?
• If a has the unreduced format at this moment, then it is simple, and h can remain unreduced.

I feel to do so, we need the following:

• A RcCell-like structure with mutable access, so that all the &self call can indeed modify the stored value.
• An algorithm that adds a reduced element to an unreduced element and obtaining an unreduced element, without reductions in the middle (which can be done somehow).

[weikengchen]

One RcCell per emulated field variable is a possible solution, though it seems to introduce too many RcCell, and may have performance overhead.

The best way, which would be more complicated, is to store the limbs in the constraint system (recall that we want the constraint system to serve as global storage). So, all the emulated variables are indeed "symbolic".