DelphiPayouts.js

// We don't know at commit time what the votes are, so can't do any ordering work there.
// We can, however, store all commits with timestamps.
// At reveal time, we can look at the timestamp of the revealed commit and insert it into a DLL
// for its plurality, and require the insert point be computed off-chain. (We check on-chain that
// the timestampe for the new inserted node is >= the timestamp for the previous inserted node).
// After reveal time, we then have a time-ordered list of who voted when in the plurality. We'll
// model it as a simple array here. The logic sketched here would be executed at claimFee time.
// 
// The motivation for this sketch is that payouts for any arbiter cannot be computed unless the
// sum of all previous payout percentages are known. Because the number of arbiters who reveal in
// the plurality can be arbitrarily large, we want to ensure that it should be possible to compute
// that sum without busting the gas limit. The solution works such that if all arbiters claim fees
// "in-order", they all pay a constant amount of gas. Arbiters who reveal out-of-order will
// charitably compute the payout values for any arbiters before them whose payout values are not
// already computed. These computations persist such that for arbiters Alice, Bob, and Charlie, who
// committed in that order, if Bob claims first he will compute both his own payout and Alice's. If
// Charlie claims next he will compute only his own payout. If Alice claims last, she will do only
// minimal computation, since Bob computed her payout for her.
//
// I think this is cryptoeconomically sound. In most cases we expect all arbiters to eventually
// claim their money, and if one goes offline it only costs the rest of the arbiters one
// arbiters-worth of computation to unblock. It's kind of like a game of chicken, where you will
// wait as long as possible for someone else to compute your payout for you, until you *really*
// need the money and just do it yourself, and in doing so do a favor for any arbiters who came
// before you.

const FEE = 200;
const DECAY_VALUE = 5;

const pluralityArbitersOrderedByCommitTime = [
  { id: 'Alice',
    pctPreviouslyAllocated: 0,
    pctOwed: 0,
    payout: 0 },
  { id: 'Bob',
    pctPreviouslyAllocated: 0,
    pctOwed: 0,
    payout: 0 },
  { id: 'Charlie',
    pctPreviouslyAllocated: 0,
    pctOwed: 0,
    payout: 0 },
];

function computePayout(claimant) {
  // Compute the 'i' in p_i
  let i;
  pluralityArbitersOrderedByCommitTime.find((arbiter, arrIndex) => {
    if (arbiter.id === claimant) {
      i = arrIndex;
      return true;
    }
    return false;
  });

  // If the claimant didn't reveal a plurality vote, they are owed nothing.
  if (i === undefined) {
    return 0;
  }

  const arbiter = pluralityArbitersOrderedByCommitTime[i];

  // If the payout has already been computed, return it
  if (arbiter.payout > 0) {
    return arbiter.payout;
  }

  // We can always compute the payout of the 0th arbiter in constant time
  if (i === 0) {
    arbiter.pctPreviouslyAllocated = 0;
    arbiter.pctOwed = (100 / DECAY_VALUE);
    arbiter.payout = arbiter.pctOwed * (FEE / 100);

    return arbiter.payout;
  }

  // For arbiters > 0 whose payouts are not already computed, recursively compute the payout
  // for the previous arbiter, and use that information to compute this arbiter's payout
  const prevArbiter = pluralityArbitersOrderedByCommitTime[i - 1];

  // If we haven't computed the previous arbiter's payout, do that now.
  if (prevArbiter.payout === 0) {
    computePayout(prevArbiter.id);
  }

  arbiter.pctPreviouslyAllocated = prevArbiter.pctPreviouslyAllocated + prevArbiter.pctOwed;
  arbiter.pctOwed = (100 - arbiter.pctPreviouslyAllocated) / 5;
  arbiter.payout = arbiter.pctOwed * (FEE / 100);

  return arbiter.payout;
}

computePayout('Bob'); // This computes payouts for Bob and Alice.
computePayout('Charlie'); // This computes the payout for Charlie

console.log(pluralityArbitersOrderedByCommitTime);

https://gist.github.com/skmgoldin/a686ca4ffae0c718b22ee2d1a751ee7f#file-delphipayouts-js-L48

This looked we could do in constant time with a doubly-linked list. Just being lazy in this sketch.