External Verification of Oblivious RAM Using Ethereum’s Smart Contracts

Oblivious RAM, or ORAM, represent a group of protocols that enable users to store data on a trustless server and to retrieve it as if it was stored on a local disk or server. The protocols are formulated to ensure that the server’s administrators would know nothing about the user’s data or the retrieval pattern, knowing only the size of the space occupied by the data and the frequency of its access by the user.

Although Oblivious RAM protocols have been initially described by Goldreich and Ostrovsky in 1993, the recent years have witnessed an evolution in the technology that markedly increased the efficiency of ORAM. A few days ago, a group of researchers published a paper that presented an Oblivious RAM protocol that implements Ethereum ‘s smart contracts for external verification.

An Overview of Oblivious RAM:

The purpose of ORAM is to enable a user to outsource storage to a trustless server. Although encrypting the data might appeal as a suitable solution, the reality is that it would be impractical because encryption would require the user to download the whole database to decrypt it every time he/she wishes to access the stored data. Another seemingly appropriate solution is to divide the stored data into blocks and each block can be encrypted separately, so that the user would need to only download the block containing the data he/she wishes to access. However, this will undermine the privacy of the user as a server administrator would be able to recognize which blocks are accessed in response to the user’s interaction(s) which can help in revealing the stored data or the computation process(es) the user is utilizing.

Godreich and Ostrovsky innovated ORAM which provided security, yet the protocol resulted in a marked increase in the required bandwidth for storage by a factor of 0 . Many researchers worked on improving the bandwidth usage of the ORAM protocols and “ORAM binary tree storage” was a major milestone that markedly reduced bandwidth usage and inspired many researchers to work on the development of ORAM protocols during the past 10 years.

Binary tree usage with ORAM storage is possible via 2 approaches: Path ORAM and Ring ORAM.

ORAM is the earliest form of binary tree usage with ORAM and it led to a decline of the bandwidth usage to a 0(). Ring ORAM was a successor to path ORAM and markedly improved its efficiency in bandwidth management.

Using Ethereum’s smart contracts to externally verify ORAM:

The researchers presented in their paper a new concept of “verifiable ORAM” which enables users to verify servers’ honesty. In other words, a user will give feedback regarding the server he/she used to store data and retrieve it. The external verifier, i.e. Ethereum’s smart contracts, will verify that a server is honestly and efficiently handling the storage tasks requested by the user and will also help in marking “cheating parties”.

Implementation of the external verifier protocol using ethereum’s smart contracts was straightforward, as described by the researchers. All implementation details related to how the smart contract communicates with ethereum’s blockchain are abstracted from ethereum’s open source libraries and further development would require some knowledge of ethereum’s virtual machine language which is known as “Solidity”.

Of course, the usage of ethereum’s smart contracts would require the user to spend some money in the form of the cryptocurrency ethereum. According to the experiments done by the researchers, external verification for a user who used the externally verifiable ORAM to outsource 10 Terrabytes worth of data, would need to spend around $0.33 in the form of ethereum, in the case that the used smart contract would end in a dispute. This would be seemingly reasonable for documenting penalties that result in data loss which are expected to cost much more than this amount.

Ethereum‘s platform and its smart contracts are starting a new era with a new concept that will turn the whole world into a group of trustless parties. The blockchain technology and smart contracts have ignited a new evolution in the Oblivious RAM technology sector. The work we presented will open the door for more innovations that will utilize autonomous 3rd parties in the areas of privacy and security where conventional verifiers are exchanged by smart contracts.