Efficient Batch Opening Schemes for Merkle Tree Commitment with Applications to Trustless Cross-chain Bridge

Abstract

In blockchain systems, Merkle trees represent a fundamental cryptographic structure for verifying the validity of public keys in digital signatures. However, the verification process presents significant computational challenges, particularly when dealing with large-scale public key participation in signing operations. This paper focuses on addressing the efficiency bottlenecks in public key validity verification within Merkle tree commitments, with particular emphasis on their application in trustless cross-chain bridge protocols. While existing cross-chain solutions predominantly rely on zero-knowledge proofs for blockchain state validation, the inherent computational cost of proof generation remains prohibitive.We present a novel batch opening scheme for Merkle tree commitments that synergistically integrates Merkle tree construction from permutation arguments to verify the membership of extensive leaf sets. Our approach demonstrates remarkable proof generation efficiency advantages, particularly maintaining consistent performance regardless of the number of opened leaves, given a fixed tree depth. Our methods significantly reduce the computational overhead associated with public key validity verification. Meanwhile, it is fully applicable to the existing classical Merkle tree structure without any modifications and has universality.To demonstrate the practicality and efficiency of our scheme, We implemented the Merkle tree opening circuit for three hash functions (Poseidon, Rescue and Keccak) based on our scheme. Our evaluation shows that the batch opening scheme achieves better performance: proof generation time begins to shorten from an opening ratio of 0.25, achieving a 3.5 to 7.1× improvement at a ratio of 0.75 (with tree depth = 9). Similar improvements are also reflected in the proof size and verification time. Moreover, as tree depth increases, our method’s performance advantages become more pronounced.