Do pools distribute "jobs" to miners based on "failed" solutions which have already been submitted?

Question

My question is this: How exactly does the stratum protocol distribute "work" to miners? More specifically, since mining can be compared (in many regards) to "brute forcing" a cryptographic hash (i.e. hashing random inputs until, by luck, a random input matches a desired output), wouldn't it make sense to keep track of potential solutions submitted and confirmed as invalid for a particular block, and to somehow communicate that to miners so the same work is not being done over and over again?

I realize this would require a lot of overhead, but it would seem worthwhile. Is there any mechanism to ensure two independent miners do not waste time working on the same inputs? Could sending a different seed for random number generation to every miner upon the start of a new round of mining have effect? I've read simplistic descriptions of mining as simply incrementing the nonce until a solution is found, but I've also read much more detailed explanations which would imply much more is involved. Even if only the nonce is changed in the input, the pool would still need to assign each miner a unique nonce to try after each submission, no?

As a final, semi-unrelated question regarding the implications of storing solutions: Say a pool stored every solution it had ever received, considering the massive size of the bitcoin network, would this not eventually become a statistically significant (in terms of usability) database of sha256 collisions? And eventually, could enough data be collected to come up with a derivation for SHA256? At minimum, could a pool with malicious intent temporarily divert unknowing miners's computing power to crack SHA256 based TLS signatures or PGP public keys? Especially a pool which also controlled the hardware and software on the majority of its devices (e.g. Antpool).

Answer 1

I've read simplistic descriptions of mining as simply incrementing the nonce until a solution is found, but I've also read much more detailed explanations which would imply much more is involved. Even if only the nonce is changed in the input, the pool would still need to assign each miner a unique nonce to try after each submission, no?

Miners do change more than just the nonce, and it is this fact that allows a mining pool to ensure that two miners don't produce the same work twice.

Because mining always involves the transactions used in the block, changing those transactions will effect the merkle root and thus the result. One of those transactions is the coinbase transaction which is something that miners have control over. In particular, the input script for the coinbase transaction's input can contain up to 100 bytes of aribtrary data. So miners will use this space as an extra nonce (known as the extranonce). They will have a nonce there too in order produce new coinbase transactions which lets them produce different merkle roots and thus different block headers. The extranonce allows miners to have more nonces than from just the 32 bit nonce in the block header.

Mining pools make use of this extranonce to ensure unique work. They will give a miner part of an extranonce (e.g the first half). Then the miner can use the rest of the extranonce as an extranonce for themselves. This lets miners still have a large search space so that they are not constantly asking the pool for more work. By giving miners different extranonce halves, the pool can be sure that two miners will not be hashing the same thing multiple times.

Say a pool stored every solution it had ever received, considering the massive size of the bitcoin network, would this not eventually become a statistically significant (in terms of usability) database of sha256 collisions?

Eventually, yes. But it's going to be a very long time before that happens. The entire Bitcoin network has done ~2^90 hashes total. However to even get to a 50% chance of a collision, you need ~2^128 hashes. 2^90 is 1/274877906944 of 2^128. So the amount of time to even get to 2^128 hashes is many times the number of years that the universe has even existed. So in theory, yes, there could be enough hashes computed that a collision is found be sheer brute force. But for all intents and purposes, it isn't going to happen.