non-terminating program

[alzeha]

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.90GHz

[Oleksandr-Tkachenko]

Does it work if you use BMR instead of Boolean GMW?

[alzeha]

Yes, suddenly it is terminating.

Thx a lot.

Not necessary, but I am interested: Do you know, why this is the case?

[Oleksandr-Tkachenko]

I assume that there are still data races in OTs for MUX gates in some cases. The attempt to fix this (https://github.com/encryptogroup/MOTION/commit/dca82d0a68f1d8a22de4343c27450b100502f21e) apparently was not completely successful.

[alzeha]

ah ok. Thx

[Oleksandr-Tkachenko]

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.

[alzeha]

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.

[Oleksandr-Tkachenko]

Do I understand you correctly that now it works with the up-to-date version of MOTION? :)

[alzeha]

yes

[Oleksandr-Tkachenko]

That's nice to hear!

Thanks also for describing the problem with the installation of type_traits.hpp. The fix is on the way.