Testing ORAM without "insecure benchmarking functionality"?

[roostab]

Hi,

I'd like to benchmark the ORAM implementations. I've run make -j 8 bmr and ./compile.py -G -D gc_oram, and now I'm running ./Scripts/bmr-program-run.sh gc_oram 3. I'm following the README step by step and I haven't made any change to the code. I get the following output:

bmr-party.x: no process found
bmr-tparty.x: no process found
memcheck-amd64-valgrind: no process found
callgrind-amd64-valgrind: no process found
bmr-program-party.x: no process found
bmr-program-tparty.x: no process found
gdb: no process found
You are trying to use insecure benchmarking functionality for MPC emulation.
You can activate this at compile time by adding -DINSECURE to the compiler options.
Make sure to run 'make clean' as well before compiling.

I understand I can add -DINSECURE and it should work, but is there a way to benchmark ORAM without using "insecure benchmarking functionality"? I'm not sure what prompts this message.

Also, I guess I can run ORAM (e.g., the test_path_oblivious_heap.mpc) with any protocol in MP-SPDZ with compile-run.py. Is that correct? If so, could you please let me know which protocol was used for the results in this graph?

Thanks!

[mkskeller]

I understand I can add -DINSECURE and it should work, but is there a way to benchmark ORAM without using "insecure benchmarking functionality"? I'm not sure what prompts this message.

bmr-program-run.sh only implements the online phase as needed by the Eurocrypt paper. For a full timing, you need to use one of the variants listed in the BMR section of the readme.

Also, I guess I can run ORAM (e.g., the test_path_oblivious_heap.mpc) with any protocol in MP-SPDZ with compile-run.py. Is that correct? If so, could you please let me know which protocol was used for the results in this graph?

All arithmetic protocols can run ORAM. The graph has been produced by @tskovlund, and I have put the question to him in #1014.

[tskovlund]

Also, I guess I can run ORAM (e.g., the test_path_oblivious_heap.mpc) with any protocol in MP-SPDZ with compile-run.py. Is that correct? If so, could you please let me know which protocol was used for the results in this graph?

Hi @roostab. I have used the LowGear protocol to produce the results in the graph.

[roostab]

I understand I can add -DINSECURE and it should work, but is there a way to benchmark ORAM without using "insecure benchmarking functionality"? I'm not sure what prompts this message.

bmr-program-run.sh only implements the online phase as needed by the Eurocrypt paper. For a full timing, you need to use one of the variants listed in the BMR section of the readme.

Also, I guess I can run ORAM (e.g., the test_path_oblivious_heap.mpc) with any protocol in MP-SPDZ with compile-run.py. Is that correct? If so, could you please let me know which protocol was used for the results in this graph?

All arithmetic protocols can run ORAM. The graph has been produced by @tskovlund, and I have put the question to him in #1014.

Thank you! Any particular reason why binary protocols can't run ORAM? Actually, I could run oram_tutorial with Yao, but not test_path_oblivious_heap, so maybe it's just a matter of implementation for that data structure?

Hi @roostab. I have used the LowGear protocol to produce the results in the graph.

Thanks @tskovlund! I also found this Insert graph quite interesting! I'm assuming that graph was obtained with LowGear as well. In your experience, does the relative performance between ORAMs depend much on the protocol used to test them? Or is it the case that at large queue capacities Path ORAM outperforms Tree ORAM, and your implementation outperforms both, independently from the underlying protocol setting?

[mkskeller]

Thank you! Any particular reason why binary protocols can't run ORAM? Actually, I could run oram_tutorial with Yao, but not test_path_oblivious_heap, so maybe it's just a matter of implementation for that data structure?

Nothing in the theory forbids using binary protocols, it's just that the focus of MP-SPDZ is more on arithmetic protocols as the primary means with binary protocols in a supporting role. This is driven by the insight that binary protocols often perform worse for general tasks because addition and multiplication is more expensive with them. As far as I can tell, the path oblivious heap functionality features an int_type argument, which could be replaced by a binary type, but this most likely requires deeper changes to make it work.

[roostab]

Got it, thank you! (Yeah also, just for the record, path oblivious heap builds on PathORAM, which gives a Code not defined for instruction 0x102 when trying Yao, despite using compile.py -B as indicated; so I guess something is missing there too. I won't try to make changes, I think replicated secret sharing works well for what I was trying out. Thanks!)

[mcocartsy]

Hi @mkskeller, I thought to use this issue for a question on oram: Is there a way to run code with oram without multithreading? Can we fix the number of threads? Thanks

[mkskeller]

You should be able to achieve if you change get_n_threads() and get_n_threads_for_tree() to always returning None.

[mcocartsy]

Yes, thank you!

[mcocartsy]

@mkskeller actually if I do that the output reports just one thread instead of 9, but on htop I still see a lot of threads fully utilizing the machine. Should I change something in compilerLib as well to fix one thread per party so each just uses one cpu? Thanks

[mkskeller]

Which protocol are you using? MP-SPDZ is making use of threads for many reasons, including facilitating communication with several parties at once, so it's not possible to make it a strictly single-threaded program.