Thanks for this pure Python implementation!

A few comments:

• There can be more than one certificate (multiple TXT records) for a given provider. This is typically the case during key rotation, where a new certificate is added before the previous one expires, possibly with a date in the future. If multiple certificates are valid for the current timestamp, the one with the highest serial number should be used.
• magic_query = '7PYqwfzt' - I am not sure where this value comes from, but it probably shouldn't be hardcoded. The header is unique to a (provider,certificate) pair, so that during a key rotation, the server knows what certificate the client is using. The value for magic_query is part of the certificate.
• The protocol is designed to mitigate DNS amplification attacks. Namely, the server can refuse to send responses that are larger than the question, if UDP is being used. In order to do so, when the TC flag is set in a response, the proxy increases the padding size for the following questions. That was implemented a long time ago in the client, and while this is not enforced in the server proxy yet, it will soon be by default.