23

Assuming a properly working RNG what are the chances of creating a Monero private key that is identical to one created by someone else (it corresponds and controls funds sent to the same XMR address)?

How does the above answer compare to the same question for Bitcoin, Ethereum and ZCash?

Improve this question

3 Answers 3

Reset to default
11

Well, private spend keys are 64 character hex strings, see here:
https://moneroaddress.org

That will give you around 1e77 possible private keys. If n is the number of possible private keys, and you only generated two private spend keys, the odds they would be the same is:
1 - (n-1)/n
Which Python tells me is 0.0 due to floating point arithmetic.

In order to estimate how many keys you would need to generate to produce a collision you can just take the square root of n, which is about 3e38, which is a lot of keys.

See this page for more info:
https://stackoverflow.com/questions/22029012/probability-of-64bit-hash-code-collisions

Bitcoin uses the same 64 character hex string for private keys, so I think it should be the same.

Disclaimer: I'm no mathologist.

Improve this answer
4
  • 1
    Not quite, because I think not every single 256 bit value is a valid private key. Besides, a collision between any two is not enough, you need a collision with a fixed set which is orders of magnitude smaller than the addres space. In practice, I think the probability is a lot smaller than what you get.
    – user36303
    Commented Jul 21, 2016 at 17:14
  • 1
    Why isn't every 256 bit value a valid private key? Is it a significant amount that are not? Also, I guess by collision with a fixed set you mean a funded address? If yes, then I agree, it would require more attempts than I estimated above.
    – jwinterm
    Commented Jul 21, 2016 at 17:51
  • 4
    I don't know the amount of valid vs full bit space, but I don't think it's more than a few bits. And yes, I meant funded addresses. Your low bound still says that it's really not worth trying though, so that's good enough I guess :)
    – user36303
    Commented Jul 21, 2016 at 18:53
  • 2
    For the sake of completeness, I believe the number of bits here is about 4. See steemit.com/monero/@luigi1111/…, the definition of reducing, and the value of l.
    – user36303
    Commented Aug 1, 2016 at 20:22
5

To answer the question for Zcash, spending keys are 252 bits (all of which are valid). There's no practical difference between 252 and 256 bits in terms of the probability of collision for a properly working RNG; both are close enough to zero for reasonable bounds on the number of keys that will ever be generated. For how to calculate this probability, see https://en.wikipedia.org/wiki/Birthday_attack .

The Zcash implementation uses libsodium's RNG, which on Linux uses getrandom to access the kernel RNG.

In both Zcash and Monero, there's also a very small probability of an address collision even when the spending key does not collide. This turns out not to affect the overall collision probability very much. In Zcash, an address is composed of a_pk which is from a space of 256 bits, and pk_enc from a space of just over 252 bits (actually exactly the same number as the space of each key component in Monero, since they use closely related elliptic curves).

Improve this answer
4

The likelihood of a collision is theoretically 1 in 2^256 which is a number with 78 digits. It's the likelihood of winning the lottery 7 times in a row, or something along those lines. Unless, of course, the random number generator is broken somehow and the "rolls" could be predicted, which I don't believe is the case here. If you were concerned about the RNG, you could always roll the dice yourself to generate the initial seed. Note it would take a series of 99 rolls (of 6-sided dice) to generate the 256bit seed. This fact can also serve as an illustration of how unlikely it would be to generate the same sequence twice.

Improve this answer
1
  • 5
    1 in 2^256 would be correct if you are trying to generate a collision for both astatic spend and static view key. The birthday paradox gives you a collision between two finds in square root of 256 bits, so 128 bits. And that's with brute force. If you consider only spend key (or only view key), the numbers fall to 128 bits (to attack a particular key - infeasible) and 64 bits (to generate keys and try to find a collision between any two generated keys).
    – user36303
    Commented Aug 1, 2016 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.