Problem when using ifelse

[HuiZ-W]

I'm trying to implement a priority queue and I'm having problems, I'm trying to use the depth bit of the hash value to select which child node to distribute the element to, but when I complete the insertion using ifelse, my output finds that this one element exists in both child nodes.
Whereas when I don't use ifelse, but fix one byte distribution there is no problem, the element is correctly placed in the corresponding position, could this be due to some data structure effect?

[mkskeller]

Have you tried using if_else? https://mp-spdz.readthedocs.io/en/latest/Compiler.html#Compiler.types.cint.if_else

[HuiZ-W]

Actually, my element_buffer is a list, and the return value of if_else seems to be a cint, and I can't access the list with that cint

[mkskeller]

I meant within the insert_info_buffer call. Anyway, maybe you could post a minimal example that I could run myself?

[HuiZ-W]

I've shrunk it down a bit, but to make sure you're operating the same way I am, I'm still constructing them as a class.

from random import randint
import math
class Node:
    def __init__(self, B=8, height=0):
        self.element_buffer = []  # mem the element (k, p) of the node
        self.delete_buffer = []   # mem the key of the element to be deleted
        self.B = B                # the maximum buffer size of each node
        self.height = height          # the height of the node

    def add_element(self, element):
        self.element_buffer.append(element)

    def add_to_delete_buffer(self, key):
        self.delete_buffer.append(key)

class testTree:
    def __init__(self, n):
        self.B = 8 
        self.height = math.ceil(math.log2(16 * n / self.B)) 
        self.n = n 
        self.root = 0  
        self.tree = [Node(B=self.B, height=math.floor(math.log2(i + 1))) for i in range(2 ** self.height)]  
        self.counter = 0
      
    def insert(self, k, p):
        self.tree[self.root].add_element((k, p, cint(randint(0, 4))))
        self.distribute_element_buffer(0, 1, 2)
    
    def distribute_element_buffer(self, node_index, left_child_index, right_child_index):
        depth = self.tree[node_index].height
        for kp in self.tree[node_index].element_buffer:
            k, p, hash = kp
            go_to_right = ((hash >> depth).bit_and(1))
            @if_e(go_to_right == 1)
            def _():
                self.insert_into_buffer(left_child_index, k, p, hash)
                print_ln('insert_into_buffer left')
                print_ln('index : %s',left_child_index)
            @else_
            def _():
                self.insert_into_buffer(right_child_index, k, p, hash)
                print_ln('insert_into_buffer right')
                print_ln('index : %s',right_child_index)

        self.tree[node_index].element_buffer = []
        for i, node in enumerate(self.tree):
            print_ln("node: %s", i)
            for j in range(0, len(node.element_buffer)):
                print_ln('element_buffer[%s] = (%s, %s)', j, node.element_buffer[j][0].reveal(),node.element_buffer[j][1].reveal())

    def insert_into_buffer(self, index, k, p, hash):
        k, p, hash = k, p, hash
        added = MemValue(0)
        buffer = self.tree[index].element_buffer
        for i, (key, priority, hash) in enumerate(buffer):
            found = key == k
            @if_(found.reveal())
            def _():
                buffer[i] = (key, ternary_operator(p < priority, p, priority), hash)
                added.write(1)
        @if_(added == 0)
        def _():
            self.tree[index].add_element((k, p, hash))

PQ = testTree(3)
PQ.insert(sint(1), sint(9999))

[mkskeller]

You cannot use Python lists in this way because they will be populated at compile-time rather than at run-time. You have to use Array or MultiArray instead.

[HuiZ-W]

I tried replacing the element_buffer in the Node with a MultiArray and calling insert, and the result seems to be the same as the previous problem, so it looks like I have to replace the tree in the priority queue with a MultiArray as well, right? And I wonder under what circumstances is it appropriate to use python's list?

[mkskeller]

Yes. Python lists are not a problem if you don't use them both in- and outside run-time branching constructions like @if_, @for_range etc. On a more general note, MP-SPDZ isn't intended for cleartext computation like this, and there's a secure heap queue in Compiler/dijkstra.py.