{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T19:19:03Z","timestamp":1788895143083,"version":"build-2803163510"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Blockchain-like ledger databases emerge in recent years as a more efficient alternative to permissioned blockchains. Conventional ledger databases mostly rely on authenticated structures such as the Merkle tree and transparency logs for supporting auditability, and hence they suffer from the performance problem. As opposed to conventional ledger DBMSes, we design VeDB - a high-performance verifiable software (Ve-S) and hardware (Ve-H) enabled DBMS with rigorous auditability for better user options and broad applications. In Ve-S, we devise a novel verifiable Shrubs array (VSA) with two-layer ordinals (serial numbers) which outperforms conventional Merkle tree-based models due to lower CPU and I\/O cost. It enables rigorous auditability through its efficient credible timestamp range authentication method, and fine-grained data verification at the client side, which are lacking in state-of-the-art relational ledger databases. In Ve-H, we devise a non-intrusive trusted affiliation by TEE leveraging digest signing, monotonic counters, and trusted timestamps in VeDB, which supports both data notarization and lineage applications. The experimental results show that VeDB-VSA outperforms Merkle tree-based authenticated data structures (ADS) up to 70\u00d7 and 3.7\u00d7 for insertion and verification; and VeDB Ve-H data lineage verification is 8.5\u00d7 faster than Ve-S.<\/jats:p>","DOI":"10.1145\/3589774","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-27","source":"Crossref","is-referenced-by-count":46,"title":["VeDB: A Software and Hardware Enabled Trusted Relational Database"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2359-9709","authenticated-orcid":false,"given":"Xinying","family":"Yang","sequence":"first","affiliation":[{"name":"ByteDance, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3639-6217","authenticated-orcid":false,"given":"Ruide","family":"Zhang","sequence":"additional","affiliation":[{"name":"ByteDance, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0263-8879","authenticated-orcid":false,"given":"Cong","family":"Yue","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5781-8216","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"ByteDance, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4446-1100","authenticated-orcid":false,"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7347-7634","authenticated-orcid":false,"given":"Qun","family":"Gao","sequence":"additional","affiliation":[{"name":"ByteDance, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4877-473X","authenticated-orcid":false,"given":"Yuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"ByteDance, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6832-525X","authenticated-orcid":false,"given":"Hao","family":"Yang","sequence":"additional","affiliation":[{"name":"ByteDance, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_2_1","unstructured":"Gluchowski Alex Gurkan Kobi Olszewski Marek Tromer Eran and Vlasov Alexander. 2019. Shrubs - A New Gas Efficient Privacy Protocol. https:\/\/archive.devcon.org\/archive\/watch\/5\/shrubs-a-new-gas-efficient-privacy-protocol\/?tab=YouTube"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190538"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386141"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457558"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467797"},{"key":"e_1_2_2_7_1","unstructured":"The Ethereum Association. 2022. PATRICIA MERKLE TREES. https:\/\/ethereum.org\/developers\/docs\/data-structures-and-encoding\/patricia-merkle-trie\/"},{"key":"e_1_2_2_8_1","unstructured":"AWS. 2018. Amazon quantum ledger database (qldb). https:\/\/aws.amazon.com\/qldb"},{"key":"e_1_2_2_9_1","unstructured":"AWS. 2022. Amazon Managed Blockchain. https:\/\/aws.amazon.com\/blockchain"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516681"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536353"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.38"},{"key":"e_1_2_2_13_1","volume-title":"A study of blockchain oracles. arXiv preprint arXiv:2004.07140","author":"Beniiche Abdeljalil","year":"2020","unstructured":"Abdeljalil Beniiche. 2020. A study of blockchain oracles. arXiv preprint arXiv:2004.07140 (2020)."},{"key":"e_1_2_2_15_1","unstructured":"Vitalik Buterin et al. 2014. A next-generation smart contract and decentralized application platform. white paper Vol. 3 37 (2014) 2--1."},{"key":"e_1_2_2_16_1","unstructured":"ByteDance. 2022. Make Your Day - TikTok. https:\/\/www.tiktok.com\/"},{"key":"e_1_2_2_17_1","unstructured":"ByteDance. 2023. Volcengine. https:\/\/github.com\/volcengine"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386712"},{"key":"e_1_2_2_19_1","first-page":"173","article-title":"Practical byzantine fault tolerance","volume":"99","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OSDI, Vol. 99. 173--186.","journal-title":"OSDI"},{"key":"e_1_2_2_20_1","volume-title":"Trusted time and monotonic counters with intel software guard extensions platform services. Online at: https:\/\/software. intel. com\/sites\/default\/files\/managed\/1b\/a2\/Intel-SGX-Platform-Services. pdf","author":"Cen Shanwei","year":"2017","unstructured":"Shanwei Cen and Bo Zhang. 2017. Trusted time and monotonic counters with intel software guard extensions platform services. Online at: https:\/\/software. intel. com\/sites\/default\/files\/managed\/1b\/a2\/Intel-SGX-Platform-Services. pdf (2017)."},{"key":"e_1_2_2_21_1","unstructured":"Alibaba Cloud. 2022. Alibaba Blockchain as a Service. https:\/\/www.alibabacloud.com\/product\/baas"},{"key":"e_1_2_2_22_1","unstructured":"Beijing Internet Court. 2023. Beijing Internet Court. https:\/\/english.bjinternetcourt.gov.cn"},{"key":"e_1_2_2_23_1","unstructured":"Yigal Edery and Rajeev Sharma. 2020. OCP Security Announces version 1.0 specs for Root of Trust. https:\/\/www.opencompute.org\/blog\/ocp-security-announces-version-10-specs-for-root-of-trust"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342636"},{"key":"e_1_2_2_25_1","unstructured":"Zachary Amsden et al. 2019. The Libra Blockchain. The Libra Association. https:\/\/mitsloan.mit.edu\/shared\/ods\/documents?PublicationDocumentID=5859"},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of 11th annual computer security application conference. 241--48","author":"Ferraiolo David","year":"1995","unstructured":"David Ferraiolo, Janet Cugini, D Richard Kuhn, et al. 1995. Role-based access control (RBAC): Features and motivations. In Proceedings of 11th annual computer security application conference. 241--48."},{"key":"e_1_2_2_27_1","volume-title":"Gartner Top 10 Trends in Data and Analytics for","year":"2020","unstructured":"Gartner. 2020. Gartner Top 10 Trends in Data and Analytics for 2020. https:\/\/www.gartner.com\/smarterwithgartner\/gartner-top-10-trends-in-data-and-analytics-for-2020"},{"key":"e_1_2_2_28_1","unstructured":"Sanjay Ghemawat and Jeff Dean. 2014. Leveldb is a fast key-value storage library written at google that provides an ordered mapping from string keys to string values."},{"key":"e_1_2_2_29_1","volume-title":"Corda Technical White Paper","volume":"2016","author":"Hearn Mike","year":"2016","unstructured":"Mike Hearn and Richard Gendal Brown. 2016. Corda: A distributed ledger. Corda Technical White Paper, Vol. 2016 (2016). https:\/\/www.corda.net\/content\/corda-technical-whitepaper.pdf"},{"key":"e_1_2_2_30_1","unstructured":"IBM. 2021. CODEPAGE option syntax. https:\/\/www.ibm.com\/docs\/en\/cobol-zos\/6.3?topic=options-codepage"},{"key":"e_1_2_2_31_1","unstructured":"IBM. 2022. IBM Blockchain. https:\/\/www.ibm.com\/blockchain"},{"key":"e_1_2_2_32_1","unstructured":"R Intel. 2020. Software guard extensions sdk developer reference for linux* os. (2020)."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303951"},{"key":"e_1_2_2_34_1","volume-title":"Verkle Trees","volume":"1","author":"Kuszmaul John","year":"2019","unstructured":"John Kuszmaul. 2019. Verkle trees. Verkle Trees, Vol. 1 (2019)."},{"key":"e_1_2_2_35_1","unstructured":"SQL Maria. 2021. Why Oracle Implement Blockchain in the Database. https:\/\/sqlmaria.com\/2021\/03\/03\/why-oracle-implement-blockchain-in-the-database"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1076-8"},{"key":"e_1_2_2_37_1","volume-title":"28th USENIX Security Symposium (USENIX Security 19)","author":"Matetic Sinisa","year":"2019","unstructured":"Sinisa Matetic, Karl W\u00fcst, Moritz Schneider, Kari Kostiainen, Ghassan Karame, and Srdjan Capkun. 2019. $$BITE$$: Bitcoin lightweight client privacy using trusted execution. In 28th USENIX Security Symposium (USENIX Security 19). 783--800."},{"key":"e_1_2_2_38_1","volume-title":"Troy McConaghy, Greg McMullen, Ryan Henderson, Sylvain Bellemare, and Alberto Granzotto.","author":"McConaghy Trent","year":"2016","unstructured":"Trent McConaghy, Rodolphe Marques, Andreas M\u00fcller, Dimitri De Jonghe, Troy McConaghy, Greg McMullen, Ryan Henderson, Sylvain Bellemare, and Alberto Granzotto. 2016. Bigchaindb: a scalable blockchain database. white paper, BigChainDB (2016)."},{"key":"e_1_2_2_39_1","volume-title":"Secure communications and asymmetric cryptosystems","author":"Merkle Ralph C","unstructured":"Ralph C Merkle. 2019. Protocols for public key cryptosystems. In Secure communications and asymmetric cryptosystems. Routledge, 73--104."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578855.2535851"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.4018\/IJCAC.2020070103"},{"key":"e_1_2_2_42_1","volume-title":"Quorum whitepaper","author":"Morgan JP","year":"2016","unstructured":"JP Morgan. 2016. Quorum whitepaper. New York: JP Morgan Chase (2016)."},{"key":"e_1_2_2_43_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review (2008). https:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"e_1_2_2_44_1","unstructured":"National University of Singapore. 2022. Ledger Database. https:\/\/github.com\/nusdbsystem\/LedgerDatabase"},{"key":"e_1_2_2_45_1","unstructured":"The Horizon 2020 Framework Programme of the European Union. 2020. Everything you need to know about the Right to be forgotten. https:\/\/gdpr.eu\/right-to-be-forgotten"},{"key":"e_1_2_2_46_1","volume-title":"2018 USENIX Annual Technical Conference (USENIX ATC 18)","author":"Oleksenko Oleksii","year":"2018","unstructured":"Oleksii Oleksenko, Bohdan Trach, Robert Krahn, Mark Silberstein, and Christof Fetzer. 2018. Varys: Protecting $$SGX$$ Enclaves from Practical $$Side-Channel$$ Attacks. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 227--240."},{"key":"e_1_2_2_47_1","unstructured":"Oracle. 2022. Blockchain Tables in Oracle Database 21c. https:\/\/oracle-base.com\/articles\/21c\/blockchain-tables-21c"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00025"},{"key":"e_1_2_2_51_1","volume-title":"Provendb: A blockchain enabled database service. https:\/\/provendb.com\/litepaper","year":"2020","unstructured":"Provendb. 2020. Provendb: A blockchain enabled database service. https:\/\/provendb.com\/litepaper"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342632"},{"key":"e_1_2_2_54_1","volume-title":"Veritasdb: High throughput key-value store with integrity. Cryptology ePrint Archive","author":"Sinha Rohit","year":"2018","unstructured":"Rohit Sinha and Mihai Christodorescu. 2018. Veritasdb: High throughput key-value store with integrity. Cryptology ePrint Archive (2018)."},{"key":"e_1_2_2_55_1","volume-title":"Andrew Yashchuk Sprague, and Dustin Byington","author":"Snow Paul","year":"2014","unstructured":"Paul Snow, Brian Deery, Jack Lu, David Johnston, Peter Kirby, Andrew Yashchuk Sprague, and Dustin Byington. 2014. Business processes secured by immutable audit trails on the blockchain. Brave New Coin (2014)."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_2"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00064"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0052"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57959-7"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833604"},{"key":"e_1_2_2_61_1","volume-title":"Timber-v: Tag-isolated memory bringing fine-grained enclaves to risc-v.. In NDSS.","author":"Weiser Samuel","year":"2019","unstructured":"Samuel Weiser, Mario Werner, Ferdinand Brasser, Maja Malenko, Stefan Mangard, and Ahmad-Reza Sadeghi. 2019. Timber-v: Tag-isolated memory bringing fine-grained enclaves to risc-v.. In NDSS."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140659.3080208"},{"key":"e_1_2_2_63_1","unstructured":"Wikepedia. 2022. Hangzhou Internet Court. https:\/\/en.wikipedia.org\/wiki\/Hangzhou_Internet_Court"},{"key":"e_1_2_2_64_1","unstructured":"Wikimedia. 2021. Block Range Index. https:\/\/en.wikipedia.org\/wiki\/Block_Range_Index"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300083"},{"key":"e_1_2_2_66_1","first-page":"628","article-title":"Blockchain-based music originality analysis method and apparatus","volume":"10","author":"Yang Xinying","year":"2020","unstructured":"Xinying Yang. 2020. Blockchain-based music originality analysis method and apparatus. US Patent 10,628,485.","journal-title":"US Patent"},{"key":"e_1_2_2_67_1","volume-title":"Ubiquitous Verification in Centralized Ledger Database. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE","author":"Yang Xinying","year":"2022","unstructured":"Xinying Yang, Sheng Wang, Feifei Li, Yuan Zhang, Wenyuan Yan, Fangyu Gai, Benquan Yu, Likai Feng, Qun Gao, and Yize Li. 2022. Ubiquitous Verification in Centralized Ledger Database. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1808--1821."},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415540"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415567"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589774","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:22Z","timestamp":1750182562000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589774"],"URL":"https:\/\/doi.org\/10.1145\/3589774","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}