OK, the worst aspects (the misleading name and documentation) have been dealt with, so that leaves the questions of:

1. Avoiding leaking the length information (seems unnecessary, since most digests are part of protocols where they have a known, published length, or you can find out the length by looking at public source code)

2. Providing a C implementation via the operator module (given the restriction to bytes values, and the assumption of caching for all relevant integers, would a C reimplementation really be buying us much additional security?)

As far as restoring unicode support (even in a C implementation) goes, I actually don't like the idea. For the general unicode case, as suggested in the updated documentation for hexdigest(), I believe the better approach is to try to stay in the bytes domain as much as possible, and avoid having a Unicode->bytes conversion for the expected value anywhere in the comparison timing path.