Add a fuzzing test case for queue management that ensures there's no way to violate the invariants in setWithdrawalQueue

[Niraj-Kamdar]

related to #404
The fuzzing case would be similar to others in the tests/integration/ section. This section of Brownie's docs will help: https://eth-brownie.readthedocs.io/en/stable/tests-hypothesis-stateful.html

[Niraj-Kamdar]

I have opened this issue. So, we don't forget it.

[pandadefi]

@Niraj-Kamdar ping!

[Niraj-Kamdar]

@pandadefi Thanks for reminder. I will try to implement it during this weekend.

[Niraj-Kamdar]

I have found 2 vaults with the same hash.

from itertools import product
        
# Creating the first release makes `latestRelease()` work
v1_vault = create_vault(version="1.0.0")
for i, j, k in product(range(100), repeat=3):
    version = f"{i}.{j}.{k}"
    # New release overrides previous release
    v2_vault = create_vault(version=version)

    a = bin(int(v1_vault.address, 16))[-4:]
    b = bin(int(v2_vault.address, 16))[-4:]
    if a == b:
       # Just for record :)
        with open("same_hash.txt", "w") as f:
            f.write(f"{i}.{j}.{k}")
        print(i, j, k)
        break

I found these 2 versions with same hash:

1. 0.0.16
2. 1.0.0

It took 5-6 minutes to find these two versions. So, I don't think it's practical to find it in tests. Maybe we should hard code it and update it whenever we make some changes to vault.

@fubuloubu I would like to have your opinions

[fubuloubu]

It took 5-6 minutes to find these two versions. So, I don't think it's practical to find it in tests. Maybe we should hard code it and update it whenever we make some changes to vault.

I'm not sure I understand what you are trying to say, do you think you've discovered a hash collision with how versions are compared? In Vyper, this uses keccak256 for string comparisions

[Niraj-Kamdar]

Since we want to test for the case when hash collision happens, I have written above script to generate 2 vaults with the same hash. In Vault contract we are using 5 least significant bits as the hash key for the set.

Note: I have used 4 LSB by mistake here.

[fubuloubu]

In Vault contract we are using 5 least significant bits as the hash key for the set.

Still not quite sure I understand, can you link to a code snippet where this is the case?

[Niraj-Kamdar]

https://github.com/Niraj-Kamdar/yearn-vaults/blob/2ffadcea3d8a9785c42236fe0c97fb4554ab2545/contracts/Vault.vy#L570-L571

[fubuloubu]

Ahhhh, I remember now where this came from!

Yes, so in general we designed this algo to be collision-tolerant, because only using the first 5 bits is unlikely to have enough entropy to avoid that condition. The idea here was to try and find two vaults with a collision in their first 5 bits, to ensure that we test this scenario thoroughly. I understand now.

Perhaps this issue is too prescriptive. What is really needed is just to test the condition of two strategy addresses with the same first 5 bits. You can just run a similar type of iterative process to find strategies with those two collisions, and then hardcode them as a test case. It would be nice to run a fuzzer case for this, but as you've found it's very difficult to farm addresses like this. More broadly, a fuzzer case could be created that is about adding strategies to the queue and withdrawing from them, but we already have a case sort of like that which could be expanded.

[Niraj-Kamdar]

I will add tests for vault collision and look into fuzzer case.

[Niraj-Kamdar]

Farming this is harder than I thought. We don't need to farm vault but strategy with the same hash and also while farming we need to maintain the order of transaction to reproduce the same smart-contract address afterwards.

Ex: While farming, I am running loop creating many strategies after creating first strategy which will change the state of blockchain so to reproduce it I need to farm every time while running tests in specific order which is impractical.

A solution would be to reset blockchain after every farming until we find a strategy that matches hash with the first strategy which will be extremely slow.

[Niraj-Kamdar]

@fubuloubu Any idea how to farm this efficiently?

[fubuloubu]

@fubuloubu Any idea how to farm this efficiently?

Farm it one time, and then start your test case from there. You can also explore finding a set of two addresses who's first txn being a strategy deployment produces a collision, and then just use those addresses for that test case (not having to re-farm).