Disclaimer: I proposed a partial solution myself to this problem (BIP 143, see below).
Did the miner collude with the creator of the transaction?
Yes, because they are the same person.
It's a transaction that consumes a ton of dust outputs, and converts them to fees, which the miner claimed.
I doubt that the intention was to cause problems; it may just have been an attempt to clean up a lot of dust at once.
However, it did make it more obvious that the theoretical problem of quadratic hashing time for verification of blocks was real. The cause is that every signature requires computing a different hash, and that that hash is computed using the entirety of the transaction as input. Thus, if the number of signature checks in a transaction grows, both the number of hashes to compute as the amount of data each of them needs to hash increases.
Several solutions have been proposed:
- Limiting the maximum size of transactions.
- Limiting the total amount of data hashed by a transaction.
- Changing the way hashes are computed.
1 (and to a lesser extent 2) would harm potentially useful large transactions in the future, depending on what the limits are. In particular, scaling solutions that rely on collapsing multiple payments into a single transaction may get hurt.
Deploying 3 for existing transaction outputs would require a hard fork, and a change to every piece of wallet software. Additionally, it would invalidate any pre-signed but unbroadcast transaction.
However, 3 can be deployed for a new type of transaction output. BIP 143 describes a new signature hashing mechanism that is at worst linear in the size of blocks, but only applies to transaction inputs that spend segregated witness outputs (see BIP 141).