# sortition-sum-tree-factory

> SortitionSumTreeFactory extracted from the Kleros core smart contracts.

Latest version **0.1.0** (published 2020-03-30) · MIT license · 0 weekly downloads

## Install

```sh
npm install sortition-sum-tree-factory
pnpm add sortition-sum-tree-factory
yarn add sortition-sum-tree-factory
bun add sortition-sum-tree-factory
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support; pre 1.0.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 0.1.0 |
| Published | 2020-03-30 |
| First published | 2020-03-30 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 12 |
| Unpacked size | 20.1 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 10 |
| Author | Kleros |
| Maintainers | asselstine |
| Keywords | blockchain, smart-contracts, ethereum |

## Links

- npm: https://www.npmjs.com/package/sortition-sum-tree-factory
- Repository: https://github.com/pooltogether/sortition-sum-tree-factory
- npm.io page: https://npm.io/package/sortition-sum-tree-factory

## Dependencies (12)

- [chai](https://npm.io/package/chai.md) ^4.2.0
- [solc](https://npm.io/package/solc.md) 0.6.4
- [ethers](https://npm.io/package/ethers.md) ^4.0.45
- [ts-node](https://npm.io/package/ts-node.md) ^8.6.2
- [typescript](https://npm.io/package/typescript.md) ^3.8.3
- [@types/chai](https://npm.io/package/@types/chai.md) ^4.2.10
- [@types/node](https://npm.io/package/@types/node.md) ^13.9.1
- [@types/mocha](https://npm.io/package/@types/mocha.md) ^7.0.2
- [ethereum-waffle](https://npm.io/package/ethereum-waffle.md) ^2.3.2
- [@nomiclabs/buidler](https://npm.io/package/@nomiclabs/buidler.md) ^1.2.0
- [@nomiclabs/buidler-ethers](https://npm.io/package/@nomiclabs/buidler-ethers.md) ^1.2.0
- [@nomiclabs/buidler-waffle](https://npm.io/package/@nomiclabs/buidler-waffle.md) ^1.2.0

## Recent versions

- 0.1.0 (latest) — 2020-03-30

## README

# SortitionSumTreeFactory

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

The majority of this code was written by [Enrique Piqueras](https://twitter.com/epiqueras1).  For an explanation of the code see the [Medium article](https://medium.com/kleros/an-efficient-data-structure-for-blockchain-sortition-15d202af3247).

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`:

```sh
$ yarn add sortition-sum-tree-factory
```

```sh
$ 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:

```solidity
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:

```solidity
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`:

```solidity
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](https://github.com/pooltogether/uniform-random-number).  This library eliminates modulo bias when constraining large numbers into a smaller set.

# Development

Install the dependencies:

```sh
$ yarn
```

Now run the tests:

```sh
$ yarn test
```

---
_Source: https://npm.io/package/sortition-sum-tree-factory · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._