123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848 |
- #include <functional>
- #include "bst.hpp"
- #ifdef BST_DEBUG
- void BST::print_oram(MPCTIO &tio, yield_t &yield) {
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- for(size_t i=0;i<R.size();++i) {
- printf("\n%04lx ", i);
- R[i].dump();
- }
- printf("\n");
- }
- #endif
- // Helper function to reconstruct shared RegBS
- bool reconstruct_RegBS(MPCTIO &tio, yield_t &yield, RegBS flag) {
- RegBS reconstructed_flag;
- if (tio.player() < 2) {
- RegBS peer_flag;
- tio.queue_peer(&flag, 1);
- tio.queue_server(&flag, 1);
- yield();
- tio.recv_peer(&peer_flag, 1);
- reconstructed_flag = flag;
- reconstructed_flag ^= peer_flag;
- } else {
- RegBS p0_flag, p1_flag;
- yield();
- tio.recv_p0(&p0_flag, 1);
- tio.recv_p1(&p1_flag, 1);
- reconstructed_flag = p0_flag;
- reconstructed_flag ^= p1_flag;
- }
- return reconstructed_flag.bshare;
- }
- /*
- A function to assign a new random 8-bit key to a node, and resets its
- pointers to zeroes. The node is assigned a new random 64-bit value.
- */
- static void randomize_node(Node &a) {
- a.key.randomize(8);
- a.pointers.set(0);
- a.value.randomize();
- }
- /*
- A function to perform key comparsions for BST traversal.
- Inputs: k1 = key of node in the tree, k2 = insertion/deletion/lookup key.
- Evaluates (k2-k1), and combines the lt and eq flag into one (flag to go
- left), and keeps the gt flag as is (flag to go right) during traversal.
- */
- std::tuple<RegBS, RegBS> compare_keys(MPCTIO &tio, yield_t &yield, RegAS k1,
- RegAS k2) {
- CDPF cdpf = tio.cdpf(yield);
- auto [lt, eq, gt] = cdpf.compare(tio, yield, k2 - k1, tio.aes_ops());
- RegBS lteq = lt^eq;
- return {lteq, gt};
- }
- // Assuming pointer of 64 bits is split as:
- // - 32 bits Left ptr (L)
- // - 32 bits Right ptr (R)
- // The pointers are stored as: (L << 32) | R
- inline RegXS extractLeftPtr(RegXS pointer){
- return ((pointer&(0xFFFFFFFF00000000))>>32);
- }
- inline RegXS extractRightPtr(RegXS pointer){
- return (pointer&(0x00000000FFFFFFFF));
- }
- inline void setLeftPtr(RegXS &pointer, RegXS new_ptr){
- pointer&=(0x00000000FFFFFFFF);
- pointer+=(new_ptr<<32);
- }
- inline void setRightPtr(RegXS &pointer, RegXS new_ptr){
- pointer&=(0xFFFFFFFF00000000);
- pointer+=(new_ptr);
- }
- // Pretty-print a reconstructed BST, rooted at node. is_left_child and
- // is_right_child indicate whether node is a left or right child of its
- // parent. They cannot both be true, but the root of the tree has both
- // of them false.
- void BST::pretty_print(const std::vector<Node> &R, value_t node,
- const std::string &prefix = "", bool is_left_child = false,
- bool is_right_child = false)
- {
- if (node == 0) {
- // NULL pointer
- if (is_left_child) {
- printf("%s\xE2\x95\xA7\n", prefix.c_str()); // ╧
- } else if (is_right_child) {
- printf("%s\xE2\x95\xA4\n", prefix.c_str()); // ╤
- } else {
- printf("%s\xE2\x95\xA2\n", prefix.c_str()); // ╢
- }
- return;
- }
- const Node &n = R[node];
- value_t left_ptr = extractLeftPtr(n.pointers).xshare;
- value_t right_ptr = extractRightPtr(n.pointers).xshare;
- std::string rightprefix(prefix), leftprefix(prefix),
- nodeprefix(prefix);
- if (is_left_child) {
- rightprefix.append("\xE2\x94\x82"); // │
- leftprefix.append(" ");
- nodeprefix.append("\xE2\x94\x94"); // └
- } else if (is_right_child) {
- rightprefix.append(" ");
- leftprefix.append("\xE2\x94\x82"); // │
- nodeprefix.append("\xE2\x94\x8C"); // ┌
- } else {
- rightprefix.append(" ");
- leftprefix.append(" ");
- nodeprefix.append("\xE2\x94\x80"); // ─
- }
- pretty_print(R, right_ptr, rightprefix, false, true);
- printf("%s\xE2\x94\xA4", nodeprefix.c_str()); // ┤
- n.dump();
- printf("\n");
- pretty_print(R, left_ptr, leftprefix, true, false);
- }
- void BST::pretty_print(MPCTIO &tio, yield_t &yield) {
- RegXS peer_root;
- RegXS reconstructed_root = root;
- if (tio.player() == 1) {
- tio.queue_peer(&root, sizeof(root));
- yield();
- } else {
- RegXS peer_root;
- yield();
- if(tio.player()==0) {
- tio.recv_peer(&peer_root, sizeof(peer_root));
- }
- reconstructed_root += peer_root;
- }
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- if(tio.player()==0) {
- pretty_print(R, reconstructed_root.xshare);
- }
- }
- // Check the BST invariant of the tree (that all keys to the left are
- // less than or equal to this key, all keys to the right are strictly
- // greater, and this is true recursively). Returns a
- // tuple<bool,address_t>, where the bool says whether the BST invariant
- // holds, and the address_t is the height of the tree (which will be
- // useful later when we check AVL trees).
- std::tuple<bool, address_t> BST::check_bst(const std::vector<Node> &R,
- value_t node, value_t min_key = 0, value_t max_key = ~0)
- {
- //printf("node = %ld\n", node);
- if (node == 0) {
- return { true, 0 };
- }
- const Node &n = R[node];
- value_t key = n.key.ashare;
- value_t left_ptr = extractLeftPtr(n.pointers).xshare;
- value_t right_ptr = extractRightPtr(n.pointers).xshare;
- auto [leftok, leftheight ] = check_bst(R, left_ptr, min_key, key);
- auto [rightok, rightheight ] = check_bst(R, right_ptr, key+1, max_key);
- address_t height = leftheight;
- if (rightheight > height) {
- height = rightheight;
- }
- height += 1;
- //printf("node = %ld, leftok = %d, rightok = %d\n", node, leftok, rightok);
- return { leftok && rightok && key >= min_key && key <= max_key,
- height };
- }
- void BST::check_bst(MPCTIO &tio, yield_t &yield) {
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- RegXS rec_root = this->root;
- if (tio.player() == 1) {
- tio.queue_peer(&(this->root), sizeof(this->root));
- yield();
- } else {
- RegXS peer_root;
- yield();
- if(tio.player()==0) {
- tio.recv_peer(&peer_root, sizeof(peer_root));
- }
- rec_root+= peer_root;
- }
- if (tio.player() == 0) {
- auto [ ok, height ] = check_bst(R, rec_root.xshare);
- printf("BST structure %s\nBST height = %u\n",
- ok ? "ok" : "NOT OK", height);
- }
- }
- /*
- The recursive insert() call, invoked by the wrapper insert() function.
- Takes as input the pointer to the current node in tree traversal (ptr),
- the key to be inserted (insertion_key), the underlying Duoram as a
- flat (A), and the Time-To_live TTL, and a shared flag (isDummy) which
- tracks if the operation is dummy/real.
- Returns a tuple <ptr, dir> where
- ptr: the pointer to the node where the insertion should happen
- dir: the bit indicating whether the new node should be inserted as the
- left/right child.
- */
- std::tuple<RegXS, RegBS> BST::insert(MPCTIO &tio, yield_t &yield, RegXS ptr,
- RegAS insertion_key, Duoram<Node>::Flat &A, int TTL, RegBS isDummy) {
- if(TTL==0) {
- RegBS zero;
- return {ptr, zero};
- }
- RegBS isNotDummy = isDummy ^ (!tio.player());
- Node cnode = A[ptr];
- // Compare key
- auto [lteq, gt] = compare_keys(tio, yield, cnode.key, insertion_key);
- // Depending on [lteq, gt] select the next ptr/index as
- // upper 32 bits of cnode.pointers if lteq
- // lower 32 bits of cnode.pointers if gt
- RegXS left = extractLeftPtr(cnode.pointers);
- RegXS right = extractRightPtr(cnode.pointers);
- RegXS next_ptr;
- mpc_select(tio, yield, next_ptr, gt, left, right, 32);
- CDPF dpf = tio.cdpf(yield);
- size_t &aes_ops = tio.aes_ops();
- // F_z: Check if this is last node on path
- RegBS F_z = dpf.is_zero(tio, yield, next_ptr, aes_ops);
- RegBS F_i;
- // F_i: If this was last node on path (F_z) && isNotDummy:
- // insert new_node here.
- mpc_and(tio, yield, F_i, (isNotDummy), F_z);
- isDummy^=F_i;
- auto [wptr, direction] = insert(tio, yield, next_ptr, insertion_key, A, TTL-1, isDummy);
- RegXS ret_ptr;
- RegBS ret_direction;
- // If we insert here (F_i), return the ptr to this node as wptr
- // and update direction to the direction taken by compare_keys
- run_coroutines(tio, [&tio, &ret_ptr, F_i, wptr, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_ptr, F_i, wptr, ptr);},
- [&tio, &ret_direction, F_i, direction, gt](yield_t &yield)
- //ret_direction = direction + F_i (direction - gt)
- { mpc_and(tio, yield, ret_direction, F_i, direction^gt);});
- ret_direction^=direction;
- return {ret_ptr, ret_direction};
- }
- /*
- The wrapper insert() operation invoked by the main insert call
- BST::insert(tio, yield, Node& new_node);
- Takes as input the new node (node), the underlying Duoram as a flat (A).
- */
- void BST::insert(MPCTIO &tio, yield_t &yield, const Node &node, Duoram<Node>::Flat &A) {
- bool player0 = tio.player()==0;
- // If there are no items in tree. Make this new item the root.
- if (num_items==0) {
- A[1] = node;
- // Set root to a secret sharing of the constant value 1
- root.set(1*tio.player());
- num_items++;
- //printf("num_items == %ld!\n", num_items);
- return;
- } else {
- // Insert node into next free slot in the ORAM
- int new_id;
- RegXS insert_address;
- int TTL = num_items++;
- bool insertAtEmptyLocation = (empty_locations.size() > 0);
- if(insertAtEmptyLocation) {
- insert_address = empty_locations.back();
- empty_locations.pop_back();
- A[insert_address] = node;
- } else {
- new_id = 1 + num_items;
- A[new_id] = node;
- insert_address.set(new_id * tio.player());
- }
- RegBS isDummy;
- //Do a recursive insert
- auto [wptr, direction] = insert(tio, yield, root, node.key, A, TTL, isDummy);
- //Complete the insertion by reading wptr and updating its pointers
- RegXS pointers = A[wptr].NODE_POINTERS;
- RegXS left_ptr = extractLeftPtr(pointers);
- RegXS right_ptr = extractRightPtr(pointers);
- RegXS new_right_ptr, new_left_ptr;
- RegBS not_direction = direction;
- if (player0) {
- not_direction^=1;
- }
- run_coroutines(tio,
- [&tio, &new_right_ptr, direction, right_ptr, insert_address](yield_t &yield)
- { mpc_select(tio, yield, new_right_ptr, direction, right_ptr, insert_address);},
- [&tio, &new_left_ptr, not_direction, left_ptr, insert_address](yield_t &yield)
- { mpc_select(tio, yield, new_left_ptr, not_direction, left_ptr, insert_address);});
- setLeftPtr(pointers, new_left_ptr);
- setRightPtr(pointers, new_right_ptr);
- A[wptr].NODE_POINTERS = pointers;
- }
- }
- /*
- Insert a new node into the BST.
- Takes as input the new node (node).
- */
- void BST::insert(MPCTIO &tio, yield_t &yield, Node &node) {
- auto A = oram.flat(tio, yield);
- insert(tio, yield, node, A);
- /*
- // To visualize database and tree after each insert:
- auto R = A.reconstruct();
- if (tio.player() == 0) {
- for(size_t i=0;i<R.size();++i) {
- printf("\n%04lx ", i);
- R[i].dump();
- }
- printf("\n");
- }
- pretty_print(R, 1);
- */
- }
- RegBS BST::lookup(MPCTIO &tio, yield_t &yield, RegXS ptr, RegAS key, Duoram<Node>::Flat &A,
- int TTL, RegBS isDummy, Node *ret_node) {
- if(TTL==0) {
- // If we found the key, then isDummy will be true
- return isDummy;
- }
- Node cnode = A[ptr];
- // Compare key
- CDPF cdpf = tio.cdpf(yield);
- auto [lt, eq, gt] = cdpf.compare(tio, yield, key - cnode.key, tio.aes_ops());
- // Depending on [lteq, gt] select the next ptr/index as
- // upper 32 bits of cnode.pointers if lteq
- // lower 32 bits of cnode.pointers if gt
- RegXS left = extractLeftPtr(cnode.pointers);
- RegXS right = extractRightPtr(cnode.pointers);
- RegXS next_ptr;
- RegBS F_found;
- // If we haven't found the key yet, and the lookup matches the current node key,
- // then we found the node to return
- RegBS isNotDummy = isDummy ^ (!tio.player());
- // Note: This logic returns the last matched key and value.
- // Returning the first one incurs an additional round.
- std::vector<coro_t> coroutines;
- coroutines.emplace_back(
- [&tio, &next_ptr, gt, left, right](yield_t &yield)
- { mpc_select(tio, yield, next_ptr, gt, left, right, 32);});
- coroutines.emplace_back(
- [&tio, &F_found, isNotDummy, eq](yield_t &yield)
- { mpc_and(tio, yield, F_found, isNotDummy, eq);});
- coroutines.emplace_back(
- [&tio, &ret_node, eq, cnode](yield_t &yield)
- { mpc_select(tio, yield, ret_node->key, eq, ret_node->key, cnode.key);});
- coroutines.emplace_back(
- [&tio, &ret_node, eq, cnode](yield_t &yield)
- { mpc_select(tio, yield, ret_node->value, eq, ret_node->value, cnode.value);});
- coroutines.emplace_back(
- [&tio, &isDummy, eq](yield_t &yield)
- { mpc_or(tio, yield, isDummy, isDummy, eq);});
- run_coroutines(tio, coroutines);
- #ifdef BST_DEBUG
- size_t ckey = mpc_reconstruct(tio, yield, cnode.key);
- size_t lkey = mpc_reconstruct(tio, yield, key);
- bool rec_lt = mpc_reconstruct(tio, yield, lt);
- bool rec_eq = mpc_reconstruct(tio, yield, eq);
- bool rec_gt = mpc_reconstruct(tio, yield, gt);
- bool rec_found = mpc_reconstruct(tio, yield, isDummy);
- bool rec_f_found = mpc_reconstruct(tio, yield, F_found);
- printf("rec_lt = %d, rec_eq = %d, rec_gt = %d\n", rec_lt, rec_eq, rec_gt);
- printf("rec_isDummy/found = %d ,rec_f_found = %d, cnode.key = %ld, lookup key = %ld\n", rec_found, rec_f_found, ckey, lkey);
- #endif
- RegBS found = lookup(tio, yield, next_ptr, key, A, TTL-1, isDummy, ret_node);
- return found;
- }
- RegBS BST::lookup(MPCTIO &tio, yield_t &yield, RegAS key, Node *ret_node) {
- auto A = oram.flat(tio, yield);
- RegBS isDummy;
- RegBS found = lookup(tio, yield, root, key, A, num_items, isDummy, ret_node);
- /*
- // To visualize database and tree after each lookup:
- auto R = A.reconstruct();
- if (tio.player() == 0) {
- for(size_t i=0;i<R.size();++i) {
- printf("\n%04lx ", i);
- R[i].dump();
- }
- printf("\n");
- }
- pretty_print(R, 1);
- */
- return found;
- }
- /*
- The recursive del() call, invoked by the wrapper del() function.
- Takes as input the pointer to the current node in tree traversal (ptr),
- the key to be deleted (del_key), the underlying Duoram as a
- flat (A), Flags af (already found) and fs (find successor), and the
- Time-To_live TTL. Finally, a return structure ret_struct that tracks
- the location of the successor node and the node to delete, in order
- to perform the actual deletion after the recursive traversal. This
- is required in the case of a deletion that requires a successor swap
- (i.e., when the node to delete has both children).
- Returns success/fail bit.
- */
- bool BST::del(MPCTIO &tio, yield_t &yield, RegXS ptr, RegAS del_key,
- Duoram<Node>::Flat &A, RegBS af, RegBS fs, int TTL,
- del_return &ret_struct) {
- bool player0 = tio.player()==0;
- //printf("TTL = %d\n", TTL);
- if(TTL==0) {
- //Reconstruct and return af
- bool success = reconstruct_RegBS(tio, yield, af);
- //printf("Reconstructed flag = %d\n", success);
- if(player0) {
- ret_struct.F_r^=1;
- }
- return success;
- } else {
- // s1: shares of 1 bit, s0: shares of 0 bit
- RegBS s1, s0;
- s1.set(tio.player()==1);
- Node node = A[ptr];
- RegXS left = extractLeftPtr(node.pointers);
- RegXS right = extractRightPtr(node.pointers);
- CDPF cdpf = tio.cdpf(yield);
- size_t &aes_ops = tio.aes_ops();
- RegBS l0, r0, lt, eq, gt;
- // l0: Is left child 0
- // r0: Is right child 0
- run_coroutines(tio,
- [&tio, &l0, left, &aes_ops, &cdpf](yield_t &yield)
- { l0 = cdpf.is_zero(tio, yield, left, aes_ops);},
- [&tio, &r0, right, &aes_ops, &cdpf](yield_t &yield)
- { r0 = cdpf.is_zero(tio, yield, right, aes_ops);},
- [&tio, <, &eq, >, del_key, node, &cdpf](yield_t &yield)
- // Compare Key
- { auto [a, b, c] = cdpf.compare(tio, yield, del_key - node.key, tio.aes_ops());
- lt = a; eq = b; gt = c;});
- /*
- // Reconstruct and Debug Block 0
- bool lt_rec, eq_rec, gt_rec;
- lt_rec = mpc_reconstruct(tio, yield, lt);
- eq_rec = mpc_reconstruct(tio, yield, eq);
- gt_rec = mpc_reconstruct(tio, yield, gt);
- size_t del_key_rec, node_key_rec;
- del_key_rec = mpc_reconstruct(tio, yield, del_key);
- node_key_rec = mpc_reconstruct(tio, yield, node.key);
- printf("node.key = %ld, del_key= %ld\n", node_key_rec, del_key_rec);
- printf("cdpf.compare results: lt = %d, eq = %d, gt = %d\n", lt_rec, eq_rec, gt_rec);
- */
- // c is the direction bit for next_ptr
- // (c=0: go left or c=1: go right)
- RegBS c = gt;
- // lf = local found. We found the key to delete in this level.
- RegBS lf = eq;
- // F_{X}: Flags that indicate the number of children this node has
- // F_0: no children, F_1: one child, F_2: both children
- RegBS F_0, F_1, F_2;
- // F_1 = l0 \xor r0
- F_1 = l0 ^ r0;
- // We set next ptr based on c, but we need to handle three
- // edge cases where we do not go by just the comparison result
- RegXS next_ptr;
- RegBS c_prime;
- // Case 1: found the node here (lf): we traverse down the lone child path.
- // or we are finding successor (fs) and there is no left child.
- RegBS F_c1, F_c2, F_c3, F_c4;
- // Case 1: lf & F_1
- run_coroutines(tio,
- [&tio, &F_c1, lf, F_1](yield_t &yield)
- { mpc_and(tio, yield, F_c1, lf, F_1);},
- [&tio, &F_0, l0, r0] (yield_t &yield)
- // F_0 = l0 & r0
- { mpc_and(tio, yield, F_0, l0, r0);});
- // F_2 = !(F_0 + F_1) (Only 1 of F_0, F_1, and F_2 can be true)
- F_2 = F_0 ^ F_1;
- if(player0)
- F_2^=1;
- /*
- // Reconstruct and Debug Block 1
- bool F_0_rec, F_1_rec, F_2_rec, c_prime_rec;
- F_0_rec = mpc_reconstruct(tio, yield, F_0);
- F_1_rec = mpc_reconstruct(tio, yield, F_1);
- F_2_rec = mpc_reconstruct(tio, yield, F_2);
- c_prime_rec = mpc_reconstruct(tio, yield, c_prime);
- printf("F_0 = %d, F_1 = %d, F_2 = %d, c_prime = %d\n", F_0_rec, F_1_rec, F_2_rec, c_prime_rec);
- */
- run_coroutines(tio,
- [&tio, &c_prime, F_c1, c, l0](yield_t &yield)
- // Set c_prime for Case 1
- { mpc_select(tio, yield, c_prime, F_c1, c, l0);},
- [&tio, &F_c2, lf, F_2](yield_t &yield)
- // Case 2: found the node here (lf) and node has both children (F_2)
- // In find successor case, so find inorder successor
- // (Go right and then find leftmost child.)
- { mpc_and(tio, yield, F_c2, lf, F_2);});
- /*
- // Reconstruct and Debug Block 2
- bool F_c2_rec, s1_rec;
- F_c2_rec = mpc_reconstruct(tio, yield, F_c2);
- s1_rec = mpc_reconstruct(tio, yield, s1);
- c_prime_rec = mpc_reconstruct(tio, yield, c_prime);
- printf("c_prime = %d, F_c2 = %d, s1 = %d\n", c_prime_rec, F_c2_rec, s1_rec);
- */
- run_coroutines(tio,
- [&tio, &c_prime, F_c2, s1](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c2, c_prime, s1);},
- [&tio, &F_c3, fs, F_2](yield_t &yield)
- // Case 3: finding successor (fs) and node has both children (F_2)
- // Go left.
- { mpc_and(tio, yield, F_c3, fs, F_2);});
- run_coroutines(tio,
- [&tio, &c_prime, F_c3, s0](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c3, c_prime, s0);},
- // Case 4: finding successor (fs) and node has no more left children (l0)
- // This is the successor node then.
- // Go right (since no more left)
- [&tio, &F_c4, fs, l0] (yield_t &yield)
- { mpc_and(tio, yield, F_c4, fs, l0);});
- mpc_select(tio, yield, c_prime, F_c4, c_prime, l0);
- RegBS af_prime, fs_prime;
- run_coroutines(tio,
- [&tio, &next_ptr, c_prime, left, right](yield_t &yield)
- // Set next_ptr
- { mpc_select(tio, yield, next_ptr, c_prime, left, right, 32);},
- [&tio, &af_prime, af, lf](yield_t &yield)
- { mpc_or(tio, yield, af_prime, af, lf);},
- [&tio, &fs_prime, fs, F_c2](yield_t &yield)
- // If in Case 2, set fs. We are now finding successor
- { mpc_or(tio, yield, fs_prime, fs, F_c2);});
- // If in Case 4. Successor found here already. Toggle fs off
- fs_prime=fs_prime^F_c4;
- bool key_found = del(tio, yield, next_ptr, del_key, A, af_prime, fs_prime, TTL-1, ret_struct);
- // If we didn't find the key, we can end here.
- if(!key_found) {
- return 0;
- }
- //printf("TTL = %d\n", TTL);
- RegBS F_rs_right, F_rs_left, not_c_prime=c_prime;
- if(player0) {
- not_c_prime^=1;
- }
- // Flag here should be direction (c_prime) and F_r i.e. we need to swap return ptr in,
- // F_r needs to be returned in ret_struct
- run_coroutines(tio,
- [&tio, &F_rs_right, c_prime, ret_struct](yield_t &yield)
- { mpc_and(tio, yield, F_rs_right, c_prime, ret_struct.F_r);},
- [&tio, &F_rs_left, not_c_prime, left, ret_struct](yield_t &yield)
- { mpc_and(tio, yield, F_rs_left, not_c_prime, ret_struct.F_r);});
- run_coroutines(tio,
- [&tio, &right, F_rs_right, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, right, F_rs_right, right, ret_struct.ret_ptr);},
- [&tio, &left, F_rs_left, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, left, F_rs_left, left, ret_struct.ret_ptr);});
- /*
- // Reconstruct and Debug Block 3
- bool F_rs_rec, F_ls_rec;
- size_t ret_ptr_rec;
- F_rs_rec = mpc_reconstruct(tio, yield, F_rs);
- F_ls_rec = mpc_reconstruct(tio, yield, F_rs);
- ret_ptr_rec = mpc_reconstruct(tio, yield, ret_struct.ret_ptr);
- printf("F_rs_rec = %d, F_ls_rec = %d, ret_ptr_rec = %ld\n", F_rs_rec, F_ls_rec, ret_ptr_rec);
- */
- RegXS new_ptr;
- setLeftPtr(new_ptr, left);
- setRightPtr(new_ptr, right);
- A[ptr].NODE_POINTERS = new_ptr;
- // Update the return structure
- RegBS F_nd, F_ns, F_r, not_af = af, not_F_2 = F_2;
- if(player0) {
- not_af^=1;
- not_F_2^=1;
- }
- // F_ns = fs & l0
- // Finding successor flag & no more left child = F_c4
- F_ns = F_c4;
- run_coroutines(tio,
- [&tio, &ret_struct, F_c2](yield_t &yield)
- { mpc_or(tio, yield, ret_struct.F_ss, ret_struct.F_ss, F_c2);},
- [&tio, &F_nd, lf, not_af](yield_t &yield)
- { mpc_and(tio, yield, F_nd, lf, not_af);});
- // F_r = F_d.(!F_2)
- // If we have to delete here, and it doesn't have two children we have to
- // update child pointer in parent with the returned pointer
- mpc_and(tio, yield, F_r, F_nd, not_F_2);
- mpc_or(tio, yield, F_r, F_r, F_ns);
- ret_struct.F_r = F_r;
- run_coroutines(tio,
- [&tio, &ret_struct, F_nd, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.N_d, F_nd, ret_struct.N_d, ptr);},
- [&tio, &ret_struct, F_ns, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.N_s, F_ns, ret_struct.N_s, ptr);},
- [&tio, &ret_struct, F_r, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.ret_ptr, F_r, ptr, ret_struct.ret_ptr);});
- //We don't empty the key and value of the node with del_key in the ORAM
- return 1;
- }
- }
- /*
- The main del() function.
- Trying to delete an item that does not exist in the tree will result in
- an explicit (non-oblivious) failure.
- Takes as input the key to delete (del_key).
- Returns success/fail bit.
- */
- bool BST::del(MPCTIO &tio, yield_t &yield, RegAS del_key) {
- if(num_items==0)
- return 0;
- if(num_items==1) {
- //Delete root
- auto A = oram.flat(tio, yield);
- Node zero;
- empty_locations.emplace_back(root);
- A[root] = zero;
- num_items--;
- return 1;
- } else {
- int TTL = num_items;
- // Flags for already found (af) item to delete and find successor (fs)
- // if this deletion requires a successor swap
- RegBS af;
- RegBS fs;
- del_return ret_struct;
- auto A = oram.flat(tio, yield);
- int success = del(tio, yield, root, del_key, A, af, fs, TTL, ret_struct);
- if(!success){
- return 0;
- }
- else{
- num_items--;
- /*
- printf("In delete's swap portion\n");
- Node del_node = A.reconstruct(A[ret_struct.N_d]);
- Node suc_node = A.reconstruct(A[ret_struct.N_s]);
- printf("del_node key = %ld, suc_node key = %ld\n",
- del_node.key.ashare, suc_node.key.ashare);
- printf("flag_s = %d\n", ret_struct.F_ss.bshare);
- */
- Node del_node = A[ret_struct.N_d];
- Node suc_node = A[ret_struct.N_s];
- RegAS zero_as; RegXS zero_xs;
- RegXS empty_loc, temp_root = root;
- run_coroutines(tio,
- [&tio, &temp_root, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, temp_root, ret_struct.F_r, temp_root, ret_struct.ret_ptr);},
- [&tio, &del_node, ret_struct, suc_node](yield_t &yield)
- { mpc_select(tio, yield, del_node.key, ret_struct.F_ss, del_node.key, suc_node.key);},
- [&tio, &del_node, ret_struct, suc_node](yield_t & yield)
- { mpc_select(tio, yield, del_node.value, ret_struct.F_ss, del_node.value, suc_node.value);},
- [&tio, &empty_loc, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, empty_loc, ret_struct.F_ss, ret_struct.N_d, ret_struct.N_s);});
- root = temp_root;
- run_coroutines(tio,
- [&tio, &A, ret_struct, del_node](yield_t &yield)
- { auto acont = A.context(yield);
- acont[ret_struct.N_d].NODE_KEY = del_node.key;},
- [&tio, &A, ret_struct, del_node](yield_t &yield)
- { auto acont = A.context(yield);
- acont[ret_struct.N_d].NODE_VALUE = del_node.value;},
- [&tio, &A, ret_struct, zero_as](yield_t &yield)
- { auto acont = A.context(yield);
- acont[ret_struct.N_s].NODE_KEY = zero_as;},
- [&tio, &A, ret_struct, zero_xs](yield_t &yield)
- { auto acont = A.context(yield);
- acont[ret_struct.N_s].NODE_VALUE = zero_xs;});
- //Add deleted (empty) location into the empty_locations vector for reuse in next insert()
- empty_locations.emplace_back(empty_loc);
- }
- return 1;
- }
- }
- // Now we use the node in various ways. This function is called by
- // online.cpp.
- void bst(MPCIO &mpcio,
- const PRACOptions &opts, char **args)
- {
- nbits_t depth=4;
- if (*args) {
- depth = atoi(*args);
- ++args;
- }
- MPCTIO tio(mpcio, 0, opts.num_cpu_threads);
- run_coroutines(tio, [&tio, depth] (yield_t &yield) {
- size_t size = size_t(1)<<depth;
- BST tree(tio.player(), size);
- int insert_array[] = {10, 10, 13, 11, 14, 8, 15, 20, 17, 19, 7, 12};
- //int insert_array[] = {1, 2, 3, 4, 5, 6};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- }
- tree.pretty_print(tio, yield);
- RegAS del_key;
- printf("\n\nDelete %x\n", 20);
- del_key.set(20 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nDelete %x\n", 10);
- del_key.set(10 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nDelete %x\n", 7);
- del_key.set(7 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nDelete %x\n", 17);
- del_key.set(17 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nDelete %x\n", 15);
- del_key.set(15 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nDelete %x\n", 5);
- del_key.set(5 * tio.player());
- tree.del(tio, yield, del_key);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nInsert %x\n", 14);
- randomize_node(node);
- node.key.set(14 * tio.player());
- tree.insert(tio, yield, node);
- tree.pretty_print(tio, yield);
- tree.check_bst(tio, yield);
- printf("\n\nLookup %x\n", 8);
- randomize_node(node);
- RegAS lookup_key;
- RegBS found;
- bool rec_found;
- lookup_key.set(8 * tio.player());
- found = tree.lookup(tio, yield, lookup_key, &node);
- rec_found = mpc_reconstruct(tio, yield, found);
- tree.pretty_print(tio, yield);
- if(tio.player()!=2) {
- if(rec_found) {
- printf("Lookup Success\n");
- size_t value = mpc_reconstruct(tio, yield, node.value);
- printf("value = %lx\n", value);
- } else {
- printf("Lookup Failed\n");
- }
- }
- });
- }
|