Designing a simple high-level API for MPC

[rozbb]

We spoke about creating a set of traits which let a caller run complicated OT+MPC protocols without having to know anything other than their function input and the network socket they're using. These are roughly the traits, structs, and methods I had in mind.

Notes:

• This only does standard OT right now. I'm not sure how we want to support both random and standard OT. Different methods? Different structs? Different traits?

• For random OT, I'm thinking that setup does setup and derandomization, and eval is when the final payload is sent. Should I split it further?

• A problem with MPC. A garbler currently doesn't know which or even how many inputs the evaluator will have. This makes it tough to do garbling and OT setup before eval. Similarly, the MPC evaluator doesn't know in advance which wire indices correspond to its input. It might be worthwhile to augment our circuits with metadata designating the wire indices belonging to the two parties. The proposal below assumes that this is resolved.

The sketch:

/// Defines a whole OT protocol. The associated types have traits defined in the `ot/extension/` dir
trait ObliviousTransfer {
    type Sender: ExtStandardSendCore;
    type Receiver: ExtStandardReceiveCore;
}

/// Defines a whole MPC protocol. The associated types have traits defined in the `garble/` dir
trait Mpc {
    type Garbler: GarbledCircuitGenerator;
    type Evaluator: GarbledCircuitEvaluator;
}

/// Define generic runners that will async-execute the entire OT protocol
struct OtReceiverRunner<OT: ObliviousTransfer>(OT::Receiver);
struct OtSenderRunner<OT: ObliviousTransfer>(OT::Sender);

/// Define generic runners that will async-execute the entire MPC protocol
struct MpcGarblerRunner<OT: ObliviousTransfer, MPC: Mpc> {
    ot_sender: OT::Sender,
    mpc_garbler: Mpc::Garbler,
}
struct MpcEvaluatorRunner<OT: ObliviousTransfer, MPC: Mpc> {
    ot_receiver: OT::Receiver,
    mpc_evaluator: Mpc::Evaluator,
}

// Define methods for all the runners

impl<OT: ObliviousTransfer> OtReceiverRunner<OT> {
    /// Does the setup phase for this OT. Everything short of `execute()`
    async fn setup<R, C>(&mut self, rng: &mut R, chan: &mut C, num_bits: usize) -> Result<(), Error>
    where
        R: Rng,
        C: AsyncRead + AsyncWrite
    {
        // Do whatever sequence is necessary to run setup
    }

    /// Receives `num_bits` labels from the sender
    async fn execute<C>(&mut self, chan: &mut C, choices: &[bool]) -> Result<Vec<Block>, Error> {
        // ...
    }
}

impl<OT: ObliviousTransfer> OtSenderRunner<OT> {
    /// Does the setup phase for this OT. Everything short of `execute()`
    async fn setup<R, C>(&mut self, rng: &mut R, chan: &mut C, num_bits: usize) -> Result<(), Error>
    where
        R: Rng,
        C: AsyncRead + AsyncWrite
    {
        // ...
    }

    /// Sends `num_bits` labels to the receiver. This returns nothing to the sender.
    async fn eval<C>(&mut self, chan: &mut C) -> Result<(), Error> {
        // ...
    }
}

impl<MPC, OT> MpcGarblerRunner
where
    MPC: Mpc,
    OT: ObliviousTransfer,
{
    /// Garbles the circuit and does the OT setup
    fn setup<R, C>(&mut self, rng: &mut R, chan: &mut C, circ: &Circuit) -> Result<(), Error> 
    where
        R: Rng,
        C: AsyncRead + AsyncWrite,
    {
        // ...
    }

    /// Does the eval, sending the garbled circuit and the input labels
    fn eval<R, C>(&mut self, rng: &mut R, chan: &mut C, inputs: &[InputLabel]) -> Result<(), Error>
    where
        R: Rng,
        C: AsyncRead + AsyncWrite,
    {
        // ...
    }
}

impl<MPC, OT> MpcEvaluatorRunner
where
    MPC: Mpc,
    OT: ObliviousTransfer,
{
    /// Receives the OT bits for the given circuit
    fn setup<R, C>(&mut self, rng: &mut R, chan: &mut C, circ: &Circuit, inputs: &[bool]) -> Result<(), Error> 
    where
        R: Rng,
        C: AsyncRead + AsyncWrite,
    {
        // ...
    }

    /// Does the eval, receiving the garbled circuit and the garbler's input labels, and running
    /// the circuit
    fn eval<R, C>(&mut self, rng: &mut R, chan: &mut C) -> Result<Vec<bool>, Error>
    where
        R: Rng,
        C: AsyncRead + AsyncWrite,
    {
        // ...
    }
}

[sinui0]

Thanks for taking a stab at this, creating clean interfaces for these protocols has proven to be nontrivial. I think our lives will be easier including the channel into the traits as you've done here, as now we can put the communication details behind it. We should keep the core/aio isolation where we can so that a future sync implementation can be built if desired, but let's not let that abstraction slow us down too much.

This only does standard OT right now. I'm not sure how we want to support both random and standard OT. Different methods? Different structs? Different traits?

I think that different traits makes sense for this, but as you pointed out earlier, the method names shouldn't collide as there will be cases where structs implementing both are in scope and we don't want the user to have to use fully qualified syntax.

For random OT, I'm thinking that setup does setup and derandomization, and eval is when the final payload is sent. Should I split it further?

This would defeat the main benefit of Random OT, where the Receiver is able to makes their choices sometime later after setup. Additionally, the Receiver's choices $c_m .. c_n$ may depend on $c0 .. c{m-1}$, so the interface needs to allow for incremental consumption of setup OTs.

A problem with MPC. A garbler currently doesn't know which or even how many inputs the evaluator will have. This makes it tough to do garbling and OT setup before eval. Similarly, the MPC evaluator doesn't know in advance which wire indices correspond to its input. It might be worthwhile to augment our circuits with metadata designating the wire indices belonging to the two parties. The proposal below assumes that this is resolved.

Yes, this is definitely something to address. I had it in mind previously but didn't get to implementing it. We need wrapper structs or a trait which provides this metadata. This shouldn't take too much effort, and the core components CircuitInput and InputLabel are already there.

trait Mpc {
    type Garbler: GarbledCircuitGenerator;
    type Evaluator: GarbledCircuitEvaluator;
}

I'm not a fan of calling this trait Mpc for a couple reasons. 1) Garbled circuits is a subclass of MPC, more specifically 2PC 2) We have/will support more protocols than Garbled Circuits.

---

Here are some things we should support

Oblivious Transfer

• Allow the user to choose which protocol to use (CO vs KOS) as well as which mode random/standard
• Setup and execution are decoupled
• (nice to have) OT setup produces an object which can be partitioned into multiple instances which can be executed independently.

Garbled Circuits

• Garbling can be done well in advance during the offline phase, then executed later.
• Support multiple modes of execution (Single, Dual, Dual + other addons for malicious security, Privacy-free)

---

Stepping back for a moment: Right now, in general, I don't think we should invest too much energy into high-level APIs, rather we should develop solid low-level APIs which meet our immediate needs.

[th4s]

Intro

In general I think that coming up with good interfaces for OT and MPC is quite hard, because I am not so sure about what are the invariants of these protocols. For example in MPC:

• the number of parties involved in the protcol can be very different, which has an impact on the number of channels.
• not all MPC protocols need OT. Some use Somewhat Homomorphic Encryption (SHE) for generating Beaver triples instead of OT.
• Garbling is a very "asymmetric" protocol in that it has a sender and receiver, but there are other MPC protocols, which do not really make a difference between those two roles.

I think for OT it is somehow similar. There is normal OT, random OT, OT extensions, ... and probably a lot of different protocols to implement these variants.

I think that different traits makes sense for this, but as you pointed out earlier, the method names shouldn't collide as there will be cases where structs implementing both are in scope and we don't want the user to have to use fully qualified syntax.

I have mixed feelings about this. On the one hand I can see that it simplifies coming up with interfaces for these variants, on the other hand are these protocols really that different considering the core concept of OT (oblivious subset selection of some elements)? I could imagine that this is something which is resolved by trying to implement an OT interface for some protocols and see how it works?

Stepping back for a moment: Right now, in general, I don't think we should invest too much energy into high-level APIs, rather we should develop solid low-level APIs which meet our immediate needs.

Absolutely! I think we will get a far better overview, once we have some protocol implementations and this will make it easier to come up with interfaces. The downside is that our code might be a little bit coupled for a while, but I think it is worth it.

General thoughts

I feel that the main design axes to have in our head are

• Parties (Sender/Receiver): In a protocol we have several parties involved. In the case of 2PC Garbling and OT we have Sender/Receiver, but we might support protocols where this can change.
• CPU/IO: This is about separation between protocol functionality and execution.
• Setup/Execution: In the execution of the protocol we often have a setup phase before the actual execution.

Some thoughts on Michael's interface

I really like the separation between protocol functionality and execution and I also tried to make use of this when coming up with my own design. Some more thoughts:

• I feel that a lot of protocols have a setup and an execution phase. Maybe we can leverage this to also come up with a trait/interface for this? In this case I would move everything else except the &mut self and the channel into the protocol implementation.
• I cannot find ExtStandardSendCore and ExtStandardReceiveCore. I assume you mean ExtOTSend and ExtOTReceive? Maybe we can put more of the intended behavior of the different communication rounds into the OT interface?

Using associated types in trait to batch Sender and Receiver

trait ObliviousTransfer {
    type Sender: ExtStandardSendCore;
    type Receiver: ExtStandardReceiveCore;
}

I also had this idea, but discarded it, when I noticed that it tightly couples Sender and Receiver. But the reason was, that when I tried to implement it, I had some sort of wrapper struct like e.g.

struct CO15 {
    sender: CO15Sender,
    receiver: CO15Receiver
}

This makes it very difficult to deal with a sole sender or receiver, which should be well supported. Then I realized that it is also possible to have a zero-sized-type struct and do it like this:

fn main() {
    // We can deal separately with sender and receiver
    let sender = <CO15 as OT>::OTSender::default();
    sender.ping();
}

trait OT {
    type OTSender: OTSend;
    type OTReceiver: OTReceive;
}

struct CO15;

impl OT for CO15 {
    type OTSender = CO15Sender;
    type OTReceiver = CO15Receiver;
}

trait OTSend {
    fn ping(&self);
}

#[derive(Default)]
struct CO15Sender;
impl OTSend for CO15Sender {
    fn ping(&self) {
        println!("ping")
    }
}
trait OTReceive {
    fn pong(&self);
}

#[derive(Default)]
struct CO15Receiver;
impl OTReceive for CO15Receiver {
    fn pong(&self) {
        println!("pong")
    }
}

So in a way this batches together Sender and Receiver under a single trait, but having a trait with associated types without any functionality (methods) somehow defeats the purpose of an interface/trait? In a way this is just syntactical sugar for dealing with Sender and Receiver directly. Are there other benefits I do not see?

[th4s]

This is just an interface design for Oblivious Transfer. When tinkering with this, I realized that I put most of the effort into a protocol/execution separation. This should be fairly similar for MPC, once we are sure about the core behavior of MPC.

Some comments:

• The main idea is to put the protocol logic into the OT traits and the whole execution into the Setup and Execute traits. The whole state mutation takes place in the setup and execute functions, which use the protocol functions from the OT traits where the core functionality of the protocol is.
• The OT trait functions only have &self access in order to get close to a functional core.
• Setup and Execute traits are separated and their functions have access to self to make use of some sort of state machine, i.e. the example implementation CO15 is generic over it's state, which serves two purposes:
  • type-safe separation of behavior: e.g. only a CO15Sender<SenderReady> can execute and when it does it is a CO15Sender<SenderFinished>.
  • more flexibility with inner state since I could imagine that they are quite different dependent on which phase the Sender or Receiver is currently in.

I am not sure, if this is maybe a bit too clunky?

use async_trait::async_trait;
use futures::io::{AsyncRead, AsyncWrite};

trait ObliviousSend {
    type Preparation;
    type Envelope;
    type Error: std::error::Error;

    fn prepare(&self) -> Result<Self::Preparation, Self::Error>;
    fn submit(&self) -> Result<&[Self::Envelope], Self::Error>;
}

trait ObliviousReceive<T> {
    type Error: std::error::Error;

    fn pick(&self) -> Result<&[u8], Self::Error>;
    fn extract(&self) -> Result<&[T], Self::Error>;
}

#[async_trait]
trait Setup
where
    Self: Sized,
{
    type Error: std::error::Error;
    type Out;

    async fn setup<C: AsyncRead + AsyncWrite + std::marker::Send>(
        self,
        channel: &mut C,
    ) -> Result<Self::Out, Self::Error>;
}

#[async_trait]
trait Execute
where
    Self: Sized,
{
    type Error: std::error::Error;
    type Out;

    async fn execute<C: AsyncRead + AsyncWrite + std::marker::Send>(
        self,
        channel: &mut C,
    ) -> Result<Self::Out, Self::Error>;
}

mod co15 {
    use super::{Execute, ObliviousReceive, ObliviousSend, Setup};
    pub use {co15_receiver::CO15Receiver, co15_sender::CO15Sender};

    pub type Message = String;

    #[derive(Debug, Clone)]
    pub enum CO15Error {
        FirstError,
        SecondError,
        // ...
    }

    impl std::fmt::Display for CO15Error {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            todo!()
        }
    }

    impl std::error::Error for CO15Error {
        fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
            todo!()
        }
    }

    mod co15_sender {
        use super::{Execute, ObliviousSend, Setup};
        use async_trait::async_trait;
        use futures::io::{AsyncRead, AsyncWrite};

        pub trait SenderState {}

        pub struct SenderInit;
        impl SenderState for SenderInit {}

        pub struct SenderReady;
        impl SenderState for SenderReady {}

        pub struct SenderFinished;
        impl SenderState for SenderFinished {}

        pub struct CO15Sender<T = SenderInit>
        where
            T: SenderState,
        {
            state: T,
        }

        impl CO15Sender<SenderInit> {
            pub fn new(param1: (), param2: ()) -> Self {
                todo!()
            }
        }

        impl ObliviousSend for CO15Sender<SenderReady> {
            type Preparation = ();
            type Envelope = ();
            type Error = super::CO15Error;

            fn prepare(&self) -> Result<Self::Preparation, Self::Error> {
                todo!()
            }

            fn submit(&self) -> Result<&[Self::Envelope], Self::Error> {
                todo!()
            }
        }

        #[async_trait]
        impl Setup for CO15Sender<SenderInit> {
            type Error = std::io::Error;
            type Out = CO15Sender<SenderReady>;

            async fn setup<C: AsyncRead + AsyncWrite + std::marker::Send>(
                self,
                channel: &mut C,
            ) -> Result<Self::Out, Self::Error> {
                todo!()
            }
        }

        #[async_trait]
        impl Execute for CO15Sender<SenderReady> {
            type Error = std::io::Error;
            type Out = CO15Sender<SenderFinished>;

            async fn execute<C: AsyncRead + AsyncWrite + std::marker::Send>(
                self,
                channel: &mut C,
            ) -> Result<Self::Out, Self::Error> {
                todo!()
            }
        }
    }

    mod co15_receiver {
        // This is very similar to co15_sender...
    }
}

[sinui0]

In general I think that coming up with good interfaces for OT and MPC is quite hard, because I am not so sure about what are the invariants of these protocols...

I agree. We should contain the scope of this initiative. We can keep it narrow to 2PC protocols, not MPC. Specifically the ones we need to implement TLSNotary. eg. Garbled circuits, OT, MAC, PRF

In a way this is just syntactical sugar for dealing with Sender and Receiver directly. Are there other benefits I do not see?

That seems to be the case to me

---

trait ObliviousSend {
    type Preparation;
    type Envelope;
    type Error: std::error::Error;

    fn prepare(&self) -> Result<Self::Preparation, Self::Error>;
    fn submit(&self) -> Result<&[Self::Envelope], Self::Error>;
}

The issue with a trait like this is that it presumes that the number of communication rounds is constant. This is one of the reason we decided to ditch having a trait at this layer.

I am more in favor of the proposed Setup and Execute traits, as the communication complexity is hidden. However, I'm not sure whether this pattern will generalize well to other types of protocols. How does user input work in this example?

---

I do like the typestate pattern but we ended up ditching it earlier on as well. However, that may have been more due to my inexperience with the pattern than its merit. If you feel like we can utilize them ergonomically I'm all for it.

---

What are your thoughts on borrowed stream vs owned stream? Your example traits assume a borrowed stream, which means the OT impl would have exclusive control over the stream until the future completes. Additionally, the parent of the OT impl would be burdened with having to manage it.

For example:

pub struct Protocol {}
impl Protocol {
  async fn foo<C: AsyncRead + AsyncWrite>(&self, channel: C) {
    let mut other = OtherProtocol::new();
    let mut ot = OTReceiver::new();
    // We'd like to execute these two sub protocols concurrently, but we're either faced with:
    // 1) We only have 1 channel to lend, so we have to execute them sequentially
    // 2) We can split our channel, but now Protocol has to manage those details, such as passing in
    // a channel controller.
    let (r1, r2) = join(
        other.bar(&mut channel),
        ot.setup(&mut channel ????)
    );
    ...
  }
}

In this situation it would be nice if Protocol didn't have to manage the channel for the sub protocols. OtherProtocol and OTReceiver could instead be dependencies for foo() where they each own their own channel. Of course there is a trade-off here, because having to own the channel comes with issues as well.

[themighty1]

Just to be clear: whatever we're trying to design here will end up being "the" half-gates 2PC crate for Rust which other projects will use. Is this still in scope of the decision-making here?

I just wanted to remind us that semi-honest GC is of very little utility to other projects as opposed to maliciously-secure GC. So, if we want to release a stand-alone GC crate, we have bake in the leaky DualEx also for malicious security. ( But again, since it is leaky, it may not be useful to others )

Im not saying I have an opinion. I just want us to keep in mind that most likely TLSNotary will be the only user of our GC impl. So, maybe, this idea could narrow down the scope of this conversation.

[sinui0]

Is this still in scope of the decision-making here?

To some extent yes, but we're getting to the point where we just need to get it put together and not have the public API slow us down much more.

So, if we want to release a stand-alone GC crate, we have bake in the leaky DualEx also for malicious security.

We don't have to do so, just need to make it clear in the docs what the security assumptions are. I won't lose any sleep over it if people aren't satisfied with what is provided. PRs will be welcome :) However, we are more-or-less implementing DE anyhow.

this idea could narrow down the scope of this conversation.

I agree with the sentiment as what trying to convey it earlier as well. We want this crate to be useful for others eventually, but our primary goal right now is our immediate needs for implementing TLSNotary. With that said, we still have to develop good APIs for ourselves to use :)

[th4s]

The issue with a trait like this is that it presumes that the number of communication rounds is constant. This is one of the reason we decided to ditch having a trait at this layer.

After thinking about this a little bit more, I agree. Do we intend to have a single OT trait at all? Having a look into the codebase OTSend and ExtOTSend (same for Receive) are identical for OT and OTE. They only consist of a single method, probably to make the trait independent of communication rounds. Do you think that these method signatures are flexible enough for more OT protocols?

How does user input work in this example?

In order to make the interface as flexible as possible, my thought was to provide user input via self so that this is not leaked into the interface because I expect this to be very different depending on the various OT implementations. So e.g. to create a Sender one would invoke a fn new(.....) -> Self which is not part of the interface and allows to provide user input. During protocol execution user input would be provided by fn execute(&mut self, ...) calling some fn user_input(&self, ...) -> UserInput which is not part of the interface and specific to the OT protocol being used.

I do like the typestate pattern but we ended up ditching it earlier on as well. However, that may have been more due to my inexperience with the pattern than its merit. If you feel like we can utilize them ergonomically I'm all for it.

Honestly, I am not sure. Maybe, let's try it it out and see if it works/feels good or if this is too much overhead. What was the reason for ruling it out?

What are your thoughts on borrowed stream vs owned stream?

I assume that our whole application makes use of a single websocket connection, which is then multiplexed for the different purposes needed. Considering your example, is there only a single Protocol running at a time, or are there several protocols running?

[sinui0]

Do we intend to have a single OT trait at all?

At the core layer, I don't think it is necessary. At the higher layer (aio), we can have OT traits as the communication details will be hidden. You're right about the trait redunancy, I really did just slap things together as I was learning about the various protocols. I think we can consolidate them.

---

I'm not totally convinced of the Setup/Execute abstraction, perhaps it is too high level? What is the benefit of buffering user input rather than providing an associated type or something along these lines?

pub trait OTSend {
  type Input;
  async fn send(&mut self, inputs: &[Self::Input]) -> Result<(), Error>;
}

pub trait OTReceive {
  type Choice;
  type Item;
  async fn receive(&mut self, inputs: &[Self::Choice]) -> Result<Vec<Self::Item>, Error>;
}

impl OTSend for Kos15Sender<Ready> {
  type Input = [Block; 2];
  async fn send(&mut self, inputs: &[Self::Input]) -> Result<(), Error> {
    // this assumes self owns a stream to receiver
    ...
  }
}

impl OTReceive for Kos15Receiver<Ready> {
  type Choice = bool;
  type Item = Block;
  async fn receive(&mut self, choice: &[Self::Choice]) -> Result<Vec<Self::Item>, Error> {
    // this assumes self owns a stream to sender
    ...
  }
}

I expect this to be very different depending on the various OT implementations

I'm not sure that will be the case. The only variables I can think of are:

• 1 of N vs 1 of 2
• Random OT vs Standard OT
• Communication rounds (which is hidden by the traits above)

---

let's try it it out and see if it works/feels good or if this is too much overhead.

Sounds good. I'm willing to give it another shot as long as it doesn't bog us down.

What was the reason for ruling it out?

I don't recall all the reasons, it was just slowing me down at first because it was my first time with the pattern. If you can use it effectively I'll follow suit.

I assume that our whole application makes use of a single websocket connection, which is then multiplexed for the different purposes needed. Considering your example, is there only a single Protocol running at a time, or are there several protocols running?

Yes, I was thinking to run it over a single connection. But my example was intended to illustrate the clunkyness of a borrowed stream when there is nesting. Protocol would actually be a sub-protocol with it's own sub-protocols, thus it would be messy if you had to pass multiple streams down the dependency tree, or have details around multiplexing leak into Protocol.

[th4s]

I'm not totally convinced of the Setup/Execute abstraction, perhaps it is too high level?

Yeah, I agree in some way. It is just an async function providing a channel. So do we want to ditch the OT traits at the core level and just come up with OT traits for the execution?

What is the benefit of buffering user input rather than providing an associated type or something along these lines?

It is a little bit more flexible (but also more cumbersome) and does not leak into the interface. For example how would you use the OTSend trait to implement CO15 using associated types? Specifically, that the sender sends a public key to the receiver at the beginning.

I'm not sure that will be the case. The only variables I can think of are...

Being independent of communication rounds is perfect. But what about different inputs to the communication rounds, depending on the protocol? I think using associated types for that could be difficult because protocols differ on what/how many/if additional input is needed.

Yes, I was thinking to run it over a single connection...

Using a single connection is a good choice I think. The multiplexing should probably bother the Protocol implementations as little as possible. I haven't looked deeply enough into this area. Are the details about how tokio/async will be used, already worked out or implemented? I will probably have to go through https://tokio.rs/tokio/tutorial as a good refresher. What do you think will the channels be in most cases, a network socket?

[sinui0]

So do we want to ditch the OT traits at the core level

Yes, I don't think we need traits in mpc-core, rather we'll have a set of traits in mpc-aio instead.

For example how would you use the OTSend trait to implement CO15 using associated types? Specifically, that the sender sends a public key to the receiver at the beginning.

It would look the same as for KOS15, the Sender wants to send 1 of 2 Block to the Receiver. The sending of public keys occurs during setup. Using your suggestion of type states we could have something like:

impl Setup for CO15Sender<Start> {
...
}

impl OTSend for CO15Sender<Ready> {
  // This is 1 of 2 OT, where the receiver can decrypt one of the two Blocks sent depending on their choice
  type Input = [Block; 2];
  async fn send(&mut self, inputs: &[Self::Input]) -> Result<(), Error> {
    // this assumes self owns a stream to receiver
    ...
  }
}

But what about different inputs to the communication rounds, depending on the protocol?

We could use different traits in that case. The above example is Standard OT, but as you point out there may be additional user input required such as with Random OT. Both CO and KOS protocols implement Standard OT.

[th4s]

Alright. Then no traits at the core level and different protocol traits on the aio level :+1:

[sinui0]

Closing, as most of the API has been designed and implemented.