FastVer: Making Data Integrity a Commodity
Arvind Arasu
(Database
group, Microsoft Research, Redmond, WA, USA)
Badrish Chandramouli (Database group,
MSR Redmond)
Johannes
Gehrke
(MSR Redmond)
Esha
Ghosh
(Cryptography
and Privacy Research, MSR Redmond)
Donald
Kossmann (Database group, MSR Redmond)
Jonathan Protzenko
(RiSE: Research
in Software Engineering, MSR Redmond)
Ravi
Ramamurthy (Database group, MSR Redmond)
Tahina Ramananandro (RiSE)
Aseem
Rastogi
(Microsoft
Research, Bengaluru, Karnataka, India)
Srinath Setty
(Systems
Security and Privacy, MSR Redmond)
Nikhil
Swamy (RiSE)
Alexander van Renen
(Database Systems, Technische Universität München)
Min Xu (Department of Computer
Science, University of Chicago)
ACM SIGMOD 2021 (accepted for publication, to appear)
We present FastVer, a high-performance key-value store with strong data integrity guarantees. FastVer is built as an extension of FASTER, an open-source, high-performance key-value store. It offers the same key-value API as FASTER plus an additional verify() method that detects if an unauthorized attacker tampered with the database and checks whether results of all read operations are consistent with historical updates. FastVer is based on a novel approach that combines the advantages of Merkle trees and deferred memory verification. We show that this approach achieves one to two orders of magnitudes higher throughputs than traditional approaches based on either Merkle trees or memory verification. We have formally proven the correctness of our approach in a proof assistant, ensuring that verify() detects any inconsistencies, except if a collision can be found on a cryptographic hash.