Revert "Use unicode instead of bytes"

This reverts commit 8554840ed01986a7b92bc1df2c40e4847844c4b6.
Since we can't break the API, let's bend the tests