Retroactive: Add support for Oracles when executing a program

[kevaundray]

Problem

The partial witness generator without oracles can be seen as a determinstic process.

What this means is that once you feed it, the initial witnesses, it no longer needs to fetch information from an outside source.

State

We make the observation that the initial set of witnesses are usually values fetched from some state storage like a database, which is why they cannot be computed from other values.

Dynamic state fetching

Now consider the situation where we need to fetch state based on a value that we compute in the middle of the program.

fn foo(x : Field) {
   let z = x + x;
   let hashpath = get_hash_path(z);
} 

The hashpath is a value which cannot be computed from z. It requires some sort of call to a database storage, or one will simply need to pass all of the leaves and recompute it.

Here is what a Noir program will likely look like as a workaround:

fn foo(x : Field, z_hash_path : [Field; 16]) {
   let z = x + x;
} 

In the above program, the hash path for z has been passed in as a parameter, because there is no way to compute it otherwise. Remembering that the partial witness generator, can only compute values based on initial or intermediate values.

Problem with dynamic state fetching

The main problem with the above program is that a programmer now needs to compute z outside of the program in order to fetch the hashpath for it. Then when the program is executed, z is computed again. This means that the program is duplicated.

The above was a simple example where the value needed to fetch state was easy to compute and at the beginning of the program. One can image a scenario where z is the result of a complex computation involving for-loops and if-statements.

Proposed solution

The proposed solution is what we refer to as Oracles.

Prelude

We want to avoid duplication of code, once in Noir and again typescript/python/Rust, as this becomes unwieldy for any large program. The intuitive choice would then be to somehow pause the partial witness generator when you need to fetch state based on some value you have already computed and then resume once you have the input.

This is the gist of how oracles work.

Oracles are Directives

An oracle is a directive in Noir that when the partial witness generator encounters, it will not attempt to solve. Because it cannot. Instead it will return the current state of the partial witness generator, along with the oracle that needs to be filled in.

Once the caller has filled in the oracle, ie supplied the information that is needed, they can then cal the partial witness generator again, inserting the filled oracle and the previous state, and the partial witness generator will resume solving.

This process is repeated for however many oracles there are. The behaviour of the partial witness generator without an oracle directive will remain the same.

Oracle Structure

An Oracle looks like the following :

OracleData {
  name: String,
  inputs: Vec<Expression>,
  input_values: Vec<FieldElement>,
  outputs: Vec<Witness>,
  output_values: Vec<FieldElement>,
 }

The name is used so that whoever is responsible for filling in the Oracle, will know what they need to do. For example, if the name was "hash_path" then the responsible entity will know that they need to fill in a hashpath.

The inputs are the circuit witness indices that the partial witness generator will use to compute input_values. ie before the partial witness generator pauses, they will compute all of the input_values based on the inputs field.

The entity responsible for filling in the Oracle, will check the input_values field and fill in the output_values field.

Once the partial witness generator has resumed, it will assign the values in the output_values field to the witness indices in outputs

Alternatives considered

Design decisions

One thing that was actively avoided was making the partial witness generator async. This is because async is viral and not colourless, meaning that the caller of the partial witness generator will need to be async and so on.

The ramifications of this, is that the partial witness generator will simply stop execution and return the state. The returning of state is a necessity, since its not awaiting for some other process to get information. This has the nice property that, one can resume the partial witness generator at any time, on top of avoiding async.
The downsides being that one returns the state and needs to pass it back in again to resume.

Note: the code that calls the partial witness generator can be async and in the web context, we expect this to be the case. In Rust, my assumption was that this would not be the case or more importantly, it does not need to be the case.

Additional context

No response

Submission Checklist

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

[kevaundray]

@iAmMichaelConnor we can use this issue plus possibly another one in Noir to track the progress of Oracles

[TomAFrench]

Closing as this is oracles (now brillig foreign calls) are fully implemented.