Further improvement on tiered fees

I really like this CIP idea: Network traffic and tiered pricing - IOHK Blog
I have an idea to improve it even further.
Another tier could be added, which would not be a fixed-fee like the others, but a user-selected custom fee, with a frontrunning fee market like Bitcoin has, with no maximum limit on the fee price.
It would add the optional benefit for rich people to reward Cardano handsomely to get their transaction settled no matter what the congestion.
Or maybe this fee-market tier could be a simpler a better replacement for the instant tier in the article?
But because the other three tiers would still be present in parallel, people who dislike frontrunning or cannot affort it could simply use these three and stay away from the proposed fourth fee-market one.
It would add even more options for the users, would be a win-win for everyone.

This would be a great improvement to the current fee system.
You can choose 3 fee values, or choose your won fee with this proposal.
Not being forced to pay only a one same for all fee.
Each Tier has its own mempool and it’s own space allocated in Blocks.
For example a slot leader is only allowed to fill 1MB max from each tier. So the maximum blocksize would be 4MB, with each mempool beaing processed fairly in paralel.
Tiers cannot be front runned by another one.
4MB blocks would only happen if all the tiers are congested.
If only one tier congested the blocks would only fill 1MB of it, even if the other 3MB is left unfilled.
The user has a chose in tx building, which tier to use.


First choice: Fair

-Deterministic fee = BaseFee0 + LovelacesPerByte0 * TxSize
-Base 0 and Space1 are constants just like the current fee computation
-But lower multiplier constants than the current ones
-So it will be a cheaper fee, but its mempool will get congested often
-The user is told how much the fee is (doesn’t change in time unless vote)
-The user is also told how many blocks it will take to settle (does change in time with congestion)
-It can settle faster if the tx in front get replayed-by-fee into higher tiers. But cannot settle slower.
-No frontrunners can delay their queue time


Second choice: Balanced

-Deterministic fee = BaseFee1 + LovelacesPerByte1 * TxSize
-It might be the same values as we have now, that is the 0.17 ADA we are used to
-It will get congested less often than Fair
-The user is told how much the fee is (doesn’t change in time unless vote)
-The user is also told how many blocks it will take to settle (does change in time with congestion)
-It can settle faster if the tx in front get replayed-by-fee into higher tiers. But cannot settle slower.
-No frontrunners can delay their queue time
-And these two mempools also can’t frontrun each other, each has their own separate block allocation
-But a user could replay-by-fee from Fair,


Third choice: Immediate

-A deterministic fee, but changes in time to meet demand, similarly to bitoin’s diffulty adjustments
-Deterministic Fee = BaseFee2 + LovelacesPerByte2 * TxSize
-BaseFee2 and LovelacesPerByte2 are only constant within adjustment widnows.
-They get auto-adjusted every epoch (or every block?), similar to bit
oin difficulty adjustments.
-They increases with congestion. If the previous blocks are filled above 50%.
-They decrease if there isn’t congestion. If the previous blocks are filled below 50%.
-Or it might adjust after every block, based on the previous block filled size
-A good solution to adjusting the fee to demand
-Without the need to change the constants with Voltaire voting all the time
-Reistant to congestion, but still might if demand changes too quickly
-Reading the blogpost again, I noticed they also talk about it for the Fair tier
-So I guess all three tiers could have the constants auto-adjusted after X blocks.
-Each tier would be auto-adjusted towards its own promised settlement time.
-The user is told how much the fee is (does change automatically in time with demand)
-It can settle faster if the tx in front get replayed-by-fee into higher tiers. But cannot settle slower.
-Still no frontrunners, the fee doesnt change until next adjustment
-The user could replay-by-fee from Fair or Balanced


(Proposed) Fourth choice: Custom

-Non-deterministic fee = LovelacesPerByte3 * TxSize (LovelacesPerByte 3 not a constant)
-So just like the bitcoin system, there is frontrunning allowed here
-Basically the users freely choose their own adjustments to fee sizes in real time.
-The user is not told how much the fee is, the user chooses their own LovelacesPerByte3
-The user is also told how many blocks it is estimated to settle
-Can adjust to demand quicker than Immediate tier
-But because of frontrunning available, the settlement time can not only get faster, but also slower
-Because the queue in front of you can both grow or shrink with new txs, or replay-by-fees
-To the point than in endless congestion it could never settle until replayed-by-fee with a higher fee
-Can replay-by-fee from all other tiers, if its higher that their fee
-With this tier, the user chooses their fee size instead of settlement time
-The user can choose one or the other as they please
-But cannot choose both fee size and settlement time for the same tx

At first reading it does seem like the fourth (“custom”) tier could make the transaction fee structure more robust overall & maybe allow users & dApps to resolve some cases of congestion or contention resulting from the regular fee tiers.

I would hope to see some more people contributing here on the forum and think it would eventually make a valid candidate CIP. Yet the usual thing to do would be to submit it relative to IOG’s official CIP documentation of its own tiered fee structure previously documented informally in their blog article. This may not come for a long time, but if I see it coming along on GitHub I’ll link it here.

In any case this would be a significant protocol change whether your “custom tier” were added or not. So all things considered I would hope to keep this thread alive in the year to come & try to get as much input as you can from the Developer community (maybe chatting about it on the IOG Discord), especially from devs who might be interested in using it for their dApps. :face_with_monocle:

I don’t think this solution would be any practical at all, because it potentially wastes a lot of block space if those upper tiers are not - or under - filled.

This “wasted potential block space” is basically the cost for frontrunning protection.
You absolutely dont want for the higher expensive tiers to eat all 4MB allocated for all tier, with the minter claiming there was no transaction traffic on the lower ones. Allowing this would bring the frontruning problem thatt Cardano is already solving with the deterministic fee, And so it would also defeat the same purpose of the 4 proposed tiers. We want the chain to be fair - process the transactions on its fixed tiers without anyone frontrunning with a higher fee.
I think it can’t even be allowed in opposite direction, imagine someone minting a block with 4MB of the cheapest tier, claiming there was congestion, and no traffic on expensive tiers. Then it be unfair if there actually were people trying to transact those expensive immediate transactions! So both ways, if you allow other tiers to take a cut from the blockspace of others, it would immediately destroy the fairness in Cardano’s fee structure. That wasted potential space is really a cost for frontrunning protection to keep it fair.

1 Like

I deleted the codes because they were not designed well, and the adjustments would not work properly in real world, I am going to report the specifications, but without the problematic parameter auto-adjustment code.
edit:
So below is the pure specification draft, with Haskell implementation for tx validation.
Note than I am a Haskell beginner, so my Haskell code is only very basic level.
Also I don’t know to translate the procedural block filling code
And a code for auto-adjustments is completely missing, too hard for me.

1 Like

Abstract:

Improvement for Scalability and Sustainability in the fee calculation. Expanding the fee choices for different users with different demands for fee size and settlement time. Automatic adjustions for fees with changing demand and ADA price.

Motivation:

The current fee structure of Cardano accounts for both fairness and storage.
Fee = a + b Ă— size
a = Ada Per Tx
b = Ada Per TxByte
size = Tx Size In Bytes
a = 0.155381 ADA
b = 0.000043946 ADA/Byte
Fairness - users can know a deterministic fee they pay and maximum settlement time)
Storage - Minimum fees for storage of the tx on chain
However this structure is not ready to scale and sustain a growing demand for transaction processing, and don’t account for the value of ADA, fees could get prohibitively expnsive if it goes up.
The fees need a mechanism to adjust their a and b parameters to these two changing conditions.
Additionally, users should get a choice to either pay less for longer settlements times, or more for faster settlements times, which should still remain guaranteed. Also the users need another choice to be able to set their own fee with no guarantees on settlement time, if none of the predetermined are acceptable for them.

Specification:

Inspired by this blogpost, below is a possible implementation of block-filling that validates fees into 4 partitions:
Custom[1] = Any fee can fit here, so the implementation skims the top most expensive fees
Fair[2] = Only Fair fees can fit here, so the implementation tries to fill this first
Balanced[3] = Only Balanced fees can fit here, so the implementation tries to fill this first
Immediate[4] = Only Immediate fees can fit here, so the implementation tries to fill this first

A procedural code would first try to fill Fair+Balanced+Immediate, then sort what’s left by most expensive and skim the top most expensive into Custom.
In other words, it first processes the 3 Cardano-style feed transactions, and then adds on top Bitcoin-style fee-market transactions.

Here is the logic in C:

float a = 0.000303478515625 ADA
float b = 8.583203125e-8 ADA
int TN = 4

struct IO{ Tx[] I,O; IO(Tx[] _I, Tx[] _O){ I = _I; O = _O; } }

int TxSize(Tx tx) { return tx.GetByteSize(); }
int TxFee(Tx tx) { return tx.GetFee(); }
float TxFeePerByte(Tx tx) { return (float)tx.GetFee() / tx.GetByteSize(); }
bool TxValid(Tx tx) { return tx.HasValidSignatures() && tx.HasValidTransaction(); }
int[] TierM = int[5]{1,1,8,8,8};
int TierFee(int Tier, int Size) { return (a + b * Size) * TierM[Tier]; }
bool TierValid(int Tier, Tx tx) { 
 return Tier <= 1 
 ? TierFee(1, TxSize(tx)) <= TxFee(tx) 
 : TierFee(Tier, TxSize(tx)) == TxFee(tx);
}

Int CanAddTx(Tx tx, int[]& Unfilled) {
 int tier = Unfilled.Length();
 while(1 <= --tier)
  if(TxSize(tx) <= Unfilled[tier] && TierValid(tier, tx)){
   Unfilled[tier] -= TxSize(tx);
   return tier;
  }
 return 0;
}
IO ValidTierTxs(int MinTier, IO Txs, int[] Unfilled){
 IO R;
 for(Tx& tx : Txs.I) 
  (CanAddTx(tx, Unfilled) >= MinTier ? R.O : R.I).Add(tx);
 return R;
}
IO SortInputTxsByFee(IO Txs) { return IO(SortByFeePerByte(Txs.I),Txs.O); }
Tx[] SortByFeePerByte(Tx[] S){
 Tx c; // Simple bubble sort
 for(int a=S.Length-1; --a <= 0;)
  for(int b=S.Length; --b > a;)
   if(TxFeePerByte(S[a]) < TxFeePerByte(S[b])) {
    c = S[a]; S[a] = S[b]; S[b] = c;
   }
}
Tx[] GetValidTxs(Tx[] I){
 Tx[] O; for(Tx& tx : I) if(TxValid(tx)) O.Add(tx);
 return O;
}
bool AreAllTxsValid(Tx[] Block){
 for(Tx& tx : Block) if(!TxValid(tx)) return false;
 return true;
}

-- USAGE EXPRESSIONS INSERTS --

bool IsBlockValid(Tx[] Block){
 int[] BlockSize = int[5]{0, 32000, 256000, 128000, 64000};
 return AreAllTxsValid(Block) 
  && ValidTierTxs(1, ValidTierTxs(2,IO(Mempool,Tx[] O),BlockSize),BlockSize).I.IsEmpty();
}
void MintIntoBlockFile(Tx[]& Mempool){
 int[] BlockSize = int[5]{0, 32000, 256000, 128000, 64000};
 Mempool = GetValidTxs(Mempool); // Filter out invalid Txs
 IO Block = IO(Mempool,Tx[] O); // Create Output structure
 Block = ValidTierTxs(2, Block, BlockSize); // Insert as many fixed tiered txs as allowed
 Block = SortInputTxsByFee(Block); // Sort the remaining by fee
 Block = ValidTierTxs(1, Block, BlockSize); // Insert as many most expensive fees as allowed
 MintBlockFile(Block.O); // Block.O are txs in Mempool that made it into block, make a block from them
 Mempool.Remove(Block.O); // Remove those from mempool as already spent;
}

Here is the same logic, which I tried to transtale into Haskell (I am just a Haskell beginner, so no idea how good this transalation is)

a = 0.000303478515625 ADA
b = 8.583203125e-8 ADA

TN :: void -> Int
-- TN = Number of fee tiers, might expand in future by vote to add more layers of fixed tiers.
TN = 4 -- 1=Custom, 2=Fair, 3=Balanced, 4=Immediate

TxSize :: Tx -> Int
-- TxSize Tx = Size of the Tx

TxFee :: Tx -> Int
-- TxFee Tx = Fee of the Tx

TxFeePerByte :: Tx -> Float
TxFeePerByte Tx = (TxFee Tx) / (TxSize Tx)

TxValid :: Tx -> Bool
-- TxValid Tx = Are the transaction data and signatures valid? Doesn't validate by fee and blocksize.

TierM :: Int -> Float
--TierM Tier = Multiplier for allowed fee for each tier.
TierM 1 = 1
-- Custom fee cannot be lower than Minimum Fee = a+b*size
TierM 2 > 1
-- Fair fee cannot be lower than Minimum Fee = a+b*size
-- autoadjust towards TargetFairSettlementTime/Congestion
TierM 3 > TierM 2
-- Balanced fee cannot be lower than Fair
-- autoadjust towards TargetBalancedSettlementTime/Congestion
TierM 4 > TierM 3
-- Immediate fee cannot be lower than Balanced
-- autoadjust towards TargetImeddiateSettlementTime/Congestion
...TierM TN > TierM (TN-1)
-- expandable by TN
-- Auto-adjustments must keep these inequalities, so Fair fee couldn't become more expensive than Balanced etc.

TierFee :: Int Int -> Int
-- TierFee Tier Size = Fee that is accepted to this Tier, for a Tx with (TxSize Tx = Size)
TierFee Tier Size = (a + b * Size) * TierM Tier

TierValid :: Int Tx -> Bool
-- TierValid Tier Tx = Is the Tx allowed into Tier by Fee?
TierValid 1 Tx = TierFee 1 (TxSize Tx) <= TxFee Tx
-- Custom tier
-- fee must be greater or equal to (a + b*size)
TierValid Tier Tx = TierFee Tier (TxSize Tx) == TxFee Tx
-- Fair/Balanced/Immediate tiers
-- fee must be equal to [(a + b*size) * TierM Tier]

BlockSize :: void -> [Int]
BlockSize = [32000, 256000,128000, 64000]
-- voteable constants for allowed block bytesize per tier - for all 4 tiers.
-- Example: BlockSize = [32000, 256000,128000, 64000] allows 32kB for Custom, 256kB for Fair, etc.

CanAddTx :: Tx [Int] -> Int
-- CanAddTx Tx Unfilled[1..TN] -> Tier into which Tx can be added (matches fee AND fits into blocksize)
CanAddTx Tx Unfilled
 | null Unflilled = 0 -- failed to fit to every Tier, 0 is failure
 | TxSize Tx <= last Unfilled && TierValid (length Unfilled) Tx = (length Unfilled)
 | otherwise = CanAddTx Tx (init Unfilled) -- failed to fit into this tier, try a lower one by recursion

Concat :: ([Tx],[Tx]) ([Tx],[Tx]) -> ([Tx],[Tx]) 
Concat ([InputTx],[OutputTx]) ([InputTxs],[OutputTxs]) = ([InputTx]++[OutputTx],[OTx]++[OutputTxs]) 

SubBytes :: [Int] Int Int -> [Int]
-- SubBytes Unfilled Tier (TxSize Tx) = Unfilled with Size subtracted from Tierth List Slot.
-- Example: SubBytes [5,6,7] 2 4 = [5,2,7]
-- Is used for counting fillled tx bytes into allowed blocksizes
SubBytes Unfilled Tier Size
 | null Unfilled || Tier <= 0 = Unfilled
 | Tier == 1 = (head Unfilled - Size) ++ (tail Unfilled)
 | otherwise = (head Unfilled) ++ (SubBytes (tail Unfilled) (Tier - 1) Size)

ValidTierTxs :: ([Tx],[Tx]) [Int] Int -> ([Tx],[Tx])
ValidTierTxs MinTier (InputTxs, OutputTxs) Unfilled 
 | null InputTxs = ([],OutputTxs)
 | otherwise = ConcatTierTxs (CanAddTx (head InputTxs) Unfilled) MinTier (head InputTxs) ((tail InputTxs),OutputTxs) Unfilled

ConcatTierTxs :: Int Int Tx [Tx] [int]
ConcatTierTxs MinTier Tier HeadInput TailInput Unfilled
 | Tier >= MinTier = Concat ([],HeadInput) (ValidTierTxs MinTier TailInput (SubBytes Unfilled Tier (TxSize HeadInput)))
 | otherwise = Concat (HeadInput,[]) (ValidTierTxs MinTier TailInput Unfilled)

SortInputTxsByFee :: ([Tx],[Tx]) -> ([Tx],[Tx])
SortInputTxsByFee (Inputxs, OutputTxs) = (SortByFeePerByte Inputxs, OutputTxs)
-- Retains the OutputTxs as they are
-- InputTxs gets sorted by their TxFeePerByte from higherst to lowest

SortByFeePerByte :: [Tx] -> [Tx]
-- TODO implement

ProcessTiers :: [Tx] -> ([Tx],[Tx])
ProcessTiers InputTxs = (ValidTierTxs 1 (SortInputTxsByFee (ValidTierTxs 2 (InputTxs,[]) BlockSize)) BlockSize)

GetValidTxs :: [Tx] -> [Tx]
-- Returns the same list of only valid transactions 
GetValidTxs  InputTxs 
 | null InputTxs = []
 | TxValid (head InputTxs) = (head InputTxs) ++ (GetValidTxs (tail InputTxs))
 | otherwise = GetValidTxs (tail InputTxs)

AreAllTxsValid :: [Tx] -> Bool
AreAllTxsValid InputTxs
 | null InputTxs = true
 | TxValid (head InputTxs) = AreAllTxsValid (tail InputTxs)
 | otherwise = false;

NoInputPending :: ([Tx],[Tx]) -> Bool
NoInputPending (InputTxs,OutputTxs) = null InputTxs

-- USAGE EXPRESSIONS INSERTS --

IsBlockValid :: [Tx] -> Bool
-- Block is valid when all contained tx are valid, and if it can fit inside allowed blocksizes by fee sortition --if processed and no input pending, then all tx fitted in)
IsBlockValid Block = AreAllTxsValid Block && NoInputPending (ProcessTiers Block)

MintIntoBlockFile :: ([Tx],[Tx]) -> ([Tx],[Tx])
-- MintIntoBlockFile (InputTxs,OutputTxs) = (InputTxs,[]) -- Also writes OutputTxs into block file as side-effect

MakeBlock :: [Tx] -> ([Tx],[Tx])
MakeBlock Mempool =  (ProcessTiers (GetValidTxs Mempool))

-- USAGE EXPRESSIONS STANDALONE --

IsBlockValid BlockToValidate
-- Example of Validating blocks, we read all Tx in block, process by Tiers...
-- and if there is any InputTx remaining unprocessed, then reject block for containing excess/invalid Txs.

MintIntoBlockFile MakeBlock
-- Example of Picking best transaction fees in mempool allowed by this tiered system, to mint a next block with them 

Rationale:

TN = 4
– inspired by the blogpost by IOG, Fair, Balanced, Immediate, but added Custom, and more could be added later

a = 0.000303478515625 ADA
b = 8.583203125e-8 ADA
– 512x smaller than curent a and b
– it will be the lowest possible fee structure
– other tiers multiplying upwards to higher values.

TierM 1 = 1, TierM 2 = 8, TierM 3 = 64, TierM 4 = 512
– start with each fixed tier being 8x more expensive than previous
– gotta start somewhere, it will then auto-adjust over time to optimal values.
– Minimum Custom would be 8x cheaper than Fair
– Fair would be 8x cheaper than Balanced
– Balanced would be 8x cheaper than Immediate

Backwards compatibility:

Proposal would not change the structure of data in any way, previous blocks can be revalidated as they are.
This proposal would significantly lower the “a” and “b” fee structure coefficients.
That would make old nodes reject the new blocks because they didn’t allow for custom fees.
The new nodes would accept the old blocks and assume they were all Custom in those eras and that they fit the blocksize limits of those eras. .

Path to Active:

Auto adjusting TierM 2, TierM 3, TierM 4:
– A difficult problem.
– Look at the congestion of each tier.
– And auto-adjust them towards target settlement times.

1 Like

The proposed design could be implemented even with the auto-adjustments still missing, afterall the current system doesn’ty adjust itself either, the proposed system would set up a modular and expansable foundation for multiple tiers with multiple rules. Later forks could then add auto-adjustment mechanics to the existing tiers as well as add entirely new tiers with new rules how to validate them. The first Custom tier can continue to be the final fallback “otherwise” tier, where every fee value is allowed, with no rules.
(except the absolute minimum a+b*size fee that is enforced even in the custom, but only as a minimum, to prevent spamming the storage for no cost).

I’ve got an idea, maybe we dont need to even implement any autoadjustments, if we just cover th entire logarithmic range with fixed tiers:

Tier 1(Custom): Fee >= a + b * size;
Tier 2: Fee == a + b * size
Tier 3: Fee == a + b * size * 10
Tier 4: Fee == a + b * size * 100
Tier 5: Fee == a + b * size * 1000
Tier 6: Fee == a + b * size * 10000
Tier 7: Fee == a + b * size * 10^5
Tier 8: Fee == a + b * size * 10^6
… all the way to fees that would even exceed the maximum supply of ADA, it would be allowed, it would technically have allocated extra blockspace for those, but no transaction could ever fit there.

Then we don’t need autoadjustments as long as the jump between two tier is not too extreme.
Everything will be covered forever. If the demand shifts, and the blockchain would then operate better with all tiers 10x more or less expensive? It already is good to go, people will just shift tiers.
And in such a case, even tha validation algoriths could get much simpler, there would basically be just 2 tiers, one custom, and one logarithmically stepped, except the stepped one would have an allowed blockspace for every step. Of course most of the tiers would be empty, but we would alwas get the block just the right size for the demand to keep it stable and fair.

So if the a and b remained the same (it shouldn’t, it should later get voted down to be lower, but that can wait), the fee system would be like this:
You could pay 0.17 ADA per your simple transaction and enter the queue for Tier 2.
Or you could pay 1.7 ADA and get into the faster less congested Tier 3. Each tier would have spearate allowance in blockspace, so both would be proccesed at the same rate, but the expensive ones will of course be less congested because people simply like to pay as little as possible to meet their settlement time needs.
Or you could pay 17 ADA, to enter yet another even less congested mempool.
And so on.
Or you could pay anything higehr than 0.17 that doesnt match the pattern, and you would enter yet another custom mempool, that acts jusyt like the one in bitcoin, with frontrunning,
As long as voting keeps the a and b parameters low enough to allow everyone to use the chain, no further automatic adjustments would be needed. Also with such a pattern for the tiers, we would not even need custom selected blocksizes for each, let’s just give the same blocksize to every tier in the pattern, because it can shift anyway, maybe only the custom tier could have a different allowed blocksize.

Here is the new procedural code for infinite tiers, stepping with base 4 instead of 10:

// Voteable constants
float a = 0.00155381;
float b = 0.00000043946;
int BlockSizeCustom = 32000;
int BlockSizeTiered = 32000;

// Mempool is a list of pending valid transactions sorted by age, [0] the oldest
List<Tx> MakeBlock(List<Tx>& Mempool) {

 List<Tx> AO; // Allowed Output = Allowed transactions
 List<Tx> PC; // Pending Custom = Custom transactions (doesn't match any tier AND is at least minimum: fee >= a+b*size)
 List<int> U; // Unfilled allowed Block Partition Bytes for each tier
 int Unfilled = BlockSizeCustom; // initialize block space allowance for custom tier

 for(Tx& tx : Txs) 
 {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size; // i = tier, e = 4^i = tiered b multiplier, f = baseless fee
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) 
   e *= 4; // find tier
  while(U.Length <= i) 
   U.Add(BlockSizeTiered); // initialize block space allowance for tiers up to this one
  if(ft * e == f && 0 <= U[e] - s) { // fee matches the found tier exactly and the transaction size still fits into allowed blockspace
   U[e] -= s; // Fill the allowed blockspace with the transaction size
   AO.Add(tx); // Allow the transaction into the block
  }
  else if(ft <= f) // Doesnt match exactly any tier, but still above minimum - pending custom
   PC.Add(tx);
 }

 // Selection Sort the Pending Custom list to add as many maximum fee transactions as allowed into allowed Custom fee blockspace 
 int x, max, pending = PC.Length;
 while(0 <= --pending) {
  max = sort = pending;
  while(0 <= --x)
   if(TxFeePerByte(PC[sort]) > TxFeePerByte(PC[max]))
    max = sort;
  if(0 <= (Unfilled -= PC[max]))
   AO.Add(PC[max]);
  PC[max] = PC[pending];
 }

 Mempool.Remove(AO); // Remove the allowed transactions from the mempool (if we want to start making another block)
 return AO; // Return list of allowed transactions into the block
}

bool IsValidBlock(Tx[] Block) {

 List<int> U; // Unfilled allowed Block Partition Bytes for each tier
 int Unfilled = BlockSizeCustom; // initialize block space allowance for custom tier

 for(Tx& tx : Block) 
 {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size;
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) 
   e *= 4; 
  while(U.Length <= i) 
   U.Add(BlockSizeTiered); 
  if(ft * e == f && 0 <= U[e] - s) 
    U[e] -= s;
  else if(ft > f || 0 > (Unfilled -= s))
   return false; // Some transaction didn't pay minimum fee, or some tier was overfilled!
 }
 return true; // all transactions could be allowed into a block by our rules, it's a valid block
}

Here is the same code, but compressed (no comments, less lines):

float a = 0.00155381;
float b = 0.00000043946;
int BlockSizeCustom = 32000;
int BlockSizeTiered = 32000;

List<Tx> MakeBlock(List<Tx>& Mempool) {
 List<Tx> AO, PC;
 List<int> U; 
 int Unfilled = BlockSizeCustom;
 for(Tx& tx : Txs) {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size;
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) e *= 4;
  while(U.Length <= i) U.Add(BlockSizeTiered); 
  if(ft * e == f && 0 <= U[e] - s) { U[e] -= s; AO.Add(tx); }
  else if(ft <= f) PC.Add(tx);
 }
 int x, max, pending = PC.Length;
 while(0 <= --pending) {
  max = sort = pending;
  while(0 <= --x) if(TxFeePerByte(PC[sort]) > TxFeePerByte(PC[max])) max = sort;
  if(0 <= (Unfilled -= PC[max])) AO.Add(PC[max]);
  PC[max] = PC[pending];
 }
 Mempool.Remove(AO); 
 return AO; 
}

bool IsValidBlock(Tx[] Block) {
 List<int> U;
 int Unfilled = BlockSizeCustom; 
 for(Tx& tx : Block) {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size;
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) e *= 4; 
  while(U.Length <= i) U.Add(BlockSizeTiered); 
  if(ft * e == f && 0 <= U[e] - s) U[e] -= s;
  else if(ft > f || 0 > (Unfilled -= s)) return false;
 }
 return true;
}

So which tier would then be the Fair, Balanced or Custom if there are infinite like this?
Fair would be the Tier 2, the lowest one that match a + b*size exactly.
Immediate would be the lowest tier that is not congested.
Balanced would be the tier with measued congestion for user’s desired settlement time.
Custom would be tier 1, user is free to choose any fee that is above the fair one, and enters the frontrunning custom queue.

For best backwards compatibility - the new a and b parameters should be chosen to match exactly one of the fixed tier steps, in my example, I chose a and b to be 100x smaller than their current value, which would make all legacy transactions fit Tier 4 (and also custom on top of that). If the allowed blockspace would be at least half on the current maximum blocksize limit, then backwards compatibility would be achieved, also wallets that didn’t update yet and still prepare fees the old-fashioned way would still make valid transactions prioritized by age just like before.

Here is an image that depicts which transactions from mempool would be allowed into a block (picture simplified to absolute fees instead of fees per byte, and stepping base is 10 as in first idea):

The algorithm can also work without the custom fees, if those turn out problematic, the custom-less infinite tier version would look like this:

float a = 0.00155381;
float b = 0.00000043946;
int BlockSizeTiered = 32000;

List<Tx> MakeBlock(List<Tx>& Mempool) {
 List<Tx> AO;
 List<int> U; 
 for(Tx& tx : Txs) {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size;
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) e *= 4;
  while(U.Length <= i) U.Add(BlockSizeTiered); 
  if(ft * e == f && 0 <= U[e] - s) { U[e] -= s; AO.Add(tx); }
  else if(ft <= f) Mempool.Remove(tx);
 }
 Mempool.Remove(AO); 
 return AO; 
}

bool IsValidBlock(Tx[] Block) {
 List<int> U;
 for(Tx& tx : Block) {
  int i = 0, e = 1, f = tx.fee - a, s = tx.size;
  float ft = b * s;
  for(i = 0; ft * e < f; ++i) e *= 4; 
  while(U.Length <= i) U.Add(BlockSizeTiered); 
  if(ft * e == f && 0 <= U[e] - s) U[e] -= s;
  else return false;
 }
 return true;
}

This code would allow only the exact matches for all the tiers, no custom tier with frontrunning, though I think the custom tier addition is simple and makes it even better as it features an extra choice for the users.

I’m thinking about adversarial spam attack resistance.
That is a nasty thing that especially these tiered designs have to thoroughly think about.
So far, I can see there is a weakness in this system that th lower cheaper tiers are naturally very easy to maliciously attacks with spam congension. I think all the fee system in real world already have to account for that and accept the effects of that, but let’s see how it effects those different designs.

In the simple bitcoin custom fee only system. There obviously can be malicious low-fee spam to make the cheap transactions settlement times very long easily. In this system the rich obciously have to advantage of avoiding these spam attacks, in fact they could have the ability to spam the poor while frontrunning them with their own high feetransactions they can afford.

AFAIK this is the main reason why cardano has chosen its fixed fee system, to make it fair for everyone and avoid this inequality.

So I think I’ll need to rethink this tiered idea from this adversarial angle, because I think in this current proposed state, it is actually vulnerable to these kinds of nasty attacks.
I hope I’ll figure out some solution, because it seems that splitting the current system even into just 2 tuers could possilby make it vulnerable to this atack.Where the rich could spam the cheaper tiers, while executing some shenanigans on their priviledged higher tiers.

On the single tier system we have now, this attack can’t happen because if the chain is spammed, then it’s spammed for everyone, the chain will be rewarded by the attackers spending fees into the attack, but at least that spamm could not be used to gain some advantage for the rich using the non-congested expensive tiers…

Basically the problem is is, how can we differentiate and make it fair - so that people could send cheaper transactions with longer settlement times with lower fees, and differentiate those who actually do meaningul transactions like that from malicious spammers who abuse that low fee tier to spam it and to make the settlement times for those people even more miserable, while the rich people above are naturally protected with those high fee costs for such spam attacks on them. hmmm…

but maybe that the point of those tiers, this problem might not be avoidable, but you can manage it with these tiered allowances. so the lower tiers will be naturally congested probably with a lot of spam, but the chain protects itself frtom bloat by not allowing letting those masses though quickly, keep it congested, if someone with legit transaction wants to go there, then ok, its cheap but deal with with the spam congestion… you wanted it cheap so it will take a longer time, that was the promised balance anyway.