Consider using a larger branching factor in the Merkle trees for more succinct auth paths

[morganthomas]

No description provided.

[mmaker]

After some more thought:
A Merkle proof with a k-branching factor for N elements leads to $(k-1)\log_k(N)$ proof size, which is minimal for $k=2$. Same goes for invocations of the compression function.

Looking around, another optimization from Kuszmaul (now implemented in Ethereum) has been proposed to improve on this idea, called verkle trees. Informally, each node stores in addition a proof of membership for each of its children. This reduces communication at the price of a more intensive computation, which still seems unfit for your use-case?