Last active
November 16, 2021 03:13
-
-
Save fiddlemath/a8f556f7a68bc15c09116b57c51b9933 to your computer and use it in GitHub Desktop.
Python-ish pseudocode for O(1) RSR staking setup
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@dataclass | |
class CumulativeWithdrawal: | |
amount: int # total number of gray shares available | |
when_avail: int # timestamp when they'll become available | |
class stRSR: | |
def pool_rate() = total_pool_rsr / total_pool_shares #{ RSR / pool_share } | |
def gray_rate() = total_gray_rsr / total_gray_shares #{ RSR / gray_shares } | |
def __init__(self): | |
self.total_pool_rsr = 0 | |
self.pool_shares = defaultdict(int) # a map, where missing elements have zero value | |
self.total_pool_shares = 0 | |
self.total_gray_rsr = 0 | |
self.gray_shares = defaultdict(int) | |
self.total_gray_shares = 0 | |
# withdrawal queue is a mapping: | |
# user -> queue<CulmulativeWithdrawal> | |
# Gonna assume queue = withdraw_queue[user] is an int-indexible array, with properties .first and .last. | |
# When either .first or .last is changed, assume it auto-resizes that array. | |
# queue.push() increments .last and sets the contents at that new index. | |
self.withdrawl_queue = defaultdict(queue) | |
def stake(self, user, rsr_amount): | |
# Do user-specific withdrawal maintenance | |
self.commit_withdrawals(user) | |
# move RSR into the pool | |
pool_shares = rsr_amount / pool_rate() | |
self.total_pool_rsr += rsr_amount | |
self.pool_shares[user] += pool_shares | |
self.total_pool_shares += pool_shares | |
rsr.transfer(from: user, to: self, amt: rsr_amount) | |
def unstake(self, user, rsr_amount): | |
# Do user-specific withdrawal maintenance | |
self.commit_withdrawals(user) | |
# turn pool RSR into gray RSR | |
pool_shares = rsr_amount / pool_rate() | |
gray_shares = rsr_amount / gray_rate() | |
self.total_pool_rsr -= rsr_amount | |
self.pool_shares[user] -= pool_shares | |
self.total_pool_shares -= pool_shares | |
self.total_gray_rsr += rsr_amount | |
self.gray_shares[user] += gray_shares | |
self.total_gray_shares += gray_shares | |
self._save_withdrawal(user, gray_shares, block.timestamp + withdrawal_delay) | |
def addRSR(self, rsr_amount): | |
# Add RSR to the pool, only | |
self.total_pool_rsr += rsr_amount | |
rsr.transfer(from: msg.sender, to: self, amount: rsr_amount) | |
def seizeRSR(self, rsr_amount): | |
# Remove RSR pro rata from the pool AND the gray zone | |
rsr_from_pool = rsr_amount * total_pool_rsr / (total_pool_rsr + total_gray_rsr) | |
rsr_from_gray = rsr_amount * total_gray_rsr / (total_pool_rsr + total_gray_rsr) | |
self.total_pool_rsr -= rsr_from_pool | |
self.total_gray_rsr -= rsr_from_gray | |
rsr.transfer(from: self, to: manager, amount: rsr_amount) | |
def _save_withdrawal(self, user, gray_shares, when_avail): | |
self._commit_withdrawals(user) | |
queue = self.withdraw_queue[user] | |
prev = queue[queue.last()] | |
self.queue.push(CumulativeWithdrawal(prev.amount + gray_shares, when_avail)) | |
def commit_withdrawals(self, user): | |
now = block.timestamp | |
cwd, found_cwd = _find_cwd(user, now) | |
if !found_cwd: return | |
shares_to_withdraw = cwd.amount - self.gray_shares_withdrawn(user) | |
rsr_to_withdraw = shares_to_withdraw * gray_rate() | |
self.total_gray_rsr -= rsr_to_withdraw | |
self.total_gray_shares -= shares_to_withdraw | |
self.gray_shares[user] -= shares_to_withdraw | |
self.gray_shares_withdrawn[user] += shares_to_withdraw | |
rsr.transfer(from: self, to: user, amount: rsr_to_withdraw) | |
# Find the most-recent cumulative withdrawal, and delete all cumulative withdrawals up to and including it. | |
def _find_cwd(self, user): | |
now = block.timestamp | |
queue = self.withdraw_queue[user] | |
# Bianry search | |
left, right = queue.first(), queue.last() + 1 | |
middle = left | |
if queue[left].when_avail > now: | |
return (None, False) | |
while left < right - 1: | |
middle = floor(left + right / 2) | |
if queue[middle].when_avail <= now: | |
left = middle | |
else: | |
right = middle | |
output = queue[middle] | |
queue.left = middle + 1 # delete all scanned-over withdrawals | |
return (output, True) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment