SortitionSumTreeFactory

This is a data structure that allows efficient O(log(n)) weighted selection. This package is an extraction from the Kleros project.

For an explanation of the code see the Medium article.

For more information on Sum Trees read Introduction to Sum Tree

Attribution

The majority of this code was written by Enrique Piqueras.

The data structure was designed by Clément Lesaege.

Thanks to the Kleros team for MIT licensing this extremely useful code!

Setup

To install use yarm or npm and install sortition-sum-tree-factory:

$ yarn add sortition-sum-tree-factory

$ npm i sortition-sum-tree-factory

Usage

The SortitionSumTreeFactory is a library that should be attached to the struct SortitionSumTreeFactory.SortitionSumTrees. This data structure allows you to create many different sortition sum trees.

For example, here we use the library to create a single global sortition sum tree:

contract WeightedSelection {
    bytes32 constant private TREE_KEY = keccak256("PoolTogether/SingleRandomWinnerPrizeStrategy");
    uint256 constant private MAX_TREE_LEAVES = 5;

    using SortitionSumTreeFactory for SortitionSumTreeFactory.SortitionSumTrees;

    SortitionSumTreeFactory.SortitionSumTrees sumTreeFactory;

    constructor () public {
        sortitionSumTrees.createTree(TREE_KEY, MAX_TREE_LEAVES);
    }
}

Let's assume the sortition sum tree is storing user token balances.

Now you can set the balances using the set function:

function updateBalanceOf(address user, uint256 amount) external override {
    sortitionSumTrees.set(TREE_KEY, amount, bytes32(uint256(user)));
}

When we want to select someone proportionally we can use draw:

function randomlyDrawUser() public view returns (address) {
    bytes32 entropy = blockhash(1);
    uint256 token = UniformRandomNumber.uniform(uint256(entropy), bound);
    return address(uint256(sortitionSumTrees.draw(TREE_KEY, token)));
}

The probability that a user is selected is proportional to their token balance.

Note the use of UniformRandomNumber. This library eliminates modulo bias when constraining large numbers into a smaller set.

Development

Install the dependencies:

$ yarn

Now run the tests:

$ yarn test