2

I know an ethereum address is generated by getting the last 20 bytes of the keccak-256 hash of the public key, which is 40 hex digits. I also know, an address does not need to have transactions associated to it to be valid, it just needs to have been generated by keccak-256. Does this mean any 40 character hex string is a valid address or are there some arrangements that keccak-256 will never generate?

  • keccak256 generates 64-hex digit hashes. – goodvibration Dec 12 '19 at 17:31
  • Indeed, but I believe you take the last 20 bytes of of the 32 bytes of data provided by keccak-256 to generate the address, correct? – Elliot Solskjaer Dec 12 '19 at 18:10
  • AFAIK, keccak256 is said to cover the entire range of 256 bits, hence the entire range of 160 bits. Not sure that it has been proven though. I do recall asking a similar (perhaps even equivalent) question here. Let me see if I can find it. – goodvibration Dec 12 '19 at 19:55
  • 2
    Yes, quite similar I believe. Here it is: ethereum.stackexchange.com/q/64138/16043. – goodvibration Dec 12 '19 at 19:59
1

Nobody can deliver a proof to an answer to that question. I'll try to explain why. The algorithm to create an address is as follows:

1) Generate private key k (slightly less than 2^256 keys, actually 2^256 - 4294968273 on curve secp256k1)

2) Derive public key P = (x,y) from k using elliptic curve scalar multiplication on curve secp256k1: P = G * k = G * ... * G (k times)

Note at this point your public key is 512 bit long, but not even nearly the whole number range is used, less than 2^256 points can be generated.

3) Hash concatenated x and y coordinates from P using keccak256 (mapping 512 bit to 256 bit)

4) Take the least-significant 160 bits from the hash, this is your address.

Until step 3 the answer can be proven. The Answer is no in that case, proof: Since we map less then 2^256 numbers to 2^256 numbers (non-surjective mapping), not every number in the target set (co-domain) can be hit. Step 4 makes everything unprovable though: We map less than 2^256 numbers inside a number range of 2^512 to 2^160 numbers. At first glance this mapping looks surjective and in that case we would answer yes. We don't know how the almost 2^256 numbers inside the number range of 2^512 are distributed. Even if we would know the distribution, we would still not know to which keccak hash those numbers are mapped. The only way to prove it is to brute force all public keys, one by one, caclculate the keccak hash and from it the address, look up if we stored it already, store it if it is not stored yet and stop when we finally hit every number in the 160 bit range or when we tried every public key available.

This answer is by far not optimal but I hope it could at least help you a bit to understand the difficulty of that problem.

| improve this answer | |
  • 1
    Thank you so much for the explanation, I understand the issue much better now. If I may ask a follow up question, if there is no way to know to which numbers keccak does and does not map, how does the ethereum network know which addresses to accept when for example fetching balance, does it accept every 40 character hex string and simply return 0 balance if there’s no transactions associated to it, or does it have some further way of address verification that goes beyond checking the length and checksum? – Elliot Solskjaer Dec 13 '19 at 13:10
  • I’d assume thanks to your argumentation that it does not, but just want to be sure. – Elliot Solskjaer Dec 13 '19 at 13:15
  • 1
    @NicolasSchapeler You're right, it does not have additional checks. Every transaction that transfers value to a 40 character hexadecimal string or internally any sequence of exactly 20 bytes is accepted. The balance is checked in the following manner: Ethereum Accounts are stored inside the Ethereum State DB. The State DB contains a collection called "Worldstate". In that Worldstate an Ethereum address is mapped to an Account datastructure (Balance, Nonce, CodeHash, StorageRoot). If the mapping does not exist, the balance is 0. If the mapping does exist, the balance is Worldstate[adr][bal]. – sea212 Dec 13 '19 at 13:31
  • Awesome, thank you so much! – Elliot Solskjaer Dec 13 '19 at 13:35
  • Here is a related post that could be helpful: ethereum.stackexchange.com/questions/3542/… – Steven Hatzakis Sep 25 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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