ElementsProject / ElementsProject/lightning

Deserializing block at height 761249 hangs lightningd for tens of minutes due to quadratic scaling on a tx containing 500003 witnesses

Open
#8,924 7 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.