mirror of
https://github.com/data61/MP-SPDZ.git
synced 2026-01-09 21:48:11 -05:00
314 lines
9.8 KiB
Plaintext
314 lines
9.8 KiB
Plaintext
from Compiler import library as lib, oram, path_oram
|
|
from Compiler.dijkstra import HeapQ
|
|
from Compiler.path_oblivious_heap import (
|
|
POHToHeapQAdapter,
|
|
POHVariant,
|
|
UniquePOHToHeapQAdapter,
|
|
path_oblivious_sort,
|
|
)
|
|
from Compiler.types import Array, sint
|
|
from Compiler.util import log2
|
|
|
|
DEBUG = True
|
|
|
|
from Compiler import path_oblivious_heap
|
|
|
|
path_oblivious_heap.DEBUG = False
|
|
|
|
|
|
def noop(*args, **kwargs):
|
|
pass
|
|
|
|
|
|
# Only print if DEBUG is enabled
|
|
dprint = lib.print_ln if DEBUG else noop
|
|
|
|
# Benchmark types
|
|
INSERT = True
|
|
EXTRACT = True
|
|
SORTING = False
|
|
|
|
INSERT = INSERT or EXTRACT # Always insert if we are going to extract
|
|
|
|
# Benchmark parameters
|
|
## General
|
|
KEY_SIZE = lambda n: 32
|
|
VALUE_SIZE = lambda n: log2(n)
|
|
N_THREADS = 1
|
|
N_PARALLEL = 1
|
|
|
|
## Insert / ExtractMin
|
|
RANGE = [2**i for i in range(1, 18)]
|
|
# Important: there must be space to insert this amount of entries in the queue
|
|
OPERATIONS_PER_STEP = 10
|
|
TIME_INIT = True
|
|
TREE_HEAP = False
|
|
TREE_PATH_HEAP = False
|
|
LINEAR_HEAP = False
|
|
OPTIMAL_TREE_HEAP = False
|
|
OPTIMAL_PATH_HEAP = False
|
|
POH_PATH = True
|
|
POH_PATH_CONSTANT_STASH = True
|
|
UNIQUE_POH_PATH_LINEAR = False
|
|
UNIQUE_POH_PATH_PATH = False
|
|
UNIQUE_POH_PATH_CONSTANT_STASH_LINEAR = False
|
|
UNIQUE_POH_PATH_CONSTANT_STASH_PATH = False
|
|
|
|
## Sorting
|
|
LENGTHS = [2**i for i in range(1, 10)]
|
|
SORTING_BITS = 32
|
|
RADIX_SORT = True
|
|
POS = True
|
|
POS_CONSTANT_STASH = True
|
|
|
|
# Set module variables based on parameters
|
|
oram.n_threads = N_THREADS
|
|
oram.n_parallel = N_PARALLEL
|
|
oram.n_threads_for_tree = N_THREADS
|
|
|
|
# Timing with consecutive ids
|
|
timer_offset = 1000 # Hopefully run timers in an unused range
|
|
|
|
|
|
def start_fancy_timer(id: int | None = None) -> int:
|
|
global timer_offset
|
|
_id = id if id is not None else timer_offset
|
|
lib.start_timer(_id)
|
|
if id is None:
|
|
timer_offset += 1
|
|
return _id
|
|
|
|
|
|
def stop_fancy_timer(id):
|
|
lib.stop_timer(id)
|
|
|
|
|
|
# BENCHMARK
|
|
|
|
if INSERT:
|
|
|
|
def operation_round(i, id, q, apply_op, capacity, tag=""):
|
|
dprint(f"\n[{tag}] Update %s for capacity {capacity}", i.reveal())
|
|
start_fancy_timer(id)
|
|
apply_op(q, i)
|
|
stop_fancy_timer(id)
|
|
|
|
def benchmark_operations(q_init, capacity, *args, tag="", **kwargs):
|
|
global timer_offset
|
|
apply_insert = lambda q, i: q.update(0, i)
|
|
apply_extract = lambda q, _: q.pop()
|
|
init_id = timer_offset
|
|
insert_id = init_id + 1
|
|
extract_id = insert_id + 1
|
|
dprint(
|
|
f"\n[{tag}] Running {OPERATIONS_PER_STEP} update{'s' if OPERATIONS_PER_STEP > 1 else ''} for capacity {capacity}"
|
|
)
|
|
@lib.for_range(OPERATIONS_PER_STEP)
|
|
def _(i):
|
|
dprint(f"\n[{tag}] Initializing empty structure with capacity {capacity}")
|
|
if TIME_INIT:
|
|
start_fancy_timer(init_id)
|
|
q = q_init(capacity, *args, **kwargs)
|
|
if TIME_INIT:
|
|
stop_fancy_timer(init_id)
|
|
if INSERT:
|
|
operation_round(
|
|
i, insert_id, q, apply_insert, capacity, tag=tag + " insert"
|
|
)
|
|
if EXTRACT:
|
|
operation_round(
|
|
i,
|
|
extract_id,
|
|
q,
|
|
apply_extract,
|
|
capacity,
|
|
tag=tag + " extract_min",
|
|
)
|
|
timer_offset += 3
|
|
|
|
dprint(f"\n\nBENCHMARKING INSERT {'AND EXTRACT ' if EXTRACT else ''}TIME")
|
|
for capacity in RANGE:
|
|
entry_size = (KEY_SIZE(capacity), VALUE_SIZE(capacity))
|
|
|
|
dprint(f"\nCAPACITY {capacity}")
|
|
|
|
if TREE_HEAP:
|
|
# Benchmark binary heap built on ORAM (Tree ORAM variant)
|
|
benchmark_operations(
|
|
HeapQ,
|
|
capacity,
|
|
oram_type=oram.RecursiveORAM,
|
|
entry_size=entry_size,
|
|
tag="ORAM Heap (Tree)",
|
|
)
|
|
|
|
if TREE_PATH_HEAP:
|
|
# Benchmark binary heap built on ORAM (Path ORAM variant)
|
|
benchmark_operations(
|
|
HeapQ,
|
|
capacity,
|
|
oram_type=path_oram.RecursivePathORAM,
|
|
entry_size=entry_size,
|
|
tag="ORAM Heap (Path)",
|
|
)
|
|
|
|
if LINEAR_HEAP:
|
|
# Benchmark binary heap built on ORAM (Linear ORAM variant)
|
|
benchmark_operations(
|
|
HeapQ,
|
|
capacity,
|
|
oram_type=oram.LinearORAM,
|
|
entry_size=entry_size,
|
|
tag="ORAM Heap (Linear)",
|
|
)
|
|
|
|
if OPTIMAL_TREE_HEAP:
|
|
# Benchmark binary heap built on ORAM (OptimalORAM variant)
|
|
benchmark_operations(
|
|
HeapQ,
|
|
capacity,
|
|
oram_type=oram.OptimalORAM,
|
|
entry_size=entry_size,
|
|
tag="ORAM Heap (Optimal Tree)",
|
|
)
|
|
|
|
if OPTIMAL_PATH_HEAP:
|
|
# Benchmark binary heap built on ORAM (OptimalORAM Path variant)
|
|
benchmark_operations(
|
|
HeapQ,
|
|
capacity,
|
|
oram_type=path_oram.OptimalORAM,
|
|
entry_size=entry_size,
|
|
tag="ORAM Heap (Optimal Path)",
|
|
)
|
|
|
|
if POH_PATH:
|
|
# Benchmark Path Oblivious Heap (Path variant)
|
|
benchmark_operations(
|
|
POHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=log2(capacity) ** 2,
|
|
variant=POHVariant.PATH,
|
|
entry_size=entry_size,
|
|
tag="POH (Path (superlogarithmic stash size))",
|
|
)
|
|
|
|
if POH_PATH_CONSTANT_STASH:
|
|
# Benchmark Path Oblivious Heap (Path variant with constant stash size)
|
|
benchmark_operations(
|
|
POHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=20, # based on empirical analysis by Keller and Scholl
|
|
variant=POHVariant.PATH,
|
|
entry_size=entry_size,
|
|
tag="POH (Path (constant stash size))",
|
|
)
|
|
|
|
if UNIQUE_POH_PATH_LINEAR:
|
|
# Benchmark Unique Path Oblivious Heap (Path variant with constant stash size and linear ORAM)
|
|
benchmark_operations(
|
|
UniquePOHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=log2(capacity) ** 2,
|
|
variant=POHVariant.PATH,
|
|
oram_type=oram.LinearORAM,
|
|
entry_size=entry_size,
|
|
tag="Unique POH (Path (superlogarithmic stash size)) (Linear ORAM)",
|
|
)
|
|
|
|
if UNIQUE_POH_PATH_PATH:
|
|
# Benchmark Unique Path Oblivious Heap (Path variant with constant stash size and linear ORAM)
|
|
benchmark_operations(
|
|
UniquePOHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=log2(capacity) ** 2,
|
|
variant=POHVariant.PATH,
|
|
oram_type=path_oram.RecursivePathORAM,
|
|
entry_size=entry_size,
|
|
tag="Unique POH (Path (superlogarithmic stash size)) (Path ORAM)",
|
|
)
|
|
|
|
if UNIQUE_POH_PATH_CONSTANT_STASH_LINEAR:
|
|
benchmark_operations(
|
|
UniquePOHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=20,
|
|
variant=POHVariant.PATH,
|
|
oram_type=oram.LinearORAM,
|
|
entry_size=entry_size,
|
|
tag="Unique POH (Path (constant stash size)) (Linear ORAM)",
|
|
)
|
|
|
|
if UNIQUE_POH_PATH_CONSTANT_STASH_PATH:
|
|
benchmark_operations(
|
|
UniquePOHToHeapQAdapter,
|
|
capacity,
|
|
bucket_size=2,
|
|
stash_size=20,
|
|
variant=POHVariant.PATH,
|
|
oram_type=path_oram.RecursivePathORAM,
|
|
entry_size=entry_size,
|
|
tag="Unique POH (Path (constant stash size)) (Path ORAM)",
|
|
)
|
|
|
|
if SORTING:
|
|
dprint("\n\nBENCHMARKING SORTING TIME")
|
|
for n in LENGTHS:
|
|
dprint(f"\nLENGTH {n}")
|
|
a = Array(n, sint)
|
|
|
|
@lib.for_range(n)
|
|
def _(i):
|
|
a[i] = sint.get_random_int(SORTING_BITS)
|
|
|
|
if RADIX_SORT:
|
|
a_ = Array(n, sint).assign(a)
|
|
lib.print_ln(
|
|
"\n[Sorting (Radix)] Unsorted array of length %s: %s", n, a_.reveal()
|
|
)
|
|
lib.print_ln("[Sorting (Radix)] Sorting array...")
|
|
id = start_fancy_timer()
|
|
a_.sort()
|
|
stop_fancy_timer(id)
|
|
lib.print_ln("[Sorting (Radix)] Sorted array: %s", a_.reveal())
|
|
|
|
if POS:
|
|
a_ = Array(n, sint).assign(a)
|
|
lib.print_ln(
|
|
"\n[Sorting (POH) superlogarithmic stash size] Unsorted array of length %s: %s",
|
|
n,
|
|
a_.reveal(),
|
|
)
|
|
lib.print_ln("[Sorting (POH) superlogarithmic stash size] Sorting array...")
|
|
id = start_fancy_timer()
|
|
path_oblivious_sort(
|
|
a_, a_, SORTING_BITS, stash_size=log2(n) ** 2, variant=POHVariant.PATH
|
|
)
|
|
stop_fancy_timer(id)
|
|
lib.print_ln(
|
|
"[Sorting (POH) superlogarithmic stash size] Sorted array: %s",
|
|
a_.reveal(),
|
|
)
|
|
|
|
if POS_CONSTANT_STASH:
|
|
a_ = Array(n, sint).assign(a)
|
|
lib.print_ln(
|
|
"\n[Sorting (POH) constant stash size] Unsorted array of length %s: %s",
|
|
n,
|
|
a_.reveal(),
|
|
)
|
|
lib.print_ln("[Sorting (POH) constant stash size] Sorting array...")
|
|
id = start_fancy_timer()
|
|
path_oblivious_sort(
|
|
a_, a_, SORTING_BITS, stash_size=20, variant=POHVariant.PATH
|
|
)
|
|
stop_fancy_timer(id)
|
|
lib.print_ln(
|
|
"[Sorting (POH) constant stash size] Sorted array: %s", a_.reveal()
|
|
)
|