Achilles' Tent Notes #12 written by Nathan Lilienthal on December 02, 2019.
- Achilles’ Tent Notes #8
- Achilles’ Tent Notes #9
- Achilles’ Tent Notes #10
- Achilles’ Tent Notes #11
- Achilles’ Tent Notes #12
- Achilles’ Tent Notes #13
Graph Notation
To run an MPC we must be able to label each party (and virtual party) which constitutes the protocol. Based on the architectures given as challenge problems in the HECTOR GFI, we attempt to create a notation for easily describing these topologies.
Fully Connected Graphs
Sets of fully connected parties are denoted with {}
, for example the
following shows a simple network of four parties:
G = { A, B, C, D }
We can nest sets within each other:
G = { { A, B }, { C, D } }
The two examples above are equivalent, however it may be useful to label specific groups of nodes anyway.
H = { A, B }
I = { C, D }
G = { Q, R }
Fully Disconnected Graphs
We can also define fully disconnected graphs with []
.
G = [A, B, C, D]
While a disconnected graph may seem useless by itself, when nested within a larger connected graph they allow us to represent arbitrarily complex topologies of graphs (TODO: is this actually true?).
Star Graphs
For example a “star” network with four edge nodes and a single center node can be represented like this:
G = { S, [A, B, C, D] }
= [{ S, A }, { S, B }, { S, C }, { S, D }]
Or a more complex example of a “server star” graph, linked into an MPC protocol.
I = [I1, I2, I3, I4, I5]
S = {S1, S3, S3}
O = [O1, O2, O3, O4]
P = init_protocol!({S, [I, O]})
Example Reduction
Here we show that starting with a graph description G
, we end up with an
equivalent graph description G'
through a series of reductions.
G
is a graph of a disconnected [A,B]
, connected to C
, all disconnected
from D
, finally connected to E
. We can interpret this more naturally by
thinking of the fully connected graph {A,B,C,D,E}
, then removing connections
to maintain the property that [A,B]
and [D, {A,B,C}]
are disconnected.
G = {[{[A,B],C},D],E}
->
{[[{A,C},{B,C}],D],E}
->
{[{A,C},{B,C},D],E}
->
G' = [{A,C,E},{B,C,E},{D,E}]
MPC Architecture
With the ability to express arbitrary graphs, we can construct MPC protocol architectures for the constituent parties. A single pair of nodes \(A\) and \(B\) can be connected together with virtual party \(P\) as shown below.
let P = protocol!([A, B]);
This gives conceal
and reveal
operations (solid edges) going up and down
the graph with respect to the virtual party \(P\), as well as send
and recv
operations (dashed edges) between the parties. It’s worth noting here that
\(A\) and \(B\) must be allowed to communicate, meaning that the notion of
“connectedness” is talking about the ability to conceal and reveal, not send
and receive. More work may need to be done on this design to make this clear.
Constituents may make up multiple protocols at once, which may even implement conversions directly between each other. In the graph below, virtual party \(A\) represents an arithmetic protocol, while virtual party \(Y\) represents a Yao protocol.
let A = protocol!([A, B]);
let Y = protocol!([A, B]);
In addition to parties participating in multiple protocols, the protocols themselves may participate in other protocols. This leads to “MPC in the head” style protocols.
let P1 = protocol!([A, B]);
let P2 = protocol!([A, B]);
let PP = protocol!([P1, P2]);
Finally, we can construct protocols for which each layer is a recursive application of a protocol through some form of party-polymorphism.
let P<X, Y, Z> = protocol!([X, Y, Z]);
let P1 = P<A, B, C>;
let P2 = P<D, E, F>;
let P3 = P<G, H, I>;
let PH = P<P1, P2, P3>;
fn calc3<@P>(a: bool@P, b: bool@P, c: bool@P);
// Works on a single layer of protocols.
let a = conceal!(@P1 <= @A { true });
let b = conceal!(@P1 <= @B { false });
let c = conceal!(@P1 <= @C { false });
calc3(a, b, c);
let d = conceal!(@P2 <= @D { false });
let e = conceal!(@P2 <= @E { true });
let f = conceal!(@P2 <= @F { true });
let g = conceal!(@P3 <= @G { true });
let h = conceal!(@P3 <= @H { false });
let i = conceal!(@P3 <= @I { true });
// Also works when we lift the values up to a higher protocol.
let abc = conceal!(@PH <= @P1 { a + b + c });
let def = conceal!(@PH <= @P2 { d + e + f });
let ghi = conceal!(@PH <= @P3 { g + h + i });
calc3(abc, def, ghi);
The details of this however, are still a work in progress.