How to Build a Trusted Database System on Untrusted Storage
Maheshwari, Vingralek, Shapiro
OSDI 2000

Let's build our own simple system
  Assume disk-like interface to untrusted store? i.e. sector #s?
  Just one piece of data (keep one hash)
    Why not just sign the data w/ RSA?
  Many unrelated pieces of data (keep array of hashes)
  Can we make the untrusted store hold the ID->hash array?
    how do we update it?
  Can we integrate the data and the hashes?
    i.e. have self-authenticating data
    how do we update it?

What's the interface to the untrusted store?
  put(k, v) ??? arbitrary key? rewriteable?
  get(k) ???

What's the interface to the trusted chunk store?
  allows re-write of chunks

Why can't the untrusted store modify data?

Why can't the untrusted store return stale data?

Can the untrusted store read or understand the data?

Why do they use a log?
  Why not wafl-like snapshot?
  So transaction can commit w/o writing ancestors?
    Which might force commit of other partial transactions?