{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:19:51Z","timestamp":1773825591562,"version":"3.50.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p>Databases in the past have helped businesses maintain and extract insights from their data. Today, it is common for a business to involve multiple independent, distrustful parties. This trend towards decentralization introduces a new and important requirement to databases: the integrity of the data, the history, and the execution must be protected. In other words, there is a need for a new class of database systems whose integrity can be verified (or verifiable databases).<\/jats:p>\n          <jats:p>In this paper, we identify the requirements and the design challenges of verifiable databases. We observe that the main challenges come from the need to balance data immutability, tamper evidence, and performance. We first consider approaches that extend existing OLTP and OLAP systems with support for verification. We next examine a clean-slate approach, by describing a new system, Spitz, specifically designed for efficiently supporting immutable and tamper-evident transaction management. We conduct a preliminary performance study of both approaches against a baseline system, and provide insights on their performance.<\/jats:p>","DOI":"10.14778\/3415478.3415567","type":"journal-article","created":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T18:46:40Z","timestamp":1600109200000},"page":"3449-3460","source":"Crossref","is-referenced-by-count":29,"title":["Spitz"],"prefix":"10.14778","volume":"13","author":[{"given":"Meihui","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongle","family":"Xie","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cong","family":"Yue","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyue","family":"Zhong","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Couchdb. https:\/\/couchdb.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Datomic. https:\/\/www.datomic.com\/."},{"key":"e_1_2_1_3_1","unstructured":"Fabricsharp. https:\/\/www.comp.nus.edu.sg\/~dbsystem\/fabricsharp."},{"key":"e_1_2_1_4_1","unstructured":"Hbase. https:\/\/hbase.apache.org\/."},{"key":"e_1_2_1_5_1","unstructured":"Hyperledger. https:\/\/www.hyperledger.org."},{"key":"e_1_2_1_6_1","unstructured":"immudb. https:\/\/github.com\/codenotary\/immudb."},{"key":"e_1_2_1_7_1","unstructured":"Querying your data - amazon quantum ledger database (amazon qldb). https:\/\/docs.aws.amazon.com\/qldb\/latest\/developerguide\/working.userdata.html."},{"key":"e_1_2_1_8_1","unstructured":"Rethinkdb. https:\/\/rethinkdb.com\/."},{"key":"e_1_2_1_9_1","unstructured":"Spark. https:\/\/spark.apache.org\/."},{"key":"e_1_2_1_10_1","volume-title":"https:\/\/laptrinhx.com\/wolk-swarmdb-decentralized-database-services-for-web3-4011398543\/","year":"2017","unstructured":"Wolk SwarmDB-decentralized database service for web3. https:\/\/laptrinhx.com\/wolk-swarmdb-decentralized-database-services-for-web3-4011398543\/, 2017."},{"key":"e_1_2_1_11_1","volume-title":"https:\/\/aws.amazon.com\/qldb\/","year":"2019","unstructured":"Amazon quantum ledger database (qldb). https:\/\/aws.amazon.com\/qldb\/, 2019."},{"key":"e_1_2_1_12_1","volume-title":"https:\/\/github.com\/mongodb-labs\/ledger","year":"2020","unstructured":"Implementing cryptographically verifiable change history using mongodb. https:\/\/github.com\/mongodb-labs\/ledger, 2020."},{"key":"e_1_2_1_13_1","volume-title":"https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/20\/ftnew\/oracle-blockchain-table.html","year":"2020","unstructured":"Oracle blockchain tables. https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/20\/ftnew\/oracle-blockchain-table.html, 2020."},{"key":"e_1_2_1_14_1","first-page":"251","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Arasu A.","year":"2017","unstructured":"A. Arasu, K. Eguro, R. Kaushik, D. Kossmann, P. Meng, V. Pandey, and R. Ramamurthy. Concerto: A high concurrency key-value store with integrity. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 251--266. ACM, 2017."},{"key":"e_1_2_1_15_1","first-page":"781","volume-title":"Proceedings of the 23rd USENIX Security Symposium","author":"Ben-Sasson E.","year":"2014","unstructured":"E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Succinct non-interactive zero knowledge for a von neumann architecture. In Proceedings of the 23rd USENIX Security Symposium, pages 781--796. USENIX Association, 2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-22792-9_7","volume-title":"Advances in Cryptology - CRYPTO 2011","volume":"6841","author":"Benabbas S.","year":"2011","unstructured":"S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets. In Advances in Cryptology - CRYPTO 2011, volume 6841, pages 111--131. Springer, 2011."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/319996.319998"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/12518"},{"key":"e_1_2_1_19_1","first-page":"377","volume-title":"Tenth International Conference on Very Large Data Bases, VLDB","author":"Boksenbaum C.","year":"1984","unstructured":"C. Boksenbaum, M. Cart, J. Ferri\u00e9, and J. Pons. Certification by intervals of timestamps in distributed database systems. In Tenth International Conference on Very Large Data Bases, VLDB, pages 377--387. Morgan Kaufmann, 1984."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282502"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2781227"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342636"},{"key":"e_1_2_1_23_1","volume-title":"Third International Symposium on Foundations and Applications of Blockchain","author":"El-Hindi M.","year":"2020","unstructured":"M. El-Hindi, S. Karrer, G. Doci, and C. Binnig. TrustDBle: Towards trustable shared databases. In Third International Symposium on Foundations and Applications of Blockchain, 2020."},{"key":"e_1_2_1_24_1","volume-title":"9th Biennial Conference on Innovative Data Systems Research, CIDR","author":"Gehrke J.","year":"2019","unstructured":"J. Gehrke, L. Allen, P. Antonopoulos, A. Arasu, J. Hammer, J. Hunter, R. Kaushik, D. Kossmann, R. Ramamurthy, S. T. V. Setty, J. Szymaszek, A. van Renen, J. Lee, and R. Venkatesan. Veritas: Shared verifiable databases and tables in the cloud. In 9th Biennial Conference on Innovative Data Systems Research, CIDR, 2019."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-017-1133-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316756"},{"key":"e_1_2_1_27_1","first-page":"489","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Kraska T.","year":"2018","unstructured":"T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 489--504. ACM, 2018."},{"key":"e_1_2_1_28_1","volume-title":"The 18th International Conference on Principles of Distributed Systems","author":"Kulkarni S.","year":"2014","unstructured":"S. Kulkarni, M. Demirbas, D. Madeppa, A. Bharadwaj, and M. Leone. Logical physical clocks and consistent snapshots in globally distributed databases. In The 18th International Conference on Principles of Distributed Systems, 2014."},{"key":"e_1_2_1_29_1","first-page":"121","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Li F.","year":"2006","unstructured":"F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin. Dynamic authenticated index structures for outsourced databases. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 121--132. ACM, 2006."},{"key":"e_1_2_1_30_1","first-page":"121","volume-title":"6th Symposium on Operating System Design and Implementation (OSDI)","author":"Li J.","year":"2004","unstructured":"J. Li, M. N. Krohn, D. Mazi\u00e8res, and D. E. Shasha. Secure untrusted data repository (SUNDR). In 6th Symposium on Operating System Design and Implementation (OSDI), pages 121--136. USENIX Association, 2004."},{"key":"e_1_2_1_31_1","first-page":"21","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Lim H.","year":"2017","unstructured":"H. Lim, M. Kaminsky, and D. G. Andersen. Cicada: Dependably fast multi-core in-memory transactions. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 21--35. ACM, 2017."},{"key":"e_1_2_1_32_1","first-page":"1718","volume-title":"36th IEEE International Conference on Data Engineering, ICDE","author":"Lin Q.","year":"2020","unstructured":"Q. Lin, K. Yang, T. T. A. Dinh, Q. Cai, G. Chen, B. C. Ooi, P. Ruan, S. Wang, Z. Xie, M. Zhang, and O. Vandans. Forkbase: Immutable, tamper-evident storage substrate for branchable applications. In 36th IEEE International Conference on Data Engineering, ICDE, pages 1718--1721. IEEE, 2020."},{"key":"e_1_2_1_33_1","first-page":"631","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Ma L.","year":"2018","unstructured":"L. Ma, D. V. Aken, A. Hefny, G. Mezerhane, A. Pavlo, and G. J. Gordon. Query-based workload forecasting for self-driving database management systems. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 631--645. ACM, 2018."},{"issue":"5","key":"e_1_2_1_34_1","first-page":"329","article-title":"Maat: Effective and scalable coordination of distributed transactions in the cloud","volume":"7","author":"Mahmoud H. A.","year":"2014","unstructured":"H. A. Mahmoud, V. Arora, F. Nawab, D. Agrawal, and A. E. Abbadi. Maat: Effective and scalable coordination of distributed transactions in the cloud. PVLDB, 7(5):329--340, 2014.","journal-title":"PVLDB"},{"key":"e_1_2_1_35_1","volume-title":"Whitepaper","author":"McConaghy T.","year":"2018","unstructured":"T. McConaghy, R. Marques, A. M\u00fcller, D. D. Jonghe, T. McConaghy, G. McMullen, R. Henderson, S. Bellemare, and A. Granzotto. Bigchaindb: A scalable blockchain database. Whitepaper, 2018."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2018.09.067"},{"key":"e_1_2_1_37_1","first-page":"235","volume-title":"Proceedings of the ACM Symposium on Applied Computing, SAC","author":"Nascimento M. A.","year":"1998","unstructured":"M. A. Nascimento and J. R. O. Silva. Towards historical r-trees. In Proceedings of the ACM Symposium on Applied Computing, SAC, pages 235--240. ACM, 1998."},{"key":"e_1_2_1_38_1","first-page":"685","volume-title":"Proceedings of the 23rd Annual ACM Conference on Multimedia Conference, MM","author":"Ooi B. C.","year":"2015","unstructured":"B. C. Ooi, K. Tan, S. Wang, W. Wang, Q. Cai, G. Chen, J. Gao, Z. Luo, A. K. H. Tung, Y. Wang, Z. Xie, M. Zhang, and K. Zheng. SINGA: A distributed deep learning platform. In Proceedings of the 23rd Annual ACM Conference on Multimedia Conference, MM, pages 685--688. ACM, 2015."},{"key":"e_1_2_1_39_1","volume-title":"An empirical analysis of deep learning for cardinality estimation. CoRR, abs\/1905.06425","author":"Ortiz J.","year":"2019","unstructured":"J. Ortiz, M. Balazinska, J. Gehrke, and S. S. Keerthi. An empirical analysis of deep learning for cardinality estimation. CoRR, abs\/1905.06425, 2019."},{"key":"e_1_2_1_40_1","first-page":"238","volume-title":"IEEE Symposium on Security and Privacy, SP","author":"Parno B.","year":"2013","unstructured":"B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE Symposium on Security and Privacy, SP, pages 238--252. IEEE Computer Society, 2013."},{"key":"e_1_2_1_41_1","first-page":"251","volume-title":"9th USENIX Symposium on Operating Systems Design and Implementation, OSDI","author":"Peng D.","year":"2010","unstructured":"D. Peng and F. Dabek. Large-scale incremental processing using distributed transactions and notifications. In 9th USENIX Symposium on Operating Systems Design and Implementation, OSDI, pages 251--264. USENIX Association, 2010."},{"key":"e_1_2_1_42_1","first-page":"637","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Peng Y.","year":"2020","unstructured":"Y. Peng, M. Du, F. Li, R. Cheng, and D. Song. FalconDB: Blockchain-based collaborative database. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 637--652. ACM, 2020."},{"key":"e_1_2_1_43_1","volume-title":"Whitepaper","author":"Platz B. M.","year":"2017","unstructured":"B. M. Platz, A. Filipowski, and K. Doubleday. Flureedb: a practical decentralized database. Whitepaper, 2017."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329775"},{"key":"e_1_2_1_45_1","volume-title":"Blockchains and distributed databases: a twin study. CoRR, abs\/1910.01310","author":"Ruan P.","year":"2019","unstructured":"P. Ruan, G. Chen, T. T. A. Dinh, Q. Lin, D. Loghin, B. C. Ooi, and M. Zhang. Blockchains and distributed databases: a twin study. CoRR, abs\/1910.01310, 2019."},{"key":"e_1_2_1_46_1","volume-title":"Revealing every story of data in blockchain systems. ACM SIGMOD Record, special issue for SIGMOD Research Highlight Award","author":"Ruan P.","year":"2020","unstructured":"P. Ruan, A. Dinh, Q. Lin, M. Zhang, G. Chen, and B. C. Ooi. Revealing every story of data in blockchain systems. ACM SIGMOD Record, special issue for SIGMOD Research Highlight Award, 2020."},{"key":"e_1_2_1_47_1","first-page":"253","volume-title":"Proceedings of the 21th USENIX Security Symposium","author":"Setty S. T. V.","year":"2012","unstructured":"S. T. V. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish. Taking proof-based verified computation a few steps closer to practicality. In Proceedings of the 21th USENIX Security Symposium, pages 253--268. USENIX Association, 2012."},{"key":"e_1_2_1_48_1","volume-title":"Scheduling OLTP transactions via machine learning. CoRR, abs\/1903.02990","author":"Sheng Y.","year":"2019","unstructured":"Y. Sheng, A. Tomasic, T. Sheng, and A. Pavlo. Scheduling OLTP transactions via machine learning. CoRR, abs\/1903.02990, 2019."},{"key":"e_1_2_1_49_1","volume-title":"Veritasdb: High throughput key-value store with integrity. IACR Cryptology ePrint Archive","author":"Sinha R.","year":"2018","unstructured":"R. Sinha and M. Christodorescu. Veritasdb: High throughput key-value store with integrity. IACR Cryptology ePrint Archive, 2018:251, 2018."},{"key":"e_1_2_1_50_1","first-page":"1493","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Taft R.","year":"2020","unstructured":"R. Taft, I. Sharif, A. Matei, N. VanBenschoten, J. Lewis, T. Grieger, K. Niemi, A. Woods, A. Birzin, R. Poss, P. Bardea, A. Ranade, B. Darnell, B. Gruneir, J. Jaffray, L. Zhang, and P. Mattis. Cockroachdb: The resilient geo-distributed SQL database. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 1493--1509. ACM, 2020."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231762"},{"issue":"2","key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3003665.3003669","article-title":"Database meets deep learning: Challenges and opportunities","volume":"45","author":"Wang W.","year":"2016","unstructured":"W. Wang, M. Zhang, G. Chen, H. V. Jagadish, B. C. Ooi, and K. Tan. Database meets deep learning: Challenges and opportunities. SIGMOD Record, 45(2):17--22, 2016.","journal-title":"SIGMOD Record"},{"key":"e_1_2_1_53_1","volume-title":"A secure decentralised generalised transaction ledger","author":"Wood D. D.","year":"2014","unstructured":"D. D. Wood. Ethereum: A secure decentralised generalised transaction ledger. 2014."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00062"},{"key":"e_1_2_1_55_1","first-page":"1223","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Wu Y.","year":"2019","unstructured":"Y. Wu, J. Yu, Y. Tian, R. Sidle, and R. Barber. Designing succinct secondary indexing mechanism by exploiting column correlations. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 1223--1240. ACM, 2019."},{"key":"e_1_2_1_56_1","first-page":"141","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Xu C.","year":"2019","unstructured":"C. Xu, C. Zhang, and J. Xu. vchain: Enabling verifiable boolean range queries over blockchain databases. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 141--158. ACM, 2019."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0113-2"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_59_1","first-page":"925","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Yue C.","year":"2020","unstructured":"C. Yue, Z. Xie, M. Zhang, G. Chen, B. C. Ooi, S. Wang, and X. Xiao. Analysis of indexing structures for immutable data. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 925--935. ACM, 2020."},{"key":"e_1_2_1_60_1","first-page":"842","volume-title":"35th IEEE International Conference on Data Engineering, ICDE","author":"Zhang C.","year":"2019","unstructured":"C. Zhang, C. Xu, J. Xu, Y. Tang, and B. Choi. Gem2-tree: A gas-efficient structure for authenticated range queries in blockchain. In 35th IEEE International Conference on Data Engineering, ICDE, pages 842--853. IEEE, 2019."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2427795"},{"key":"e_1_2_1_62_1","first-page":"415","volume-title":"Proceedings of the International Conference on Management of Data, SIGMOD","author":"Zhang J.","year":"2019","unstructured":"J. Zhang, Y. Liu, K. Zhou, G. Li, Z. Xiao, B. Cheng, J. Xing, Y. Wang, T. Cheng, L. Liu, M. Ran, and Z. Li. An end-to-end automatic cloud database tuning system using deep reinforcement learning. In Proceedings of the International Conference on Management of Data, SIGMOD, pages 415--432. ACM, 2019."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.43"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","first-page":"1480","DOI":"10.1145\/2810103.2813711","volume-title":"Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security","author":"Zhang Y.","year":"2015","unstructured":"Y. Zhang, J. Katz, and C. Papamanthou. Integridb: Verifiable SQL for outsourced databases. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1480--1491. ACM, 2015."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12652-018-0757-8"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3415478.3415567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T02:13:22Z","timestamp":1758075202000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3415478.3415567"}},"subtitle":["a verifiable database system"],"short-title":[],"issued":{"date-parts":[[2020,8]]},"references-count":65,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.14778\/3415478.3415567"],"URL":"https:\/\/doi.org\/10.14778\/3415478.3415567","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,8]]}}}