[](https://)# Fully Non-deterministic Noir

- Maybe we should call it fully non-deterministic Noir. Moreso because this allows us to reimplement the non-determinism in a more general way.

## Extern functions

- These are functions in noir which have no body, and are executed by the acvm solver, by calling an extern function or by acvm directly.
- pub types are not allowed in extern

Example 1:

extern fn foo(a : Field, b : [Field;10]) -> Field;

This foo function is seen by acvm as the following opcode:

Directive::general{
    name: "foo"
    inputs : vec![a, b[0], b[1], b[2], .., b[9]]    
    outputs : vec![c]
}

**Discussion**

In this example, the directive gets the function name as `name`, it then gets the inputs as a flat sequence of witness indices, and the outputs as a sequence of witness indices.

## Declaring an extern function

- There are only two ways to declare an extern function in Noir.

### Builtin extern functions

These correspond to builtin directives that are supported by acvm directly.

An example of this is Split. ie this is a compile time directives already seen in acvm.

In Noir, these will look like:

// This requires us to expose the avcm directives to Noir, but we need an unsafe block to call them
#[builtin_directive("split")]
fn split(a: Field) -> [Field];

#[builtin("modulus_bits")]
// This should return a constant
fn modulus_bits() -> u32;

fn to_bits(a: Field) -> [Field] {
    // This is safe because we apply the constraints to 
    // ensure b is the split of a below
    // Note that the LHS being [u1;32] applies the constraints
    let b : [u1; 32] = unsafe { split(a)};
    
    let a_from_bits = 0;
    let mut r = 1;
    let mut s = 0;
    for i in b {
        a_from_bits = a_from_bits + r*i;
        r=r*2;
        s =s+1;
    }
    constrain array::len(b) < modulus_bits() - 1;
    constrain a == a_from_bits;
}

Note that extern means that the implementation of the function will not apply constraints and will have their function definitions linked later.

### External extern functions

An external library will declare a set of non-deterministic functions alongside a C library which will specify how acvm should handle these non-deterministic functions in Noir.

The folder structure will look like:

- header.nr
- C code

The header.nr file will hold the function declarations for external functions. Note again, they will not have definitions. The C code directory will hold the C code that the vm will call during witness generation to handle noir code calling a function in header.nr.

## How extern functions are handled in the vm

First note that we do currently have a few non-deterministic functions in the VM already, this is how one can do an inverse efficiently and one can bit decompose a function efficiently.

This change will generalise this mechanism.

Instead of having:

Directive::Inverse(input : Field, output: Field)
Directive::BitDecompose(input : Field,output : Vec<Field> )

We now have a generic Directive:

Directive::general(name: String, input : Vec<Field>, output : Vec<Field>)

We can reimplement the inverse directive, by simply calling the general directive with the string "::inverse"

In general, the directives that are builtin and can thus be declared in the stdlib will look like so:

#[builtin_directive(inverse)]
fn inverse(a : Field) -> Field;

The prepended `::` is so that they cannot be overwritten. As we shall see, for external extern functions, the general format for the name of a directive is `"{package_name}::{function_name}"` Where package_name is therefore non-empty except for builtin directives.

### Handling ad-hoc external functions

There are a set of external functions that the vm will be able to handle, such as an inverse and bit decomposition. However, as noted there are also external extern functions whose handling needs to be specified by some C code.

**External extern package**

First, suppose we have an extern noir package at the github address: `github.com/foo/extern`.

The file structure as previously noted, will look like:

- header.nr
- C code

// header.nr
extern fn some_extern_func(a : Field) -> Field;

**Local package**

Now suppose that we have a local package which should call this external package. First consider the Nargo.toml file.

// Nargo.toml
my_extern_lib = {git = "github.com/foo/extern", extern = true}

Above, we pull in the external_library from github and name it `my_extern_lib` for use in our noir program.

Now consider the main.nr file

use my_extern_lib;



fn main(a : Field) {
    let c = unsafe {my_extern_lib::some_extern_func(a)};
    let b : [u32;10] = convert_fields_to_u32(c, 10);
}

This file simply uses the `my_extern_lib` dependency and calls the `some_extern_func` function.

> Still deciding if we should make it very clear that we are calling an extern lib, like rust has `unsafe`

**ACIR**

This will generate an ACIR opcode like this:

Directive::general(name : "my_extern_lib::some_extern_func", input : vec![a], output : vec![])

Now when the vm sees this, it needs to find the dynamic library that should handle the `some_extern_func`.

The pseudocode for how it will do it is as follows:

nargo_meta = Map<String, LocationOnDisk>
location = nargo_meta[{package_name}]
call_library(field_type, lib_path, inputs, len_input,&mut outputs, len_output);

Lets break down whats happening:

- We get the location for the package named `my_extern_lib` from nargo.toml's metadata.
- We then compile and load the dynamic library that is located in the C code.
- We then call the C code's library with the field_type, the inputs and the outputs.

Notice, inputs and outputs is a flattened byte vector. We flatten the byte vector because the field size may not be fixed. The C library could be made to handle multiple fields.

## A way to write generic unsafe code

So you can do:

unsafe {
  let k = foo (10,20);
}

Question: how do you capture variables from outside of the unsafe?

Note that evaluation is done in ACVM.

In terms of priority, this is second class because the library is easier.

The problem is that we do not know how to link variables to witness indices for the acvm to correctly evaluate. However, if we used Noir and generated the SSA code which includes the witness indices, then this is easy. We will just need to evaluate the ssa code in acvm.

# Scribble space below

## Common example

Without this, we need to pass in the hashpaths.

## Draft

let x = void; //could just let x;
x*x = z; // n-d => x is computed during solve

x can be solved by generic solver

let path, index = void;
let root = compute_root_from_leaf(leaf, index, path); //n-d => index and path are computed during solve

index and path cannot be solved by generic solver, we need the merkle tree i.e some state

Directive::Merkle_tree(leaf, root);

check_membership(public_root, leaf, path) {
let root = compute_root(leaf, path)
assert public_root == root
}

let input2 = extern_oracle my_custom_function(input1,x,..);
my_custom_gate(input_1, input2); => the backend has the inputs

//my_custom_function is called during solve by the solver

custom_function: - could come from a lib (dynamic .so..), function is declared in a header file
- a rust crate => then the user can do what he wants inside, e.g call an extern library if needed
- defined in noir: noir compiles it to what?

extern fn my_custom_function() -> Field; => noir compiles to rust extern.c API? file?
=> the backend knows what to do; he call internally what is needed and suppply the solver:
extern_oracle my_custom_function() in noir => Extern Gate(inputs are from the function ) outputs are matching the declaration
Directive_Gate::my_custom_function()
Directive_Gate::my_custom_function2()

Directive_universal(String, inputs, outputs)
Directive => handled by acvm
Directive_universal => generic handling by acvm

use my_extern_lib in .nr file => on a github somewhere

my_extern_lib::my_function()
during solve: acvm see the gate Directive_universal(String..)
from the string it sees that it uses my_extern_lib, which is properly declared in noir so it can call it with the gate.
QN: how is declared my_extern_lib?
for instance: as a crate in cargo.toml => easy but not flexible

my_statefull_program.nr

use my_extern_lib("../libs/my_lib.a"); //or declared in nargo.toml

fn main(a:Field) {
    let v = my_extern_lib::my_function(a);
}

my_lib.a is a (rust) program called by acvm (using a C API)
C interface : solve(field_type, Gate, inputs (NoirFIeld), len1, outputs (NoirFIeld), len2)

can my_lib use FieldElement?

let path = mekrle_lib::get_path(leaf, 2); //no hash here !
let root = compute_root(leaf, path, hash);// noir hash function it's ok because is a noir function, so it can use hash()

## Thing

// a.nr
extern foo(in, out)

// b.nr
extern foo(in, out)

my_lib::foo(); //my_lib references a precise location in nargo.toml

a::foo();
b::foo();

Gate(String, inputs, outputs)

nargo_meta = Map<String, LocationOnDisk>
name = "{package_name}::{function_name}"
loc = nargo_meta[{package_name}]
lib_path =get_library(loc); //returns the library from nargo.toml
call_library(field_type, lib_path, inputs, len1,&mut output, len2);