Thinking about this more carefully, I think there may be a problem here. We say:

collation-key($K1, $C) eq collation-key($K2, $C) if and only if compare($K1, $K2, $C) eq 0

and we also say in a note

The result of the function can be of any atomic type that permits ordering.

But what if the collation key has a type whose "eq" operator is context-sensitive? For example, if it depends on the default collation, or on the implicit timezone? This clearly isn't intended: the whole idea is that collation keys should be comparable in a predictable context-free manner.

The XQuery use case we give for collation-key() 

order by fn:collation-key($e/@key, $collation)

doesn't work if the ordering semantics for collation keys are context-dependent. To achieve this I think we need to ban the use of xs:string, xs:untypedAtomic, and untimezoned dates/times as collation keys.

I think the requirements are:

* The eq operator on collation keys must give the same result as the op:same-key() relation

* The type must be ordered, and the ordering must be context-free and must reflect the order of strings in the collation

* The value space must be infinite (in the sense that the value space of strings is infinite)

* The value space and ordering must be such that for any two values A and B where A<B, there is an infinite set of values between A and B. 

I think this pretty well leaves the two binary types as the only possible candidates. (One can imagine other theoretical possibilities, e.g. infinite precision decimal or infinite precision duration, but they don't seem very practical choices).

I therefore propose that we define the collation key to be xs:base64Binary. (We could choose either binary type, but it's messy to allow both, and base64Binary is the one that the EXPath binary project chose, so it's better supported. The two types are identical unless you convert the collation key to a string, and there's no real use case for doing that.)

A minor difficulty is that XSLT 3.0 defines the fn:collation-key() function to be usable with XPath 3.0 implementations, and xs:base64Binary is not an ordered type in XPath 3.0. But the use cases for wanting collation keys to be ordered came primarily from XQuery (XQuery "order by", unlike xsl:sort, does not allow a dynamic collation URI), and it's no great loss if for this particular case (XSLT 3.0 + XPath 3.0) the collation keys aren't ordered.

The WG agreed that collation keys should always be xs:base64Binary values.

The change has been applied to both F+O 3.1 and XSLT 3.0.