When dealing with public blockchains, nothing comes for free. That’s why incremental gains in efficiency can lead to big cost reductions, especially over the long run. On Ethereum and other blockchains that use the EVM, this often means finding ways to save on gas costs, either by avoiding the blockchain altogether when possible (e.g., counterfactual instantiation and generalized state channels, eloquently explained here by Rick Sanchez) or by carefully optimizing on-chain transactions when necessary.
There’s a relatively obscure technique to confer one such incremental gain: find an address that costs less to use, depending on the circumstances. By using an address with more zero bytes than usual (i.e., a low hamming weight) and, in certain cases, with more zero bytes at the start of the address, we can save gas on many types of transactions.
I can already guess what you’re thinking:
Wait a minute — every vanilla transaction costs 21,000 gas, regardless of the addresses in question. Besides, my sweet
0xdecafdeadbeefvanity address took forever to find. I’m going to need some evidence backing up your pugnacious claim that our choice in address makes a difference.
As per usual, the answer can be found in the Yellow Paper. (Whoa, bold move opening with that one…)
We’re interested in few of these operations (and their counterparts) in particular: Gtxdatazero (vs. Gtxdatanonzero) and Gsload + Gsset (vs. not using Gsset — that whole SSTORE thing sounds pretty damned expensive).
Call data, small data
First, let’s look at Gtxdatazero: it costs 4 gas for every zero byte of transaction data. Compare that to the cost of Gtxdatanonzero: 68 gas, or 17 times as expensive. As a consequence, every time a zero byte is used in msg.data in place of a non-zero byte, it saves 64 gas. A few things to remember concerning this observation:
- When viewing byte strings in hexadecimal form, each pair of numbers (where each character represents one of 16 possible digits) forms a byte (16² = 2⁸ = 256 bits). Single hexadecimal zeroes, or adjacent zeroes that are spread across two different bytes, will not reduce the hamming weight of the byte string.
- The ordering of the zero bytes has no bearing on the benefit derived — from this particular optimization, at least — only the total number of zero bytes used to replace a corresponding non-zero byte.
Addresses are one area where this property can come in handy. Consider the case of an ERC20 transfer(). The hamming weight of msg.sender makes no difference here, but as it turns out, the _to parameter passed into msg.data as part of the transfer function does (by the way, so does the function selector).
Using OpenZeppelin’s StandardToken as a reference implementation, a standard transfer to an address with no zero bytes costs 51,486 gas. However, a transfer to an address with eight zero bytes only costs 50,974 gas, a difference of 51486 — 50974 = 512 gas. This can also be expressed as 64 * 8: just what we would expect from the calculations above. It’s like having a “buy one hundred, get one free” card for all of the tokens transferred to the address. And, in case you were wondering about transferFrom (which of course you were, you sly dog), well guess what: if both addresses have eight zero bytes, the gas savings per transaction will be twice as high!
There are lots of other ways to bank on this method, but it basically comes down to whether or not you can use zero bytes instead of their inferior, non-zero equivalents. Another nice thing about this trick is that it’s totally backwards-compatible — you can use it to save gas even when calling contracts that weren’t built to take advantage of it.
(As an aside, when using this method you want to be extra careful to protect against the Short Address attack, explained in more depth here. In brief, if an address has trailing zero bytes, you can truncate them when requesting that a third party construct some token transfer for you, and if they don’t validate the input properly it will “steal” the extra bytes from the next parameter, amount. Then, whaddaya know: we now get back 256 times as many tokens!)
Next, consider Gsset: this and Gsreset both deal with the SSTORE opcode and set 32-byte words into state, and it costs 20,000 gas to store any non-zero data for the first time (yeah… if we can avoid calling SSTORE, That_Would_Be_Great.gif). Once the word has been stored, it’ll cost another 200 gas every time it’s retrieved via SLOAD, which is also not cool.
When it comes to addresses in particular, we can pull off some nice gas savings as follows: if the address has at least four leading zero bytes (or eight leading zeroes in hex-encoded format), then each address will only need to take up 16 bytes. If you do the math, taking covariance into account when integrating over the partial differential equations and remembering to carry the seven, we find that two addresses can be packed into one sweet 32-byte package. (Word.)
The interesting thing about this optimization is that, not only do you tap in to the savings from the Gtxdatazero improvements, but you save even more gas by not having to read and write as many words from call data. The other interesting thing about this optimization is that a proof-of-concept token to take advantage of it already exists — more details later, but the gist of it is that (depending on the method of transfer) we can shave off up to 5% of the total cost of a token transfer.
You can also see a related benefit of this optimization in action by checking out the infamous GasToken, specifically the way it handles GST2. The address of GST2, 0x0000000000b3F879cb30FE243b4Dfee438691c04, only uses 15 bytes of storage. That way, the deployed junk contracts can be 5 bytes shorter and still check that msg.sender matches the GST2 contract in order to selfdestruct and reap the gas rebates, saving an extra 5 bytes at 200 gas a byte when deploying them. If you’re going to game the gas system and fill up storage space with junk contracts, you may as well do it the right way! (This optimization around factory contracts is also discussed at the end of EIP-1167.)
W0000000ah… sign me up!
Now, you might say:
Alright, 0age — you zero-loving weirdo — I guess I’m convinced. But how can I actually get a hold of such an address?
Well, there are a few ways. The most straightforward option: basically, you “mine” one.
Addresses are deterministically generated, either from a private key (see here for a great article that goes into the details) in the case of externally-owned accounts, or from the caller’s address and a nonce (a counter when calling CREATE, or an arbitrarily-provided nonce when calling CREATE2, one of the opcodes included in Constantinople). Either way, it all feeds into a keccak256 hash, which means that, given a change in input, each byte’s resultant output is as good as random.
Zero bytes occur in random addresses at a frequency described by the binomial distribution:
with the binomial coefficient expressed as:
In our case, there is a 1 in 256 chance of a zero byte, and 20 bytes in an address. Using p = (1/256) and k = 20:
Take a look at the distribution (each line is three orders of magnitude — one in one, one in a thousand, one in a million, etc.):
You’re looking at a:
- 92.47% chance of finding zero zero bytes on the address.
- 7.25% chance of finding one zero byte.
- 0.27% chance of finding two zero bytes.
- 0.00635% chance of finding three zero bytes.
- 0.00000106% chance of finding four, or about one-in-a-million.
These kind of addresses are easily attainable without too much effort. However, finding an address with seven zero bytes takes, on average, 978,054,817,444 attempts — just shy of a trillion hashes — with a 0.00000000010224% chance of finding all seven of them in one place.
A glance at the distribution shows just how much more difficult it gets from there. If you can find one with ten zero bytes, I will buy you a beer some time; if you can find one with fourteen, the NSA will buy you one.
Let’s also look at addresses with leading zero bytes. The formula for finding an address with n leading zero bytes is much simpler:
The probability mass distribution for these bad boys is as follows:
The odds of finding an address with four leading zero bytes in a single attempt are one in 4,294,967,296. However, that doesn’t just mean we can crunch 4.3 billion hashes and call it a day. The odds of finding an address with four leading zero bytes in a specific number of hashes can be derived from the geometric distribution, where H denotes the number of hashes:
The problem with this distribution, especially when you have just enough hash power to find it, lies in its positive skew. you may have to wait for a very long time for an address with enough zeroes to come up if you get unlucky. Mining pools for Proof-of-work consensus mechanisms are a common response to this phenomenon, and serve the primary purpose of “smoothing out” the long tail of the distribution.
The “other way”
If you’ve been paying attention (if so, you’re officially a nerd), you might remember that I mentioned that there are a few ways of getting one of these addresses. If your botnet of smart-home gadgetry isn’t quite putting out the hash power you need, you can get someone else to mine one for you. As an added benefit of this approach, they will also manage any funds you send to this address on your behalf, since they’ll know the private key that was used to generate the address.
There is another way, though — that doesn’t come with the perks of sharing your private keys, however — that the Constantinople hardfork makes possible. The CREATE2 opcode lets us deploy contract addresses derived from sha3(msg.sender ++ salt ++ init_code)[12:] rather than the usual sha3(rlp.encode([msg.sender, nonce])) utilized by the CREATE opcode we already know and love. Now, couple that with a contract factory that creates upgradeable proxies, such as the AdminUpgradeabilityProxy from ZeppelinOS, and we have suddenly created a mechanism by which efficient addresses could get churned out by the dozens. Dozens, I say!
(It’s worth remembering that the overhead of using the proxy will clock in at around 1600 gas. That being said, if you need an upgradeable proxy anyway, why not go with the more efficient one?)
Everything — even nothing — has a price
Let’s follow this line of thinking through. We create a smart contract called Pr000xy that allows users to either create or claim transparent proxy contracts at efficient addresses. In order for people to actually start submitting hashes to the smart contract, they’re going to have to get something for the trouble. That means there needs to be a fair price for each address — ideally one that closely aligns with the actual probability of finding the address. We also want to take both the total number of zero bytes and the total number of leading zero bytes into consideration (but let’s set the leading zeroes aside for just a moment).
Turns out, the fair price isn’t best set by the odds finding a specific number of zeroes. It’s better to price an address based on the odds of having at least a specific number of zeroes. To find this, first calculate the cumulative distribution function (or sum, for those of you that prefer to talk about these kinds of things without sounding pompous) of all the odds of finding a specific number of zeros up to one less than the number we want. Then, you just subtract that number from one, and there you have it. This is also known as the survival function of the given binomial distribution.
In addition, the reward function should reflect the odds of getting the number of leading zero bytes given the total number of zero bytes. Here’s a way to get there: given some number of leading zeroes, subtract that total from the total number of zero bytes, as well as from the total number of bytes in the address. Next, feed that into the survival function using the new, smaller inputs. Finally, multiply that by the odds of finding the leading zero bytes to arrive at the probability for that particular “combo” of zero bytes and leading zero bytes.
Combining the two distributions in such a manner yields the probability of finding z or more zero bytes and s starting bytes on a given random address, stated as follows:
Translating this figure into an appropriate value of tokens that the proxy factory should mint when creating a proxy, and burn when claiming a proxy, takes just two more steps: finding the inverse of the combined odds, and adjusting by an appropriate scaling factor (since most addresses are just too ordinary to merit a payment) that rounds off the reward into integer values. A nice scaling factor is 256³ (or 2²⁴ for the bit-freaks out there), which makes the minimum reward broadly attainable — generating a vanity address with three leading zero bytes (i.e., six leading zeroes) will take 16,777,216 tries on average, but it’s totally doable on most commodity hardware, assuming you have a dash of patience. Seriously, try it yourself if you don’t believe me.
That leaves us with a reward function R that gives the precise value of creating a proxy with an address containing z zero bytes and s starting bytes, calculated as follows:
I’ll stop you now before you say:
This expression generates some gigantic numbers! How the hell is making me compute this monstrosity on-chain every time I want to use the proxy factory supposed to save me gas, exactly?
You know why? It’s because you’re not going to have to compute it on-chain. Luckily for all of us, a lookup table will do, as there are only 200 valid inputs to the function. I’ve saved you the headache of having to troubleshoot floating point precision errors when dealing with odds of a trillionth of a trillionth of a trillionth of a percent. You’re welcome. (It’s actually not that bad — you’re more than welcome to check my work.)
In your quest to locate proxy addresses that will generate a non-zero reward when created by Pr000xy, you can use this handy regular expression that will let you know if the address is worth any tokens:
^0{6}|^0{4}((.{2})*(00)){2}|^((.{2})*(00)){5}With all that out of the way, let’s look at some charts of the reward function without any formulas for all you visual learners out there.
But wait, there’s more!
There are additional benefits to using a factory contract for upgradeable proxies with efficient addresses over simply brute-forcing an address the old-fashioned way. If we fashion the proxy so that the salt fed to CREATE2 is derived from both the address of the submitter and a nonce that they submit, a reliable source of randomness is no longer a prerequisite to generating secure vanity addresses. Simply stepping through nonces incrementally will work, since only the intended submitter will be able to deliver the intended salt that will generate the contract to the factory contract. This, combined with the fact that a key pair doesn’t need to be generated for every attempt (rather, a keccak256 hash is performed on a concatenated byte string to verify the contract address), should increase the number of addresses that can be checked with a given amount of compute power.
Furthermore, using the factory pattern has another interesting benefit: vanity addresses can be safely mined in an untrusted environment. There are no private keys to steal, as the address that will submit the nonce is supplied as an argument and the associated private key is never made available to the machine that’s mining the vanity address. Congratulations—your shady website now has a new way to secretly mine crypto in the background! (Just kidding — don’t be that guy.)
If you build it (and put in a waterslide), they will come
Assuming there’s a demand for proxies with efficient addresses, the trick to making a factory contract for them really hum lies in incentivizing enough miners to get hashing. An accurate reward function goes a long way, and the ability to mine addresses faster and in untrusted environments helps. However, there are already a lot of highly-optimized tools for finding vanity addresses using traditional means, and going through the factory contract will require paying some extra gas — a touch ironic, considering the ultimate aim. But there’s one more ace in the hole — even if they’re just looking for a vanity address for themselves, they can amortize the cost of finding it, or even make money, by capitalizing on all the addresses they find that would otherwise go to waste.
By way of example, let’s say the hot new blockchainBuzzwordSoup project wants a proxy contract with an address that has at least eight zero bytes. They also have the means to mine it themselves, and Pr000xy tokens are a touch too expensive right now for their tastes, especially since it takes 9 million tokens to claim the address they want. With the hash power at their disposal, it will take them about Two Weeks™ to find it — which means it could take forever — but, thankfully, they drink the Kool-aid and decide to use Pr000xy.
Once they start mining, they’ll begin to find efficient, but not-quite-efficient-enough-for-blockchainBuzzwordSoup, proxy addresses that they can create until an address comes up that meets their specifications, or until they have earned enough tokens to buy it outright. The former case allows them to sell off the extra tokens and recoup some of their excessive electricity bill and corresponding heat damage inflicted on their processors. The latter case effectively “smoothes out” the long tail of the distribution we touched on above, protecting them from a stroke of bad luck that significantly delays a positive match.
To really amplify this effect, Pr000xy can let users make offers to buy custom vanity addresses. To do so, they stake ether in the factory contract. Then, once a proxy is created by the factory that matches the request, anyone can call a method to match a valid offer with the proxy, transferring the staked funds to the proxy’s creator (with a fee offered by the requester for finding the match) and ownership of the proxy to the user that set the offer (burning any required tokens in the process if the address has enough zero bytes). The more users looking for custom vanity addresses, the stronger the incentives for miners to use the proxy, and the faster the custom addresses will be found — a virtuous, but mostly vain, cycle.
T000kenomics
Now that we’ve established a method for procuring efficient addresses, let’s turn to what to do with them. For the use-case of ERC20 tokens, and particularly for tokens that are willing to “bend the rules” a bit by, shall we say, extending the interface.
Imagine a token — let’s call it T000ken for the lulz — where only addresses with four leading zeroes are permitted to carry a balance. Assuming you have an address that meets these requirements, you can mint T000kens by locking up Dai or something similar, then you can use them, send them around to all your buddies with zero-byte addresses, and eventually burn them and get back your Dai if you like. In order to reap the bulk of the rewards, you deviate juuust a little from the standard ERC20 methods, packing the arguments where possible and using function selectors with lots of zero bytes. (Ha! You knew that little tidbit from earlier was going to come up again.) To provide a few specific examples:
- having four zero bytes in
fromaddress saves64 * 4 = 256gas, and more if there are extra zeroes - packing
toandfrominto one word gets rid of 32 empty bytes of call data, yielding another32 * 4 = 128gas savings - replacing the default
allowed, which takes the form ofmapping (address => mapping (address => uint256)), with the more efficientmapping(<packed addresses> => uint256)saves a whopping 66 gas (7/11ths of which comes from the extrasha3required to get the value out of the nested hash table) - using function selectors with three zero bytes (you can even use one with four!) saves
64 * 3 = 192gas - ordering function selectors carefully — they’re sorted alphanumerically by their selector — saves 12 gas a pop
Squared up against a fresh-out-of-the-box OpenZeppelin ERC20 implementation, a T000ken proof of concept implementation actually fares pretty well: over 3% gas savings on transfer and over 5% on transferFrom. Even when the reference implementation uses the same addresses, T000ken still provides 2.5% off for a transfer and 4% for a transferFrom.
----------------------- Gas Savings Analysis -----------------------
cost to lock: 41499 (in-only: 56499) free: 65260 total: 1067591. T000ken using standard ERC20 methods
Transfer TransferFrom Approve
Example (regular address) 36518 44113 30308
T000ken (ERC20 methods) 36027 42777 30045
Gas savings: 491 1336 263
Percentage savings: 1.34% 3.03% 0.87%Example (compact address) 36262 43601 30052
T000ken (ERC20 methods) 36027 42777 30045
Gas savings: 235 824 7
Percentage savings: 0.65% 1.89% 0.02%
Breakeven txs: (in only) 241 69
Breakeven txs: (in and out) 455 1302. T000ken using extra-efficient "sort of like ERC20" methods
Transfer TransferFrom Approve
Example (regular address) 36518 44113 30308
T000ken (efficient) 35308 41829 29566
Gas savings: 1210 2284 742
Percentage savings: 3.31% 5.18% 2.45%Example (compact address) 36262 43601 30052
T000ken (efficient) 35308 41829 29566
Gas savings: 954 1772 486
Percentage savings: 2.63% 4.06% 1.62%
Breakeven txs: (in only) 241 32
Breakeven txs: (in and out) 455 60
Show me the code!
Check out the code for Pr000xy here or play around with it on Ropsten (the code for T000ken is still pretty rough around the edges, but let me know if you’re interested in taking a look). There’s even a node script you can use to mine your own — be sure to replace the address with one you control. If you don’t want a transparent upgradeable proxy but would still like a gas-efficient address for your next contract, you can use Create2Factory (code here, deployed to Ropsten here) to specify your own contract initialization code and use a similar address-mining technique as that employed by Pr000xy — see this follow-up article for a walkthrough of the process. There’s also a brand-new Pr000xy Telegram group that would love to have you. Keep in mind that Pr000xy is still highly experimental and has not yet been audited— get involved and help fix that!
Big thanks to Stephane Gosselin, Connor Spelliscy, Santiago Palladino, Alejandro Santander, David Bleznak, Martin Holst Swende, Nicolas Venturo, Francisco Giordano, and Sina Habibian for their thoughtful assistance and advice in this eccentric endeavor.
