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

[whitslack]

There is a CLN performance bomb buried in the blockchain at height 761249 in transaction 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.

[whitslack]

Oops, I'm Googling now and seeing that this transaction was actually an attack on LND. The message in the OP_RETURN was intended to promote CLN, not to ironically attack it. Well, it turns out that the transaction was pretty brutal to CLN nodes too.

[jgriffiths]

The attack tx (as passive aggressive and misguided as it is) probably predates the addition of wally size checks to avoid memory exhaustion. See the wally issue for more commentary.

[whitslack]

The attack tx (as passive aggressive and misguided as it is) probably predates the addition of wally size checks to avoid memory exhaustion. See the wally issue for more commentary.

@jgriffiths: I don't understand. Are you saying that libwally-core is supposed to refuse to parse a transaction containing 500003 witnesses just because such a transaction is non-standard? It's not in violation of consensus rules, as evidenced by its inclusion in the Mainnet blockchain. I really did run into a half-hour hang of my CLN node today while it was scanning historical blocks to fix up the data damage caused by another bug, and the hang was caused by a bad algorithm in libwally-core, regardless of any "size checks" that may have been instituted before or after the malicious transaction entered the blockchain.

EDIT: I think I understand now after reading the code again. I had not noticed the subtle disregard in wally_tx_witness_stack_init_alloc for the requested allocation length. The function silently disobeys the caller's instructions. Not a good interface! It should return an "invalid argument" error if it doesn't want to allocate a large number of witness stack items. That said, why would you arbitrarily limit an allocation? Imagine if malloc quietly capped all of its allocations at 1 MiB because “no one should need to allocate more than that much memory at once.” Anyway, I think you're saying that, at the time of the attack transaction, libwally-core was not silently capping allocations, so there would not have been any performance issue at that time.

[jgriffiths]

Anyway, I think you're saying that, at the time of the attack transaction, libwally-core was not silently capping allocations, so there would not have been any performance issue at that time.

Correct