non-terminating program
alzeha opened this issue · 9 comments
Hi,
I have a non-terminating program (at least I waited for several hours now...) and wanted to ask, whether there is a known reason for this or whether I just have to wait a little bit longer. I try to create an MPC program with the following logic:
Each party inputs a value.
The MPC program returns a vector with the ids of the parties, starting with the party that inputs the lowest number, then the second-lowest, and so on.
For this, I created the following code:
void EvaluateProtocol(mo::PartyPointer& party, std::uint32_t value) {
const std::size_t number_of_parties{party->GetConfiguration()->GetNumOfParties()};
// (pre-)allocate indices and input values
std::vector<mo::SecureUnsignedInteger> indices(number_of_parties), input_values(number_of_parties);
// share inputs
// remark: the input values to other parties' input gates are considered as buffers
// and the values are simply ignored and overwritten later
for (std::size_t i = 0; i < number_of_parties; ++i) {
input_values[i] = party->In<mo::MpcProtocol::kBooleanGmw>(mo::ToInput(value), i);
indices[i] = party->In<mo::MpcProtocol::kBooleanGmw>(mo::ToInput(i), 0);
}
std::cerr << "start the scheduler!" << std::endl;
auto sched_result = scheduler(input_values, indices);
std::cerr << "scheduler is done!" << std::endl;
std::vector<mo::ShareWrapper> temp(number_of_parties);
std::vector<mo::ShareWrapper> output(number_of_parties);
for(int i = 0; i < sched_result.size(); ++i) {
temp[i] = sched_result[i].Get();
output[i] = temp[i].Out();
}
// construct an output gate. This is slit in two expressions to avoid a wrong
// tempate type deduction
// mo::ShareWrapper& temp{sched_result[0].Get()};
// auto current = temp.Out();
// auto output = temp.Out();
std::cerr << "still alive, now running the protocol" << std::endl;
// run the protocol
party->Run();
party->Finish();
std::cerr << "protocol is done" << std::endl;
// and now do some stuff with the output...With "scheduler" being the following function:
inline std::vector<mo::SecureUnsignedInteger> scheduler(std::vector<mo::SecureUnsignedInteger> in, std::vector<mo::SecureUnsignedInteger> indices) {
// for unknown reasons, I can't use two dimensional vectors here (???). Therefore using one-dimensional and doing some ptr arithemtic for access
std::vector<mo::SecureUnsignedInteger> sorted_in (in.size()*in.size());
std::vector<mo::SecureUnsignedInteger> result (in.size()*in.size());
for(std::size_t i = 0; i < in.size(); ++i) {
result[0+i] = indices[i];
sorted_in[0+i] = in[i];
}
std::cerr << "start bubble sort" << std::endl;
// using bubble sort. Needs less gates than e.g. merge sort, but has complexity O(n^2) instead of O(n*log(n))
for(int i = 0; i < (in.size()-1); ++i) {
std::cerr << "i: " << i << std::endl;
auto current = sorted_in[i*in.size() + in.size() - 1];
auto cur_id = result[i*in.size() + in.size() - 1];
for(int j =(in.size() - 2); j >= i; --j) {
std::cerr << j << std::endl;
auto comparator = sorted_in[i*in.size() + j] > current;
sorted_in[(i+1)*in.size() + j+1] = comparator.Mux((sorted_in[i*in.size() + j]).Get(), current.Get());
current = comparator.Mux(current.Get(), (sorted_in[i*in.size() + j]).Get());
result[(i+1)*in.size() + j+1] = comparator.Mux((result[i*in.size() + j]).Get(), cur_id.Get());
cur_id = comparator.Mux(cur_id.Get(), (result[i*in.size() + j]).Get());
}
sorted_in[(i+1)*in.size() + i] = current;
result[(i+1)*in.size() + i] = cur_id;
}
std::cerr << "finished bubble sort" << std::endl;
std::vector<mo::SecureUnsignedInteger> output(in.size());
for(int i = 0; i < in.size(); ++i) {
output[i] = result[(in.size()-1) + i];
}
return output;
}When running with two parties, I get the following output:
start the scheduler!
start bubble sort
i: 0
0
finished bubble sort
scheduler is done!
still alive, now running the protocol
and then nothing happens for several hours.
Is there a reason for this?
Thanks a lot!
OS Information:
$ alsi
OS: Arch Linux x86_64
Hostname: -
Uptime: -
Kernel: 5.12.15-arch1-1
Shell: /bin/bash
Packages:-
DE: XFCE4
RAM: 1949M / 7645M (25%)
SWAP: - (0%)
CPU: Intel(R) Core(TM) i5-4300U CPU @ 1.90GHzDoes it work if you use BMR instead of Boolean GMW?
Yes, suddenly it is terminating.
Thx a lot.
Not necessary, but I am interested: Do you know, why this is the case?
I assume that there are still data races in OTs for MUX gates in some cases. The attempt to fix this (dca82d0) apparently was not completely successful.
ah ok. Thx
I just tested something similar for 2 to 5 parties and didn't experience any problems. Can you tell us more about your setting: operating system, compiler, compilation type? Is your code up to date with the master branch?
It would also be nice if you could provide a minimal (not) working example s.t. we could test it and find the problem, e.g., something like the millionaires' example that we can just plug in and run.
Hi,
I've pulled today's version of MOTION, deleted the old library & headers by hand (motioncore & flatbuffers), and installed it again. Then I recognized, that the utility/type_traits.hpp was not copied to /usr/install/include/motioncore. So I copied it by hand (not sure, whether I did sth wrong during the installation process, but that was a little bit strange).
Actually, I did a pull, make and make install, on tuesday, which seems to not have worked. The reason might be, that I did not do the deletion stuff beforehand.
Therefore, unfortunately, my version was like 2 months old and that caused this issue. Sorry for this.
Do I understand you correctly that now it works with the up-to-date version of MOTION? :)
yes
That's nice to hear!
Thanks also for describing the problem with the installation of type_traits.hpp. The fix is on the way.