ICDE 2022-Ubiquitous Verification in Centralized Ledger Databases.pdf

波风水门

312

14页

8次

2023-05-31

免费下载

Ubiquitous Veriﬁcation in Centralized Ledger

Database

Xinying Yang

†

, Sheng Wang

†

, Feifei Li

†

, Yuan Zhang

, Wenyuan Yan

†

Fangyu Gai

†

, Benquan Yu

, Likai Feng

, Qun Gao

†

, Yize Li

†

{xinying.yang, sh.wang, lifeifei, yuenzhang.zy, daniel.ywy,

gaifangyu.gfy, benquan.ybq, likai.ﬂk, gaoqun, yize.lyz}@alibaba-inc.com

†

Alibaba Group

Ant Group

Abstract—Veriﬁability is the backbone of most ledger sys-

tems to realize credible authentication. However, existing per-

missioned blockchains and centralized ledger databases lack

rigorous veriﬁability to authenticate all facts (i.e., what-when-

who validation). Besides, they suffer from high veriﬁcation cost

to a continually growing immutable storage. In this paper, we

introduce veriﬁcation principles behind LedgerDB, a centralized

ledger database that achieves both strong external auditability

and fast veriﬁcation. We coin a novel concept called Dasein

Veriﬁcation that composes of three validation factors what-when-

who to formalize ledger auditing. Regarding what, LedgerDB

devises fam (fractal accumulating model) to accelerate existence

veriﬁcation, and CM-Tree for efﬁcient lineage veriﬁcation. Veri-

ﬁable data mutations are also supported. For when, we discuss

attacks on existing time pegging protocols that compromise the

authenticity of timestamps, and propose a time notary protocol

to resolve those threats. Evaluations show that fam and CM-Tree

signiﬁcantly outperform traditional approaches. Compared to

Hyperledger Fabric, LedgerDB achieves 23× higher veriﬁcation

throughput with 500× lower latency in notarization applications,

and 3× higher throughput with 300× lower latency in lineage

tracking applications. As a public-cloud ledger service, the end-

to-end veriﬁcation latencies of LedgerDB are on average 50×

and 1000× lower than that of QLDB in the above applications,

respectively.

I. INTRODUCTION

Data veriﬁcation is essential for both decentralized and

centralized ledger technologies. Blockchain is the most in-

demand decentralized ledger technology (DLT) that provides

veriﬁable tamper-evident objects maintained by mutually dis-

trusting participants [1]–[4]. However, in the latest trend,

centralized ledger database (CLD) attracts more and more

attentions back to centralized ledger technology (CLT) [5]–

[8]. CLD systems utilize their representative ‘trust but verify’

methodology to achieve ledger’s integrity assurance and non-

repudiation clearance, but lack external auditability that needs

rigorously veriﬁable authentication. To solve this problem, we

designed LedgerDB [9], a centralized ledger database that

achieves both strong external auditability and fast veriﬁcation.

In our earlier paper [7], we provided an overview of

LedgerDB’s architecture. The key contribution of [7] is to

show that, as a CLD system, LedgerDB not only provides su-

perior write and read performance compared to permissioned

blockchains, but also achieves the same level of auditability

as in permissionless blockchains. In this paper, we focus

on the topic of veriﬁcation mechanisms in our system. We

ﬁrst introduce a new concept called Dasein Veriﬁcation to

better formalize veriﬁcation demands behind a ledger system.

We then explain how LedgerDB becomes the ﬁrst Dasein-

complete CLD system and achieves high veriﬁcation efﬁ-

ciency.

The concept Dasein is introduced by existential philosopher

Martin Heidegger [10], aiming to express the existence of

things (e.g., being and time). Similarly, we use Dasein to

embody the auditability of object existence in LedgerDB. As

the perceptive embodiment in ledger systems, the Dasein of

a piece of electronic data includes three essential elements,

which we call a what-when-who (3w) factorization — exis-

tence veriﬁcation relates to what; time veriﬁcation guarantees

when; and non-repudiation answers the question of who. We

call a ledger system Dasein-complete if all 3w factors of stored

data can be rigorously veriﬁed.

We argue that Dasein-completeness is indispensable to

satisfy real-world judicial auditing [11]–[13] and it covers a

wide range of use cases. For example, consider a national

Grain-Cotton-Oil (GCO) supply chain which involves multiple

corporations such as banks, oil manufacturers, cotton retailers,

suppliers, and grain warehouses. All the participants need to

append their manuscripts, invoice copies, receipts as records

on an auditable ledger. With Dasein-completeness, any record

on the ledger can be auditable by any external parties in terms

of what-when-who. Similarly, such a feature is also required

by many other applications, such as authorship and royalty no-

tarization [14] and luxury merchandise lineage [15]. However,

existing ledger systems fail to reach Dasein-complete, though

each individual factor has already been extensively considered

in many systems. We categorize existing veriﬁcation mecha-

nisms and their limitations related to 3w factors of Dasein

veriﬁcation as follows:

The what. To verify the existence of a transaction,

blockchains usually rely on Merkle trees [16]. Bitcoin [1]

organizes transaction digests from the same block as a Merkle

tree. Hence, a light node can verify transactions using a

simpliﬁed payment veriﬁcation (SPV) approach without down-

loading the entire ledger. Ethereum [2] uses account-based

model and adopts Merkle Patricia Tree (MPT) [17] to verify

all historical balances. Since each data slot on the MPT

path should be maintained, its space overhead is also high.

The Diem blockchain [18] blurs block concept in a Merkle

accumulator model. Each transaction becomes an incremental

leaf node, which generates corresponding Merkle root hash

as its ﬁne-grained tamper proof, rendering high storage and

veriﬁcation overhead. CLD systems such as SQL Ledger [19],

QLDB [20], [21] and Oracle blockchain table [22], [23] also

use simple Merkle tree models that lead to similar problems

above.

The when. Time information is critical for many appli-

cations. However, few ledger systems consider rigorous au-

thenticity of timestamps in their designs. In permissionless

blockchains, timestamps are credible due to the peer-to-peer

architecture, but cannot be used for judicial purposes. Permis-

sioned blockchains like Hyperledger Fabric [24]–[26] fail to

provide credible time for external audit, because timestamps

on the ledger can be tampered when most peers collude.

Regarding CLD systems, QLDB does not consider malicious

behaviors from LSP (ledger service provider), who might

fabricate timestamps. ProvenDB [27] submits transaction di-

gests to a public blockchain (e.g., Bitcoin) periodically to

gain external timestamp evidence. In this case, though LSP

cannot directly tamper with a timestamp, it can still inﬁnitely

delay its actual effective time (as discussed in § III-B1). SQL

Ledger [19] provides forward integrity [28], which assumes

LSP is trusted until the hash of modiﬁcation is securely (and

immutably) stored outside of the systems. This makes them

fail to provide a rigorous when audit.

The who. It is easy for DLT systems to verify the authentic-

ity and non-repudiation of data from a user (in permissionless

blockchain) or an organization (in permissioned blockchain)

using digital signatures. In contrast, since CLD systems like

QLDB and ProvenDB do not consider the moral hazard of the

LSP, the LSP can repudiate for previous request responses by

tampering log data to fabricate a user’s operation (e.g., delete

a journal). This makes them fail to provide a rigorous who

audit.

In summary, Existing DLT systems cannot satisfy Dasein’s

when, while conventional CLD systems cannot satisfy Da-

sein’s when and who. In addition, all mentioned systems are

inefﬁcient in what veriﬁcation, especially for data lineage

veriﬁcation, which is a notable real-world application. To-

wards designing a Dasein-complete CLD system with high

veriﬁcation efﬁciency and low storage overhead, we introduce

ubiquitous veriﬁcation mechanisms adopted in LedgerDB. We

summarize our main contributions as follows:

• We coin a concept of dasein veriﬁcation to formalize what-

when-who validation for ledger databases, which has been

adopted in LedgerDB. To meet all Dasein factors, we

propose an overall framework and speciﬁc mechanisms with

external ledger auditability. To the best of our knowledge,

LedgerDB is the ﬁrst CLD system that provides native

Dasein veriﬁcation (i.e., Dasein-complete) for judicial au-

dit [11]–[13].

• To support fast what veriﬁcation, we devise an advanced

transaction accumulator called fractal accumulating model

(fam) in § III-A to organize journal digests, and further en-

hance it with trusted anchors. For when veriﬁcation, we ﬁrst

introduce attack models that compromise the authenticity of

timestamps in existing time pegging protocols. To achieve

globally credible timestamps in action, we then propose a

time notary protocol called Time Ledger (T-Ledger), which

provides high write throughput and makes above attacks

impractical.

• To enable efﬁcient N-lineage veriﬁcation, we design a

two-layer clue merged tree (CM-Tree) that guarantees the

authenticity of application-level data lineage (§ IV). The

veriﬁcation throughput of CM-Tree is 33× higher than

ccMPT used in [7] and the latency is 24× lower. Advanced

mutation veriﬁcation variants (for purge and occult) are also

provided.

• We conduct empirical evaluation to validate the veriﬁcation

efﬁciency and completeness of LedgerDB. The results show

that LedgerDB provides excellent veriﬁcation throughput

for data notarization and lineage applications, 23× and 3×

higher compared to Hyperledger Fabric. At the same time,

it achieves 500× and 300× lower latency on average. As a

public-cloud ledger service, LedgerDB gets on average 56×

and 1000× lower latency in above applications compared to

QLDB.

The rest of this paper is organized as follows. We ﬁrst give

our motivation and an overview of LedgerDB in § II. We intro-

duce the concept of Dasein veriﬁcation and our corresponding

designs in § III, We describe the Dasein-complete audit in § V

and the N-lineage veriﬁcation mechanism in § IV. We provide

experimental evaluations in § VI. Finally, we discuss related

work in § VII and conclude in § VIII.

II. MOTIVATION AND OVERVIEW

In this section, we ﬁrst introduce veriﬁabilities in existing

ledger systems and their limitations, which motivate the design

of LedgerDB. After that, we present an overview to LedgerDB.

A. Ledger Systems and Limitations

We categorize ledger systems into decentralized ledger

techniques DLT (e.g., blockchain) and centralized ledger tech-

niques CLT (e.g., CLD systems) according to their distinct

architectures. However, from the perspective of veriﬁcation

mechanisms being used, there is no explicit boundary between

DLT and CLD. In particular, all typical ledger systems lever-

age tree-based (e.g., Merkle tree) models to verify integrity

and signature-based models to withstand repudiation. Here we

look into ledger veriﬁcation mechanisms used by both DLT

and CLD systems, and compare them from six dimensions as

summarized in Table I.

• Trusted Dependency. Permissionless blockchains are open

to the public. Anyone can join the network without involving

any central authority. Permissioned blockchains’ participants

are usually pre-registered enterprise-level entities. We call its

trusted dependency as ‘trust the consortium, but not every

single one’. CLD systems follow a centralized architecture.

This allows them to adopt a ‘trust but verify’ approach,

which means users have to fully trust the ledger service

provider (LSP). This brings in several defects when facing

of 14

免费下载

关注

评论