Add support for sub-computations

[mortendahl]

This issue is about allowing computation graphs to invoke other computation graphs for the usual reasons of code modularity and reuse. Sub-computations also forms the backbone of supporting iteration through recursion. Sub-computations could also form the basis of a future Moose standard library for various tasks.

One design goal of sub-computations, is to support multi-phased cryptographic protocols, such as for instance commitment protocols where a value is committed to in phase 1 and opened in phase 2, with arbitrary operations allowed to happen in-between. For this reason we should not adapt a strict function call semantics where all inputs are available initially.

Moreover, computations should not have a single call site since we want to allow inputs from several different players/placements.

Finally, we want the ability to run sub-computations concurrently.

[mortendahl]

Below is my proposed design for sub-computations. It is based on generalizing a computation to not be a single graph, but rather a labelled set of graphs. The graph with label main is the entrypoint. The arguments to a computation are still its Input operations, and its return values are still its Output operations.

Enter and Exit operations are used for calling a sub-computation, with bijections between Enter and Input, and between Output and Exit operations. As usual all operations have unique names, with Enter and Exit nodes holding the names of the Input and Output operations as attributes, in addition to the label of the sub-computation. Enter and Exit operations belonging to the same sub-computation invocation are linked together through the value of the activation_tag (aka activation_key) attribute.

Note that it may in some cases be relevant to bring extra players/placements into a sub-computation, even if they don't provide input values. In this case we add extra unit-valued inputs. It may likewise in some cases be relevant to output unit values, or instance to signal to a player/placement that a certain point in the computation has been reached. Technically, these dummy inputs allow the runtime on the corresponding worker to schedule a sub-session for (it's part of) the sub-computation.

As an example, say we have sub-computation:

This could then be invoked as follows from the main computation:

Each sub-computation is evaluated under a sub-session id computed as sub-sid = sid || activation_tag. This ensures that sub-session ids are unique and deterministic.

Note that we could consider adding gate operations that ignored their input but generates a unit value instead. These can be used to keep players somewhat in sync and prevent early scheduling. Note also that when scheduling a sub-computation it may be useful to either derive or extract the dependencies between inputs and outputs in a sub-computation (and fail if this introduces a cycles); when doing scheduling in the async setting this makes sure that the task and future for an output is available before scheduling the task and future for the exit.

Additional notes:

• Computations can be precompiled so that repeated invocation is faster; need to take some care to make sure placement instantiation is taken into account when caching.
• Recursion in particular will require some form of conditional invocation, eg conditional Enter/Exit nodes that invokes one out of two sub-computations (with the same signature) depending on a third boolean input.
• Open question about how scheduling can best be done on a worker. One potential solution might be to have Enter and Exit nodes send a message to a scheduler components to provide an input or receive an output from a session, and launch that session if it doesn't exist yet.

[mortendahl]

Jamboard: https://jamboard.google.com/d/1Dr294lS34XxOwrxDImaRFwNl0w280ba-mjUn5ss1LCc/viewer?f=0