If I understand correctly on Wikipedia, this is a pointer algorithm, it uses O(1) memory, but the data structure itself, for which pointers will be created how much will it occupy?
You don't store it at all.
You start with some seed for x[0] and then compute x[1] and x[2] and so on.
x[n + 1] = Hash(x[n])
After around 2
80 steps, x[n] collides with one of the previous values. This creates a loop.
* A -> B -> C -> D -> E .
* ^ \
* | v
* J F
* \ /
* I <- H <- G
So, compute H = x[2
80] and then start from x[0] again. If you hit H before you get to 2
80, then you know you have a loop. Continue until you hit H a second time and that gives you the length of the loop.
Once you have the length of the loop and the location(s) of H, you can compute where merge point is. In the diagram that is the positions of J and B. Run a third time, and store J and B, you now how 2 values which hash to the same value.
To steal money, you actually need to have 2 types of hash. The fair and fraudulent one.
Based on LSB of x[n]
EVEN: x[n + 1] = Hash(multisig with [Alice's public key & x[n] as Eve's public key])
ODD: x[n + 1] = Hash(checksig with [Eve's public key] + DROP(x[n]))
In the multisig, Eve doesn't even need to have the private key. She isn't planning to use that version anyway.
Assume capitals are "fair" and lower case is "fraud", the diagram would change to
* a -> B -> c -> D -> e .
* ^ \
* | v
* J f
* \ /
* I <- H <- g
In this case, B and J are both fair. So the collision is useless.
Eve would try again with another seed. She needs to get one fair and one fraud.
There is a 50% chance she gets a mix, so on average she will need 2 seeds.