Practical Foundations of History Independence
The way data structures organize data is often a function of the sequence of past operations. The organization of data is referred to as the data structure's state, and the sequence of past operations constitutes the data structure's history. A data structure state can therefore be used as an oracle to derive information about its history. As a result, for history-sensitive applications, such as privacy in e-voting, incremental signature schemes, and regulatory compliant data retention; it is imperative to conceal historical information contained within data structure states. Data structure history can be hidden by making data structures history independent. In this paper, we explore how to achieve history independence. We observe that current history independence notions are significantly limited in number and scope. There are two existing notions of history independence -- weak history independence (WHI) and strong history independence (SHI). WHI does not protect against insider adversaries and SHI mandates canonical representations, resulting in inefficiency. We postulate the need for a broad, encompassing notion of history independence, which can capture WHI, SHI, and a broad spectrum of new history independence notions. To this end, we introduce $Δ$history independence ($Δ$HI), a generic game-based framework that is malleable enough to accommodate existing and new history independence notions. As an essential step towards formalizing $Δ$HI, we explore the concepts of abstract data types, data structures, machine models, memory representations and history independence. Finally, to bridge the gap between theory and practice, we outline a general recipe for building end-to-end, history independent systems and demonstrate the use of the recipe in designing two history independent file systems.