Skip to content

Instantly share code, notes, and snippets.

@tevador

tevador/mw-fees.md

Last active Jan 31, 2021
Embed
What would you like to do?

Compact representation of fees for Mimblewimble

1. Introduction

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.

1.1 Contribution

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) |
+-------------------+-------------------+-----------------------+

2.1 Priority

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.

encoding priority multiplier
00 Low 1
01 Medium 4
10 High 32
11 Instant 1024

We can then define the following non-consensus rule:

A transaction may only be relayed if its total fee rate is at least L times the minimum transaction fee rate, where L is 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 [1]. 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 s as:

fee = s * 2^(a*e+b) + 1024 * Σ(j < e) 2^(a*j+b)

where a, 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 a=2 and b=6, the values (e=1,s=994) encode the fee amount of 994*2^8 + 1024*2^6 = 320000 atomic units.

3. Grin

Grin has 109 atomic units per coin. Good values for encoding the fee are a=2 and 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

3.1 Example

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 1010100110001000.

References

[1] https://github.com/monero-project/monero/blob/d2fda6c25f476c45acbc875721106f965435d99f/src/wallet/wallet2.cpp#L7435

@DavidBurkett

This comment has been minimized.

Copy link

@DavidBurkett DavidBurkett commented Jan 30, 2021

You also have the option of moving fees to the outputs so they're pruned when spent.

@tromp

This comment has been minimized.

Copy link

@tromp tromp commented Jan 30, 2021

Your reference [1] is missing.

It may be worth pointing out that this type of limited precision encoding was introduced in the cryptocurrency space with Bitcoin's "nBits" network difficulty [1].

Grin already uses a 4 bit priority field, in addition to 40 bits for the fee value [2].
If so desired, the space savings could be achieved without artificially restricting the possible fee values
by allowing some compression scheme in the peer-to-peer layer, as is already done for the TXO spent bitmap.

[1] https://btcinformation.org/en/developer-reference#target-nbits
[2] https://github.com/mimblewimble/grin-rfcs/blob/master/text/0017-fix-fees.md

@tevador

This comment has been minimized.

Copy link
Owner Author

@tevador tevador commented Jan 30, 2021

You also have the option of moving fees to the outputs so they're pruned when spent.

I thought about this, but it brings a host of issues:

  • How do you split the fee between multiple outputs without leaking information?
  • What happens if an output is spent off-chain? The fee value could then be stolen.

Your reference [1] is missing.

Thanks, It was a clickable link, but I added an explicit reference at the end.

It may be worth pointing out that this type of limited precision encoding was introduced in the cryptocurrency space with Bitcoin's "nBits" network difficulty [1].

It seems that the encoding of "nBits" is not unique, for example 0x18001b30 and 0x171b3000 both encode the same value.

4 bit priority field, in addition to 40 bits for the fee value

The 40-bit fixed-precision fee has about the same range as the 14-bit variable-precision fee. Monero gets by just fine with 4 priority levels. Having the user choose their priority from 16 levels may be bad for UX (search for "Hick's law").

without artificially restricting the possible fee values

Is there a practical benefit to setting the fee to 0.100000001 as opposed to 0.1? I don't see the need to keep the fixed precision across the whole range of possible fee values. In fact, high-precision fees were identified as a possible privacy leak in Monero (but this is less of an issue for Grin).

@tromp

This comment has been minimized.

Copy link

@tromp tromp commented Jan 30, 2021

Monero gets by just fine with 4 priority levels. Having the user choose their priority from 16 levels may be bad for UX (search for "Hick's law").

And currently Grin gets by just fine with only 1 level. Current clients don't support the multitude of priority levels.
And could choose to support whatever number they think best balances UX complexity against priority setting needs.
The 16 is just for future proofing.
Note that the current 2-input 2-output 1-kernel minfee at max priority 15 takes exactly 40 bits.

Is there a practical benefit to setting the fee to 0.100000001 as opposed to 0.1? I don't see the need to keep the fixed precision across the whole range of possible fee values.

No benefit that I can see at this time. This choice is more for simplicity.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment