Implementation and results for DHTPIR simulations

Stan Gurtler 5f7aba370d Updated to identify the specific libraries that need to be installed for things to compile and run properly 1 year ago
cuckoo_simulation 64ebbe5d68 Update to the latest cuckoo simulation code 1 year ago
dhtpir_simulation aeca3a2d31 those files shouldn't actually be in git 1 year ago
outputs 44de1f2746 Preparing artifacts for external review 1 year ago
plots 0eef06f516 new directory names means one line needs to be updated 1 year ago
README.md 5f7aba370d Updated to identify the specific libraries that need to be installed for things to compile and run properly 1 year ago

README.md

DHTPIR

Simulation code for research performed by Miti Mazmudar, Stan Gurtler, and Ian Goldberg at the University of Waterloo

Directories

  • ./dhtpir_simulation/: The code used to simulate DHTPIR and other related works, in order to compare their respective computational and bandwidth usage. (Details on running this code in "Usage" below)
  • ./cuckoo_simulation/: The code used to simulate behaviour of the cuckoo and commensal cuckoo rules referred to in the work, in order to obtain specific values for the relevant parameters. (Details on running this code in "Usage" below)
  • ./outputs/: The raw outputs of the code in ./dhtpir_simulation/, as obtained when we ran it on our machines. Subdirectories are organized by type of system, then by the number of quorums in the simulation, then by the number of nodes per quorum, then by the number of documents in the simulation, then by seed. At the leaf level, a variety of output files (depending on the system) are present describing different measured values for that given simulation run.
  • ./plots/: The graphs we generated from these outputs, as well as the code to generate these graphs. Many of these graphs are in the work itself, but a few additional graphs are also present in this directory; further detail on graphs in "Graphs" below.

Usage

DHTPIR Simulation

To run an individual run of our simulator, you will need Python3 and Numpy installed. You will also need to be in the ./dhtpir_simulation/ directory. From there, run ./test_harness.py <type> <numDocuments> <sizeOfDocuments> <numGroups> <numNodes> --seed [seed], with appropriate values for each of these variables.

<type> takes one of the following forms, depending on which type of system you intend to simulate:

  • -b: "BaseNode", or a basic DHT system with no additional privacy-preserving or secure behaviour of any kind simulated
  • -r: "RCPNode", which simulates the RCP procedures described by Young et al. on top of a basic DHT system
  • -q: "QPNode", which simulates the QP procedures described by Backes et al. on top of the RCP system (but does not implement any form of oblivious transfer at the final quorum, which returns back the sought document)
  • -l: "QPNode + LastHop", which simulates the same QP procedures as -q, but additionally implements oblivious transfer at the final quorum (which returns back the sought document)
  • -d: "DHTPIRNode", which simulates DHTPIR procedures (that is, QP procedures until the final quorum, and then IT-PIR among the final quorum instead of oblivious transfer)

<numDocuments> describes the number of documents that will be in the system during simulation (as used in the paper, these are intended to simulate erasure-coded chunks of documents, rather than full documents themselves).

<sizeOfDocuments> describes the size of documents in bytes that will be in the system during simulation (again, as used in the paper, these actually set the size of the erasure-coded chunks of documents: we used 512 bytes consistently throughout our simulation). All documents in the system will be randomly generated with exactly the specified number of bytes.

<numGroups> describes the number of quorums in the system as a whole. For BaseNode, this describes the number of total nodes in the DHT, as BaseNode does not use quorums at all.

<numNodes> describes the number of nodes per quorum in the system. For BaseNode, this value is ignored, as BaseNode does not use quorums.

[seed] is an optional parameter, which seeds the randomness used to generate documents. Because document IDs within the system are their hashes (in our case, the SHA256 hash of the file), this impacts the distribution of documents throughout the system; in our simulations, we ran several instances of each type of node with each set of relevant parameters, varying the seed, in a Monte Carlo simulation.

In addition, ./test_harness.py -h displays a help message similar in content to what is discussed in this README.

There are two other programs in the directory, options_setup.c and run_tests.c. options_setup.c generates a config file used by run_tests.c to run several simulation runs simultaneously/in succession. A Makefile is included to compile them (make all compiles both, or make options_setup / make run_tests compiles each individually). No additional installation is necessary beyond gcc (and make). options_setup does not take any arguments, and run_tests takes one argument, the maximum number of processes it may run simulations inside of simultaneously.

Cuckoo Simulation

In order to build this code, you will need Cargo installed. From the ./dhtpir_simulation/ directory, run cargo build --release in order to build the simulation code.

With the code built, run ./target/release/cuckoo_simulation <honest> <malicious> <log2_regions> <k> <nodesPerRegion> <log2_regionsPerQuorum> <iterations> <seed>, with appropriate values for each of these variables.

<honest> describes the number of honest nodes in the system.

<malicious> describes the number of malicious nodes in the system.

<log2_regions> describes log2(the number of regions in the system).

<k> describes k-1, the number of secondary joins in the commensal cuckoo rule before new primary joins are accepted.

<nodesPerRegion> describes the desired average number of nodes in a given region.

<log2_regionsPerQuorum> describes log2(the number of regions per quorum in the system). Typically use 0 for the commensal cuckoo rule.

<iterations> is the number of malicious leaves and joins to simulate

<seed> is a random seed.

There are additional scripts to binary search for the largest number of malicious nodes globally that keeps the maximum fraction of malicious nodes per quorum under 1/4. Use ./find_m <nodesPerRegion> <log2_regions> <log2_regionsPerQuorum> (which itself will call the accompanying script ./run_m <nodesPerRegion> <log2_regions> <log2_regionsPerQuorum> <malicious>).

Graphs

The graphs present in the ./plots/ directory are generated by make_graphs.py, from output in the ./outputs/ directory, using plots.json as a config file for determining text content in the graphs. To run this file for yourself, you will need Python3, Numpy, and Matplotlib installed. With that in place, from the ./plots/ directory, run ./make_graphs.py, and as long as plots.json has not been altered (or has been altered appropriately to generate new graphs), the same graphs will be generated.

The graphs present are organized as follows: <y-axis>-<x-axis>-<which>.pdf.

The <y-axis> value can be one of the following:

  • "latencies": latency per query request (generally in seconds)
  • "num_bytes_recv": number of bytes sent by the client (received by the system) per query request
  • "num_bytes_sent": number of bytes received by the client (sent by the system) per query request
  • "num_bytes_total": sum of "num_bytes_sent" and "num_bytes_recv"
  • "num_pub_bytes_total": number of bytes required for a client to publish a document (note that, as DHTPIR does not do anything novel around publishing a document, merely around retrieving it, this graph does not show much of interest)
  • "throughputs": throughput of the system, in maximum number of lookups possible per second

The <x-axis> value can be one of the following:

  • "num_chunks_per_quorum": Number of chunks per quorum. The <which> associated with these graphs identifies what the number of quorums and nodes per quorum were in the simulation runs that make the selected graph.
  • "num_quorums": Number of quorums. The <which> associated with these graphs identifies what the number of chunks per quorum were in the simulation runs that make the selected graph.