#![no_std]
#![deny(unsafe_code)]
#![deny(missing_docs)]
extern crate alloc;
use aligned_cmov::{
subtle::{Choice, ConstantTimeEq, ConstantTimeGreater},
typenum, A64Bytes, A8Bytes, ArrayLength, AsAlignedChunks, CMov,
};
use alloc::vec::Vec;
use core::{
hash::{BuildHasher, Hash, Hasher},
marker::PhantomData,
ops::{Add, Sub},
};
use generic_array::sequence::Split;
use mc_oblivious_traits::{
log2_ceil, OMapCreator, ORAMCreator, ObliviousHashMap, OMAP_FOUND, OMAP_INVALID_KEY,
OMAP_NOT_FOUND, OMAP_OVERFLOW, ORAM,
};
use rand_core::{CryptoRng, RngCore};
use typenum::{PartialDiv, Sum, U8};
mod build_hasher;
use build_hasher::SipBuildHasher;
const MAX_EVICTION_RETRIES: usize = 6;
pub struct CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>
where
KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static,
ValueSize: ArrayLength<u8> + PartialDiv<U8>,
BlockSize: ArrayLength<u8> + PartialDiv<U8>,
RngType: RngCore + CryptoRng + Send + Sync + 'static,
O: ORAM<BlockSize> + Send + Sync + 'static,
Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,
{
num_items: u64,
num_buckets: u64,
hash1: SipBuildHasher,
hash2: SipBuildHasher,
oram1: O,
oram2: O,
rng: RngType,
_key_size: PhantomData<fn() -> KeySize>,
_value_size: PhantomData<fn() -> ValueSize>,
_block_size: PhantomData<fn() -> BlockSize>,
}
impl<KeySize, ValueSize, BlockSize, RngType, O>
CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>
where
KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static,
ValueSize: ArrayLength<u8> + PartialDiv<U8>,
BlockSize: ArrayLength<u8> + PartialDiv<U8>,
RngType: RngCore + CryptoRng + Send + Sync + 'static,
O: ORAM<BlockSize> + Send + Sync + 'static,
Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,
{
pub fn new<OC, M>(desired_capacity: u64, stash_size: usize, mut maker: M) -> Self
where
OC: ORAMCreator<BlockSize, RngType, Output = O>,
M: 'static + FnMut() -> RngType,
{
assert!(Self::BUCKET_CAPACITY > 0, "Block size is insufficient to store even one item. For good performance it should be enough to store several items.");
let num_buckets = 1u64 << log2_ceil((desired_capacity / Self::BUCKET_CAPACITY) / 2);
debug_assert!(
num_buckets & (num_buckets - 1) == 0,
"num_buckets must be a power of two"
);
let oram1 = OC::create(num_buckets, stash_size, &mut maker);
debug_assert!(num_buckets <= oram1.len(), "unexpected oram capacity");
let oram2 = OC::create(num_buckets, stash_size, &mut maker);
debug_assert!(num_buckets <= oram2.len(), "unexpected oram capacity");
debug_assert!(
oram1.len() == oram2.len(),
"Orams didn't have the same length, not expected"
);
let mut rng = maker();
let hash1 = SipBuildHasher::from_rng(&mut rng);
let hash2 = SipBuildHasher::from_rng(&mut rng);
Self {
num_items: 0,
num_buckets,
hash1,
hash2,
oram1,
oram2,
rng,
_key_size: Default::default(),
_value_size: Default::default(),
_block_size: Default::default(),
}
}
fn hash_query(&self, query: &A8Bytes<KeySize>) -> [u64; 2] {
let result1 = {
let mut hasher = self.hash1.build_hasher();
query.as_slice().hash(&mut hasher);
hasher.finish() & (self.num_buckets - 1)
};
let result2 = {
let mut hasher = self.hash2.build_hasher();
query.as_slice().hash(&mut hasher);
hasher.finish() & (self.num_buckets - 1)
};
[result1, result2]
}
fn count_before_insert(query: &A8Bytes<KeySize>, block: &A64Bytes<BlockSize>) -> (Choice, u32) {
let mut found = Choice::from(0);
let mut empty_count = 0u32;
let pairs: &[A8Bytes<Sum<KeySize, ValueSize>>] = block.as_aligned_chunks();
for pair in pairs {
let (key, _): (&A8Bytes<KeySize>, &A8Bytes<ValueSize>) = pair.split();
found |= key.ct_eq(query);
empty_count += key.ct_eq(&A8Bytes::<KeySize>::default()).unwrap_u8() as u32;
}
(found, empty_count)
}
fn insert_to_block(
condition: Choice,
query: &A8Bytes<KeySize>,
new_value: &A8Bytes<ValueSize>,
block: &mut A64Bytes<BlockSize>,
) {
let mut key_buf = query.clone();
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] = block.as_mut_aligned_chunks();
for pair in pairs {
let (key, value): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) =
<&mut A8Bytes<Sum<KeySize, ValueSize>> as Split<u8, KeySize>>::split(pair);
let test = condition & (key.ct_eq(query) | key.ct_eq(&A8Bytes::<KeySize>::default()));
key.cmov(test, &key_buf);
key_buf.cmov(test, &A8Bytes::default());
value.cmov(test, new_value);
}
}
const BUCKET_CAPACITY: u64 = (BlockSize::U64 / (KeySize::U64 + ValueSize::U64));
}
impl<KeySize, ValueSize, BlockSize, RngType, O> ObliviousHashMap<KeySize, ValueSize>
for CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>
where
KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static,
ValueSize: ArrayLength<u8> + PartialDiv<U8>,
BlockSize: ArrayLength<u8> + PartialDiv<U8>,
RngType: RngCore + CryptoRng + Send + Sync + 'static,
O: ORAM<BlockSize> + Send + Sync + 'static,
Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,
{
fn len(&self) -> u64 {
self.num_items
}
fn capacity(&self) -> u64 {
2 * self.num_buckets * Self::BUCKET_CAPACITY
}
fn read(&mut self, query: &A8Bytes<KeySize>, output: &mut A8Bytes<ValueSize>) -> u32 {
if bool::from(query.ct_eq(&A8Bytes::<KeySize>::default())) {
return OMAP_INVALID_KEY;
}
let mut result_code = OMAP_NOT_FOUND;
let hashes = self.hash_query(query);
self.oram1.access(hashes[0], |block| {
let pairs: &[A8Bytes<Sum<KeySize, ValueSize>>] = block.as_aligned_chunks();
for pair in pairs {
let (key, value): (&A8Bytes<KeySize>, &A8Bytes<ValueSize>) = pair.split();
let test = query.ct_eq(key);
result_code.cmov(test, &OMAP_FOUND);
output.cmov(test, value);
}
});
self.oram2.access(hashes[1], |block| {
let pairs: &[A8Bytes<Sum<KeySize, ValueSize>>] = block.as_aligned_chunks();
for pair in pairs {
let (key, value): (&A8Bytes<KeySize>, &A8Bytes<ValueSize>) = pair.split();
let test = query.ct_eq(key);
result_code.cmov(test, &OMAP_FOUND);
output.cmov(test, value);
}
});
result_code
}
fn access<F: FnOnce(u32, &mut A8Bytes<ValueSize>)>(&mut self, query: &A8Bytes<KeySize>, f: F) {
let mut callback_buffer = A8Bytes::<ValueSize>::default();
if bool::from(query.ct_eq(&A8Bytes::<KeySize>::default())) {
f(OMAP_INVALID_KEY, &mut callback_buffer);
return;
}
let hashes = self.hash_query(query);
let oram1 = &mut self.oram1;
let oram2 = &mut self.oram2;
oram1.access(hashes[0], |block1| {
oram2.access(hashes[1], |block2| {
let mut result_code = OMAP_NOT_FOUND;
for block in &[&block1, &block2] {
let pairs: &[A8Bytes<Sum<KeySize, ValueSize>>] = block.as_aligned_chunks();
for pair in pairs {
let (key, val): (&A8Bytes<KeySize>, &A8Bytes<ValueSize>) = pair.split();
let test = query.ct_eq(key);
callback_buffer.cmov(test, val);
debug_assert!(
result_code != OMAP_FOUND || bool::from(!test),
"key should not be found twice"
);
result_code.cmov(test, &OMAP_FOUND);
}
}
f(result_code, &mut callback_buffer);
for block in &mut [block1, block2] {
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] =
block.as_mut_aligned_chunks();
for pair in pairs {
let (key, val): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) =
pair.split();
let test = query.ct_eq(key);
val.cmov(test, &callback_buffer);
}
}
});
});
}
fn remove(&mut self, query: &A8Bytes<KeySize>) -> u32 {
if bool::from(query.ct_eq(&A8Bytes::<KeySize>::default())) {
return OMAP_INVALID_KEY;
}
let mut result_code = OMAP_NOT_FOUND;
let hashes = self.hash_query(query);
self.oram1.access(hashes[0], |block| {
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] = block.as_mut_aligned_chunks();
for pair in pairs {
let (key, _): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) = pair.split();
let test = query.as_slice().ct_eq(key.as_slice());
key.cmov(test, &Default::default());
result_code.cmov(test, &OMAP_FOUND);
}
});
self.oram2.access(hashes[1], |block| {
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] = block.as_mut_aligned_chunks();
for pair in pairs {
let (key, _): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) = pair.split();
let test = query.as_slice().ct_eq(key.as_slice());
key.cmov(test, &Default::default());
result_code.cmov(test, &OMAP_FOUND);
}
});
result_code
}
fn vartime_write_extended(
&mut self,
query: &A8Bytes<KeySize>,
new_value: &A8Bytes<ValueSize>,
allow_overwrite: Choice,
allow_sideeffects_and_eviction: Choice,
) -> u32 {
if bool::from(query.ct_eq(&A8Bytes::<KeySize>::default())) {
return OMAP_INVALID_KEY;
}
let mut result_code = OMAP_NOT_FOUND;
let mut evicted_key = A8Bytes::<KeySize>::default();
let mut evicted_val = A8Bytes::<ValueSize>::default();
let mut eviction_retries = MAX_EVICTION_RETRIES;
let mut eviction_from = Vec::<u64>::with_capacity(eviction_retries);
let mut eviction_indices = Vec::<usize>::with_capacity(eviction_retries);
let hashes = self.hash_query(query);
let rng = &mut self.rng;
let oram1 = &mut self.oram1;
let oram2 = &mut self.oram2;
oram1.access(hashes[0], |block1| {
oram2.access(hashes[1], |block2| {
let (block1_found, block1_empty_count) = Self::count_before_insert(query, block1);
let (block2_found, block2_empty_count) = Self::count_before_insert(query, block2);
debug_assert!(
!bool::from(block1_found & block2_found),
"key should not be found twice"
);
let found = block1_found | block2_found;
result_code.cmov(found, &OMAP_FOUND);
{
let condition = allow_sideeffects_and_eviction & (allow_overwrite | !found);
let write_to_block1 = !block2_found
& (block1_found | block1_empty_count.ct_gt(&block2_empty_count));
Self::insert_to_block(condition & write_to_block1, query, new_value, block1);
Self::insert_to_block(condition & !write_to_block1, query, new_value, block2);
}
if bool::from(
!found
& block1_empty_count.ct_eq(&0)
& block2_empty_count.ct_eq(&0)
& allow_sideeffects_and_eviction,
) {
result_code = OMAP_OVERFLOW;
let random = rng.next_u32();
let index = (random % (Self::BUCKET_CAPACITY as u32)) as usize;
eviction_from.push(hashes[0]);
eviction_indices.push(index);
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] =
block1.as_mut_aligned_chunks();
let pair = &mut pairs[index];
let (key, val): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) = pair.split();
evicted_key = key.clone();
evicted_val = val.clone();
debug_assert!(bool::from(allow_sideeffects_and_eviction));
*key = query.clone();
*val = new_value.clone();
}
});
});
while result_code == OMAP_OVERFLOW {
if eviction_retries > 0 {
let last_evicted_from = eviction_from[eviction_from.len() - 1];
let next_oram = eviction_from.len() % 2;
let hashes = self.hash_query(&evicted_key);
debug_assert!(hashes[1 - next_oram] == last_evicted_from);
let dest = hashes[next_oram];
let rng = &mut self.rng;
let oram = if next_oram == 0 {
&mut self.oram1
} else {
&mut self.oram2
};
oram.access(dest, |block| {
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] =
block.as_mut_aligned_chunks();
debug_assert!(pairs.len() == Self::BUCKET_CAPACITY as usize);
let mut found_vacant = Choice::from(0);
for pair in pairs.iter_mut() {
let (key, val): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) =
pair.split();
debug_assert!(
key != &evicted_key,
"evicted key should not be present anywhere"
);
let is_vacant = key.ct_eq(&A8Bytes::<KeySize>::default());
debug_assert!(bool::from(allow_sideeffects_and_eviction));
let cond = !found_vacant & is_vacant;
key.cmov(cond, &evicted_key);
val.cmov(cond, &evicted_val);
found_vacant |= is_vacant;
}
if bool::from(found_vacant) {
result_code = OMAP_NOT_FOUND;
} else {
let index = (rng.next_u32() % (Self::BUCKET_CAPACITY as u32)) as usize;
let pair = &mut pairs[index];
let (key, val): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) =
pair.split();
debug_assert!(bool::from(allow_sideeffects_and_eviction));
core::mem::swap(key, &mut evicted_key);
core::mem::swap(val, &mut evicted_val);
eviction_from.push(dest);
eviction_indices.push(index);
}
});
eviction_retries = eviction_retries.wrapping_sub(1);
} else {
debug_assert!(eviction_from.len() == eviction_indices.len());
while !eviction_indices.is_empty() {
let next_oram = eviction_from.len() % 2;
let evicted_index = eviction_indices.pop().unwrap();
let evicted_from = eviction_from.pop().unwrap();
debug_assert!(
self.hash_query(&evicted_key)[1 - next_oram] == evicted_from,
"The evicted key doesn't hash to the spot we thought we evicted it from"
);
let oram = if next_oram == 0 {
&mut self.oram2
} else {
&mut self.oram1
};
oram.access(evicted_from, |block| {
let pairs: &mut [A8Bytes<Sum<KeySize, ValueSize>>] =
block.as_mut_aligned_chunks();
let pair = &mut pairs[evicted_index as usize];
let (key, val): (&mut A8Bytes<KeySize>, &mut A8Bytes<ValueSize>) =
pair.split();
debug_assert!(bool::from(allow_sideeffects_and_eviction));
core::mem::swap(key, &mut evicted_key);
core::mem::swap(val, &mut evicted_val);
})
}
debug_assert!(&evicted_key == query, "After rolling back evictions, we didn't end up with the initially inserted item coming back");
return OMAP_OVERFLOW;
}
}
self.num_items += (result_code.ct_eq(&OMAP_NOT_FOUND) & allow_sideeffects_and_eviction)
.unwrap_u8() as u64;
result_code
}
}
pub struct CuckooHashTableCreator<BlockSize, RngType, OC>
where
BlockSize: ArrayLength<u8>,
RngType: RngCore + CryptoRng + Send + Sync + 'static,
OC: ORAMCreator<BlockSize, RngType>,
OC::Output: ORAM<BlockSize> + Send + Sync + 'static,
{
_block_size: PhantomData<fn() -> BlockSize>,
_rng_type: PhantomData<fn() -> RngType>,
_oc: PhantomData<fn() -> OC>,
}
impl<KeySize, ValueSize, BlockSize, RngType, OC> OMapCreator<KeySize, ValueSize, RngType>
for CuckooHashTableCreator<BlockSize, RngType, OC>
where
KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static,
ValueSize: ArrayLength<u8> + PartialDiv<U8> + 'static,
BlockSize: ArrayLength<u8> + PartialDiv<U8> + 'static,
RngType: RngCore + CryptoRng + Send + Sync + 'static,
OC: ORAMCreator<BlockSize, RngType>,
OC::Output: ORAM<BlockSize> + Send + Sync + 'static,
Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,
{
type Output = CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, OC::Output>;
fn create<M: 'static + FnMut() -> RngType>(
size: u64,
stash_size: usize,
rng_maker: M,
) -> Self::Output {
Self::Output::new::<OC, M>(size, stash_size, rng_maker)
}
}
#[cfg(test)]
mod testing {
use super::*;
use mc_oblivious_ram::PathORAM4096Z4Creator;
use mc_oblivious_traits::{
rng_maker, testing, HeapORAMStorageCreator, OMapCreator, OMAP_FOUND, OMAP_NOT_FOUND,
};
use test_helper::{run_with_several_seeds, RngType};
use typenum::{U1024, U8};
extern crate std;
const STASH_SIZE: usize = 16;
type ORAMCreatorZ4 = PathORAM4096Z4Creator<RngType, HeapORAMStorageCreator>;
type CuckooCreatorZ4 = CuckooHashTableCreator<U1024, RngType, ORAMCreatorZ4>;
fn a8_8<N: ArrayLength<u8>>(src: u8) -> A8Bytes<N> {
let mut result = A8Bytes::<N>::default();
for byte in result.as_mut_slice() {
*byte = src;
}
result
}
#[test]
fn sanity_check_omap_z4_4() {
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
4,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U8>::default();
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(1), &a8_8(2), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(2));
assert_eq!(OMAP_FOUND, omap.vartime_write(&a8_8(1), &a8_8(3), 1.into()));
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(3));
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(3),
"omap.read must not modify the output on not_found"
);
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(20), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(20));
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(20),
"omap.write must not modify when overwrite is disallowed"
);
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(30));
})
}
#[test]
fn sanity_check_omap_z4_256() {
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
256,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U8>::default();
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(1), &a8_8(2), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(2));
assert_eq!(OMAP_FOUND, omap.vartime_write(&a8_8(1), &a8_8(3), 1.into()));
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(3));
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(3),
"omap.read must not modify the output on not_found"
);
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(20), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(20));
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(20),
"omap.write must not modify when overwrite is disallowed"
);
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(30));
})
}
#[test]
fn sanity_check_omap_z4_524288() {
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
524288,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U8>::default();
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(1), &a8_8(2), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(2));
assert_eq!(OMAP_FOUND, omap.vartime_write(&a8_8(1), &a8_8(3), 1.into()));
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(3));
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(3),
"omap.read must not modify the output on not_found"
);
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(20), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(20));
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(20),
"omap.write must not modify when overwrite is disallowed"
);
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(30));
})
}
#[test]
fn sanity_check_omap_z4_2097152() {
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
2097152,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U8>::default();
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(1), &a8_8(2), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(2));
assert_eq!(OMAP_FOUND, omap.vartime_write(&a8_8(1), &a8_8(3), 1.into()));
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(3));
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(3),
"omap.read must not modify the output on not_found"
);
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(20), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(20));
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(20),
"omap.write must not modify when overwrite is disallowed"
);
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(30));
})
}
#[test]
#[cfg(not(debug_assertions))]
fn sanity_check_omap_z4_262144() {
run_with_several_seeds(|rng| {
use typenum::{U16, U280};
let mut omap = <CuckooCreatorZ4 as OMapCreator<U16, U280, RngType>>::create(
262144,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U280>::default();
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(1), &a8_8(2), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(2));
assert_eq!(OMAP_FOUND, omap.vartime_write(&a8_8(1), &a8_8(3), 1.into()));
assert_eq!(OMAP_FOUND, omap.read(&a8_8(1), &mut temp));
assert_eq!(&temp, &a8_8(3));
assert_eq!(OMAP_NOT_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(3),
"omap.read must not modify the output on not_found"
);
assert_eq!(
OMAP_NOT_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(20), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(20));
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 0.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(
&temp,
&a8_8(20),
"omap.write must not modify when overwrite is disallowed"
);
assert_eq!(
OMAP_FOUND,
omap.vartime_write(&a8_8(2), &a8_8(30), 1.into())
);
assert_eq!(OMAP_FOUND, omap.read(&a8_8(2), &mut temp));
assert_eq!(&temp, &a8_8(30));
})
}
#[test]
fn exercise_omap_two_choice_path_oram_z4_256() {
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap =
<CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(256, STASH_SIZE, maker);
testing::exercise_omap(200, &mut omap, &mut rng);
});
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap =
<CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(256, STASH_SIZE, maker);
testing::exercise_omap_counter_table(200, &mut omap, &mut rng);
});
}
#[test]
fn exercise_omap_two_choice_path_oram_z4_3072() {
run_with_several_seeds(|rng| {
use typenum::{U16, U280};
let mut maker = rng_maker(rng);
let _ = maker();
let mut rng = maker();
let mut omap = <CuckooCreatorZ4 as OMapCreator<U16, U280, RngType>>::create(
3072, STASH_SIZE, maker,
);
testing::exercise_omap(400, &mut omap, &mut rng);
});
run_with_several_seeds(|rng| {
use typenum::U16;
let mut maker = rng_maker(rng);
let _ = maker();
let mut rng = maker();
let mut omap =
<CuckooCreatorZ4 as OMapCreator<U16, U8, RngType>>::create(3072, STASH_SIZE, maker);
testing::exercise_omap_counter_table(400, &mut omap, &mut rng);
});
}
#[test]
#[cfg(not(debug_assertions))]
fn exercise_omap_two_choice_path_oram_z4_65536() {
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap =
<CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(65536, STASH_SIZE, maker);
testing::exercise_omap(2000, &mut omap, &mut rng);
});
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap =
<CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(65536, STASH_SIZE, maker);
testing::exercise_omap_counter_table(2000, &mut omap, &mut rng);
});
}
#[test]
#[cfg(not(debug_assertions))]
fn exercise_omap_two_choice_path_oram_z4_524288() {
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
524288, STASH_SIZE, maker,
);
testing::exercise_omap(16_000, &mut omap, &mut rng);
});
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
524288, STASH_SIZE, maker,
);
testing::exercise_omap_counter_table(16_000, &mut omap, &mut rng);
});
}
#[test]
#[cfg(not(debug_assertions))]
fn exercise_omap_two_choice_path_oram_z4_2097152() {
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
2097152, STASH_SIZE, maker,
);
testing::exercise_omap(16_000, &mut omap, &mut rng);
});
run_with_several_seeds(|rng| {
let mut maker = rng_maker(rng);
let mut rng = maker();
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U8, RngType>>::create(
2097152, STASH_SIZE, maker,
);
testing::exercise_omap_counter_table(16_000, &mut omap, &mut rng);
});
}
#[test]
#[cfg(not(debug_assertions))]
fn omap_70_capacity_two_choice_path_oram_z4_16384() {
use typenum::U248;
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U248, RngType>>::create(
16384,
STASH_SIZE,
rng_maker(rng),
);
let mut temp = A8Bytes::<U8>::default();
let val = A8Bytes::<U248>::default();
for idx in 1u64..(omap.capacity() * 7 / 10) {
temp.copy_from_slice(&idx.to_le_bytes());
let result_code = omap.vartime_write(&temp, &val, 0.into());
assert!(OMAP_OVERFLOW != result_code);
assert!(OMAP_NOT_FOUND == result_code);
assert_eq!(omap.len(), idx);
}
});
}
#[test]
#[cfg(not(debug_assertions))]
fn omap_overflow_semantics_two_choice_path_oram_z4_16384() {
use std::println;
use typenum::U248;
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U248, RngType>>::create(
16384,
STASH_SIZE,
rng_maker(rng),
);
let len = testing::test_omap_overflow(&mut omap);
let cap = omap.capacity();
let fraction = (len as f32) * 100f32 / (cap as f32);
println!("Overflowed at {} / {} = {}%", len, cap, fraction);
})
}
#[test]
#[cfg(not(debug_assertions))]
fn omap_overflow_semantics_two_choice_path_oram_z4_32768() {
use std::println;
use typenum::U248;
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U248, RngType>>::create(
32768,
STASH_SIZE,
rng_maker(rng),
);
let len = testing::test_omap_overflow(&mut omap);
let cap = omap.capacity();
let fraction = (len as f32) * 100f32 / (cap as f32);
println!("Overflowed at {} / {} = {}%", len, cap, fraction);
})
}
#[test]
#[cfg(not(debug_assertions))]
fn omap_overflow_semantics_two_choice_path_oram_z4_65536() {
use std::println;
use typenum::U248;
run_with_several_seeds(|rng| {
let mut omap = <CuckooCreatorZ4 as OMapCreator<U8, U248, RngType>>::create(
65536,
STASH_SIZE,
rng_maker(rng),
);
let len = testing::test_omap_overflow(&mut omap);
let cap = omap.capacity();
let fraction = (len as f32) * 100f32 / (cap as f32);
println!("Overflowed at {} / {} = {}%", len, cap, fraction);
})
}
}