TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead

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~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 \textit{TreePIR}, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary \textit{root-to-leaf path} in a Merkle tree with no storage redundancy. This type of tree 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 \textit{Merkle proof}. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel \et~S\&P'18, Mughees-Ren~S\&P'23, Liu \et~S\&P'24), in all metrics, achieving 3×3× lower total storage and 1.51.5-3×3× lower computation and communication costs. Most notably, TreePIR has 88-160×160× lower setup time and its \textit{polylog}-complexity indexing algorithm is 1919-160×160× faster than PBC for trees of 210210-224224 leaves.