A more expressive IR, going from circuits to bytecode

[robinhundt]

With #232 we already went into a direction where the output of Garble is a list of instructions operating on registers. At the moment, there is still a lot of similarity between this representation and the previous circuit representation of gates and wires. I propose making this bytecode more expressive to significantly reduce compilation time and memory consumption.

What should this change to the Bytecode enable?

• compact loops with a fixed number of iterations, where we only store the instructions for one iteration instead of all
  • this would likely also require having registers that can store a usize and plain text operations on them, to track the number of loop iterations
• function definitions and calls, where the instructions of a function are just stored once and referenced multiple times

To achieve this, I think we at minimum need:

• A JUMP instruction to a fixed instruction (whose address is potentially stored in a register)
• A register type that can store an instruction address
• A register type that can store a loop counter variable (could probably be the same as for address)
• Plain text operations on these loop counter variable registers (at minimum, increment)
• Conditional JUMPs based on these loop counters

Drawbacks

• This would make the execution of the IR in Polytune more complicated.
• Special care needs to be taken that the correlated randomness created in the function dependent phase is used for the correct AND instructions in the online phase.

Benefits

• Much more compact representation of many functions
  • Especially something like the pairwise comparison for the measles check could likely be represented with a couple of KB instead of GB, as the loops in the program can stay loops in the IR.
• Faster compilation. Instead of e.g. compiling each iteration of a loop, we compile it once.
• Opens up a way of potentially removing the need to recompile programs if external constants change (this would also require changes in the surface syntax and semantics of Garble)

Open questions

• How would this interact with constant folding and dead code elimination?
  • This gets tricky if for example only parts of the arguments of a function call are constants

Prior work

The MP-SPDZ bytecode and other VM-based MPC implementations.