Copyright © 2014 W3C® (MIT, ERCIM, Keio, Beihang), All Rights Reserved. W3C liability, trademark and document use rules apply.
Any EXI document is part of a set of EXI documents that are logically equivalent within an application context, but which vary in physical representation based on differences permitted by the [Efficient XML Interchange (EXI) Format 1.0 (Second Edition)]. This specification describes a relatively simple method for generating a physical representation, the canonical form, of an EXI document that accounts for the permissible changes. An example of the applications targeted by this specification is one that needs to guarantee non-repudiation using XML Signature yet allows certain flexibility for intermediaries to reconstitute the documents before they reach final destination without breaking the signatures. Note that two documents may have differing canonical forms yet still be equivalent in a given context based on more elaborate application-specific equivalence rules which is out of scope of this specification.
This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.
This is the second Public Working Draft of the Canonical EXI specification. It is intended for review by W3C members and other interested parties. The document identifies all steps and algorithms that are currently in the final scope of the specification. Feedback is welcome on the document content as well as on any other relevant topic.
Please send comments about this document to the public-exi-comments@w3.org mailing list ( Archives ).
A diff-marked version against the previous version of this document is available.
This document has been produced by the Efficient XML Interchange Working Group as part of the W3C XML Activity. The goals of the Efficient XML Interchange (EXI) Format are discussed in the Efficient XML Interchange (EXI) Format 1.0 document. The authors of this document are the members of the Efficient XML Interchange Working Group.
Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.
This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.
This document is governed by the 14 October 2005 W3C Process Document.
1. Introduction
1.1 Notational Conventions and Terminology
1.2 Need of Canonical EXI
1.3 Applications
1.4 Limitations
2. Canonical EXI Stream
3. Canonical EXI Body
3.1 EXI Alignment Options and Streams
3.2 EXI Event Selection
3.2.1 Prune productions according to specific conventions
3.2.2 Prune productions for non applicable events with content values
3.2.3 Use the event with the most accurate event
3.3 EXI Stream Order
3.4 EXI Datatypes
3.4.1 Unsigned Integer
3.4.2 Enumeration
3.4.3 Decimal
3.4.4 Float
3.4.5 Date-Time
3.4.6 String and String Table
3.4.7 Restricted Character Sets
3.4.8 Datatype Representation Map
4. Canonical EXI Header
A Design Decisions
A.1 Relationship to XML
A.2 No Unicode Normalization
B Canonical EXI Examples
B.1 EXI Event Selection
B.2 EXI Stream Order
B.3 EXI Floats
C Canonical EXI Applications
C.1 Signature Processing Steps
C.2 Exchange EXI Options (Best Practices "Work in Progress")
C.2.1 Option 1 - XML Signature element
C.2.2 Option 2 - Uri scheme fragment identifier
C.2.3 Option 3 - EXI options within EXI stream
D References
The EXI 1.0 Recommendation [Efficient XML Interchange (EXI) Format 1.0 (Second Edition)] specifies the syntax of a class of resources called EXI streams. It is possible for EXI streams which are equivalent for the purposes of many applications to differ in physical representation. For example, they may differ in their datatype representation and attribute ordering. It is the goal of this specification to establish a method for determining whether two documents are identical, or whether an application has not changed a document, except for transformations permitted by EXI 1.0.
The key words MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear EMPHASIZED in this document, are to be interpreted as described in RFC 2119 [IETF RFC 2119].
The term canonical is used throughout this document to denote a normative form in regard to the physical representation. The term canonical EXI refers to EXI that is in canonical form produced by the method described in this specification.
The term sorted lexicographically denotes lexicographical ordering of strings which is done by comparing character by character. Individual characters are ordered by comparing their Unicode code points.
Many environments and device classes have difficulties to handle plain-text XML due to various reasons (e.g., document size and processing overhead). W3C's Efficient XML Interchange Format has been developed to provide a solution to these issues and to extend the use of XML and its tools.
With EXI, constrained environments and device classes (low memory, bandwidth, and processing power) have the possibility to be part of the XML world. However, some use cases also require a canonical representation of the XML-based data for comparison of logical and physical equivalence. Hence, supporting EXI canonicalization without going through plain-text XML where nothing else but EXI is available is needed.
One application field for the canonical form of an XML-based document or document subset is digital signature. During signature generation, the digest is computed over the canonical form of the document or the document subset respectively. The document is then transferred to the relying party, which validates the signature by reading the document and computing a digest of the canonical form of the received document (see C.1 Signature Processing Steps). If there is equivalence the relying parties can ensure that the information content of the document has not been altered since it was signed.
Although EXI supports plain-text XML Signature by preserving XML information such as comments and prefixes (see EXI Best Practices for XML Signature) this strategy is not suited for all environments and use cases.
It is the goal of this specification to provide a canonical EXI form for various use-cases. For example, restricted and very limited devices should be able to create or check against a canonical EXI stream. This applies to devices that may be able to speak only a given EXI language only (according to an XML Schema) or support only a subset of all EXI features.
For example an EXI stream may or may not contain the EXI options that were used to encode the stream. However, the process for building a Canonical EXI stream bases upon the knowledge of the used EXI options and MUST follow the rules defined in 2. Canonical EXI Stream. Moreover, there is not one canonical EXI stream but many according to the schema knowledge in use and the according EXI options and fidelity settings.
The EXI specification defines an EXI stream as an EXI header followed by an EXI body. In this sense a Canonical EXI stream is a 4. Canonical EXI Header followed by a 3. Canonical EXI Body.
EXI Canonicalization may be used as a canonicalization method algorithm in XML
Signature [XMLDSIG-CORE1] and XML Encryption [XMLENC-CORE1]. The identifier http://www.w3.org/TR/exi-c14n
hereby specifies the rules of this document.
The subsequently described EXI Canonicalization steps and algorithms expect as input EXI events (e.g., SE, NS, and AT events). The input MUST be a sequence of EXI events and produces as output a canonicalized EXI body stream. Following the presented algorithms guarantees that logically-identical documents produce identical serialized EXI Body stream representations (assuming the same EXI coding options).
Note:
An EXI stream can be passed to a final recipient over multiple intermediary nodes. In general, it is feasible to parse and re-encode the EXI stream on such intermediary node without affecting the canonical EXI stream. However, please note that alternating EXI Options (e.g., preserve option or schemaId) used to encode the body of the EXI stream, may lead to irrecoverable data loss or differences.
EXI provides four alignment options, namely bit-packed, byte-alignment, pre-compression, and compression.
The canonicalized EXI form is the resulting EXI stream following the rules defined in this document. When the alignment option compression is set for an EXI stream, its canonical form is computed as if the EXI stream was encoded using the alignment option pre-compression.
EXI processors may make use of padding bits, for example to make the length of the EXI stream byte-aligned. In a Canonical EXI stream padding bits, if necessary, MUST always be represented as a sequence of 0 (zero) bits.
EXI processors represent a given event such as a start element or an attribute by serializing an event code first, followed by the according event content. Each event code is represented by a sequence of 1 to 3 parts that uniquely identifies an event.
In situations where EXI grammars provide more than one possible event (-code) the canonical EXI form prescribes which event and respectively which event code has to be chosen. That said, it is not uncommon that an EXI processors has certain flexibility in choosing the appropriate EXI grammar production, or respectively the appropriate event.
Canonical EXI processors MUST follow a three step process for selecting the one valid event(-code).
The availability of grammar productions is subject to the convention used by the application. A prominent convention is the [Efficient XML Interchange (EXI) Profile], which is more restrictive in regard to which production is usable than the [Efficient XML Interchange (EXI) Format 1.0 (Second Edition)] specification.
In the case of an attribute (AT) or a character (CH) event, productions MUST be pruned that cannot be used to represent the content value according to the associated EXI datatype (e.g., the content value "abc" cannot be represented with the the EXI Integer datatype).
After excluding productions that are not usable (according to the convention in use or according to the EXI datatype) a canonical EXI processor MUST follow the subsequent order:
Use the event with the most accurate event content first
For Start Element events the order is as follows:
SE( qname )
SE ( uri : * )
SE ( * )
For Attribute events the order is as follows:
AT( qname )
AT ( uri : * )
AT ( * )
IF the accurateness is the same use the event with the least event code parts
Further, a value content item that can be represented by the associated EXI datatype MUST be represented with the associated datatype representation. When the strict option is false, attributes and character events that cannot be represented by the associated EXI datatype representations (e.g., schema-invalid values) MUST use the additional untyped AT and CH terminal symbols.
Note:
A Canonical EXI processor MUST NOT account for XML schema validity (just like an EXI processor). The verification solely bases on EXI grammars and EXI datatypes.
The appendix section B.1 EXI Event Selection depicts one concrete example for choosing the correct event.
In general, a canonical EXI processor SHALL NOT change the order of the EXI input sequence. The only exceptions to this statement are sequences of attributes and/or namespace declarations.
The EXI specification defines that namespace (NS) and attribute (AT) events associated with a given element occur directly after the start element (SE) event in the following order:
| NS | NS | ... | NS | AT (xsi:type) | AT (xsi:nil) | AT | AT | ... | AT |
In addition, canonical EXI specifies that namespace declarations for a given element MUST be sorted lexicographically according to the NS prefix. Further, canonical EXI strictly requires that an xsi:type or an xsi:nil attribute MUST occur before other AT events even if it does not impact grammar selection. Moreover, attributes other than xsi:type and xsi:nil for a given element MUST be sorted lexicographically, first by qname local-name then by qname uri.
Note:
Optimizations such as pruning insignificant xsi:type values
(e.g., xsi:type="xsd:string" for string values) or
insignificant xsi:nil values (e.g.,
xsi:nil="false") is prohibited for a Canonical EXI
processor.
This section describes the built-in EXI datatype representations used for representing content items in canonical EXI streams.
When the Preserve.lexicalValues option is true, individual items are represented as String. Each value MUST be represented as a String with the associated restricted character set, if such a set is defined for the associated datatype representation (see Restricted Character Sets for Built-in EXI Datatype Representations). String content items associated with a restricted character MUST also follow the rules described in 3.4.7 Restricted Character Sets.
When the Preserve.lexicalValues option is false, a value content item MUST be represented with the associated datatype representation. The following sub-sections describe the Canonical EXI behavior for datatypes that otherwise may not lead to a uniquely defined representation.
EXI 1.0 permits the use of untyped AT or CH terminal symbols to represent a value content item even when a typed AT or CH terminal symbol is available that could have been used to represent the value. Therefore, given an input value content item that uses an untyped AT or CH terminal symbol despite the availability of a typed alternative terminal symbol, it is not apparent whether the use of the untyped terminal symbol was due to the result of observing the event selection rule described in Section 3.2 EXI Event Selection or otherwise (i.e. negligence of observing the rule) unless switching to the typed alternative terminal symbol is actually attempted by a Canonical EXI processor. To cope with this situation, Canonical EXI processors SHOULD be able to convert an untyped value into each of the datatype representations defined in EXI 1.0 as long as the target datatype representation can accept the value.
The EXI specification defines that the Unsigned Integer datatype representation supports unsigned integer numbers of arbitrary magnitude. EXI processors SHOULD support arbitrarily large Unsigned Integer values. EXI processors MUST support Unsigned Integer values less than 2147483648.
Canonical EXI processors MUST use the Unsigned Integer datatype representation even if a value goes beyond the value 2147483647.
The EXI Enumeration assigns to each item an unsigned integer value that corresponds to its ordinal position in the enumeration in schema-order starting with position zero. When there is more than one item that represents the same value in the enumeration, the value MUST be represented by using the first ordinal position that represents the value.
The EXI Decimal datatype is a Boolean sign followed by two Unsigned Integers. A sign value of zero (0) is used to represent positive Decimal values and a sign value of one (1) is used to represent negative Decimal values. The first Unsigned Integer represents the integral portion of the Decimal value. The second Unsigned Integer represents the fractional portion of the Decimal value with the digits in reverse order to preserve leading zeros.
The canonical EXI Decimal MUST respect the following constraint.
A sign value of one (1) MUST be changed to zero (0) if both the integral portion and the fractional portion of the Decimal value are 0 (zero).
The EXI Float datatype uses two consecutive EXI Integers. The first Integer represents the mantissa of the floating point number and the second Integer represents the base-10 exponent of the floating point number.
The canonical EXI Float MUST respect the following constraints.
A mantissa value of -0 MUST be changed to 0. If the mantissa is 0, then the exponent MUST be 0. If the mantissa is not 0, mantissas MUST have no trailing zeros.
An exponent value of -0 MUST be changed to 0.
Given an EXI Float value that consists of one integer representing its mantissa and the other integer representing its exponent, Canonical EXI processors MUST find an equivalent canonical EXI Float that satisfies the above constraints, where the rules of determining equivalence is described below.
Two floats A and B each denoted as (mantissa, exponent) pair of (mA, eA) and (mB, eB) where eA >= eB are equivalent under the following circumstances.
Both mantissa and exponent are the same between the two floats.
Otherwise, if two exponents are different (i.e. eA > eB), substitute A with A2 where A2 has exponent eB and mantissa mA * 10(eA-eB). If A2 and B are equivalent per the rule 1 above, A and B are equivalent.
The appendix section B.3 EXI Floats depicts one example algorithm for finding the canonical EXI Float that is equivalent to a given EXI Float value.
The EXI Date-Time is a sequence of values representing the individual components of the Date-Time.
The values MUST be canonicalized according to XML Schema dateTime canonical representation.
The EXI String datatype representation is a length prefixed sequence of characters. If no restricted character set is defined for the string, each character is represented by its Unicode code point. The Unicode standard allows multiple different representations of certain characters. A canonical EXI processor MUST NOT change the code points.
Further, a String value MUST be represented as string value hit if possible. Unless the convention used by the application dictates differently (e.g., EXI Profile parameter localValuePartitions set to "0"). EXI processors MUST first try to represent the string value as local hit and only when this is not successful as global value hit.
Note:
A String value miss MAY also need to follow the rules described in 3.4.7 Restricted Character Sets according to the given restricted character set, if available.
Note that a Canonical EXI processor MUST also respect the XML schema whiteSpace facet, if available.
Restricted Character Sets in EXI enable to restrict the characters of the string datatype. The canonical representation dictates that characters from the restricted character set MUST use the according n-bit Unsigned Integer. Hence, only characters that are not in the set SHALL be represented by the n-bit Unsigned Integer N followed by the Unicode code point of the character represented as an Unsigned Integer.
The EXI option datatypeRepresentationMap may specify an alternate set of datatype representations for typed values in the EXI body stream. This specification does not define any canonicalization rules for alternate representations. Other specifications and/or groups making use of this feature MAY describe a canonical form.
Each EXI stream begins with an EXI header and identifies the version of the EXI format being used, and specifies the options used to process the body of the EXI stream. The EXI header has the following structure:
| [ EXI Cookie ] | Distinguishing Bits |
|
| [EXI Options] | [Padding Bits] |
A Canonical EXI Header MUST NOT begin with the optional EXI Cookie and the Presence Bit for EXI Options MUST always be 1 (true) to indicate that the fifth part of the EXI Header, the EXI Options, is present. Padding bits (if any) MUST always be represented as a sequence of 0 (zero) bits.
The EXI Options are represented as an EXI Options document. That said, the subsequently described canonicalization steps expect as input a set of EXI Options (or respectively an EXI options document) and produce as output a canonicalized set of EXI options that MUST be represented as 3. Canonical EXI Body.
A canonical EXI Options document MUST respect the following constraints.
The options elements that change the default EXI option values (i.e. byte, pre-compress, selfContained, valueMaxLength, valuePartitionCapacity, dtd, prefixes, lexicalValues, comments, pis, blockSize, compression, fragment, schemaId, strict) MUST NOT be omitted (see EXI specification for default values). On the contrary, values that match the default value (i.e. <blockSize>1000000</blockSize>) MUST be omitted.
The element blockSize MUST be omitted if neither compression nor pre-compress is present.
When the alignment option compression is set, pre-compress MUST be used instead.
The element schemaId MUST always be present to indicate which schema information is used.
Note:
The EXI working group is aware of use-cases that do not require or do not even have a schemaId. Nevertheless the burden of requiring the schemaId element has been found justifiable due to the increased security.If the element datatypeRepresentationMap does have nested element tuples (tuple of schema datatype and datatype representation), the tuples are to be sorted lexicographically according to the schema datatype first by {name} then by {namespace}. Moreover, the EXI event sequence of each nested element MUST be SE followed by EE. Mappings that match the default built-in EXI datatype representations map (e.g., {http://www.w3.org/2001/XMLSchema}base64Binary → {http://www.w3.org/2009/exi}base64Binary) MUST be omitted.
The user defined meta-data MUST NOT be used.
| Editorial note | |
| The user defined meta-data conveys auxiliary information and does not alter or extend the EXI data format. Hence it deemed acceptable to omit this information. | |
Elements that are necessary to structure the EXI options document according to the XML schema (i.e. lesscommon, uncommon, alignment, datatypeRepresentationMap, preserve and common) MUST be omitted unless there is at least one nested element according to the previous steps.
The example below illustrates some requirements and the associated modifications that have been described.
<exi:header xmlns:exi="http://www.w3.org/2009/exi">
<exi:lesscommon>
<exi:preserve/>
<exi:blockSize>1000000</exi:blockSize>
</exi:lesscommon>
<exi:common>
<exi:compression/>
<exi:fragment/>
</exi:common>
</exi:header> | → | <exi:header xmlns:exi="http://www.w3.org/2009/exi">
<exi:lesscommon>
<exi:uncommon>
<exi:alignment>
<exi:pre-compress/>
</exi:alignment>
</exi:uncommon>
</exi:lesscommon>
<exi:common>
<exi:fragment/>
</exi:common>
</exi:header>
|
This section discusses a number of key decision points. A rationale for each decision is given as well as background information is provided.
Canonical XML is designed to be useful to applications that test whether an XML document has been changed (e.g., XML signature). EXI can be used in such use cases and offers benefits w.r.t. compact data exchange and fast processing. To ensure that relevant Infoset items are available the following EXI Fidelity Options must be always enabled: Preserve.pis, Preserve.prefixes, and Preserve.lexicalValues. When the XML canonicalization algorithm preserves comments the EXI fidelity option Preserve.comments must be also enabled.
Canonical EXI, in contrast to Canonical XML, deals with EXI documents and does not require XML data and the associated overhead.
The Unicode standard allows multiple different representations of certain characters. Thus two character sequences that have the same appearance and meaning when printed or displayed may differ in sequences of code points. EXI Canonicalization uses as its input EXI events in which Strings are represented as sequences of Unicode code points.
A canonical EXI processor must not change the code points as it is not allowed to alter any other event. However, character model normalization may become an issue when working with plain-text XML.
The subsequently following example depicts the available productions for an example DocContent grammar. From the perspective of the [Efficient XML Interchange (EXI) Format 1.0 (Second Edition)] specification it is perfectly fine to match a start element "A" with event code 0 (zero) or 4 (four). A canonical EXI form prescribes event code 0 (zero).
The Float datatype representation can be converted to the canonical form going through the following steps. Note, implementations are free to choose any strategy as long as the constraints in 3.4.4 Float are met.
Let the float value have a decimal notation of the form
<before>.<after> where before
represents the value before the decimal point and after
represents the value after the decimal point. The canonical representation
of the mantissa and exponent SHALL be determined as follows:
Initialize the exponent with the value 0 (zero) and jump to step 2.
Examine the float value and extract the portion before and after the decimal point. If the value after the decimal point can be represented as 0 (zero) without losing precision jump to step 4, otherwise to step 3.
Decrement the exponent by 1 (one) and shift the decimal point of the float value by one digit to the right. Jump back to step 2.
The portion before the decimal point can be safely converted to the signed mantissa value. Jump to step 5.
If the signed mantissa is unequal 0 (zero), unequal -0 (negative zero), and contains a trailing zero jump to 6, otherwise to step 7.
Increment the exponent by 1 (one) and shift the mantissa by one digit to the right. Jump back to 5.
If the mantissa is equal -0 set the mantissa value to 0 (zero). Finished.
The subsequently following examples depict possible float values opposed to their canonical form.
The figure below describes the involved processing steps when Canonical EXI is used for signing an EXI document or a fragment and the signature value is embedded within the document: First, the EXI stream or fragment of the EXI stream to be signed has to be transformed in a canonical form according to the requirements given in this document (see 2. Canonical EXI Stream). Then, the canonical representation is used to determine the signature value based on the intended signature algorithm. At this point the signature value can be set within the EXI document and can be transmitted to the recipient.
To validate the signature value for compliance, the receiver has to build the canonical EXI stream for the signed portion. Note, this step can be skipped if there is pre-knowledge on the receiver side that the EXI stream already fulfills the requirements of Canonical EXI. Finally, to determine the correctness of the signature value (based on the signature algorithm) it can be compared with the embedded signature value provided by the sender.
In the case of XML Signature processing, a detached signature can be used or an enveloped signature, in which case the signature element is not included in the hash calculation.
During signature generation, the digest is computed over the canonical EXI stream. There are two independent aspects that are to be solved.
What gets hashed and
How to exchange and share EXI options other than out-of-band or as part of the EXI stream (see C.2 Exchange EXI Options (Best Practices "Work in Progress"))
The canonicalization process of EXI bases upon the knowledge of the used EXI options which is an optional part of the EXI header. These options communicate the various EXI options that have been used to encode the actual XML information with EXI and are crucial to be known. This sections provides some best practices - so that for example it can be succesfully used as part of the digital signature framework or in other use-cases. Currently different options are discussed.
According to section 6.1 of XML Signature Syntax and Processing Version explicit additional parameters to an algorithm appear as content elements within the algorithm role element. The role element in this case is "CanonicalizationMethod". Hence, Canonical EXI use cases can leverage the sub-elements in CanonicalizationMethod.
CanonicalizationMethod element is given a schema type as:
<element name="CanonicalizationMethod" type="ds:CanonicalizationMethodType"/>
<complexType name="CanonicalizationMethodType" mixed="true">
<sequence>
<any namespace="##any" minOccurs="0" maxOccurs="unbounded"/>
<!-- (0,unbounded) elements from (1,1) namespace -->
</sequence>
<attribute name="Algorithm" type="anyURI" use="required"/>
</complexType>
| Editorial note | |
| Another proposal is to use the SignatureProperties element. | |
The advantages of this kind of approach are that EXI options are
easily integrated within digital signature
represented as plain-text XML (no need of an EXI options decoder)
The disadvantages of this kind of approach are that EXI options
cannot be easily used in scenarios where no digital signature framework is used
In general the identifier http://www.w3.org/TR/exi-c14n
specifies the use of Canonical EXI. Additionally a fragment identifier could
be used to uniquely refer to a specific set of options (e.g.,
http://www.w3.org/TR/exi-c14n#AB1235). One possibility is
to make up some uri schema for the EXI options. Another possibility is to
encode the EXI options element as EXI stream and map it to binary (e.g.,
hexBinary). For the latter it is important to make sure that one set of
options maps to exactly one fragment identifier. Hence we ought to define a
canonical representation of the EXI Options (see 4. Canonical EXI Header).
The advantages of this kind of approach are that EXI options are
Closely coupled with canonicalization method algorithm
It is very efficient and short
Can be used in many scenarios where no digital signature framework is used
The disadvantage of this kind of approach is that it
demands retrieving EXI options required to decode the fragment identifier (byte array?) with an EXI processor
| Editorial note | |
| What IF the EXI stream itself contains the EXI options and what if there are conflicts between them? | |
Another possibility is that the EXI options are present in the EXI stream itself.
The advantages of this kind of approach are that EXI options are
Closely coupled with the EXI stream
It is very efficient and EXI processors can already deal with it
Can be used in many scenarios where no digital signature framework is used
The disadvantage of this kind of approach is that it
seems to be an undesirable overhead (e.g., size) for many use cases to require EXI options to be present all the time.