An on-chain leaderboard for Solidity, efficiently supporting large data sets using an Augmented Left-Leaning Red-Black (LLRB) Tree.
On-chain leaderboards are tricky due to gas costs associated with sorting (
-
Logarithmic Operations: Inserts, deletes, and ranked lookups are
$O(\log n)$ , keeping gas costs predictable. - Self-Balancing: Ensures efficient operations without costly manual rebalancing.
- On-Chain Ranking: Tree augmentation allows efficient rank queries.
- FIFO Tie-Breaking: If two entries have the same score, this library prioritizes the entry that was inserted first (lower nonce), ensuring fairness based on submission order.
-
Embedded Library: Uses only
internal
functions, meaning the library code is embedded directly into your contract. No separate deployment of the library is required. - Multiple Leaderboards: Easily manage multiple independent leaderboards within a single contract.
This makes @trifle/leaderboard
ideal for on-chain games or DeFi applications needing efficient, gas-conscious ranked lists.
The Leaderboard
library operates on a Leaderboard.s
storage struct within your contract. You initialize each struct instance by calling its init
function, specifying the desired sorting order with the sortAscending
boolean argument:
init(true)
(Ascending Order): Suitable for scenarios where a higher score is better (e.g., points). The highest score getsrank 0
.init(false)
(Descending Order): Suitable for scenarios where a lower score is better (e.g., fastest time). The lowest score getsrank 0
.
Key Points:
- Tie-Breaking (FIFO): Regardless of the sorting order, if multiple entries have the same score, the entry that was inserted first (lower nonce) will always have the better rank.
- Index vs. Rank: It's important to distinguish between retrieving by index and retrieving by rank:
getValueAtIndex(i)
,getOwnerAtIndex(i)
,getIndexOfOwner(owner)
: These functions operate on the tree's internal 0-based index.index 0
always refers to the leftmost node according to the tree's comparison logic (smallest value if ascending, largest value if descending).index size-1
is always the rightmost node.getValueAtRank(r)
,getOwnerAtRank(r)
,getRankOfOwner(owner)
: These functions operate on a 0-based rank, whererank 0
always represents the most desirable score (highest score if ascending, lowest score if descending).rank size-1
is always the least desirable score.
This implementation builds upon the foundational work of previous on-chain sorted data structures:
- Rob Hitchens's OrderStatisticsTree: (https://github.com/rob-Hitchens/OrderStatisticsTree) - Provided an excellent self-balancing binary search tree with order statistics.
- BokkyPooBah's RedBlackTreeLibrary: (https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary) - An earlier red-black tree implementation.
While these libraries established the core tree structures, @trifle/leaderboard
introduces a crucial nonce-based mechanism to handle score ties based on insertion order, a feature we needed at trifle.
To use this library in your Hardhat or Foundry project, install it via npm or yarn:
npm install @trifle/leaderboard
# or
yarn add @trifle/leaderboard
- Import the Library:
Import
Leaderboard.sol
into your Solidity file. - Use the Library:
Apply the library to its storage struct
Leaderboard.s
. - Declare Storage:
Declare one or more variables of type
Leaderboard.s
in your contract's storage. - Initialize:
Call the
init
function on each storage variable, likely in your constructor or an initializer function. - Call Functions: Use the library functions directly on your storage variable.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "@trifle/leaderboard/contracts/Leaderboard.sol";
contract YourGameContract {
// Apply the library's functions to the Leaderboard.s struct
using Leaderboard for Leaderboard.s;
// Declare storage variables for one or more leaderboards
Leaderboard.s public highScores; // Ascending order (higher score is better)
Leaderboard.s public fastestTimes; // Descending order (lower time is better)
// Prevent multiple initializations (if using an initializer pattern)
bool private _initialized;
event Initialized(uint8 version);
// Use constructor or an initializer
constructor() {
_initialize();
}
function initialize() external {
// Example initializer pattern
require(!_initialized, "Already initialized");
_initialize();
}
function _initialize() private {
require(!_initialized, "Already initialized");
// Initialize each leaderboard instance
highScores.init(true); // true = ascending (high score wins)
fastestTimes.init(false); // false = descending (low time wins)
_initialized = true;
emit Initialized(1);
}
function recordHighScore(address player, uint256 score) external {
// Handles inserting or updating the player's score
highScores.insert(score, player);
}
function recordFastestTime(address player, uint256 time) external {
fastestTimes.insert(time, player);
}
function getPlayerRankHighScore(address player) external view returns (uint256) {
require(highScores.contains(player), "Player not on high score leaderboard");
// Rank 0 is the highest score
return highScores.getRankOfOwner(player);
}
function getPlayerRankFastestTime(address player) external view returns (uint256) {
require(fastestTimes.contains(player), "Player not on fastest time leaderboard");
// Rank 0 is the lowest time
return fastestTimes.getRankOfOwner(player);
}
function getTopPlayerHighScore() external view returns (address) {
require(highScores.size() > 0, "High score leaderboard is empty");
// Rank 0 is the highest score
return highScores.getOwnerAtRank(0);
}
function getTopPlayerFastestTime() external view returns (address) {
require(fastestTimes.size() > 0, "Fastest time leaderboard is empty");
// Rank 0 is the lowest time
return fastestTimes.getOwnerAtRank(0);
}
}
This project uses Hardhat.
- Compile contracts:
npx hardhat compile
- Run tests:
npx hardhat test
- Run gas benchmark tests:
REPORT_GAS=true npx hardhat test
Contributions are welcome! Please feel free to submit issues or pull requests.