In our last post, we talked about how Cairo solves two of the three gas-consuming actions on Ethereum – computation and transmission – and promised to talk about the third, storage, in a separate post. Well, we are nothing if not people who honor their commitments. (Yes, that’s a pun on Merkle roots).
The Problems with Storage
The way users interact with storage on Ethereum today is pretty simple – you write something to an address, and then you can go back and read it. Writing is expensive, reading is (relatively) cheap. So if you need to update the stored state infrequently, it might not be a big issue, but when you face frequent state updates, storage can become quite expensive.
The problem with Cairo and storage is that Cairo is stateless – meaning any Cairo run is independent of an external state, and of other Cairo runs (in the future, there may be some stateful version of Cairo, but we’re not there yet). The statelessness of Cairo has the great benefit of making any proof of a Cairo statement true absolutely, regardless of any chronological constraints. This allows for ordering proofs in any order we want, creating multiple proofs concurrently and other nice features. The downside of statelessness is that once we need to work with statements that involve state, it becomes more tricky. In this post we will discuss how we do that.
Cairo & Storage
The basic idea is to keep the state stored on Ethereum, but to “compress” it to a single Ethereum word (32 bytes).
Compressing State
One way to compress the state (which is the way we do it) is via a data structure called a Merkle Tree. If you’re already familiar with the concept, skip to the next paragraph. Otherwise, read on.
A Merkle tree is a cryptographic primitive that allows “compressing” data of an arbitrary size to a very short value. It works as follows: you take an array of values (usually of size which is a power of 2, say 2𝑘) and you compute the hashes of pairs of values so that you obtain 2𝑘/2=2𝑘−1 hashes. You repeat this step once more to obtain 2𝑘−2 hashes, and continue for a total of 𝑘 steps, which results in one hash, called “the Merkle root”. The important property of Merkle trees is that given the Merkle root of an array of values, it is not feasible to find a different array of the same size with the same Merkle root. This way the Merkle root not only commits all of the tree’s data – it’s not possible to change even one value in the original array without changing the Merkle root.
Using Merkle trees, we are able to “store” (i.e., commit to) millions of values using a single Ethereum word (32 bytes). It’s important to know that Merkle root compression is a one-way deal – you cannot uncompress it and get the values if you’re only given the root. This means that anyone who wishes to perform actions on the full state, needs to have access to it – somewhere off-chain. We will not get into the whole data availability debate here – it’s out of scope, but there are solutions for making sure the state is available publicly.
The Voting System Example
Last week we updated the Cairo documentation with a new tutorial – writing a simple voting system in Cairo. Conveniently, it’s a really good example of how Cairo works with applications that require state, and therefore is a good working example for our purpose here.
Let’s describe it briefly: we are implementing a simple, secure, non-anonymous voting mechanism, where there are a million voters who are represented by their public keys. Each voter can vote only once – either yes or no.
Now, let’s say a new batch of votes has just arrived and we want to count them and update the state accordingly. Our Cairo program will calculate the new Merkle root, representing the new state of voters, and output the number of yes and no votes in the batch and the two roots – both the old one and the new one.
The SHARP (our SHARed Prover) will now generate a STARK proof that asserts these 2 roots represent a valid state transition with the given vote counts, and will write a fact on chain – a stamp of approval that this new root is a true and valid representation of the state after this recent batch of votes (to refresh your memory on how the SHARP works and how proofs prove the computational integrity of Cairo programs, go to our last post).
We will now call a function implemented as part of our dapp’s Solidity smart contract on Ethereum called “update state”, with the new root as an input. This function will do three things: it will check that this new root is valid by checking that there’s a fact attesting to it (the fact the SHARP just wrote to the chain, which means the transition was proven to be valid), it will update this new root on-chain instead of the old root, and it will update the yes and no counts. The new votes are now committed on-chain and are (implicitly) part of Ethereum’s state.
Saving on Storage
Implementing what we just described purely with Solidity would have been a pretty expensive exercise. To make sure we prevent double-voting, we would have been forced to keep each and every voter’s vote in storage, and change it once they voted. With a million voters, that would have translated into a million storage-writing transactions. That’s expensive.
With Cairo we could, theoretically, write to storage just once for each “election” (since a single proof can attest to the validity of as many votes as needed). But even assuming we would be batching the votes into groups of 10,000 (committing each batch to the state with a seperate proof), we would still need to write to storage only 100 times – making the Cairo/Solidity hybrid a few orders of magnitude cheaper than the pure-solidity approach.
If you find the Cairo/Solidity hybrid interesting (and we assume you do, having read this post to the end), we will be publishing a step-by-step tutorial soon, walking you through everything you need to know to get a Cairo/Solidity voting dapp up and running. In the meantime – try following the Cairo voting system tutorial. And as always, if you have any questions, ideas, or problems – talk to us over at the Cairo devs discord server.