tmpp_split.py - electrum - Electrum Bitcoin wallet
HTML git clone https://git.parazyd.org/electrum
DIR Log
DIR Files
DIR Refs
DIR Submodules
---
tmpp_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)