Dividend-bearing tokens on Ethereum

My lawyer would want me to say this: The article below is about the computer science and software engineering aspects of writing a token contract. It is not securities or accounting advice; please do not take it as such. I’m writing this as an individual, not a member of the Ethereum Foundation.

One thing I’ve seen come up frequently on the Solidity channel of late is the idea of dividend-bearing ERC20 tokens, and the calculations needed to support them. A naive implementation of disbursing dividends works something like this:

struct Account {
  uint balance;
}
Account[] accounts;
uint totalSupply;
function disburse(uint amount) {
  deduct(msg.sender, amount);
  for(var i = 0; i < accounts.length; i++) {
    accounts[i].balance += (amount * accounts[i].balance) / totalSupply;
  }
}

We’ll ignore for a moment that you can’t iterate over maps in Solidity to address the real issue: this function has to do work proportional to the number of token holders, which means you rapidly hit the block gas limit.

With further work, it’s possible to split this up into multiple transactions, but apart from being complex and prone to implementation bugs, it’s still impractical for tokens with a lot of users and frequent dividends, and it wastes a lot of gas doing duplicate calculations for users who aren’t making any transactions between dividend rounds.

Fortunately, there is a better way — and an excellent excuse to talk about one of the most useful design patterns in smart contracts: amortisation of work.

A better way

Any loop like the one in the snippet above should set your spidey-sense tingling, and the first thing you should look for is a way to amortise the work being done — that is, to break it up over many other operations. In this case, instead of updating every user’s account at once, we can keep track of the total dividends, and add a user’s pending dividends when there’s a transaction against their account. Here’s a quick sketch of how it would work:

struct Account {
  uint balance;
  uint lastDividends;
}
mapping(address=>Account) accounts;
uint totalSupply;
uint totalDividends;
function dividendsOwing(address account) internal returns(uint) {
  var newDividends = totalDividends - accounts[account].lastDividends;
  return (accounts[account].balance * newDividends) / totalSupply;
}
modifier updateAccount(address account) {
  var owing = dividendsOwing(account);
  if(owing > 0) {
    accounts[account].balance += owing;
    accounts[account].lastDividends = totalDividends;
  }
  _;
}
function disburse(uint amount) {
  totalDividends += amount;
  deduct(msg.sender, amount);
}

Then, we make sure to apply the updateAccount modifier to all functions that modify an account balance, to update any associated accounts’ balances before they’re operated on by the rest of our code.

Presto! All of our users automatically get dividends in a manner that avoids having to do an unbounded amount of work in any one transaction. If a user transacts infrequently, we even save net gas, since the user only needs to do one dividend calculation in total.

There’s still two problems with this, however: rounding errors, and the assumption of a fixed totalSupply.

Rounding Errors

The code above makes the assumption that the dividend can be evenly divided across all accounts, with no rounding errors. This isn’t true, of course, and the result will be a few wei lost to rounding errors.

In the grand scheme of things, this is a trivial amount of money, but it does mean breaking the invariant that the totalBalance is the sum of all balances, which complicates reasoning about the contract, and will throw off any attempt to reconcile the contract’s current balances. In general, it’s not great to lose track of money, even trivial amounts of it.

One solution to this is to explicitly keep track of a dividend account with its own balance. Whenever you pay out dividends to an account, subtract the same amount from the dividend account. The amount in the dividend account, then, is all the unclaimed dividends plus the rounding errors. The rounding errors are still effectively burned, but they’re no longer unaccounted for.

Changing the totalSupply

The second complication arises if we want to be able to change the totalSupply, either to mint or destroy tokens, or so that the dividend can be paid from outside. The code above assumes that the total supply is fixed; if it isn’t, users will get different proportions of dividends based on how the supply has varied since the dividend was issued.

Can we fix the scheme above to work in the presence of a varying total balance? It turns out we can. To see how, it helps to start by analysing what we’re actually trying to calculate.

If we go way back to the original naive algorithm, we can describe the dividends a user receives over time as a running sum:

(D_1 * B) / S_1 + ... + (D_n * B) / S_n

Where D_n represents the amount of the nth dividend, B is the user’s balance (it doesn’t change, because we assume we will take all dividends before sending or receiving funds), and S_n is the total supply at the time of dividend n.

In our first refactor, we assumed S == S_1 == ... == S_n — that is, that the total supply never changes. That allowed us to rewrite the equation as:

((D_1 + ... + D_n) * B) / S

That is, to sum up all the unpaid dividends and pay them all out at once. We can do a similar rearrangement without the assumption that the supply is constant, though, giving us this equation:

(D_1 / S_1 + ... + D_n / S_n) * B

That is, instead of storing the sum of total dividends so far, we store the sum of dividend percentages so far. To calculate a user’s dividends owing, we then calculate (totalDividendPercent — lastDividendPercent) * balance!

One final issue remains: S_n will generally be larger than D_n, and we’re working with integers, so all our percentages will round down to zero. This is easily fixed, however — just multiply both sides by a large constant integer. So our final equation is:

(D_1 * X / S_1 + ... + D_n * X / S_n) * B / X

To minimise rounding errors, we pick a large number for X — say, 10¹⁸. This gives us teeny tiny rounding errors, but still allows plenty of headroom for large token balances (with 10¹⁸ for X, we won’t overflow until someone’s balance exceeds about 10⁵⁹ tokens).

The final code, then, looks something like this:

const uint pointMultiplier = 10e18;
struct Account {
  uint balance;
  uint lastDividendPoints;
}
mapping(address=>Account) accounts;
uint totalSupply;
uint totalDividendPoints;
uint unclaimedDividends;
function dividendsOwing(address account) internal returns(uint) {
  var newDividendPoints = totalDividendPoints - accounts[account].lastDividendPoints;
  return (accounts[account].balance * newDividendPoints) / pointMultiplier;
}
modifier updateAccount(address account) {
  var owing = dividendsOwing(account);
  if(owing > 0) {
    unclaimedDividends -= owing;
    accounts[account].balance += owing;
    accounts[account].lastDividendPoints = totalDividendPoints;
  }
  _;
}
function disburse(uint amount) {
  totalDividendPoints += (amount * pointsMultiplier / totalSupply);
  totalSupply += amount;
  unclaimedDividends += amount;
}