std::out_of_range in BitVector

[Isweet]

I was playing around with MOTION and I'm getting a strange out of bounds exception. Here's a small example which will (hopefully) recreate the error.

namespace mo = encrypto::motion;

mo::BitVector<> do_share(mo::PartyPointer& party, mo::BitVector<> input, std::size_t me) {
  mo::ShareWrapper sh = party->In<mo::MpcProtocol::kBooleanGmw>(input, me);
  party->Run();
  mo::BitVector<> ret = sh.As<mo::BitVector<>>();
  party->Reset();
  return ret;
}

mo::BitVector<> do_and(mo::PartyPointer& party, mo::BitVector<> lhs, mo::BitVector<> rhs) {
  mo::ShareWrapper lhs_sh = party->SharedIn<mo::MpcProtocol::kBooleanGmw>(std::vector<mo::BitVector<>>{lhs});
  mo::ShareWrapper rhs_sh = party->SharedIn<mo::MpcProtocol::kBooleanGmw>(std::vector<mo::BitVector<>>{rhs});
  mo::ShareWrapper sh = lhs_sh & rhs_sh;
  party->Run();
  mo::BitVector<> ret = lhs_sh.As<mo::BitVector<>>();
  party->Reset();
  return ret;
}

void EvaluateProtocol(mo::PartyPointer& party) {
  std::vector<bool> inpA{false, true, false};
  std::vector<bool> inpB{true, false, true};

  mo::BitVector sh1 = do_share(party, mo::BitVector(inpA), 0);
  mo::BitVector sh2 = do_share(party, mo::BitVector(inpB), 1);
  mo::BitVector sh4 = do_and(party, sh1, sh2);
  std::cout << sh4 << std::endl;
  mo::BitVector sh5 = do_and(party, sh1, sh2);
  std::cout << sh5 << std::endl;

  party->Finish();
}

I've just got one of the standard harnesses initializing everything.

./bin/bug --my-id 0 --parties 0,127.0.0.1,23000 1,127.0.0.1,23001 &
./bin/bug --my-id 1 --parties 0,127.0.0.1,23000 1,127.0.0.1,23001

This results in:

111
101
terminate called after throwing an instance of 'std::out_of_range'
  what():  Accessing positions 3 to 9 of 3
terminate called after throwing an instance of 'std::out_of_range'
  what():  Accessing positions 3 to 9 of 3
Aborted (core dumped)

I'd really like to use MOTION for some of my own work, but I do need to be able to Reset() / Clear() and then start a new computation based on pre-shared inputs.

Is this a bug, or user error?

Thanks!

[Oleksandr-Tkachenko]

Unfortunately, Reset()/Clear() do not work yet: #4. Is it necessary to use those functions or is it possible for you to reallocate the Party object?

[Isweet]

Hmm, I'm not sure. Could the Party constructor take a reference to a CommunicationLayer (rather than a std::unique_ptr), so I don't have to setup the channels repeatedly?

Beyond the CommunicationLayer, what work gets done when a Party is constructed? I imagine this is also when shared seeds for PRGs are established, does anything else happen at that point?

I'm not a C++ expert, so if there is already a way to copy a Party object cheaply I'd be happy to try it.

[Oleksandr-Tkachenko]

But who then would own the CommunicationLayer?

The easiest way seems to me to just set up the channels repeatedly.

A less easy way is probably to somehow extract the CommunicationLayer instance or the raw sockets before they get closed and 'import' that in the new Party object. PRs are, of course, very welcome.

[Isweet]

Our main difficulty with using MOTION is the need to handle MPC code like:

mo::SecureUnsignedInteger x = f(...); // a large MPC computation
mo::SecureUnsignedInteger y = predicate(x); // compute some predicate over `x`
auto out = y.Out(); // we need to reveal the result and perform a cleartext conditional on it
mo::SecureUnsignedInteger z;
if (out) {
  z = g(x);
} else {
  z = h(x);
}
...

Of course, the code above won't work because out will not contain the cleartext value until the protocol is run with party->Run(). But, once that is done, we must create a new Party object. This presents two problems.

1. We must re-compute the circuit contained in x.
2. We must re-establish network connections, and backend setup even though the parties haven't changed.

We can solve (1) by running each gate individually (which is what the original code in this issue is doing) and extract the secret-shared value. This works for Boolean and Arithmetic protocols, but not BMR.

However, if we solve (1) as outlined above, we are re-creating the Party on every gate. This is obviously untenable.

It would be preferable if we could write the following:

mo::SecureUnsignedInteger x = f(...); // a large MPC computation
mo::SecureUnsignedInteger y = predicate(x); // compute some predicate over `x`
auto out = y.Out(); // we need to reveal the result and perform a cleartext conditional on it
party->Run();
mo::SecureUnsignedInteger z;
if (out) {
  z = g(x);
} else {
  z = h(x);
}
auto result = z.Out();
party->Run();
party->Finish();
std::cout << "Result: " << result << std::endl;

In the second call to Run, the values of the wires which are computed by the first call to Run are reused.

How large / invasive a change would something like this be?

Some example programs that require this kind of flexibility with intermediate revelation are tree-based ORAM constructions (e.g. Circuit ORAM) in which the position tag is revealed when reading from the ORAM, and secure sorting using a comparison-based sort on a shuffled array.

[Oleksandr-Tkachenko]

That's some non-standard functionality. The good news is that It's possible to realize it without invoking Run() multiple times. That's what Gates in MOTION are for - you could implement whatever functionality you want inside a Gate. You would input your x,y or x,out and output z, which boils down to outputting Wires in MOTION (on a low level), which are "waitable" objects, so other Gates can wait for the result of your new Gate without even knowing which Gate produced it.

It's also possible to implement a generic functionality that can handle multiple protocols like GMW, BMR, etc. I would usually implement it as multiple Gates, but your use case is not usual, so maybe you want to do it differently. So, the takeaway here is that you can implement arbitrary functionalities using Gates very flexibly.

As a simple example of how the logic of a Gate works, you might want to take a look at some simple Gate, e.g., GMW XOR. In a nutshell, for each registered Gate MOTION will run the corresponding EvaluateSetup() and EvaluateOnline() function as a separate fiber.

[Isweet]

I should clarify that we are intending to use MOTION as a library for an MPC interpreter. In other words, programs like the ones I mentioned above would be provided by the user and our interpreter would run these user-defined programs using MOTION as a backend.

I'll take a closer look at the Gate interface and see if there's a way to achieve what I want.

I appreciate all your help! Thanks for following up so quickly.

[Oleksandr-Tkachenko]

I think it should work if you implement your new gate in your own code. It should not be necessary to modify the MOTION code.