feat(client): consolidate excessive amount of notes in a given tier

[dpc]

In Fedi's LN gateway deployement, we've hit a condition where LN gateway accumulated tons of tiny notes and at some point is trying to spend all of them at once, creating tx larger than consensus limit.

Fundamentally, when an client like LN gateway is handling a lot of tiny payements, it will keep dealing with and accumulating tiny note denominations. The change outputs note selection algorithm tries to create outputs so that user has at least certain amount of notes available at every tier, but does nothing to get rid of excessive ones.

At some point it has to consolidate them.

This PR hooks up into the tx finalization, to potentially add some excessive notes to each transaction.

There are multiple ways to approach this problem, some might be more elegant or smarter, but this solution is simple and should deal with the issue without changing normal use-cases.

Testing

Some automated test would be better, but RN I tested by manually lowering the tresholds and in devimint env running:

export RUST_LOG=fm::client::module::mint=debug,info
fedimint-cli info
fedimint-cli ln-invoice --amount 4msat
etc.

when the treshold of given denomination is reached:

2024-04-11T01:37:21.106950Z DEBUG fm::client::module::mint: Will consolidate excessive notes note_num=16 denominations_msats=[2, 2, 128, 128, 512, 512, 1024, 10
24, 4096, 4096, 32768, 32768, 524288, 524288, 1048576, 1048576]

Testing this is tricky, because it requires creating unbalanced notes, while the change selector keeps recreating notes to fill up the tiers.

Re #4913

[dpc]

After thinking about it more, it seems to me that making note selector spend excessive notes as a priority would be much better approach, but that seems like much more involved change, and I created #4923 on how I'd approach it.

[dpc]

I just can't help but keep refactoring...

[douglaz]

I'm inclined to NACK this. I don't think "excess notes" was or will ever be an issue. The issue we had and will continue to have is a matter of a lack of notes (in that specific incident, a lack of mid-sized ones). So we should be talking about shortage of notes and filling these gaps. While filling these gaps we may or may not consume "excess notes". Probably we want spend high-tier notes to fill mid-tier ones.

[dpc]

I'm inclined to NACK this. I don't think "excess notes" was or will ever be an issue. The issue we had and will continue to have is a matter of a lack of notes (in that specific incident, a lack of mid-sized ones). So we should be talking about shortage of notes and filling these gaps. While filling these gaps we may or may not consume "excess notes". Probably we want spend high-tier notes to fill mid-tier ones.

"Lack of high-tier notes" is the same thing as "having too many low-tier notes". If we have 100s of low-tier notes, and consolidate them, we'll get the extra higher-tier notes we were lacking.

Probably we want spend high-tier notes to fill mid-tier ones.

If we lack a mid-tier note we can always spend a high-tier one and get a change. Also low-tier notes first consolidate into mid-tier, mid-tier into high-tier.

The goal is to generally have a flatter distribution altogether, so it's always possible to spend everything at once.

Though again - this is a quick provisional solution.

@douglaz :+1: :question:

[douglaz]

I'm inclined to NACK this. I don't think "excess notes" was or will ever be an issue. The issue we had and will continue to have is a matter of a lack of notes (in that specific incident, a lack of mid-sized ones). So we should be talking about shortage of notes and filling these gaps. While filling these gaps we may or may not consume "excess notes". Probably we want spend high-tier notes to fill mid-tier ones.

"Lack of high-tier notes" is the same thing as "having too many low-tier notes". If we have 100s of low-tier notes, and consolidate them, we'll get the extra higher-tier notes we were lacking.

Lower tier notes won't give too much yield because of their small value. the way of solving the lack of high tier notes is by spending even higher notes.

Probably we want spend high-tier notes to fill mid-tier ones.

If we lack a mid-tier note we can always spend a high-tier one and get a change. Also low-tier notes first consolidate into mid-tier, mid-tier into high-tier.

Lower tier notes are more "useful" (i.e they can always be used if within the transaction limit). Proactively spending them may be harmful. I think any consolidation algorithm should focus on spending higher tiers first.

The goal is to generally have a flatter distribution altogether, so it's always possible to spend everything at once. A pyramid shape is perfectly ok supposing we don't have missing tiers on the middle.

Though again - this is a quick provisional solution.

@douglaz 👍 ❓

Ok, this may help in some cases, so it's a valid quick-improvement

My guess is that it would not be enough to avoid that particular incident and will create a slightly worse note distribution in some extraordinary circumstances.

Anyway it's probably better than what we have today.

[dpc]

Lower tier notes won't give too much yield because of their small value. the way of solving the lack of high tier notes is by spending even higher notes.

The change consolidates all notes all the same. Notes will continuously consolidate into higher ones, higher into even higher.

Lower tier notes are more "useful" (i.e they can always be used if within the transaction limit). Proactively spending them may be harmful. I think any consolidation algorithm should focus on spending higher tiers first.

I don't understand. As implemented RN, consolidation only ever spends notes that you already have plenty of.

Maybe we can discuss the whole thing in a Deep Dive. Added to https://github.com/fedimint/fedimint/wiki/Deep-Dive-Topics

[dpc]

Commits with overlapping changes were pilling up, so just decided to squash it all.

Notably I changed the algo. so it first detects if any tier is above a MAX_TRIGGER and then consolidates all notes above MIN per tier. This should lead to less churn.

I need to test it again manually, and maybe think about a good test of some kinid, so will not merge just yet.

[dpc]

OK, seems to work.

I'd really love a test for that. Need to find some good way to test though.

[douglaz]

Provide some initial funds to a client, then create transactions generating uneven notes (see how fedimint-load-test-tool does that) then check if a normal spending/reissue will rebalance the notes.

[maan2003]

I would love a explicit "rebalance" function that I can run whenever client is online, so in future selection is better when offline

[justinmoon]

dev call: needs testing

[dpc]

Test should be ready.

Rebased on top of #5128 due to conflicts.

[dpc]

 00:00:41 assertion failed: epochs_descriptors.contains(*utxo_descriptor)

Known problem, re-added to MQ.