To understand what an MMR is, we have to first understand the concept of Merkle trees.
Skip to MMRMerkle tree is a balanced binary tree, in which values are stored in leaves and every other node is a hash of its children. The structure guarantees that (provided that cryptographic hash function is used) changing value of any leaf, changes (with very high probability) the root hash. Therefore, we can think of the root hash as a "representation" of array of elements stored in leaves.
The above is a representation of the Merkle Tree for array [ 4, 12, 7, 1, 23, 6, 41, 7 ]
Now you may think, why create such a complex structure, when we can just hash the whole array and we would get as valid representation of that array as with Merkle Trees. And indeed that isn't necessary unless you want to perform one crucial operation on that structure, which is proving that some value is at the given index in the array.
Let's say we have an array of 8 elements and one person (prover) wants to prove to someone else (verifier) that he knows the value of 5-th element. So the prover is saying "I claim that in this array, 5-th element has a value of 23". To specify which array we are talking about, we can just provide its hash, which, as we mentioned above, is a representation of the whole array. To verify that claim, the verifier needs to compute hash of an array with value 23 at index 5 and compare it with the real array hash. Therefore, the verifier would need to know not only index, value and array hash but also other 7 values, to be able to compute the array hash.
On the other hand, if we use Merkle Tree, to compute the root hash with a certain value at the given index, we only need to know values of sibling nodes on the path from the given leaf to the root. In the example above, to prove that 5-th element has a value of 23, we only need to know values 6, hash(41, 7) and hash(hash(4, 12), hash(7, 1)); and notice that we don't have to compute those hashes, because they are stored in the tree. So with this approach, we only need to hash 3 times, instead of 8 times. This doesn't seem like a big improvement, but it becomes significant when we have a lot of elements. That's because in the first case we need to hash n times, while in the second case we need to hash log(n) times. This means that proving in tree of 1024 elements requires only 10 hashes.
So to sum up, Merkle Trees allow us to prove existence of a value at the given index in the array with much less computation than hashing the whole array. The only downside is that we need to store additional hashes, but this only increases the size of the structure by (approximately) a factor of 2.
Also, the downside of both approaches is that if we want to increase the size of the array, we need to recompute the whole tree/array hash. Moreover, in case of Merkle Trees, number of elements in the tree must always be a power of 2, which means that if we want to add an element to tree of size 16, we need to create a new tree of size 32 and fill remaining 15 elements with some default value. Readers which are familiar with analysis of amortized time complexity and/or implementations of vector (dynamic array) structure, may notice that actually cost of such operation amortizes to O(log n) (cost of updating value of the given element is logarithmic). However, in some cases (especially in programs running on-chain) amortized algorithms aren't desireable, because they can lead to unpredictable costs. This is where Merkle Mountain Ranges come in handy.
Merkle Mountain Range is a data structure that is a sequence of Merkle Trees, where every tree size occurs at most once and trees are arranged in descending order of their size.
For example, a sequence of Merkle Trees of sizes 8, 2 and 1 (size measured in number of leaves) creates a Merkle Mountain Range with 11 leaves and looks like this.
Nodes are indexed in post-order system, meaning that for every node, its left subtree is indexed first, then right subtree and at the end the node itself. This implies e.g. that in every tree, root has the greatest index, all nodes in left subtree have lower number then those in right subtree and left-most leaf has the smallest index.
Now let's define some terms which will be useful when we get to more details about MMR.
MMR consists of many trees (or mountains). Tree roots are called peaks.
Every tree has a hight, which is number of edges on a path from the root to any leaf. So in this case, the first tree has height 2, second height 1, and third height 0.
Nodes that have no children are called leaves, whereas nodes with children are called inner nodes.
Notice that number of leaves always imply what trees (of what hight) will be present in the mmr.