Hey all! I’ve elaborated on the idea of the block roots cache at Lido research forum, I’ll appreciate any feedback!
Hey, today I did some quick slides about the BLOCKHASH situation fro Verkle Trees.
If you go to the last slide, you’ll see that “Solution 4” proposes a ring buffer. This EIP-4788 takes a similar approach to this other use case of beacon roots.
In the slides, I mention a potential DoS attack vector. Remember that in Verkle Trees, there’s a single tree for all accounts and storage. This means that someone could try brute-forcing writes to generate tree addresses with the same prefixes as the branches to attack, which would cause that branch to be longer than average.
In the case of the BLOCKHASH ring buffer, these addresses are fixed (or could be in a contract as proposed in EIP-4788). The point is that the same DoS risk would exist for the (two) ring buffer entries in this contract. This would mean updating the ring buffer can have a higher cost than the average depth of the tree.
This kind of DoS attack can be done in any branch of any storage slot. The main difference between any branch and these branches is that these ones are “system-related,” so from an economic perspective might have a better ratio of cost/benefit for an attacker (that’s the handwavy argument).
To be clear, I don’t have numbers if this is a true problem – just sharing the concern. Maybe someone can have more experience and knowledge to gauge if this is a problem.
Hey folks! I’ve compiled a small project demonstrating a usage of the block roots. It includes:
- creating a proof from a beacon state (thanks to the
lodestarjavascript packages) - verifying a proof via a smart contract
I will be glad for any feedback and suggestions if you find how to make it more useful.
2 Likes
I don’t understand what the attack is. Even today it is possible to mine addresses near an account to create a deeper branch. It can be a bit more difficult with storage because, today, that keyspace is controlled fully by the contract. After verkle, it will no longer be, but still, I don’t see what the regression will be beyond a small performance hit (which the attacker will pay dearly for in other storage costs).
I don’t understand what the attack is. Even today it is possible to mine addresses near an account to create a deeper branch. It can be a bit more difficult with storage because, today, that keyspace is controlled fully by the contract.
Correct. I never claimed this is a “novel attack” strategy, just that it’s now possible for storage slots in VKTs, and considering this EIP uses a “system contract,” attacking those branches might have a different impact in the protocol than any other random branch from a contract. Totally fair if that is found irrelevant, just mentioned this as a point that might not be obvious to everybody.
I don’t see what the regression will be beyond a small performance hit (which the attacker will pay dearly for in other storage costs).
Sure, maybe (and I hope too!) it’s a small performance hit, but I’m not sure we can extrapolate the conclusion from MPT to VKT since:
- VKT use EC scalar multiplications to update tree updates (i.e: update commitments). These scalar mults are slower than Keccack.
- The VKT will be shallower, so maybe this will offset the above fact. (Isn’t obvious to me).
(which the attacker will pay dearly for in other storage costs).
In a VKT, you only need to find, for example, one key with an 8-byte prefix match to attack a branch and generate a branch of depth 8. Also, storage slots next to each other live in the same leaf node, meaning that a single key attacks 256 storage slots at once.
This isn’t an argument to say that “the attacker will pay dearly for in other storage costs” is wrong. I’m just sharing some facts that explain why I don’t think it is obvious.
It’s totally possible I’m being paranoid – so I hope your intuition is correct! Having to solve this problem would be quite annoying.
I wanted to signal that there’s currently a discussion on whether or not these branch poisoning attack vectors in VKT are a concerning problem. Also, to be clear, the concern is not coupled to the ring buffer idea since it’s a more general concern.
I’ve done some initial exploration: Verkle Trees - An exploration of tree branches attacks - HackMD, where I dive deeper into some points I made before. There might be more discussions until we conclude. In any case, all this is off-topic here.
Again, sorry if this was an unnecessary tangent in the thread!
1 Like