Compact representation of fees for Mimblewimble
The Mimblewimble (MW) protocol requires each transaction to specify an explicit fee amount. It is usually stored in the transaction kernel and signed with the kernel public key to prevent tampering. However, the ~100-byte kernel is the only part of a MW transaction that needs to be stored in the blockchain indefinitely. If the transaction fees are stored with full 64-bit precision, the fees may represent up to 8 percent of the whole blockchain download size as the transaction history grows.
This article describes a method to encode transaction priority and fee value in just 2 bytes (16 bits). The main idea is that instead of encoding the fee with the fixed precision of 1 atomic currency unit, we can encode the fee with a relative precision of about 0.1%-0.3%, which should be acceptable to most users.
2. Encoding scheme
We will use the 16 bits as follows:
+-------------------+-------------------+-----------------------+ | Priority (2 bits) | Exponent (4 bits) | Significand (10 bits) | +-------------------+-------------------+-----------------------+
Transaction priority is usually given by the fee rate, which is the fee amount divided by the transaction size. In Bitcoin, the transaction size is known to the sender, so the priority is set implicitly by the specified fee amount.
However, MW allows for non-interactive aggregation of transactions, which means that when Bob is sending a transaction, he cannot know the final size of his transaction when it arrives to a miner. Even if he sets an above-average fee amount, Mallory can join her low-fee transaction with Bob's, resulting in a tranasction that has a total fee rate lower than Bob intended.
It is therefore necessary to specify an explicit priority to prevent fee hijacking. Our protocol supports 4 different priority levels. This should be sufficient in cases when the transaction fee only serves as a spam deterrent and is not meant to replace the block subsidy.
We can then define the following non-consensus rule:
A transaction may only be relayed if its total fee rate is at least
Ltimes the minimum transaction fee rate, where
Lis the highest priority multiplier among the transaction's kernels.
Now if Bob wants to expedite his transaction, he can set the High priority level and pay at least 32 times the minimum fee. If Mallory wants to aggregate her transaction with Bob's, she must also pay at least 32 times the minimum fee or the aggregated transaction won't be relayed by the network.
Note: Monero uses similar values of transaction priority multipliers . The exact values are not critical as they can be changed by a simple client update without forking.
2.2 Fee amount
The fee amount is calculated from the unsigned exponent
e and unsigned significand
fee = s * 2^(a*e+b) + 1024 * Σ(j < e) 2^(a*j+b)
b are constants that can be selected depending on the required minimum and maximum representable fee value and
^ is the exponentiation operator. The second term in the formula sums the ranges of all the exponents lower than
e, ensuring that different exponents represent disjunct intervals.
For example, with
b=6, the values
(e=1,s=994) encode the fee amount of
994*2^8 + 1024*2^6 = 320000 atomic units.
Grin has 109 atomic units per coin. Good values for encoding the fee are
b=0. The range of representable non-zero values then ranges from 1 nanogrin (nG) up to ~1465 Grin, which is more than 20 times the block subsidy and should be enough to submit any reasonably sized transaction with the Instant priority level.
|exponent||approx. range||approx. precision|
|0||0-1 μG||1 nG|
|1||1-5 μG||4 nG|
|2||5-21 μG||16 nG|
|3||21-87 μG||64 nG|
|4||87-349 μG||256 nG|
|5||0.35-1.4 mG||1 μG|
|6||1.4-5.6 mG||4 μG|
|7||5.6-22 mG||16 μG|
|8||22-89 mG||65 μG|
|9||89-358 mG||262 μG|
|10||0.36-1.4 G||1 mG|
|11||1.4-5.7 G||4 mG|
|12||5.7-22.9 G||17 mG|
|13||22.9-91.6 G||67 mG|
|14||91.6-366 G||268 mG|
|15||367-1465 G||1 G|
Bob wants to submit a transaction that requires a minimum fee of 24 mG with the High priority level. The kernel fee should be at least 0.768 G. The closest representable value is
(e=10,s=392), which results in a fee value of 0.768693248 G (that's only 0.09% higher than the intended value). The priority+fee will be encoded in binary as