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).

[pandadefi]

@Niraj-Kamdar ping

[Niraj-Kamdar]

I was trying to farm two strategy with same hash for a vault but not sure how can I do this deterministically?
Ex:

    v1_vault = create_vault(version="0.0.1")
    s1_strategy = gov.deploy(TestStrategy, v1_vault)

Here, all the parameters are kind of constant that we can't change so I am not sure how can we farm such strategy. One option I consider was to keep deploying until we find the two strategy with same hash but that wouldn't work for testing purpose since that'd be very slow.

Do you guys have any idea? @fubuloubu