Fix error messages when asking t for ids it does not know
Refactor prefixing method

There is still an issue when there are ids that start with the same
bytes. The TODO/FIXME describes the expected behaviour.