Hints vs builtins

[mimoo]

When should something be a builtin vs not a builtin? That's the big problem we're trying to solve here...

Bit decomposition as an example

Let's take bit decomposition as an example of a noname operation that would lead to different outcomes depending on the constraint system (currently called "backend" in noname).

There are two ways we could implement bit decomposition in the noname language, either using the native language:

fn decompose_bits(val: Field) -> [Field; 5] {
    // ???
}

or using builtins:

use std::bits;

let bits = bits::decompose(val, 5); // 5-bit val

Before we go further, let's take a look at what the constraints would look like depending on the constraint systems

Bit decomposition in R1CS

A i-th constraint that bit-decompose a 4-bit value $v$ into bits $b_0, b_1, b_2, b3$ would look like this so that you have $\sum{i=0} 2^i \cdot b_i = v$:

A[i] = [0, ..., 0, 1, 2, 4, 8, 0, ... 0] // powers of 2 against the bits
B[i] = [1, 0, ..., 0] // constant 1
C[i] = [0, ..., 0, 1, 0, ..., 0] // selects the value
z = [_, v, b0, b1, b2, b3, _] // value and its bits are in the witness

In addition we would need to constrain each $b_i$ to be a bit as well.

Here's what such a function looks like in circom:

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }

    lc1 === in;
}

And here are the constraints that Circom creates (as shown by circomscribe):

Bit decomposition in Plonk

You would need at least around 4 constraints to bit decompose a 4-bit value, and you'd need bit constraints as well for each bit value (so potentially ~8 constraints):

// bit constraints
b_0 * (b_0 - 1) = 0
b_1 * (b_1 - 1) = 0
b_2 * (b_2 - 1) = 0
b_3 * (b_3 - 1) = 0
// accumulation
1 * acc0 = 1 * b_0 + 2 * b_1
1 * acc1 = 4 * b_2 + 1 * acc0
1 * v = 8 * b_3 + 1 * acc1

Each of these lines would be translated to a generic Plonk gate. (So clearly, R1CS wins in these kind of operations due to linear combinations taking only a single constraint.)

A native approach

So from the user perspective, what we're doing is:

1. obtain the (constrained) bits $b_i$ behind $v$
2. constrain $\sum_{i=0} 2^i \cdot b_i = v$

Step 2 is what leads to multiple constraints in Plonk, as opposed to a single constraint in R1CS. A "reducer" function in the compiler could observe the many multiplications happening in that step 2 and decide to either use a single constraint if the constraint system is R1CS, or reduce it using temporary variables if the constraint system is Plonk.

[!NOTE]
The implementation of this reducer is an interesting question that we could try to answer in this document as well. There are three approaches that I know of:

1. Create constraints as soon as we see an addition or a multiplication. This is what noname does at the moment, it is highly unefficient but it is simple.
2. Implement addition and multiplication as "delayed" operations that only create constraints once they're loaded/at capacity. Snarky did this by creating a mini-AST of add/scale/mul which would then be "reduced" once we hit an assert or a custom gate (which can be seen as assertions). TODO: The previous sentence might not be clear to someone who has not seen such code before, so I could develop this further if needed.
3. Implement addition and multiplication to produce instructions for an IR. We could then perform optimizations on that IR. I'm guessing optimizations would be of two kind, first they could be "general" (apply to every constraint system), and then a second phase of optimization could apply only to specific backends. I think this idea is implemented in Circom.

The IR path seems more and more attractive to me. Because it would cleanly separate the parsing/compiling of the noname code to producing elegant constraints depending on the constraint system. This would be major refactor though and we have to think about this carefuly.

We can discuss this more in depth in https://github.com/zksecurity/noname/issues/45

But what about step 1? Let's imagine that we had access to out-of-circuit functionalities as well as const generics (none of these exist in noname at the moment). We would then have to write the bit decomposition function like this:

fn bit_constrain(val: Field) {
    assert_eq(val * (val - 1 ), 0);
}

fn decompose_bits(val: Field, const bitlen: Number) -> [Field; bitlen] {
    let mut acc = 0;
    let mut res = [0; bitlen];
    for ii in 0..bitlen {
        res[ii] = ith_bit(val)
        acc += res[ii] * 2.pow(ii);
    }
    assert_eq!(acc, val);
    return res;
}

// maybe hints could be "functions" that have two blocks:
// the first block is the out-of-circuit stuff
// the second block is optional constraint
hint ith_bit(val: Field, ii: Number) -> Field {
    // this code is purely out-of-circuit code
    // this passes a Field to next function
    return (val >> ii) & 1;
} {
    // this code is in-circuit constraint code
    bit_constrain(bit_ii);
    return bit_ii;
}

but actually the last example for a hint is not super useful... one could always be forced to wrap a hint within a non-hint function to ensure things are properly constrained anyway

hint ith_bit(val: Field, ii: Number) -> Field {
    // this code is purely out-of-circuit code
    // this passes a Field to next function
    return (val >> ii) & 1;
} 

fn ith_bit(val: Field, ii:Number) -> Field {
    let bit_ii = hint(val, ii);
    bit_constrain(bit_ii);
    return bit_ii;
}

What should we do?

The native way sucks because 1) we don't have generics and 2) It exposes out-of-circuit code with these hints, which is prone to error.

On the other hand the builtin approach is super simple, but sucks as well for different reason: it might lead to us having a LOT of builtin code. It might also be that eventually, users do need access to writing out-of-circuit logic in noname anyway.

I think we could go a long way by using a lot of builtins in order to handle different constraint systems, generics, as well as hints.

It's an interesting approach because unlike Circom, we're hiding a lot of complexity/gadget/abstractions within the compiler.

I'm in favor of not exposing hints to the user. I feel like this design decision is a "Golang vs Rust" type of design decision, and I'm in favor of going the Golang way here because it is more high-level and user-friendly (but not necessarily low-level developer friendly).