search

Visa-Research / volepsi

Efficient Private Set Intersection base on VOLE
MIT License
104 stars 32 forks source link

Psi_Rs_multiThrd_test failed #75

Open nhysteric opened 2 weeks ago

nhysteric commented 2 weeks ago 
./frontend -u 38
38 - Psi_Rs_multiThrd_test       frontend: /home/nhy/test/extern/volePSI/volePSI/SimpleIndex.cpp:276: static volePSI::u64 volePSI::SimpleIndex::get_bin_size(volePSI::u64, volePSI::u64, volePSI::u64, bool): Assertion `B2 <= B' failed.
[2]    131216 abort (core dumped)  ./frontend -u 38

This is the gdb backtrace:

(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff79d1859 in __GI_abort () at abort.c:79
#2  0x00007ffff79d1729 in __assert_fail_base (fmt=0x7ffff7b67588 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n",
    assertion=0x555555cefb26 "B2 <= B",
    file=0x555555cefaf0 "/home/nhy/test/extern/volePSI/volePSI/SimpleIndex.cpp", line=276, function=<optimized out>)
    at assert.c:92
#3  0x00007ffff79e2fd6 in __GI___assert_fail (assertion=0x555555cefb26 "B2 <= B",
    file=0x555555cefaf0 "/home/nhy/test/extern/volePSI/volePSI/SimpleIndex.cpp", line=276,
    function=0x555555cefa88 "static volePSI::u64 volePSI::SimpleIndex::get_bin_size(volePSI::u64, volePSI::u64, volePSI::u64, bool)") at assert.c:101
#4  0x00005555559a7def in volePSI::SimpleIndex::get_bin_size (numBins=8, numBalls=13243, statSecParam=40,
    approx=true) at /home/nhy/test/extern/volePSI/volePSI/SimpleIndex.cpp:276
#5  0x000055555567fcf3 in volePSI::Baxos::getBinSize (numBins=8, numBalls=13243, statSecParam=40)
    at /home/nhy/test/extern/volePSI/volePSI/../volePSI/PaxosImpl.h:2559
#6  0x000055555599a9da in volePSI::RsPsiReceiver::run(volePSI::RsPsiReceiver::_ZN7volePSI13RsPsiReceiver3runESt4spanIN9osuCrypto5blockELm18446744073709551615EERN7coproto6SocketE.Frame *) (frame_ptr=0x555555fd5800)
    at /home/nhy/test/extern/volePSI/volePSI/RsPsi.cpp:234
#7  0x0000555555926331 in volePSI::RsOprfReceiver::receive(volePSI::RsOprfReceiver::_ZN7volePSI14RsOprfReceiver7receiveESt4spanIKN9osuCrypto5blockELm18446744073709551615EES1_IS3_Lm18446744073709551615EERNS2_4PRNGERN7coproto6SocketEmb.Frame *) (frame_ptr=0x555555fd6db0) at /home/nhy/test/extern/volePSI/volePSI/RsOprf.cpp:266
#8  0x0000555555926331 in volePSI::RsOprfReceiver::receive(volePSI::RsOprfReceiver::_ZN7volePSI14RsOprfReceiver7receiveESt4spanIKN9osuCrypto5blockELm18446744073709551615EES1_IS3_Lm18446744073709551615EERNS2_4PRNGERN7coproto6SocketEmb.Frame *) (frame_ptr=0x555555fd6db0) at /home/nhy/test/extern/volePSI/volePSI/RsOprf.cpp:266
#9  0x0000555555580bd2 in macoro::make_eager(macoro::_ZN6macoro10make_eagerINS_4taskIvLb1EEEEENS1_INSt11conditionalIXsrSt19is_rvalue_referenceINS_16awaitable_traitsIT_vE12await_resultEE5valueENSt16remove_referenceIS8_E4typeES8_E4typeELb0EEES6_.Frame *) (frame_ptr=0x555555fd8c20)
    at /home/nhy/test/extern/volePSI/out/install/linux/include/macoro/task.h:707
#10 0x0000555555929880 in osuCrypto::SilentVoleReceiver<osuCrypto::block, osuCrypto::block, osuCrypto::CoeffCtxGF128>::silentReceiveInplace(osuCrypto::SilentVoleReceiver<osuCrypto::block, osuCrypto::block, osuCrypto::CoeffCtxGF128>::_ZN9osuCrypto18SilentVoleReceiverINS_5blockES1_NS_13CoeffCtxGF128EE20silentReceiveInplaceEmRNS_4PRNGERN7coproto6Socket

And this assertion is also appeared in other test, like test 47:

./frontend -u 47
47 - filebase_psi_csv_Test       frontend: /home/nhy/test/extern/volePSI/volePSI/SimpleIndex.cpp:276: static volePSI::u64 volePSI::SimpleIndex::get_bin_size(volePSI::u64, volePSI::u64, volePSI::u64, bool): Assertion `B2 <= B' failed.
[2]    136147 abort (core dumped)  ./frontend -u 47
nhysteric commented 2 weeks ago

I also have a question about the max size of RsOpprf:

# receiver
oc::span<const block> keyspan(key.data() + offset, binSize);
oc::MatrixView<block> outputspan(outputs.data() + offset * outputs.cols(), binSize, outputs.cols());
auto p = receiver.receive(binSize * context.max_in_bin, keyspan, outputspan, prng, context.threads, chl);

# sender
oc::span<const block> keyspan(key.data() + offset, binSize * context.max_in_bin);
oc::MatrixView<block> valuespan(value.data() + offset * value.cols(), binSize * context.max_in_bin, value.cols());
auto p = sender.send(binSize, keyspan, valuespan, prng, context.threads, chl);

In this situation, the size of (valuespan+keyspan) is 4288042880 bytes, which is lower than u32 max 4294967295 bytes. However it still failed in extern/volePSI/out/install/linux/include/coproto/Socket/SocketScheduler.h:1016

COPROTO_ASSERT(data.size() < std::numeric_limits<u32>::max());

where data.size is 5771200000.

So my question is, how many additional information will be attached to the payloads?

ladnir commented 2 weeks ago

You could modify the code to use u64. I believe the size is n*1.24 or something like that.

I'll try to look at the multi threading at some point. Might not be soon.

nhysteric commented 2 weeks ago

Thank you for your reply. Modification code looks a bit complicated and I couldn't find a starting point. I'm now using subpackages to transfer data.

ladnir commented 2 weeks ago

OK. So apart from the multi thread thing your are good?

Also, you likely don't want to do a psi with more than a million items. If you do have that many, you can shard your dataset and process each shard independently.

https://eprint.iacr.org/2022/294

nhysteric commented 2 weeks ago

Yes, and this assertion `B2 <= B' will aslo failed in RsOPPRF with some specific input size.

ladnir commented 2 weeks ago

what sizes

nhysteric commented 2 weeks ago

Well, here is some tests I made:

X val values
sender 26840 26840*5000 receiver 2684
20180 20180*3000 2018
18216 18216*5268 2024

Where X and values are oc::span<block>, val is oc::MatrixView<block>. All sizes are in blocks.