Validator Selection
Saga Musical Chairs
In Saga, time is split into discrete epochs (i.e. 1 day). Developers pay for Chainlets on an epoch-by-epoch basis. Every validator in the Saga Mainnet publicly posts the price they would like to charge a developer to run a Chainlet for one epoch. Some time before the beginning of the next epoch, the validators’ bids are locked for the epoch, and a session of Musical Chairs begins to determine a universal price for running a Chainlet for the epoch. The validators’ bids are set for all future epochs until the validators indicate they would like to change their bids
Musical Chairs terms and definitions:
Total Set: The set of validators interested in being validators in the network. Anyone interested is able to join the total set.
Player Set: The set of validators who get to participate in the musical chair session.
Player Set Count (p): The number of validators in the Player Set.
Musical Chairs Price: The resulting price from the Musical Chairs auction. Used to set the Chainlet price of the next epoch.
Winning Set: The set of validators whose bid is less than or equal to the Musical Chairs Price.
Winning Set Count (w): The number of validators in the Winning Set.
Losing Set: The set of validators whose bid is greater than the Musical Chairs Price.
Losing Set Count (l) The number of validators in the Losing Set and l = p - w.
Active Set: The set of validators who get to validate Chainlets in the next epoch.
Step 1: Player Selection
The first step of Musical Chairs is to determine which validators participate in the game from the Total Set. The number of validators who are included in the Player Set is determined by the network as a parameter p. The validators in the Player Set are the top p validators by delegator stake weight. Our assumption in the Musical Chairs auction is that Saga may support a very large number of validators in the Player Set.
Step 2: Musical Chairs
The validators in the Player Set play a round of musical chairs to determine the Winning Set and the Losing Set. The parameter of the Chainlet price that the validator has configured for their validator will be pulled in for the current Musical Chairs session. The number of validators in the Winning Set is set as a parameter w. Saga sorts the validators in the Player Set by their auction bid. The cheapest w validators get included in the Winning Set. The remaining validators with the highest prices get included in the Losing Set.
Step 3: Price Setting
The price for the epoch is set by the most expensive validator in the Winning Set. This guarantees that every validator in the Winning Set receives Chainlets fees that are greater than or equal to the amount they bid.
Let’s go through an example system where p=10 and w=8. In the following example, there are 12 validators in the total set. Each validator’s price bid is denoted as dollar figures in the box. First, the Player Set is determined by rank ordering by stake weight: Validators 11 and 12 (the two validators with the least amount of stake) are excluded because p=10. Then, the Winning Set is determined by choosing the cheapest w validators in the Player Set. In the example, validators 2 and 7 are included in the Losing Set because their prices are the highest two bids from the player set. The Winning Set for the next epoch will be validators 1, 3, 4, 5, 6, 8, 9 and 10. Finally, the Chainlet price for the next epoch will be max(Winning Set), which is $5 in this example.
Step 4: Rewards and Punishment
The final step of Musical Chairs is to reward the Winning Set and punish the Losing Set. The Saga team is evaluating a number of methods to reward and punish these validators to incentivize the validators and delegators while keeping the security assumptions of the network intact. Here is one way:
The Active Set of the network in the next epoch is the Player Set. (Validators in both the Winning and Losing Set are included.)
Everyone in the Active Set receives Chainlet fees for the Chainlets they are validating.
However, the price is set by only the winning validators. Therefore, validators in the Losing Set are receiving less than their requested price.
Delegators to the validators in the Losing Set receive zero inflation from the network for the epoch. This directly incentivizes the validator to bid lower in the next epoch or risk their delegators re-delegating to other validators.
Another way the network could configure the rewards and punishment is:
The Active Set of the network in the next epoch is the Winning Set.
Validators in the Losing Set get kicked out of validating the next epoch.
Delegators to the validators in the Losing Set receive zero inflation from the network for the epoch. This directly incentivizes the validator to bid lower in the next epoch or risk their delegators re-delegating to other validators.
In the first scenario, the validators in the Losing Set still validate Chainlets, but receive less reward than they would have wanted. A validator who is in the Losing Set consistently will lose delegation because the delegators are not receiving any inflation rewards, which will eventually push the validator out of the Player Set.
In the second scenario, the punishment is more strict. Validators in the Losing Set are immediately kicked out of the Active Set and receive zero rewards and inflation. They also are no longer required to validate Chainlets. However, there are some security implications of removing large validators from the Active Set, and the Saga team is researching the best way to design the reward and punishment mechanism to minimize Chainlet costs (Tenet 3) while maintaining the security guarantees of a Proof of Stake network.
Properly Setting the Parameters
The parameters, w and p, and the punishment mechanisms are very important for the incentives of the network. If w is too small, too many validators will be punished. If w is set too high, the economics of commoditizing blockspace won’t function properly.
There are also security implications that we need to consider. A malicious actor can Sybil attack the Saga validator set to attempt to control the network or the outcome of the Musical Chairs process. It is notable that validators can attempt to collude/Sybil attack the Winning Set (bid prices low) or the Losing Set (bid prices high). The parameters need to consider both dynamics.
The Saga team’s current thought is that w needs to be approximately 75-85% of p. This makes w sufficiently large enough to ensure it is difficult to control the Winning Set. At the same time, a Losing Set size of 15-25% ensures that filling the Losing Set with Sybil validators is difficult.
Another lever Saga has to prevent Sybil attacks and collusion is to make the social cost of such attacks very high. Saga can, for example, include in its upcoming Constitution that a Sybil validator will be slashed fully to disincentivize such behavior.
Saga Chainlet Scheduler
How can the network further lower prices of Chainlets for developers (Tenet 3)? The Musical Chairs process determines the amount each validator will receive for each Chainlet, but the actual price that the developer pays will be (Musical Chairs Price x number of active validators for their Chainlet). The Musical Chairs Price variable is automatically reduced as validators compete to join the Winning Set, but we can also reduce the active validators per Chainlet to decrease the price that developers pay.
One way to reduce the number of active validators is to reduce the total number of validators participating in the network. However, this has decentralization and security implications that may not be ideal. There may be a way to increase the total number of validators but still reduce the number of active validators per Chainlet. Instead of requiring every validator on the Saga Mainnet to validate every Chainlet, we can relax the SLA requirement for certain validators and have a partial set validate each Chainlet. This can be accomplished using the Chainlet Scheduler.
Imagine the network sets a certain threshold of quorum for each Chainlet. Let’s arbitrarily pick 70% of total staked assets. For each Chainlet prior to the beginning of each epoch, the scheduler randomly selects a set of validators whose stake weight adds up to greater than or equal to the 70% threshold. There are many different ways to randomly select this set, but an easy way to do this is to keep picking individual validators randomly based on their stake weight until the set has greater than or equal to 70% stake weight. Let’s define the validators selected as s and those not selected as n. There will be a different set of {s,n} for each Chainlet per epoch. Only those in s are required to validate the Chainlet. Conversely, the SLA for the n validators are loosened to allow those validators to not validate the Chainlet.
The chart below shows the potential reduction in the number of validators per Chainlet when we apply this kind of scheduler on existing token distributions in the Cosmos ecosystem. A small reduction in quorum threshold and SLA can have a very significant impact on the number of validators.
There are some nice behaviors that result from utilizing this kind of scheduler. First, we can guarantee that every Chainlet will have the full security of the Saga Mainnet. Second, because the number of validators per Chainlet is significantly reduced, the total price for developers will also go down (Tenet 3). By setting a quorum threshold, below 100%, we are able to cut down on the steepest part of the cost curve. Third, the number of Chainlets each validator validates will be proportional to their stake weight. This means the top validators will validate all Chainlets, while validators with little stake weight will be required to validate a very small number of Chainlets. This makes validator requirements for smaller validators significantly less than those for larger validators. We can vary the total threshold level and see how many Chainlets each validator ends up validating. We can see that regardless of the threshold level, there is a much smaller number of Chainlets in the tail end validators.
There are some complications that may arise with a scheduler.
First, with a lower quorum threshold, the risk of stalling due to a downed validator increases. With a threshold rate of 70%, a validator with 4% of stake may halt Chainlets if they accidentally go down since a quorum of 66% won’t be possible. In reality, this threshold will likely be set by governance targeting a minimum failure tolerance for validators going down.
Second, a random sampling scheduler may vary the number of validators per Chainlet from one epoch to another. The Saga team has simulated a simple random sampling scheduler and found that the number of validators per Chainlet follows a normal distribution and is kept fairly consistent across epochs. Saga can employ a more sophisticated scheduler to make the distribution tighter, making the cost for developers less lumpy from one epoch to another. Also, in all scenarios, the scheduler reduces the number of validators vs. the whole validator set. Even if there are small variations for developers, the cost will always be less than the price without the scheduler.
Finally, every validator will be validating a different set of Chainlets every epoch. This means that we will need to implement fast-syncing of blockchain data (state and mempool) across validators to make sure there is an automatic transition of validator sets between epochs. One way to solve this problem is to require the top validators to always validate every Chainlet. The number of validators in this set can be parameterized using governance. This way, there is always a consistent set of validators to state sync as the other validators swap between Chainlets to validate.
Last updated