search

lightningnetwork / lnd

Lightning Network Daemon ⚡️
MIT License
7.64k stars 2.07k forks source link

Off-by-one mistake in shachain implementation #4916

Open LLFourn opened 3 years ago

LLFourn commented 3 years ago

I've been reviewing implementations of the "shachain" trick from BOLT03.

There seems to be an implementation mistake in LND here: https://github.com/lightningnetwork/lnd/blob/1a73bc7d7407bcbf43886d9855dd95e747a798b0/shachain/store.go#L49

maxHeight is set to 48 which means this array will have 48 elements. However, in the spec this array should have 49 elements because it counts the number of leading zeros. A 48 bit number can have 0 to 48 leading zeros inclusive which means 49 possible values. For comparison see c-lightning (note the +1 there).

I speculate that it is possible to induce an error in an LND peer by getting to index 0 (the last index) which has 48 trailing zeros. This will then hit this line of code and get an index out of range error.

I guess it is difficult to actually hit 2^48 channel revocations so this problem does not represent a realistic issue for the next few decades!

Roasbeef commented 3 years ago

Thanks for pointing this out! As you mentioned, in practice this doesn't really matter unless a channel is somehow "advanced" towards the end of a shachain state before it's used. We should be able to patch this just by adding a +1 there as our serialization code reads the total number of live buckets rather than filling out space of the unused buckets.