kip-0009.md

  KIP: 9
  Layer: Mempool, P2P, Consensus
  Title: Extended mass formula for mitigating state bloat
  Authors: Michael Sutton <[email protected]>
           Ori Newman <[email protected]>
           Shai Wyborski <[email protected]>
           Yonatan Sompolinsky
  Status: proposed, implemented in the rust codebase and activated in testnet 11 

We propose a mechanism for regulating the growth rate of the UTXO set in both organic and adversarial settings. Our proposal is fundamentally different than existing attempts to mitigate state bloat (e.g., statelessness or state rent, both requiring active user involvement), and only entails a simple change to the logic of how the mass of a transaction is computed. In this proposal, we specify the revised formula and its consequences and describe how ecosystem software such as wallets, pools, and exchanges should adapt to this change without affecting the quality of service. We provide an intuitive overview of the properties of the new mass formula and defer the formal treatment to a soon-to-be-published preprint.

Motivation

A few months ago, the Kaspa network faced a dust attack that exploited the high throughput to create many minuscule UTXOs, forever increasing the storage costs of full nodes. The attack was countered and eventually stopped by deploying a mempool patch [2]. The patch imposed a limitation on the number of transactions with more outputs than inputs that are allowed in each block; see [1] for a detailed account of the attack and its resolution. Since many standard transactions are of this form (most typically, a transaction with a single input, a destination output, and a change output), this resulted in noticeable UX and QoS inconveniences. This KIP aims to address the state bloat challenge more fundamentally, by introducing a transaction cost -- or mass -- function that inherently limits state bloat attacks. While the current state of the system is bearable (the patch increasing the delay of such transactions by a dozen seconds at worst), increased adoption will greatly exacerbate this effect, providing ample motivation to expedite the implementation of a sustainable solution.

Specification

The formal specification of the suggested changes is described below, followed by a detailed overview and analysis.

Extended mass formula

We refer to the quantity currently known as "mass" by the name compute_mass, and introduce a new quantity called the storage_mass. As the name suggests, the former regulates computational costs while the latter regulates storage costs. We redefine the total mass of a transaction as the maximum over both: $$\text{mass}(tx) = max\lbrace\text{compute mass}(tx) , \text{storage mass}(tx)\rbrace\text{.}$$

In the context of storage mass, a transaction is modeled as two collections of values: the input values $I$ and output values $O$. We use the notation $x^+ = \max\lbrace x,0 \rbrace$. The storage mass is defined as follows:

$$\text{storage mass}(tx) = C\cdot\left(\sum_{o \in O} \frac{1}{o} - \frac{|I|^2}{\sum_{v \in I} v}\right)^+\text{,}$$ where $C$ is a constant controlling the correlation of inverse KAS value to mass units.

A relaxed version of the mass formula treats inputs and outputs symmetrically: $$\text{storage mass}^*(tx) = C\cdot\left(\sum_{o \in O} \frac{1}{o} - \sum_{v \in I} \frac{1}{v}\right)^+\text{.}$$

We call this the relaxed formula. As shown in [3], storage_mass* can be used for transactions satisfying $|O|\le|I|\le 2$ or if $|O|=1$.

As mandatory in consensus systems, storage mass calculation must use only integers and cannot rely on floating-point arithmetics. This means that the constant $C$ must be computed within each fraction otherwise the loss of precision will render the calculation useless. The following compiles the overall pseudo-code for calculating the new extended mass formula:

def negative_mass(I, |O|):
    """
    Calculates the negative component of the storage mass formula. Note that there is no dependency on output
    values but only on their count. The code is designed to maximize precision and to avoid intermediate overflows.  
    In practice, all calculations should be saturating, i.e., clamped between u64::MIN and u64::MAX  
    """
    if |O| == 1 or |O| <= |I| <= 2:
        return sum(C/v for v in I)
    return |I|*(C/(sum(v for v in I)/|I|)) 

def storage_mass(I, O):
    N = negative_mass(I, |O|)
    P = sum(C/o for o in O)
    return max(P-N, 0)

def mass(tx):
    return max(storage_mass(I=tx.inputs, O=tx.outputs), compute_mass(tx)) 

Storage mass (unlike compute mass) cannot be computed from the standalone transaction structure, but requires knowing the exact input values, which are only available with full UTXO context (i.e., it requires a populated transaction).

Constants

We suggest setting $C=10^{12}$. Note that transaction input and output values are represented in dworks (also known as sompis), which are the smallest unit of KAS value (a single KAS is equal $10^{8}$ dworks).

P2P & Mining rules

The new mass formula can be implemented as a mempool policy rather than a consensus rule. This has the benefit of not requiring a fork to roll out, but the disadvantage of trusting the miners to follow this policy. Due to the urgency of the update, we suggest to initially roll it out as a P2P/mining rule, while also including it in the nearest upcoming hard-fork.

P2P rule A node receiving a $\text{tx}$ via RPC or P2P should validate the transaction and calculate its mass using the new formula. If the computed mass exceeds the standard mass (currently $100,000$ grams), $\text{tx}$ should be rejected from the mempool and not broadcasted to peers.

Mining The new mass should be used by the mempool transaction selection algorithm to calculate the $\text{fee}/\text{mass}$ ratio, and the overall block template mass should respect the block mass limit ($500,000$ grams).

Consensus (hard-fork)

Applying the proposal as a consensus change requires the following updates:

Transaction mass field A new explicit mass field should be added to the Transaction structure. This field is used as a commitment to the total mass consumed by the transaction (including the storage mass), until it can be verified in full UTXO context. To make the stated mass binding, the mass field must be hashed when computing the transaction hash. However, we suggest that the logic for computing a transaction ID should ignore this field, as this avoids unnecessary changes in ecosystem software (clients such as wallets frequently compute the ID locally). Note that wallets composing a transaction can leave the mass field empty, and let miners fill it for them during block template building.

Block validation rule The mass field of all transactions in a given block is summed and verified not to pass the block limit. Additionally, for each transaction $\text{tx}$, the expected compute_mass is calculated and verified to be equal or lower than the mass commitment $\text{tx.mass}$.

Transaction validation rule The full mass is only calculated during contextual transaction validation (that is, validation with full UTXO context of the containing block or a chain block merging it). If the computed mass does not match the committed mass, the transaction is considered invalid and is discarded. Like other transaction validation rules, blocks containing transactions committed to a wrong storage mass are considered disqualified from the selected-chain.

Wallets

Current wallet developers in the Kaspa ecosystem are familiar with the term “compounding”. When compute_mass of a transaction is larger than $M$ (where $M=100,000$ is the standard transaction mass limit), wallets compose a chain or a tree of transactions for iteratively compounding UTXOs until a final payment can be made with the desired, typically large, value. Similarly, with storage_mass introduced, wallets might encounter cases where the desired payment is extremely small and the initial storage_mass is larger than $M$. Below we specify a “fragmentation” process, which iteratively “unbalances” a pair of UTXOs until one of them is small enough to make the micropayment. Notably, this unbalancing process relies on the sensitivity of the relaxed formula to the distribution of input values.

Consider a user with a single UTXO holding $1$ KAS making a payment of $0.05$ KAS. For simplicity, assume the transaction fee is always $0.001$ KAS. The following chain of transactions performs the desired micropayment while not surpassing $M$ in any transaction:

       0.5       0.1      0.05
    /       \  /     \  / 
1.0                
    \       /  \     /  \ 
      0.449     0.898     0.947

In section Wallet algorithm we fully specify an unbalancing algorithm that minimizes the number of steps required to make the micropayment, and discuss the relation to existing wallet algorithms. In section Micropayments we provide alternative costless methods for supporting micropayments in the long-run.

Currently, the vast majority of Kaspa transactions have outputs larger than one KAS, for which storage_mass hardly ever surpass $M$. Hence, a simple but very short-term way for wallets to adapt to the new formula is to reject payments below $0.2$ KAS (roughly the value at which storage mass gets close to $M$). If the change value is very small, larger/more inputs should be used, or the fee can be increased to consume the change. Exceptions to the common usage are faucet-like services used to demonstrate or experiment with the system. We suggest adapting the fragmentation process so that the wallet backing such services will always have small enough UTXOs ready to make the next micropayment.

RPC API

Before the hard-fork is applied, all mining software must update their RPC client interface to a version that includes the new transaction mass field. Otherwise, blocks submitted via RPC will hash incorrectly and be deemed invalid.

Rationale

The following provides an overview of the design decisions made and the rationality behind them. Formal statements presented rely on the analysis in [3].

Transaction mass vs. fees

In Kaspa, the capacity of a block is given in a quantity called mass. The difference between mass and size is that different types of data are considered "heavier" or "denser", in the sense that they consume more mass per byte. For instance, signatures have a relatively high mass per byte compared with other data since verifying them is computationally intensive. For an exact specification of how compute_mass is currently calculated, see here.

Increasing the mass cost of storage-wasting transactions is an effective countermeasure for regulating state growth, as it allows us to control how much each block increases the state (to a limited but sufficient extent, as we will soon see). This approach could be considered an adaptable version of imposing high fees on wasteful transactions, with the following benefits:

1. It does not require an estimate of what constitutes a "high" fee. Instead, the fee is naturally monetized as the value of the blockspace consumed by the transaction.
2. It works in the absence of an active fee market. Even if there are no fees, the mass limits and bounded block rate regulate the storage increase.

Quadratic storage costs via local mass costs

Our overarching goal is to make the cost of wasting some amount of storage quadratic in the amount of the storage wasted. That is, taking up ten times more storage takes 100 times more mass, taking up 100 times more storage takes 10000 times more mass, etc.

As mentioned in the previous section, lower bounds on mass consumption can be seen as lower bounds on the time required to execute a series of transactions. Alternatively, one can argue that the budget locked within a segment of storage, adds additional cost to the currency owner, in the form of initial acquisition, unearned interest, etc. Thus, we sought for a formula where the accumulated mass required to waste some amount of storage decreases with the budget locked within it. If we use growth to denote the inflation in storage caused by the attack, the desired constraint is that the accumulated mass is proportional to $\text{growth}^2/\text{budget}$.

Designing a mass function providing such quadratic growth is challenging, due to two contrasting desires:

1. Local mass pricing: the mass of a transaction is defined locally and may not depend on other transactions.
2. Global cost: the cost should be quadratic in the state inflation caused, regardless of how the attacker structured his attack. An attacker can structure his attack in many ways, creating many transactions with intertwined dependencies between them, and the mass formula must ensure that even the cleverest of attacks will ultimately pay a quadratic price.

To illustrate the intricacy, consider attempting the above by setting the mass of a transaction with $I$ inputs and $O$ outputs to be proportional to $(O-I)^2$. While locally it achieves quadratic growth, a clever attacker can increase the size of the UTXO set by $N$ entries by creating $N$ transactions, each with one input and two outputs. The accumulated mass of the attack is linear in $N$ rather than quadratic. In fact, we prove in [3] that any attempt to compute mass based only on the amount of inputs and outputs or their total value (while ignoring how the values are distributed) will fail. The reason for this ultimately boils down to the following observation: the mass of a transaction with two outputs of value $V/2$ is the same as that of a transaction (with the same inputs) outputting two inputs of values $\varepsilon V$ and $(1-\varepsilon)V$ for an arbitrarily small $\varepsilon$, and this property can be abused to cheaply increase the storage.

Revisiting the mass formula

A more mathematical representation of the formula defined above can be given using the harmonic and arithmetic means ($H, A$ respectively): $$\text{storage mass}(tx) = C\left(\frac{|O|}{H(O)} - \frac{|I|}{A(I)}\right)^+$$

The idea behind this formula is that a transaction should be charged for the storage it requires and credited for the storage it frees. However, there is a principal difference between them: the storage charge should reflect how distributed the outputs are, while the credit should only reflect the number of consumed UTXOs and their total value. This way, transactions that do not increase the UTXO set much (or even decrease it) but create minuscule outputs are heavily charged, while transactions whose inputs and outputs are on the same order of magnitude will not pay a lot of mass, even if they do increase the UTXO set. This excludes the ability of a storage attack, since such an attack requires breaking large UTXOs into small UTXOs. This is why using the arithmetic mean to credit and the harmonic mean to charge makes sense: The arithmetic mean is the same for any two sets of values of the same size and sum, it completely "forgets" how the values are distributed. On the other hand, the harmonic mean is extremely sensitive to how values are distributed and becomes very small if the smallest value is very small (by definition, the harmonic sum of $N>1$ values, one of which is $v$, is smaller than $vN$).

In [3], we formalize this intuitive interpretation by proving that this definition of storage_mass satisfies the property that the total storage_mass required for executing a set of transactions is lower bounded by a quadratic function of the global state growth it caused. More formally, assume $G$ is a DAG of transactions containing an aggregate value of $\text{budget}(G)$, and which increases the UTXO set by $\text{growth}(G)$ entries. Then, $$\sum_{\text{tx}\in G}\text{storage mass}\left(tx\right)\ge C\cdot\frac{\text{growth}^2(G)}{\text{budget}}\text{.}$$

Below we provide concrete illustrations of the consequences of this bound.

Security analysis and growth regulation

In this section, we consider the consequences of applying the storage mass policy, using $C=10^{12}$. We consider an attacker seeking to increase the storage requirements by one gigabyte. For that, they would have to create $20$ million, or $2 \cdot 10^7$ new UTXO entries. We can now ask ourselves two questions: 1. How long would the attack last given a fixed budget? 2. How expensive the attack should be given it should last a fixed amount of time.

• Fixed budget Say the attacker has a budget of $20,000$ kas. That is, $2\cdot 10^4\cdot 10^8$ dworks. Plugging this into the bound, we get that $C\cdot growth^2/budget = (10^{12}\cdot 4 \cdot 10^{14})/(2 \cdot 10^4 \cdot 10^8) = 2 \cdot 10^{14}$. That is, the attack would cost $2 \cdot 10^{14}$ grams, which would take the full capacity of 400 million blocks. Hence, in 10BPS such an attack would require at least a year and a half, assuming the attacker uses 100% of the network throughput and the fees are negligible.

• Fixed growth rate Say the attacker wishes to increase the storage by a whole GB within a single day (again, assuming the attacker is given the entire network throughput for negligible fees). In 10BPS, the network has a throughput of a bit over $4\cdot 10^{11}$ grams per day. Substituting into the bound and rearranging we get $budget \ge C \cdot growth^2/\text{mass}$. Substituting $C = 10^{12}$, $growth = 2 \cdot 10^7$ and $\text{mass} = 4\cdot 10^{11}$ we get that the required budget is at least $10^{15}/4$ dworks, which is $2.5$ million kaspa.

Overall, the attack is either very slow or very expensive. How does this compare with the dust attack? That attack created 1185 UTXOs per block. In 10BPS, this means 50GB per day. Without the quadratic bound, the only limitation to such an attack is that each output must be at least $10,000$ dworks. In other words, assuming 10BPS, an attacker could increase the storage by 50GB in a single day for 100,000 kaspa. The computation above shows that, with a budget of 100,000 kaspa, it would take 750 years to waste 50GB. Conversely, wasting 50GB in one day requires a budget of 125 million kaspa.

We can also use the bound to provide an absolute worst-case upper bound on the organic growth of the UTXO set. Assume for simplicity the total circulation is $20$ billion kaspa. In 10BPS, the daily mass capacity is about $4\cdot 10^{11}$. The quadratic bound implies that in $d$ days the storage can increase by at most $460\sqrt{d}$ gigabytes. This allows us to bound the storage increase as a function of the time that passed since the mass policy was implemented. During the first day, the storage can increase by at most one terabyte. During the first year: at most $10$ terabyte. During the first ten years: at most $25$ terabytes. Reaching $100$ terabyte will require almost 130 years, and $1$ peta will not happen before 13 thousand years. This is a very mild growth considering it bounds even the worst scenario possible: all Kaspa holders joining forces to increase the storage as much as possible, managing to apply the best strategy to do so.

Quality of service

We discuss the implications of storage mass on common everyday transactions.

First consider a transaction $\text{tx}$ with a single $100$ kaspa input, and two near-equal outputs of values $\sim 50$ kaspa. We can compute that $$\text{storage mass}(\text{tx}) \approx 2C\cdot \left(\frac{2}{50 \cdot 10^8} - \frac{1}{100 \cdot 10^8}\right) = 300$$

In contrast, one can check that $\text{compute mass}(\text{tx}) \ge 2000$, so we see that the total mass is not changed, despite the fact that $\text{tx}$ is a relatively low-value transaction with more outputs than inputs.

More generally, we see that the storage_mass becomes dominant only when relatively small inputs emerge (where the exact threshold is inversely proportional to the total budget of the transaction). Still, even in everyday use, we see that small outputs can emerge. Small UTXOs commonly appear as change or as micropayments, and however we set $C$, we should account for the possibility that a standard payment from a standard wallet could exceed this threshold, affecting the QoS of everyday users. In section Wallet algorithm we will show how to compose transactions for sending arbitrarily small values, and in section Micropayments we will discuss strategies for mitigating this cost altogether.

Compounding transactions

A transaction $\text{tx}$ is compounding if $|O| \le |I|$ and all values in $O$ are equal, namely $=\text{budget}/|O|$ (most commonly, we have that $|O|=1$). Since all values in $O$ are the same we have that $H(O) = A(O) = \text{budget}/|O|$ and we get that $$\text{storage mass}(\text{tx}) = C\cdot\left(\frac{|O|}{A(O)} - \frac{|I|}{A(I)}\right)^+ = C\cdot\left(\frac{|O|^2 - |I|^2}{\text{budget}}\right)^+ = 0\text{.}$$ Hence, compounding several outputs into an equal or smaller number of outputs of equal value will never incur storage mass. This is true regardless of the magnitude of the output values.

It is worth deliberating a bit on how fees affect this phenomenon. The presence of a fee modifies the mass equation as so: $\text{storage mass}\left(\text{tx}\right)=C\cdot\left(\frac{\left|O\right|^{2}}{\text{budget}-\text{fee}}-\frac{\left|I\right|^{2}}{\text{budget}}\right)$, and after some rearrangement, one can see that the storage mass becomes positive if and only if $\left(1-\left(\frac{\left|O\right|}{\left|I\right|}\right)^{2}\right)<\frac{\text{fee}}{\text{budget}}$. It is nice to notice that the condition above completely depends on the number of inputs and outputs and the fee-to-budget ratio, not the actual values or even $C$. However, in scenarios where the storage mass is positive, its actual value does depend on all of these quantities. The first example that jumps to the eye is the case $|I|=|O|$, where clearly any positive fee will beget positive storage mass. However, one can see numerically that unless the values are very small and/or the fee is very large, the storage mass will still be smaller than the computation mass.

In the case $|O| = 1$ the condition becomes $\left(1-\frac{1}{\left|I\right|^{2}}\right)<\frac{\text{fee}}{\text{budget}}$. So even for $|I|=2$, the storage mass vanishes unless the fee is at least three-quarters of the entire value.

The overall takeaway of the analysis is that compounding is treated "nicely" by the storage mass function, even in the presence of fees.

Exchanges and pools

Exchanges and pools should immediately benefit from this proposal. Both do not usually deal with micropayments, and the currently deployed patch highly limits their ability to submit many transactions at times of increased load. Also in the long term, an exchange can be considered a highly active wallet whose deposit and withdrawal volumes are roughly the same. That is, the values of deposits are distributed roughly the same as those of withdrawals. By matching inputs with outputs of the same magnitude, exchanges can keep the storage mass low even in a future where typical transactions have low (say, sub-kaspa) values.

Similarly, pools can remove most storage mass by setting the cashout limit to be larger than a typical coinbase output.

Micropayments

A comprehensive solution must also consider scenarios where everyday users wish to spend very small values (much smaller than $0.1$ kaspa). We discuss how this can be achieved, assuming all wallets hold at least 1 kaspa (i.e. $10^8$ dworks).

Consider an eccentric millionaire with a penchant for ice cream. Every morning, our hero grabs a wallet containing a single UTXO of at least $1000$ kaspa, and goes to the stand to buy a vanilla cone for a comfortable price of $0.1$ kaspa. How should the millionaire pay for her purchase?

Consider a transaction $\text{tx}$ with a single input of value $V$ and two outputs of values $v$ and $V-v$ where $v\ll V$, then it follows that $$\text{storage mass}\left(\text{tx}\right)\approx C\cdot\left(\frac{1}{V-v}+\frac{1}{v}-\frac{1}{V}\right)\approx\frac{C}{v}\text{.}$$ In particular, in order to pay the vendor $0.1$ kaspa, and the change back to himself, the millionaire would have to create a transaction whose mass is around $100,000$ grams. This is one-fifth of the capacity of a block. That is, the fees for this transaction would be 40 times more expensive than "standard" transactions (whose storage mass is lower than their computation mass). Paying as much for a single transaction might be excusable as a one-time last resort, but users would not (and should not) agree to pay it daily.

The key point is in realizing that the merchant selling the ice cream does not keep such small amounts indefinitely, but rather will compound them eventually (say on a daily basis). However the future actions of the merchant are unknown to the system, and the action is locally indistinguishable from the actions of a deliberate dust attacker. In an account-based model, such a transaction would merely appear as a transfer of a small value between significantly larger accounts. Essentially, the account model embeds the future compounding of the payment into the local operation.

We argue that this exact behavior can be emulated also in the UTXO model by creating a mutually signed transaction. The vendor and the millionaire create a transaction together with two $1000$ kaspa inputs, one spent by the vendor and the other spent by the millionaire, and two outputs, one paying $1000.1$ kaspa to the vendor and the other paying $999.9$ kaspa to the millionaire. This facilitates the payment while removing the storage mass costs. Note that the UTXO available to the merchant need not exactly match in value to the millionaire's wallet. Even using a UTXO of $10$ kaspa, the outputs are $999.9$ and $10.1$. Since the smallest output is much larger, the mass would turn out much smaller.

The downside to this solution is that the merchant must constantly have a hot wallet available and cooperate with the customer to create a mutually signed transaction. In a following KIP, we will specify auto-compounding wallet addresses, where UTXOs owned by such addresses will allow anyone to add to their balance without the owner of the UTXO having to sign it. Among other applications, this mechanism will allow the millionaire to purchase ice cream as described above, using her wallet alone.

Wallet algorithm

In this section we provide an optimal algorithm for making a payment of a given value using a given set of UTXOs. The algorithm is "optimal" in the sense that it minimizes the number of transactions required to make this payment and the overall mass they consume.

Disclaimer: the algorithm described does not cover all possible edge-cases (especially fee-related aspects), and is brought here as a guideline to the path which should be taken. With the help of the community we hope to soon publish a comprehensive standalone reference implementation (in the form of a Python Jupyter notebook), which will address the need for a more accurate reference.

Denote $M$ to be the maximal storage mass a single transaction could have. The value $M$ can be either the common mempool bound (currently set to $100,000$ grams), or user specified. Additionally, assume there is a conversion ratio $r$ of mass to fee. The value of $r$ is usually obtained by the wallet software by monitoring the network usage. Hence a transaction of mass $m$ will pay a fee of $rm$. We let $F=rM$ denote the fee of a maximally heavy transaction.

Say the user desires to make a payment with value $P$ and that we already collected sufficient inputs $I$ such that $\sum_{v \in I}v \ge P + F$. The algorithm pre-assumes that a transaction composed of $I$ and $O = \lbrace P, \sum_{v \in I}v - P - F\rbrace$ has $\text{compute mass} \le M$ but $\text{storage mass} > M$. Otherwise, if compute mass is too large, it should be solved using the current methods of compounding by building a transaction tree. Recall that such compounding transactions will never have storage mass, so there's never a need to solve both objectives in parallel. Eventually we arrive at a root transaction where compute mass is low enough, at which point storage mass can be dealt with if needed.

Single step optimization We begin by solving a single step of the process. The question we ask is “Given a mass bound $M$ and a set of inputs $I$, what is the minimum payment value possible without surpassing $M$?”. Or in more mathematical terms “What is the maximum asymmetry we can create between the 2 outputs given the constrains?”. Denote $N$ to be the negative component of the storage mass as described by the relaxed formula. Note that $I$ and the number of outputs (which is known to be 2 in this case), are sufficient for calculating this part. Let $T=\sum_{v \in I}v - F$ denote the total outputs value. We need to solve the following equation: $M = C/T\alpha + C/T(1-\alpha) - N$, where $\alpha \in (0, 1)$. Reorganizing terms we get $(M+N)T/C = 1/\alpha + 1/(1-\alpha)$. Let $D = (M+N)T/C$. Reorganizing terms further we arrive at the quadratic equation $D\alpha^2 - D\alpha + 1 = 0$ which solutions for are $\alpha = (D \pm \sqrt{D^2 - 4D})/2D$. Note that from symmetry of $\alpha, (1-\alpha)$ both solutions of the equation essentially give the same answer.

Iterative process Using this single step optimization we now describe an iterative algorithm for composing the chain of transactions required for making a micropayment:

def build_txs(inputs, payment):
    txs = []
    while storage_mass(I=inputs, O=[payment, sum(inputs) - payment - F]) > M:
        T = sum(inputs) - F
        N = negative_mass(inputs, 2) 
        D = (M + N)T/C
        alpha = (D - sqrt(D^2 - 4D))/2D                         # single step optimization, taking the smaller solution 
        outputs = [ceiling(alpha * T), T - ceiling(alpha * T)]  # round up in order to not increase the mass above M
        txs.append((inputs, outputs))
        inputs = outputs
    txs.append((inputs, [payment, sum(inputs) - payment - F]))
    return txs

Remarks

• In all iterations of the while loop (except maybe for the first), $I=O=2$
• Without the relaxed formula which uses the harmonic mean over the inputs (in the 2:2 case), the loop would not converge. The arithmetic averaging done over the inputs would yield the same $N$ value over and over
• The initial inputs should contain sufficient slack to cover all fees along the process. The value returned by the initial call to storage_mass is a good estimation for the overall mass required and hence can be used to estimate the overall fee.
• In all intermediate transactions built within the loop, the recipient for both outputs should be the change address of the sender
• In the final transaction built, it is possible that the actual fee can be decreased below $F$ depending on the final mass

Implementation details

Consensus implementation

Recall that consensus implementation required a relatively complex design. Here we elaborate on this subtlety, and how it was solved by slightly changing the structure of a transaction.

Background The block validation in Kaspa is divided into three phases:

• Header validation: the block header has the required form, points to known blocks, satisfies the difficulty target, etc.
• Data validation: the block body has the required form, as do all transactions therein, and in particular it satisfies the mass limit
• Transaction validation: all transactions have valid signatures and spend existing UTXOs. Perhaps surprisingly, a block only has to pass the first two phases to be considered valid. The reason for that is that the third part of validation does not rely on the block data alone, but requires us to compute the UTXO set from the point of view of that block. For efficiency reasons, we only want to compute the UTXO set for selected-chain blocks. This tension is resolved by having this "intermediate status" where a block could be perfectly valid, but disqualified from being in the selected-chain. In particular, future blocks pointing at this block will process any valid transactions that appear therein (otherwise they will also be disqualified from the selected-chain).

The Problem The values of UTXOs are not explicitly written inside the transaction but are rather recovered from the UTXO set. So in order to compute the storage mass, we must compute the UTXO state of the block. This contradicts our ambition to validate the block during the data validation phase while avoiding having to compute its UTXO state.

Solution We adapt an idea we already used for fixing an issue with the sig_op_count opcode (see [4]). We require transactions to have an explicit mass field. During the data validation phase, the client only verifies that the sum of masses does not exceed the block mass limit. Verifying that the stated mass values are consistent with the formula is only performed for chain blocks and deferred to the transaction validation phase. Transactions with false mass values are considered invalid, and blocks containing them are disqualified from the selected-chain.

Current status

This proposal is already implemented by the Kaspa on Rust codebase (PR). Currently applied on the mempool level for all networks (mainnet, testnet 10, testnet 11). It is also implemented on the consensus level, but only activated for testnet 11 (TN11). The current implementation however is slightly different. Particularly, it sums the storage mass with the compute mass instead of using max, and it also does not implement the relaxed formula. The implementation should be updated shortly to reflect this final proposal. To avoid code clutter and multiple versions, we suggest hard-forking or restarting TN11 with the fixed rules.

References

[1] “A Very Dusty Yom-Kippur (dust attack post-mortem)” https://medium.com/@shai.wyborski/a-very-dusty-yom-kippur-dust-attack-post-mortem-faa11804e37

[2] Kaspad go-lang dust patch: kaspanet/kaspad#2244

[3] Unpublished paper on state growth regulation in permissionless systems, this reference will be updated once the paper is published online.

[4] “Kaspa Security Patch and Hard Fork — September 2022” https://medium.com/@michaelsuttonil/kaspa-security-patch-and-hard-fork-september-2022-12da617b0094