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?
3
-
Is this a legit question or did you just want to answer your own question? How/why would you want to commit big sets of data and not have them saved on the ledger? I'm not clear on what you mean by 'commit' without storing to ledger.– MC_Brisbane - JUST PoolAug 22, 2022 at 11:18
-
1I wanted to share my knowledge, it is common on SE. I had this question a few weeks ago and did some research on it, wanted to document it for others. With 'commit' I mean: publicly fix the database in a verifiable manner. Example: If I store a hash of a number onchain, and you try to guess my number, I can later reveal that number, and compare your guess. I committed to the number via its hash and cannot change it.– FermatAug 22, 2022 at 11:32
-
On the topic of why I would want this? Since Cardano only has local state, it is hard to track things, like the number of tokens mint by certain policy. You might want this data onchain for other scripts to use (without the use of oracles). This allows you to introduce such data, its a general design pattern common in crypto. The core idea of this is to use the Cardano blockchain not as a database, but as a ledger to check if things are done in a valid way.– FermatAug 22, 2022 at 11:36
Add a comment
|
1 Answer
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_iis a member of the old root. - Given the new root
H'and the proof of step 1, this proofs that the new stateT'_iis a member ofH'.
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).