mpp_split.py (10308B)
1 import random 2 import math 3 from typing import List, Tuple, Optional, Sequence, Dict 4 from collections import defaultdict 5 6 from .util import profiler 7 from .lnutil import NoPathFound 8 9 PART_PENALTY = 1.0 # 1.0 results in avoiding splits 10 MIN_PART_MSAT = 10_000_000 # we don't want to split indefinitely 11 EXHAUST_DECAY_FRACTION = 10 # fraction of the local balance that should be reserved if possible 12 13 # these parameters determine the granularity of the newly suggested configurations 14 REDISTRIBUTION_FRACTION = 50 15 SPLIT_FRACTION = 50 16 17 # these parameters affect the computational work in the probabilistic algorithm 18 STARTING_CONFIGS = 50 19 CANDIDATES_PER_LEVEL = 10 20 REDISTRIBUTE = 20 21 22 # maximum number of parts for splitting 23 MAX_PARTS = 5 24 25 26 def unique_hierarchy(hierarchy: Dict[int, List[Dict[bytes, int]]]) -> Dict[int, List[Dict[bytes, int]]]: 27 new_hierarchy = defaultdict(list) 28 for number_parts, configs in hierarchy.items(): 29 unique_configs = set() 30 for config in configs: 31 # config dict can be out of order, so sort, otherwise not unique 32 unique_configs.add(tuple((c, config[c]) for c in sorted(config.keys()))) 33 for unique_config in sorted(unique_configs): 34 new_hierarchy[number_parts].append( 35 {t[0]: t[1] for t in unique_config}) 36 return new_hierarchy 37 38 39 def number_nonzero_parts(configuration: Dict[bytes, int]): 40 return len([v for v in configuration.values() if v]) 41 42 43 def create_starting_split_hierarchy(amount_msat: int, channels_with_funds: Dict[bytes, int]): 44 """Distributes the amount to send to a single or more channels in several 45 ways (randomly).""" 46 # TODO: find all possible starting configurations deterministically 47 # could try all permutations 48 49 split_hierarchy = defaultdict(list) 50 channels_order = list(channels_with_funds.keys()) 51 52 for _ in range(STARTING_CONFIGS): 53 # shuffle to have different starting points 54 random.shuffle(channels_order) 55 56 configuration = {} 57 amount_added = 0 58 for c in channels_order: 59 s = channels_with_funds[c] 60 if amount_added == amount_msat: 61 configuration[c] = 0 62 else: 63 amount_to_add = amount_msat - amount_added 64 amt = min(s, amount_to_add) 65 configuration[c] = amt 66 amount_added += amt 67 if amount_added != amount_msat: 68 raise NoPathFound("Channels don't have enough sending capacity.") 69 split_hierarchy[number_nonzero_parts(configuration)].append(configuration) 70 71 return unique_hierarchy(split_hierarchy) 72 73 74 def balances_are_not_ok(proposed_balance_from, channel_from, proposed_balance_to, channel_to, channels_with_funds): 75 check = ( 76 proposed_balance_to < MIN_PART_MSAT or 77 proposed_balance_to > channels_with_funds[channel_to] or 78 proposed_balance_from < MIN_PART_MSAT or 79 proposed_balance_from > channels_with_funds[channel_from] 80 ) 81 return check 82 83 84 def propose_new_configuration(channels_with_funds: Dict[bytes, int], configuration: Dict[bytes, int], 85 amount_msat: int, preserve_number_parts=True) -> Dict[bytes, int]: 86 """Randomly alters a split configuration. If preserve_number_parts, the 87 configuration stays within the same class of number of splits.""" 88 89 # there are three basic operations to reach different split configurations: 90 # redistribute, split, swap 91 92 def redistribute(config: dict): 93 # we redistribute the amount from a nonzero channel to a nonzero channel 94 redistribution_amount = amount_msat // REDISTRIBUTION_FRACTION 95 nonzero = [ck for ck, cv in config.items() if 96 cv >= redistribution_amount] 97 if len(nonzero) == 1: # we only have a single channel, so we can't redistribute 98 return config 99 100 channel_from = random.choice(nonzero) 101 channel_to = random.choice(nonzero) 102 if channel_from == channel_to: 103 return config 104 proposed_balance_from = config[channel_from] - redistribution_amount 105 proposed_balance_to = config[channel_to] + redistribution_amount 106 if balances_are_not_ok(proposed_balance_from, channel_from, proposed_balance_to, channel_to, channels_with_funds): 107 return config 108 else: 109 config[channel_from] = proposed_balance_from 110 config[channel_to] = proposed_balance_to 111 assert sum([cv for cv in config.values()]) == amount_msat 112 return config 113 114 def split(config: dict): 115 # we split off a certain amount from a nonzero channel and put it into a 116 # zero channel 117 nonzero = [ck for ck, cv in config.items() if cv != 0] 118 zero = [ck for ck, cv in config.items() if cv == 0] 119 try: 120 channel_from = random.choice(nonzero) 121 channel_to = random.choice(zero) 122 except IndexError: 123 return config 124 delta = config[channel_from] // SPLIT_FRACTION 125 proposed_balance_from = config[channel_from] - delta 126 proposed_balance_to = config[channel_to] + delta 127 if balances_are_not_ok(proposed_balance_from, channel_from, proposed_balance_to, channel_to, channels_with_funds): 128 return config 129 else: 130 config[channel_from] = proposed_balance_from 131 config[channel_to] = proposed_balance_to 132 assert sum([cv for cv in config.values()]) == amount_msat 133 return config 134 135 def swap(config: dict): 136 # we swap the amounts from a single channel with another channel 137 nonzero = [ck for ck, cv in config.items() if cv != 0] 138 all = list(config.keys()) 139 140 channel_from = random.choice(nonzero) 141 channel_to = random.choice(all) 142 143 proposed_balance_to = config[channel_from] 144 proposed_balance_from = config[channel_to] 145 if balances_are_not_ok(proposed_balance_from, channel_from, proposed_balance_to, channel_to, channels_with_funds): 146 return config 147 else: 148 config[channel_to] = proposed_balance_to 149 config[channel_from] = proposed_balance_from 150 return config 151 152 initial_number_parts = number_nonzero_parts(configuration) 153 154 for _ in range(REDISTRIBUTE): 155 configuration = redistribute(configuration) 156 if not preserve_number_parts and number_nonzero_parts( 157 configuration) == initial_number_parts: 158 configuration = split(configuration) 159 configuration = swap(configuration) 160 161 return configuration 162 163 164 @profiler 165 def suggest_splits(amount_msat: int, channels_with_funds, exclude_single_parts=True) -> Sequence[Tuple[Dict[bytes, int], float]]: 166 """Creates split configurations for a payment over channels. Single channel 167 payments are excluded by default.""" 168 def rate_configuration(config: dict) -> float: 169 """Defines an objective function to rate a split configuration. 170 171 We calculate the normalized L2 norm for a split configuration and 172 add a part penalty for each nonzero amount. The consequence is that 173 amounts that are equally distributed and have less parts are rated 174 lowest.""" 175 F = 0 176 total_amount = sum([v for v in config.values()]) 177 178 for channel, amount in config.items(): 179 funds = channels_with_funds[channel] 180 if amount: 181 F += amount * amount / (total_amount * total_amount) # a penalty to favor distribution of amounts 182 F += PART_PENALTY * PART_PENALTY # a penalty for each part 183 decay = funds / EXHAUST_DECAY_FRACTION 184 F += math.exp((amount - funds) / decay) # a penalty for channel saturation 185 186 return F 187 188 def rated_sorted_configurations(hierarchy: dict) -> Sequence[Tuple[Dict[bytes, int], float]]: 189 """Cleans up duplicate splittings, rates and sorts them according to 190 the rating. A lower rating is a better configuration.""" 191 hierarchy = unique_hierarchy(hierarchy) 192 rated_configs = [] 193 for level, configs in hierarchy.items(): 194 for config in configs: 195 rated_configs.append((config, rate_configuration(config))) 196 sorted_rated_configs = sorted(rated_configs, key=lambda c: c[1], reverse=False) 197 return sorted_rated_configs 198 199 # create initial guesses 200 split_hierarchy = create_starting_split_hierarchy(amount_msat, channels_with_funds) 201 202 # randomize initial guesses and generate splittings of different split 203 # levels up to number of channels 204 for level in range(2, min(MAX_PARTS, len(channels_with_funds) + 1)): 205 # generate a set of random configurations for each level 206 for _ in range(CANDIDATES_PER_LEVEL): 207 configurations = unique_hierarchy(split_hierarchy).get(level, None) 208 if configurations: # we have a splitting of the desired number of parts 209 configuration = random.choice(configurations) 210 # generate new splittings preserving the number of parts 211 configuration = propose_new_configuration( 212 channels_with_funds, configuration, amount_msat, 213 preserve_number_parts=True) 214 else: 215 # go one level lower and look for valid splittings, 216 # try to go one level higher by splitting a single outgoing amount 217 configurations = unique_hierarchy(split_hierarchy).get(level - 1, None) 218 if not configurations: 219 continue 220 configuration = random.choice(configurations) 221 # generate new splittings going one level higher in the number of parts 222 configuration = propose_new_configuration( 223 channels_with_funds, configuration, amount_msat, 224 preserve_number_parts=False) 225 226 # add the newly found configuration (doesn't matter if nothing changed) 227 split_hierarchy[number_nonzero_parts(configuration)].append(configuration) 228 229 if exclude_single_parts: 230 # we only want to return configurations that have at least two parts 231 try: 232 del split_hierarchy[1] 233 except: 234 pass 235 236 return rated_sorted_configurations(split_hierarchy)