1 #include <ccan/array_size/array_size.h>
2 #include <ccan/tal/str/str.h>
3 #include <common/dijkstra.h>
4 #include <common/gossmap.h>
5 #include <common/json_stream.h>
6 #include <common/memleak.h>
7 #include <common/pseudorand.h>
8 #include <common/random_select.h>
9 #include <common/type_to_string.h>
10 #include <errno.h>
11 #include <math.h>
12 #include <plugins/libplugin-pay.h>
13 #include <sys/types.h>
14 #include <wire/peer_wire.h>
15
16 static struct gossmap *global_gossmap;
17
init_gossmap(struct plugin * plugin)18 static void init_gossmap(struct plugin *plugin)
19 {
20 size_t num_channel_updates_rejected;
21 global_gossmap
22 = notleak_with_children(gossmap_load(NULL,
23 GOSSIP_STORE_FILENAME,
24 &num_channel_updates_rejected));
25 if (!global_gossmap)
26 plugin_err(plugin, "Could not load gossmap %s: %s",
27 GOSSIP_STORE_FILENAME, strerror(errno));
28 if (num_channel_updates_rejected)
29 plugin_log(plugin, LOG_DBG,
30 "gossmap ignored %zu channel updates",
31 num_channel_updates_rejected);
32 }
33
get_gossmap(struct plugin * plugin)34 struct gossmap *get_gossmap(struct plugin *plugin)
35 {
36 if (!global_gossmap)
37 init_gossmap(plugin);
38 else
39 gossmap_refresh(global_gossmap, NULL);
40 return global_gossmap;
41 }
42
payment_new(tal_t * ctx,struct command * cmd,struct payment * parent,struct payment_modifier ** mods)43 struct payment *payment_new(tal_t *ctx, struct command *cmd,
44 struct payment *parent,
45 struct payment_modifier **mods)
46 {
47 struct payment *p = tal(ctx, struct payment);
48
49 static u64 next_id = 0;
50
51 p->children = tal_arr(p, struct payment *, 0);
52 p->parent = parent;
53 p->modifiers = mods;
54 p->cmd = cmd;
55 p->start_time = time_now();
56 p->result = NULL;
57 p->why = NULL;
58 p->getroute = tal(p, struct getroute_request);
59 p->label = NULL;
60 p->failreason = NULL;
61 p->getroute->riskfactorppm = 10000000;
62 p->abort = false;
63 p->route = NULL;
64 p->temp_exclusion = NULL;
65 p->failroute_retry = false;
66 p->invstring = NULL;
67 p->routetxt = NULL;
68 p->max_htlcs = UINT32_MAX;
69 p->aborterror = NULL;
70 p->on_payment_success = NULL;
71 p->on_payment_failure = NULL;
72
73 /* Copy over the relevant pieces of information. */
74 if (parent != NULL) {
75 assert(cmd == NULL);
76 tal_arr_expand(&parent->children, p);
77 p->destination = parent->destination;
78 p->destination_has_tlv = parent->destination_has_tlv;
79 p->amount = parent->amount;
80 p->label = parent->label;
81 p->payment_hash = parent->payment_hash;
82 p->partid = payment_root(p->parent)->next_partid++;
83 p->plugin = parent->plugin;
84
85 /* Re-establish the unmodified constraints for our sub-payment. */
86 p->constraints = *parent->start_constraints;
87 p->deadline = parent->deadline;
88
89 p->min_final_cltv_expiry = parent->min_final_cltv_expiry;
90 p->routes = parent->routes;
91 p->features = parent->features;
92 p->id = parent->id;
93 p->local_id = parent->local_id;
94 p->local_offer_id = parent->local_offer_id;
95 p->groupid = parent->groupid;
96 } else {
97 assert(cmd != NULL);
98 p->partid = 0;
99 p->next_partid = 1;
100 p->plugin = cmd->plugin;
101 p->channel_hints = tal_arr(p, struct channel_hint, 0);
102 p->excluded_nodes = tal_arr(p, struct node_id, 0);
103 p->id = next_id++;
104 /* Caller must set this. */
105 p->local_id = NULL;
106 p->local_offer_id = NULL;
107 p->groupid = 0;
108 }
109
110 /* Initialize all modifier data so we can point to the fields when
111 * wiring into the param() call in a JSON-RPC handler. The callback
112 * can also just `memcpy` the parent if this outside access is not
113 * required. */
114 p->modifier_data = tal_arr(p, void *, 0);
115 for (size_t i=0; mods[i] != NULL; i++) {
116 if (mods[i]->data_init != NULL)
117 tal_arr_expand(&p->modifier_data,
118 mods[i]->data_init(p));
119 else
120 tal_arr_expand(&p->modifier_data, NULL);
121 }
122
123 return p;
124 }
125
payment_root(struct payment * p)126 struct payment *payment_root(struct payment *p)
127 {
128 if (p->parent == NULL)
129 return p;
130 else
131 return payment_root(p->parent);
132 }
133
134 static void
paymod_log_header(struct payment * p,const char ** type,u64 * id)135 paymod_log_header(struct payment *p, const char **type, u64 *id)
136 {
137 struct payment *root = payment_root(p);
138 /* We prefer to show the command ID here since it is also known
139 * by `lightningd`, so in theory it can be used to correlate
140 * debugging logs between the main `lightningd` and whatever
141 * plugin is using the paymod system.
142 * We only fall back to a unique id per root payment if there
143 * is no command with an id associated with this payment.
144 */
145 if (root->cmd && root->cmd->id) {
146 *type = "cmd";
147 *id = *root->cmd->id;
148 } else {
149 *type = "id";
150 *id = root->id;
151 }
152 }
153
154 static void
paymod_log(struct payment * p,enum log_level l,const char * fmt,...)155 paymod_log(struct payment *p, enum log_level l, const char *fmt, ...)
156 {
157 const char *type;
158 u64 id;
159 char *txt;
160 va_list ap;
161
162 va_start(ap, fmt);
163 txt = tal_vfmt(tmpctx, fmt, ap);
164 va_end(ap);
165
166 paymod_log_header(p, &type, &id);
167 plugin_log(p->plugin, l, "%s %"PRIu64" partid %"PRIu32": %s",
168 type, id, p->partid, txt);
169 }
170 static void
paymod_err(struct payment * p,const char * fmt,...)171 paymod_err(struct payment *p, const char *fmt, ...)
172 {
173 const char *type;
174 u64 id;
175 char *txt;
176 va_list ap;
177
178 va_start(ap, fmt);
179 txt = tal_vfmt(tmpctx, fmt, ap);
180 va_end(ap);
181
182 paymod_log_header(p, &type, &id);
183 plugin_err(p->plugin, "%s %"PRIu64" partid %"PRIu32": %s",
184 type, id, p->partid, txt);
185 }
186
187 /* Generic handler for RPC failures that should end up failing the payment. */
payment_rpc_failure(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)188 static struct command_result *payment_rpc_failure(struct command *cmd,
189 const char *buffer,
190 const jsmntok_t *toks,
191 struct payment *p)
192 {
193 payment_fail(p,
194 "Failing a partial payment due to a failed RPC call: %.*s",
195 toks->end - toks->start, buffer + toks->start);
196 return command_still_pending(cmd);
197 }
198
payment_collect_result(struct payment * p)199 struct payment_tree_result payment_collect_result(struct payment *p)
200 {
201 struct payment_tree_result res;
202 size_t numchildren = tal_count(p->children);
203 res.sent = AMOUNT_MSAT(0);
204 res.attempts = 1;
205 res.treestates = p->step;
206 res.leafstates = 0;
207 res.preimage = NULL;
208 res.failure = NULL;
209 if (p->step == PAYMENT_STEP_FAILED && p->result != NULL)
210 res.failure = p->result;
211
212 if (numchildren == 0) {
213 res.leafstates |= p->step;
214 if (p->result && p->result->state == PAYMENT_COMPLETE) {
215 res.sent = p->result->amount_sent;
216 res.preimage = p->result->payment_preimage;
217 }
218 }
219
220 for (size_t i = 0; i < numchildren; i++) {
221 struct payment_tree_result cres =
222 payment_collect_result(p->children[i]);
223
224 /* Some of our subpayments have succeeded, aggregate how much
225 * we sent in total. */
226 if (!amount_msat_add(&res.sent, res.sent, cres.sent))
227 paymod_err(
228 p,
229 "Number overflow summing partial payments: %s + %s",
230 type_to_string(tmpctx, struct amount_msat,
231 &res.sent),
232 type_to_string(tmpctx, struct amount_msat,
233 &cres.sent));
234
235 /* Bubble up the first preimage we see. */
236 if (res.preimage == NULL && cres.preimage != NULL)
237 res.preimage = cres.preimage;
238
239 res.leafstates |= cres.leafstates;
240 res.treestates |= cres.treestates;
241 res.attempts += cres.attempts;
242
243 /* We bubble the failure result with the highest failcode up
244 * to the root. */
245 if (res.failure == NULL ||
246 (cres.failure != NULL &&
247 cres.failure->failcode > res.failure->failcode)) {
248 res.failure = cres.failure;
249 }
250 }
251 return res;
252 }
253
254 static struct command_result *
payment_getblockheight_success(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)255 payment_getblockheight_success(struct command *cmd,
256 const char *buffer,
257 const jsmntok_t *toks,
258 struct payment *p)
259 {
260 const jsmntok_t *blockheighttok =
261 json_get_member(buffer, toks, "blockheight");
262 json_to_number(buffer, blockheighttok, &p->start_block);
263 payment_continue(p);
264 return command_still_pending(cmd);
265 }
266
267 #define INVALID_BLOCKHEIGHT UINT32_MAX
268
269 static
payment_start_at_blockheight(struct payment * p,u32 blockheight)270 void payment_start_at_blockheight(struct payment *p, u32 blockheight)
271 {
272 struct payment *root = payment_root(p);
273
274 /* Should have been set in root payment, or propagated from root
275 * payment to all child payments. */
276 assert(p->local_id);
277
278 p->step = PAYMENT_STEP_INITIALIZED;
279 p->current_modifier = -1;
280
281 /* Pre-generate the getroute request, so modifiers can have their say,
282 * before we actually call `getroute` */
283 p->getroute->destination = p->destination;
284 p->getroute->max_hops = ROUTING_MAX_HOPS;
285 p->getroute->cltv = root->min_final_cltv_expiry;
286 p->getroute->amount = p->amount;
287
288 p->start_constraints = tal_dup(p, struct payment_constraints, &p->constraints);
289
290 if (blockheight != INVALID_BLOCKHEIGHT) {
291 /* The caller knows the actual blockheight. */
292 p->start_block = blockheight;
293 return payment_continue(p);
294 }
295 if (p->parent) {
296 /* The parent should have a start block. */
297 p->start_block = p->parent->start_block;
298 return payment_continue(p);
299 }
300
301 /* `waitblockheight 0` can be used as a query for the current
302 * block height.
303 * This is slightly better than `getinfo` since `getinfo`
304 * counts the channels and addresses and pushes more data
305 * onto the RPC but all we care about is the blockheight.
306 */
307 struct out_req *req;
308 req = jsonrpc_request_start(p->plugin, NULL, "waitblockheight",
309 &payment_getblockheight_success,
310 &payment_rpc_failure, p);
311 json_add_u32(req->js, "blockheight", 0);
312 send_outreq(p->plugin, req);
313 }
payment_start(struct payment * p)314 void payment_start(struct payment *p)
315 {
316 payment_start_at_blockheight(p, INVALID_BLOCKHEIGHT);
317 }
318
channel_hints_update(struct payment * p,const struct short_channel_id scid,int direction,bool enabled,bool local,const struct amount_msat * estimated_capacity,u16 * htlc_budget)319 static void channel_hints_update(struct payment *p,
320 const struct short_channel_id scid,
321 int direction, bool enabled, bool local,
322 const struct amount_msat *estimated_capacity,
323 u16 *htlc_budget)
324 {
325 struct payment *root = payment_root(p);
326 struct channel_hint hint;
327
328 /* If the channel is marked as enabled it must have an estimate. */
329 assert(!enabled || estimated_capacity != NULL);
330
331 /* Try and look for an existing hint: */
332 for (size_t i=0; i<tal_count(root->channel_hints); i++) {
333 struct channel_hint *hint = &root->channel_hints[i];
334 if (short_channel_id_eq(&hint->scid.scid, &scid) &&
335 hint->scid.dir == direction) {
336 bool modified = false;
337 /* Prefer to disable a channel. */
338 if (!enabled && hint->enabled) {
339 hint->enabled = false;
340 modified = true;
341 }
342
343 /* Prefer the more conservative estimate. */
344 if (estimated_capacity != NULL &&
345 amount_msat_greater(hint->estimated_capacity,
346 *estimated_capacity)) {
347 hint->estimated_capacity = *estimated_capacity;
348 modified = true;
349 }
350 if (htlc_budget != NULL && *htlc_budget < hint->htlc_budget) {
351 hint->htlc_budget = *htlc_budget;
352 modified = true;
353 }
354
355 if (modified)
356 paymod_log(p, LOG_DBG,
357 "Updated a channel hint for %s: "
358 "enabled %s, "
359 "estimated capacity %s",
360 type_to_string(tmpctx,
361 struct short_channel_id_dir,
362 &hint->scid),
363 hint->enabled ? "true" : "false",
364 type_to_string(tmpctx,
365 struct amount_msat,
366 &hint->estimated_capacity));
367 return;
368 }
369 }
370
371 /* No hint found, create one. */
372 hint.enabled = enabled;
373 hint.scid.scid = scid;
374 hint.scid.dir = direction;
375 hint.local = local;
376 if (estimated_capacity != NULL)
377 hint.estimated_capacity = *estimated_capacity;
378
379 if (htlc_budget != NULL)
380 hint.htlc_budget = *htlc_budget;
381
382 tal_arr_expand(&root->channel_hints, hint);
383
384 paymod_log(
385 p, LOG_DBG,
386 "Added a channel hint for %s: enabled %s, estimated capacity %s",
387 type_to_string(tmpctx, struct short_channel_id_dir, &hint.scid),
388 hint.enabled ? "true" : "false",
389 type_to_string(tmpctx, struct amount_msat,
390 &hint.estimated_capacity));
391 }
392
payment_exclude_most_expensive(struct payment * p)393 static void payment_exclude_most_expensive(struct payment *p)
394 {
395 struct route_hop *e = &p->route[0];
396 struct amount_msat fee, worst = AMOUNT_MSAT(0);
397
398 for (size_t i = 0; i < tal_count(p->route)-1; i++) {
399 if (!amount_msat_sub(&fee, p->route[i].amount, p->route[i+1].amount))
400 paymod_err(p, "Negative fee in a route.");
401
402 if (amount_msat_greater_eq(fee, worst)) {
403 e = &p->route[i];
404 worst = fee;
405 }
406 }
407 channel_hints_update(p, e->scid, e->direction, false, false,
408 NULL, NULL);
409 }
410
payment_exclude_longest_delay(struct payment * p)411 static void payment_exclude_longest_delay(struct payment *p)
412 {
413 struct route_hop *e = &p->route[0];
414 u32 delay, worst = 0;
415
416 for (size_t i = 0; i < tal_count(p->route)-1; i++) {
417 delay = p->route[i].delay - p->route[i+1].delay;
418 if (delay >= worst) {
419 e = &p->route[i];
420 worst = delay;
421 }
422 }
423 channel_hints_update(p, e->scid, e->direction, false, false,
424 NULL, NULL);
425 }
426
payment_route_fee(struct payment * p)427 static struct amount_msat payment_route_fee(struct payment *p)
428 {
429 struct amount_msat fee;
430 if (!amount_msat_sub(&fee, p->route[0].amount, p->amount)) {
431 paymod_log(
432 p,
433 LOG_BROKEN,
434 "gossipd returned a route with a negative fee: sending %s "
435 "to deliver %s",
436 type_to_string(tmpctx, struct amount_msat,
437 &p->route[0].amount),
438 type_to_string(tmpctx, struct amount_msat, &p->amount));
439 abort();
440 }
441 return fee;
442 }
443
444 /* Update the constraints by subtracting the delta_fee and delta_cltv if the
445 * result is positive. Returns whether or not the update has been applied. */
446 static WARN_UNUSED_RESULT bool
payment_constraints_update(struct payment_constraints * cons,const struct amount_msat delta_fee,const u32 delta_cltv)447 payment_constraints_update(struct payment_constraints *cons,
448 const struct amount_msat delta_fee,
449 const u32 delta_cltv)
450 {
451 if (delta_cltv > cons->cltv_budget)
452 return false;
453
454 /* amount_msat_sub performs a check before actually subtracting. */
455 if (!amount_msat_sub(&cons->fee_budget, cons->fee_budget, delta_fee))
456 return false;
457
458 cons->cltv_budget -= delta_cltv;
459 return true;
460 }
461
payment_chanhints_get(struct payment * p,struct route_hop * h)462 static struct channel_hint *payment_chanhints_get(struct payment *p,
463 struct route_hop *h)
464 {
465 struct payment *root = payment_root(p);
466 struct channel_hint *curhint;
467 for (size_t j = 0; j < tal_count(root->channel_hints); j++) {
468 curhint = &root->channel_hints[j];
469 if (short_channel_id_eq(&curhint->scid.scid, &h->scid) &&
470 curhint->scid.dir == h->direction) {
471 return curhint;
472 }
473 }
474 return NULL;
475 }
476
477 /* Given a route and a couple of channel hints, apply the route to the channel
478 * hints, so we have a better estimation of channel's capacity. We apply a
479 * route to a channel hint before calling `sendonion` so subsequent `route`
480 * calls don't accidentally try to use those out-of-date estimates. We unapply
481 * if the payment failed, i.e., all HTLCs we might have added have been torn
482 * down again. Finally we leave the update in place if the payment went
483 * through, since the balances really changed in that case. The `remove`
484 * argument indicates whether we want to apply (`remove=false`), or clear a
485 * prior application (`remove=true`). */
payment_chanhints_apply_route(struct payment * p,bool remove)486 static bool payment_chanhints_apply_route(struct payment *p, bool remove)
487 {
488 bool apply;
489 struct route_hop *curhop;
490 struct channel_hint *curhint;
491 struct payment *root = payment_root(p);
492 assert(p->route != NULL);
493
494 /* No need to check for applicability if we increase
495 * capacity and budgets. */
496 if (remove)
497 goto apply_changes;
498
499 /* First round: make sure we can cleanly apply the update. */
500 for (size_t i = 0; i < tal_count(p->route); i++) {
501 curhop = &p->route[i];
502 curhint = payment_chanhints_get(root, curhop);
503
504 /* If we don't have a hint we can't fail updating it. */
505 if (!curhint)
506 continue;
507
508 /* For local channels we check that we don't overwhelm
509 * them with too many HTLCs. */
510 apply = (!curhint->local) || curhint->htlc_budget > 0;
511
512 /* For all channels we check that they have a
513 * sufficiently large estimated capacity to have some
514 * chance of succeeding. */
515 apply &= amount_msat_greater(curhint->estimated_capacity,
516 curhop->amount);
517
518 if (!apply) {
519 /* This can happen in case of multiple
520 * concurrent getroute calls using the
521 * same channel_hints, no biggy, it's
522 * an estimation anyway. */
523 paymod_log(p, LOG_DBG,
524 "Could not update the channel hint "
525 "for %s. Could be a concurrent "
526 "`getroute` call.",
527 type_to_string(tmpctx,
528 struct short_channel_id_dir,
529 &curhint->scid));
530 return false;
531 }
532 }
533
534 apply_changes:
535 /* Second round: apply the changes, now that we know they'll succeed. */
536 for (size_t i = 0; i < tal_count(p->route); i++) {
537 curhop = &p->route[i];
538 curhint = payment_chanhints_get(root, curhop);
539 if (!curhint)
540 continue;
541
542 /* Update the number of htlcs for any local
543 * channel in the route */
544 if (curhint->local && remove)
545 curhint->htlc_budget++;
546 else if (curhint->local)
547 curhint->htlc_budget--;
548
549 if (remove && !amount_msat_add(
550 &curhint->estimated_capacity,
551 curhint->estimated_capacity,
552 curhop->amount)) {
553 /* This should never happen, it'd mean
554 * that we unapply a route that would
555 * result in a msatoshi
556 * wrap-around. */
557 abort();
558 } else if (!amount_msat_sub(
559 &curhint->estimated_capacity,
560 curhint->estimated_capacity,
561 curhop->amount)) {
562 /* Given our preemptive test
563 * above, this should never
564 * happen either. */
565 abort();
566 }
567 }
568 return true;
569 }
570
571 static const struct short_channel_id_dir *
payment_get_excluded_channels(const tal_t * ctx,struct payment * p)572 payment_get_excluded_channels(const tal_t *ctx, struct payment *p)
573 {
574 struct payment *root = payment_root(p);
575 struct channel_hint *hint;
576 struct short_channel_id_dir *res =
577 tal_arr(ctx, struct short_channel_id_dir, 0);
578 for (size_t i = 0; i < tal_count(root->channel_hints); i++) {
579 hint = &root->channel_hints[i];
580
581 if (!hint->enabled)
582 tal_arr_expand(&res, hint->scid);
583
584 else if (amount_msat_greater_eq(p->amount,
585 hint->estimated_capacity))
586 /* We exclude on equality because we've set the
587 * estimate to the smallest failed attempt. */
588 tal_arr_expand(&res, hint->scid);
589
590 else if (hint->local && hint->htlc_budget == 0)
591 /* If we cannot add any HTLCs to the channel we
592 * shouldn't look for a route through that channel */
593 tal_arr_expand(&res, hint->scid);
594 }
595 return res;
596 }
597
payment_get_excluded_nodes(const tal_t * ctx,struct payment * p)598 static const struct node_id *payment_get_excluded_nodes(const tal_t *ctx,
599 struct payment *p)
600 {
601 struct payment *root = payment_root(p);
602 return root->excluded_nodes;
603 }
604
605 /* FIXME: This is slow! */
find_hint(const struct channel_hint * hints,const struct short_channel_id * scid,int dir)606 static const struct channel_hint *find_hint(const struct channel_hint *hints,
607 const struct short_channel_id *scid,
608 int dir)
609 {
610 for (size_t i = 0; i < tal_count(hints); i++) {
611 if (short_channel_id_eq(scid, &hints[i].scid.scid)
612 && dir == hints[i].scid.dir)
613 return &hints[i];
614 }
615 return NULL;
616 }
617
618 /* FIXME: This is slow! */
dst_is_excluded(const struct gossmap * gossmap,const struct gossmap_chan * c,int dir,const struct node_id * nodes)619 static bool dst_is_excluded(const struct gossmap *gossmap,
620 const struct gossmap_chan *c,
621 int dir,
622 const struct node_id *nodes)
623 {
624 struct node_id dstid;
625
626 /* Premature optimization */
627 if (!tal_count(nodes))
628 return false;
629
630 gossmap_node_get_id(gossmap, gossmap_nth_node(gossmap, c, !dir),
631 &dstid);
632 for (size_t i = 0; i < tal_count(nodes); i++) {
633 if (node_id_eq(&dstid, &nodes[i]))
634 return true;
635 }
636 return false;
637 }
638
payment_route_check(const struct gossmap * gossmap,const struct gossmap_chan * c,int dir,struct amount_msat amount,struct payment * p)639 static bool payment_route_check(const struct gossmap *gossmap,
640 const struct gossmap_chan *c,
641 int dir,
642 struct amount_msat amount,
643 struct payment *p)
644 {
645 struct short_channel_id scid;
646 const struct channel_hint *hint;
647
648 if (dst_is_excluded(gossmap, c, dir, payment_root(p)->excluded_nodes))
649 return false;
650
651 if (dst_is_excluded(gossmap, c, dir, p->temp_exclusion))
652 return false;
653
654 scid = gossmap_chan_scid(gossmap, c);
655 hint = find_hint(payment_root(p)->channel_hints, &scid, dir);
656 if (!hint)
657 return true;
658
659 if (!hint->enabled)
660 return false;
661
662 if (amount_msat_greater_eq(amount, hint->estimated_capacity))
663 /* We exclude on equality because we've set the
664 * estimate to the smallest failed attempt. */
665 return false;
666
667 if (hint->local && hint->htlc_budget == 0)
668 /* If we cannot add any HTLCs to the channel we
669 * shouldn't look for a route through that channel */
670 return false;
671
672 return true;
673 }
674
payment_route_can_carry(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount,struct payment * p)675 static bool payment_route_can_carry(const struct gossmap *map,
676 const struct gossmap_chan *c,
677 int dir,
678 struct amount_msat amount,
679 struct payment *p)
680 {
681 if (!route_can_carry(map, c, dir, amount, p))
682 return false;
683
684 return payment_route_check(map, c, dir, amount, p);
685 }
686
payment_route_can_carry_even_disabled(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount,struct payment * p)687 static bool payment_route_can_carry_even_disabled(const struct gossmap *map,
688 const struct gossmap_chan *c,
689 int dir,
690 struct amount_msat amount,
691 struct payment *p)
692 {
693 if (!route_can_carry_even_disabled(map, c, dir, amount, p))
694 return false;
695
696 return payment_route_check(map, c, dir, amount, p);
697 }
698
699 /* Rene Pickhardt:
700 *
701 * Btw the linear term of the Taylor series of -log((c+1-x)/(c+1)) is 1/(c+1)
702 * meaning that another suitable Weight for Dijkstra would be amt/(c+1) +
703 * \mu*fee(amt) which is the linearized version which for small amounts and
704 * suitable value of \mu should be good enough)
705 */
capacity_bias(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount)706 static u64 capacity_bias(const struct gossmap *map,
707 const struct gossmap_chan *c,
708 int dir,
709 struct amount_msat amount)
710 {
711 struct amount_sat capacity;
712 u64 capmsat, amtmsat = amount.millisatoshis; /* Raw: lengthy math */
713
714 /* Can fail in theory if gossmap changed underneath. */
715 if (!gossmap_chan_get_capacity(map, c, &capacity))
716 return 0;
717
718 capmsat = capacity.satoshis * 1000; /* Raw: lengthy math */
719 return -log((capmsat + 1 - amtmsat) / (capmsat + 1));
720 }
721
722 /* Prioritize costs over distance, but bias to larger channels. */
route_score(u32 distance,struct amount_msat cost,struct amount_msat risk,int dir,const struct gossmap_chan * c)723 static u64 route_score(u32 distance,
724 struct amount_msat cost,
725 struct amount_msat risk,
726 int dir,
727 const struct gossmap_chan *c)
728 {
729 u64 cmsat = cost.millisatoshis; /* Raw: lengthy math */
730 u64 rmsat = risk.millisatoshis; /* Raw: lengthy math */
731 u64 bias = capacity_bias(global_gossmap, c, dir, cost);
732
733 /* Smoothed harmonic mean to avoid division by 0 */
734 u64 costs = (cmsat * rmsat * bias) / (cmsat + rmsat + bias + 1);
735
736 if (costs > 0xFFFFFFFF)
737 costs = 0xFFFFFFFF;
738 return costs;
739 }
740
route(const tal_t * ctx,struct gossmap * gossmap,const struct gossmap_node * src,const struct gossmap_node * dst,struct amount_msat amount,u32 final_delay,double riskfactor,size_t max_hops,struct payment * p,const char ** errmsg)741 static struct route_hop *route(const tal_t *ctx,
742 struct gossmap *gossmap,
743 const struct gossmap_node *src,
744 const struct gossmap_node *dst,
745 struct amount_msat amount,
746 u32 final_delay,
747 double riskfactor,
748 size_t max_hops,
749 struct payment *p,
750 const char **errmsg)
751 {
752 const struct dijkstra *dij;
753 struct route_hop *r;
754 bool (*can_carry)(const struct gossmap *,
755 const struct gossmap_chan *,
756 int,
757 struct amount_msat,
758 struct payment *);
759
760 can_carry = payment_route_can_carry;
761 dij = dijkstra(tmpctx, gossmap, dst, amount, riskfactor,
762 can_carry, route_score, p);
763 r = route_from_dijkstra(ctx, gossmap, dij, src, amount, final_delay);
764 if (!r) {
765 /* Try using disabled channels too */
766 /* FIXME: is there somewhere we can annotate this for paystatus? */
767 can_carry = payment_route_can_carry_even_disabled;
768 dij = dijkstra(ctx, gossmap, dst, amount, riskfactor,
769 can_carry, route_score, p);
770 r = route_from_dijkstra(ctx, gossmap, dij, src,
771 amount, final_delay);
772 if (!r) {
773 *errmsg = "No path found";
774 return NULL;
775 }
776 }
777
778 /* If it's too far, fall back to using shortest path. */
779 if (tal_count(r) > max_hops) {
780 tal_free(r);
781 /* FIXME: is there somewhere we can annotate this for paystatus? */
782 dij = dijkstra(tmpctx, gossmap, dst, amount, riskfactor,
783 can_carry, route_score_shorter, p);
784 r = route_from_dijkstra(ctx, gossmap, dij, src,
785 amount, final_delay);
786 if (!r) {
787 *errmsg = "No path found";
788 return NULL;
789 }
790
791 /* If it's still too far, fail. */
792 if (tal_count(r) > max_hops) {
793 *errmsg = tal_fmt(ctx, "Shortest path found was length %zu",
794 tal_count(r));
795 return tal_free(r);
796 }
797 }
798
799 return r;
800 }
801
payment_getroute(struct payment * p)802 static struct command_result *payment_getroute(struct payment *p)
803 {
804 const struct gossmap_node *dst, *src;
805 struct amount_msat fee;
806 const char *errstr;
807 struct gossmap *gossmap;
808
809 gossmap = get_gossmap(p->plugin);
810
811 dst = gossmap_find_node(gossmap, p->getroute->destination);
812 if (!dst) {
813 payment_fail(
814 p, "Unknown destination %s",
815 type_to_string(tmpctx, struct node_id,
816 p->getroute->destination));
817
818 /* Let payment_finished_ handle this, so we mark it as pending */
819 return command_still_pending(p->cmd);
820 }
821
822 /* If we don't exist in gossip, routing can't happen. */
823 src = gossmap_find_node(gossmap, p->local_id);
824 if (!src) {
825 payment_fail(p, "We don't have any channels");
826
827 /* Let payment_finished_ handle this, so we mark it as pending */
828 return command_still_pending(p->cmd);
829 }
830
831 p->route = route(p, gossmap, src, dst, p->getroute->amount, p->getroute->cltv,
832 p->getroute->riskfactorppm / 1000000.0, p->getroute->max_hops,
833 p, &errstr);
834 if (!p->route) {
835 payment_fail(p, "%s", errstr);
836 /* Let payment_finished_ handle this, so we mark it as pending */
837 return command_still_pending(p->cmd);
838 }
839
840 /* OK, now we *have* a route */
841 p->step = PAYMENT_STEP_GOT_ROUTE;
842
843 if (tal_count(p->route) == 0) {
844 payment_root(p)->abort = true;
845 payment_fail(p, "Empty route returned by getroute, are you "
846 "trying to pay yourself?");
847 }
848
849 fee = payment_route_fee(p);
850
851 /* Ensure that our fee and CLTV budgets are respected. */
852 if (amount_msat_greater(fee, p->constraints.fee_budget)) {
853 payment_exclude_most_expensive(p);
854 p->route = tal_free(p->route);
855 payment_fail(
856 p, "Fee exceeds our fee budget: %s > %s, discarding route",
857 type_to_string(tmpctx, struct amount_msat, &fee),
858 type_to_string(tmpctx, struct amount_msat,
859 &p->constraints.fee_budget));
860 return command_still_pending(p->cmd);
861 }
862
863 if (p->route[0].delay > p->constraints.cltv_budget) {
864 u32 delay = p->route[0].delay;
865 payment_exclude_longest_delay(p);
866 p->route = tal_free(p->route);
867 payment_fail(p, "CLTV delay exceeds our CLTV budget: %d > %d",
868 delay, p->constraints.cltv_budget);
869 return command_still_pending(p->cmd);
870 }
871
872 /* Now update the constraints in fee_budget and cltv_budget so
873 * modifiers know what constraints they need to adhere to. */
874 if (!payment_constraints_update(&p->constraints, fee, p->route[0].delay)) {
875 paymod_log(p, LOG_BROKEN,
876 "Could not update constraints.");
877 abort();
878 }
879
880 /* Allow modifiers to modify the route, before
881 * payment_compute_onion_payloads uses the route to generate the
882 * onion_payloads */
883 payment_continue(p);
884 return command_still_pending(p->cmd);
885 }
886
tal_towire_legacy_payload(const tal_t * ctx,const struct legacy_payload * payload)887 static u8 *tal_towire_legacy_payload(const tal_t *ctx, const struct legacy_payload *payload)
888 {
889 const u8 padding[] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
890 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
891 /* Prepend 0 byte for realm */
892 u8 *buf = tal_arrz(ctx, u8, 1);
893 towire_short_channel_id(&buf, &payload->scid);
894 towire_amount_msat(&buf, payload->forward_amt);
895 towire_u32(&buf, payload->outgoing_cltv);
896 towire(&buf, padding, ARRAY_SIZE(padding));
897 assert(tal_bytelen(buf) == 1 + 32);
898 return buf;
899 }
900
tal_sendpay_result_from_json(const tal_t * ctx,const char * buffer,const jsmntok_t * toks)901 static struct payment_result *tal_sendpay_result_from_json(const tal_t *ctx,
902 const char *buffer,
903 const jsmntok_t *toks)
904 {
905 const jsmntok_t *idtok = json_get_member(buffer, toks, "id");
906 const jsmntok_t *hashtok = json_get_member(buffer, toks, "payment_hash");
907 const jsmntok_t *partidtok = json_get_member(buffer, toks, "partid");
908 const jsmntok_t *senttok = json_get_member(buffer, toks, "amount_sent_msat");
909 const jsmntok_t *statustok = json_get_member(buffer, toks, "status");
910 const jsmntok_t *preimagetok = json_get_member(buffer, toks, "payment_preimage");
911 const jsmntok_t *codetok = json_get_member(buffer, toks, "code");
912 const jsmntok_t *datatok = json_get_member(buffer, toks, "data");
913 const jsmntok_t *erridxtok, *msgtok, *failcodetok, *rawmsgtok,
914 *failcodenametok, *errchantok, *errnodetok, *errdirtok;
915 struct payment_result *result;
916
917 /* Check if we have an error and need to descend into data to get
918 * details. */
919 if (codetok != NULL && datatok != NULL) {
920 idtok = json_get_member(buffer, datatok, "id");
921 hashtok = json_get_member(buffer, datatok, "payment_hash");
922 partidtok = json_get_member(buffer, datatok, "partid");
923 senttok = json_get_member(buffer, datatok, "amount_sent_msat");
924 statustok = json_get_member(buffer, datatok, "status");
925 }
926
927 /* Initial sanity checks, all these fields must exist. */
928 if (idtok == NULL || idtok->type != JSMN_PRIMITIVE ||
929 hashtok == NULL || hashtok->type != JSMN_STRING ||
930 senttok == NULL || senttok->type != JSMN_STRING ||
931 statustok == NULL || statustok->type != JSMN_STRING) {
932 return NULL;
933 }
934
935 result = tal(ctx, struct payment_result);
936
937 if (codetok != NULL)
938 json_to_u32(buffer, codetok, &result->code);
939 else
940 result->code = 0;
941
942 /* If the partid is 0 it'd be omitted in waitsendpay, fix this here. */
943 if (partidtok != NULL)
944 json_to_u32(buffer, partidtok, &result->partid);
945 else
946 result->partid = 0;
947
948 json_to_u64(buffer, idtok, &result->id);
949 json_to_msat(buffer, senttok, &result->amount_sent);
950 if (json_tok_streq(buffer, statustok, "pending")) {
951 result->state = PAYMENT_PENDING;
952 } else if (json_tok_streq(buffer, statustok, "complete")) {
953 result->state = PAYMENT_COMPLETE;
954 } else if (json_tok_streq(buffer, statustok, "failed")) {
955 result->state = PAYMENT_FAILED;
956 } else {
957 goto fail;
958 }
959
960 if (preimagetok != NULL) {
961 result->payment_preimage = tal(result, struct preimage);
962 json_to_preimage(buffer, preimagetok, result->payment_preimage);
963 }
964
965 /* Now extract the error details if the error code is not 0 */
966 if (result->code != 0) {
967 erridxtok = json_get_member(buffer, datatok, "erring_index");
968 errnodetok = json_get_member(buffer, datatok, "erring_node");
969 errchantok = json_get_member(buffer, datatok, "erring_channel");
970 errdirtok = json_get_member(buffer, datatok, "erring_direction");
971 failcodetok = json_get_member(buffer, datatok, "failcode");
972 failcodenametok =json_get_member(buffer, datatok, "failcodename");
973 msgtok = json_get_member(buffer, toks, "message");
974 rawmsgtok = json_get_member(buffer, datatok, "raw_message");
975 if (failcodetok == NULL || failcodetok->type != JSMN_PRIMITIVE ||
976 (failcodenametok != NULL && failcodenametok->type != JSMN_STRING) ||
977 (erridxtok != NULL && erridxtok->type != JSMN_PRIMITIVE) ||
978 (errnodetok != NULL && errnodetok->type != JSMN_STRING) ||
979 (errchantok != NULL && errchantok->type != JSMN_STRING) ||
980 (errdirtok != NULL && errdirtok->type != JSMN_PRIMITIVE) ||
981 msgtok == NULL || msgtok->type != JSMN_STRING ||
982 (rawmsgtok != NULL && rawmsgtok->type != JSMN_STRING))
983 goto fail;
984
985 if (rawmsgtok != NULL)
986 result->raw_message = json_tok_bin_from_hex(result, buffer, rawmsgtok);
987 else
988 result->raw_message = NULL;
989
990 if (failcodenametok != NULL)
991 result->failcodename = json_strdup(result, buffer, failcodenametok);
992 else
993 result->failcodename = NULL;
994
995 json_to_u32(buffer, failcodetok, &result->failcode);
996 result->message = json_strdup(result, buffer, msgtok);
997
998 if (erridxtok != NULL) {
999 result->erring_index = tal(result, u32);
1000 json_to_u32(buffer, erridxtok, result->erring_index);
1001 } else {
1002 result->erring_index = NULL;
1003 }
1004
1005 if (errdirtok != NULL) {
1006 result->erring_direction = tal(result, int);
1007 json_to_int(buffer, errdirtok, result->erring_direction);
1008 } else {
1009 result->erring_direction = NULL;
1010 }
1011
1012 if (errnodetok != NULL) {
1013 result->erring_node = tal(result, struct node_id);
1014 json_to_node_id(buffer, errnodetok,
1015 result->erring_node);
1016 } else {
1017 result->erring_node = NULL;
1018 }
1019
1020 if (errchantok != NULL) {
1021 result->erring_channel =
1022 tal(result, struct short_channel_id);
1023 json_to_short_channel_id(buffer, errchantok,
1024 result->erring_channel);
1025 } else {
1026 result->erring_channel = NULL;
1027 }
1028 }
1029
1030 return result;
1031 fail:
1032 return tal_free(result);
1033 }
1034
1035 /* Try to infer the erring_node, erring_channel and erring_direction from what
1036 * we know, but don't override the values that are returned by `waitsendpay`. */
payment_result_infer(struct route_hop * route,struct payment_result * r)1037 static void payment_result_infer(struct route_hop *route,
1038 struct payment_result *r)
1039 {
1040 int i, len;
1041 assert(r != NULL);
1042
1043 if (r->code == 0 || r->erring_index == NULL || route == NULL)
1044 return;
1045
1046 len = tal_count(route);
1047 i = *r->erring_index;
1048 assert(i <= len);
1049
1050 if (r->erring_node == NULL)
1051 r->erring_node = &route[i-1].node_id;
1052
1053 /* The above assert was enough for the erring_node, but might be off
1054 * by one on channel and direction, in case the destination failed on
1055 * us. */
1056 if (i == len)
1057 return;
1058
1059 if (r->erring_channel == NULL)
1060 r->erring_channel = &route[i].scid;
1061
1062 if (r->erring_direction == NULL)
1063 r->erring_direction = &route[i].direction;
1064 }
1065
1066 /* If a node takes too much fee or cltv, the next one reports it. We don't
1067 * know who to believe, but log it */
report_tampering(struct payment * p,size_t report_pos,const char * style)1068 static void report_tampering(struct payment *p,
1069 size_t report_pos,
1070 const char *style)
1071 {
1072 const struct node_id *id = &p->route[report_pos].node_id;
1073
1074 if (report_pos == 0) {
1075 paymod_log(p, LOG_UNUSUAL,
1076 "Node #%zu (%s) claimed we sent them invalid %s",
1077 report_pos + 1,
1078 type_to_string(tmpctx, struct node_id, id),
1079 style);
1080 } else {
1081 paymod_log(p, LOG_UNUSUAL,
1082 "Node #%zu (%s) claimed #%zu (%s) sent them invalid %s",
1083 report_pos + 1,
1084 type_to_string(tmpctx, struct node_id, id),
1085 report_pos,
1086 type_to_string(tmpctx, struct node_id,
1087 &p->route[report_pos-1].node_id),
1088 style);
1089 }
1090 }
1091
1092 static bool
failure_is_blockheight_disagreement(const struct payment * p,u32 * blockheight)1093 failure_is_blockheight_disagreement(const struct payment *p,
1094 u32 *blockheight)
1095 {
1096 struct amount_msat unused;
1097
1098 assert(p && p->result);
1099
1100 if (p->result->failcode == 17 /* Former final_expiry_too_soon */)
1101 *blockheight = p->start_block + 1;
1102 else if (!fromwire_incorrect_or_unknown_payment_details(
1103 p->result->raw_message,
1104 &unused, blockheight))
1105 /* If it's incorrect_or_unknown_payment_details, that tells us
1106 * what height they're at */
1107 return false;
1108
1109 /* If we are already at the desired blockheight there is no point in
1110 * waiting, and it is likely just some other error. Notice that
1111 * start_block gets set by the initial getinfo call for each
1112 * attempt.*/
1113 if (*blockheight <= p->start_block)
1114 return false;
1115
1116 return true;
1117 }
1118
describe_failcode(const tal_t * ctx,enum onion_wire failcode)1119 static char *describe_failcode(const tal_t *ctx, enum onion_wire failcode)
1120 {
1121 char *rv = tal_strdup(ctx, "");
1122 if (failcode & BADONION) {
1123 tal_append_fmt(&rv, "BADONION|");
1124 failcode &= ~BADONION;
1125 }
1126 if (failcode & PERM) {
1127 tal_append_fmt(&rv, "PERM|");
1128 failcode &= ~PERM;
1129 }
1130 if (failcode & NODE) {
1131 tal_append_fmt(&rv, "NODE|");
1132 failcode &= ~NODE;
1133 }
1134 if (failcode & UPDATE) {
1135 tal_append_fmt(&rv, "UPDATE|");
1136 failcode &= ~UPDATE;
1137 }
1138 tal_append_fmt(&rv, "%u", failcode);
1139 return rv;
1140 }
1141
1142 static struct command_result *
handle_final_failure(struct command * cmd,struct payment * p,const struct node_id * final_id,enum onion_wire failcode)1143 handle_final_failure(struct command *cmd,
1144 struct payment *p,
1145 const struct node_id *final_id,
1146 enum onion_wire failcode)
1147 {
1148 u32 unused;
1149
1150 /* Need to check for blockheight disagreement case here,
1151 * otherwise we would set the abort flag too eagerly.
1152 */
1153 if (failure_is_blockheight_disagreement(p, &unused)) {
1154 paymod_log(p, LOG_DBG,
1155 "Blockheight disagreement, not aborting.");
1156 goto nonerror;
1157 }
1158
1159 paymod_log(p, LOG_DBG,
1160 "Final node %s reported %04x (%s) on route %s",
1161 type_to_string(tmpctx, struct node_id, final_id),
1162 failcode, onion_wire_name(failcode),
1163 p->routetxt);
1164
1165 /* We use an exhaustive switch statement here so you get a compile
1166 * warning when new ones are added, and can think about where they go */
1167 switch (failcode) {
1168 case WIRE_FINAL_INCORRECT_CLTV_EXPIRY:
1169 report_tampering(p, tal_count(p->route)-1, "cltv");
1170 goto error;
1171 case WIRE_FINAL_INCORRECT_HTLC_AMOUNT:
1172 report_tampering(p, tal_count(p->route)-1, "amount");
1173 goto error;
1174
1175 /* BOLT #4:
1176 *
1177 * A _forwarding node_ MAY, but a _final node_ MUST NOT:
1178 *...
1179 * - return an `invalid_onion_version` error.
1180 *...
1181 * - return an `invalid_onion_hmac` error.
1182 *...
1183 * - return an `invalid_onion_key` error.
1184 *...
1185 * - return a `temporary_channel_failure` error.
1186 *...
1187 * - return a `permanent_channel_failure` error.
1188 *...
1189 * - return a `required_channel_feature_missing` error.
1190 *...
1191 * - return an `unknown_next_peer` error.
1192 *...
1193 * - return an `amount_below_minimum` error.
1194 *...
1195 * - return a `fee_insufficient` error.
1196 *...
1197 * - return an `incorrect_cltv_expiry` error.
1198 *...
1199 * - return an `expiry_too_soon` error.
1200 *...
1201 * - return an `expiry_too_far` error.
1202 *...
1203 * - return a `channel_disabled` error.
1204 */
1205 case WIRE_INVALID_ONION_VERSION:
1206 case WIRE_INVALID_ONION_HMAC:
1207 case WIRE_INVALID_ONION_KEY:
1208 case WIRE_TEMPORARY_CHANNEL_FAILURE:
1209 case WIRE_PERMANENT_CHANNEL_FAILURE:
1210 case WIRE_REQUIRED_CHANNEL_FEATURE_MISSING:
1211 case WIRE_UNKNOWN_NEXT_PEER:
1212 case WIRE_AMOUNT_BELOW_MINIMUM:
1213 case WIRE_FEE_INSUFFICIENT:
1214 case WIRE_INCORRECT_CLTV_EXPIRY:
1215 case WIRE_EXPIRY_TOO_FAR:
1216 case WIRE_EXPIRY_TOO_SOON:
1217 case WIRE_CHANNEL_DISABLED:
1218 goto strange_error;
1219
1220 case WIRE_INVALID_ONION_PAYLOAD:
1221 case WIRE_INVALID_REALM:
1222 case WIRE_PERMANENT_NODE_FAILURE:
1223 case WIRE_TEMPORARY_NODE_FAILURE:
1224 case WIRE_REQUIRED_NODE_FEATURE_MISSING:
1225 #if EXPERIMENTAL_FEATURES
1226 case WIRE_INVALID_ONION_BLINDING:
1227 #endif
1228 case WIRE_INCORRECT_OR_UNKNOWN_PAYMENT_DETAILS:
1229 case WIRE_MPP_TIMEOUT:
1230 goto error;
1231 }
1232
1233 strange_error:
1234 paymod_log(p, LOG_UNUSUAL,
1235 "Final node %s reported strange error code %04x (%s)",
1236 type_to_string(tmpctx, struct node_id, final_id),
1237 failcode, describe_failcode(tmpctx, failcode));
1238
1239 error:
1240 p->result->code = PAY_DESTINATION_PERM_FAIL;
1241 payment_root(p)->abort = true;
1242
1243 nonerror:
1244 payment_fail(p, "%s", p->result->message);
1245 return command_still_pending(cmd);
1246
1247 }
1248
1249
1250 static struct command_result *
handle_intermediate_failure(struct command * cmd,struct payment * p,const struct node_id * errnode,const struct route_hop * errchan,enum onion_wire failcode)1251 handle_intermediate_failure(struct command *cmd,
1252 struct payment *p,
1253 const struct node_id *errnode,
1254 const struct route_hop *errchan,
1255 enum onion_wire failcode)
1256 {
1257 struct payment *root = payment_root(p);
1258
1259 paymod_log(p, LOG_DBG,
1260 "Intermediate node %s reported %04x (%s) at %s on route %s",
1261 type_to_string(tmpctx, struct node_id, errnode),
1262 failcode, onion_wire_name(failcode),
1263 type_to_string(tmpctx, struct short_channel_id,
1264 &errchan->scid),
1265 p->routetxt);
1266
1267 /* We use an exhaustive switch statement here so you get a compile
1268 * warning when new ones are added, and can think about where they go */
1269 switch (failcode) {
1270 /* BOLT #4:
1271 *
1272 * An _intermediate hop_ MUST NOT, but the _final node_:
1273 *...
1274 * - MUST return an `incorrect_or_unknown_payment_details` error.
1275 *...
1276 * - MUST return `final_incorrect_cltv_expiry` error.
1277 *...
1278 * - MUST return a `final_incorrect_htlc_amount` error.
1279 */
1280 case WIRE_INCORRECT_OR_UNKNOWN_PAYMENT_DETAILS:
1281 case WIRE_FINAL_INCORRECT_CLTV_EXPIRY:
1282 case WIRE_FINAL_INCORRECT_HTLC_AMOUNT:
1283 /* FIXME: Document in BOLT that intermediates must not return this! */
1284 case WIRE_MPP_TIMEOUT:
1285 goto strange_error;
1286
1287 case WIRE_PERMANENT_CHANNEL_FAILURE:
1288 case WIRE_CHANNEL_DISABLED:
1289 case WIRE_UNKNOWN_NEXT_PEER:
1290 case WIRE_REQUIRED_CHANNEL_FEATURE_MISSING:
1291 /* All of these result in the channel being marked as disabled. */
1292 channel_hints_update(root, errchan->scid,
1293 errchan->direction, false, false, NULL,
1294 NULL);
1295 break;
1296
1297 case WIRE_TEMPORARY_CHANNEL_FAILURE: {
1298 /* These are an indication that the capacity was insufficient,
1299 * remember the amount we tried as an estimate. */
1300 channel_hints_update(root, errchan->scid,
1301 errchan->direction, true, false,
1302 &errchan->amount, NULL);
1303 goto error;
1304 }
1305
1306 case WIRE_INCORRECT_CLTV_EXPIRY:
1307 report_tampering(p, errchan - p->route, "cltv");
1308 goto error;
1309
1310 case WIRE_INVALID_ONION_VERSION:
1311 case WIRE_INVALID_ONION_HMAC:
1312 case WIRE_INVALID_ONION_KEY:
1313 case WIRE_PERMANENT_NODE_FAILURE:
1314 case WIRE_TEMPORARY_NODE_FAILURE:
1315 case WIRE_REQUIRED_NODE_FEATURE_MISSING:
1316 case WIRE_INVALID_ONION_PAYLOAD:
1317 case WIRE_INVALID_REALM:
1318 #if EXPERIMENTAL_FEATURES
1319 case WIRE_INVALID_ONION_BLINDING:
1320 #endif
1321 tal_arr_expand(&root->excluded_nodes, *errnode);
1322 goto error;
1323
1324 case WIRE_AMOUNT_BELOW_MINIMUM:
1325 case WIRE_FEE_INSUFFICIENT:
1326 case WIRE_EXPIRY_TOO_FAR:
1327 case WIRE_EXPIRY_TOO_SOON:
1328 goto error;
1329 }
1330
1331 strange_error:
1332 paymod_log(p, LOG_UNUSUAL,
1333 "Intermediate node %s reported strange error code %04x (%s)",
1334 type_to_string(tmpctx, struct node_id, errnode),
1335 failcode, describe_failcode(tmpctx, failcode));
1336
1337 error:
1338 payment_fail(p, "%s", p->result->message);
1339 return command_still_pending(cmd);
1340 }
1341
1342 /* From the docs:
1343 *
1344 * - *erring_index*: The index of the node along the route that
1345 * reported the error. 0 for the local node, 1 for the first hop,
1346 * and so on.
1347 *
1348 * The only difficulty is mapping the erring_index to the correct hop.
1349 * We split into the erring node, and the error channel, since they're
1350 * used in different contexts. NULL error_channel means it's the final
1351 * node, whose errors are treated differently.
1352 */
assign_blame(const struct payment * p,const struct node_id ** errnode,const struct route_hop ** errchan)1353 static bool assign_blame(const struct payment *p,
1354 const struct node_id **errnode,
1355 const struct route_hop **errchan)
1356 {
1357 int index;
1358
1359 if (p->result->erring_index == NULL)
1360 return false;
1361
1362 index = *p->result->erring_index;
1363
1364 /* BADONION errors are reported on behalf of the next node. */
1365 if (p->result->failcode & BADONION)
1366 index++;
1367
1368 /* Final node *shouldn't* report BADONION, but don't assume. */
1369 if (index >= tal_count(p->route)) {
1370 *errchan = NULL;
1371 *errnode = &p->route[tal_count(p->route) - 1].node_id;
1372 return true;
1373 }
1374
1375 *errchan = &p->route[index];
1376 if (index == 0)
1377 *errnode = p->local_id;
1378 else
1379 *errnode = &p->route[index - 1].node_id;
1380 return true;
1381 }
1382
1383 /* Fix up the channel_update to include the type if it doesn't currently have
1384 * one. See ElementsProject/lightning#1730 and lightningnetwork/lnd#1599 for the
1385 * in-depth discussion on why we break message parsing here... */
patch_channel_update(const tal_t * ctx,u8 * channel_update TAKES)1386 static u8 *patch_channel_update(const tal_t *ctx, u8 *channel_update TAKES)
1387 {
1388 u8 *fixed;
1389 if (channel_update != NULL &&
1390 fromwire_peektype(channel_update) != WIRE_CHANNEL_UPDATE) {
1391 /* This should be a channel_update, prefix with the
1392 * WIRE_CHANNEL_UPDATE type, but isn't. Let's prefix it. */
1393 fixed = tal_arr(ctx, u8, 0);
1394 towire_u16(&fixed, WIRE_CHANNEL_UPDATE);
1395 towire(&fixed, channel_update, tal_bytelen(channel_update));
1396 if (taken(channel_update))
1397 tal_free(channel_update);
1398 return fixed;
1399 } else {
1400 return tal_dup_talarr(ctx, u8, channel_update);
1401 }
1402 }
1403
1404 /* Return NULL if the wrapped onion error message has no channel_update field,
1405 * or return the embedded channel_update message otherwise. */
channel_update_from_onion_error(const tal_t * ctx,const u8 * onion_message)1406 static u8 *channel_update_from_onion_error(const tal_t *ctx,
1407 const u8 *onion_message)
1408 {
1409 u8 *channel_update = NULL;
1410 struct amount_msat unused_msat;
1411 u32 unused32;
1412
1413 /* Identify failcodes that have some channel_update.
1414 *
1415 * TODO > BOLT 1.0: Add new failcodes when updating to a
1416 * new BOLT version. */
1417 if (!fromwire_temporary_channel_failure(ctx,
1418 onion_message,
1419 &channel_update) &&
1420 !fromwire_amount_below_minimum(ctx,
1421 onion_message, &unused_msat,
1422 &channel_update) &&
1423 !fromwire_fee_insufficient(ctx,
1424 onion_message, &unused_msat,
1425 &channel_update) &&
1426 !fromwire_incorrect_cltv_expiry(ctx,
1427 onion_message, &unused32,
1428 &channel_update) &&
1429 !fromwire_expiry_too_soon(ctx,
1430 onion_message,
1431 &channel_update))
1432 /* No channel update. */
1433 return NULL;
1434
1435 return patch_channel_update(ctx, take(channel_update));
1436 }
1437
1438
1439 static struct command_result *
payment_addgossip_success(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)1440 payment_addgossip_success(struct command *cmd, const char *buffer,
1441 const jsmntok_t *toks, struct payment *p)
1442 {
1443 const struct node_id *errnode;
1444 const struct route_hop *errchan;
1445
1446 if (!assign_blame(p, &errnode, &errchan)) {
1447 paymod_log(p, LOG_UNUSUAL,
1448 "No erring_index set in `waitsendpay` result: %.*s",
1449 json_tok_full_len(toks),
1450 json_tok_full(buffer, toks));
1451 /* FIXME: Pick a random channel to fail? */
1452 payment_set_step(p, PAYMENT_STEP_FAILED);
1453 payment_continue(p);
1454 return command_still_pending(cmd);
1455 }
1456
1457 if (!errchan)
1458 return handle_final_failure(cmd, p, errnode,
1459 p->result->failcode);
1460
1461 return handle_intermediate_failure(cmd, p, errnode, errchan,
1462 p->result->failcode);
1463 }
1464
1465 /* If someone gives us an invalid update, all we can do is log it */
1466 static struct command_result *
payment_addgossip_failure(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)1467 payment_addgossip_failure(struct command *cmd, const char *buffer,
1468 const jsmntok_t *toks, struct payment *p)
1469 {
1470 paymod_log(p, LOG_DBG, "Invalid channel_update: %.*s",
1471 json_tok_full_len(toks),
1472 json_tok_full(buffer, toks));
1473
1474 return payment_addgossip_success(cmd, NULL, NULL, p);
1475 }
1476
1477 static struct command_result *
payment_waitsendpay_finished(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)1478 payment_waitsendpay_finished(struct command *cmd, const char *buffer,
1479 const jsmntok_t *toks, struct payment *p)
1480 {
1481 u8 *update;
1482
1483 assert(p->route != NULL);
1484
1485 p->end_time = time_now();
1486 p->result = tal_sendpay_result_from_json(p, buffer, toks);
1487
1488 if (p->result == NULL) {
1489 paymod_log(p, LOG_UNUSUAL,
1490 "Unable to parse `waitsendpay` result: %.*s",
1491 json_tok_full_len(toks),
1492 json_tok_full(buffer, toks));
1493 payment_set_step(p, PAYMENT_STEP_FAILED);
1494 payment_continue(p);
1495 return command_still_pending(cmd);
1496 }
1497
1498 payment_result_infer(p->route, p->result);
1499
1500 if (p->result->state == PAYMENT_COMPLETE) {
1501 payment_set_step(p, PAYMENT_STEP_SUCCESS);
1502 payment_continue(p);
1503 return command_still_pending(cmd);
1504 }
1505
1506 payment_chanhints_apply_route(p, true);
1507
1508 /* Tell gossipd, if we received an update */
1509 update = channel_update_from_onion_error(tmpctx, p->result->raw_message);
1510 if (update) {
1511 struct out_req *req;
1512 paymod_log(p, LOG_DBG,
1513 "Extracted channel_update %s from onionreply %s",
1514 tal_hex(tmpctx, update),
1515 tal_hex(tmpctx, p->result->raw_message));
1516 req = jsonrpc_request_start(p->plugin, NULL, "addgossip",
1517 payment_addgossip_success,
1518 payment_addgossip_failure, p);
1519 json_add_hex_talarr(req->js, "message", update);
1520 send_outreq(p->plugin, req);
1521 return command_still_pending(cmd);
1522 }
1523
1524 return payment_addgossip_success(cmd, NULL, NULL, p);
1525 }
1526
payment_sendonion_success(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)1527 static struct command_result *payment_sendonion_success(struct command *cmd,
1528 const char *buffer,
1529 const jsmntok_t *toks,
1530 struct payment *p)
1531 {
1532 struct out_req *req;
1533 req = jsonrpc_request_start(p->plugin, NULL, "waitsendpay",
1534 payment_waitsendpay_finished,
1535 payment_waitsendpay_finished, p);
1536 json_add_sha256(req->js, "payment_hash", p->payment_hash);
1537 json_add_num(req->js, "partid", p->partid);
1538 json_add_u64(req->js, "groupid", p->groupid);
1539 send_outreq(p->plugin, req);
1540
1541 return command_still_pending(cmd);
1542 }
1543
payment_createonion_success(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)1544 static struct command_result *payment_createonion_success(struct command *cmd,
1545 const char *buffer,
1546 const jsmntok_t *toks,
1547 struct payment *p)
1548 {
1549 struct out_req *req;
1550 struct route_hop *first = &p->route[0];
1551 struct secret *secrets;
1552
1553 p->createonion_response = json_to_createonion_response(p, buffer, toks);
1554
1555 req = jsonrpc_request_start(p->plugin, NULL, "sendonion",
1556 payment_sendonion_success,
1557 payment_rpc_failure, p);
1558 json_add_hex_talarr(req->js, "onion", p->createonion_response->onion);
1559
1560 json_object_start(req->js, "first_hop");
1561 json_add_amount_msat_only(req->js, "amount_msat", first->amount);
1562 json_add_num(req->js, "delay", first->delay);
1563 json_add_node_id(req->js, "id", &first->node_id);
1564 json_object_end(req->js);
1565
1566 json_add_sha256(req->js, "payment_hash", p->payment_hash);
1567 json_add_amount_msat_only(req->js, "msatoshi", p->amount);
1568
1569 json_array_start(req->js, "shared_secrets");
1570 secrets = p->createonion_response->shared_secrets;
1571 for(size_t i=0; i<tal_count(secrets); i++)
1572 json_add_secret(req->js, NULL, &secrets[i]);
1573 json_array_end(req->js);
1574
1575 json_add_num(req->js, "partid", p->partid);
1576 json_add_u64(req->js, "groupid", p->groupid);
1577
1578 if (p->label)
1579 json_add_string(req->js, "label", p->label);
1580
1581 if (p->invstring)
1582 /* FIXME: rename parameter to invstring */
1583 json_add_string(req->js, "bolt11", p->invstring);
1584
1585 if (p->destination)
1586 json_add_node_id(req->js, "destination", p->destination);
1587
1588 if (p->local_offer_id)
1589 json_add_sha256(req->js, "localofferid", p->local_offer_id);
1590
1591 send_outreq(p->plugin, req);
1592 return command_still_pending(cmd);
1593 }
1594
1595 /* Temporary serialization method for the tlv_payload.data until we rework the
1596 * API that is generated from the specs to use the setter/getter interface. */
tlvstream_set_tlv_payload_data(struct tlv_field ** stream,struct secret * payment_secret,u64 total_msat)1597 static void tlvstream_set_tlv_payload_data(struct tlv_field **stream,
1598 struct secret *payment_secret,
1599 u64 total_msat)
1600 {
1601 u8 *ser = tal_arr(NULL, u8, 0);
1602 towire_secret(&ser, payment_secret);
1603 towire_tu64(&ser, total_msat);
1604 tlvstream_set_raw(stream, TLV_TLV_PAYLOAD_PAYMENT_DATA, ser, tal_bytelen(ser));
1605 tal_free(ser);
1606 }
1607
payment_add_hop_onion_payload(struct payment * p,struct createonion_hop * dst,struct route_hop * node,struct route_hop * next,bool final,bool force_tlv,struct secret * payment_secret)1608 static void payment_add_hop_onion_payload(struct payment *p,
1609 struct createonion_hop *dst,
1610 struct route_hop *node,
1611 struct route_hop *next,
1612 bool final,
1613 bool force_tlv,
1614 struct secret *payment_secret)
1615 {
1616 struct createonion_request *cr = p->createonion_request;
1617 u32 cltv = p->start_block + next->delay + 1;
1618 u64 msat = next->amount.millisatoshis; /* Raw: TLV payload generation*/
1619 struct tlv_field **fields;
1620 struct payment *root = payment_root(p);
1621 static struct short_channel_id all_zero_scid = {.u64 = 0};
1622
1623 /* This is the information of the node processing this payload, while
1624 * `next` are the instructions to include in the payload, which is
1625 * basically the channel going to the next node. */
1626 dst->style = node->style;
1627 if (force_tlv)
1628 dst->style = ROUTE_HOP_TLV;
1629 dst->pubkey = node->node_id;
1630
1631 switch (dst->style) {
1632 case ROUTE_HOP_LEGACY:
1633 dst->legacy_payload = tal(cr->hops, struct legacy_payload);
1634 dst->legacy_payload->forward_amt = next->amount;
1635
1636 if (!final)
1637 dst->legacy_payload->scid = next->scid;
1638 else
1639 dst->legacy_payload->scid = all_zero_scid;
1640
1641 dst->legacy_payload->outgoing_cltv = cltv;
1642 break;
1643 case ROUTE_HOP_TLV:
1644 dst->tlv_payload = tlv_tlv_payload_new(cr->hops);
1645 fields = &dst->tlv_payload->fields;
1646 tlvstream_set_tu64(fields, TLV_TLV_PAYLOAD_AMT_TO_FORWARD,
1647 msat);
1648 tlvstream_set_tu32(fields, TLV_TLV_PAYLOAD_OUTGOING_CLTV_VALUE,
1649 cltv);
1650
1651 if (!final)
1652 tlvstream_set_short_channel_id(fields,
1653 TLV_TLV_PAYLOAD_SHORT_CHANNEL_ID,
1654 &next->scid);
1655
1656 if (payment_secret != NULL) {
1657 assert(final);
1658 tlvstream_set_tlv_payload_data(
1659 fields, payment_secret,
1660 root->amount.millisatoshis); /* Raw: TLV payload generation*/
1661 }
1662 break;
1663 }
1664 }
1665
payment_compute_onion_payloads(struct payment * p)1666 static void payment_compute_onion_payloads(struct payment *p)
1667 {
1668 struct createonion_request *cr;
1669 size_t hopcount;
1670 struct payment *root = payment_root(p);
1671 char *routetxt = tal_strdup(tmpctx, "");
1672
1673 p->step = PAYMENT_STEP_ONION_PAYLOAD;
1674 hopcount = tal_count(p->route);
1675
1676 /* Now that we are about to fix the route parameters by
1677 * encoding them in an onion is the right time to update the
1678 * channel hints. */
1679 if (!payment_chanhints_apply_route(p, false)) {
1680 /* We can still end up with a failed channel_hints
1681 * update, either because a plugin changed the route,
1682 * or because a modifier was not synchronous, allowing
1683 * for multiple concurrent routes being built. If that
1684 * is the case, discard this route and retry. */
1685 payment_set_step(p, PAYMENT_STEP_RETRY_GETROUTE);
1686 return payment_continue(p);
1687 }
1688
1689 /* Now compute the payload we're about to pass to `createonion` */
1690 cr = p->createonion_request = tal(p, struct createonion_request);
1691 cr->assocdata = tal_arr(cr, u8, 0);
1692 towire_sha256(&cr->assocdata, p->payment_hash);
1693 cr->session_key = NULL;
1694 cr->hops = tal_arr(cr, struct createonion_hop, tal_count(p->route));
1695
1696 /* Non-final hops */
1697 for (size_t i = 0; i < hopcount - 1; i++) {
1698 /* The message is destined for hop i, but contains fields for
1699 * i+1 */
1700 payment_add_hop_onion_payload(p, &cr->hops[i], &p->route[i],
1701 &p->route[i + 1], false, false,
1702 NULL);
1703 tal_append_fmt(&routetxt, "%s -> ",
1704 type_to_string(tmpctx, struct short_channel_id,
1705 &p->route[i].scid));
1706 }
1707
1708 /* Final hop */
1709 payment_add_hop_onion_payload(
1710 p, &cr->hops[hopcount - 1], &p->route[hopcount - 1],
1711 &p->route[hopcount - 1], true, root->destination_has_tlv,
1712 root->payment_secret);
1713 tal_append_fmt(&routetxt, "%s",
1714 type_to_string(tmpctx, struct short_channel_id,
1715 &p->route[hopcount - 1].scid));
1716
1717 paymod_log(p, LOG_DBG,
1718 "Created outgoing onion for route: %s", routetxt);
1719
1720 p->routetxt = tal_steal(p, routetxt);
1721
1722 /* Now allow all the modifiers to mess with the payloads, before we
1723 * serialize via a call to createonion in the next step. */
1724 payment_continue(p);
1725 }
1726
payment_sendonion(struct payment * p)1727 static void payment_sendonion(struct payment *p)
1728 {
1729 struct out_req *req;
1730 u8 *payload, *tlv;
1731 req = jsonrpc_request_start(p->plugin, NULL, "createonion",
1732 payment_createonion_success,
1733 payment_rpc_failure, p);
1734
1735 json_array_start(req->js, "hops");
1736 for (size_t i = 0; i < tal_count(p->createonion_request->hops); i++) {
1737 json_object_start(req->js, NULL);
1738 struct createonion_hop *hop = &p->createonion_request->hops[i];
1739 json_add_node_id(req->js, "pubkey", &hop->pubkey);
1740 if (hop->style == ROUTE_HOP_LEGACY) {
1741 payload = tal_towire_legacy_payload(tmpctx, hop->legacy_payload);
1742 json_add_hex_talarr(req->js, "payload", payload);
1743 }else {
1744 tlv = tal_arr(tmpctx, u8, 0);
1745 towire_tlvstream_raw(&tlv, hop->tlv_payload->fields);
1746 payload = tal_arr(tmpctx, u8, 0);
1747 towire_bigsize(&payload, tal_bytelen(tlv));
1748 towire(&payload, tlv, tal_bytelen(tlv));
1749 json_add_hex_talarr(req->js, "payload", payload);
1750 tal_free(tlv);
1751 }
1752 tal_free(payload);
1753 json_object_end(req->js);
1754 }
1755 json_array_end(req->js);
1756
1757 json_add_hex_talarr(req->js, "assocdata",
1758 p->createonion_request->assocdata);
1759
1760 if (p->createonion_request->session_key)
1761 json_add_secret(req->js, "sessionkey",
1762 p->createonion_request->session_key);
1763
1764 send_outreq(p->plugin, req);
1765 }
1766
1767 /* Mutual recursion. */
1768 static void payment_finished(struct payment *p);
1769
1770 /* A payment is finished if a) it is in a final state, of b) it's in a
1771 * child-spawning state and all of its children are in a final state. */
payment_is_finished(const struct payment * p)1772 static bool payment_is_finished(const struct payment *p)
1773 {
1774 top:
1775 if (p->step == PAYMENT_STEP_FAILED || p->step == PAYMENT_STEP_SUCCESS || p->abort)
1776 return true;
1777 else if (p->step == PAYMENT_STEP_SPLIT || p->step == PAYMENT_STEP_RETRY) {
1778 size_t num_children = tal_count(p->children);
1779
1780 /* Retry case will almost always have just one child, so avoid
1781 * the overhead of pushing and popping off the C stack and
1782 * tail-recurse manually. */
1783 if (num_children == 1) {
1784 p = p->children[0];
1785 goto top;
1786 }
1787
1788 for (size_t i = 0; i < num_children; i++)
1789 /* In other words: if any child is unfinished,
1790 * we are unfinished. */
1791 if (!payment_is_finished(p->children[i]))
1792 return false;
1793 return true;
1794 } else {
1795 return false;
1796 }
1797 }
1798
payment_aggregate_states(struct payment * p)1799 static enum payment_step payment_aggregate_states(struct payment *p)
1800 {
1801 enum payment_step agg = p->step;
1802
1803 for (size_t i=0; i<tal_count(p->children); i++)
1804 agg |= payment_aggregate_states(p->children[i]);
1805
1806 return agg;
1807 }
1808
1809 /* A payment is finished if a) it is in a final state, of b) it's in a
1810 * child-spawning state and all of its children are in a final state. */
payment_is_success(struct payment * p)1811 static bool payment_is_success(struct payment *p)
1812 {
1813 return (payment_aggregate_states(p) & PAYMENT_STEP_SUCCESS) != 0;
1814 }
1815
1816 /* Function to bubble up completions to the root, which actually holds on to
1817 * the command that initiated the flow. */
payment_child_finished(struct payment * p,struct payment * child)1818 static void payment_child_finished(struct payment *p,
1819 struct payment *child)
1820 {
1821 if (!payment_is_finished(p))
1822 return;
1823
1824 /* Should we continue bubbling up? */
1825 payment_finished(p);
1826 }
1827
payment_add_attempt(struct json_stream * s,const char * fieldname,struct payment * p,bool recurse)1828 static void payment_add_attempt(struct json_stream *s, const char *fieldname, struct payment *p, bool recurse)
1829 {
1830 bool finished = p->step >= PAYMENT_STEP_RETRY,
1831 success = p->step == PAYMENT_STEP_SUCCESS;
1832
1833 /* A fieldname is only reasonable if we're not recursing. Otherwise the
1834 * fieldname would be reused for all attempts. */
1835 assert(!recurse || fieldname == NULL);
1836
1837 json_object_start(s, fieldname);
1838
1839 if (!finished)
1840 json_add_string(s, "status", "pending");
1841 else if (success)
1842 json_add_string(s, "status", "success");
1843 else
1844 json_add_string(s, "status", "failed");
1845
1846 if (p->failreason != NULL)
1847 json_add_string(s, "failreason", p->failreason);
1848
1849 json_add_u64(s, "partid", p->partid);
1850 json_add_amount_msat_only(s, "amount", p->amount);
1851 if (p->parent != NULL)
1852 json_add_u64(s, "parent_partid", p->parent->partid);
1853
1854 json_object_end(s);
1855 for (size_t i=0; i<tal_count(p->children); i++) {
1856 payment_add_attempt(s, fieldname, p->children[i], recurse);
1857 }
1858 }
1859
payment_json_add_attempts(struct json_stream * s,const char * fieldname,struct payment * p)1860 static void payment_json_add_attempts(struct json_stream *s,
1861 const char *fieldname, struct payment *p)
1862 {
1863 assert(p == payment_root(p));
1864 json_array_start(s, fieldname);
1865 payment_add_attempt(s, NULL, p, true);
1866 json_array_end(s);
1867 }
1868
payment_notify_failure(struct payment * p,const char * error_message)1869 static void payment_notify_failure(struct payment *p, const char *error_message)
1870 {
1871 struct payment *root = payment_root(p);
1872 struct json_stream *n;
1873
1874 n = plugin_notification_start(p->plugin, "pay_failure");
1875 json_add_sha256(n, "payment_hash", p->payment_hash);
1876 if (root->invstring != NULL)
1877 json_add_string(n, "bolt11", root->invstring);
1878
1879 json_object_start(n, "error");
1880 json_add_string(n, "message", error_message);
1881 json_object_end(n); /* .error */
1882
1883 plugin_notification_end(p->plugin, n);
1884 }
1885
1886 /* This function is called whenever a payment ends up in a final state, or all
1887 * leafs in the subtree rooted in the payment are all in a final state. It is
1888 * called only once, and it is guaranteed to be called in post-order
1889 * traversal, i.e., all children are finished before the parent is called. */
payment_finished(struct payment * p)1890 static void payment_finished(struct payment *p)
1891 {
1892 struct payment_tree_result result = payment_collect_result(p);
1893 struct json_stream *ret;
1894 struct command *cmd = p->cmd;
1895 const char *msg;
1896 struct json_stream *n;
1897 struct payment *root = payment_root(p);
1898
1899 /* Either none of the leaf attempts succeeded yet, or we have a
1900 * preimage. */
1901 assert((result.leafstates & PAYMENT_STEP_SUCCESS) == 0 ||
1902 result.preimage != NULL);
1903
1904 if (p->parent == NULL) {
1905 /* We are about to reply, unset the pointer to the cmd so we
1906 * don't attempt to return a response twice. */
1907 p->cmd = NULL;
1908 if (cmd == NULL) {
1909 /* This is the tree root, but we already reported
1910 * success or failure, so noop. */
1911 return;
1912 } else if (payment_is_success(p)) {
1913 assert(result.treestates & PAYMENT_STEP_SUCCESS);
1914 assert(result.leafstates & PAYMENT_STEP_SUCCESS);
1915 assert(result.preimage != NULL);
1916
1917 /* Call any callback we might have registered. */
1918 if (p->on_payment_success != NULL)
1919 p->on_payment_success(p);
1920
1921 ret = jsonrpc_stream_success(cmd);
1922 json_add_node_id(ret, "destination", p->destination);
1923 json_add_sha256(ret, "payment_hash", p->payment_hash);
1924 json_add_timeabs(ret, "created_at", p->start_time);
1925 json_add_num(ret, "parts", result.attempts);
1926
1927 json_add_amount_msat_compat(ret, p->amount, "msatoshi",
1928 "amount_msat");
1929 json_add_amount_msat_compat(ret, result.sent,
1930 "msatoshi_sent",
1931 "amount_sent_msat");
1932
1933 if (result.leafstates != PAYMENT_STEP_SUCCESS)
1934 json_add_string(
1935 ret, "warning_partial_completion",
1936 "Some parts of the payment are not yet "
1937 "completed, but we have the confirmation "
1938 "from the recipient.");
1939 json_add_preimage(ret, "payment_preimage", result.preimage);
1940
1941 json_add_string(ret, "status", "complete");
1942
1943 n = plugin_notification_start(p->plugin, "pay_success");
1944 json_add_sha256(n, "payment_hash", p->payment_hash);
1945 if (root->invstring != NULL)
1946 json_add_string(n, "bolt11", root->invstring);
1947 plugin_notification_end(p->plugin, n);
1948
1949 if (command_finished(cmd, ret)) {/* Ignore result. */}
1950 p->cmd = NULL;
1951 return;
1952 } else if (p->aborterror != NULL) {
1953 /* We set an explicit toplevel error message,
1954 * so let's report that. */
1955 ret = jsonrpc_stream_fail(cmd, PAY_STOPPED_RETRYING,
1956 p->aborterror);
1957 payment_json_add_attempts(ret, "attempts", p);
1958
1959 payment_notify_failure(p, p->aborterror);
1960
1961 if (command_finished(cmd, ret)) {/* Ignore result. */}
1962 p->cmd = NULL;
1963 return;
1964 } else if (result.failure == NULL || result.failure->failcode < NODE) {
1965 if (p->on_payment_failure != NULL)
1966 p->on_payment_failure(p);
1967
1968 /* This is failing because we have no more routes to try */
1969 msg = tal_fmt(cmd,
1970 "Ran out of routes to try after "
1971 "%d attempt%s: see `paystatus`",
1972 result.attempts,
1973 result.attempts == 1 ? "" : "s");
1974 ret = jsonrpc_stream_fail(cmd, PAY_STOPPED_RETRYING,
1975 msg);
1976 payment_json_add_attempts(ret, "attempts", p);
1977
1978 payment_notify_failure(p, msg);
1979
1980 if (command_finished(cmd, ret)) {/* Ignore result. */}
1981 p->cmd = NULL;
1982 return;
1983
1984 } else {
1985 struct payment_result *failure = result.failure;
1986 assert(failure!= NULL);
1987 if (p->on_payment_failure != NULL)
1988 p->on_payment_failure(p);
1989 ret = jsonrpc_stream_fail(cmd, failure->code,
1990 failure->message);
1991
1992 json_add_u64(ret, "id", failure->id);
1993
1994 json_add_u32(ret, "failcode", failure->failcode);
1995 json_add_string(ret, "failcodename",
1996 failure->failcodename);
1997
1998 if (p->invstring)
1999 json_add_invstring(ret, p->invstring);
2000
2001 json_add_hex_talarr(ret, "raw_message",
2002 result.failure->raw_message);
2003 json_add_num(ret, "created_at", p->start_time.ts.tv_sec);
2004 json_add_node_id(ret, "destination", p->destination);
2005 json_add_sha256(ret, "payment_hash", p->payment_hash);
2006
2007 if (result.leafstates & PAYMENT_STEP_SUCCESS) {
2008 /* If one sub-payment succeeded then we have
2009 * proof of payment, and the payment is a
2010 * success. */
2011 json_add_string(ret, "status", "complete");
2012
2013 } else if (result.leafstates & ~PAYMENT_STEP_FAILED) {
2014 /* If there are non-failed leafs we are still trying. */
2015 json_add_string(ret, "status", "pending");
2016
2017 } else {
2018 json_add_string(ret, "status", "failed");
2019 }
2020
2021 json_add_amount_msat_compat(ret, p->amount, "msatoshi",
2022 "amount_msat");
2023
2024 json_add_amount_msat_compat(ret, result.sent,
2025 "msatoshi_sent",
2026 "amount_sent_msat");
2027
2028 if (failure != NULL) {
2029 if (failure->erring_index)
2030 json_add_num(ret, "erring_index",
2031 *failure->erring_index);
2032
2033 if (failure->erring_node)
2034 json_add_node_id(ret, "erring_node",
2035 failure->erring_node);
2036
2037 if (failure->erring_channel)
2038 json_add_short_channel_id(
2039 ret, "erring_channel",
2040 failure->erring_channel);
2041
2042 if (failure->erring_direction)
2043 json_add_num(
2044 ret, "erring_direction",
2045 *failure->erring_direction);
2046 }
2047
2048 payment_notify_failure(p, failure->message);
2049
2050 if (command_finished(cmd, ret)) { /* Ignore result. */}
2051 p->cmd = NULL;
2052 return;
2053 }
2054 } else {
2055 payment_child_finished(p->parent, p);
2056 return;
2057 }
2058 }
2059
payment_set_step(struct payment * p,enum payment_step newstep)2060 void payment_set_step(struct payment *p, enum payment_step newstep)
2061 {
2062 p->current_modifier = -1;
2063 p->step = newstep;
2064
2065 /* Any final state needs an end_time */
2066 if (p->step >= PAYMENT_STEP_SPLIT)
2067 p->end_time = time_now();
2068 }
2069
payment_continue(struct payment * p)2070 void payment_continue(struct payment *p)
2071 {
2072 struct payment_modifier *mod;
2073 void *moddata;
2074 /* If we are in the middle of calling the modifiers, continue calling
2075 * them, otherwise we can continue with the payment state-machine. */
2076 p->current_modifier++;
2077 mod = p->modifiers[p->current_modifier];
2078
2079 if (mod != NULL) {
2080 /* There is another modifier, so call it. */
2081 moddata = p->modifier_data[p->current_modifier];
2082 return mod->post_step_cb(moddata, p);
2083 } else {
2084 /* There are no more modifiers, so reset the call chain and
2085 * proceed to the next state. */
2086 p->current_modifier = -1;
2087 switch (p->step) {
2088 case PAYMENT_STEP_INITIALIZED:
2089 case PAYMENT_STEP_RETRY_GETROUTE:
2090 payment_getroute(p);
2091 return;
2092
2093 case PAYMENT_STEP_GOT_ROUTE:
2094 payment_compute_onion_payloads(p);
2095 return;
2096
2097 case PAYMENT_STEP_ONION_PAYLOAD:
2098 payment_sendonion(p);
2099 return;
2100
2101 case PAYMENT_STEP_SUCCESS:
2102 case PAYMENT_STEP_FAILED:
2103 payment_finished(p);
2104 return;
2105
2106 case PAYMENT_STEP_RETRY:
2107 case PAYMENT_STEP_SPLIT:
2108 /* Do nothing, we'll get pinged by a child succeeding
2109 * or failing. */
2110 return;
2111 }
2112 }
2113 /* We should never get here, it'd mean one of the state machine called
2114 * `payment_continue` after the final state. */
2115 abort();
2116 }
2117
payment_abort(struct payment * p,const char * fmt,...)2118 void payment_abort(struct payment *p, const char *fmt, ...) {
2119 va_list ap;
2120 struct payment *root = payment_root(p);
2121 payment_set_step(p, PAYMENT_STEP_FAILED);
2122 p->end_time = time_now();
2123
2124 va_start(ap, fmt);
2125 p->failreason = tal_vfmt(p, fmt, ap);
2126 va_end(ap);
2127
2128 root->abort = true;
2129
2130 /* Only set the abort error if it's not yet set, otherwise we
2131 * might end up clobbering the earliest and decisive failure
2132 * with less relevant ones. */
2133 if (root->aborterror == NULL)
2134 root->aborterror = tal_dup_talarr(root, char, p->failreason);
2135
2136 paymod_log(p, LOG_INFORM, "%s", p->failreason);
2137
2138 /* Do not use payment_continue, because that'd continue
2139 * applying the modifiers before calling
2140 * payment_finished(). */
2141 payment_finished(p);
2142 }
2143
payment_fail(struct payment * p,const char * fmt,...)2144 void payment_fail(struct payment *p, const char *fmt, ...)
2145 {
2146 va_list ap;
2147 p->end_time = time_now();
2148 payment_set_step(p, PAYMENT_STEP_FAILED);
2149 va_start(ap, fmt);
2150 p->failreason = tal_vfmt(p, fmt, ap);
2151 va_end(ap);
2152
2153 paymod_log(p, LOG_INFORM, "%s", p->failreason);
2154
2155 payment_continue(p);
2156 }
2157
payment_mod_get_data(const struct payment * p,const struct payment_modifier * mod)2158 void *payment_mod_get_data(const struct payment *p,
2159 const struct payment_modifier *mod)
2160 {
2161 for (size_t i = 0; p->modifiers[i] != NULL; i++)
2162 if (p->modifiers[i] == mod)
2163 return p->modifier_data[i];
2164
2165 /* If we ever get here it means that we asked for the data for a
2166 * non-existent modifier. This is a compile-time/wiring issue, so we
2167 * better check that modifiers match the data we ask for. */
2168 abort();
2169 }
2170
2171 static struct retry_mod_data *retry_data_init(struct payment *p);
2172
2173 static inline void retry_step_cb(struct retry_mod_data *rd,
2174 struct payment *p);
2175
2176 static struct retry_mod_data *
retry_data_init(struct payment * p)2177 retry_data_init(struct payment *p)
2178 {
2179 struct retry_mod_data *rdata = tal(p, struct retry_mod_data);
2180 struct retry_mod_data *parent_rdata;
2181
2182 /* We start the retry counter from scratch for the root payment, or if
2183 * the parent was split, meaning this is a new attempt with new
2184 * amounts. */
2185 if (p->parent == NULL || p->parent->step == PAYMENT_STEP_SPLIT) {
2186 rdata->retries = 10;
2187 } else {
2188 parent_rdata = payment_mod_retry_get_data(p->parent);
2189 rdata->retries = parent_rdata->retries - 1;
2190 }
2191 return rdata;
2192 }
2193
2194 /* Determine whether retrying could possibly succeed. Retrying in this case
2195 * means that we repeat the entire flow, including computing a new route, new
2196 * payload and a new sendonion call. It does not mean we retry the exact same
2197 * attempt that just failed. */
payment_can_retry(struct payment * p)2198 static bool payment_can_retry(struct payment *p)
2199 {
2200 struct payment_result *res = p->result;
2201 u32 idx;
2202 bool is_final;
2203
2204 if (p->result == NULL)
2205 return p->failroute_retry;
2206
2207 idx = res->erring_index != NULL ? *res->erring_index : 0;
2208 is_final = (idx == tal_count(p->route));
2209
2210 /* Full matrix of failure code x is_final. Prefer to retry once too
2211 * often over eagerly failing. */
2212 switch (res->failcode) {
2213 case WIRE_EXPIRY_TOO_FAR:
2214 case WIRE_INCORRECT_OR_UNKNOWN_PAYMENT_DETAILS:
2215 case WIRE_INVALID_ONION_PAYLOAD:
2216 case WIRE_INVALID_ONION_VERSION:
2217 case WIRE_INVALID_REALM:
2218 case WIRE_MPP_TIMEOUT:
2219 case WIRE_PERMANENT_NODE_FAILURE:
2220 case WIRE_REQUIRED_NODE_FEATURE_MISSING:
2221 case WIRE_TEMPORARY_NODE_FAILURE:
2222 case WIRE_UNKNOWN_NEXT_PEER:
2223 return !is_final;
2224
2225 case WIRE_AMOUNT_BELOW_MINIMUM:
2226 case WIRE_CHANNEL_DISABLED:
2227 case WIRE_EXPIRY_TOO_SOON:
2228 case WIRE_FEE_INSUFFICIENT:
2229 case WIRE_FINAL_INCORRECT_CLTV_EXPIRY:
2230 case WIRE_FINAL_INCORRECT_HTLC_AMOUNT:
2231 case WIRE_INCORRECT_CLTV_EXPIRY:
2232 case WIRE_INVALID_ONION_HMAC:
2233 case WIRE_INVALID_ONION_KEY:
2234 case WIRE_PERMANENT_CHANNEL_FAILURE:
2235 case WIRE_REQUIRED_CHANNEL_FEATURE_MISSING:
2236 case WIRE_TEMPORARY_CHANNEL_FAILURE:
2237 #if EXPERIMENTAL_FEATURES
2238 case WIRE_INVALID_ONION_BLINDING:
2239 #endif
2240 return true;
2241 }
2242
2243 /* We should never get here, otherwise the above `switch` isn't
2244 * exhaustive. Nevertheless the failcode is provided by the erring
2245 * node, so retry anyway. `abort()`ing on externally supplied info is
2246 * not a good idea. */
2247 return true;
2248 }
2249
retry_step_cb(struct retry_mod_data * rd,struct payment * p)2250 static inline void retry_step_cb(struct retry_mod_data *rd,
2251 struct payment *p)
2252 {
2253 struct payment *subpayment, *root = payment_root(p);
2254 struct retry_mod_data *rdata = payment_mod_retry_get_data(p);
2255 struct timeabs now = time_now();
2256
2257 if (p->step != PAYMENT_STEP_FAILED)
2258 return payment_continue(p);
2259
2260 if (time_after(now, p->deadline)) {
2261 paymod_log(
2262 p, LOG_INFORM,
2263 "Payment deadline expired, not retrying (partial-)payment "
2264 "%s/%d",
2265 type_to_string(tmpctx, struct sha256, p->payment_hash),
2266 p->partid);
2267 root->abort = true;
2268 return payment_continue(p);
2269 }
2270
2271 /* If we failed to find a route, it's unlikely we can suddenly find a
2272 * new one without any other changes, so it's time to give up. */
2273 if (p->route == NULL && !p->failroute_retry)
2274 return payment_continue(p);
2275
2276 /* If the root is marked as abort, we do not retry anymore */
2277 if (payment_root(p)->abort)
2278 return payment_continue(p);
2279
2280 if (!payment_can_retry(p))
2281 return payment_continue(p);
2282
2283 /* If the failure was not final, and we tried a route, try again. */
2284 if (rdata->retries > 0) {
2285 payment_set_step(p, PAYMENT_STEP_RETRY);
2286 subpayment = payment_new(p, NULL, p, p->modifiers);
2287 payment_start(subpayment);
2288 subpayment->why =
2289 tal_fmt(subpayment, "Still have %d attempts left",
2290 rdata->retries - 1);
2291 paymod_log(
2292 p, LOG_DBG,
2293 "Retrying %s/%d (%s), new partid %d. %d attempts left\n",
2294 type_to_string(tmpctx, struct sha256, p->payment_hash),
2295 p->partid,
2296 type_to_string(tmpctx, struct amount_msat, &p->amount),
2297 subpayment->partid,
2298 rdata->retries - 1);
2299 }
2300
2301 payment_continue(p);
2302 }
2303
2304 REGISTER_PAYMENT_MODIFIER(retry, struct retry_mod_data *, retry_data_init,
2305 retry_step_cb);
2306
2307 static struct command_result *
local_channel_hints_listpeers(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)2308 local_channel_hints_listpeers(struct command *cmd, const char *buffer,
2309 const jsmntok_t *toks, struct payment *p)
2310 {
2311 const jsmntok_t *peers, *peer, *channels, *channel, *spendsats, *scid,
2312 *dir, *connected, *max_htlc, *htlcs;
2313 size_t i, j;
2314 peers = json_get_member(buffer, toks, "peers");
2315
2316 if (peers == NULL)
2317 goto done;
2318 /* cppcheck-suppress uninitvar - cppcheck can't undestand these macros. */
2319 json_for_each_arr(i, peer, peers) {
2320 channels = json_get_member(buffer, peer, "channels");
2321 if (channels == NULL)
2322 continue;
2323
2324 connected = json_get_member(buffer, peer, "connected");
2325
2326 json_for_each_arr(j, channel, channels) {
2327 struct channel_hint h;
2328 spendsats = json_get_member(buffer, channel, "spendable_msat");
2329 scid = json_get_member(buffer, channel, "short_channel_id");
2330 dir = json_get_member(buffer, channel, "direction");
2331 max_htlc = json_get_member(buffer, channel, "max_accepted_htlcs");
2332 htlcs = json_get_member(buffer, channel, "htlcs");
2333 if (spendsats == NULL || scid == NULL || dir == NULL ||
2334 max_htlc == NULL ||
2335 max_htlc->type != JSMN_PRIMITIVE || htlcs == NULL ||
2336 htlcs->type != JSMN_ARRAY)
2337 continue;
2338
2339 json_to_bool(buffer, connected, &h.enabled);
2340 json_to_short_channel_id(buffer, scid, &h.scid.scid);
2341 json_to_int(buffer, dir, &h.scid.dir);
2342
2343 json_to_msat(buffer, spendsats, &h.estimated_capacity);
2344
2345 /* Take the configured number of max_htlcs and
2346 * subtract any HTLCs that might already be added to
2347 * the channel. This is a best effort estimate and
2348 * mostly considers stuck htlcs, concurrent payments
2349 * may throw us off a bit. */
2350 json_to_u16(buffer, max_htlc, &h.htlc_budget);
2351 h.htlc_budget -= htlcs->size;
2352 h.local = true;
2353
2354 channel_hints_update(p, h.scid.scid, h.scid.dir,
2355 h.enabled, true, &h.estimated_capacity, &h.htlc_budget);
2356 }
2357 }
2358
2359 done:
2360 payment_continue(p);
2361 return command_still_pending(cmd);
2362 }
2363
local_channel_hints_cb(void * d UNUSED,struct payment * p)2364 static void local_channel_hints_cb(void *d UNUSED, struct payment *p)
2365 {
2366 struct out_req *req;
2367 /* If we are not the root we don't look up the channel balances since
2368 * it is unlikely that the capacities have changed much since the root
2369 * payment looked at them. We also only call `listpeers` when the
2370 * payment is in state PAYMENT_STEP_INITIALIZED, right before calling
2371 * `getroute`. */
2372 if (p->parent != NULL || p->step != PAYMENT_STEP_INITIALIZED)
2373 return payment_continue(p);
2374
2375 req = jsonrpc_request_start(p->plugin, NULL, "listpeers",
2376 local_channel_hints_listpeers,
2377 local_channel_hints_listpeers, p);
2378 send_outreq(p->plugin, req);
2379 }
2380
2381 REGISTER_PAYMENT_MODIFIER(local_channel_hints, void *, NULL, local_channel_hints_cb);
2382
2383 /* Trim route to this length by taking from the *front* of route
2384 * (end points to destination, so we need that bit!) */
trim_route(struct route_info ** route,size_t n)2385 static void trim_route(struct route_info **route, size_t n)
2386 {
2387 size_t remove = tal_count(*route) - n;
2388 memmove(*route, *route + remove, sizeof(**route) * n);
2389 tal_resize(route, n);
2390 }
2391
2392 /* Make sure routehints are reasonable length, and (since we assume we
2393 * can append), not directly to us. Note: untrusted data! */
filter_routehints(struct gossmap * map,struct payment * p,struct routehints_data * d,struct node_id * myid,struct route_info ** hints)2394 static struct route_info **filter_routehints(struct gossmap *map,
2395 struct payment *p,
2396 struct routehints_data *d,
2397 struct node_id *myid,
2398 struct route_info **hints)
2399 {
2400 const size_t max_hops = ROUTING_MAX_HOPS / 2;
2401 char *mods = tal_strdup(tmpctx, "");
2402 struct gossmap_node *src = gossmap_find_node(map, p->local_id);
2403
2404 if (src == NULL) {
2405 tal_append_fmt(&mods,
2406 "Could not locate ourselves in the gossip map, "
2407 "leaving routehints untouched. ");
2408 }
2409
2410 for (size_t i = 0; i < tal_count(hints) && src != NULL; i++) {
2411 struct gossmap_node *entrynode;
2412 u32 distance;
2413
2414 /* Trim any routehint > 10 hops */
2415 if (tal_count(hints[i]) > max_hops) {
2416 tal_append_fmt(&mods,
2417 "Trimmed routehint %zu (%zu hops) to %zu. ",
2418 i, tal_count(hints[i]), max_hops);
2419 trim_route(&hints[i], max_hops);
2420 }
2421
2422 /* If we are first hop, trim. */
2423 if (tal_count(hints[i]) > 0
2424 && node_id_eq(&hints[i][0].pubkey, myid)) {
2425 tal_append_fmt(&mods,
2426 "Removed ourselves from routehint %zu. ",
2427 i);
2428 trim_route(&hints[i], tal_count(hints[i])-1);
2429 }
2430
2431 /* If route is empty, remove altogether. */
2432 if (tal_count(hints[i]) == 0) {
2433 tal_append_fmt(&mods,
2434 "Removed empty routehint %zu. ", i);
2435 tal_arr_remove(&hints, i);
2436 i--;
2437 continue;
2438 }
2439
2440 /* If routehint entrypoint is unreachable there's no
2441 * point in keeping it. */
2442 entrynode = gossmap_find_node(map, &hints[i][0].pubkey);
2443 if (entrynode == NULL) {
2444 tal_append_fmt(&mods,
2445 "Removed routehint %zu because "
2446 "entrypoint %s is unknown. ",
2447 i,
2448 type_to_string(tmpctx, struct node_id,
2449 &hints[i][0].pubkey));
2450 plugin_log(p->plugin, LOG_DBG,
2451 "Removed routehint %zu because "
2452 "entrypoint %s is unknown. ",
2453 i,
2454 type_to_string(tmpctx, struct node_id,
2455 &hints[i][0].pubkey));
2456 tal_arr_remove(&hints, i);
2457 i--;
2458 continue;
2459 }
2460
2461 distance = dijkstra_distance(
2462 dijkstra(tmpctx, map, entrynode, AMOUNT_MSAT(1), 1,
2463 payment_route_can_carry_even_disabled,
2464 route_score_cheaper, p),
2465 gossmap_node_idx(map, src));
2466
2467 if (distance == UINT_MAX) {
2468 tal_append_fmt(&mods,
2469 "Removed routehint %zu because "
2470 "entrypoint %s is unreachable. ",
2471 i,
2472 type_to_string(tmpctx, struct node_id,
2473 &hints[i][0].pubkey));
2474 plugin_log(p->plugin, LOG_DBG,
2475 "Removed routehint %zu because "
2476 "entrypoint %s is unreachable. ",
2477 i,
2478 type_to_string(tmpctx, struct node_id,
2479 &hints[i][0].pubkey));
2480 tal_arr_remove(&hints, i);
2481 i--;
2482 }
2483 }
2484
2485 if (!streq(mods, ""))
2486 d->routehint_modifications = tal_steal(d, mods);
2487
2488 return tal_steal(d, hints);
2489 }
2490
2491 static bool route_msatoshi(struct amount_msat *total,
2492 const struct amount_msat msat,
2493 const struct route_info *route, size_t num_route);
2494
routehint_excluded(struct payment * p,const struct route_info * routehint)2495 static bool routehint_excluded(struct payment *p,
2496 const struct route_info *routehint)
2497 {
2498 const struct node_id *nodes = payment_get_excluded_nodes(tmpctx, p);
2499 const struct short_channel_id_dir *chans =
2500 payment_get_excluded_channels(tmpctx, p);
2501 const struct channel_hint *hints = payment_root(p)->channel_hints;
2502
2503 /* Note that we ignore direction here: in theory, we could have
2504 * found that one direction of a channel is unavailable, but they
2505 * are suggesting we use it the other way. Very unlikely though! */
2506 for (size_t i = 0; i < tal_count(routehint); i++) {
2507 const struct route_info *r = &routehint[i];
2508 for (size_t j = 0; j < tal_count(nodes); j++)
2509 if (node_id_eq(&r->pubkey, &nodes[j]))
2510 return true;
2511
2512 for (size_t j = 0; j < tal_count(chans); j++)
2513 if (short_channel_id_eq(&chans[j].scid, &r->short_channel_id))
2514 return true;
2515
2516 /* Skip the capacity check if this is the last hop
2517 * in the routehint.
2518 * The last hop in the routehint delivers the exact
2519 * final amount to the destination, which
2520 * payment_get_excluded_channels uses for excluding
2521 * already.
2522 * Thus, the capacity check below only really matters
2523 * for multi-hop routehints.
2524 */
2525 if (i == tal_count(routehint) - 1)
2526 continue;
2527
2528 /* Check our capacity fits. */
2529 struct amount_msat needed_capacity;
2530 if (!route_msatoshi(&needed_capacity, p->amount,
2531 r + 1, tal_count(routehint) - i - 1))
2532 return true;
2533 /* Why do we scan the hints again if
2534 * payment_get_excluded_channels already does?
2535 * Because payment_get_excluded_channels checks the
2536 * amount at destination, but we know that we are
2537 * a specific distance from the destination and we
2538 * know the exact capacity we need to send via this
2539 * channel, which is greater than the destination.
2540 */
2541 for (size_t j = 0; j < tal_count(hints); j++) {
2542 if (!short_channel_id_eq(&hints[j].scid.scid, &r->short_channel_id))
2543 continue;
2544 /* We exclude on equality because we set the estimate
2545 * to the smallest failed attempt. */
2546 if (amount_msat_greater_eq(needed_capacity,
2547 hints[j].estimated_capacity))
2548 return true;
2549 }
2550 }
2551 return false;
2552 }
2553
next_routehint(struct routehints_data * d,struct payment * p)2554 static struct route_info *next_routehint(struct routehints_data *d,
2555 struct payment *p)
2556 {
2557 size_t numhints = tal_count(d->routehints);
2558 struct route_info *curr;
2559
2560 if (d->routehints == NULL || numhints == 0)
2561 return NULL;
2562
2563 /* BOLT #11:
2564 *
2565 * - if a writer offers more than one of any field type, it:
2566 * - MUST specify the most-preferred field first, followed
2567 * by less-preferred fields, in order.
2568 */
2569 for (; d->offset < numhints; d->offset++) {
2570 curr = d->routehints[(d->base + d->offset) % numhints];
2571 if (curr == NULL || !routehint_excluded(p, curr))
2572 return curr;
2573 }
2574 return NULL;
2575 }
2576
2577 /* Calculate how many millisatoshi we need at the start of this route
2578 * to get msatoshi to the end. */
route_msatoshi(struct amount_msat * total,const struct amount_msat msat,const struct route_info * route,size_t num_route)2579 static bool route_msatoshi(struct amount_msat *total,
2580 const struct amount_msat msat,
2581 const struct route_info *route, size_t num_route)
2582 {
2583 *total = msat;
2584 for (ssize_t i = num_route - 1; i >= 0; i--) {
2585 if (!amount_msat_add_fee(total,
2586 route[i].fee_base_msat,
2587 route[i].fee_proportional_millionths))
2588 return false;
2589 }
2590 return true;
2591 }
2592
2593 /* The pubkey to use is the destination of this routehint. */
route_pubkey(const struct payment * p,const struct route_info * routehint,size_t n)2594 static const struct node_id *route_pubkey(const struct payment *p,
2595 const struct route_info *routehint,
2596 size_t n)
2597 {
2598 if (n == tal_count(routehint))
2599 return p->destination;
2600 return &routehint[n].pubkey;
2601 }
2602
route_cltv(u32 cltv,const struct route_info * route,size_t num_route)2603 static u32 route_cltv(u32 cltv,
2604 const struct route_info *route, size_t num_route)
2605 {
2606 for (size_t i = 0; i < num_route; i++)
2607 cltv += route[i].cltv_expiry_delta;
2608 return cltv;
2609 }
2610
2611 /** routehint_generate_exclusion_list
2612 *
2613 * @brief generate a list of items to append to `excludes`
2614 * parameter of `getroute`.
2615 *
2616 * @param ctx - the context to allocate off of.
2617 * @param routehint - the actual routehint, a `tal` array.
2618 * @param payment - the payment that we will create an
2619 * exclusion list for.
2620 *
2621 * @return an array of strings that will be appended to the
2622 * `excludes` parameter of `getroute`.
2623 */
2624 static
routehint_generate_exclusion_list(const tal_t * ctx,struct route_info * routehint,struct payment * payment)2625 struct node_id *routehint_generate_exclusion_list(const tal_t *ctx,
2626 struct route_info *routehint,
2627 struct payment *payment)
2628 {
2629 struct node_id *exc;
2630
2631 if (!routehint || tal_count(routehint) == 0)
2632 /* Nothing to exclude. */
2633 return NULL;
2634
2635 exc = tal_arr(ctx, struct node_id, tal_count(routehint));
2636 /* Exclude every node except the first, because the first is
2637 * the entry point to the routehint. */
2638 for (size_t i = 1 /* Skip the first! */; i < tal_count(routehint); ++i)
2639 exc[i-1] = routehint[i].pubkey;
2640
2641 /* Also exclude the destination, because it would be foolish to
2642 * pass through it and *then* go to the routehint entry point. */
2643 exc[tal_count(routehint)-1] = *payment->destination;
2644 return exc;
2645 }
2646
2647 /* Change the destination and compute the final msatoshi amount to send to the
2648 * routehint entry point. */
routehint_pre_getroute(struct routehints_data * d,struct payment * p)2649 static void routehint_pre_getroute(struct routehints_data *d, struct payment *p)
2650 {
2651 bool have_more;
2652 d->current_routehint = next_routehint(d, p);
2653
2654 /* Signal that we could retry with another routehint even if getroute
2655 * fails. */
2656 have_more = (d->offset < tal_count(d->routehints) - 1);
2657 p->failroute_retry = have_more;
2658
2659 p->temp_exclusion = tal_free(p->temp_exclusion);
2660
2661 if (d->current_routehint != NULL) {
2662 if (!route_msatoshi(&p->getroute->amount, p->amount,
2663 d->current_routehint,
2664 tal_count(d->current_routehint))) {
2665 }
2666 d->final_cltv = p->getroute->cltv;
2667 p->getroute->destination = &d->current_routehint[0].pubkey;
2668 p->getroute->cltv =
2669 route_cltv(p->getroute->cltv, d->current_routehint,
2670 tal_count(d->current_routehint));
2671 paymod_log(
2672 p, LOG_DBG, "Using routehint %s (%s) cltv_delta=%d",
2673 type_to_string(tmpctx, struct node_id,
2674 &d->current_routehint->pubkey),
2675 type_to_string(tmpctx, struct short_channel_id,
2676 &d->current_routehint->short_channel_id),
2677 d->current_routehint->cltv_expiry_delta);
2678
2679 /* Exclude the entrypoint to the routehint, so we don't end up
2680 * going through the destination to the entrypoint. */
2681 p->temp_exclusion = routehint_generate_exclusion_list(p, d->current_routehint, p);
2682 } else
2683 paymod_log(p, LOG_DBG, "Not using a routehint");
2684 }
2685
routehint_check_reachable(struct payment * p)2686 static void routehint_check_reachable(struct payment *p)
2687 {
2688 const struct gossmap_node *dst, *src;
2689 struct gossmap *gossmap = get_gossmap(p->plugin);
2690 const struct dijkstra *dij;
2691 struct route_hop *r;
2692 struct payment *root = payment_root(p);
2693 struct routehints_data *d = payment_mod_routehints_get_data(root);
2694
2695 /* Start a tiny exploratory route computation, so we know
2696 * whether we stand any chance of reaching the destination
2697 * without routehints. This will later be used to mix in
2698 * attempts without routehints. */
2699 src = gossmap_find_node(gossmap, p->local_id);
2700 dst = gossmap_find_node(gossmap, p->destination);
2701 if (dst == NULL)
2702 d->destination_reachable = false;
2703 else if (src != NULL) {
2704 dij = dijkstra(tmpctx, gossmap, dst, AMOUNT_MSAT(1000),
2705 10 / 1000000.0,
2706 payment_route_can_carry_even_disabled,
2707 route_score_cheaper, p);
2708 r = route_from_dijkstra(tmpctx, gossmap, dij, src,
2709 AMOUNT_MSAT(1000), 0);
2710
2711 /* If there was a route the destination is reachable
2712 * without routehints. */
2713 d->destination_reachable = r != NULL;
2714 } else {
2715 paymod_log(p, LOG_DBG,
2716 "Could not locate ourselves in the network. "
2717 "Allowing direct attempts");
2718 d->destination_reachable = true;
2719 }
2720
2721 if (d->destination_reachable) {
2722 tal_arr_expand(&d->routehints, NULL);
2723 /* The above could trigger a realloc.
2724 * However, p->routes and d->routehints are
2725 * actually the same array, so we need to update the
2726 * p->routes pointer, since the realloc
2727 * might have changed pointer addresses, in order to
2728 * ensure that the pointers are not stale.
2729 */
2730 p->routes = d->routehints;
2731
2732 /* FIXME: ***DO*** we need to add this extra routehint?
2733 * Once we run out of routehints the default system will
2734 * just attempt directly routing to the destination anyway. */
2735 } else if (tal_count(d->routehints) == 0) {
2736 /* If we don't have any routehints and the destination
2737 * isn't reachable, then there is no point in
2738 * continuing. */
2739
2740 payment_abort(
2741 p,
2742 "Destination %s is not reachable directly and "
2743 "all routehints were unusable.",
2744 type_to_string(tmpctx, struct node_id, p->destination));
2745 return;
2746 }
2747
2748 routehint_pre_getroute(d, p);
2749
2750 paymod_log(p, LOG_DBG,
2751 "The destination is%s directly reachable %s attempts "
2752 "without routehints",
2753 d->destination_reachable ? "" : " not",
2754 d->destination_reachable ? "including" : "excluding");
2755
2756 /* Now we can continue on our merry way. */
2757 payment_continue(p);
2758 }
2759
routehint_step_cb(struct routehints_data * d,struct payment * p)2760 static void routehint_step_cb(struct routehints_data *d, struct payment *p)
2761 {
2762 struct route_hop hop;
2763 const struct payment *root = payment_root(p);
2764 struct gossmap *map;
2765 if (p->step == PAYMENT_STEP_INITIALIZED) {
2766 if (root->routes == NULL)
2767 return payment_continue(p);
2768
2769 /* We filter out non-functional routehints once at the
2770 * beginning, and every other payment will filter out the
2771 * exluded ones on the fly. */
2772 if (p->parent == NULL) {
2773 map = get_gossmap(p->plugin);
2774 d->routehints = filter_routehints(
2775 map, p, d, p->local_id, p->routes);
2776 /* filter_routehints modifies the array, but
2777 * this could trigger a resize and the resize
2778 * could trigger a realloc.
2779 * Keep the invoice pointer up-to-date.
2780 * FIXME: We should really consider that if we are
2781 * mutating p->routes, maybe we should
2782 * drop d->routehints and just use p->routes
2783 * directly.
2784 * It is probably not a good idea to *copy* the
2785 * routehints: other paymods are interested in
2786 * p->routes, and if the routehints system
2787 * itself adds or removes routehints from its
2788 * copy, the *actual* number of routehints that we
2789 * end up using is the one that the routehints paymod
2790 * is maintaining and traversing, and it is *that*
2791 * set of routehints that is the important one.
2792 * So rather than copying the array of routehints
2793 * in paymod, paymod should use (and mutate) the
2794 * p->routes array, and
2795 */
2796 p->routes = d->routehints;
2797
2798 paymod_log(p, LOG_DBG,
2799 "After filtering routehints we're left with "
2800 "%zu usable hints",
2801 tal_count(d->routehints));
2802 /* Do not continue normally, instead go and check if
2803 * we can reach the destination directly. */
2804 return routehint_check_reachable(p);
2805 }
2806
2807 routehint_pre_getroute(d, p);
2808 } else if (p->step == PAYMENT_STEP_GOT_ROUTE && d->current_routehint != NULL) {
2809 /* Now it's time to stitch the two partial routes together. */
2810 struct amount_msat dest_amount;
2811 struct route_info *routehint = d->current_routehint;
2812 struct route_hop *prev_hop;
2813 for (ssize_t i = 0; i < tal_count(routehint); i++) {
2814 prev_hop = &p->route[tal_count(p->route)-1];
2815 if (!route_msatoshi(&dest_amount, p->amount,
2816 routehint + i + 1,
2817 tal_count(routehint) - i - 1)) {
2818 /* Just let it fail, since we couldn't stitch
2819 * the routes together. */
2820 return payment_continue(p);
2821 }
2822
2823 hop.node_id = *route_pubkey(p, routehint, i + 1);
2824 hop.style = ROUTE_HOP_LEGACY;
2825 hop.scid = routehint[i].short_channel_id;
2826 hop.amount = dest_amount;
2827 hop.delay = route_cltv(d->final_cltv, routehint + i + 1,
2828 tal_count(routehint) - i - 1);
2829
2830 /* Should we get a failure inside the routehint we'll
2831 * need the direction so we can exclude it. Luckily
2832 * it's rather easy to compute given the two
2833 * subsequent hops. */
2834 hop.direction =
2835 node_id_cmp(&prev_hop->node_id, &hop.node_id) > 0 ? 1
2836 : 0;
2837 tal_arr_expand(&p->route, hop);
2838 }
2839 }
2840
2841 payment_continue(p);
2842 }
2843
routehint_data_init(struct payment * p)2844 static struct routehints_data *routehint_data_init(struct payment *p)
2845 {
2846 struct routehints_data *pd, *d = tal(p, struct routehints_data);
2847 /* If for some reason we skipped the getroute call (directpay) we'll
2848 * need this to be initialized. */
2849 d->current_routehint = NULL;
2850 if (p->parent != NULL) {
2851 pd = payment_mod_routehints_get_data(payment_root(p));
2852 d->destination_reachable = pd->destination_reachable;
2853 d->routehints = pd->routehints;
2854 pd = payment_mod_routehints_get_data(p->parent);
2855 if (p->parent->step == PAYMENT_STEP_RETRY) {
2856 d->base = pd->base;
2857 d->offset = pd->offset;
2858 /* If the previous try failed to route, advance
2859 * to the next routehint. */
2860 if (!p->parent->route)
2861 ++d->offset;
2862 } else {
2863 size_t num_routehints = tal_count(d->routehints);
2864 d->offset = 0;
2865 /* This used to be pseudorand.
2866 *
2867 * However, it turns out that using the partid for
2868 * this payment has some nice properties.
2869 * The partid is in general quite random, due to
2870 * getting entropy from the network on the timing
2871 * of when payments complete/fail, and the routehint
2872 * randomization is not a privacy or security feature,
2873 * only a reliability one, thus does not need a lot
2874 * of entropy.
2875 *
2876 * But the most important bit is that *splits get
2877 * contiguous partids*, e.g. a presplit into 4 will
2878 * usually be numbered 2,3,4,5, and an adaptive split
2879 * will get two consecutive partid.
2880 * Because of the contiguity, using the partid for
2881 * the base will cause the split-up payments to
2882 * have fairly diverse initial routehints.
2883 *
2884 * The special-casing for <= 2 and the - 2 is due
2885 * to the presplitter skipping over partid 1, we want
2886 * the starting splits to have partid 2 start at
2887 * base 0.
2888 */
2889 if (p->partid <= 2 || num_routehints <= 1)
2890 d->base = 0;
2891 else
2892 d->base = (p->partid - 2) % num_routehints;
2893 }
2894 return d;
2895 } else {
2896 /* We defer the actual initialization of the routehints array to
2897 * the step callback when we have the invoice attached. */
2898 d->routehints = NULL;
2899 d->base = 0;
2900 d->offset = 0;
2901 return d;
2902 }
2903 return d;
2904 }
2905
2906 REGISTER_PAYMENT_MODIFIER(routehints, struct routehints_data *,
2907 routehint_data_init, routehint_step_cb);
2908
2909 /* For tiny payments the fees incurred due to the fixed base_fee may dominate
2910 * the overall cost of the payment. Since these payments are often used as a
2911 * way to signal, rather than actually transfer the amount, we add an
2912 * exemption that allows tiny payments to exceed the fee allowance. This is
2913 * implemented by setting a larger allowance than we would normally do if the
2914 * payment is below the threshold. */
2915
exemptfee_data_init(struct payment * p)2916 static struct exemptfee_data *exemptfee_data_init(struct payment *p)
2917 {
2918 if (p->parent == NULL) {
2919 struct exemptfee_data *d = tal(p, struct exemptfee_data);
2920 d->amount = AMOUNT_MSAT(5000);
2921 return d;
2922 } else {
2923 return payment_mod_exemptfee_get_data(p->parent);
2924 }
2925 }
2926
exemptfee_cb(struct exemptfee_data * d,struct payment * p)2927 static void exemptfee_cb(struct exemptfee_data *d, struct payment *p)
2928 {
2929 if (p->step != PAYMENT_STEP_INITIALIZED || p->parent != NULL)
2930 return payment_continue(p);
2931
2932 if (amount_msat_greater_eq(d->amount, p->constraints.fee_budget)) {
2933 paymod_log(
2934 p, LOG_INFORM,
2935 "Payment fee constraint %s is below exemption threshold, "
2936 "allowing a maximum fee of %s",
2937 type_to_string(tmpctx, struct amount_msat, &p->constraints.fee_budget),
2938 type_to_string(tmpctx, struct amount_msat, &d->amount));
2939 p->constraints.fee_budget = d->amount;
2940 p->start_constraints->fee_budget = d->amount;
2941 }
2942 return payment_continue(p);
2943 }
2944
2945 REGISTER_PAYMENT_MODIFIER(exemptfee, struct exemptfee_data *,
2946 exemptfee_data_init, exemptfee_cb);
2947
2948 /* BOLT #7:
2949 *
2950 * If a route is computed by simply routing to the intended recipient and
2951 * summing the `cltv_expiry_delta`s, then it's possible for intermediate nodes
2952 * to guess their position in the route. Knowing the CLTV of the HTLC, the
2953 * surrounding network topology, and the `cltv_expiry_delta`s gives an
2954 * attacker a way to guess the intended recipient. Therefore, it's highly
2955 * desirable to add a random offset to the CLTV that the intended recipient
2956 * will receive, which bumps all CLTVs along the route.
2957 *
2958 * In order to create a plausible offset, the origin node MAY start a limited
2959 * random walk on the graph, starting from the intended recipient and summing
2960 * the `cltv_expiry_delta`s, and use the resulting sum as the offset. This
2961 * effectively creates a _shadow route extension_ to the actual route and
2962 * provides better protection against this attack vector than simply picking a
2963 * random offset would.
2964 */
2965
shadow_route_init(struct payment * p)2966 static struct shadow_route_data *shadow_route_init(struct payment *p)
2967 {
2968 struct shadow_route_data *d = tal(p, struct shadow_route_data), *pd;
2969
2970 /* If we're not the root we need to inherit the flags set only on the
2971 * root payment. Since we inherit them at each step it's sufficient to
2972 * do so from our direct parent. */
2973 if (p->parent != NULL) {
2974 pd = payment_mod_shadowroute_get_data(p->parent);
2975 d->fuzz_amount = pd->fuzz_amount;
2976 #if DEVELOPER
2977 d->use_shadow = pd->use_shadow;
2978 #endif
2979 } else {
2980 d->fuzz_amount = true;
2981 }
2982 return d;
2983 }
2984
2985 /* Mutual recursion */
2986 static struct command_result *shadow_route_listchannels(struct command *cmd,
2987 const char *buf,
2988 const jsmntok_t *result,
2989 struct payment *p);
2990
shadow_route_extend(struct shadow_route_data * d,struct payment * p)2991 static struct command_result *shadow_route_extend(struct shadow_route_data *d,
2992 struct payment *p)
2993 {
2994 struct out_req *req;
2995 req = jsonrpc_request_start(p->plugin, NULL, "listchannels",
2996 shadow_route_listchannels,
2997 payment_rpc_failure, p);
2998 json_add_string(req->js, "source",
2999 type_to_string(req, struct node_id, &d->destination));
3000 return send_outreq(p->plugin, req);
3001 }
3002
shadow_route_listchannels(struct command * cmd,const char * buf,const jsmntok_t * result,struct payment * p)3003 static struct command_result *shadow_route_listchannels(struct command *cmd,
3004 const char *buf,
3005 const jsmntok_t *result,
3006 struct payment *p)
3007 {
3008 struct shadow_route_data *d = payment_mod_shadowroute_get_data(p);
3009 struct payment_constraints *cons = &d->constraints;
3010 struct route_info *best = NULL;
3011 double total_weight = 0.0;
3012 size_t i;
3013 struct amount_msat best_fee;
3014 const jsmntok_t *sattok, *delaytok, *basefeetok, *propfeetok, *desttok,
3015 *channelstok, *chan, *scidtok;
3016
3017 /* Check the invariants on the constraints between payment and modifier. */
3018 assert(d->constraints.cltv_budget <= p->constraints.cltv_budget / 4);
3019 assert(amount_msat_greater_eq(p->constraints.fee_budget,
3020 d->constraints.fee_budget));
3021
3022 channelstok = json_get_member(buf, result, "channels");
3023 json_for_each_arr(i, chan, channelstok) {
3024 struct route_info curr;
3025 struct amount_sat capacity;
3026 struct amount_msat fee;
3027
3028 sattok = json_get_member(buf, chan, "satoshis");
3029 delaytok = json_get_member(buf, chan, "delay");
3030 basefeetok = json_get_member(buf, chan, "base_fee_millisatoshi");
3031 propfeetok = json_get_member(buf, chan, "fee_per_millionth");
3032 scidtok = json_get_member(buf, chan, "short_channel_id");
3033 desttok = json_get_member(buf, chan, "destination");
3034
3035 if (sattok == NULL || delaytok == NULL ||
3036 delaytok->type != JSMN_PRIMITIVE || basefeetok == NULL ||
3037 basefeetok->type != JSMN_PRIMITIVE || propfeetok == NULL ||
3038 propfeetok->type != JSMN_PRIMITIVE || desttok == NULL ||
3039 scidtok == NULL)
3040 continue;
3041
3042 json_to_u16(buf, delaytok, &curr.cltv_expiry_delta);
3043 json_to_number(buf, basefeetok, &curr.fee_base_msat);
3044 json_to_number(buf, propfeetok,
3045 &curr.fee_proportional_millionths);
3046 json_to_short_channel_id(buf, scidtok, &curr.short_channel_id);
3047 json_to_sat(buf, sattok, &capacity);
3048 json_to_node_id(buf, desttok, &curr.pubkey);
3049
3050 /* If the capacity is insufficient to pass the amount
3051 * it's not a plausible extension. */
3052 if (amount_msat_greater_sat(p->amount, capacity))
3053 continue;
3054
3055 if (curr.cltv_expiry_delta > cons->cltv_budget)
3056 continue;
3057
3058 if (!amount_msat_fee(
3059 &fee, p->amount, curr.fee_base_msat,
3060 curr.fee_proportional_millionths)) {
3061 /* Fee computation failed... */
3062 continue;
3063 }
3064
3065 if (amount_msat_greater_eq(fee, cons->fee_budget))
3066 continue;
3067
3068 if (random_select(1.0, &total_weight)) {
3069 best = tal_dup(tmpctx, struct route_info, &curr);
3070 best_fee = fee;
3071 }
3072 }
3073
3074 if (best != NULL) {
3075 /* Check that we could apply the shadow route extension. Check
3076 * against both the shadow route budget as well as the
3077 * original payment's budget. */
3078 if (best->cltv_expiry_delta > d->constraints.cltv_budget ||
3079 best->cltv_expiry_delta > p->constraints.cltv_budget) {
3080 best = NULL;
3081 goto next;
3082 }
3083
3084 /* Check the fee budget only if we didn't opt out, since
3085 * testing against a virtual budget is not useful if we do not
3086 * actually use it (it could give false positives and fail
3087 * attempts that might have gone through, */
3088 if (d->fuzz_amount &&
3089 (amount_msat_greater(best_fee, d->constraints.fee_budget) ||
3090 (amount_msat_greater(best_fee,
3091 p->constraints.fee_budget)))) {
3092 best = NULL;
3093 goto next;
3094 }
3095
3096 /* Now we can be sure that adding the shadow route will succeed */
3097 paymod_log(
3098 p, LOG_DBG,
3099 "Adding shadow_route hop over channel %s: adding %s "
3100 "in fees and %d CLTV delta",
3101 type_to_string(tmpctx, struct short_channel_id,
3102 &best->short_channel_id),
3103 type_to_string(tmpctx, struct amount_msat, &best_fee),
3104 best->cltv_expiry_delta);
3105
3106 d->destination = best->pubkey;
3107 d->constraints.cltv_budget -= best->cltv_expiry_delta;
3108 p->getroute->cltv += best->cltv_expiry_delta;
3109
3110 if (!d->fuzz_amount)
3111 goto next;
3112
3113 /* Only try to apply the fee budget changes if we want to fuzz
3114 * the amount. Virtual fees that we then don't deliver to the
3115 * destination could otherwise cause the route to be too
3116 * expensive, while really being ok. If any of these fail then
3117 * the above checks are insufficient. */
3118 if (!amount_msat_sub(&d->constraints.fee_budget,
3119 d->constraints.fee_budget, best_fee) ||
3120 !amount_msat_sub(&p->constraints.fee_budget,
3121 p->constraints.fee_budget, best_fee))
3122 paymod_err(p,
3123 "Could not update fee constraints "
3124 "for shadow route extension. "
3125 "payment fee budget %s, modifier "
3126 "fee budget %s, shadow fee to add %s",
3127 type_to_string(tmpctx, struct amount_msat,
3128 &p->constraints.fee_budget),
3129 type_to_string(tmpctx, struct amount_msat,
3130 &d->constraints.fee_budget),
3131 type_to_string(tmpctx, struct amount_msat,
3132 &best_fee));
3133 }
3134
3135 next:
3136
3137 /* Now it's time to decide whether we want to extend or continue. */
3138 if (best == NULL || pseudorand(2) == 0) {
3139 payment_continue(p);
3140 return command_still_pending(cmd);
3141 } else {
3142 return shadow_route_extend(d, p);
3143 }
3144 }
3145
shadow_route_cb(struct shadow_route_data * d,struct payment * p)3146 static void shadow_route_cb(struct shadow_route_data *d,
3147 struct payment *p)
3148 {
3149 #if DEVELOPER
3150 if (!d->use_shadow)
3151 return payment_continue(p);
3152 #endif
3153
3154 if (p->step != PAYMENT_STEP_INITIALIZED)
3155 return payment_continue(p);
3156
3157 d->destination = *p->destination;
3158
3159 /* Allow shadowroutes to consume up to 1/4th of our budget. */
3160 d->constraints.cltv_budget = p->constraints.cltv_budget / 4;
3161 d->constraints.fee_budget
3162 = amount_msat_div(p->constraints.fee_budget, 4);
3163
3164 if (pseudorand(2) == 0) {
3165 return payment_continue(p);
3166 } else {
3167 shadow_route_extend(d, p);
3168 }
3169 }
3170
3171 REGISTER_PAYMENT_MODIFIER(shadowroute, struct shadow_route_data *,
3172 shadow_route_init, shadow_route_cb);
3173
direct_pay_override(struct payment * p)3174 static void direct_pay_override(struct payment *p) {
3175
3176 /* The root has performed the search for a direct channel. */
3177 struct payment *root = payment_root(p);
3178 struct direct_pay_data *d;
3179 struct channel_hint *hint = NULL;
3180
3181 /* If we were unable to find a direct channel we don't need to do
3182 * anything. */
3183 d = payment_mod_directpay_get_data(root);
3184
3185 if (d->chan == NULL)
3186 return payment_continue(p);
3187
3188 /* If we have a channel we need to make sure that it still has
3189 * sufficient capacity. Look it up in the channel_hints. */
3190 for (size_t i=0; i<tal_count(root->channel_hints); i++) {
3191 struct short_channel_id_dir *cur = &root->channel_hints[i].scid;
3192 if (short_channel_id_eq(&cur->scid, &d->chan->scid) &&
3193 cur->dir == d->chan->dir) {
3194 hint = &root->channel_hints[i];
3195 break;
3196 }
3197 }
3198
3199 if (hint && hint->enabled &&
3200 amount_msat_greater(hint->estimated_capacity, p->amount)) {
3201 /* Now build a route that consists only of this single hop */
3202 p->route = tal_arr(p, struct route_hop, 1);
3203 p->route[0].amount = p->amount;
3204 p->route[0].delay = p->getroute->cltv;
3205 p->route[0].scid = hint->scid.scid;
3206 p->route[0].direction = hint->scid.dir;
3207 p->route[0].node_id = *p->destination;
3208 p->route[0].style = p->destination_has_tlv ? ROUTE_HOP_TLV : ROUTE_HOP_LEGACY;
3209 paymod_log(p, LOG_DBG,
3210 "Found a direct channel (%s) with sufficient "
3211 "capacity, skipping route computation.",
3212 type_to_string(tmpctx, struct short_channel_id_dir,
3213 &hint->scid));
3214
3215 payment_set_step(p, PAYMENT_STEP_GOT_ROUTE);
3216 }
3217
3218
3219 payment_continue(p);
3220 }
3221
3222 /* Now that we have the listpeers result for the root payment, let's search
3223 * for a direct channel that is a) connected and b) in state normal. We will
3224 * check the capacity based on the channel_hints in the override. */
direct_pay_listpeers(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)3225 static struct command_result *direct_pay_listpeers(struct command *cmd,
3226 const char *buffer,
3227 const jsmntok_t *toks,
3228 struct payment *p)
3229 {
3230 struct listpeers_result *r =
3231 json_to_listpeers_result(tmpctx, buffer, toks);
3232 struct direct_pay_data *d = payment_mod_directpay_get_data(p);
3233
3234 if (tal_count(r->peers) == 1) {
3235 struct listpeers_peer *peer = r->peers[0];
3236 if (!peer->connected)
3237 goto cont;
3238
3239 for (size_t i=0; i<tal_count(peer->channels); i++) {
3240 struct listpeers_channel *chan = r->peers[0]->channels[i];
3241 if (!streq(chan->state, "CHANNELD_NORMAL"))
3242 continue;
3243
3244 d->chan = tal(d, struct short_channel_id_dir);
3245 d->chan->scid = *chan->scid;
3246 d->chan->dir = *chan->direction;
3247 }
3248 }
3249 cont:
3250 direct_pay_override(p);
3251 return command_still_pending(cmd);
3252
3253 }
3254
direct_pay_cb(struct direct_pay_data * d,struct payment * p)3255 static void direct_pay_cb(struct direct_pay_data *d, struct payment *p)
3256 {
3257 struct out_req *req;
3258
3259 /* Look up the direct channel only on root. */
3260 if (p->step != PAYMENT_STEP_INITIALIZED)
3261 return payment_continue(p);
3262
3263
3264
3265 req = jsonrpc_request_start(p->plugin, NULL, "listpeers",
3266 direct_pay_listpeers, direct_pay_listpeers,
3267 p);
3268 json_add_node_id(req->js, "id", p->destination);
3269 send_outreq(p->plugin, req);
3270 }
3271
direct_pay_init(struct payment * p)3272 static struct direct_pay_data *direct_pay_init(struct payment *p)
3273 {
3274 struct direct_pay_data *d = tal(p, struct direct_pay_data);
3275 d->chan = NULL;
3276 return d;
3277 }
3278
3279 REGISTER_PAYMENT_MODIFIER(directpay, struct direct_pay_data *, direct_pay_init,
3280 direct_pay_cb);
3281
waitblockheight_rpc_cb(struct command * cmd,const char * buffer,const jsmntok_t * toks,struct payment * p)3282 static struct command_result *waitblockheight_rpc_cb(struct command *cmd,
3283 const char *buffer,
3284 const jsmntok_t *toks,
3285 struct payment *p)
3286 {
3287 const jsmntok_t *blockheighttok, *codetok;
3288
3289 u32 blockheight;
3290 int code;
3291 struct payment *subpayment;
3292
3293 blockheighttok = json_get_member(buffer, toks, "blockheight");
3294
3295 if (!blockheighttok ||
3296 !json_to_number(buffer, blockheighttok, &blockheight)) {
3297 codetok = json_get_member(buffer, toks, "code");
3298 json_to_int(buffer, codetok, &code);
3299 if (code == WAIT_TIMEOUT) {
3300 payment_fail(
3301 p,
3302 "Timed out while attempting to sync to blockheight "
3303 "returned by destination. Please finish syncing "
3304 "with the blockchain and try again.");
3305
3306 } else {
3307 plugin_err(
3308 p->plugin,
3309 "Unexpected result from waitblockheight: %.*s",
3310 json_tok_full_len(toks),
3311 json_tok_full(buffer, toks));
3312 }
3313 } else {
3314 subpayment = payment_new(p, NULL, p, p->modifiers);
3315 payment_start_at_blockheight(subpayment, blockheight);
3316 payment_set_step(p, PAYMENT_STEP_RETRY);
3317 subpayment->why = tal_fmt(
3318 subpayment, "Retrying after waiting for blockchain sync.");
3319 paymod_log(
3320 p, LOG_DBG,
3321 "Retrying after waitblockheight, new partid %" PRIu32,
3322 subpayment->partid);
3323 payment_continue(p);
3324 }
3325 return command_still_pending(cmd);
3326 }
3327
waitblockheight_cb(void * d,struct payment * p)3328 static void waitblockheight_cb(void *d, struct payment *p)
3329 {
3330 struct out_req *req;
3331 struct timeabs now = time_now();
3332 struct timerel remaining;
3333 u32 blockheight;
3334 if (p->step != PAYMENT_STEP_FAILED)
3335 return payment_continue(p);
3336
3337 /* If we don't have an error message to parse we can't wait for blockheight. */
3338 if (p->result == NULL)
3339 return payment_continue(p);
3340
3341 /* Check if we'd be waiting more than 0 seconds. If we have
3342 * less than a second then waitblockheight would return
3343 * immediately resulting in a loop. */
3344 if (time_after(now, p->deadline))
3345 return payment_continue(p);
3346
3347 remaining = time_between(p->deadline, now);
3348 if (time_to_sec(remaining) < 1)
3349 return payment_continue(p);
3350
3351 /* *Was* it a blockheight disagreement that caused the failure? */
3352 if (!failure_is_blockheight_disagreement(p, &blockheight))
3353 return payment_continue(p);
3354
3355 paymod_log(p, LOG_INFORM,
3356 "Remote node appears to be on a longer chain, which causes "
3357 "CLTV timeouts to be incorrect. Waiting up to %" PRIu64
3358 " seconds to catch up to block %d before retrying.",
3359 time_to_sec(remaining), blockheight);
3360
3361 /* Set temporarily set the state of the payment to not failed, so
3362 * interim status queries don't show this as terminally failed. We're
3363 * in control for this payment so nobody else could be fooled by
3364 * this. The callback will set it to retry anyway. */
3365 payment_set_step(p, PAYMENT_STEP_RETRY);
3366
3367 req = jsonrpc_request_start(p->plugin, NULL, "waitblockheight",
3368 waitblockheight_rpc_cb,
3369 waitblockheight_rpc_cb, p);
3370 json_add_u32(req->js, "blockheight", blockheight);
3371 json_add_u32(req->js, "timeout", time_to_sec(remaining));
3372 send_outreq(p->plugin, req);
3373 }
3374
3375 REGISTER_PAYMENT_MODIFIER(waitblockheight, void *, NULL, waitblockheight_cb);
3376
3377 /*****************************************************************************
3378 * presplit -- Early MPP splitter modifier.
3379 *
3380 * This splitter modifier is applied to the root payment, and splits the
3381 * payment into parts that are more likely to succeed right away. The
3382 * parameters are derived from probing the network for channel capacities, and
3383 * may be adjusted in future.
3384 */
3385
3386
3387 /*By probing the capacity from a well-connected vantage point in the network
3388 * we found that the 80th percentile of capacities is >= 9765 sats.
3389 *
3390 * Rounding to 10e6 msats per part there is a ~80% chance that the payment
3391 * will go through without requiring further splitting. The fuzzing is
3392 * symmetric and uniformy distributed around this value, so this should not
3393 * change the success rate much. For the remaining 20% of payments we might
3394 * require a split to make the parts succeed, so we try only a limited number
3395 * of times before we split adaptively.
3396 *
3397 * Notice that these numbers are based on a worst case assumption that
3398 * payments from any node to any other node are equally likely, which isn't
3399 * really the case, so this is likely a lower bound on the success rate.
3400 *
3401 * As the network evolves these numbers are also likely to change.
3402 *
3403 * Finally, if applied trivially this splitter may end up creating more splits
3404 * than the sum of all channels can support, i.e., each split results in an
3405 * HTLC, and each channel has an upper limit on the number of HTLCs it'll
3406 * allow us to add. If the initial split would result in more than 1/3rd of
3407 * the total available HTLCs we clamp the number of splits to 1/3rd. We don't
3408 * use 3/3rds in order to retain flexibility in the adaptive splitter.
3409 */
3410 #define MPP_TARGET_SIZE (10 * 1000 * 1000)
3411 #define PRESPLIT_MAX_HTLC_SHARE 3
3412
3413 /* How many parts do we split into before we increase the bucket size. This is
3414 * a tradeoff between the number of payments whose parts are identical and the
3415 * number of concurrent HTLCs. The larger this amount the more HTLCs we may
3416 * end up starting, but the more payments result in the same part sizes.*/
3417 #define PRESPLIT_MAX_SPLITS 16
3418
presplit_mod_data_init(struct payment * p)3419 static struct presplit_mod_data *presplit_mod_data_init(struct payment *p)
3420 {
3421 struct presplit_mod_data *d;
3422 if (p->parent == NULL) {
3423 d = tal(p, struct presplit_mod_data);
3424 d->disable = false;
3425 return d;
3426 } else {
3427 return payment_mod_presplit_get_data(p->parent);
3428 }
3429 }
3430
payment_max_htlcs(const struct payment * p)3431 static u32 payment_max_htlcs(const struct payment *p)
3432 {
3433 const struct payment *root;
3434 struct channel_hint *h;
3435 u32 res = 0;
3436 for (size_t i = 0; i < tal_count(p->channel_hints); i++) {
3437 h = &p->channel_hints[i];
3438 if (h->local && h->enabled)
3439 res += h->htlc_budget;
3440 }
3441 root = p;
3442 while (root->parent)
3443 root = root->parent;
3444 if (res > root->max_htlcs)
3445 res = root->max_htlcs;
3446 return res;
3447 }
3448
3449 /** payment_lower_max_htlcs
3450 *
3451 * @brief indicates that we have a good reason to believe that
3452 * we should limit our number of max HTLCs.
3453 *
3454 * @desc Causes future payment_max_htlcs to have a maximum value
3455 * they return.
3456 * Can be called by multiple paymods: the lowest one any paymod
3457 * has given will be used.
3458 * If this is called with a limit higher than the existing limit,
3459 * it just successfully returns without doing anything.
3460 *
3461 * @param p - a payment on the payment tree we should limit.
3462 * @param limit - the number of max HTLCs.
3463 * @param why - the reason we think the given max HTLCs is
3464 * reasonable.
3465 */
payment_lower_max_htlcs(struct payment * p,u32 limit,const char * why)3466 static void payment_lower_max_htlcs(struct payment *p, u32 limit,
3467 const char *why)
3468 {
3469 struct payment *root = payment_root(p);
3470 if (root->max_htlcs > limit) {
3471 paymod_log(p, LOG_INFORM,
3472 "%s limit on max HTLCs: %"PRIu32", %s",
3473 root->max_htlcs == UINT32_MAX ?
3474 "Initial" : "Lowering",
3475 limit, why);
3476 root->max_htlcs = limit;
3477 }
3478 }
3479
payment_supports_mpp(struct payment * p)3480 static bool payment_supports_mpp(struct payment *p)
3481 {
3482 return feature_offered(p->features, OPT_BASIC_MPP);
3483 }
3484
3485 /* Return fuzzed amount ~= target, but never exceeding max */
fuzzed_near(struct amount_msat target,struct amount_msat max)3486 static struct amount_msat fuzzed_near(struct amount_msat target,
3487 struct amount_msat max)
3488 {
3489 s64 fuzz;
3490 struct amount_msat res = target;
3491
3492 /* Somewhere within 25% of target please. */
3493 fuzz = pseudorand(target.millisatoshis / 2) /* Raw: fuzz */
3494 - target.millisatoshis / 4; /* Raw: fuzz */
3495 res.millisatoshis = target.millisatoshis + fuzz; /* Raw: fuzz < msat */
3496
3497 if (amount_msat_greater(res, max))
3498 res = max;
3499 return res;
3500 }
3501
presplit_cb(struct presplit_mod_data * d,struct payment * p)3502 static void presplit_cb(struct presplit_mod_data *d, struct payment *p)
3503 {
3504 struct payment *root = payment_root(p);
3505
3506 if (d->disable || p->parent != NULL || !payment_supports_mpp(p))
3507 return payment_continue(p);
3508
3509 if (p->step == PAYMENT_STEP_ONION_PAYLOAD) {
3510 /* We need to tell the last hop the total we're going to
3511 * send. Presplit disables amount fuzzing, so we should always
3512 * get the exact value through. */
3513 size_t lastidx = tal_count(p->createonion_request->hops) - 1;
3514 struct createonion_hop *hop = &p->createonion_request->hops[lastidx];
3515 if (hop->style == ROUTE_HOP_TLV) {
3516 struct tlv_field **fields = &hop->tlv_payload->fields;
3517 tlvstream_set_tlv_payload_data(
3518 fields, root->payment_secret,
3519 root->amount.millisatoshis); /* Raw: onion payload */
3520 }
3521 } else if (p->step == PAYMENT_STEP_INITIALIZED) {
3522 /* The presplitter only acts on the root and only in the first
3523 * step. */
3524 size_t count = 0;
3525 u32 htlcs;
3526 struct amount_msat target, amt = p->amount;
3527 char *partids = tal_strdup(tmpctx, "");
3528 u64 target_amount = MPP_TARGET_SIZE;
3529
3530 /* We aim for at most PRESPLIT_MAX_SPLITS parts, even for
3531 * large values. To achieve this we take the base amount and
3532 * multiply it by the number of targetted parts until the
3533 * total amount divided by part amount gives us at most that
3534 * number of parts. */
3535 while (amount_msat_less(amount_msat(target_amount * PRESPLIT_MAX_SPLITS),
3536 p->amount))
3537 target_amount *= PRESPLIT_MAX_SPLITS;
3538
3539 /* We need to opt-in to the MPP sending facility no matter
3540 * what we do. That means setting all partids to a non-zero
3541 * value. */
3542 root->partid++;
3543
3544 /* Bump the next_partid as well so we don't have duplicate
3545 * partids. Not really necessary since the root payment whose
3546 * id could be reused will never reach the `sendonion` step,
3547 * but makes debugging a bit easier. */
3548 root->next_partid++;
3549
3550 htlcs = payment_max_htlcs(p);
3551 /* Divide it up if we can, but it might be v low already */
3552 if (htlcs >= PRESPLIT_MAX_HTLC_SHARE)
3553 htlcs /= PRESPLIT_MAX_HTLC_SHARE;
3554
3555 int targethtlcs =
3556 p->amount.millisatoshis / target_amount; /* Raw: division */
3557 if (htlcs == 0) {
3558 p->abort = true;
3559 return payment_fail(
3560 p, "Cannot attempt payment, we have no channel to "
3561 "which we can add an HTLC");
3562 } else if (targethtlcs > htlcs) {
3563 paymod_log(p, LOG_INFORM,
3564 "Number of pre-split HTLCs (%d) exceeds our "
3565 "HTLC budget (%d), skipping pre-splitter",
3566 targethtlcs, htlcs);
3567 return payment_continue(p);
3568 } else
3569 target = amount_msat(target_amount);
3570
3571 /* If we are already below the target size don't split it
3572 * either. */
3573 if (amount_msat_greater(target, p->amount))
3574 return payment_continue(p);
3575
3576 payment_set_step(p, PAYMENT_STEP_SPLIT);
3577 /* Ok, we know we should split, so split here and then skip this
3578 * payment and start the children instead. */
3579 while (!amount_msat_eq(amt, AMOUNT_MSAT(0))) {
3580 double multiplier;
3581
3582 struct payment *c =
3583 payment_new(p, NULL, p, p->modifiers);
3584
3585 /* Annotate the subpayments with the bolt11 string,
3586 * they'll be used when aggregating the payments
3587 * again. */
3588 c->invstring = tal_strdup(c, p->invstring);
3589
3590 /* Get ~ target, but don't exceed amt */
3591 c->amount = fuzzed_near(target, amt);
3592
3593 if (!amount_msat_sub(&amt, amt, c->amount))
3594 paymod_err(
3595 p,
3596 "Cannot subtract %s from %s in splitter",
3597 type_to_string(tmpctx, struct amount_msat,
3598 &c->amount),
3599 type_to_string(tmpctx, struct amount_msat,
3600 &amt));
3601
3602 /* Now adjust the constraints so we don't multiply them
3603 * when splitting. */
3604 multiplier = amount_msat_ratio(c->amount, p->amount);
3605 if (!amount_msat_scale(&c->constraints.fee_budget,
3606 c->constraints.fee_budget,
3607 multiplier))
3608 abort(); /* multiplier < 1! */
3609 payment_start(c);
3610 /* Why the wordy "new partid n" that we repeat for
3611 * each payment?
3612 * So that you can search the logs for the
3613 * creation of a partid by just "new partid n".
3614 */
3615 if (count == 0)
3616 tal_append_fmt(&partids, "new partid %"PRIu32, c->partid);
3617 else
3618 tal_append_fmt(&partids, ", new partid %"PRIu32, c->partid);
3619 count++;
3620 }
3621
3622 p->result = NULL;
3623 p->route = NULL;
3624 p->why = tal_fmt(
3625 p,
3626 "Split into %zu sub-payments due to initial size (%s > %s)",
3627 count,
3628 type_to_string(tmpctx, struct amount_msat, &root->amount),
3629 type_to_string(tmpctx, struct amount_msat, &target));
3630 paymod_log(p, LOG_INFORM, "%s: %s", p->why, partids);
3631 }
3632 payment_continue(p);
3633 }
3634
3635 REGISTER_PAYMENT_MODIFIER(presplit, struct presplit_mod_data *,
3636 presplit_mod_data_init, presplit_cb);
3637
3638 /*****************************************************************************
3639 * Adaptive splitter -- Split payment if we can't get it through.
3640 *
3641 * The adaptive splitter splits the amount of a failed payment in half, with
3642 * +/- 10% randomness, and then starts two attempts, one for either side of
3643 * the split. The goal is to find two smaller routes, that still adhere to our
3644 * constraints, but that can complete the payment.
3645 *
3646 * This modifier also checks whether we can split and still have enough HTLCs
3647 * available on the channels and aborts if that's no longer the case.
3648 */
3649
3650 #define MPP_ADAPTIVE_LOWER_LIMIT AMOUNT_MSAT(100 * 1000)
3651
adaptive_splitter_data_init(struct payment * p)3652 static struct adaptive_split_mod_data *adaptive_splitter_data_init(struct payment *p)
3653 {
3654 struct adaptive_split_mod_data *d;
3655 if (p->parent == NULL) {
3656 d = tal(p, struct adaptive_split_mod_data);
3657 d->disable = false;
3658 d->htlc_budget = 0;
3659 return d;
3660 } else {
3661 return payment_mod_adaptive_splitter_get_data(p->parent);
3662 }
3663 }
3664
adaptive_splitter_cb(struct adaptive_split_mod_data * d,struct payment * p)3665 static void adaptive_splitter_cb(struct adaptive_split_mod_data *d, struct payment *p)
3666 {
3667 struct payment *root = payment_root(p);
3668 struct adaptive_split_mod_data *root_data =
3669 payment_mod_adaptive_splitter_get_data(root);
3670 if (d->disable)
3671 return payment_continue(p);
3672
3673 if (!payment_supports_mpp(p) || root->abort)
3674 return payment_continue(p);
3675
3676 if (p->parent == NULL && d->htlc_budget == 0) {
3677 /* Now that we potentially had an early splitter run, let's
3678 * update our htlc_budget that we own exclusively from now
3679 * on. We do this by subtracting the number of payment
3680 * attempts an eventual presplitter has already performed. */
3681 int children = tal_count(p->children);
3682 d->htlc_budget = payment_max_htlcs(p);
3683 if (children > d->htlc_budget) {
3684 p->abort = true;
3685 return payment_fail(
3686 p,
3687 "Cannot add %d HTLCs to our channels, we "
3688 "only have %d HTLCs available.",
3689 children, d->htlc_budget);
3690 }
3691 d->htlc_budget -= children;
3692 }
3693
3694 if (p->step == PAYMENT_STEP_ONION_PAYLOAD) {
3695 /* We need to tell the last hop the total we're going to
3696 * send. Presplit disables amount fuzzing, so we should always
3697 * get the exact value through. */
3698 size_t lastidx = tal_count(p->createonion_request->hops) - 1;
3699 struct createonion_hop *hop = &p->createonion_request->hops[lastidx];
3700 if (hop->style == ROUTE_HOP_TLV) {
3701 struct tlv_field **fields = &hop->tlv_payload->fields;
3702 tlvstream_set_tlv_payload_data(
3703 fields, root->payment_secret,
3704 root->amount.millisatoshis); /* Raw: onion payload */
3705 }
3706 } else if (p->step == PAYMENT_STEP_FAILED && !p->abort) {
3707 if (amount_msat_greater(p->amount, MPP_ADAPTIVE_LOWER_LIMIT)) {
3708 struct payment *a, *b;
3709 /* Random number in the range [90%, 110%] */
3710 double rand = pseudorand_double() * 0.2 + 0.9;
3711 u64 mid = p->amount.millisatoshis / 2 * rand; /* Raw: multiplication */
3712 bool ok;
3713 /* Use the start constraints, not the ones updated by routes and shadow-routes. */
3714 struct payment_constraints *pconstraints = p->start_constraints;
3715
3716 /* First check that splitting doesn't exceed our HTLC budget */
3717 if (root_data->htlc_budget == 0) {
3718 root->abort = true;
3719 return payment_fail(
3720 p,
3721 "Cannot split payment any further without "
3722 "exceeding the maximum number of HTLCs "
3723 "allowed by our channels");
3724 }
3725
3726 p->step = PAYMENT_STEP_SPLIT;
3727 a = payment_new(p, NULL, p, p->modifiers);
3728 b = payment_new(p, NULL, p, p->modifiers);
3729
3730 a->amount.millisatoshis = mid; /* Raw: split. */
3731 b->amount.millisatoshis -= mid; /* Raw: split. */
3732
3733 double multiplier = amount_msat_ratio(a->amount,
3734 p->amount);
3735 assert(multiplier >= 0.4 && multiplier < 0.6);
3736
3737 /* Adjust constraints since we don't want to double our
3738 * fee allowance when we split. */
3739 if (!amount_msat_scale(&a->constraints.fee_budget,
3740 pconstraints->fee_budget,
3741 multiplier))
3742 abort();
3743
3744 ok = amount_msat_sub(&b->constraints.fee_budget,
3745 pconstraints->fee_budget,
3746 a->constraints.fee_budget);
3747
3748 /* Should not fail, mid is less than 55% of original
3749 * amount. fee_budget_a <= 55% of fee_budget_p (parent
3750 * of the new payments).*/
3751 assert(ok);
3752
3753 payment_start(a);
3754 payment_start(b);
3755
3756 paymod_log(p, LOG_DBG,
3757 "Adaptively split into 2 sub-payments: "
3758 "new partid %"PRIu32" (%s), "
3759 "new partid %"PRIu32" (%s)",
3760 a->partid,
3761 type_to_string(tmpctx, struct amount_msat,
3762 &a->amount),
3763 b->partid,
3764 type_to_string(tmpctx, struct amount_msat,
3765 &b->amount));
3766
3767 /* Take note that we now have an additional split that
3768 * may end up using an HTLC. */
3769 root_data->htlc_budget--;
3770 } else {
3771 paymod_log(p, LOG_INFORM,
3772 "Lower limit of adaptive splitter reached "
3773 "(%s < %s), not splitting further.",
3774 type_to_string(tmpctx, struct amount_msat,
3775 &p->amount),
3776 type_to_string(tmpctx, struct amount_msat,
3777 &MPP_ADAPTIVE_LOWER_LIMIT));
3778 }
3779 }
3780 payment_continue(p);
3781 }
3782
3783 REGISTER_PAYMENT_MODIFIER(adaptive_splitter, struct adaptive_split_mod_data *,
3784 adaptive_splitter_data_init, adaptive_splitter_cb);
3785
3786
3787 /*****************************************************************************
3788 * payee_incoming_limit
3789 *
3790 * @desc every channel has a limit on the number of HTLCs it is willing to
3791 * transport.
3792 * This is particularly crucial for the payers and payees, as they represent
3793 * the bottleneck to and from the network.
3794 * The `payment_max_htlcs` function will, by itself, be able to count the
3795 * payer-side channels, but assessing the payee requires us to probe the
3796 * area around it.
3797 *
3798 * This paymod must be *after* `routehints` but *before* `presplit` paymods:
3799 *
3800 * - If we cannot find the destination on the public network, we can only
3801 * use channels it put in the routehints.
3802 * In this case, that is the number of channels we assess the payee as
3803 * having.
3804 * However, the `routehints` paymod may filter out some routehints, thus
3805 * we should assess based on the post-filtered routehints.
3806 * - The `presplit` is the first splitter that executes, so we have to have
3807 * performed the payee-channels assessment by then.
3808 */
3809
3810 /* The default `max-concurrent-htlcs` is 30, but node operators might want
3811 * to push it even lower to reduce their liabilities in case they have to
3812 * unilaterally close.
3813 * This will not necessarily improve even in a post-anchor-commitments world,
3814 * since one of the reasons to unilaterally close is if some HTLC is about to
3815 * expire, which of course requires the HTLCs to be published anyway, meaning
3816 * it will still be potentially costly.
3817 * So our initial assumption is 15 HTLCs per channel.
3818 *
3819 * The presplitter will divide this by `PRESPLIT_MAX_HTLC_SHARE` as well.
3820 */
3821 #define ASSUMED_MAX_HTLCS_PER_CHANNEL 15
3822
3823 static struct command_result *
payee_incoming_limit_count(struct command * cmd,const char * buf,const jsmntok_t * result,struct payment * p)3824 payee_incoming_limit_count(struct command *cmd,
3825 const char *buf,
3826 const jsmntok_t *result,
3827 struct payment *p)
3828 {
3829 const jsmntok_t *channelstok;
3830 size_t num_channels = 0;
3831
3832 channelstok = json_get_member(buf, result, "channels");
3833 assert(channelstok);
3834
3835 /* Count channels.
3836 * `listchannels` returns half-channels, i.e. it normally
3837 * gives two objects per channel, one for each direction.
3838 * However, `listchannels <source>` returns only half-channel
3839 * objects whose `source` is the given channel.
3840 * Thus, the length of `channels` is accurately the number
3841 * of channels.
3842 */
3843 num_channels = channelstok->size;
3844
3845 /* If num_channels is 0, check if there is an invoice. */
3846 if (num_channels == 0)
3847 num_channels = tal_count(p->routes);
3848
3849 /* If we got a decent number of channels, limit! */
3850 if (num_channels != 0) {
3851 const char *why;
3852 u32 lim;
3853 why = tal_fmt(tmpctx,
3854 "Destination %s has %zd channels, "
3855 "assuming %d HTLCs per channel",
3856 type_to_string(tmpctx, struct node_id,
3857 p->destination),
3858 num_channels,
3859 ASSUMED_MAX_HTLCS_PER_CHANNEL);
3860 lim = num_channels * ASSUMED_MAX_HTLCS_PER_CHANNEL;
3861 payment_lower_max_htlcs(p, lim, why);
3862 }
3863
3864 payment_continue(p);
3865 return command_still_pending(cmd);
3866 }
3867
payee_incoming_limit_step_cb(void * d UNUSED,struct payment * p)3868 static void payee_incoming_limit_step_cb(void *d UNUSED, struct payment *p)
3869 {
3870 /* Only operate at the initialization of te root payment.
3871 * Also, no point operating if payment does not support MPP anyway.
3872 */
3873 if (p->parent || p->step != PAYMENT_STEP_INITIALIZED
3874 || !payment_supports_mpp(p))
3875 return payment_continue(p);
3876
3877 /* Get information on the destination. */
3878 struct out_req *req;
3879 req = jsonrpc_request_start(p->plugin, NULL, "listchannels",
3880 &payee_incoming_limit_count,
3881 &payment_rpc_failure, p);
3882 json_add_node_id(req->js, "source", p->destination);
3883 (void) send_outreq(p->plugin, req);
3884 }
3885
3886 REGISTER_PAYMENT_MODIFIER(payee_incoming_limit, void *, NULL,
3887 payee_incoming_limit_step_cb);
3888