Full-Stack StarkNet:
Completed code on GitHub here.
UPDATE: Since the time of writing, there has been official guidance and structure developed for fees on StarkNet. Defer to that page for any inconsistencies found here.
We'll keep this one brief. Honestly, before even continuing here, just go read RoboTeddy's post on the topic. No point in regurgitating something already informative yet concise. Some of it may end up outdated as the fee discussion develops furthers, though it's definitely a great set of guidelines to shoot for regardless. We'll know more closer to the v0.8.0 release (expected in March).
Since you're pretty early to the ecosytem, it's likely a good idea to read some of the fee discussion linked above too. Just to get a sense of the current stakeholders and where their heads are at with this pretty impactful topic.
In this post, we'll quickly identify the most expensive part of our application, and try to think of how we might be able to mitigate that.
After going through the post and understanding โ generally โ where our expected costs are going to be, you may be thinking of something in our project that now feels a little suspect. The maxim Computation is Cheap, Writes are Expensive
raises some red flags.
The primary use case of the application, committing a hash to be stored on chain for later auditing, is likely going to be mad expensive. Writing to a new storage slot every time that attest_state()
is called? ๐คฆ
Instead, maybe we should think about challenging the fundamental purpose of storing the hash itself on chainโฆ
T1: Car takes hash of diagnostics (H1), just after stopping at a stop sign
โฆ
T5: Car gets pulled over for "running a stop sign", then wants to prove integrity of locally saved diagnostics that dispute the ticket
So we store (Vehicle ID, T1) = H1
in the smart contract, and later read it back to prove:
T1
, the vehicle attested to state H1
H1
The primary thing we're worried about is the fact that at time T1
, the car committed some state H1
. We don't necessarily care to store that hash on chain. Instead, we only care that if we present some untrusted hash H1_proposed
to the contract, it can return true/false depending on if that hash was committed at T1
.
How would we store enough information to indicate that one fact, without needing to store so much as all the actual time & hash pairs? Perhaps a bloom filter, as suggested in the previously linked post.
An example of a Bloom filter, representing the set {x, y, z} . The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z} , because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.
So even though many writes still take place, there should be a non-negligible overlap in storage slots being updated. If multiple bits in the same felt of storage get updated, within the same batch rolled up to L1, there will be a "Batching Rebate" to discount those writes proportionally.
An excerpt from the article we read at the beginning explains it futher:
If a particular storage slot is written to n times within a single StarkNet batch (~1-4 hours), each write costs only 1/nth as much. This is true even if the writes to the storage slot were caused by different tx, calls from other contracts, etc.
As a cairo dev, you'll often find that a lot of the tools you try to reach forโฆ just don't exist yet. I came across RoboTeddy's suggestion for a bloom filter, but couldn't find an implementation online when looking to refactor our contract. So I did my best to hack one together ๐
First lets jog our memory with a python reference implementation on geeksforgeeks. After playing with that in python for a minute, the general approach should feel intuitive. Just deterministically make K hashes of the item, and flip those bits in an array.
๐ก Tip: You'll likely start to run into some of the warts/complexities of cairo development in this one. Among others, revoked references come to mind. Specifically, they come up when there is branching logic. These can typically be handled by either reorganizing/duplicating some branches, or by making more use of local variables.
To start, we'll import some functions that might be helpful in our implementation. The TRUE
and FALSE
constants are just aliases for felts 1
and 0
, respectively.
Then, we'll stub out the parameters for the data structure:
A user should be able to call bloom_add(42424242)
to add an element to the set. Similarly, they should able to call bloom_check(42424242)
to be check whether we've probably seen the item (res=1
) or definitely have not seen it (res=0
).
A testcase demonstrating the interface:
Let's start by focussing just on the bloom_add
function. To start, we'll keep track of the current total in the filter, and make sure it stays below the rated capacity.
Diving deeper into the primary recursive loop, we're essentially going to start with _add(item, K)
and keep calling _add(item, K-1)
until we get to K=0
. At each step, we'll hash the item
and set the bit_array[index=hash]
to TRUE
.
โจ Exercise: Implement the TODO above using some of the functions we imported at the beginning. You can try to accomplish it with only felts. However, after hitting a few restrictions, you may quickly find that some operations will need Uint256.
(answer hidden below)
Running the test with our bloom_check
section commented out, we should be able to successfully add items.
โจ Exercise: Re-using a lot of the same logic, try implementing
bloom_check()
to get our tests to pass
(answer hidden below)
As you probably figured out, this really isn't that efficient. We're using a full felt of storage for each bit in the bit array. Can you think of a way to condense this? Somehow squeezing multiple bits into a single storage slot?
I gave it a shot here: https://github.com/sambarnes/cairo-bloom. Definitely still needs a ton of work to be production ready.
There are likely plenty more clever tricks that could be applied. If you manage to pack even more bits into a single felt or make improvements in some other way, feel free to make a PR!
One last thing. In order to get a sense of your contract cost, it helps to put some numbers to it. Luckily it's been right in front of us this whole time:
When you run the tests, we should drop into a REPL:
Specifically, we can see the number of steps โ 11978
. Comparatively, when I switch to the our original implementation from this post: 5474
. Around half the length. As expected, we added cheap computation in order to reduce expensive writes.
We're not going to go about re-implementing everything with a bloom filter now. Even still, try to think about how our design might have to change:
That wraps up the series for now! We've introduced most major parts of a typical StarkNet Dapp โ accounts, cairo development, testnet deployment, working with a devnet, and interacting from a frontend with Argent X.
Hopefully you've found this somewhat helpful in getting started :) Feel free to make comments/PRs if you hit roadblocks or think things could be presented in a better way โ