Factoring in birth day attacks and all that, with 256-bit elliptic curve cryptography, lets take secp256k1 as example that Bitcoin uses, what is the maximum number of accounts that are secure? It isn't $2^{256}$ since then any time you generate a random number you find a used account.

Birth day paradox and all that, what is the upper limit of how many accounts secp256k1 actually supports?


1 Answer 1


The upper limit really depends on your risk. The birthday attack's 50% probability is a too big risk to rely on. Let's look at some numbers assuming that the total of the points is $2^{256}$ which is not bu very close*. Assuming the keys are constructed uniform randomly like a coin toss.

We will use the fact that the probability of collision among uniform randomly selected $k$ elements in the set of $n$ element can be approximated by $(2^{k})^2/2^{n}/2=2^{2k-n-1}$

  • Consider $2^{100}$ private keys, that has a probability of collision

    $$(2^{100})^2/2^{256}/2 = 2^{200 - 256 - 1} = 1/2^{57}.$$ Not going to happen $\times 2^{-40}$ ans still very low proabaility to execute an attack.

  • Consider $2^{90}$ private keys, that has a probability of collision

    $$(2^{90})^2/2^{256}/2 = 2^{180 - 256 - 1} = 1/2^{77}.$$ Not going to happen $\times 2^{-20}$

  • Consider $2^{80}$ private keys, that has a probability of collision

    $$(2^{80})^2/2^{256}/2 = 2^{160 - 256 - 1} = 1/2^{97}.$$ Not going to happen

  • Consider $2^{70}$ private keys, that has a probability of collision

    $$(2^{70})^2/2^{256}/2 = 2^{140 - 256 - 1} = 1/2^{117}.$$ Not going to happen $\times 2^{20}$

  • Consider $2^{60}$ private keys, that has a probability of collision

    $$(2^{60})^2/2^{256}/2 = 2^{120 - 256 - 1} = 1/2^{137}.$$ Not going to happen $\times 2^{40}$

  • Consider $2^{50}$ private keys, that has a probability of collision

    $$(2^{50})^2/2^{256}/2 = 2^{100 - 256 - 1} = 1/2^{157}.$$ Not going to happen $\times 2^{60}$

  • Consider $2^{40}$ private keys, that has a probability of collision

    $$(2^{40})^2/2^{256}/2 = 2^{80 - 256 - 1} = 1/2^{177}.$$ Not going to happen $\times 2^{80}$

Actually, there is no need to look lower than $2^{70}$ since the probability is already is so tiny to happen. When it is around $1/2^{100}$ we simply say that it is not going to happen. Similarly, there is no need to look over $2^{80}$ since normally, that amount of users is not going to be needed. This also shows that if an entity tries to randomly guess the private keys, will fail.

In the case that one entity decides to attack all $t$ targets than the cost to find the first of $t$ target is not cheaper than the DLOG.

* the order of the base point is = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

  • $\begingroup$ Thanks, good answer for someone like me who is not as good as that as you are. I'm a bit interested in the lowest bound, even if it far exceeds number of users (2^80 is already a trillion trillion accounts. ) Working downwards from 1/2^96, where do you think probability starts breaking it? $\endgroup$ Commented Oct 29, 2020 at 13:38
  • $\begingroup$ The reason I wonder is because I've created a new population registry paradigm, and it supports at most as many people as secp256k1 supports accounts. github.com/0xAnonymous/Polytopia/blob/main/Polytopia.sol. I like to say "trillions of trillions of people" but I wanted to get a bit better at thinking about more exactly where the limit is. $\endgroup$ Commented Oct 29, 2020 at 13:43
  • $\begingroup$ I think what I need to understand is, when are probability of collision brute forceable? Based on computations per second, 1 in 2^97, and 10^20 computations per second (all computer capacity of world or something like that), that’s a billion seconds for a collision? 30 years? $\endgroup$ Commented Oct 29, 2020 at 16:05
  • $\begingroup$ Well, I've only talked about the collision of the generation as of question. If given $t$ target than hitting one, one need the multi-target attack, I'll update for that. $\endgroup$
    – kelalaka
    Commented Oct 29, 2020 at 17:28
  • $\begingroup$ the question was more in general, how many accounts secp256k1 (to have a clear, popular and well known reference example) actually supports (and brute force I guess being main attack and reason for an upper limit. ) I'm a bit of a lay man, but interested in improving my understanding. you gave a really good answer. $\endgroup$ Commented Oct 29, 2020 at 20:07

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.