We have implemented a new cryptographic data structure called Merkle Mountain Ranges (MMRs) in Cairo, a blockchain platform that aims to provide efficient and verifiable data storage. MMRs can be considered a list of Merkle Trees, where each tree is represented as a mountain, and the whole list forms the range.
MMRs share the common properties of Merkle Trees, such as the efficiency in data storage and the ability to generate Merkle proofs to prove the existence of an element in the tree. However, they also add some additional benefits, such as efficient appending and updating of elements.
By implementing this new data structure in Cairo, we aim to enhance the efficiency and verifiability of data storage on the platform, making it useful for various applications that require on-chain data storage and verification.
We use this for our optimistic commitments inbox. To access the state from different chains, we need to access the block headers, from which we can retrieve all sorts of information (including the state). We have various strategies to get the block headers across different chains, one of which is an MPC protocol that runs a threshold ECDSA signature algorithm. The protocol output is a single signature that will be validated on-chain. This is better than having one signature per party, which is possible due to a DKG ceremony (distributed key generation).