Retroactive: Define necesary Brillig opcodes

[kevaundray]

Problem

As a part of #191 we need to define the opcodes needed for Brillig. The main requirement is for it to be simple.

There are some things to consider when defining the opcodes:

• Brillig can have intrinsic functions (these are the blackbox functions defined in ACIR)
• Brillig does not perform IO, but it is possible to stop execution of Brillig using an Oracle. The Oracle will stop execution and supply the caller with an Oracle name, inputs and ask the caller to fill in its output values.
• Brillig is capable of doing arithmetic operations and the base type is a Field element. This is opposed to a 64-bit system whose base type is a uint64.
• Brillig has a concept of memory, where each memory cell is also a Field Element.
• Brillig is Turing complete and can have un/conditional jumps.

Proposed solution

Defining the opcodes and their rough structures is the first step. The hardest part here would be defining how memory is handled.

We should not need to concern ourselves with Noir, though it might make life easier if we eventually do something that is similar to the way the new ssa refactor is working in Noir.

Alternatives considered

No response

Additional context

No response

Submission Checklist

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

[kevaundray]

Pinging @TomAFrench for visibility

[ludamad]

Confirmed with Kev to be done