Stacking: a New Consensus Algorithm for Blockchains

[jude]

Hi @shea256, thanks for your feedback!

We’ve been calling the scenario you just described “free-mining,” whereby a miner who knows their addresses are going to be picked for the next round of PoX rewards has every reason to transfer as much BTC as they possibly can in order to win sortition “for free” (since they’d be getting their BTC back in the overwhelmingly-likely case that they win). There’s a variation of PoX whereby miners are required to burn at least b% of their BTC no matter what, which reduces the problem from mining blocks for free to mining blocks with a maximum discount.

I think your proposal is interesting, but I have a few questions:

The way to fix this would be to add a third phase in the beginning in which miners must commit to a given round and post collateral before the recipient addresses in that round are revealed. If this is done, then the collateral can be seized if the miner does not actually participate in the round.

The collateral can be posted in Stacks by having the miner send a commitment transaction from an address with a Stacks balance. The protocol has control over the Stacks balances, so it has the capacity to seize the collateral in the instance that a miner fails to send the Bitcoin in the round.

I think what you saying is that before the “prepare” phase (where Stackers bless the fork), there’d be a phase where miners put up a STX collateral for each Bitcoin sortition they intend to participate in. If a miner intends to mine a Stacks block in Bitcoin block B, they have to lock up some number of STX that effectively constitutes a promise that at Bitcoin block B, they’ll send a PoX transaction. If they do, they’ll get their STX back. If they don’t, the STX will be burnt. Is my understanding correct?

If this is what you mean by “commit to a given round,” then aren’t the following still true?

• Miners still have a chance of free-mining if their Stacker reward addresses are selected for Bitcoin block B – i.e. a miner can get lucky.
• A STX whale miner can post collateral for every Bitcoin block in the reward period and be guaranteed that they’ll get to free-mine.

The amount of Stacks required to be posted as collateral could be the same amount as the potential reward for that block. This would ensure that there is no possible way that any miner could cheat and come out net positive.

I think you’re saying here that miners have to put up an entire STX coinbase as collateral? There’s no way to know in advance how many STX a miner will receive from a block, however, since the miner doesn’t know how much transaction fees they’ll get. Doesn’t this mean that the protocol-dictated collateral is potentially too low, in any case?

[shea256]

If they do, they’ll get their STX back. If they don’t, the STX will be burnt. Is my understanding correct?

Yes this is correct.

Miners still have a chance of free-mining if their Stacker reward addresses are selected for Bitcoin block B – i.e. a miner can get lucky.

I’m not saying there’s an issue with free-mining. I’m saying there’s an issue with only free-mining. Committing before the “prepare” phase means that you can only free-mine probabilistically. You can’t do so opportunistically.

[shea256]

I think you’re saying here that miners have to put up an entire STX coinbase as collateral? There’s no way to know in advance how many STX a miner will receive from a block, however, since the miner doesn’t know how much transaction fees they’ll get. Doesn’t this mean that the protocol-dictated collateral is potentially too low, in any case?

Yes, there are two options here. Either (a) put up the entire STX Coinbase, which is a lot but solves the problem, or (b) figure out a way for the protocol to “know” the exchange rate between BTC and STX.

[jude]

I’m not saying there’s an issue with free-mining. I’m saying there’s an issue with only free-mining. Committing before the “prepare” phase means that you can only free-mine probabilistically. You can’t do so opportunistically.

Ah, I’m more pessimistic. I think that free-mining should be prohibited at all times, as a hedge against any future attacks STX and/or BTC miners and/or Stackers can come up with after the protocol gets launched. I’m worried that the minute it becomes possible to free-mine in any circumstance, economic efficiencies will ensure that eventually, only free-miners can afford to mine.

[ryan]

Ah, I’m more pessimistic. I think that free-mining should be prohibited at all times, as a hedge against any future attacks STX and/or BTC miners and/or Stackers can come up with after the protocol gets launched. I’m worried that the minute it becomes possible to free-mine in any circumstance, economic efficiencies will ensure that eventually, only free-miners can afford to mine.

OK so at a minimum it seems we agree the current arrangement is problematic.

Do you believe that requiring a commitment before the “prepare” phase is a strict improvement?

I’d argue it fully addresses the problem, but it seems you don’t believe that.

The reason I say this is because everyone gets the same deal and there is no strategy that can be employed to selectively mine.

The problem arises when there are dominant strategies that can be employed to outcompete others.

With a commitment to participate before you see the recipient addresses, I believe this is addressed.

[ryan]

My second proposed modification would be to revisit the method of:

1. Cycling through all addresses
2. Having a minimum threshold for participation

Why not reset the randomization every time instead of rotating through addresses in round robin fashion? And why not just remove the threshold?

I see why one would want to cycle through all the addresses - this allows you to guarantee that all addresses will get paid out in a given time period. But I would say that if you do a random selection each and every round then you will probabilistically get everyone paid out the same.

As a thought experiment, if you and I play a game where we flip coins, and I call heads on the first round and win, we don’t force the second round to come up tails. We keep the same odds every round. Yes, I could win 3 times in a row with 3 heads in a row, or you could win 3 times in a row with 3 tails in a row, but as the number of flips goes up the distribution approaches 50-50. This is closer to what Bitcoin mining is.

I fear that moving away from probability and towards supposed “equality guarantees” (with a round robin system), we’re creating a more complex system that isn’t actually more equal.

One alternative would be to allow for any address to participate (without pooling), and for their participation to be weighted proportional to the number of Stacks they have in their addresses. This would mean addresses with 100,000 Stacks would be chosen 10x as often as addresses with 10,000 Stacks.

Pooling would become an emergent property rather than a built-in feature.

And yes, one should be concerned about excessive transactions with lower thresholds to participate, but the high transaction fees (as a percentage of revenue) for the smaller participants would mean that there would be natural incentive for the smaller participants to pool. This should lead to a reduction in transaction volume.

[jude]

A key advantage of the randomized round-robin approach is that it puts an upper-bound on reward frequency. A participant will receive BTC within the reward cycle if the system is working. This is not true for probabilistic approaches.

[ryan]

My third proposed modification is a method for significantly reducing the variance of payouts from one address to another, while also reducing the amount of data load on the blockchain.

First, when we think about variance, we should consider that for any given set of eligible mining addresses, there is a fixed period it will take for the expected variance to fall below a desirable threshold. This expected variance is the same whether the rounds have an independent probability (like coin flips) or whether one employs a round robin approach to cycle through all addresses before restarting a round cycle.

Second, when we think about minimizing load on the Bitcoin blockchain, we should not be focusing on the total number of transactions, but rather the total number of bytes. Bitcoin addresses are priced in bytes and the scarce resource is bytes. Transactions scale with the number of inputs and outputs. A transaction with 1 input and 7 outputs (5 recipients, 1 change address, 1 data field) can lead to approximately 2x the data load as a transaction with 1 input and 3 outputs (1 recipient, 1 change address, 1 data field).

Now for the proposed modification.

In SIP-007, the proposal features a mechanism where in every round, a new set of 5 addresses is randomly selected to be the recipients of the proof-of-transfer process.

I propose changing this so that in each round, instead of requiring all miners to send to the same 5 recipients, the protocol randomly selects a distinct address for each miner, which serves as the recipient for the miner’s proof-of-transfer transaction.

For example, imagine that in a hypothetical system there are 5000 miners and 5000 addresses with equal balances. Then in each round, each address should probabilistically be the recipient of 1 mining transaction on average (#2438 would send to #1872, while if #1872 is mining it would send to #4831, and so on).

In a hypothetical system with 5000 addresses with unequal balances, the probability of being selected in any given round-miner-pair would be proportional to the balance of the hodling address.

Address selection would be accomplished by taking the same verifiable random function (VRF), producing a new seed in every round using the VRF, and combining the seed with the address of every pre-committed miner to produce the full list of miner-specific addresses for that round.

This would result in a web of sending in every given round, rather than all miners sending to the same recipients every round.

Variance of earning Bitcoin via the mining process would be significantly reduced, since in every single round a hodler would have N chances to be chosen as the recipient, where N is the number of miners.

Data used per round would also be reduced, since instead of 5000 miners sending 5000 7-output transactions each round, 5000 miners would be sending 5000 3-output transactions each round.

Hope this is helpful and curious to know what you think. Happy to elaborate further or answer any questions you have.

[jude]

I propose changing this so that in each round, instead of requiring all miners to send to the same 5 recipients, the protocol randomly selects a distinct address for each miner, which serves as the recipient for the miner’s proof-of-transfer transaction.

The PoX protocol, by design, does not know which miners exist a priori, and therefore cannot assign miners an address to send to. It only assigns addresses to blocks, which any miner(s) must send to whether they like it or not.

Such a scheme could only work in conjunction with a “miner registration” system whereby miners announce their intentions to mine on a particular block. Such a scheme would also be extremely risky, since it would enable free-mining if miners had any freedom to choose which addresses they could send to – they’d only ever send to themselves, or at least try and bias it so that their addresses have a better-than-random chance of being selected. The fact that miners must send to a particular set of address that they cannot choose is a feature, not a bug.

[ryan]

The PoX protocol, by design, does not know which miners exist a priori , and therefore cannot assign miners an address to send to. It only assigns addresses to blocks, which any miner(s) must send to whether they like it or not.

Such a scheme could only work in conjunction with a “miner registration” system whereby miners announce their intentions to mine on a particular block.

With this proposal the protocol wouldn’t need to know which miners exist a priori. Each miner would take the seed for the round and combine it with their own address and the list of recipient addresses to deterministically figure out the recipient they need to send to.

Such a scheme would also be extremely risky, since it would enable free-mining if miners had any freedom to choose which addresses they could send to – they’d only ever send to themselves, or at least try and bias it so that their addresses have a better-than-random chance of being selected. The fact that miners must send to a particular set of address that they cannot choose is a feature, not a bug.

This is proposed to be in combination with a pre-commitment process with collateral, which seems to be required anyway to prevent gaming. If this pre-commitment with collateral is implemented, then opportunistic free-mining would not be possible.

[muneeb]

Love the proposal and love the idea of updating the proof-of-burn system to a proof-of-transfer system. Seems like a clear upgrade.

I think it’s a clear upgrade to SIP-001 as well!

I’m going to boil down the above discussion into a few topics and then comment.

Discounted Mining:

We plan to update SIP-007 with a discussion on discounted mining. I think “free mining” is a potentially misleading term for this because the discount is in the 10-20% range given no. of slots and the probability of the discount being 90% or whatever is negligible.

A miner’s main motivation to mine should be the STX coinbase, transaction fees (in STX), and Clarity contract fees (in STX). This decision to mine or not mine needs to be made by the miner for the vast majority of the blocks (where the miner does not have an address) and the miner will decide to mine if it’s profitable to do so.

No miner will mine at a loss, it’s about how much profit can a miner make. It’s a local decision that every miner makes, a miner will not even know if someone else is engaging in discounted mining or not.

Sporadic Mining:
If a miner decides that it only makes sense to mine in blocks where she has a payout addresses then that will likely result in sporadic mining where say that miner is participating only in a small subset of blocks.

First, I think the miner does not have the right incentives to participate in sporadic mining. The STX coinbase is not a guarantee but a probability. If you mine sporadically then you are potentially hurting your chances to get the STX coinbase vs mining regularly.

Secondly, you can make it harder for miners to participate in sporadic mining. You can introduce a minimum participation window. For example, if you don’t participate in at least 10 consecutive blocks as a miner then you don’t qualify for the STX coinbase at all. This takes the 10-20% discount to a 1-2% discount and can make it even smaller by increasing the size of the minimum participation window.

Interestingly, an earlier version of STX mining had a window and we got rid of it due to some potential unintended consequences. It might be worth exploring if a modification of a sliding window in the form of a “minimum participation threshold” makes sense.

Thanks for the discussion around discounted mining! It definitely opens interesting discussions and design tradeoffs.

[muneeb]

For any readers following along I think it’s important to put some of these in a more practical/realistic scenario.

Practical Scenario: Let’s say a miner is willing to put up significant capital, say $1M, to take advantage of discounted mining. At the current ~$0.10 price that is roughly 10M STX or 2.0% of the liquid supply (current circulating supply is ~508M STX). 2% of liquid STX means that this miner now gets 100 out of ~5000 slots for a payout and would need to make a decision about mining (or not mining) in the vast majority of the blocks where the miner does not have an address.

Also, it’s unclear to me if this behavior is net negative to the ecosystem, especially in the initial year(s). There are crypto-assets like BNB (Binance) where holders of BNB get a discount on trading. Miners who want to use discounted mining are providing value to the network by becoming longer-term holders. There is very clearly a cost to the miner for locking $1M USD in Stacking to get discounts vs using that money somewhere else.

The sliding window mentioned above (which was part of an earlier design for a different reason) addresses this issue anyway but it’s interesting to explore what positive/negative impacts this miner behavior can have.

[muneeb]

reset the randomization every time instead of rotating through addresses in round robin fashion?

We debated the two designs and their pros/cons. Ultimately the question is that do we want a system that behaves more like a lottery or a system that behaves more like “I hold STX and do work that is useful to the network and get a predictable payout from the network each month”.

We can certainly discuss modifications to the two approaches where they start looking a bit more like each other but the lottery vs predictable monthly payouts for work is a central design question. SIP-007 is in the camp of predictable monthly payouts for work. Interesting to explore randomness and how that impacts potential Stackers and their incentives.

5000 miners sending 5000 7-output transactions each round, 5000 miners would be sending 5000 3-output transactions each round.

I like the data reduction aspect of this. The 5000 miners number looks very high to me and might not be realistic, especially in the initial year(s).

Large crypto projects struggle to get full-nodes in that range and having independent miners in 5K range is even harder. We’re currently debating a minimum threshold for no. of miners that can trigger a switch from Stacks 1.0 to Stacks 2.0 and are debating 10-20 miners as a range.

[ryan]

I like the data reduction aspect of this. The 5000 miners number looks very high to me and might not be realistic, especially in the initial year(s).

Glad you like that! Would be awesome to cut the data usage in half.

The part I think is an even bigger improvement with the proposal is the enormous increase in payout frequency.

(I used the 5000 figure for number of miners but we can do thought experiments with other orders of magnitude)

Let’s assume 5000 addresses at 0.02% holdings each.

• w/ 50 miners, each address would get paid out every 100 blocks vs every 1000 blocks (10x)
• w/ 500 miners, each address would get paid out every 10 blocks vs every 1000 blocks (100x)
• w/ 5000 miners, each address would get paid out once per block vs every 1000 blocks (1000x)

And all that with 1/2 the amount of data transmitted on the blockchain.

[ryan]

Here are some charts to help visualize the payout schedule:

With these visualizations, I chose to go simple and assume the randomization always places one in the middle of the set. A better visualization would show proper randomization, leading to a more unexpected placement of the spikes. But the basic differences in variance would be the same, so this should properly illustrate the point.

[fluidvoice]

Stacking rewards encourage users to support honest miners through things like user support burns (see SIP 001) in order to help honest miners win.

I don’t understand this. Can you explain? What are “user support” burns?

[jude]

Per SIP 001, anyone can burn (not transfer) BTC in support of another block-commit in the same block. The idea is that if there are users (i.e. non-miners) who want a particular block to have a high chance of winning, they can “help out” the miner by burning some BTC in favor of that block. By making a separate transaction type for doing this, users don’t need to coordinate with one another or with the miner to do so – they can do it spur-of-the-moment just by looking at the (Bitcoin) mempool and looking at the unconfirmed block-commit transactions.

The reason users would want to do this at all are two-fold:

• Users get a fraction of the coinbase proportional to their contribution if the block they support wins.
• If there’s a miner-based attack ongoing like a selfish mining cartel, users can tip the balance of power towards the coalition of honest miners in order to harm the cartel.

User support burns not only get us decentralized mining pools, but also in doing so, give users a greater say in the evolution of the chain state.

[Sirlupinwatson1]

@shea256 Hi,

The way to fix this would be to add a third phase in the beginning in which miners must commit to a given round and post collateral before the recipient addresses in that round are revealed. If this is done, then the collateral can be seized if the miner does not actually participate in the round.

Good coding idea, just to add sort of a script pool that would relay on a node and support every stackers while running in parallel with the miner client.

[fluidvoice]

Per SIP 001, anyone can burn (not transfer) BTC in support of another block-commit in the same block. The idea is that if there are users (i.e. non-miners) who want a particular block to have a high chance of winning, they can “help out” the miner by burning some BTC in favor of that block. By making a separate transaction type for doing this, users don’t need to coordinate with one another or with the miner to do so – they can do it spur-of-the-moment just by looking at the (Bitcoin) mempool and looking at the unconfirmed block-commit transactions.

The reason users would want to do this at all are two-fold:

• Users get a fraction of the coinbase proportional to their contribution if the block they support wins.
• If there’s a miner-based attack ongoing like a selfish mining cartel, users can tip the balance of power towards the coalition of honest miners in order to harm the cartel.

User support burns not only get us decentralized mining pools, but also in doing so, give users a greater say in the evolution of the chain state.

Could big monied “whale” miners/users also use this to tip the balance of power towards their own or other miners? This would be easier/faster to do than spinning up mining hardware, so does this make one type of attack easier?

[jude]

Could big monied “whale” miners/users also use this to tip the balance of power towards their own or other miners? This would be easier/faster to do than spinning up mining hardware, so does this make one type of attack easier?

There’s no mining hardware in the first place beyond your laptop, so it doesn’t make it any easier than simply running a miner themselves. You’re right in that someone with a lot of BTC could out-mine everyone else, but that’s true with or without user burn supports.

Also, a subtlety – a whale miner would have to out-burn everyone else for at least N Bitcoin blocks in order to execute an N-deep reorg. It’s not enough that a whale can just out-burn everyone else; they have to do so consistently. This is a departure from traditional PoW systems, which rely on the most work done (even if the resulting fork has fewer blocks). It’s possible to do this safely in Stacks because unlike PoW blockchains, all Stacks peers have a global understanding of time (i.e. Bitcoin block height), which allows them to measure a fork’s quality as the number of sortitions it contains.