Post
Topic
Board Development & Technical Discussion
Re: The case for moving from a 160 bit to a 256 bit Bitcoin address
by
gmaxwell
on 03/05/2017, 08:24:34 UTC
My intuition is that on average it requires twice as many P2SH addresses to be generated as the "birthday problem" would (since each new address in one set is effectively a new potential match in the other set)?
You've got it.

You should generally think of birthday problem numbers as approximate in any case,  because to achieve the bound you need lots of storage.  A cost optimized solver will make some time/memory tradeoff and usually end up using a couple times more computation than the birthday number in exchange for little to no storage.  (google floyds cycle finding algorithim)

And yes, thats the risk-- that your counterparties degree of freedom in choosing part of the contract will let them find an alternative contract with only collision like work, rather than with second-preimage like work.

You can mitigate by having multiple rounds of communication with commitments, but few to no one will implement this in practice:  Each communication round is a huge software engineering and UI cost, and most people don't understand this collision vulnerability (or _any_ collision vulnerability) even after having it explained.  The longer hash should also be somewhat more secure against second preimages assuming our hash functions become weakened by attacks in the future.

[Basically _any_ time I've seen a collision come up in discussions about the protocols people-- even people who should know better-- get them wrong. Someone on Reddit just the other day argued that a 64-bit collision would take 2^64 work, so I generated one based on his message.. then he argued that I got really lucky to have managed to produce one using only a 32-bit nonce and couldn't provide another, so I did... Tongue  they're highly unintuitive to people)