  A sparse Merkle tree is a Merkle tree with fixed height and indexed leaves
given by a map from indices to leaf values. It allows for both efficient
membership and non-membership proofs. It has been widely used as an
authenticated data structure in various applications, such as layer-2 rollups
for blockchains. zkSync Lite, a popular Ethereum layer-2 rollup solution, uses
a sparse Merkle tree to represent the state of the layer-2 blockchain. The
account information is recorded in the leaves of the tree. In this paper, we
study the sparse Merkle tree algorithms presented in zkSync Lite, and propose
an efficient batch update algorithm to calculate a new root hash given a list
of account (leaf) operations. Using the construction in zkSync Lite as a
benchmark, our algorithm 1) improves the account update time from
$\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ and 2) reduces the batch update cost
by half using a one-pass traversal. Empirical analysis of real-world block data
shows that our algorithm outperforms the benchmark by at most 14%.
