duoram.cpp 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437
  1. #include <type_traits> // std::is_same<>
  2. #include <limits> // std::numeric_limits<>
  3. #include <climits> // CHAR_BIT
  4. #include <cmath> // std::log2, std::ceil, std::floor
  5. #include <stdexcept> // std::runtime_error
  6. #include <array> // std::array<>
  7. #include <iostream> // std::istream and std::ostream
  8. #include <vector> // std::vector<>
  9. #include <memory> // std::shared_ptr<>
  10. #include <utility> // std::move
  11. #include <algorithm> // std::copy
  12. #include <cstring> // std::memcpy
  13. #include <bsd/stdlib.h> // arc4random_buf
  14. #include <x86intrin.h> // SSE and AVX intrinsics
  15. #include <chrono>
  16. #include <thread>
  17. #include <deque>
  18. #include <../boost/asio.hpp>
  19. using boost::asio::ip::tcp;
  20. using namespace std::chrono;
  21. using namespace std;
  22. using socket_t = boost::asio::ip::tcp::socket;
  23. size_t communication_cost_dep_read = 0;
  24. size_t communication_cost_write = 0;
  25. #include "prg.h"
  26. #include "prg_aes_impl.h"
  27. #include "block.h"
  28. #include "duoram-utils.h"
  29. #include "readvectors.h"
  30. #include "duoram-read.h"
  31. #include "duoram-refresh.h"
  32. #include "duoram-write.h"
  33. double dependent_read_time = 0.0;
  34. double write_time = 0.0;
  35. void accept_conncections_from_Pb(boost::asio::io_context&io_context, std::vector<socket_t>& sockets_, int port, size_t j)
  36. {
  37. tcp::acceptor acceptor_a(io_context, tcp::endpoint(tcp::v4(), port));
  38. tcp::socket sb_a(acceptor_a.accept());
  39. sockets_[j] = std::move(sb_a);
  40. }
  41. int main(const int argc, const char * argv[])
  42. {
  43. size_t expo = atoi(argv[3]);
  44. size_t db_nitems = 1ULL << expo;
  45. size_t number_of_writes = atoi(argv[4]);
  46. size_t number_of_ind_reads = atoi(argv[5]);
  47. size_t number_of_dep_reads = atoi(argv[6]);
  48. size_t number_of_accesses = atoi(argv[7]);
  49. reading_temp = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  50. DB = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  51. updated_DB = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  52. blinded_DB = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  53. blinded_DB_recv = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  54. updated_blinded_DB_recv = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  55. b = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  56. c = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  57. d = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  58. reading_b = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  59. reading_c = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  60. reading_d = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  61. writing_b = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  62. writing_c = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  63. writing_d = (int8_t *) malloc(db_nitems * sizeof(int8_t));
  64. size_t * rotate_by_ = new size_t[number_of_writes];
  65. boost::asio::io_context io_context;
  66. tcp::resolver resolver(io_context);
  67. std::string addr = "127.0.0.1";
  68. const std::string host1 = (argc < 2) ? "127.0.0.1" : argv[1];
  69. const std::string host2 = (argc < 3) ? "127.0.0.1" : argv[2];
  70. bool party;
  71. const size_t number_of_sockets = 40;
  72. std::vector<socket_t> sockets_;
  73. for(size_t j = 0; j < number_of_sockets + 1; ++j)
  74. {
  75. tcp::socket emptysocket(io_context);
  76. sockets_.emplace_back(std::move(emptysocket));
  77. }
  78. sockets_.reserve(number_of_sockets + 1);
  79. //printf("number_of_sockets = %zu\n", number_of_sockets);
  80. std::vector<socket_t> sockets_2;
  81. std::vector<int> ports;
  82. for(size_t j = 0; j < number_of_sockets; ++j)
  83. {
  84. int port = 6000;
  85. ports.push_back(port + j);
  86. }
  87. std::vector<int> ports2_0;
  88. for(size_t j = 0; j < number_of_sockets; ++j)
  89. {
  90. int port = 8000;
  91. ports2_0.push_back(port + j);
  92. }
  93. std::vector<int> ports2_1;
  94. for(size_t j = 0; j < number_of_sockets; ++j)
  95. {
  96. int port = 9000;
  97. ports2_1.push_back(port + j);
  98. }
  99. #if (PARTY == 0)
  100. party = false;
  101. #ifdef ThreeParty
  102. for(size_t j = 0; j < number_of_sockets; ++j)
  103. {
  104. tcp::socket sb_a(io_context);
  105. boost::asio::connect(sb_a, resolver.resolve({host2, std::to_string(ports2_0[j])}));
  106. sockets_2.emplace_back(std::move(sb_a));
  107. }
  108. #endif
  109. for(size_t j = 0; j < number_of_sockets; ++j)
  110. {
  111. tcp::socket sb_a(io_context);
  112. boost::asio::connect(sb_a, resolver.resolve({host1, std::to_string(ports[j])}));
  113. sockets_[j] = std::move(sb_a);
  114. }
  115. #else
  116. party = true;
  117. #ifdef ThreeParty
  118. for(size_t j = 0; j < number_of_sockets; ++j)
  119. {
  120. tcp::socket sb_a(io_context);
  121. boost::asio::connect(sb_a, resolver.resolve({host2, std::to_string(ports2_1[j])}));
  122. sockets_2.emplace_back(std::move(sb_a));
  123. }
  124. #endif
  125. boost::asio::thread_pool pool2(number_of_sockets);
  126. for(size_t j = 0; j < number_of_sockets; ++j)
  127. {
  128. boost::asio::post(pool2, std::bind(accept_conncections_from_Pb, std::ref(io_context), std::ref(sockets_), ports[j], j));
  129. }
  130. pool2.join();
  131. #endif
  132. generate_random_distinguished_points(party);
  133. AES_KEY aeskey;
  134. blinds = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  135. updated_blinds = (DB_t *) std::aligned_alloc(sizeof(__m256i), db_nitems * sizeof(DB_t));
  136. size_t * where_to_write = new size_t[number_of_writes];
  137. size_t * where_to_read_dependent = new size_t[number_of_dep_reads];
  138. size_t * where_to_read_independent = new size_t[number_of_ind_reads];
  139. auto start_total = std::chrono::steady_clock::now();
  140. setup(DB, updated_DB, blinded_DB_recv, blinds, updated_blinds, updated_blinded_DB_recv, db_nitems, party);
  141. for(size_t i = 0; i < number_of_accesses; ++i)
  142. {
  143. for(size_t j = 0; j < number_of_writes; ++j)
  144. {
  145. where_to_write[j] = j + 4;
  146. }
  147. for(size_t j = 0; j < number_of_dep_reads; ++j)
  148. {
  149. where_to_read_dependent[j] = j + 4;
  150. }
  151. for(size_t j = 0; j < number_of_ind_reads; ++j)
  152. {
  153. where_to_read_independent[j] = j + 4;
  154. }
  155. for(size_t j = 0; j < db_nitems; ++j)
  156. {
  157. blinds[j] = 0;
  158. updated_blinds[j] = blinds[j];
  159. updated_blinded_DB_recv[j] = blinded_DB_recv[j];
  160. }
  161. // arc4random_buf(&ri, sizeof(ri));
  162. // ri = ri % db_nitems;
  163. // boost::asio::write(sockets_[0], boost::asio::buffer(&ri, sizeof(ri)));
  164. // boost::asio::read(sockets_[0], boost::asio::buffer(&ri_recv, sizeof(ri_recv)));
  165. // if(party) ri = 2 - ri_recv;
  166. int64_t ri;
  167. read_rand_indx(party, ri);
  168. #ifdef DEBUG
  169. int64_t ri_recv;
  170. boost::asio::write(sockets_[0], boost::asio::buffer(&ri, sizeof(ri)));
  171. boost::asio::read(sockets_[0], boost::asio::buffer(&ri_recv, sizeof(ri_recv)));
  172. ri_recv = ri_recv + ri;
  173. std::cout << "ri_recv = " << ri_recv % db_nitems << std::endl;
  174. #endif
  175. #ifdef VERBOSE
  176. boost::asio::write(sockets_[0], boost::asio::buffer(&ri, sizeof(ri)));
  177. boost::asio::read(sockets_[0], boost::asio::buffer(&ri_recv, sizeof(ri_recv)));
  178. int64_t ri_reconstruction = ri + ri_recv;
  179. std::cout << "ri_reconstruction = " << ri_reconstruction << std::endl;
  180. #endif
  181. DuORAM_Write * WritePb_ = new DuORAM_Write[number_of_writes];
  182. DuORAM_Write * WritePb_recv = new DuORAM_Write[number_of_writes];
  183. #ifdef ThreeParty
  184. DB_t * read_out = new DB_t[number_of_writes];
  185. DB_t * Gamma = new DB_t[number_of_writes];
  186. #endif
  187. DB_t * CW = new DB_t[number_of_writes];
  188. DB_t * update_message = new DB_t[number_of_writes];
  189. auto start_writes = std::chrono::steady_clock::now();
  190. #ifdef ThreeParty
  191. for(size_t w = 0; w < number_of_writes; ++w)
  192. {
  193. DB_t FCW_read = 0;
  194. /*The definition of read_final_correction_word appears in duoram-utils.h*/
  195. read_final_correction_word(party, FCW_read);
  196. #ifdef VERBOSE
  197. std::cout << "FCW_read (from) = " << FCW_read << std::endl;
  198. #endif
  199. DB_t alpha0 = -FCW_read;
  200. WritePb_[w].shift = where_to_write[w] -ri;
  201. WritePb_[w].CW = distinguised_value[0];
  202. boost::asio::write(sockets_2[0], boost::asio::buffer(&WritePb_[w], sizeof(DuORAM_Write)));
  203. communication_cost_write += sizeof(DuORAM_Write);
  204. read(sockets_2[1], boost::asio::buffer(&Gamma[w], sizeof(DB_t)));
  205. boost::asio::write(sockets_[0], boost::asio::buffer(&WritePb_[w], sizeof(DuORAM_Write)));
  206. communication_cost_write += sizeof(DuORAM_Write);
  207. boost::asio::read(sockets_[0], boost::asio::buffer(&WritePb_recv[w], sizeof(DuORAM_Write)));
  208. /*The definition of read_flags_for_writing appears in duoram-utils.h*/
  209. read_flags_for_writing(party, db_nitems);
  210. rotate_by_[w] = WritePb_[w].shift + WritePb_recv[w].shift;
  211. #ifdef VERBOSE
  212. std::cout << "print database (prints the non-zero database entries): " << std::endl;
  213. /* The definition of reconstruct_database appears in duoram-utils.h */
  214. reconstruct_database(sockets_[0], DB, db_nitems);
  215. #endif
  216. for(size_t j = 0; j < db_nitems; ++j) reading_temp[j] = DB[j] + updated_blinded_DB_recv[j];
  217. /*The definition of dot_product_with_bool appears in duoram-write.h*/
  218. if(!party) read_out[w] = dot_product_with_bool(reading_temp, writing_b, db_nitems, rotate_by_[w]) +
  219. dot_product_with_bool(updated_blinds, writing_b, db_nitems, rotate_by_[w]) -
  220. dot_product_with_bool(updated_blinds, writing_c, db_nitems, rotate_by_[w]) + Gamma[w];
  221. if(party) read_out[w] = dot_product_with_bool(reading_temp, writing_c, db_nitems, rotate_by_[w]) +
  222. dot_product_with_bool(updated_blinds, writing_c, db_nitems, rotate_by_[w]) -
  223. dot_product_with_bool(updated_blinds, writing_d, db_nitems, rotate_by_[w]) + Gamma[w];
  224. #ifdef VERBOSE
  225. std::cout << "read_out[" << w << "] = " << read_out[w] << std::endl;
  226. #endif
  227. #ifdef VERBOSE
  228. std::cout << "reconstructing the output: " << print_reconstruction(sockets_[0], read_out[w]) << "\n";
  229. #endif
  230. distinguised_value[0] = 80 * (1 + w);
  231. update_message[w] = distinguised_value[0] - read_out[w] + alpha0;
  232. #ifdef VERBOSE
  233. std::cout << "The updated message shares is = " << update_message[w] << std::endl;
  234. #endif
  235. boost::asio::write(sockets_2[2], boost::asio::buffer(&update_message[w], sizeof(DB_t)));
  236. boost::asio::write(sockets_[2], boost::asio::buffer(&update_message[w], sizeof(DB_t)));
  237. communication_cost_write += 2 * sizeof(DB_t);
  238. boost::asio::read(sockets_[2], boost::asio::buffer(&CW[w], sizeof(DB_t)));
  239. CW[w] = CW[w] + update_message[w];
  240. #ifdef VERBOSE
  241. std::cout << "cw = " << CW[w] << std::endl;
  242. #endif
  243. }
  244. #else // 2-party case
  245. for(size_t w = 0; w < number_of_writes; ++w)
  246. {
  247. WritePb_[w].shift = where_to_write[w] -ri;
  248. WritePb_[w].CW = distinguised_value[0];
  249. boost::asio::write(sockets_[0], boost::asio::buffer(&WritePb_[w], sizeof(DuORAM_Write)));
  250. communication_cost_write += sizeof(DuORAM_Write);
  251. boost::asio::read(sockets_[0], boost::asio::buffer(&WritePb_recv[w], sizeof(DuORAM_Write)));
  252. rotate_by_[w] = WritePb_[w].shift + WritePb_recv[w].shift;
  253. }
  254. #endif
  255. delete[] WritePb_;
  256. delete[] WritePb_recv;
  257. for(size_t w = 0; w < number_of_writes; ++w)
  258. {
  259. /*The definition of DuoramUpdate appears in duoram-write.h*/
  260. DuoramUpdate(party, db_nitems, rotate_by_[w], DB, updated_DB, writing_b, b, CW[w], update_message[w], writing_c, writing_d, c, d);
  261. #ifdef DEBUG
  262. #ifdef ThreeParty
  263. /*The definition debug_ appears in duoram-utils.h*/
  264. debug_(sockets_2[0], sockets_[0], db_nitems);
  265. #endif
  266. #endif
  267. }
  268. delete[] rotate_by_;
  269. delete[] CW;
  270. delete[] update_message;
  271. auto end_writes = std::chrono::steady_clock::now();
  272. std::chrono::duration<double> elapsed_seconds_writes = end_writes - start_writes;
  273. write_time = elapsed_seconds_writes.count();
  274. // printf("elapsed_seconds_writes = %f\n",elapsed_seconds_writes.count());
  275. // std::cout << "communication_cost_writes = " << communication_cost_write << std::endl;
  276. #ifdef VERBOSE
  277. std::cout << "Reconstructing the database after doing " << number_of_writes << " writes " << std::endl;
  278. reconstruct_database(sockets_[0], DB, db_nitems);
  279. #endif
  280. // WRITES END.
  281. #ifdef ThreeParty
  282. #ifdef VERBOSE
  283. std::cout << std::endl << std::endl << "============== WRITES END ==============" << std::endl << std::endl;
  284. #endif
  285. auto start_ind_reads = std::chrono::steady_clock::now();
  286. size_t * WritePb_ind_reads = new size_t[number_of_ind_reads];
  287. size_t * WritePb_ind_reads_recv = new size_t[number_of_ind_reads];
  288. size_t * rotate = new size_t[number_of_ind_reads];
  289. for(size_t r = 0; r < number_of_ind_reads; ++r) WritePb_ind_reads[r] = where_to_read_independent[r] -ri;
  290. boost::asio::write(sockets_2[3], boost::asio::buffer(WritePb_ind_reads, number_of_ind_reads * sizeof(size_t)));
  291. boost::asio::write(sockets_[3], boost::asio::buffer(WritePb_ind_reads, number_of_ind_reads * sizeof(size_t)));
  292. boost::asio::read(sockets_[3], boost::asio::buffer(WritePb_ind_reads_recv, number_of_ind_reads * sizeof(size_t)));
  293. DB_t * Gamma_reads = new DB_t[number_of_ind_reads];
  294. boost::asio::read(sockets_2[4], boost::asio::buffer(Gamma_reads, number_of_ind_reads * sizeof(DB_t)));
  295. for(size_t j = 0; j < number_of_ind_reads; ++j)
  296. {
  297. rotate[j] = WritePb_ind_reads[j] + WritePb_ind_reads_recv[j];
  298. }
  299. DB_t * read_out_independent_reads = new DB_t[number_of_ind_reads];
  300. for(size_t r = 0; r < number_of_ind_reads; ++r)
  301. {
  302. #ifdef VERBOSE
  303. std::cout << "rotate[r]" << rotate[r] << std::endl;
  304. std::cout << "Gamma_reads[r] = " << Gamma_reads[r] << std::endl;
  305. #endif
  306. read_out_independent_reads[r] = DuoramIndependentRead(party, db_nitems, ri, Gamma_reads, rotate, r);
  307. #ifdef VERBOSE
  308. std::cout << "---> [duoram independent reads] " << print_reconstruction(sockets_[0], read_out_independent_reads[r]) << std::endl;
  309. #endif
  310. }
  311. auto end_ind_reads = std::chrono::steady_clock::now();
  312. std::chrono::duration<double> elapsed_seconds_ind_reads = end_ind_reads - start_ind_reads;
  313. //printf("elapsed_seconds_ind_reads = %f\n",elapsed_seconds_ind_reads.count());
  314. #ifdef VERBOSE
  315. std::cout << std::endl << std::endl << "============== INDEPENDENT READS END ==============" << std::endl << std::endl;
  316. #endif
  317. auto start_dep_reads = std::chrono::steady_clock::now();
  318. #ifdef VERBOSE
  319. std::cout << std::endl << std::endl << "============== DEPENDENT READS START ==============" << std::endl << std::endl;
  320. #endif
  321. DB_t * read_out_dependent_reads = new DB_t[number_of_dep_reads];
  322. for(size_t r = 0; r < number_of_dep_reads; ++r)
  323. {
  324. read_out_dependent_reads[r] = DuoramRead(party, db_nitems, ri, where_to_read_dependent[r], sockets_2[5], sockets_2[6], sockets_[5]);
  325. communication_cost_dep_read += sizeof(DB_t);
  326. communication_cost_dep_read += sizeof(DB_t);
  327. #ifdef VERBOSE
  328. std::cout << "dependent read (share) " << r << " -> " << read_out_dependent_reads[r] << std::endl;
  329. std::cout << print_reconstruction(sockets_[0], read_out_dependent_reads[r]) << std::endl;
  330. #endif
  331. }
  332. auto end_dep_reads = std::chrono::steady_clock::now();
  333. std::chrono::duration<double> elapsed_seconds_dep_reads = end_dep_reads - start_dep_reads;
  334. dependent_read_time = elapsed_seconds_dep_reads.count();
  335. // printf("elapsed_seconds_dep_reads = %f\n",elapsed_seconds_dep_reads.count());
  336. // std::cout << "communication_cost_dep_read = " << communication_cost_dep_read << std::endl;
  337. #ifdef VERBOSE
  338. std::cout << std::endl << std::endl << "============== DEPENDENT READS END ==============" << std::endl << std::endl;
  339. #endif
  340. #endif
  341. }
  342. auto end_total = std::chrono::steady_clock::now();
  343. std::chrono::duration<double> elapsed_seconds_total = end_total - start_total;
  344. //printf("elapsed_seconds_total = %f\n",elapsed_seconds_total.count());
  345. std::cout << "write_time = " << write_time << std::endl;
  346. std::cout << "communication_cost_writes = " << communication_cost_write << " bytes" << std::endl;
  347. #ifdef ThreeParty
  348. std::cout << "dependent_read_time = " << dependent_read_time << std::endl;
  349. std::cout << "communication_cost_dep_read = " << communication_cost_dep_read << " bytes" << std::endl;
  350. std::cout << "interleaved_time = " << dependent_read_time + write_time << std::endl;
  351. std::cout << "communication_cost_interleaved = " << (communication_cost_dep_read + communication_cost_write) << " bytes" << std::endl;
  352. #endif
  353. free(reading_temp);
  354. return 0;
  355. }