  We propose and define a recursive Merkle structure with q-mercurial
commitments, in order to create a concise B-Merkle tree. This Merkle B-Tree
builds on previous work of q-ary Merkle trees which use concise, constant size,
q-mercurial commitments for intranode proofs. Although these q-ary trees reduce
the branching factor and height, they still have their heights based on the key
length, and are forced to fixed heights. Instead of basing nodes on q-ary
prefix trees, the B Merkle Tree incorporates concise intranode commitments
within a self-balancing tree. The tree is based on the ordering of elements,
which requires extra information to determine element placement, but it enables
significantly smaller proof sizes. This allows for much lower tree heights
(directed by the order of elements, not the size of the key), and therefore
creates smaller and more efficient proofs and operations. Additionally, the B
Merkle Tree is defined with subset queries that feature similar communication
costs to non-membership proofs. Our scheme has the potential to benefit
outsourced database models, like blockchain, which use authenticated data
structures and database indices to ensure immutability and integrity of data.
We present potential applications in key-value stores, relational databases,
and, in part, Merkle forests.
