The way I understand their implementation [0] is that the client sha256s their password and sends the first 5 characters, not bytes. The server then responds with all the matching hashes. In the article the example was 477 matching hashes.
So it’s not all possible hashes with that prefix, it’s only the hashes of entries in the known passwords.
If the server was compromised, it would be able to know which users requested which hash prefixes and compare that to the “known hashes” that match that prefix. Not all passwords submitted are matches, but some are. And it’s likely that a users pattern of testing particular hash prefixes could make it much easier to crack a password.
[0] https://blog.cloudflare.com/validating-leaked-passwords-with...