Block 364422 contains a transaction that takes a long time to verify. This transaction design demonstrates a way a denial of service attack could be executed. This prompted Gavin Andresen to propose additional limits to the protocol.
Gavin talks about this issue in this video.
Is it known who mined this particular block? What was their intention? Did they collude with the person who generated the transaction?
Excellent answer by Pieter Wuille. Pieter just forgot to answer the question of the post title, "Who mined the infamous block 364423?"
Unfortunately, the question is was "wrong": the first two links in the OP's text point at block 364422, not 364423. (edit: meanwhile the OP removed the discrepancy)
Either way, both
Bitcoin blocks 364422 and 364423 had been mined by F2Pool (also called "DiscusFish"). The outputs went to the Bitcoin address 1KFHE7w8BhaENAswwryaoccDb6qcT6DbYY which belongs to F2Pool, see https://github.com/blockchain/Blockchain-Known-Pools/blob/master/pools.json
Both blocks were merged-mined with Namecoin blocks 238371 and 238372 respectively. The coinbase string of Bitcoin block 364422 as well as the auxPoW data in Namecoin block 238371 contain "新視野號距冥王星6951602公里" (Chinese for: "New Horizons' distance to Pluto: 6951602 km"). The coinbase string of Bitcoin block 364423 as well as the auxPoW data in Namecoin block 238372 contain "New Horizons is 6948752 km to Pluto" (this time in English). One of the pool operators at F2Pool wrote a script that inserted the current distance of NASA's New Horizons probe from Pluto into the coinbase string. After the arrival of the NASA probe he removed that script, and the F2Pool coinbase string contains the usual F2Pool info as before. Amongst other data this includes "七彩神仙鱼", "Discus Fish" in Chinese language.
Yes, because they are the same person.
I guess Pieter is refering to Wang Chun. There is a little message in the tx output script: "七彩神仙鱼 🐟 Bitcoin to Pluto!"
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:
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).
