by Arasu, Arvind, Chandramouli, Badrish, Gehrke, Johannes, Ghosh, Esha, Kossmann, Donald, Protzenko, Jonathan, Ramamurthy, Ravi, Ramananandro, Tahina, Rastogi, Aseem, Setty, Srinath, Swamy, Nikhil, van Renen, Alexander and Xu, Min
Abstract:
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.
Reference:
FastVer: Making Data Integrity a Commodity (Arasu, Arvind, Chandramouli, Badrish, Gehrke, Johannes, Ghosh, Esha, Kossmann, Donald, Protzenko, Jonathan, Ramamurthy, Ravi, Ramananandro, Tahina, Rastogi, Aseem, Setty, Srinath, Swamy, Nikhil, van Renen, Alexander and Xu, Min), In Proceedings of the 2021 International Conference on Management of Data, Association for Computing Machinery, 2021.
Bibtex Entry:
@inproceedings{fastver,
author = {Arasu, Arvind and Chandramouli, Badrish and Gehrke, Johannes and Ghosh, Esha and Kossmann, Donald and Protzenko, Jonathan and Ramamurthy, Ravi and Ramananandro, Tahina and Rastogi, Aseem and Setty, Srinath and Swamy, Nikhil and van Renen, Alexander and Xu, Min},
title = {FastVer: Making Data Integrity a Commodity},
year = {2021},
isbn = {9781450383431},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3448016.3457312},
doi = {10.1145/3448016.3457312},
abstract = {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.},
booktitle = {Proceedings of the 2021 International Conference on Management of Data},
pages = {89–101},
numpages = {13},
keywords = {key-value database, concurrency, data integrity, cryptographic hashing, merkle tree, memory checking},
location = {Virtual Event, China},
series = {SIGMOD '21}
}