Add distinct keyword to make public return values be assigned to distinct witnesses

[kevaundray]

Problem

Suppose that the Noir proof being created needed to conform to some Virtual Machine.

This virtual machine will take in a Noir proof and a fixed number of public inputs.

Lets produce a Noir program which will cause this VM model problems:

fn main(x : Field) -> [Field;2] {
[x,x]
}

Our example, VM will expect a proof and 2 distinct public inputs. The noir compiler will notice that x is being used twice and return the same public input twice. So it returns one distinct public input.

Proposed solution

We propose to add a distinct keyword for return types on main, which will ensure that the witnesses being returned as public inputs are all unique.

The noir program will now look like:

fn main(x : Field) -> pub distinct [Field;2] {
[x,x]
}

How this transformation will happen

The naive way to apply this transformation is to create N public witnesses and create a constraint to make them equal to the N return witnesses which may have duplicates. This has been implemented in a hacked together branch here

A clever way to do this would be to keep track of the witnesses which we have already seen and do not create new witnesses for them.

Alternatives considered

No response

Additional context

In the parser, we can add this new enum for the distinct keyword:

/// Distinctness refers to whether the public return type
/// from the entry-point functions have distinct witness values.
///
/// The compiler will ensure witness values are distinct, if
/// variant is `Distinctness::Distinct`.
///
/// if the variant is `Distinctness::Duplicated` it could be the
/// case that the witness values are distinct due to the users
/// program.  
pub enum Distinctness {
    Distinct,
    Duplicated,
}

If the distinct keyword is present then we have Distinctness::Distinct and the other caseif not.

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[kevaundray]

CLosing due to #1219 being merged