user2335: The Cardano blockchain has no global state, this means that shared state needs to be introduced. Is there a design pattern that lets you commit big sets of data to the ledger without storing it? This while still preserving the ability to later retrieve/change the data via proofs?

user2335: You can use Merkle tree's for this! This is an inverted tree like data structure that uses hashes to create a root hash that is uniquely defined by its leafs, the leafs are the nodes in the lowest layer here (1). Thus, with this root hash, you can commit a big set of data by only storing the root hash on the ledger (it is just a byte string).
This data structure also allows you to construct a proof that can prove that a leaf is a member of a Merkle tree, given only its root hash and this proof. These proofs are maximally of size log(n) where n is the number of leafs in the tree. A proof that a leaf is in the tree consists of giving a list of hashes for each layer of the tree. The hashes are not arbitrary, for each layer the hash is chosen that is needed for the path of the leaf that is proven to go up the tree. To visualize this,

Here, the data set is represented by the Tₙ, where n is a letter in the range A - H. The hashes of these Tₙ are Hₙ (these are the leafs). We see for example that going up one layer in the graph combines H_C and H_D into the hash H_{CD}. This combining of paired hashes keeps going until the upper layer is reached, this is the root hash H_{ABCDEFGH}. Note that changing any leaf (swapping leafs or change underlying data T) will result in a different root hash. This is because changing the input of a hash function gives in an entirely different output.
Now, to prove that the red leaf is in the green root, you have to provide for each layer two things. The first thing is a hash of the sibling node that together with the leaf you try to prove goes up the tree. The second thing is the position of these hashes relative to each other, left, or right. So, the proof that T_D is in the dataset with root H_{ABCDEFGH} takes the form.
[left H_C, Left H_{AB}, right H_{EFGH}]

To verify this proof, you can combine the hashes while taking note of the hash order (left or right), and compare it to the root hash.
H_{ABCDEFGH}=Hash(Hash(H_{AB},Hash(H_C,Hash(T_D))),H_{EFGH})


To utilize this structure on the ledger and provide a way to update a leaf using plutus, consider storing the root hash in a datum. This datum represents the commitment to the dataset and should be locked at a script with at least the following logic.
To verifiably update say leaf H_i from state T_i to state T'_i, you provide the validator three things in a redeemer when spending the UTxO that holds the root hash datum. These are the old state of that leaf, a proof that this old state is a member of the tree, and, a new root hash H' that is derived from the updated tree (where the old state of T_i is replaced with T'_i).
The validator only needs to check two things to accept the new root hash as the representation of the newly updated dataset,

The old state T_i is a member of the old root.
Given the new root H' and the proof of step 1, this proofs that the new state T'_i is a member of H'.

If these conditions are met, it is safe to update the datum to hold the root hash of the new state. Note that any arbitrary extra logic can be added to this (like mandating that the new output is sent to the same script address). This protocol works since a proof never contains a hash that is derived from the member you need to proof. So, changing the leaf that is being proved, still makes the proof valid for a root hash that is derived with this new leaf. Any change to other leafs renders this proof invalid.

Some last words, this design pattern is pretty cool as it lets you convert storage requirements to computation requirements on the ledger. Do note that this comes at a cost, that is, it obscures the data availability of the dataset since it is captured only in a hash. If the beginning state is publicly published, the current state of the dataset can be derived in a decentralized way by traversing the chain and logging the transaction that changed the state of the chain. This is cumbersome, but worth it for large databases.
With the new Vasil feature of reference inputs coming up, this method opens the door to exciting solutions! This since you only have to provide/verify a log(n) proof to fetch a leaf to use in some other plutus script. A small disclaimer here, a dataset in one UTxO is not a concurrent solution, splitting it over multiple outputs may be desirable. Moreover, the length of the database is fixed (though you could set entries to null).
I hope you liked this in depth post! You can find an implementation of Merkle trees for plutus here (3).

2335: <p>The Cardano blockchain has no global state, this means that shared state needs to be introduced. Is there a design pattern that lets you commit big sets of data to the ledger without storing it? This while still preserving the ability to later retrieve/change the data via proofs?</p>
 2335: <p>You can use Merkle tree's for this! This is an inverted tree like data structure that uses hashes to create a <em>root hash</em> that is uniquely defined by its leafs, the leafs are the nodes in the lowest layer here <a href="https://en.wikipedia.org/wiki/Merkle_tree" rel="nofollow noreferrer">(1)</a>. Thus, with this root hash, you can commit a big set of data by only storing the root hash on the ledger (it is just a byte string).</p>
<p>This data structure also allows you to construct a proof that can prove that a leaf is a member of a Merkle tree, given only its root hash and this proof. These proofs are maximally of size <code>log(n)</code> where <code>n</code> is the number of leafs in the tree. A proof that a leaf is in the tree consists of giving a list of hashes for each layer of the tree. The hashes are not arbitrary, for each layer the hash is chosen that is needed for the path of the leaf that is proven to go up the tree. To visualize this,
<a href="https://i.stack.imgur.com/4LNki.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4LNki.png" alt="Example of hash tree with proof" /></a></p>
<p>Here, the data set is represented by the <code>Tₙ</code>, where <code>n</code> is a letter in the range <code>A - H</code>. The hashes of these <code>Tₙ</code> are <code>Hₙ</code> (these are the leafs). We see for example that going up one layer in the graph combines <code>H_C</code> and <code>H_D</code> into the hash <code>H_{CD}</code>. This combining of paired hashes keeps going until the upper layer is reached, this is the root hash <code>H_{ABCDEFGH}</code>. Note that changing any leaf (swapping leafs or change underlying data <code>T</code>) will result in a different root hash. This is because changing the input of a hash function gives in an entirely different output.</p>
<p>Now, to prove that the red leaf is in the green root, you have to provide for each layer two things. The first thing is a hash of the sibling node that together with the leaf you try to prove goes up the tree. The second thing is the position of these hashes relative to each other, left, or right. So, the proof that <code>T_D</code> is in the dataset with root <code>H_{ABCDEFGH}</code> takes the form.</p>
<pre><code>[left H_C, Left H_{AB}, right H_{EFGH}]
</code></pre>
<p>To verify this proof, you can combine the hashes while taking note of the hash order (left or right), and compare it to the root hash.</p>
<pre><code>H_{ABCDEFGH}=Hash(Hash(H_{AB},Hash(H_C,Hash(T_D))),H_{EFGH})
</code></pre>
<hr />
<p>To utilize this structure on the ledger and provide a way to update a leaf using plutus, consider storing the root hash in a datum. This datum represents the commitment to the dataset and should be locked at a script with at least the following logic.</p>
<p>To verifiably update say leaf <code>H_i</code> from state <code>T_i</code> to state <code>T'_i</code>, you provide the validator three things in a redeemer when spending the UTxO that holds the root hash datum. These are the old state of that leaf, a proof that this old state is a member of the tree, and, a new root hash <code>H'</code> that is derived from the updated tree (where the old state of <code>T_i</code> is replaced with <code>T'_i</code>).</p>
<p>The validator only needs to check two things to accept the new root hash as the representation of the newly updated dataset,</p>
<ol>
<li>The old state <code>T_i</code> is a member of the old root.</li>
<li>Given the new root <code>H'</code> and the proof of step 1, this proofs that the new state <code>T'_i</code> is a member of <code>H'</code>.</li>
</ol>
<p>If these conditions are met, it is safe to update the datum to hold the root hash of the new state. Note that any arbitrary extra logic can be added to this (like mandating that the new output is sent to the same script address). This protocol works since a proof never contains a hash that is derived from the member you need to proof. So, changing the leaf that is being proved, still makes the proof valid for a root hash that is derived with this new leaf. Any change to other leafs renders this proof invalid.</p>
<hr />
<p>Some last words, this design pattern is pretty cool as it lets you convert storage requirements to computation requirements on the ledger. Do note that this comes at a cost, that is, it obscures the data availability of the dataset since it is captured only in a hash. If the beginning state is publicly published, the current state of the dataset can be derived in a decentralized way by traversing the chain and logging the transaction that changed the state of the chain. This is cumbersome, but worth it for large databases.</p>
<p>With the new Vasil feature of reference inputs coming up, this method opens the door to exciting solutions! This since you only have to provide/verify a <code>log(n)</code> proof to fetch a leaf to use in some other plutus script. A small disclaimer here, a dataset in one UTxO is not a concurrent solution, splitting it over multiple outputs may be desirable. Moreover, the length of the database is fixed (though you could set entries to null).</p>
<p>I hope you liked this in depth post! You can find an implementation of Merkle trees for plutus here <a href="https://github.com/input-output-hk/hydra-poc/tree/master/plutus-merkle-tree" rel="nofollow noreferrer">(3)</a>.</p>
