lnd: [bug]: garbage collect `batch-replay` bucket in `sphinxreplay.db`

Background on replays and how LND handles them:

• What is a replay and why does it matter?

  • A replay is where the same onion packet traverses the same outgoing path, again. We don’t want to relay these packets in case somebody is attempting to determine the path of the HTLC.
  • We can receive a replayed packet on a different channel than the original one it was received from.

• When do replays no longer matter in lnd?

  • When the CLTV of the incoming HTLC has expired. This is because lnd stores the incoming timeout in the sharedHashes bucket.

• Lifetime of a batch:

  • A batch stores the set of replays that have occurred in a particular forwarding package. The key is the ID of the forwarding package. The value is the set of replays that occurred (possible empty).
  • A batch is stored with DecayedLog.PutBatch. This happens when DecodeHopIterators in processRemoteAdds. This may or may not be the first time the function has run.
  • If DecodeHopIterators is called and the batch already exists, the set of replays are fetched and returned. The main purpose of the batch is so that if the link runs DecodeHopIterators again, the set of replays for that forwarding package / batch can be retrieved. This allows the link to fail these HTLCs backwards.
  • The above point means that the batch only matters for the lifetime of the corresponding forwarding package. After that, DecodeHopIterators will never run for the batch ID.

• Forwarding packages are removed when:

  • The link starts up and the state is FwdStateCompleted in resolveFwdPkgs. This might not occur depending on if other links are up and able to receive the add/settle/fail.
  • Periodically during link operation in fwdPkgGarbager if in state FwdStateCompleted. This might not occur depending on if other links are up and able to receive the add/settle/fail.
  • When the channel is closed via Packager.Wipe().

The issue can be solved with a migration and with new non-migration code:

• Migration:
  • For closed channels, delete all batches when the channel doesn’t exist
  • For open channels, delete batches where the forwarding package doesn’t exist
• New code:
  • For closed channels, delete all batches for the channel in the same database transaction. This happens in CloseChannel
  • For open channels, delete the batch when the forwarding transaction is removed. This should be done in the same database transaction.

One thing to note about the above approach is that it’s possible that the batches linger until the channel is closed due to forwarding packages not getting removed. However, there is nothing we can do about this because the link may call DecodeHopIterators again and the batch must exist or else things will break.

Yeah, you’re right. That’s a lot of data. And I think I found the bug. We write to the batch-replay bucket here but we apparently never delete from it. That needs garbage collection as well. Though I’m not familiar with it enough to say whether that’s easy to fix or not.

you’re right it needs to be persisted

Regarding the tests:

If you look at this commit, tests are indeed there. tx.ProcessOnionPacket calls PutBatch. Sure you can argue there should be a lower level tests there, but this were talking about a commit that’s 5 years old. If you wish, you can certainly add a lower level test here yourself (just grasping at straws here tbh).

Regarding empty batches:

Looks like the issue is that when you revoke, you don’t always have new HTLCs to forward, however, this is called unconditionally: https://github.com/lightningnetwork/lnd/blob/f6ae63fd7b53e366f50a96216fb056dd8fb8f4a7/htlcswitch/link.go#L1990-L2049

So that should either just exit early in the func, or only be called if the number of adds is non zero. We can then add an assertion (that we never try to write an empty batch) to catch regressions in the future.

As migrating/GCing the old data seems rather expensive to me, would it be viable to just delete the sphinxreplay.db or empty the offending batch-replay bucket once?

I would not recommend that as I’m not 100% sure of the security implications. I guess you could stop accepting new HTLCs for the number of blocks that correspond to your max channel’s CLTV delta value and then you had some confidence that a replay would fail because of wrong CLTV values. But again, I would not recommend just deleting the file.

OK, I think I got it. If we call PutBatch with two packets a, b twice (for whatever reason) where only b is a replay, for both invocations we need to only return b as a replay. Without the bucket we’d check a and b individually and, for the second invocation, would return both as replays, as now also a was already seen (in the first invocation).

Yes, I saw your PR. But I don’t think we can delete the bucket, we need it to make sure a batch of packages wasn’t relayed before.

I have 612,489 pairs in batch-replay, 31,389 pairs in shared-hash.

I’m going to change the title to indicate this is a bug.

The Sphinx replay DB is lnd’s implementation of the ReplayLog defined in the sphinx packet. It keeps track of onion packets to make sure they aren’t used in a replay attack. Each package is stored with its CLTV and is garbage collected as soon as the CLTV has expired. That means the DB is subject to a lot of reads and writes and therefore does profit from regular compaction.

Can you try compacting it and see if it still stays as as it currently is?

Maybe another option (after compaction) would be to take a look at it with boltbrowser (shut down lnd first, create a copy of the DB file, start lnd again, inspect copy) and check whether there are expired hashes in there? Or maybe there’s some data stored in there in addition to the hashes themselves that aren’t properly garbage collected? I’ll take a look at my DB as well to see if I can identify anything.