  Supply chain traceability refers to product tracking from the source to
customers, demanding transparency, authenticity, and high efficiency. In recent
years, blockchain has been widely adopted in supply chain traceability to
provide transparency and authenticity, while the efficiency issue is
understudied. In practice, as the numerous product records accumulate, the
time- and storage- efficiencies will decrease remarkably. To the best of our
knowledge, this paper is the first work studying the efficiency 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
efficiency. 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.
