1 High-efﬁciency Blockchain-based Supply Chain Traceability

2025-04-30 0 0 2.33MB 11 页 10玖币

侵权投诉

High-efﬁciency Blockchain-based

Supply Chain Traceability

Hanqing Wu, Shan Jiang, Jiannong Cao, Fellow, IEEE

Abstract—Supply chain traceability refers to product track-

ing from the source to customers, demanding transparency,

authenticity, and high efﬁciency. In recent years, blockchain

has been widely adopted in supply chain traceability to pro-

vide transparency and authenticity, while the efﬁciency issue

is understudied. In practice, as the numerous product records

accumulate, the time- and storage- efﬁciencies will decrease

remarkably. To the best of our knowledge, this paper is the ﬁrst

work studying the efﬁciency issue in blockchain-based supply

chain traceability. Compared to the traditional method, which

searches the records stored in a single chunk sequentially, we

replicate the records in multiple chunks and employ parallel

search to boost the time efﬁciency. However, allocating the record

searching primitives to the chunks with maximized parallelization

ratio is challenging. To this end, we model the records and chunks

as a bipartite graph and solve the allocation problem using a

maximum matching algorithm. The experimental results indicate

that the time overhead can be reduced by up to 85.1% with

affordable storage overhead.

Index Terms—Blockchain traceability; supply chain traceabil-

ity; searchable blockchain.

I. INTRODUCTION

In 2019, the global supply chain market value surpassed

14.6trillion US dollars, having increased at a compound

annual growth rate of 10.8% since 2015 [1]. The supply

chain plays a vital role in the global economy. Supply chain

management, which refers to the ﬂow management of goods

and services, including all the processes that transform raw

materials into ﬁnal products along the supply chain, is essen-

tial for boosting customer services, reducing operation costs,

improving ﬁnancial positions, etc. [2]

Among supply chain management services, traceability is

essential because it allows product tracking from the sources

to end consumers [3]. Supply chain traceability provides

opportunities to enhance the supply chain efﬁciencies, meet the

regulatory requirements, and, most importantly, to story-tell

the consumers about the provenance and journey of products.

Regarding the products whose safety is critical, e.g., food and

pharmaceuticals, supply chain traceability is critical and has

been pursued for decades by the industries [4].

Despite its importance, supply chain traceability is challeng-

ing primarily because of its undue reliance on the collaboration

of multiple stakeholders who are not motivated to collaborate.

Moreover, there is a lack of mechanisms to deﬁne the mini-

mum amount of data required from the stakeholders to achieve

Hanqing Wu, Shan Jiang, and Jiannong Cao were with the Department of

Computing, The Hong Kong Polytechnic University.

Emails: hanqing.91.wu@connect.polyu.hk, cs-shan.jiang@polyu.edu.hk,

jiannong.cao@polyu.edu.hk.

Corresponding author: Shan Jiang.

supply chain traceability. In existing studies, the researchers

focused on modeling supply chain traceability, especially the

data among different stakeholders [5], [6]. The incentives of

collaboration are understudied, letting alone the safety and

quality of the tracing process [7].

In recent years, blockchain has been regarded as a promising

solution for supply chain traceability because of the distinctive

features of immutability, transparency, auditability, and native

support of incentivization [8], [9]. Generally, a blockchain

is an append-only list of blocks, each containing a set of

transactions, maintained by a decentralized peer-to-peer net-

work [10]. The product records stored on the blockchain are

publicly available and cannot be modiﬁed, making the stored

information reliable. The auditability makes it possible to track

product information on a blockchain. Furthermore, blockchain

natively embeds tokens to incentivize collaboration among

supply chain stakeholders. To summarize, blockchain empow-

ers supply chain traceability with high reliability, auditability,

and incentives for collaboration [11]–[13].

Besides the applications of blockchain-based supply chain

traceability in big enterprises such as IBM and Walmart

[14], blockchain solutions for supply chain traceability are

also extensively studied in academia. On the one hand, the

concept of blockchain-based supply chain traceability and

the corresponding system design are discussed in many re-

search works [15]–[19]. On the other hand, the researchers

ﬁnd blockchain technology can be used together with other

technologies, such as the Internet of Things (IoT), to provide

the traceability service [20]–[24]. However, all these works in

industry and academia focus on the design of the traceability

system while leaving the efﬁciency issue alone. In practice,

the time- and storage- efﬁciencies are signiﬁcantly affected

by the considerable and increasing number of product records

generated by the ubiquitous IoT devices.

To the best of our knowledge, this paper is the ﬁrst work

studying high-efﬁciency blockchain-based supply chain trace-

ability. In particular, we demonstrate the system architecture

of a blockchain-based supply chain and model the product

records as a directed acyclic graph. To this end, the traceability

problem is deﬁned as a graph searching problem over the

blockchain. To address the problem, we propose replicating the

product records in multiple chunks in a database and develop-

ing a novel parallel search algorithm based on the maximum

matching algorithm to improve searching efﬁciency signiﬁ-

cantly. The fundamental principle of efﬁciency improvement

lies in sacriﬁcing storage overhead to reduce time overhead.

The key technical depth lies in the matching-based parallel

search algorithm.

arXiv:2210.09202v1 [cs.DC] 17 Oct 2022

The main contributions of this work are as follows:

•To the best of our knowledge, we are the ﬁrst to study and

formally model the high-efﬁciency issue in blockchain-

based supply chain traceability.

•We propose a novel parallel search algorithm based on the

maximum matching algorithm, which signiﬁcantly boosts

product tracking efﬁciency.

•We conduct extensive experiments on the proposed al-

gorithm, which indicates up to 85.1% time reduction for

product tracking.

The rest of this paper is organized as follows. Sec. II

introduces the related work of this work. Sec. III provides the

preliminaries of the problem. In Sec. IV, we explain the system

model and formally deﬁne the problem of high-efﬁciency

blockchain-based supply chain traceability. Sec. V gives the

traditional approach and the proposed algorithm for solving the

traceability problem. Sec. VI demonstrates the experimental

results. Finally, Sec. VII concludes this work and discusses

the future directions.

II. RELATED WORK

In this section, we survey the related work about high-

efﬁciency blockchain-based supply chain traceability, i.e., sup-

ply chain traceability and searching over blockchain, and

articulate the motivations and novelty of this work.

A. Supply Chain Traceability

The research on supply chain traceability can be roughly

divided into two categories, i.e., uniﬁed data representation

methods for various stakeholders along the supply chain,

and digital technologies to facilitate reliable and ubiquitous

information storage.

A large number of stakeholders along the supply chain

have their own data management systems with diversiﬁed

data formats. Supply chain traceability needs to retrieve the

data from the stakeholders, and a uniﬁed data representation

method is demanded. The uniﬁed data representation methods

for supply chain information have been studied for years. In

[6], Bechini et al. investigate the issues for supply chain trace-

ability, introduce a traceability data model and a set of suitable

patterns, discuss the suitable technological standards to deﬁne,

real-world system for food supply chain traceability. In [5],

Hu et al. propose a Uniﬁed Modeling Language (UML) model

for traceability along with a set of suitable patterns, develop

a series of UML class diagrams to conceive a method for

modeling the product, process, and quality information along

the supply chain, and conduct a case study on vegetable supply

chain traceability.

Regarding digital technologies for supply chain traceability,

radio-frequency identiﬁcation (RFID) and blockchain are rep-

resentative. In particular, RFID is a sensing technology that

helps to collect the data along supply chains ubiquitously,

while blockchain is a distributed ledger technology to provide

secure and reliable data storage services.

The usage of RFID in supply chain traceability can be traced

back to as early as 2003 [25], at which time Karkkainen

proposed to develop an RFID-based data capture system to

solve the problems associated with the logistics of short shelf-

life products. In 2007, RFID was widely recognized as a

promising technology for supply chain traceability [4], [26]

because the passive RFID tags on the products are cheap,

do not need to be within the line of sight of the RFID

reader (compared with barcodes), and do not need batteries

(compared with other sensors). Later, there are also surveys

about RFID-enabled supply chain traceability [27]–[29].

The potential of using blockchain technology for supply

chain traceability was investigated by Tian in 2016 for the

ﬁrst time [20], in which a traceability system was designed

for agri-food supply chains combining RFID and blockchain

technologies. Although the work is a pioneer, it is concep-

tual without real-world deployment. We see that the product

information recorded on a blockchain is immutable, i.e., it

cannot be modiﬁed once stored, making the traceability results

reliable. Similar works include [30]–[35] in the supply chains

of construction, wine, etc., some of which are implemented in

real-world settings.

B. Searching over Blockchain

Blockchain-based supply chain traceability requires

blockchain data to be searched given a product item. We

present the related work about searching over blockchain in

this subsection. In particular, searching over blockchain refers

to the process that the users (with no local storage) request

blockchain full nodes (with full storage) to search data on

a blockchain, in which the search requests can be keyword

search, range query, etc. In literature, integrity, privacy, and

efﬁciency are the three concerned performance metrics of

searching over blockchain, in which integrity means whether

the search results are sound and complete, privacy means

whether data leakage happens during searching, and efﬁciency

means the time and communication overhead.

The naive procedure of searching over the blockchain is

as follows. First, the user sends a searching request to a

blockchain full node. Then, the full node proceeds with the

request by scanning the data on the blockchain block by

block and transaction by transaction, and recording all the data

satisfying the searching request. Finally, the full node returns

the search result. As we can see, the integrity of the search

result cannot be guaranteed, the privacy can be disclosed

because of the raw data on the blockchain, and the efﬁciency

is low because scanning transactions one by one takes a long

time. The research community has been developing solutions

to improve integrity, privacy, and efﬁciency.

Smart contracts and veriﬁable computation are the two

approaches to guarantee searching integrity. The basic idea

of the smart contract is to send the searching requests to all

the blockchain nodes rather than a single one. The incentive

mechanism of blockchain will motivate the majority of the

blockchain nodes to return sound and complete search results,

which guarantees integrity. The advantage of using smart con-

tracts is that the method is general and can be easily adapted

to all kinds of data and queries. However, the drawback

lies in the high cost of executing smart contracts. In terms

of veriﬁable computation, the search result returned to the

user will be accompanied by proof for integrity veriﬁcation.

Using veriﬁable computation can ﬁne-tune the efﬁciency by

designing subtle data structure [36]–[41]. In contrast, the

disadvantage is that there is no general data structure for all

types of data and queries.

Searchable encryption is the major approach for privacy

preservation during searching over blockchains. The data,

queries, and search results are encrypted compared with the

naive search approach. The research community has been

developing efﬁcient searchable encryption scheme for various

types of data and queries [42]–[46].

To summarize, the existing studies about blockchain-based

supply chain traceability mainly focus on the system design

while leaving the efﬁciency issue alone. When we reduce

blockchain-based supply chain traceability to a problem of

searching over blockchain, we ﬁnd that the reduced graph

searching problem on blockchains is new.

III. PRELIMINARIES

In this section, we introduce the preliminary knowledge

about blockchain data structure and maximum matching al-

gorithms for bipartite graphs. Note that the maximum match-

ing algorithm is a necessary component for maximizing the

parallelization ratio in Sec. V.

A. Blockchain Data Structure

Block Header

Transactions

Block Header

Transactions

Previous Hash Value

Version Number

Timestamp

Merkle Root

Tx 1 Tx 2

Tx 3 Tx 4

Tx1

Tx2 Tx3 Tx4

H2 H3 H4

H12 =

H(H1+H2)

H34 =

H(H3+H4)

H(H12+H34)

Previous Hash Value

Version Number

Timestamp

Merkle Root

Block Header

Transactions

Block N+1Block NBlock N-1

Fig. 1. Structure of a typical blockchain. The blocks are linked into a chain

using cryptographic hash values.

A blockchain is an append-only list of blocks linked by

cryptographic values, in which each block contains a set

of transactions, maintained by a decentralized peer-to-peer

network [47]. Fig. 1 depicts the structure of blockchain with

description. Speciﬁcally, a single valid block consists of a

block header and a list of transactions. The following ﬁelds

brieﬂy document the block details:

•Block Header provides the important information inside

the block. It includes the Version Number, Previous

Hash Value, Timestamp, Merkle root, etc. Each block

header is hashed, unique, and cryptographically secured,

supporting the immutability property of blockchains. For

example, in Bitcoin [48], “target difﬁculty” and “nonce”

are included as part of the Proof of Work (PoW) consen-

sus algorithm used when mining.

•Version Number indicates which version of block valida-

tion rules to follow. If the block version number differs

from other blocks, it means this block is running on a

different chain, commonly known as a hard fork.

•Previous Hash Value is a byte ﬁeld containing the hash

of the previous block header, serving as a pointer to the

previous block. Such a ﬁeld ensures that no previous

block can be modiﬁed without changing the current block

header, making the whole blockchain difﬁcult and even

impossible to be modiﬁed.

•Timestamp is the time of generating this block which

is more commonly known as the time when the miner

started hashing the current block header. It can be used

to calculate the average block propagation time.

•Merkle root is derived from the hashes of all transactions

included in the current block. It is a tamper resistance

measure that those transactions cannot be modiﬁed with-

out changing the Merkle Root value, furthermore, the

entire header. Merkle root is also a fast and efﬁcient way

to verify the data. In Fig. 1, the Merkle root of block

N+ 1 is computed as the hierarchical hash results upon

the transactions inside.

•Transactions contains the transactions conﬁrmed by the

blockchain network and packed in the block. For exam-

ple, in Bitcoin [48], a typical transaction represents the

money transfer of two or more parties.

B. Maximum Matching

In graph theory, a matching in an undirected graph is a set

of edges without common vertices. The maximum matching

problem is to ﬁnd a matching that uses as many edges as

possible given an undirected graph.

A bipartite graph is a graph whose vertices can be divided

into two disjoint and independent sets Uand Vsuch that every

edge connects a vertex in Uand a vertex in V. The maximum

matching problem on a bipartite graph is well studied and can

be solved efﬁciently (in polynomial time) using the Hungarian

algorithm [49], Ford-Fulkerson algorithm, etc.

IV. SYSTEM MODEL AND PROBLEM DEFINITION

This section ﬁrst gives the system model of the blockchain-

based supply chain and then formally deﬁnes the problem of

high-efﬁciency blockchain-based supply chain traceability.

A. System Model

Fig. 2 elaborates on the system model of the blockchain-

based supply chain. In particular, the stakeholders along the

supply chain, e.g., raw material suppliers, factories, ware-

houses, transportation companies, and retailers, form a peer-

to-peer network and maintain a permissioned blockchain. The

regulatory authorities can also join and expand the blockchain

network. Our system prefers permissioned blockchain to the

public one because the nodes not hosted by the supply chain

stakeholders should be forbidden from joining the blockchain

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1High-efciencyBlockchain-basedSupplyChainTraceabilityHanqingWu,ShanJiang,JiannongCao,Fellow,IEEEAbstractSupplychaintraceabilityreferstoproducttrack-ingfromthesourcetocustomers,demandingtransparency,authenticity,andhighefciency.Inrecentyears,blockchainhasbeenwidelyadoptedinsupplychaintraceabilityt...

展开>> 收起<<

1 High-efﬁciency Blockchain-based Supply Chain Traceability.pdf

共11页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 High-efﬁciency Blockchain-based Supply Chain Traceability

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: