Add random 'shadow route' CLTV delta offsets to improve privacy. #1286

tnull · 2022-01-27T10:48:00Z

This PR is an attempt to address #158.

In order to generate a plausible CLTV delta offset, a three-hop random walk starting from the payee is conducted and cltv_expiry_delta values are aggregated. This offset is then added to all but the final hop of the selected paths (since the last hop knows anyways that it is the recipient).

Tests are currently failing since they of course do not expect the randomly added offset. I'll fix them when someone had a look at the implementation itself.

TheBlueMatt

Sorry for the delay on this one! A few comments, don't worry about the failing tests for now, I can help out with those if needed.

lightning-invoice/src/utils.rs

lightning/src/routing/router.rs

tnull · 2022-02-04T14:12:45Z

Addressed comments and rebased off a1fedea.

lightning/src/routing/router.rs

lightning/src/util/mod.rs

lightning/src/routing/router.rs

ariard · 2022-02-14T23:27:41Z

lightning/src/routing/router.rs

+					if let Some(random_index) = usize::from_be_bytes(random_path_bytes).checked_rem(cur_node.channels.len()) {
+						if let Some(random_channel_id) = cur_node.channels.get(random_index) {
+							if let Some(random_channel) = network_channels.get(random_channel_id) {
+								if random_channel.node_one == cur_node_id {


One improvement, I think if the randomly selected next hop is actually part of the extended payment path you could pick up another hop to pursue the random walk. What we would like to avoid is the random walk rolling back on the actually drawn out path. Let's say you have A -> B -> C -> D and you sort the random walk D -> C -> B -> A thus a shadow offset partially overlapping with the real cltv deltas. I would say it's a low-probability phenomena but the last publicly known node might not have numerous public channels opened for routing.

That said, it might not be worthy the effort at that point.

Thank you very much for having a look at this! Could you elaborate why we wouldn't want the shadow route to overlap the actual path? I see this only as a problem if we assume an on-path adversary that can say for sure that it wasn't part of the actual payment path and hence might be able to reduce the number of candidate routes. However, if we exclude overlapping paths from the beginning, we might reduce the randomness from the getgo, making any adversary's life easier?

I'm not sure if its worth the effort to implement this, but I see a few concerns with overlapping paths. eg if you're an attacker and the CLTV deltas only line up with one path, and it overlaps/backtraces, you know for sure that that is shadow route, because the normal routing algorithm won't exhibit that behavior.

Hum, I think it may not be worth to rule out any overlap, since this could indeed reduce the variety of potential random walks quite a bit. But maybe it would be enough to ensure that we do not immediately loop back on the actual path. And in the case this excludes the only public edge we could fall back to a 'synthetic' random offset, just as in the case for fully private paths.

Yea, I'll leave it up to you. I don't care too much because so many nodes use the same CLTV delta that its probably all the same in practice, but if its easy to avoid the same-node-backtrack then feel free to add it.

I think I'm leaning on the side of leaving this as-is for now and potentially having another look at it in a potential follow-up PR. We might want to have a follow-up anyways, for example in order to introduce some kind of value obfuscation, as noted in #158.

Yeah really up to you, fine to leave it as a follow-up.

lightning/src/routing/router.rs

TheBlueMatt · 2022-02-15T21:56:11Z

Looks like this needs rebase, sorry about that.

tnull · 2022-02-16T08:18:33Z

Looks like this needs rebase, sorry about that.

Rebased.

TheBlueMatt

I'm basically happy with this. There's some compilation errors due to new tests that weren't updated on rebase and the benchmark-only code needs updating, I believe. I'm happy to help resolve any test failures left after that.

lightning/src/routing/router.rs

TheBlueMatt · 2022-02-21T22:33:19Z

To make the router tests pass, maybe it'd be best to split get_route into two methods, one that gets the route and one that applies the CLTV deltas so that you don't have to update all the tests.

tnull · 2022-02-22T10:41:22Z

To make the router tests pass, maybe it'd be best to split get_route into two methods, one that gets the route and one that applies the CLTV deltas so that you don't have to update all the tests.

Good idea, especially given that get_route is ~1000 lines already. I now split adding the offset to its dedicated add_random_cltv_offset method and added a test.

For the time being I left random_seed_bytes as a parameter to get_route instead of removing it and all the changes to the test etc. I think it could be used to implement the 'real' random shuffle in Step (6). If that is wanted I can add this to this PR or open a follow-up.

codecov-commenter · 2022-02-22T11:58:31Z

Codecov Report

Merging #1286 (e92b5a7) into main (af99a94) will decrease coverage by 0.14%.
The diff coverage is 95.26%.

@@            Coverage Diff             @@
##             main    #1286      +/-   ##
==========================================
- Coverage   90.75%   90.60%   -0.15%     
==========================================
  Files          72       72              
  Lines       42254    40324    -1930     
==========================================
- Hits        38347    36536    -1811     
+ Misses       3907     3788     -119

Impacted Files	Coverage Δ
lightning-invoice/src/utils.rs	`86.92% <58.33%> (-1.22%)`	⬇️
lightning/src/ln/channelmanager.rs	`84.61% <87.50%> (-1.52%)`	⬇️
lightning/src/routing/network_graph.rs	`89.52% <88.88%> (-0.01%)`	⬇️
lightning/src/routing/router.rs	`92.39% <96.15%> (+0.29%)`	⬆️
lightning/src/routing/scoring.rs	`94.29% <96.96%> (-1.13%)`	⬇️
lightning-background-processor/src/lib.rs	`93.10% <100.00%> (+0.05%)`	⬆️
lightning/src/ln/functional_test_utils.rs	`95.32% <100.00%> (+0.03%)`	⬆️
lightning/src/ln/functional_tests.rs	`97.13% <100.00%> (+0.36%)`	⬆️
lightning/src/ln/onion_route_tests.rs	`97.62% <100.00%> (ø)`
lightning/src/ln/payment_tests.rs	`99.15% <100.00%> (+<0.01%)`	⬆️
... and 8 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 1a73449...e92b5a7. Read the comment docs.

lightning/src/routing/router.rs

TheBlueMatt · 2022-02-22T16:34:36Z

Feel free to squash the commits down to one or two, note that we'd ideally like to ensure all code compiles and all tests pass after each commit.

tnull · 2022-02-22T18:00:11Z

Feel free to squash the commits down to one or two, note that we'd ideally like to ensure all code compiles and all tests pass after each commit.

Sure sure, just wanted to avoid squashing too early. Rebased and squashed with 67137c6.

TheBlueMatt

Some style nits and minor test comments.

fuzz/src/router.rs

fuzz/src/full_stack.rs

lightning-invoice/src/utils.rs

TheBlueMatt · 2022-02-22T21:00:24Z

lightning-invoice/src/utils.rs

+		) -> Result<Route, LightningError> {
+		let mut locked_random_seed_bytes = self.random_seed_bytes.lock().unwrap();
+		*locked_random_seed_bytes = sha256::Hash::hash(&*locked_random_seed_bytes).into_inner();
+		find_route(payer, params, &*self.network_graph, first_hops, &*self.logger, scorer, &locked_random_seed_bytes.clone())


As is the lock is held through find_route which we maybe don't want. Instead, we'll need an explicit {} scope to tell the compiler where to drop the locked_random_seed_bytes

Should we consider parameterizing DefaultRouter by K: Deref where K::Target: KeysInterface and call get_secure_random_bytes each time? I suppose the interface is too broad, but I wonder if a narrower Randomness interface is warranted. No strong opinion here, but it would avoid the mutex.

I now went the scoping route with 386a0b5. However, I agree that introducing a Randomness interface (not only here) would be a nicer abstraction than pushing around arrays with random_seed_bytes. Possibly a good follow-up PR?

I suppose we could, yea, agree we'd want to do it in a followup, though. I'm a little hesitant to replace a trivial parameter with a full interface, though, as it just seems like overkill, but we can discuss that later.

lightning/src/routing/router.rs

lightning/src/routing/scoring.rs

lightning/src/routing/router.rs

lightning-background-processor/src/lib.rs

jkczyz · 2022-02-22T23:04:00Z

lightning-invoice/src/utils.rs

+		) -> Result<Route, LightningError> {
+		let mut locked_random_seed_bytes = self.random_seed_bytes.lock().unwrap();
+		*locked_random_seed_bytes = sha256::Hash::hash(&*locked_random_seed_bytes).into_inner();
+		find_route(payer, params, &*self.network_graph, first_hops, &*self.logger, scorer, &locked_random_seed_bytes.clone())


Should we consider parameterizing DefaultRouter by K: Deref where K::Target: KeysInterface and call get_secure_random_bytes each time? I suppose the interface is too broad, but I wonder if a narrower Randomness interface is warranted. No strong opinion here, but it would avoid the mutex.

lightning/src/ln/channelmanager.rs

lightning/src/ln/functional_test_utils.rs

lightning/src/ln/payment_tests.rs

lightning/src/routing/router.rs

ariard

Good with the new approach of only offsetting the final hop.
(Thought the old one had the benefit to also mask the sender topology as the intermediate node couldn't deduce from their CLTV deltas the distance from sender, I believe)

lightning/src/routing/router.rs

tnull · 2022-02-24T16:08:28Z

Thanks for all the great feedback, I'll take it into account going forward!

lightning/src/routing/router.rs

TheBlueMatt · 2022-02-25T23:54:39Z

lightning/src/routing/router.rs

+		// Limit the offset so we never exceed the max_total_cltv_expiry_delta
+		let max_path_offset = payment_params.max_total_cltv_expiry_delta
+			.checked_sub(path.iter().map(|h| h.cltv_expiry_delta).sum())
+			.unwrap_or(shadow_ctlv_expiry_delta_offset);


Shouldn't this be unwrap_or(0)? If our path expiry is more than the max already we probably shouldn't add an offset at all? Also, were we planning on limiting the total CLTV during the get_route run to give us a little headroom here?

Well my thinking here was that since we limit the route overall with max_total_cltv_expiry_delta, this subtraction should never fail. If however something unexpected were to happen and it would fail, we might be better off to default to provide some privacy (capped at 3*144), instead of none. But it can of course also default to 0, I have no strong preference here.

As for the considering the offset in get_route: after looking at the data I found that there were basically no cases in which there was not ample room to add the offset and hence thought it would be cleaner not to interfere with pathfinding and keep the two methods entirely separate. However, if we still want to take some of the offset into account, I can of course go back to, for example, subtracting 2*40 or 2*144 from the limit during path finding.

Well my thinking here was that since we limit the route overall with max_total_cltv_expiry_delta, this subtraction should never fail.

Right, sorry, indeed.

If however something unexpected were to happen and it would fail, we might be better off to default to provide some privacy (capped at 3*144), instead of none.

🤷‍♂️ I guess we shouldn't ever violate the user-provided value ever?

As for the considering the offset in get_route: #1286 (comment) I found that there were basically no cases in which there was not ample room to add the offset and hence thought it would be cleaner not to interfere with pathfinding and keep the two methods entirely separate.

Hmm, I feel like that's a better reason to interfere than to not interfere.

I'm still a bit confused by this hunk here - why do we do the subtraction at max_path_offset.checked_sub(max_path_offset.wrapping_rem(40))?

🤷‍♂️ I guess we shouldn't ever violate the user-provided value ever?
...
Hmm, I feel like that's a better reason to interfere than to not interfere.

Alright, both addressed by f7be9da.

I'm still a bit confused by this hunk here - why do we do the subtraction at max_path_offset.checked_sub(max_path_offset.wrapping_rem(40))?

The difference of the path total to max_total_cltv_expiry_delta may be a pretty uncommon value, which could result in an implausible shadow route offset. The thinking here therefore was to choose the path offset to be the closest multiple of 40 to increase plausibility. I now had another look at this part and added a comment to make this more transparent in f7be9da.

lightning/src/routing/network_graph.rs

lightning-invoice/src/utils.rs

lightning/src/routing/router.rs

tnull · 2022-02-28T21:29:58Z

Rebased and squashed once more.

jkczyz · 2022-02-28T22:46:33Z

lightning/src/routing/router.rs

-	logger: L, scorer: &S
+	our_node_pubkey: &PublicKey, payment_params: &PaymentParameters, network_graph: &ReadOnlyNetworkGraph,
+	first_hops: Option<&[&ChannelDetails]>, final_value_msat: u64, final_cltv_expiry_delta: u32,
+	logger: L, scorer: &S, random_seed_bytes: &[u8; 32]


random_seed_bytes is not needed here since it is only used in add_random_cltv_offset.

This is correct. If however possible, I’d like to leave it in get_route for now and use it to implement the 'real random shuffle' TODO in a follow-up PR. I now prefixed it with an underscore to disable the warning, but let me know if you'd rather keep it out of get_route altogether in this PR.

hey @tnull is it okay if I take a stab at implementing the real random shuffle? I believe it may be related to this issue #869

hey @tnull is it okay if I take a stab at implementing the real random shuffle? I believe it may be related to this issue #869

Ah, thank you for the interest! This issue indeed seems related. However, I’m already mostly done with a first draft and plan to open a PR in the next few days.

fuzz/src/router.rs

lightning/src/routing/network_graph.rs

jkczyz · 2022-03-01T19:16:01Z

lightning/src/routing/router.rs

+		max_path_offset = max_path_offset
+			.wrapping_sub(max_path_offset.wrapping_rem(MEDIAN_HOP_CLTV_EXPIRY_DELTA))
+			.max(max_path_offset.wrapping_rem(MEDIAN_HOP_CLTV_EXPIRY_DELTA));
+		shadow_ctlv_expiry_delta_offset = cmp::min(shadow_ctlv_expiry_delta_offset, max_path_offset);


If the subtraction wraps, shadow_ctlv_expiry_delta_offset would not likely change, IIUC. Could it then possibly exceed payment_params.max_total_cltv_expiry_delta for small values?

Hum, I'm not entirely sure if I'm understanding you correctly. The wrapping_sub should actually never wrap due to x >= x mod y. I made this a bit more explicit by using saturating_sub in 0b777cb.
Moreover, the line prior ensures that max_path_offset is never larger than max_total_cltv_expiry_delta and all changes from there only ever would reduce it further.

lightning/src/routing/router.rs

tnull · 2022-03-09T17:26:15Z

Rebased.

TheBlueMatt reviewed Jan 31, 2022

View reviewed changes

lightning-invoice/src/utils.rs Outdated Show resolved Hide resolved

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

tnull force-pushed the add_random_cltv_offsets branch from 87fc7d4 to ea0ad9d Compare February 4, 2022 14:08

tnull commented Feb 4, 2022

View reviewed changes

lightning/src/routing/router.rs Show resolved Hide resolved

TheBlueMatt reviewed Feb 4, 2022

View reviewed changes

lightning/src/util/mod.rs Outdated Show resolved Hide resolved

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

lightning/src/routing/router.rs Show resolved Hide resolved

tnull force-pushed the add_random_cltv_offsets branch from 251374f to f6793ab Compare February 7, 2022 12:35

ariard reviewed Feb 14, 2022

View reviewed changes

tnull force-pushed the add_random_cltv_offsets branch from 3794bf6 to 803348f Compare February 16, 2022 08:17

tnull force-pushed the add_random_cltv_offsets branch from 803348f to 4e9cb21 Compare February 18, 2022 13:47

TheBlueMatt reviewed Feb 18, 2022

View reviewed changes

lightning/src/routing/router.rs Show resolved Hide resolved

jkczyz self-requested a review February 18, 2022 18:57

tnull force-pushed the add_random_cltv_offsets branch from ea06afb to 28cebe1 Compare February 21, 2022 12:58

tnull force-pushed the add_random_cltv_offsets branch from 78e9dcd to a20cd5c Compare February 22, 2022 10:19

tnull commented Feb 22, 2022

View reviewed changes

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

tnull force-pushed the add_random_cltv_offsets branch from c0657fd to 67137c6 Compare February 22, 2022 17:57

TheBlueMatt added the Seeking Code Review label Feb 22, 2022

TheBlueMatt reviewed Feb 22, 2022

View reviewed changes

jkczyz reviewed Feb 22, 2022

View reviewed changes

ariard reviewed Feb 23, 2022

View reviewed changes

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

TheBlueMatt removed the Seeking Code Review label Feb 23, 2022

tnull force-pushed the add_random_cltv_offsets branch 2 times, most recently from 386a0b5 to 01bccc4 Compare February 24, 2022 16:06

tnull force-pushed the add_random_cltv_offsets branch from 22b4eeb to ee58764 Compare February 25, 2022 11:51

TheBlueMatt reviewed Feb 25, 2022

View reviewed changes

tnull force-pushed the add_random_cltv_offsets branch from f7be9da to 773e76b Compare February 27, 2022 09:07

jkczyz reviewed Feb 28, 2022

View reviewed changes

tnull force-pushed the add_random_cltv_offsets branch 3 times, most recently from 09c262f to a6f241c Compare February 28, 2022 21:28

jkczyz reviewed Feb 28, 2022

View reviewed changes

tnull force-pushed the add_random_cltv_offsets branch from a6f241c to f5b1b46 Compare March 1, 2022 08:45

jkczyz reviewed Mar 1, 2022

View reviewed changes

tnull force-pushed the add_random_cltv_offsets branch 3 times, most recently from 0b777cb to 5731df3 Compare March 4, 2022 12:47

TheBlueMatt previously approved these changes Mar 7, 2022

View reviewed changes

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

tnull dismissed TheBlueMatt’s stale review via e2efb0c March 7, 2022 16:37

tnull force-pushed the add_random_cltv_offsets branch from 5731df3 to e2efb0c Compare March 7, 2022 16:37

TheBlueMatt previously approved these changes Mar 7, 2022

View reviewed changes

jkczyz added this to the 0.0.106 milestone Mar 7, 2022

Add a random per-path CLTV offset for privacy.

e92b5a7

tnull dismissed TheBlueMatt’s stale review via e92b5a7 March 9, 2022 17:23

tnull force-pushed the add_random_cltv_offsets branch from e2efb0c to e92b5a7 Compare March 9, 2022 17:23

TheBlueMatt approved these changes Mar 9, 2022

View reviewed changes

jkczyz approved these changes Mar 9, 2022

View reviewed changes

jkczyz merged commit a50e954 into lightningdevkit:main Mar 9, 2022

tnull deleted the add_random_cltv_offsets branch March 9, 2022 22:45

This was referenced Mar 10, 2022

Randomize candidate paths during route selection. #1359

Merged

Avoid looping CLTV shadow routes. #1360

Merged

TheBlueMatt mentioned this pull request May 13, 2022

Add random CLTV offsets (or max CLTV offsets) during route calculation #158

Closed

Add random 'shadow route' CLTV delta offsets to improve privacy. #1286

Add random 'shadow route' CLTV delta offsets to improve privacy. #1286

Conversation

tnull commented Jan 27, 2022

TheBlueMatt left a comment

Choose a reason for hiding this comment

tnull commented Feb 4, 2022 • edited

ariard Feb 14, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

TheBlueMatt commented Feb 15, 2022

tnull commented Feb 16, 2022

TheBlueMatt left a comment

Choose a reason for hiding this comment

TheBlueMatt commented Feb 21, 2022

tnull commented Feb 22, 2022 • edited

codecov-commenter commented Feb 22, 2022 • edited

Codecov Report

TheBlueMatt commented Feb 22, 2022

tnull commented Feb 22, 2022

TheBlueMatt left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ariard left a comment

Choose a reason for hiding this comment

tnull commented Feb 24, 2022

Choose a reason for hiding this comment

tnull Feb 26, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

tnull Feb 27, 2022 • edited

Choose a reason for hiding this comment

tnull commented Feb 28, 2022

Choose a reason for hiding this comment

tnull Mar 1, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

tnull Mar 3, 2022 • edited

Choose a reason for hiding this comment

tnull commented Mar 9, 2022

tnull commented Feb 4, 2022 •

edited

ariard Feb 14, 2022 •

edited

tnull commented Feb 22, 2022 •

edited

codecov-commenter commented Feb 22, 2022 •

edited

tnull Feb 26, 2022 •

edited

tnull Feb 27, 2022 •

edited

tnull Mar 1, 2022 •

edited

tnull Mar 3, 2022 •

edited