1

I might be wrong in some of the facts that I state here, so please correct me if necessary.

My understanding:

  • Private key - 256 bits
  • Public key - 256 bits
  • Public address - the last 160 bits of a public key
  • Every private key is mapped to a public key, and hence to a public address

The facts above imply that some private keys are mapped to the same public address, but they do not imply that some private keys are mapped to the same public key.

I would like to ask the following questions:

  1. Do we have any other knowledge as to whether or not some private keys are mapped to the same public key, and hence, some public keys have no private key which is mapped to them?

  2. If the answer to the above question is yes, then there's a possibility that some public addresses have no private key which is mapped to them. Do we know of any such addresses, or if they even exist?

My motivation for asking this, is that I have an ERC20 contract which sometimes (depending on the current state) mints an additional amount of tokens which will later be distributed among (i.e., transferred to) some users.

Now, I need some address to hold these tokens, but I wish to avoid the case where someone has the private key of this address (as slim a chance as it may be).

At present, I am generating this address as follows:

address public constant MINTING_ACCOUNT = address(keccak256("MINTING_ACCOUNT"));

Ideally, I would like to replace this with a constant address which has no private key.

Thank you!

goodvibration
  • 26,003
  • 5
  • 46
  • 86

5 Answers5

5

TLDR: Use address 0.

  1. Depending on your definition of a private key, then yes or no. The public key is generated from the private key by scalar elliptic curve multiplication.

    P = k * G

    We know that the order of the generator G is 

    n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

    and so every k in the range [0, n) gives a unique public key. Sometimes people say that a private key is just a random 256-bit number, but private keys are equivalent mod n, which is slightly less than 2^256. For instance the private key k and n+k will give the same public key.

If you define a "public key" as any 512-bit integer then clearly almost all of them do not have associated private keys. (There are only n < 2^256 distinct private keys).

  1. The question of whether or not an address exists with no private key is a completely separate issue. Essentially you want to know if there is a 20-byte string such that no keccak256 hash ever ends in that postfix. The answer is that nobody knows, but probably not. Cryptographic hashes are designed exactly to avoid these sorts of nontrivial patterns in their output, and it would be a major flaw if such a string were to be discovered.

In summary, no. There is no "safe address". On the other hand, as many others have pointed out, the probability of guessing a private key corresponding to the 0 address is almost exactly 2^-160. This will never happen. Note that I don't say "this will probably never happen", because humans tend to be bad at reasoning about big numbers. I say "there's a 1 in 2^160" chance, and you say "so there's a chance?"

The chance is lower than any the probability of every computer on the network spontaneously combusting. There's no chance.

So we see the only option is to just pick an address "at random". You seem to want to pick a address generated by the hash of some string. I argue that you should use the 0 address instead. In cryptography this is sometimes called a "nothing up my sleve number". The more freedom you have in picking the address, the less confident users will be that you didn't intentionally search for a collision between the fake address and a real address. If you pick 0, users can be sure you have nothing up your sleeve.

Tjaden Hess
  • 37,046
  • 10
  • 91
  • 118
  • Excellent answer. I upvoted. – Rob Hitchens Dec 17 '18 at 20:00
  • Thanks. However, implementation-wise, I'm inheriting OpenZeppelin's ERC20 contract, which asserts that the address is not zero when minting, buring and transferring tokens. So I cannot quite make use of this address unless I override their functions (or just avoid inheriting it to begin with). I understand that on average, every private key is mapped to 2 ** 96 public addresses (I think I wrote it in a comment to one of the answers above here). I just thought I'd check to see if there was a "bullet proof" choice of a public address. – goodvibration Dec 17 '18 at 20:07
  • If 0 doesn't work for some reason, you can always use 1. But general best practice in this space is to use 0 for the"impossible" address, because everyone will understand immediately what you are using it for. – Tjaden Hess Dec 17 '18 at 20:09
  • BTW, with regards to your The chance is lower than... argument - I'm sure someone once said that about SHA-128. Then within a few years time, computing power has increased by several magnitudes, some people (or more precisely, agencies) pre-generated huge tables with hash info, and made this algorithm compromised to the point where it had to be replaced. But of course, if that ever happens to keccak256, then I guess my choice for a public address would be the least of my worries here. – goodvibration Dec 17 '18 at 20:10
  • When we design systems, we need to make assumptions. In Ethereum, we assume that keccak256 is not broken, i.e. there are no attacks for this sort of thing that are faster than brute-force. As for computing power, this kind of argument is exactly why I say there is no chance. There is not enough energy in the universe to carry out a brute-force attack like this, it doesn't matter how fast our computers get. The collision-security of sha-1 is only 80 bits. That's why it is depreciated. The preimage security is still 160 bits, which is perfectly fine. SHA-128 isn't a real thing AFAIK. – Tjaden Hess Dec 17 '18 at 20:14
  • In any case, your answer refers to the two bullets in my question in the most accurate manner. Thank you for the elaboration! Side note with regards to your last comment - I'm not sure it would hold in a quantum computing (or some other type of non-deterministic Turing machine) eco-system. – goodvibration Dec 17 '18 at 20:17
  • 1
    Quantum computers at most halve the bit-security of symmetric functions. See https://en.wikipedia.org/wiki/Grover%27s_algorithm. Even with quantum computing brute force attacks would be impossible. – Tjaden Hess Dec 17 '18 at 20:19
2

This issue is not a reason to be worry.

The probability of getting by chance a privatekey that you have already or that anyone has already in use is neglegible.

Also, the amount of time required by the fastest super-computer today to generate all the possible addresses is about 13 billion years see this answer for the case of Bitcoin

Finally, is not true that there is a 20bytes number that will not be related to a privatekey, in fact every possible address will be linked to several privatekeys. See this for a discusion

By the time this computational capability is available we should have move already to quantum resistant cryptography, whcih already exist.

Hope this helps

Jaime
  • 8,340
  • 1
  • 12
  • 20
  • Thank you. But with the exception of one statement, you've basically repeated the previous answer, which did not relate to my question directly, but rather told me that I shouldn't be worried about it. The one statement: "Finally, is not true that there is a 20bytes number that will not be related to a privatekey, in fact every possible address will be linked to several privatekeys." Do you have anything to back this up? Even a link to an article or some official documentation of the Ethereum blockchain? – goodvibration Dec 16 '18 at 15:46
  • I think your comment is very unfair, the link you I shared shows how to calculate the probability of getting a particular address, the reason I say to not to worry is that of that calculation, which is different than the argument in the previous answer. On the other hand, If the address is the 160 last bits of the publickey, and the public key is 256 bits, several publickey will lead to the same address. Assume the posssinle public keys are 3 bits long and the address is 1 bit (2 addresses: 0 or 1), 000, 010 and 100 are the publickeys with the same address. – Jaime Dec 16 '18 at 15:59
  • Please take a look to my editted answer for a discussion about several private keys with the same address – Jaime Dec 16 '18 at 16:10
  • did this cleared things for you? – Jaime Dec 16 '18 at 16:20
  • Thank you. First of all, there is one statement in that link which reveals an error in the facts that I have stated: "A public key is 512-bit long" (and not 256-bit long as I mentioned). – goodvibration Dec 16 '18 at 18:57
  • But the rest of that statement actually implies my request for s public address which has no private key: "However, since each of them is derived from its own private key, there are only 2 ** 256 valid public keys". The the question is, do these public keys cover the entire range of 2 ** 160 public addresses? If not, then the answer to my question is yes - there is a public address which is not mapped by any private key. – goodvibration Dec 16 '18 at 18:57
  • Now, I understand that statistically, most likely every public address is mapped by many private keys (2 ** 96 private keys on average, which is a hell of a lot). But I'm asking - is this true in an absolute manner, or just statistically? Has anyone investigated the hash function to determine whether or not those 2 * 256 private keys "cover" the entire range of 2 ** 160 public addresses? – goodvibration Dec 16 '18 at 18:59
  • is just impractical (and basically impossible) to test all the possible values (today) if this were not the case the hash will be useless. – Jaime Dec 16 '18 at 23:43
  • True, but I didn't ask if (or suggest that) all possible values have been tested. I asked if it is known whether or not some values are not mapped to any private key. It is possible that the answer to this question is Yes, even without checking all possible values (e.g., some proof which was made on the hash function characteristics). – goodvibration Dec 17 '18 at 07:03
2

A contract has no private key.

You could consider a very idiomatic contract with an Ownable or Multi-signature pattern and a possibility of withdrawing the tokens or distributing. Mint tokens to that contract's address.

Obviously, there will still be an account or combination of accounts that can perform some limited range of options, defined in the contract, with the tokens held in the contract. If that is not the case, then the tokens would be burned.

The contract itself, like all contracts, would have no known private key.

Hope it helps.

Rob Hitchens
  • 55,151
  • 11
  • 89
  • 145
  • That's exactly the approach that we started off with - Mint tokens to one of our contract addresses (good guess!). However, there's one problem with that - we cannot allow ourselves to upgrade this contract (i.e., redeploy it, and in our "registry" contract which maps unique strings to contract addresses, update this contract address). More precisely, we would need to rewrite some of our system-upgrade mechanism to handle this, and transfer all the tokens to the address of the new contract. – goodvibration Dec 16 '18 at 19:06
  • So we figured we'd use some hard-coded address like 0x12345678.... But instead of a magic number, we figured we'd use keccak256 in order to generate this hard-coded address. You have stated that a contract has no private key - do you have anything to back this up? Are contract addresses somehow generated in a different manner, such that no private key possibly maps to them? – goodvibration Dec 16 '18 at 19:07
  • I found an interesting thread on this. Now matters are less clear. Yes, contracts are different and no private key is generated in the process. No, possibly it is merely extremely unlikely anyone can generate a private key to spend from a contract address. Not quite the same as impossible. See here for two credible descriptions: https://ethereum.stackexchange.com/questions/185/where-is-the-private-key-for-a-contract-stored – Rob Hitchens Dec 16 '18 at 19:21
  • So what's the difference between using a contract's address and using address(keccak256("SomeString")) as I have demonstrated in my question? Sounds to me like both will yield an address with an unknown (and hard to find) private key. – goodvibration Dec 16 '18 at 19:34
  • From the perspective of an ERC20 contract, your made up address is fine. From the perspective of the owner (you), I fail to see how you will get the funds back since it would be neither a wallet with a private or a contract that responds to inputs. – Rob Hitchens Dec 16 '18 at 19:39
  • Oh, sorry, I have an onlyOwner function which transfers the tokens to a user when certain conditions are met. So no private key is required here. And if I used a contract address instead of the "made up" address, then I would need to extend the infrastructure that I mentioned above, to transfer all the minted tokens from the old contract address to the new contract address (whenever I upgraded the contract). – goodvibration Dec 17 '18 at 06:50
  • It's not necessarily true that a contract has no private key. That statement is true in exactly the same sense that "the 0x0 address has no private key". – Tjaden Hess Dec 17 '18 at 19:28
  • Agreed. Thanks. I added "known" to clarify that, briefly. – Rob Hitchens Dec 17 '18 at 19:57
  • Actually, it's much easier to find a contract address with a known private key than it is to find a private key for the 0 address. You can do a birthday attack to generate a contract with a known private key with just 2^80 tries on average. – Tjaden Hess Dec 17 '18 at 20:01
  • That's really interesting. If I understand the essence of that, this is why 0 is less suspicious than some arbitrary address that could be "something up my sleeve." – Rob Hitchens Dec 17 '18 at 20:04
2

No, there is no way to use "non-private-key addresses". Ethereum uses ECDSA that generates the public keys exclusively from the private key. So there are no "privileged" addresses that can be used as non-public address. The full set of public addresses can be generated from the full set of private addresses.

earizon
  • 606
  • 4
  • 15
1

There really is no need to consider the possibility that someone might, by pure chance, find that private key. You really have to appreciate how small these probabilities really are.

  • The chance that you and I will both die within this hour is much larger.

  • The chance that you will win a national lottery 5 times in a row is much larger.

The entire cryptocurrency ecosystem and the entire field of cryptography is built on the assumption that these extremely-low-probability events will not happen. You have a billion other things to worry about before you have to worry about someone accidentally finding a private key for your random public key.

Jesbus
  • 10,478
  • 6
  • 35
  • 62
  • I'm sure someone once said that about SHA-128. Then within a few years time, computing power has increased by several magnitudes, some people (or more precisely, agencies) pre-generated huge tables with hash info, and made this hash algorithm compromised to the point where it had to be replaced. But in any case, my point is, if we know of such address then why not use it? Hence my question. Thank you. – goodvibration Dec 16 '18 at 10:58