# Obladi

Motivating app: Medical records
- access by docs locally at hospital
- storage outsourced to cloud


**Oblivious RAM (ORAM):**
- Compiler that transforms algorithms such that memory access pattern unrelated to original program, but input-output behavior preserved.
- Otherwise informatiom leakage about type, algorithm, and possibly general info about progress.
- Protection while on cloud platforms.
- Works by replacing data layout w/ binary tree, reads and writes transformed into tree
  accesses (both modify the tree in random ways).
- accessed objects remapped to new locations
  - flushed back during *eviction*
  - objects that can't be flushed go into *stash* (client-side)
  
![](obladiRing.png)

**Two issues:**
- stash growth unbounded
- all buckets soon invalid
Address with *eviction* and *bucket reshuffling*.

Periodically, a *target path* chosen:
![](obladiEvict.png)
- *read phase*
  - retrieves Z objects from each bucket in path
    - all real objects
    - dummies to add up to Z
![](obladiShuffle.png)
- *write phase*
  - each stashed object placed on deepest bucket where target path intersects assigned path	
  - permutes real and dummy values in each bucket along target
  - marks their slots as valid
  
Obladi uses deterministic random permutation to map real data into tree, stores at client.


## Obladi
**acid transactions** through *delayed visibility*

Problems with generic ORAM:
- not fault tolerant
  - data often stashed, durability requires this to be recovered on crash
- no support for concurrency?

Transactions *are good*, in the sense that serialization is not strict.

Delay allows *multi-versioned database*, so that:
- reads are non-blocking
- only *last* writes written to disk
  (reduces number of ORAM operations)
 - concurrency allows further delays w/ other work.

Delay allows ORAM to be parallelized
- conflicting ops pipelined: only secure if write-back delayed.


![](obladiArch.png)


## Threat Model
*trused proxy* model:
- mutually trusting clients
- trusted proxy

**honest-but-curious** cloud server.
- can see and control comm to and from proxy
- can't see comm between proxy and clients
- *executes protocol faithfully*

Gurantees that adversary won't learn:
- transx decisions
- num ops in transaction
- type of requests
- which data

Is okay to leak type of app (OLTP vs OLAP).

## It's all about the epochs

- transactions run in a single **epoch** (or are aborted)
- commit/abort at end
- cascades avoided by *fate-sharing*
  - either all trans that commit made durable, or all abort
- optimistic *timestamp-ordering* concurrency control
  - *necessary* because transx all commit at epoch end
  - 2PL would increase contention because locks held to end

![](obladiBatching.png)
- write of *a* by **t1** immediately seen by **t3**
- **t2**'s write to *d* causes **t2** to abort

Note:
- time increases downwards
- **t1** -> **t2** -> **t3** -> **t4**

## Data Handling
Always correct to re-write transx so that all reads happen before all writes (if known a
priori)
- batched across all transx
- de-duplicated (prevents detection of parallelism)



## Parallelizing the ORAM
Types of parallelism:
- accesses concurrent with evictions
- between accesses
  - hotspots turn into accesses to distinct locations, so can be parallelized

Dependencies
- operations broken into sub-ops, ordering at top level needs to be tracked at
  sub level (physical)
- 

![](obladiPipe.png)





## Bottom line
![](obladiPerf.png)

- 5x-12x slowdown in throughput
- 70x slowdown in latency

(actually pretty good)
