  A Batch Private Information Retrieval (batch-PIR) scheme allows a client to
retrieve multiple data items from a database without revealing them to the
storage server(s). Most existing approaches for batch-PIR are based on batch
codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18),
which incur large storage overheads. In this work, we show that \textit{zero}
storage overhead is achievable for tree-shaped databases. In particular, we
develop TreePIR, a novel approach tailored made for private retrieval of the
set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no
storage redundancy. This type of trees has been widely implemented in many
real-world systems such as Amazon DynamoDB, Google's Certificate Transparency,
and blockchains. Tree nodes along a root-to-leaf path forms the well-known
Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a
fundamental component in state-of-the-art batch-PIR schemes (Angel et al.
S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving
$3\times$ lower total storage and $1.5$-$2\times$ lower computation and
communication costs. Most notably, TreePIR has $8$-$160\times$ lower setup time
and its polylog-complexity indexing algorithm is $19$-$160\times$ faster than
PBC for trees of $2^{10}$-$2^{24}$ leaves.
