stacks-network / stacks-core

The Stacks blockchain implementation
https://docs.stacks.co
GNU General Public License v3.0
3.01k stars 666 forks source link

Fees: Implement Kth-highest Transaction Fees #1190

Closed jcnelson closed 3 years ago

jcnelson commented 4 years ago

~The Vickrey auction-based block reward implementation from SP1 is broken, and will need to be fixed for SP2 (once we figure out how to ensure the static analysis code remains outside of the consensus code).~

Slight correction -- technically, this isn't a Vickrey auction because bids aren't sealed. But, we do need to make it so the Kth-highest transaction fee rate sets the transaction fee rate for all transaction in an epoch, subject to the rules below:

jcnelson commented 4 years ago

The rules are as follows:

diwakergupta commented 4 years ago

Not necessarily a Neon blocker, we can push something simple now and add more nuance later.

jcnelson commented 4 years ago
kantai commented 3 years ago

My understanding of the original thinking is roughly:

  1. Transactions should be charged for their consumed scalar execution units.
  2. The rate at which transactions are charged is the Kth highest fee rate in the block (I'm not sure what K is exactly here -- is it the lowest fee rate in the block?)

The above can be hard to implement directly, because accounts must be charged before transaction execution. Other blockchains that implement similar pricing schemes typically do an overcharge and refund. We can support that using fee amount, rather than fee rate:

  1. Transactions broadcast a fee amount, not a rate. This, however, is effectively a rate, because nodes in the network measure the scalar "execution cost" of each transaction.
  2. After executing the transaction, nodes can measure the rate. Miners interested in doing an efficient block fill can use static analysis to aid in this process (to avoid an exponential bin-packing problem in which they need to re-execute the transactions on each attempt).
  3. After executing the block, the fee rate is calculated based on the measured fee rates of the transactions in the block.
  4. Refunds are issued to accounts with higher fee rates than the block rate.

The only thing unclear to me is how to compute the "block rate".

kantai commented 3 years ago

Reading (https://arxiv.org/pdf/1901.06830.pdf, page 13), which I think is the motivation for this mechanism, they propose:

  1. Using the minimum fee (in our case, this would be fee rate) in the block as the block fee.
  2. Requiring all blocks be filled, or: a. Miners declare that the mempool is "empty", so the block does not need to be filled, in which case the fee rate charged is always the "minimum fee rate". b. Miners pay a fill penalty, which is (fill - actual_fill_amount) * block_fee
  3. Miners share transaction fees across blocks.

Without 2 and 3 above, the scheme does not incentivize good behavior on the part of miners. Implementing 2 is possible, though we would likely need to use a fairly low fill number, because of the dimensionality of our block limit (even though it can be collapsed to a scalar, the limit itself is multi-dimensional). 3, however, is a new mechanism, that we'd previously decided against multiple times.

jcnelson commented 3 years ago

The above can be hard to implement directly, because accounts must be charged before transaction execution. Other blockchains that implement similar pricing schemes typically do an overcharge and refund. We can support that using fee amount, rather than fee rate:

I took a stab at implementing this a long time ago, before I got side-tracked into working on more important issues (I think it was around the time of the Neon launch). I had a solution that was easier than this.

The way I solved this problem was to alter the Coinbase transaction wire format so that it included what the Kth highest fee rate ought to be for the epoch it confirmed (i.e. the Kth highest rate for all transactions in the block's parent microblock stream as well as the block's included transactions). The miner would calculate what K was as part of building the anchored block, and would write it to the Coinbase once it had finished mining transactions. Then, other nodes would use this value as the going fee rate when evaluating the parent microblocks and the block transactions, and would re-calculate K as they were processing the transactions. If the node's final K matched the miner's K, and all transactions were sufficiently funded, then the epoch was valid. If the node calculated a different K, or any transaction was insufficiently funded, then the node rejected the block. This had the side-effect of making K a consensus-critical value, but I think this is already something we wanted anyway.

Without 2 and 3 above, the scheme does not incentivize good behavior on the part of miners. Implementing 2 is possible, though we would likely need to use a fairly low fill number, because of the dimensionality of our block limit (even though it can be collapsed to a scalar, the limit itself is multi-dimensional). 3, however, is a new mechanism, that we'd previously decided against multiple times.

I'm not sure we need to do (3) for this to work. Without averaging the transaction payouts over B blocks, miners ought to be even more incentivized to include the K-highest paying transactions, because they receive those fees exclusively. In our case, it's a little bit more complicated -- miners are incentivized to make it so the K-highest-paying transactions are anchor-able transactions instead of streamable transactions, since they receive those fees exclusively. In addition, they are incentivized to confirm as many streamable transactions as possible if there are fewer than K anchored transactions available, since this minimizes their fill penalty. By making it so that a miner's K value is determined from both the transactions it confirms in its parent microblock stream and the transactions it mines in its anchored block, we make it so a miner's payout is maximized by first confirming as many streamed transactions as they can (to avoid the fill penalty), and then to mine as many high-value anchorable transactions as we can (to maximize profits). What this ought to mean in practice is that a transaction that can be either streamed or anchored will be anchored if possible (since this maximizes profits -- a miner keeps 100% of the transaction fee instead of 40%), but a stream-only transaction will still be confirmed (since this minimizes fill penalty, and if the fee is high enough, bumps up K).

What do you think?

kantai commented 3 years ago

The above can be hard to implement directly, because accounts must be charged before transaction execution. Other blockchains that implement similar pricing schemes typically do an overcharge and refund. We can support that using fee amount, rather than fee rate:

The way I solved this problem was to alter the Coinbase transaction wire format so that it included what the Kth highest fee rate ought to be for the epoch it confirmed (i.e. the Kth highest rate for all transactions in the block's parent microblock stream as well as the block's included transactions). The miner would calculate what K was as part of building the anchored block, and would write it to the Coinbase once it had finished mining transactions. Then, other nodes would use this value as the going fee rate when evaluating the parent microblocks and the block transactions, and would re-calculate K as they were processing the transactions. If the node's final K matched the miner's K, and all transactions were sufficiently funded, then the epoch was valid. If the node calculated a different K, or any transaction was insufficiently funded, then the node rejected the block. This had the side-effect of making K a consensus-critical value, but I think this is already something we wanted anyway.

I don't think this solves the problem -- the problem isn't knowing K, it's knowing the execution cost of the transaction. If the execution cost of the transaction is x, we want to charge Kx, but we can only estimate the execution cost before execution (even using a static analysis which provides x' > x, we wouldn't want to charge Kx', because it is an overcharge).

I'm not sure we need to do (3) for this to work. Without averaging the transaction payouts over B blocks, miners ought to be even more incentivized to include the K-highest paying transactions, because they receive those fees exclusively.

The problem with not averaging transaction fees over a window is that miners are capable of generating and including as many transactions as they want to fill a block. Because they receive 100% of the tx fees for those transactions, they can use a high fee rate on those transactions, such that miners are now capable of arbitrarily circumventing the block-fill requirement. And without the block-fill requirement, the fee auction is no longer efficient.

jcnelson commented 3 years ago

I don't think this solves the problem -- the problem isn't knowing K, it's knowing the execution cost of the transaction. If the execution cost of the transaction is x, we want to charge Kx, but we can only estimate the execution cost before execution (even using a static analysis which provides x' > x, we wouldn't want to charge Kx', because it is an overcharge).

The node shouldn't need to know x a priori, nor should it need to know any bounds on it. The node should only need to be able to calculate x on-the-fly when evaluating the transaction. It would do the following:

let K be the fee rate for the epoch
for each transaction tx in the epoch:
   let cost_budget_before = get_cost_so_far()
   run_transaction(tx)
   let cost_budget_after = get_cost_so_far()
   if cost_budget_after exceeds the epoch cost budget:
      reject the epoch
      return
   let cost_used = cost_budget_after - cost_budget_before  // this is x
   let tx_fee = cost_used * K
   if get_balance_of_payer(tx) < tx_fee:
      reject the epoch
      return
   debit_account_payer(tx, tx_fee)

As you point out, the exact value of x cannot be calculated a priori because it may depend on chainstate. So to be safe, a miner would want to mine transactions whose accounts have enough balance to cover the maximum execution cost of their transactions. Fortunately, this should already be known to the miner, since the node can pre-compute this:

The problem with not averaging transaction fees over a window is that miners are capable of generating and including as many transactions as they want to fill a block. Because they receive 100% of the tx fees for those transactions, they can use a high fee rate on those transactions, such that miners are now capable of arbitrarily circumventing the block-fill requirement. And without the block-fill requirement, the fee auction is no longer efficient.

Ah, yes, I see -- we'll want to do some kind of pay-it-forward with anchored transactions. So, regarding this:

3, however, is a new mechanism, that we'd previously decided against multiple times.

I know we're adamantly opposed to miners smoothing coinbases, and I don't think this fee approach requires it. But, if I recall correctly, the thrust of the argument against sharing transaction fees is that we want to discourage free-riding. We don't want a lazy miner receiving a fraction of its parent's transaction fees, plus a coinbase, for doing nothing but mine an empty block. Fortunately, this fee strategy should mitigate this somewhat:

What should b be? The trade-offs are as follows:

So, what's the smallest b whereby we expect it to be unprofitable for miners to pack anchored blocks? Is b = 2 good enough? If the network has a high transaction load, the cost of pushing K up beyond market demand would increase, since users would be competing with miners.

kantai commented 3 years ago

Debiting after execution works fine for block validation, but it significantly complicates mempool admission (how does a node know that a transaction has enough balance to cover its fee without trying to estimate execution cost?) and will complicate mining, whereas I'm still not sure what the downside of doing a debit -> execute -> refund is (it also provides a specific upper bound to the user/transaction signer what the maximum tx fee is without relying on wallet providers to do cost estimation).

Regarding transaction fee sharing, the choice of b depends on a lot of empirical data: the number of miners, the fees that users broadcast, etc. A low b, like 2, would likely make block filling to boost K still very profitable, because the miner may be paying a 50% fee to boost K, but if the alternative is mining a minimum cost block, that can still be profitable. ~It would also mean that any miner's profit maximizing behavior would be to try to boost K in all blocks they try to mine after a block in which they won~ (EDIT: Not exactly, but miner share definitely impacts the behavior here). Also, regarding the choice of a penalty, a miner must be able to choose which kind of penalty they pay (the rationale for this is discussed in the paper):

  1. Miner claims that there just aren't enough transactions to fill a block. In this case, K is set to the minimum fee rate. No other penalty applies.

  2. Miner doesn't fill block, K is set to the lowest fee rate in the block, but miner pays a penalty.

Strictly speaking, a miner would never choose (2) if (transaction fees - penalty) < (minimum fee rate * transactions), which would mean that the penalty could never eat into the coinbase. So there's always a little bit of an incentive in this scheme to "free ride" as a miner: just by claiming the minimum fee rate because the mempool isn't full, and taking the fractional rewards from the b window. Thinking about this more closely, it seems like the choice of b is very important, and there's no recommendations on how to choose b from the paper (indeed, the forces acting on the choice of b would be expected to change dramatically over the lifetime of a blockchain).

At this point, I think my feelings are that we should not attempt to perform auction-based fee pricing at launch. It's solving for a problem (over priced fees) that the Stacks chain is very unlikely to have for the first year or so of its life, and if anything, complicates the incentives for miners to participate early on in the lifetime of the blockchain, which is when miner participation is perhaps most important. I'm not wholly convinced by the arguments of this paper, and there's a lot of tuning parameters here that don't seem to have obvious answers. Further, sharing transaction fees is in opposition to much of the design that we'd previously proposed to various network stakeholders, and I think we should be pretty wary of altering that design unless there is a very clear benefit to doing so, and I am less than sure of that.

jcnelson commented 3 years ago

Debiting after execution works fine for block validation, but it significantly complicates mempool admission (how does a node know that a transaction has enough balance to cover its fee without trying to estimate execution cost?) and will complicate mining, whereas I'm still not sure what the downside of doing a debit -> execute -> refund is (it also provides a specific upper bound to the user/transaction signer what the maximum tx fee is without relying on wallet providers to do cost estimation).

Debit -> execute -> refund is 2x as expensive as just a debit -- you're doing two MARF reads/writes instead of one. Also, you can't switch to the more efficient one read/write later -- these are visible changes to the MARF, so they'll be visible in Clarity, meaning we'd be stuck with it unless we did a hard fork.

The miner code is already written to handle transactions aborting at runtime, so I'm not sure what the problem there is? The miner can still just try to include all minable transactions in the mempool (i.e. in fee-rate order and nonce order) and omit the ones that abort due to having an insufficient balance (just as how it would omit transactions that, say, failed post-condition checks). Also, the mempool today only rejects transactions that have a relay fee that is too low -- it doesn't check the sender's balance if it, say, ran a stx-transfer? internally based on the current state of the VRF.

Regarding fee estimation in the wallet, the only changes we'd need to do are:

Wallets could hit up both of these endpoints for SmartContract and ContractCall payloads, and could use payload length alone to estimate the fee for PoisonMicroblock and TokenTransfer payloads.

Even if we don't implement this fee strategy, we are going to need to do this anyway, since any fee strategy is going to need to take into account how much compute budget gets used to run each transaction.

Miner claims that there just aren't enough transactions to fill a block. In this case, K is set to the minimum fee rate. No other penalty applies.

Not quite -- not sure if you saw it in my comment above, but under-filled blocks get reduced (possibly 0) coinbases, which is a pretty stiff penalty. The paper isn't written too well on this point, but having talked with the authors about this, miners always pay a fill penalty if the block isn't full, full stop. The act of declaring that there aren't enough transactions to fill the block is the act of paying a fill penalty and setting the fee rate to be the relay fee -- this is the cost of getting the block included into the blockchain at all. Miners declare that there aren't enough transactions by way of taking the fill penalty and using the minimum fee rate. Miners can't just produce a block and tag it with a bit to say "whelp, there aren't enough transactions in the mempool, so pay me the minimum fee rate but give me all of the coinbase."

Recall that there is also the protocol constant F -- a block must be at least F% full if the miner is to receive 100% of the coinbase. If a budget amount M is missing from the block to make it under-filled -- i.e. a block is (F - M)% full for some 0 <= M <= F -- then the miner receives (F - M) / F of the coinbase. If the miner must produce a block that is less than F% full due to a lack of transactions, then they set their coinbase payout appropriately to signal this (if they don't do this, then the block is invalid), and they set the fee rate to be the smallest allowed value. The reason for this is to ensure that even if a miner can pack a block with its own transactions for free, the revenue is the same as it would have been if the miner just took this fill penalty.

Also, recall that transactions that pay lower than the Kth-highest fee in a block that is at least F% full are free -- their senders pay no fee at all. If b = 1, then this means that there is no world in which miners are obliged produce under-filled blocks -- they can just produce free transactions to themselves and/or use the extra space for their own purposes.

The thrust of the argument for having b > 1 is to impose a price on artificially filling blocks. In expectation, no matter what b is, a miner with mining power fraction p out of total mining power P would lose 1 - p/P percent of the fees spent on block-stuffing (since they'd only win back p/P of the fees). Having b > 1 makes it so that there can be a better payout to miners to take the fill penalty instead of stuffing their blocks (if b = 1, the payout is the same either way).

An important caveat about b > 1 that I don't think the paper does a good job discussing is that setting b > 1 is most useful when there are few transactions available to mine -- having b > 1 can make it more profitable to mine low-fee transactions than it is to ignore them and just stuff one's blocks with free fake transactions. If there are lots of transactions available to mine -- i.e. if the set of available transactions to mine exceeds F% of the filled block -- then the miner's payout is maximized by mining them all even when b = 1. This makes me think that we can get away with b = 1.

I think my feelings are that we should not attempt to perform auction-based fee pricing at launch. It's solving for a problem (over priced fees) that the Stacks chain is very unlikely to have for the first year or so of its life, and if anything, complicates the incentives for miners to participate early on in the lifetime of the blockchain, which is when miner participation is perhaps most important.

It's interesting that you say this, because the justification for the paper is that having a Kth-highest pricing mechanism ought to reduce the cognitive load on users paying fees, because it would maximize their payout when they bid honestly. I can understand the desire to not share transaction fees, and per the above I don't think it would hurt us in the long run to set b = 1.

kantai commented 3 years ago

The miner code is already written to handle transactions aborting at runtime, so I'm not sure what the problem there is? The miner can still just try to include all minable transactions in the mempool (i.e. in fee-rate order and nonce order) and omit the ones that abort due to having an insufficient balance (just as how it would omit transactions that, say, failed post-condition checks). Also, the mempool today only rejects transactions that have a relay fee that is too low -- it doesn't check the sender's balance if it, say, ran a stx-transfer? internally based on the current state of the VRF.

The mempool admission policy currently checks whether or not the fee payer has enough balance to pay the advertised fee. Yes, we could require that the payer has at least the relay fee, and then that all transactions pay max( K * execution_cost, relay_fee), and I think that would address this. I think transactions broadcasting max fee vs. max fee rate is sufficiently a wash, that either way this is settled would be fine with me. I could be convinced if tooling and wallet implementations have already implemented one way or the other.

Not quite -- not sure if you saw it in my comment above, but under-filled blocks get reduced (possibly 0) coinbases, which is a pretty stiff penalty. The paper isn't written too well on this point, but having talked with the authors about this, miners always pay a fill penalty if the block isn't full, full stop. The act of declaring that there aren't enough transactions to fill the block is the act of paying a fill penalty and setting the fee rate to be the relay fee -- this is the cost of getting the block included into the blockchain at all. Miners declare that there aren't enough transactions by way of taking the fill penalty and using the minimum fee rate. Miners can't just produce a block and tag it with a bit to say "whelp, there aren't enough transactions in the mempool, so pay me the minimum fee rate but give me all of the coinbase."

Right -- I saw that in your comment above, but that is markedly different from what is proposed in the paper:

A  block  is  defined  to  be  filled  if  it  contains K transactions  or if  the  miner  pays  a fill  
penalty. The  necessary  fill  level, K,  is a parameter which can be chosen to be some fraction, 
say 80%, of the capacity of a block.  The fill penalty is defined to be the difference between K and 
the number of transactions in the block times the fee paid by each transaction.  A miner can also 
avoid paying the  fill  penalty  by  declaring  that  there  were  not  enough transactions in the mempool 
to fill the block, in which case each user is charged the minimum allowable fee for a transaction to be 
included in the mempool.

So if a block does not get to fill level F, then either every transaction in the block just pays the relay rate or the miner pays a fee which is (F-f) * r where f is the actual fill level of the block and r is the fee paid by every transaction in the block. I cannot see that to mean that this value could ever be negative.

The penalty scheme that you described above, though, is different and would have some potentially very negative consequences during periods of low activity. I would be much more worried about that than too-high transaction fees. For example, if there were ~100 transactions per block during the first few months (which is ~50x the current activity level of Stacks 1.0), that's likely a block fill of 5% (assuming 2000 txs/block). Setting F even to 10% (which is way too low for this scheme to be effective at managing transaction fees) would result in a reduction in coinbase rewards of 50%. With a larger block limit, and likely a higher F so that this scheme is actually effective at providing an efficient auction, the effects on rewards would be even larger.

jcnelson commented 3 years ago

So if a block does not get to fill level F, then either every transaction in the block just pays the relay rate or the miner pays a fee which is (F-f) * r where f is the actual fill level of the block and r is the fee paid by every transaction in the block. I cannot see that to mean that this value could ever be negative.

Right -- blocks would never cost the miner any STX to produce. It's just that a block can pay out closer to 0 (less than the coinbase even) if the miner does less work. The penalty, if assessed, is never more than the block's coinbase, so the penalty is assessed by docking the coinbase.

The penalty scheme that you described above, though, is different and would have some potentially very negative consequences during periods of low activity. I would be much more worried about that than too-high transaction fees. For example, if there were ~100 transactions per block during the first few months (which is ~50x the current activity level of Stacks 1.0), that's likely a block fill of 5% (assuming 2000 txs/block). Setting F even to 10% (which is way too low for this scheme to be effective at managing transaction fees) would result in a reduction in coinbase rewards of 50%. With a larger block limit, and likely a higher F so that this scheme is actually effective at providing an efficient auction, the effects on rewards would be even larger.

Okay, I'm convinced that in our case, a block must have a minimum block reward, and it must be at least as big as the coinbase.
This is a unique property to Stacks, because unlike PoW currencies, there is a floor to how expensive it is to produce a block, and that floor is not something that the system can control. So, we need to adapt to it -- i.e. by making it so that unclaimed coinbases accumulate. But, this precludes any sort of fill penalty system that would reduce a block's coinbase.

I'm also convinced that we must keep b = 1 -- no anchored transaction fee-sharing should take place. We don't want free-rider miners, and it's difficult to explain to would-be miners that they won't earn all of the transaction fees they mine.

Given these constraints, is there still a way we can implement transaction fees as a second-price auction? Also, my main concern here isn't that we implement a second-price auction per se, but that our fee system ensures users can bid as close to the true valuation as possible on the next block's compute capacity (so they don't find themselves either overpaying a fee, or having a transaction stuck in the mempool forever). Maybe in our case it's not necessary to do this, because streamed transactions give users and miners a way to measure the true price for computing in real-time?

kantai commented 3 years ago

Given these constraints, is there still a way we can implement transaction fees as a second-price auction?

I'm sure that there is, but I believe that these constraints would make it pretty close to a greenfield project.

Also, my main concern here isn't that we implement a second-price auction per se, but that our fee system ensures users can bid as close to the true valuation as possible on the next block's compute capacity (so they don't find themselves either overpaying a fee, or having a transaction stuck in the mempool forever).

Agreed. I think that the big property that second-price auctions provide is that the excess value from user time-sensitivity is refunded to the user rather than captured by miners. This is very nice from a user perspective, and in a perfect world, something that we'd be able to provide.

Maybe in our case it's not necessary to do this, because streamed transactions give users and miners a way to measure the true price for computing in real-time?

Yes, I think this may be true -- I think that streamed transactions do help this problem, because they give a real-time price for transactions that could be included immediately. I'm not convinced that they solve the fee market problem entirely, but I do think they help.

Because of that, I think our best course of action on the fee markets is to continue to price transactions using the fee/fee rate broadcasted by the transaction itself. Miners collect the full share of transactions they include, except for streamed transactions, which have a 40/60 split. We should actively research fee markets after launch, though, so that if there are network upgrades down the line, fee payouts can be revisited.

jcnelson commented 3 years ago

Because of that, I think our best course of action on the fee markets is to continue to price transactions using the fee/fee rate broadcasted by the transaction itself. Miners collect the full share of transactions they include, except for streamed transactions, which have a 40/60 split. We should actively research fee markets after launch, though, so that if there are network upgrades down the line, fee payouts can be revisited.

Given that solving the second-price auction problem in the context of Stacks is likely to be a greenfield problem, I'm fine with this outcome. For now, let's go ahead and treat the fee_rate field as the total fee paid by the transaction, since I think this is what the tooling currently does (if so, then I think we should also re-factor the code to change this field name to just fee).

We can revisit implementing a second-price system for Stacks 2.1. In addition, we can consider ways to implement a second-price system as a soft-fork (naively, miners could just refund users their overpayment).

kantai commented 3 years ago

Marking this as stacks-future to indicate that we're not planning to implement this as part of the next mainnet release.

stale[bot] commented 3 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

stale[bot] commented 3 years ago

This issue has been automatically closed. Please reopen if needed.