electrum

Electrum Bitcoin wallet
git clone https://git.parazyd.org/electrum
Log | Files | Refs | Submodules

commit 10c799faab45ea53962d89527bf72bdc392c9862
parent 1b7d8c0387734463dca66ddc978b4c966320272d
Author: bitromortac <bitromortac@protonmail.com>
Date:   Thu, 11 Mar 2021 12:00:47 +0100

mpp_split: add penalty for exhaustion of channels

A penalty is added for split configurations which saturate a channel.
Saturation of channels is discouraged as we don't know the fees
beforehand. The penalty is accomplished via an exponential function that
kicks in when the subamount reaches about the total funds available
(this amount is controlled by the parameter EXHAUST_DECAY_FRACTION).

Diffstat:
Melectrum/mpp_split.py | 31++++++++++++++++++++-----------
Melectrum/tests/test_mpp_split.py | 14+++++++++++++-
2 files changed, 33 insertions(+), 12 deletions(-)

diff --git a/electrum/mpp_split.py b/electrum/mpp_split.py @@ -1,20 +1,26 @@ import random +import math from typing import List, Tuple, Optional, Sequence, Dict from collections import defaultdict + from .util import profiler from .lnutil import NoPathFound PART_PENALTY = 1.0 # 1.0 results in avoiding splits MIN_PART_MSAT = 10_000_000 # we don't want to split indefinitely +EXHAUST_DECAY_FRACTION = 10 # fraction of the local balance that should be reserved if possible # these parameters determine the granularity of the newly suggested configurations -REDISTRIBUTION_FRACTION = 10 -SPLIT_FRACTION = 10 +REDISTRIBUTION_FRACTION = 50 +SPLIT_FRACTION = 50 # these parameters affect the computational work in the probabilistic algorithm STARTING_CONFIGS = 50 CANDIDATES_PER_LEVEL = 10 -REDISTRIBUTE = 10 +REDISTRIBUTE = 20 + +# maximum number of parts for splitting +MAX_PARTS = 5 def unique_hierarchy(hierarchy: Dict[int, List[Dict[bytes, int]]]) -> Dict[int, List[Dict[bytes, int]]]: @@ -167,12 +173,16 @@ def suggest_splits(amount_msat: int, channels_with_funds, exclude_single_parts=T amounts that are equally distributed and have less parts are rated lowest.""" F = 0 - amount = sum([v for v in config.values()]) + total_amount = sum([v for v in config.values()]) + + for channel, amount in config.items(): + funds = channels_with_funds[channel] + if amount: + F += amount * amount / (total_amount * total_amount) # a penalty to favor distribution of amounts + F += PART_PENALTY * PART_PENALTY # a penalty for each part + decay = funds / EXHAUST_DECAY_FRACTION + F += math.exp((amount - funds) / decay) # a penalty for channel saturation - for channel, value in config.items(): - if value: - value /= amount # normalize - F += value * value + PART_PENALTY * PART_PENALTY return F def rated_sorted_configurations(hierarchy: dict) -> Sequence[Tuple[Dict[bytes, int], float]]: @@ -189,9 +199,8 @@ def suggest_splits(amount_msat: int, channels_with_funds, exclude_single_parts=T # create initial guesses split_hierarchy = create_starting_split_hierarchy(amount_msat, channels_with_funds) - # randomize initial guesses - MAX_PARTS = 5 - # generate splittings of different split levels up to number of channels + # randomize initial guesses and generate splittings of different split + # levels up to number of channels for level in range(2, min(MAX_PARTS, len(channels_with_funds) + 1)): # generate a set of random configurations for each level for _ in range(CANDIDATES_PER_LEVEL): diff --git a/electrum/tests/test_mpp_split.py b/electrum/tests/test_mpp_split.py @@ -28,7 +28,7 @@ class TestMppSplit(ElectrumTestCase): def test_suggest_splits(self): with self.subTest(msg="do a payment with the maximal amount spendable over a single channel"): splits = mpp_split.suggest_splits(1_000_000_000, self.channels_with_funds, exclude_single_parts=True) - self.assertEqual({0: 500_000_000, 1: 500_000_000, 2: 0, 3: 0}, splits[0][0]) + self.assertEqual({0: 660_000_000, 1: 340_000_000, 2: 0, 3: 0}, splits[0][0]) with self.subTest(msg="do a payment with a larger amount than what is supported by a single channel"): splits = mpp_split.suggest_splits(1_100_000_000, self.channels_with_funds, exclude_single_parts=True) @@ -43,6 +43,18 @@ class TestMppSplit(ElectrumTestCase): for s in splits[:4]: self.assertEqual(1, mpp_split.number_nonzero_parts(s[0])) + def test_saturation(self): + """Split configurations which spend the full amount in a channel should be avoided.""" + channels_with_funds = {0: 159_799_733_076, 1: 499_986_152_000} + splits = mpp_split.suggest_splits(600_000_000_000, channels_with_funds, exclude_single_parts=True) + + uses_full_amount = False + for c, a in splits[0][0].items(): + if a == channels_with_funds[c]: + uses_full_amount |= True + + self.assertFalse(uses_full_amount) + def test_payment_below_min_part_size(self): amount = mpp_split.MIN_PART_MSAT // 2 splits = mpp_split.suggest_splits(amount, self.channels_with_funds, exclude_single_parts=False)