--- title: Achilles' Tent Notes #12 date: '2019-12-02' collection: research --- - [Achilles' Tent Notes #8](/research/2019-10-13-achilles-8) - [Achilles' Tent Notes #9](/research/2019-10-15-achilles-9) - [Achilles' Tent Notes #10](/research/2019-10-28-achilles-10) - [Achilles' Tent Notes #11](/research/2019-11-11-achilles-11) - [**Achilles' Tent Notes #12**](/research/2019-12-02-achilles-12) - [Achilles' Tent Notes #13](/research/2019-12-13-achilles-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: ```graph G = { A, B, C, D } ``` ![Fully connected graph of nodes A, B, C and D](/img/research/achilles/connected-graph.png) We can nest sets within each other: ```graph G = { { A, B }, { C, D } } ``` The two examples above are equivalent, however it may be useful to label specific groups of nodes anyway. ```graph H = { A, B } I = { C, D } G = { Q, R } ``` #### Fully Disconnected Graphs We can also define fully disconnected graphs with `[]`. ![Nodes A, B, C and D with no edges between them](/img/research/achilles/disconnected-graph.png) ```graph 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: ![Star graph with S in the center connected to A, B, C and D](/img/research/achilles/star-graph.png) ```graph 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. ```graph 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. ```graph 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. ```rust let P = protocol!([A, B]); ``` ![Party P connected to A and B, with a dashed line between A and B](/img/research/achilles/single-mpc-graph.png) 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. ```rust let A = protocol!([A, B]); let Y = protocol!([A, B]); ``` ![Parties A and Y each connected to nodes A and B, with a dashed line between the two parties](/img/research/achilles/double-mpc-graph.png) 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. ```rust let P1 = protocol!([A, B]); let P2 = protocol!([A, B]); let PP = protocol!([P1, P2]); ``` ![Head party P prime over parties P1 and P2 connected to A and B, and over P1 through Pn connected to A](/img/research/achilles/head-mpc-graph.png) Finally, we can construct protocols for which each layer is a recursive application of a protocol through some form of party-polymorphism. ```rust let P = protocol!([X, Y, Z]); let P1 = P; let P2 = P; let P3 = P; let PH = P; ``` ![Tree with P hat at the root over P1, P2 and P3, each with three leaf nodes A through I](/img/research/achilles/recursive-mpc-graph.png) ```rust 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.