1 #include "features.h"
2 #include <assert.h>
3 #include <ccan/array_size/array_size.h>
4 #include <ccan/tal/str/str.h>
5 #include <wire/peer_wire.h>
6
7 enum feature_copy_style {
8 /* Feature is not exposed (importantly, being 0, this is the default!). */
9 FEATURE_DONT_REPRESENT,
10 /* Feature is exposed. */
11 FEATURE_REPRESENT,
12 /* Feature is exposed, but always optional. */
13 FEATURE_REPRESENT_AS_OPTIONAL,
14 };
15
16 struct feature_style {
17 u32 bit;
18 enum feature_copy_style copy_style[NUM_FEATURE_PLACE];
19 };
20
21 const char *feature_place_names[] = {
22 "init",
23 NULL,
24 "node",
25 "channel",
26 "invoice"
27 };
28
29 static const struct feature_style feature_styles[] = {
30 { OPT_DATA_LOSS_PROTECT,
31 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
32 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT } },
33 { OPT_INITIAL_ROUTING_SYNC,
34 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT_AS_OPTIONAL,
35 [NODE_ANNOUNCE_FEATURE] = FEATURE_DONT_REPRESENT } },
36 { OPT_UPFRONT_SHUTDOWN_SCRIPT,
37 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
38 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT } },
39 { OPT_GOSSIP_QUERIES,
40 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
41 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT } },
42 { OPT_GOSSIP_QUERIES_EX,
43 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
44 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT } },
45 { OPT_VAR_ONION,
46 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
47 [GLOBAL_INIT_FEATURE] = FEATURE_REPRESENT,
48 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
49 [BOLT11_FEATURE] = FEATURE_REPRESENT } },
50 { OPT_STATIC_REMOTEKEY,
51 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
52 [GLOBAL_INIT_FEATURE] = FEATURE_REPRESENT,
53 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT } },
54 { OPT_PAYMENT_SECRET,
55 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
56 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
57 [BOLT11_FEATURE] = FEATURE_REPRESENT } },
58 { OPT_BASIC_MPP,
59 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
60 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
61 [BOLT11_FEATURE] = FEATURE_REPRESENT } },
62 /* BOLT #9:
63 * | 18/19 | `option_support_large_channel` |... IN ...
64 */
65 { OPT_LARGE_CHANNELS,
66 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
67 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
68 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT } },
69 { OPT_ONION_MESSAGES,
70 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
71 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
72 [BOLT11_FEATURE] = FEATURE_REPRESENT,
73 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT} },
74 { OPT_SHUTDOWN_WRONG_FUNDING,
75 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
76 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
77 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT} },
78 { OPT_ANCHOR_OUTPUTS,
79 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
80 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
81 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT } },
82 { OPT_DUAL_FUND,
83 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
84 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
85 [BOLT11_FEATURE] = FEATURE_REPRESENT,
86 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT} },
87 { OPT_SHUTDOWN_ANYSEGWIT,
88 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
89 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
90 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT } },
91 { OPT_QUIESCE,
92 .copy_style = { [INIT_FEATURE] = FEATURE_REPRESENT,
93 [NODE_ANNOUNCE_FEATURE] = FEATURE_REPRESENT,
94 [CHANNEL_FEATURE] = FEATURE_DONT_REPRESENT } },
95 };
96
97 struct dependency {
98 size_t depender;
99 size_t must_also_have;
100 };
101
102 static const struct dependency feature_deps[] = {
103 /* BOLT #9:
104 * Name | Description | Context | Dependencies |
105 *...
106 * `gossip_queries_ex` | ... | ... | `gossip_queries` |
107 *...
108 * `payment_secret` | ... | ... | `var_onion_optin` |
109 *...
110 * `basic_mpp` | ... | ... | `payment_secret` |
111 */
112 { OPT_GOSSIP_QUERIES_EX, OPT_GOSSIP_QUERIES },
113 { OPT_PAYMENT_SECRET, OPT_VAR_ONION },
114 { OPT_BASIC_MPP, OPT_PAYMENT_SECRET },
115 /* BOLT #9:
116 * Name | Description | Context | Dependencies |
117 *...
118 * `option_anchor_outputs` | ... | ... | `option_static_remotekey`
119 */
120 { OPT_ANCHOR_OUTPUTS, OPT_STATIC_REMOTEKEY },
121 /* BOLT-f53ca2301232db780843e894f55d95d512f297f9 #9:
122 * Name | Description | Context | Dependencies |
123 * ...
124 * `option_dual_fund` | ... | ... | `option_anchor_outputs`
125 */
126 { OPT_DUAL_FUND, OPT_ANCHOR_OUTPUTS },
127 };
128
trim_features(u8 ** features)129 static void trim_features(u8 **features)
130 {
131 size_t trim, len = tal_bytelen(*features);
132
133 /* Don't try to tal_resize a NULL array */
134 if (len == 0)
135 return;
136
137 /* Big-endian bitfields are weird, but it means we trim
138 * from the front: */
139 for (trim = 0; trim < len && (*features)[trim] == 0; trim++);
140 memmove(*features, *features + trim, len - trim);
141 tal_resize(features, len - trim);
142 }
143
clear_feature_bit(u8 * features,u32 bit)144 static void clear_feature_bit(u8 *features, u32 bit)
145 {
146 size_t bytenum = bit / 8, bitnum = bit % 8, len = tal_count(features);
147
148 if (bytenum >= len)
149 return;
150
151 features[len - 1 - bytenum] &= ~(1 << bitnum);
152 }
153
feature_copy_style(u32 f,enum feature_place p)154 static enum feature_copy_style feature_copy_style(u32 f, enum feature_place p)
155 {
156 for (size_t i = 0; i < ARRAY_SIZE(feature_styles); i++) {
157 if (feature_styles[i].bit == COMPULSORY_FEATURE(f))
158 return feature_styles[i].copy_style[p];
159 }
160 abort();
161 }
162
feature_set_for_feature(const tal_t * ctx,int feature)163 struct feature_set *feature_set_for_feature(const tal_t *ctx, int feature)
164 {
165 struct feature_set *fs = tal(ctx, struct feature_set);
166
167 for (size_t i = 0; i < ARRAY_SIZE(fs->bits); i++) {
168 fs->bits[i] = tal_arr(fs, u8, 0);
169 switch (feature_copy_style(feature, i)) {
170 case FEATURE_DONT_REPRESENT:
171 continue;
172 case FEATURE_REPRESENT:
173 set_feature_bit(&fs->bits[i], feature);
174 continue;
175 case FEATURE_REPRESENT_AS_OPTIONAL:
176 set_feature_bit(&fs->bits[i], OPTIONAL_FEATURE(feature));
177 continue;
178 }
179 abort();
180 }
181 return fs;
182 }
183
feature_set_or(struct feature_set * a,const struct feature_set * b TAKES)184 bool feature_set_or(struct feature_set *a,
185 const struct feature_set *b TAKES)
186 {
187 /* Check first, before we change anything! */
188 for (size_t i = 0; i < ARRAY_SIZE(b->bits); i++) {
189 /* FIXME: We could allow a plugin to upgrade an optional feature
190 * to a compulsory one? */
191 for (size_t j = 0; j < tal_bytelen(b->bits[i])*8; j++) {
192 if (feature_is_set(b->bits[i], j)
193 && feature_offered(a->bits[i], j)) {
194 if (taken(b))
195 tal_free(b);
196 return false;
197 }
198 }
199 }
200
201 for (size_t i = 0; i < ARRAY_SIZE(a->bits); i++) {
202 for (size_t j = 0; j < tal_bytelen(b->bits[i])*8; j++) {
203 if (feature_is_set(b->bits[i], j))
204 set_feature_bit(&a->bits[i], j);
205 }
206 }
207
208 if (taken(b))
209 tal_free(b);
210 return true;
211 }
212
feature_set_sub(struct feature_set * a,const struct feature_set * b TAKES)213 bool feature_set_sub(struct feature_set *a,
214 const struct feature_set *b TAKES)
215 {
216 /* Check first, before we change anything! */
217 for (size_t i = 0; i < ARRAY_SIZE(b->bits); i++) {
218 for (size_t j = 0; j < tal_bytelen(b->bits[i])*8; j++) {
219 if (feature_is_set(b->bits[i], j)
220 && !feature_offered(a->bits[i], j)) {
221 if (taken(b))
222 tal_free(b);
223 return false;
224 }
225 }
226 }
227
228 for (size_t i = 0; i < ARRAY_SIZE(a->bits); i++) {
229 for (size_t j = 0; j < tal_bytelen(b->bits[i])*8; j++) {
230 if (feature_is_set(b->bits[i], j))
231 clear_feature_bit(a->bits[i], j);
232 }
233 trim_features(&a->bits[i]);
234 }
235
236
237 if (taken(b))
238 tal_free(b);
239 return true;
240 }
241
242 /* BOLT #1:
243 *
244 * All data fields are unsigned big-endian unless otherwise specified.
245 */
set_feature_bit(u8 ** ptr,u32 bit)246 void set_feature_bit(u8 **ptr, u32 bit)
247 {
248 size_t len = tal_count(*ptr);
249 if (bit / 8 >= len) {
250 size_t newlen = (bit / 8) + 1;
251 u8 *newarr = tal_arrz(tal_parent(*ptr), u8, newlen);
252 memcpy(newarr + (newlen - len), *ptr, len);
253 tal_free(*ptr);
254 *ptr = newarr;
255 len = newlen;
256 }
257 (*ptr)[len - 1 - bit / 8] |= (1 << (bit % 8));
258 }
259
test_bit(const u8 * features,size_t byte,unsigned int bit)260 static bool test_bit(const u8 *features, size_t byte, unsigned int bit)
261 {
262 assert(byte < tal_count(features));
263 return features[tal_count(features) - 1 - byte] & (1 << (bit % 8));
264 }
265
266 /* BOLT #7:
267 *
268 * - MUST set `features` based on what features were negotiated for this channel, according to [BOLT #9](09-features.md#assigned-features-flags)
269 * - MUST set `len` to the minimum length required to hold the `features` bits
270 * it sets.
271 */
get_agreed_channelfeatures(const tal_t * ctx,const struct feature_set * our_features,const u8 * their_features)272 u8 *get_agreed_channelfeatures(const tal_t *ctx,
273 const struct feature_set *our_features,
274 const u8 *their_features)
275 {
276 u8 *f = tal_dup_talarr(ctx, u8, our_features->bits[CHANNEL_FEATURE]);
277 size_t max_len = 0;
278
279 /* Clear any features which they didn't offer too */
280 for (size_t i = 0; i < 8 * tal_count(f); i += 2) {
281 if (!feature_offered(f, i))
282 continue;
283 if (!feature_offered(their_features, i)) {
284 clear_feature_bit(f, COMPULSORY_FEATURE(i));
285 clear_feature_bit(f, OPTIONAL_FEATURE(i));
286 trim_features(&f);
287 continue;
288 }
289 max_len = (i / 8) + 1;
290 }
291
292 /* Trim to length (unless it's already NULL). */
293 if (f)
294 tal_resize(&f, max_len);
295 return f;
296 }
297
feature_is_set(const u8 * features,size_t bit)298 bool feature_is_set(const u8 *features, size_t bit)
299 {
300 size_t bytenum = bit / 8;
301
302 if (bytenum >= tal_count(features))
303 return false;
304
305 return test_bit(features, bytenum, bit % 8);
306 }
307
feature_offered(const u8 * features,size_t f)308 bool feature_offered(const u8 *features, size_t f)
309 {
310 return feature_is_set(features, COMPULSORY_FEATURE(f))
311 || feature_is_set(features, OPTIONAL_FEATURE(f));
312 }
313
feature_negotiated(const struct feature_set * our_features,const u8 * their_features,size_t f)314 bool feature_negotiated(const struct feature_set *our_features,
315 const u8 *their_features, size_t f)
316 {
317 return feature_offered(their_features, f)
318 && feature_offered(our_features->bits[INIT_FEATURE], f);
319 }
320
feature_check_depends(const u8 * their_features,size_t * depender,size_t * missing_dependency)321 bool feature_check_depends(const u8 *their_features,
322 size_t *depender, size_t *missing_dependency)
323 {
324 for (size_t i = 0; i < ARRAY_SIZE(feature_deps); i++) {
325 if (!feature_offered(their_features, feature_deps[i].depender))
326 continue;
327 if (feature_offered(their_features,
328 feature_deps[i].must_also_have))
329 continue;
330 *depender = feature_deps[i].depender;
331 *missing_dependency = feature_deps[i].must_also_have;
332 return false;
333 }
334 return true;
335 }
336
337 /**
338 * all_supported_features - Check if we support what's being asked
339 *
340 * Given the features vector that the remote connection is expecting
341 * from us, we check to see if we support all even bit features, i.e.,
342 * the required features.
343 *
344 * @bitmap: the features bitmap the peer is asking for
345 *
346 * Returns -1 on success, or first unsupported feature.
347 */
all_supported_features(const struct feature_set * our_features,const u8 * bitmap,enum feature_place p)348 static int all_supported_features(const struct feature_set *our_features,
349 const u8 *bitmap,
350 enum feature_place p)
351 {
352 size_t len = tal_count(bitmap) * 8;
353
354 /* It's OK to be odd: only check even bits. */
355 for (size_t bitnum = 0; bitnum < len; bitnum += 2) {
356 if (!test_bit(bitmap, bitnum/8, bitnum%8))
357 continue;
358
359 if (feature_offered(our_features->bits[p], bitnum))
360 continue;
361
362 return bitnum;
363 }
364 return -1;
365 }
366
features_unsupported(const struct feature_set * our_features,const u8 * their_features,enum feature_place p)367 int features_unsupported(const struct feature_set *our_features,
368 const u8 *their_features,
369 enum feature_place p)
370 {
371 /* BIT 2 would logically be "compulsory initial_routing_sync", but
372 * that does not exist, so we special case it. */
373 if (feature_is_set(their_features,
374 COMPULSORY_FEATURE(OPT_INITIAL_ROUTING_SYNC)))
375 return COMPULSORY_FEATURE(OPT_INITIAL_ROUTING_SYNC);
376
377 return all_supported_features(our_features, their_features, p);
378 }
379
feature_name(const tal_t * ctx,size_t f)380 const char *feature_name(const tal_t *ctx, size_t f)
381 {
382 static const char *fnames[] = {
383 "option_data_loss_protect", /* 0/1 */
384 "option_initial_routing_sync",
385 "option_upfront_shutdown_script",
386 "option_gossip_queries",
387 "option_var_onion_optin",
388 "option_gossip_queries_ex", /* 10/11 */
389 "option_static_remotekey",
390 "option_payment_secret",
391 "option_basic_mpp",
392 "option_support_large_channel",
393 "option_anchor_outputs", /* 20/21 */
394 "option_anchors_zero_fee_htlc_tx",
395 "option_trampoline_routing", /* https://github.com/lightningnetwork/lightning-rfc/pull/836 */
396 "option_shutdown_anysegwit",
397 "option_dual_fund",
398 "option_amp", /* 30/31 */ /* https://github.com/lightningnetwork/lightning-rfc/pull/658 */
399 NULL,
400 "option_quiesce", /* https://github.com/lightningnetwork/lightning-rfc/pull/869 */
401 NULL,
402 "option_onion_messages", /* https://github.com/lightningnetwork/lightning-rfc/pull/759 */
403 "option_want_peer_backup", /* 40/41 */ /* https://github.com/lightningnetwork/lightning-rfc/pull/881 */
404 "option_provide_peer_backup", /* https://github.com/lightningnetwork/lightning-rfc/pull/881 */
405 NULL,
406 NULL,
407 NULL,
408 NULL, /* 50/51 */
409 NULL,
410 "option_keysend",
411 NULL,
412 NULL,
413 NULL, /* 60/61 */
414 NULL,
415 NULL,
416 NULL,
417 NULL,
418 NULL, /* 70/71 */
419 NULL,
420 NULL,
421 NULL,
422 NULL,
423 NULL, /* 80/81 */
424 NULL,
425 NULL,
426 NULL,
427 NULL,
428 NULL, /* 90/91 */
429 NULL,
430 NULL,
431 NULL,
432 NULL,
433 NULL, /* 100/101 */
434 };
435
436 if (f / 2 >= ARRAY_SIZE(fnames) || !fnames[f / 2])
437 return tal_fmt(ctx, "option_unknown_%zu/%s",
438 COMPULSORY_FEATURE(f), (f & 1) ? "odd" : "even");
439
440 return tal_fmt(ctx, "%s/%s",
441 fnames[f / 2], (f & 1) ? "odd" : "even");
442 }
443
list_supported_features(const tal_t * ctx,const struct feature_set * fset)444 const char **list_supported_features(const tal_t *ctx,
445 const struct feature_set *fset)
446 {
447 const char **list = tal_arr(ctx, const char *, 0);
448
449 for (size_t i = 0; i < tal_bytelen(fset->bits[INIT_FEATURE]) * 8; i++) {
450 if (test_bit(fset->bits[INIT_FEATURE], i / 8, i % 8))
451 tal_arr_expand(&list, feature_name(list, i));
452 }
453
454 return list;
455 }
456
featurebits_or(const tal_t * ctx,const u8 * f1 TAKES,const u8 * f2 TAKES)457 u8 *featurebits_or(const tal_t *ctx, const u8 *f1 TAKES, const u8 *f2 TAKES)
458 {
459 size_t l1 = tal_bytelen(f1), l2 = tal_bytelen(f2);
460 u8 *result;
461
462 /* Easier if f2 is shorter. */
463 if (l1 < l2)
464 return featurebits_or(ctx, f2, f1);
465
466 assert(l2 <= l1);
467 result = tal_dup_arr(ctx, u8, f1, l1, 0);
468
469 /* Note: features are packed to the end of the bitmap */
470 for (size_t i = 0; i < l2; i++)
471 result[l1 - l2 + i] |= f2[i];
472
473 /* Cleanup the featurebits if we were told to do so. */
474 if (taken(f2))
475 tal_free(f2);
476
477 return result;
478 }
479
featurebits_eq(const u8 * f1,const u8 * f2)480 bool featurebits_eq(const u8 *f1, const u8 *f2)
481 {
482 size_t len = tal_bytelen(f1);
483
484 if (tal_bytelen(f2) > len)
485 len = tal_bytelen(f2);
486
487 for (size_t i = 0; i < len * 8; i++) {
488 if (feature_is_set(f1, i) != feature_is_set(f2, i))
489 return false;
490 }
491 return true;
492 }
493
fromwire_feature_set(const tal_t * ctx,const u8 ** cursor,size_t * max)494 struct feature_set *fromwire_feature_set(const tal_t *ctx,
495 const u8 **cursor, size_t *max)
496 {
497 struct feature_set *fset = tal(ctx, struct feature_set);
498
499 for (size_t i = 0; i < ARRAY_SIZE(fset->bits); i++)
500 fset->bits[i] = fromwire_tal_arrn(fset, cursor, max,
501 fromwire_u16(cursor, max));
502
503 if (!*cursor)
504 return tal_free(fset);
505 return fset;
506 }
507
towire_feature_set(u8 ** pptr,const struct feature_set * fset)508 void towire_feature_set(u8 **pptr, const struct feature_set *fset)
509 {
510 for (size_t i = 0; i < ARRAY_SIZE(fset->bits); i++) {
511 towire_u16(pptr, tal_bytelen(fset->bits[i]));
512 towire_u8_array(pptr, fset->bits[i], tal_bytelen(fset->bits[i]));
513 }
514 }
515
fmt_featurebits(const tal_t * ctx,const u8 * featurebits)516 const char *fmt_featurebits(const tal_t *ctx, const u8 *featurebits)
517 {
518 size_t size = tal_count(featurebits);
519 char *fmt = tal_strdup(ctx, "");
520 const char *prefix = "";
521
522 for (size_t i = 0; i < size * 8; i++) {
523 if (feature_is_set(featurebits, i)) {
524 tal_append_fmt(&fmt, "%s%zu", prefix, i);
525 prefix = ",";
526 }
527 }
528 return fmt;
529 }
530