How to whitelist up to 50k addresses in a single contract?

Question

What is the best practice in whitelisting a large amount of addresses in a contract. For example, if I wanted to include 50k addresses into a mapping that will reflect true for only the 50k addresses, would this be the optimal way? How much would this cost, per address?

mapping (address => bool) userAddr;

function whitelistAddress (address user) onlyOwner { userAddr[user] = true; }

Including 50k addresses hardcoded into the contract would hit the block gas limit, no doubt. How do I calculate exactly how much this would cost

Answer 1

Quick Lower Bound

You can put a lower bound on the cost, because each address will include one SSTORE, at the very least. So the cost to hard-code 50k addresses, at 20 kgas each would be more than 1 Gigagas total. The latest block limit is 6.7 Megagas. It will not fit, by a long shot.

Gsset - 20000 gas - Paid for an SSTORE operation when the storage value is set to non-zero from zero

source: Yellow Paper, Appendix G

---

Practical Cost

So let's look at the practical cost of incrementally adding whitelist addresses. Remix is an excellent way to quickly estimate gas costs for your function.

Using this contract:

pragma solidity ^0.4.15;

contract Owned {
    address owner;

    function Owned() {
        owner = msg.sender;
    }

    modifier onlyOwner() {
        require(msg.sender == owner);
        _;
    }
}
contract Whitelist is Owned {
    mapping (address => bool) userAddr;

    function whitelistAddress (address user) onlyOwner {
        userAddr[user] = true;
    }
}

I ran the function this way:

1. Choose the "Javascript VM" Environment
2. Click [Create] under Whitelist on the right bar
3. Enter "0x5B2063246F2191f18F2675ceDB8b28102e957458" next to the [whitelistAddress] button
4. Click the [whitelistAddress] button

Running whitelistAddress(...) results in: Transaction cost: 43464 gas

Total cost: 50k transactions * 43k gas ~= 2 Gigagas

At current "Safe Low" costs of 0.5 gwei , that equates to about 1 ether of total gas costs.

---

Batching for Marginal Improvement

Some of that call to add a whitelisted address is overhead: the original function call, checking the owner, etc. Let's find out how much.

pragma solidity ^0.4.15;

contract Whitelist is Owned {
    mapping (address => bool) userAddr;

    function whitelistAddress (address[] users) onlyOwner {
        for (uint i = 0; i < users.length; i++) {
            userAddr[users[i]] = true;
        }
    }
}

Calling this with a list of four addresses costs 109833 gas, resulting in a per-address cost of only 27458.25 gas. We won't do much better than that on an explicit whitelist, since the lower bound is 20k gas per address.

Using this method, the total ether cost at the Safe Low price has dropped to about:

50k addresses * 27k gas * 0.5 gigawei ~= 0.7 Ether

---

Weirder Alternatives

Maybe you don't really have a whitelist, maybe it's a blacklist or a guest list where the occasional false positive isn't too bad. Then a bloom filter could be a reasonable solution. Tuning the bloom filter requires knowing too much about your specific use case, but it could easily reduce the total cost by 1,000x or 10,000x.