ElementsProject / ElementsProject/lightning
Deserializing block at height 761249 hangs lightningd for tens of minutes due to quadratic scaling on a tx containing 500003 witnesses
- Dominant language
- C
- Stars
- 3.1k
- Forks
- 1k
- Avg merge
- 4d 10h
- Merged PRs (30d)
- 13
Description
There is a CLN performance bomb buried in the blockchain at height 761249 in transaction [73be398c4bdc43709db7398106609eea2a7841aaf3a4fa2000dc18184faa2a7e](https://mempool.space/tx/73be398c4bdc43709db7398106609eea2a7841aaf3a4fa2000dc18184faa2a7e). (Click the "Details" button on that mempool.space page if you want to hang your browser too. 😉)
The transaction contains 500003 witnesses and carries an `OP_RETURN` data payload that reads: “you'll run cln. and you'll be happy.” This was clearly a very expensive stunt intended to highlight a performance issue in CLN, but apparently it has gone unreported until now.
The issue appears to be that libwally-core's `wally_tx_witness_stack_set` function expands a heap-allocated array by calling a deceptively named internal function, `array_realloc`, which in fact does not delegate to `reallocarray` as one might expect but rather calls `malloc` to allocate a new chunk of memory and then `memcpy` to copy the existing data into it. (It also does not contain the protection against multiplication overflow that `reallocarray` does!) The pathological transaction at block height 761249 contains 500003 individual witnesses, _each_ of which cause the loop in `wally_tx_witness_stack_set` to expand its array of witness items by _one_ item. **This algorithm scales quadratically.** Oddly, there is another function, right next to `array_realloc`, called `array_grow`, which implements the customary, sane behavior of growing an array by doubling its size. It looks as though `wally_tx_witness_stack_set` ought to be rewritten to use `array_grow` rather than `array_realloc`. It also looks as though the fix would be a one-liner, which makes me suspect that this could have been an _intentionally_ introduced bug.
The function call chain that leads to the hang is:
`getrawblockbyheight_callback` → `bitcoin_block_from_hex` → `pull_wtx` → `wally_tx_from_bytes` → `tx_from_bytes` → `wally_tx_witness_stack_set`
I'll open an issue on libwally-core's tracker too since the fix needs to land there.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.