Contract Source Code (Solidity)

IDE

• Blockscan IDE
• 🤖 Code ReaderBeta

Outline

• library SortitionSumTreeFactory
•    - function createTree(SortitionSumTrees ...
•    - function set(SortitionSumTrees storag ...
•    - function queryLeafs(
•    - function draw(SortitionSumTrees stora ...
•    - function stakeOf(SortitionSumTrees st ...
•    - function updateParents(SortitionSumTr ...

More Options

• Similar
• Submit Audit
• Compare

/**
 *Submitted for verification at gnosisscan.io on 2022-08-04
*/

// File: @kleros/kleros/contracts/data-structures/SortitionSumTreeFactory.sol

/**
 *  @authors: [@epiqueras]
 *  @reviewers: [@clesaege, @unknownunknown1, @ferittuncer, @remedcu]
 *  @auditors: []
 *  @bounties: [{ duration: 28 days, link: https://github.com/kleros/kleros/issues/115, maxPayout: 50 ETH }]
 *  @deployments: [ https://etherscan.io/address/0x180eba68d164c3f8c3f6dc354125ebccf4dfcb86 ]
 */

pragma solidity ^0.4.24;

/**
 *  @title SortitionSumTreeFactory
 *  @author Enrique Piqueras - <[email protected]>
 *  @dev A factory of trees that keep track of staked values for sortition.
 */
library SortitionSumTreeFactory {
    /* Structs */

    struct SortitionSumTree {
        uint K; // The maximum number of childs per node.
        // We use this to keep track of vacant positions in the tree after removing a leaf. This is for keeping the tree as balanced as possible without spending gas on moving nodes around.
        uint[] stack;
        uint[] nodes;
        // Two-way mapping of IDs to node indexes. Note that node index 0 is reserved for the root node, and means the ID does not have a node.
        mapping(bytes32 => uint) IDsToNodeIndexes;
        mapping(uint => bytes32) nodeIndexesToIDs;
    }

    /* Storage */

    struct SortitionSumTrees {
        mapping(bytes32 => SortitionSumTree) sortitionSumTrees;
    }

    /* Public */

    /**
     *  @dev Create a sortition sum tree at the specified key.
     *  @param _key The key of the new tree.
     *  @param _K The number of children each node in the tree should have.
     */
    function createTree(SortitionSumTrees storage self, bytes32 _key, uint _K) public {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        require(tree.K == 0, "Tree already exists.");
        require(_K > 1, "K must be greater than one.");
        tree.K = _K;
        tree.stack.length = 0;
        tree.nodes.length = 0;
        tree.nodes.push(0);
    }

    /**
     *  @dev Set a value of a tree.
     *  @param _key The key of the tree.
     *  @param _value The new value.
     *  @param _ID The ID of the value.
     *  `O(log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function set(SortitionSumTrees storage self, bytes32 _key, uint _value, bytes32 _ID) public {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = tree.IDsToNodeIndexes[_ID];

        if (treeIndex == 0) { // No existing node.
            if (_value != 0) { // Non zero value.
                // Append.
                // Add node.
                if (tree.stack.length == 0) { // No vacant spots.
                    // Get the index and append the value.
                    treeIndex = tree.nodes.length;
                    tree.nodes.push(_value);

                    // Potentially append a new node and make the parent a sum node.
                    if (treeIndex != 1 && (treeIndex - 1) % tree.K == 0) { // Is first child.
                        uint parentIndex = treeIndex / tree.K;
                        bytes32 parentID = tree.nodeIndexesToIDs[parentIndex];
                        uint newIndex = treeIndex + 1;
                        tree.nodes.push(tree.nodes[parentIndex]);
                        delete tree.nodeIndexesToIDs[parentIndex];
                        tree.IDsToNodeIndexes[parentID] = newIndex;
                        tree.nodeIndexesToIDs[newIndex] = parentID;
                    }
                } else { // Some vacant spot.
                    // Pop the stack and append the value.
                    treeIndex = tree.stack[tree.stack.length - 1];
                    tree.stack.length--;
                    tree.nodes[treeIndex] = _value;
                }

                // Add label.
                tree.IDsToNodeIndexes[_ID] = treeIndex;
                tree.nodeIndexesToIDs[treeIndex] = _ID;

                updateParents(self, _key, treeIndex, true, _value);
            }
        } else { // Existing node.
            if (_value == 0) { // Zero value.
                // Remove.
                // Remember value and set to 0.
                uint value = tree.nodes[treeIndex];
                tree.nodes[treeIndex] = 0;

                // Push to stack.
                tree.stack.push(treeIndex);

                // Clear label.
                delete tree.IDsToNodeIndexes[_ID];
                delete tree.nodeIndexesToIDs[treeIndex];

                updateParents(self, _key, treeIndex, false, value);
            } else if (_value != tree.nodes[treeIndex]) { // New, non zero value.
                // Set.
                bool plusOrMinus = tree.nodes[treeIndex] <= _value;
                uint plusOrMinusValue = plusOrMinus ? _value - tree.nodes[treeIndex] : tree.nodes[treeIndex] - _value;
                tree.nodes[treeIndex] = _value;

                updateParents(self, _key, treeIndex, plusOrMinus, plusOrMinusValue);
            }
        }
    }

    /* Public Views */

    /**
     *  @dev Query the leaves of a tree. Note that if `startIndex == 0`, the tree is empty and the root node will be returned.
     *  @param _key The key of the tree to get the leaves from.
     *  @param _cursor The pagination cursor.
     *  @param _count The number of items to return.
     *  @return startIndex The index at which leaves start.
     *  @return values The values of the returned leaves.
     *  @return hasMore Whether there are more for pagination.
     *  `O(n)` where
     *  `n` is the maximum number of nodes ever appended.
     */
    function queryLeafs(
        SortitionSumTrees storage self,
        bytes32 _key,
        uint _cursor,
        uint _count
    ) public view returns(uint startIndex, uint[] values, bool hasMore) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];

        // Find the start index.
        for (uint i = 0; i < tree.nodes.length; i++) {
            if ((tree.K * i) + 1 >= tree.nodes.length) {
                startIndex = i;
                break;
            }
        }

        // Get the values.
        uint loopStartIndex = startIndex + _cursor;
        values = new uint[](loopStartIndex + _count > tree.nodes.length ? tree.nodes.length - loopStartIndex : _count);
        uint valuesIndex = 0;
        for (uint j = loopStartIndex; j < tree.nodes.length; j++) {
            if (valuesIndex < _count) {
                values[valuesIndex] = tree.nodes[j];
                valuesIndex++;
            } else {
                hasMore = true;
                break;
            }
        }
    }

    /**
     *  @dev Draw an ID from a tree using a number. Note that this function reverts if the sum of all values in the tree is 0.
     *  @param _key The key of the tree.
     *  @param _drawnNumber The drawn number.
     *  @return ID The drawn ID.
     *  `O(k * log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function draw(SortitionSumTrees storage self, bytes32 _key, uint _drawnNumber) public view returns(bytes32 ID) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = 0;
        uint currentDrawnNumber = _drawnNumber % tree.nodes[0];

        while ((tree.K * treeIndex) + 1 < tree.nodes.length)  // While it still has children.
            for (uint i = 1; i <= tree.K; i++) { // Loop over children.
                uint nodeIndex = (tree.K * treeIndex) + i;
                uint nodeValue = tree.nodes[nodeIndex];

                if (currentDrawnNumber >= nodeValue) currentDrawnNumber -= nodeValue; // Go to the next child.
                else { // Pick this child.
                    treeIndex = nodeIndex;
                    break;
                }
            }

        ID = tree.nodeIndexesToIDs[treeIndex];
    }

    /** @dev Gets a specified ID's associated value.
     *  @param _key The key of the tree.
     *  @param _ID The ID of the value.
     *  @return value The associated value.
     */
    function stakeOf(SortitionSumTrees storage self, bytes32 _key, bytes32 _ID) public view returns(uint value) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = tree.IDsToNodeIndexes[_ID];

        if (treeIndex == 0) value = 0;
        else value = tree.nodes[treeIndex];
    }

    /* Private */

    /**
     *  @dev Update all the parents of a node.
     *  @param _key The key of the tree to update.
     *  @param _treeIndex The index of the node to start from.
     *  @param _plusOrMinus Wether to add (true) or substract (false).
     *  @param _value The value to add or substract.
     *  `O(log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function updateParents(SortitionSumTrees storage self, bytes32 _key, uint _treeIndex, bool _plusOrMinus, uint _value) private {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];

        uint parentIndex = _treeIndex;
        while (parentIndex != 0) {
            parentIndex = (parentIndex - 1) / tree.K;
            tree.nodes[parentIndex] = _plusOrMinus ? tree.nodes[parentIndex] + _value : tree.nodes[parentIndex] - _value;
        }
    }
}

• No Contract Security Audit Submitted- Submit Audit Here

[{"constant":false,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_value","type":"uint256"},{"name":"_ID","type":"bytes32"}],"name":"set","outputs":[],"payable":false,"stateMutability":"nonpayable","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_cursor","type":"uint256"},{"name":"_count","type":"uint256"}],"name":"queryLeafs","outputs":[{"name":"startIndex","type":"uint256"},{"name":"values","type":"uint256[]"},{"name":"hasMore","type":"bool"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_ID","type":"bytes32"}],"name":"stakeOf","outputs":[{"name":"value","type":"uint256"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_drawnNumber","type":"uint256"}],"name":"draw","outputs":[{"name":"ID","type":"bytes32"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":false,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_K","type":"uint256"}],"name":"createTree","outputs":[],"payable":false,"stateMutability":"nonpayable","type":"function"}]

6108d0610030600b82828239805160001a6073146000811461002057610022565bfe5b5030600052607381538281f30073000000000000000000000000000000000000000030146080604052600436106100835763ffffffff7c01000000000000000000000000000000000000000000000000000000006000350416632e25c38a811461008857806365b81f4f146100ab5780637521ccb11461012557806388c1d467146101485780639075789e14610159575b600080fd5b81801561009457600080fd5b506100a9600435602435604435606435610177565b005b6100bf600435602435604435606435610464565b604051808481526020018060200183151515158152602001828103825284818151815260200191508051906020019060200280838360005b8381101561010f5781810151838201526020016100f7565b5050505090500194505050505060405180910390f35b610136600435602435604435610573565b60408051918252519081900360200190f35b6101366004356024356044356105c6565b81801561016557600080fd5b506100a9600435602435604435610697565b600083815260208581526040808320848452600381019092528220549091808080808086151561031157891561030c576001880154151561028257600288018054600180820183556000928352602090922081018c9055975087148015906101ed5750875460001988018115156101ea57fe5b06155b1561027d578754878115156101fe57fe5b04600081815260048a01602052604090205460028a0180549298509096506001890195509081908890811061022f57fe5b600091825260208083209091015483546001810185559383528183209093019290925587815260048a01808352604080832083905588835260038c0184528083208890558783529252208590555b6102d9565b600188018054600019810190811061029657fe5b6000918252602090912001546001890180549198506102b990600019830161085a565b508988600201888154811015156102cc57fe5b6000918252602090912001555b600089815260038901602090815260408083208a905589835260048b01909152902089905561030c8c8c8960018e6107c0565b610456565b89151561039f576002880180548890811061032857fe5b906000526020600020015492506000886002018881548110151561034857fe5b60009182526020808320909101929092556001808b01805491820181558252828220018990558a815260038a018252604080822082905589825260048b0190925290812081905561030c908d908d908a90876107c0565b600288018054889081106103af57fe5b90600052602060002001548a141515610456578988600201888154811015156103d457fe5b9060005260206000200154111591508161040b578988600201888154811015156103fa57fe5b906000526020600020015403610429565b6002880180548890811061041b57fe5b90600052602060002001548a035b905089886002018881548110151561043d57fe5b6000918252602090912001556104568c8c8985856107c0565b505050505050505050505050565b60008381526020859052604081206060908290818080805b60028501548410156104ac57600285015485548502600101106104a1578397506104ac565b60019093019261047c565b6002850154888b019350898401116104c457886104cd565b60028501548390035b6040519080825280602002602001820160405280156104f6578160200160208202803883390190505b509650600091508290505b60028501548110156105645788821015610553576002850180548290811061052557fe5b9060005260206000200154878381518110151561053e57fe5b6020908102909101015260019091019061055c565b60019550610564565b600101610501565b50505050509450945094915050565b6000828152602084815260408083208484526003810190925282205480151561059f57600092506105bd565b600282018054829081106105af57fe5b906000526020600020015492505b50509392505050565b60008281526020849052604081206002810180548391829182918291829190829081106105ef57fe5b90600052602060002001548881151561060457fe5b0693505b600286015486548602600101101561067957600192505b8554831161067457855460028701805491870285019350908390811061064157fe5b906000526020600020015490508084101515610661578084039350610669565b819450610674565b60019092019161061f565b610608565b50505060009182525060049091016020526040902054949350505050565b600082815260208490526040902080541561071357604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601460248201527f5472656520616c7265616479206578697374732e000000000000000000000000604482015290519081900360640190fd5b6001821161078257604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601b60248201527f4b206d7573742062652067726561746572207468616e206f6e652e0000000000604482015290519081900360640190fd5b8181556000610794600183018261085a565b5060006107a4600283018261085a565b5060020180546001810182556000918252602082200155505050565b6000848152602086905260409020835b801561085157815460001982018115156107e657fe5b049050836108115782826002018281548110151561080057fe5b906000526020600020015403610830565b82826002018281548110151561082357fe5b9060005260206000200154015b6002830180548390811061084057fe5b6000918252602090912001556107d0565b50505050505050565b81548183558181111561087e5760008381526020902061087e918101908301610883565b505050565b6108a191905b8082111561089d5760008155600101610889565b5090565b905600a165627a7a72305820f7b0b6cb20b64775129cdb830e5e8035676b7963618d7e4d6e2a3931d91377bc0029

0x737ae716d9935f41f173d944fe6557c1e117d561e930146080604052600436106100835763ffffffff7c01000000000000000000000000000000000000000000000000000000006000350416632e25c38a811461008857806365b81f4f146100ab5780637521ccb11461012557806388c1d467146101485780639075789e14610159575b600080fd5b81801561009457600080fd5b506100a9600435602435604435606435610177565b005b6100bf600435602435604435606435610464565b604051808481526020018060200183151515158152602001828103825284818151815260200191508051906020019060200280838360005b8381101561010f5781810151838201526020016100f7565b5050505090500194505050505060405180910390f35b610136600435602435604435610573565b60408051918252519081900360200190f35b6101366004356024356044356105c6565b81801561016557600080fd5b506100a9600435602435604435610697565b600083815260208581526040808320848452600381019092528220549091808080808086151561031157891561030c576001880154151561028257600288018054600180820183556000928352602090922081018c9055975087148015906101ed5750875460001988018115156101ea57fe5b06155b1561027d578754878115156101fe57fe5b04600081815260048a01602052604090205460028a0180549298509096506001890195509081908890811061022f57fe5b600091825260208083209091015483546001810185559383528183209093019290925587815260048a01808352604080832083905588835260038c0184528083208890558783529252208590555b6102d9565b600188018054600019810190811061029657fe5b6000918252602090912001546001890180549198506102b990600019830161085a565b508988600201888154811015156102cc57fe5b6000918252602090912001555b600089815260038901602090815260408083208a905589835260048b01909152902089905561030c8c8c8960018e6107c0565b610456565b89151561039f576002880180548890811061032857fe5b906000526020600020015492506000886002018881548110151561034857fe5b60009182526020808320909101929092556001808b01805491820181558252828220018990558a815260038a018252604080822082905589825260048b0190925290812081905561030c908d908d908a90876107c0565b600288018054889081106103af57fe5b90600052602060002001548a141515610456578988600201888154811015156103d457fe5b9060005260206000200154111591508161040b578988600201888154811015156103fa57fe5b906000526020600020015403610429565b6002880180548890811061041b57fe5b90600052602060002001548a035b905089886002018881548110151561043d57fe5b6000918252602090912001556104568c8c8985856107c0565b505050505050505050505050565b60008381526020859052604081206060908290818080805b60028501548410156104ac57600285015485548502600101106104a1578397506104ac565b60019093019261047c565b6002850154888b019350898401116104c457886104cd565b60028501548390035b6040519080825280602002602001820160405280156104f6578160200160208202803883390190505b509650600091508290505b60028501548110156105645788821015610553576002850180548290811061052557fe5b9060005260206000200154878381518110151561053e57fe5b6020908102909101015260019091019061055c565b60019550610564565b600101610501565b50505050509450945094915050565b6000828152602084815260408083208484526003810190925282205480151561059f57600092506105bd565b600282018054829081106105af57fe5b906000526020600020015492505b50509392505050565b60008281526020849052604081206002810180548391829182918291829190829081106105ef57fe5b90600052602060002001548881151561060457fe5b0693505b600286015486548602600101101561067957600192505b8554831161067457855460028701805491870285019350908390811061064157fe5b906000526020600020015490508084101515610661578084039350610669565b819450610674565b60019092019161061f565b610608565b50505060009182525060049091016020526040902054949350505050565b600082815260208490526040902080541561071357604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601460248201527f5472656520616c7265616479206578697374732e000000000000000000000000604482015290519081900360640190fd5b6001821161078257604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601b60248201527f4b206d7573742062652067726561746572207468616e206f6e652e0000000000604482015290519081900360640190fd5b8181556000610794600183018261085a565b5060006107a4600283018261085a565b5060020180546001810182556000918252602082200155505050565b6000848152602086905260409020835b801561085157815460001982018115156107e657fe5b049050836108115782826002018281548110151561080057fe5b906000526020600020015403610830565b82826002018281548110151561082357fe5b9060005260206000200154015b6002830180548390811061084057fe5b6000918252602090912001556107d0565b50505050505050565b81548183558181111561087e5760008381526020902061087e918101908301610883565b505050565b6108a191905b8082111561089d5760008155600101610889565b5090565b905600a165627a7a72305820f7b0b6cb20b64775129cdb830e5e8035676b7963618d7e4d6e2a3931d91377bc0029