Nitro uses general-purpose compression to reduce cost. Here’s a quick summary of how we do that and some research issues it raises.
As a rollup, Nitro puts transactions’ calldata on the L1 chain as Ethereum calldata. This is typically done in large batches, which are put together by the Sequencer. A batch might be 100 kilobytes or more.
It’s fine to compress these batches, in order to reduce the cost of posting them on L1, as long as the L2 code can use a deterministic algorithm to decompress and recover the original transaction data. (After decompressing, the L2 code will check users’ signatures on the decompressed transactions, to ensure the integrity of the transactions.)
In the original Arbitrum software stack, we used a home-brew compression scheme to compress individual transactions. This helped, but we knew we could do better.
In Nitro, we use brotli, a well-known general purpose compression method, to compress each batch. Because batches are fairly large, this can make batches much smaller. We looked at some other general-purpose compressors, such as zlib, but chose brotli because it looks to get the most effective compression of the algorithms that are practical for a rollup.
One of the interesting research questions that arises is how much to charge each user tx for its calldata. If we compress a batch of many transactions, and achieve a factor of (say) 3 reduction in size, do we charge each transaction for 1/3 of its uncompressed calldata size? Or do we somehow try to figure out which transactions deserve more credit for the compressibility of the batch, and give them a better deal? And what does it even mean for a transaction to “deserve credit” for making other transactions more compressible? (This can be defined theoretically but the obvious formal definitions will be too expensive to evaluate trustlessly in practice.)
167 Likes
Really interesting! Thanks for sharing! In your example charging each transaction 1/3 of the price is probably the easiest way to reduce transaction cost fast short term. If other more complicated methods turn out to be cheaper overall, it is obviously something that should be considered long term.
56 Likes
Agree that pricing proportionally to decompressed data size is a reasonable approach.
A drawback of that approach is that in the common case where transaction batches are large, individual senders don’t have much incentive to make their transactions more compressible. If your tx is in a batch of 100, and you make your tx twice as compressible, your cost will only decrease by 0.5%. You’ll have to share the benefits of your improvement with 99 other senders. Ideally, we’d like to give stronger incentives to senders to contribute to better compressibility.
49 Likes
True, though evaluating each transaction compressablility individually might result in a bigger overhead(in terms of computing resources). Including the overhead it might not be worth it even though considering stronger incentives. After all it is a topic worth researching.
33 Likes
Yes, there are some interesting tradeoffs and design challenges in figuring out how to generate better incentives efficiently.
30 Likes
I think that in an fair system, each transaction pays gas approximately equal its share of the overhead of posting calldata on L1. How to implement this under compression is an interesting design space. Although the compression ratio is a useful metric, it may not perfectly track the real scaling gains due to reduction in gas costs after compression. The gas cost of calldata inclusion on L1 is a two dimensional function that depends both on the number of nonzero bytes and the number of zero bytes in the calldata. EIP-2028 specifies that the gas cost of L1 calldata is 4 gas per zero byte and 16 gas per non-zero byte. We can define a simple cost ratio of pre/post compressed batches using these parameters.
u_zeros = count_zeros(uncompressed)
u_nonzeros = len(uncompressed) - u_zeros
c_zeros = count_zeros(compressed)
c_nonzeros = len(compressed) - c_zeros
cost_ratio = (u_zeros + 4 * u_nonzeros) / (c_zeros + 4 * c_nonzeros)
Although the specific brotli settings that are default to Google’s python implementation may not match Nitro’s settings, I used python to simulate the change in calldata size and the change in calldata gas cost before and after compression. I retrieved a sample of batched calldata from this transaction.
Notably, gas savings are potentially lower than space savings. In the simple scheme of reducing a user’s calldata pricing by the compression ratio, users may collectively underpay for the real costs of posting the calldata to L1. In other words, compression has a dynamic gas efficiency depending on the contents of the data being compressed. In the rare event that two compressed batches have the exact same length, if they have mismatched quantities of zero bytes, then they will have different cost ratios.
The cost ratio described here is a rough estimation ignoring the associated gas costs of evm execution to process the calldata batch. More refined results may be more or less dramatic. I compressed the entire function call to addSequencerL2BatchFromOrigin beyond the function selector, whereas in practice maybe only the bytes sequence of concatenated transaction calldatas is compressed (I’m just guessing without understanding how Nitro does compression specifically).
I think that this rough data justifies exploring a different metric than compression ratio to determine individual calldata gas costs. Something like 33k batch events have been emitted in block range (13318918, 14413651). I’m interested in studying more relationships in this dataset. For example, I’m curious to see plots of the compression ratio vs batch number and cost ratio vs batch number.
Understanding the true cost of including compressed calldata batches on L1 seems foundational to assigning costs to user’s calldata, because we can use total gas cost for including a batch on L1 as the minimum total calldata cost that must be paid by all users in a batch, from which each user’s share of the calldata fee can be computed using some method that incentivizes compressibility of batches, if such a method exists.
41 Likes
I did a rough analysis of simulated compression ratios and cost ratios for sequencer batch transactions on Arbitrum One. Here are two figures of interest:
You can see the code and an explanation of how I generated this data at the following repository:
34 Likes
Thanks! That’s a really useful analysis. What it suggests, I think, is that in thinking about the compressibility of a user’s data, our notion of “size before compression” might only charge 1/4 for a zero byte, and 1 for all other bytes. That gives us a better measure of how much gas the user’s data can save by compression.
19 Likes
No problem! It was nice to venture back into python data visualization for a brief moment. I’d like to offer two thoughts I had about how developers could make a batch more compressible through intentional design (assuming the cost incentives are nailed down).
- Mining for specific contract addresses
- Mining for specific function selectors
Point 1 already happens on Ethereum mainnet, where developers mine for contract addresses or EOA with many leading zeros (to save on gas), however the approach will be different for compression. Basically, the way to make a batch more compressible is to include byte sequences that repeat many times (so that they can be replaced with backreferences). We could study transaction calldata on L1 to find the most-repeating byte sequences, but I would probably just focus on function selectors because it’s probably safe to assume that those are the most commonly repeating sequences. Instead of mining for leading zeros, a developer mines for an address that begins with the function selector for approve(address,uint256), transfer(address,uint256), or whatever selectors are most popular according to on-chain data.
Point 2 could incentivize developers to craft function selector collisions by appending extraneous characters to their function names until they get a function selector that collides with transfer, while having a different name. I’m not sure if this is a good or a bad thing, though.
In both cases, the more that developers adopted practices like these, the more compressible batches would become over time.
19 Likes
Really interesting, I was wondering about the technology behind the nitro update. This cleared lot of doubts.
Thanks for sharing this information to the community!
25 Likes