# Digest Values for DOM (DOMHASH) Proposal

Last modified: Fri Jun 12 18:13:34 JST 1998

23 Apr 1998 | Initial version
25 May 1998 |
12 Jun 1998 | Clean up for external

Authors:
  Hiroshi MARUYAMA, IBM Research, Tokyo Research Laboratory
  Kent TAMURA, IBM Research, Tokyo Research Laboratory
  Naohiko URAMOTO, IBM Research, Tokyo Research Laboratory

## Status of this Document

This document is intended to contribute discussions how digest (hash) values should be defined for general DOM structures. See W3C Document Object Model Specification 1.0 Draft for the latest draft specifications of DOM 1.0.

## Contents

1. Introduction
2. Hash Value Calculation
3. Proposed API
4. Discussions
5. References

## 1. Introduction

The purpose of this document is to give a clear and unambiguous definition of digest (hash) values of the XML objects. In particular, we propose to add a new API `getDigest()` to the interface `Node` that returns a digest value, a fixed length value (normally 128 bits or 160 bits) representing an entire subtree. Two subtrees are considered identical if their hash values are the same, and different if their hash values are different.

There are at least two usage scenarios of DOMHASH. One is as a basis for the Digital Signature for XML (XMLDSIG) proposal. Digital signature algorithms normally require hashing a signed content before signing. DOMHASH provides a concrete definition of the hash value calculation.

The other is to use DOMHASH when synchronizing two DOM structures. Suppose that a server program generates a DOM structure which is to be rendered by clients. If the server makes frequent small changes on a large DOM tree, it is desirable that only the modified parts are sent over to the client. A client can initiate a request by sending the root hash value of the structure in the cache memory. If it matches with the root hash value of the current server structure, nothing needs be sent. If not, then the server compares the client hash with the older versions in the server's cache. If it finds one that matches the client's version of the structure, then it locates differences with the current version by recursively comparing the hash values of each node. This way, the client can receive only an updated portion of a large structure without requesting the whole thing. A similar idea of minimizing the network communication for data replication was proposed in The HTTP Distribution and Replication Protocol.

One way of defining digest values is to take a surface string as the input for a digest algorithm. However, this approach has several drawbacks. The same internal DOM structure may be represented in may different ways as surface strings even if they strictly conform to the XML specification. Treatment of white spaces, selection of character encodings, entity references (i.e., use of ampersands), and so on have impact on the generation of a surface string. If the implementations of surface string generation are different, the hash values would be different, resulting in unvalidatable digital signatures and unsuccessful detection of identical DOM structures.

Therefore, it is desirable that digest of DOM is defined in the DOM terms -- that is, as an unambiguous algorithm using the DOM API. This is the approach we take in this proposal.

## 2. Hash Value Calculation

Hash values are defined on the DOM type `Node`. We consider the following five node types that are used for representing a DOM document structure:

1. ELEMENT
2. ATTRIBUTE
3. PI
4. COMMENT
5. TEXT

> Note: It is not simple to define hash values for DTD. At this moment, we do not define hash values for the DOCUMENT, DocumentType, ElementDefinition, and so on, to avoid this complication. Future release will cover this point.

Below, we give the precise definitions of digest for these types. We describe the format of the data to be supplied to a hash algorithm using a figure and a simple description, followed by a Java code fragment using the DOM API and the JDK 1.1 Platform Core API only. Therefore, the semantics should be unambiguous.

As the rule of thumb, all strings are to be in UTF-16 in the network byte order (Big Endian) with no byte order mark. If there is a sequence of text nodes without any element nodes inbetween, these text nodes are merged into one by concatenating them. A zero-length text node is always ignored.

The code fragments in the definitions below assume that they are in implementation classes of `Node`. Therefore, a methods call without an explicit object reference is for the Node itself. For example, `getData()` returns the text data of the current node if it is a `TEXT` node. The parameter `digestAlgorithm` is to be replaced by an identifier of the digest algorithm, such as "MD5" and "SHA".

The computation should begin with a four byte integer that represents the type of the node, such as TEXT or ELEMENT.

TEXT Nodes

  The hash value of a TEXT node is computed on the four byte header followed by the UTF-16 encoded text string.

  `Node.TEXT` (6) in 32 bit network-byte-ordered integer
  Text data in UTF-16 stream (variable length)

        public byte[] getDigest(String digestAlgorithm) {
            MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
            md.update((byte)((Node.TEXT >> 24) & 0xff));
            md.update((byte)((Node.TEXT >> 16) & 0xff));
            md.update((byte)((Node.TEXT >> 8) & 0xff));
            md.update((byte)(Node.TEXT & 0xff));
            md.update(getData().getBytes("UnicodeBigUnmarked"));
            return md.digest();
        }

  Here, `MessageDigest` is in the package `java.security.*`, one of the built-in packages of JDK 1.1.

COMMENT Nodes

  COMMENT nodes are similar to TEXT nodes except for the header.

  `Node.COMMENT` (5) in 32 bit network-byte-ordered integer
  Comment data in UTF-16 stream (variable length)

        public byte[] getDigest(String digestAlgorithm) {
            MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
            md.update((byte)((Node.COMMENT >> 24) & 0xff));
            md.update((byte)((Node.COMMENT >> 16) & 0xff));
            md.update((byte)((Node.COMMENT >> 8) & 0xff));
            md.update((byte)(Node.COMMENT & 0xff));
            md.update(getData().getBytes("UnicodeBigUnmarked"));
            return md.digest();
        }

PI Nodes

  A PI node has two components: the target and the data. Accordingly, the hash is computed on the concatenation of both. Note that the data contains the leading space character so there is no ambiguity even if there is no separator between the target and the data.

  `Node.PI` (4) in 32 bit network-byte-ordered integer
  PI target and data in UTF-16 stream (variable length)

        public byte[] getDigest(String digestAlgorithm) {
            MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
            md.update((byte)((Node.PI >> 24) & 0xff));
            md.update((byte)((Node.PI >> 16) & 0xff));
            md.update((byte)((Node.PI >> 8) & 0xff));
            md.update((byte)(Node.PI & 0xff));
            md.update(getName().getBytes("UnicodeBigUnmarked"));
            md.update(getData().getBytes("UnicodeBigUnmarked"));
            return md.digest();
        }

ATTRIBUTE Nodes

  ATTRIBUTE Nodes are similar to PI Nodes, except that we need a separator between the attribute name and the attribute value. Note that the '0x0000' value in UTF-16 is allowed nowhere in an XML document, so it can serve as an unambiguous separator.

  `Node.ATTRIBUTE` (3) in 32 bit network-byte-ordered integer
  Attribute name in UTF-16 stream (variable length)
  0x00 | 0x00 |  |
  Attribute value in UTF-16 stream (variable length)

        public byte[] getDigest(String digestAlgorithm) {
            MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
            md.update((byte)((Node.ATTRIBUTE >> 24) & 0xff));
            md.update((byte)((Node.ATTRIBUTE >> 16) & 0xff));
            md.update((byte)((Node.ATTRIBUTE >> 8) & 0xff));
            md.update((byte)(Node.ATTRIBUTE & 0xff));
            md.update(getName().getBytes("UnicodeBigUnmarked"));
            md.update((byte)0);
            md.update((byte)0);
             // getValue() returns String instance in WD-DOM-19980416
            md.update(getValue().getBytes("UnicodeBigUnmarked"));
            return md.digest();
        }

ELEMENT Nodes

  ELEMENT nodes are the most complex because they consist of other nodes recursively. Hash values of these component nodes are used to calculate the node's digest so that we can save computation when the structure is partially changed.

  One delicate point in this definition is that we need to sort the attributes by the attribute names. This is done using the string comparison operator defined as `String#compareTo()` in Java. The sorting is done in ascending order in terms of the UTF-16 encoded attribute names. The semantics of this sorting operation should be clear.

  `Node.ELEMENT` (2) in 32 bit network-byte-ordered integer
  Element name in UTF-16 stream (variable length)
  0x00 | 0x00 |  |
  A number of attributes in 32 bit network-byte-ordered unsigned integer
  Sequence of digest values of attribute, sorted by `String#compareTo()` for attribute names
  A number of child elements in 32bit network-byte-ordered unsigned integer
  Sequence of digest values of each child elements (variable length)

  (A sequence of child texts is merged to one text. A zero-length text is not counted as child)

        public byte[] getDigest(String digestAlgorithm) {
            MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            DataOutputStream dos = new DataOutputStream(baos);
            dos.writeInt(Node.ELEMENT);    // This is stored in the network byte order
            dos.write(getName().getBytes("UnicodeBigUnmarked"));
            dos.write((byte)0);
            dos.write((byte)0);
            NodeIterator ni = getAttributes();
            int len = ni.getLength()
            dos.writeInt(len);    // This is sotred in the network byte order
            // Sort attributes by String#compareTo().
            ...
            // Assume that `Attribute[] aattr' has sorted Attribute instances.
            for (int i = 0;  i < len;  i ++)
                dos.write(aattr[i].getDigest(digestAlgorithm));

            ni = getChildNodes();
            // Assume that adjoining Texts are merged and no 0-length Text.
            len = ni.getLength();
            dos.writeInt(len);    // This is stored in the network byte order
            Node n;
            while (null != (n = ni.toNextNode()))
                dos.write(n.getDigest(digestAlgorithm));
            dos.close();
            md.update(baos.toByteArray());
            return md.digest();
        }

## 3. Proposed API

We propose to add a new method to the `Node` interface as shown below. The `getDigest()` method takes one string as its parameter that specifies the digest algorithm. We assume that at least two algorithms, "MD5" and "SHA", must be implemented for any DOM processor to be compliant with DOMHASH.

>     public interface Node {   // NodeType
>        public static final int            DOCUMENT             = 1;
>        public static final int            ELEMENT              = 2;
>        public static final int            ATTRIBUTE            = 3;
>        public static final int            PI                   = 4;
>        public static final int            COMMENT              = 5;
>        public static final int            TEXT                 = 6;
>        public int               getNodeType();
>        public Node              getParentNode();
>        public NodeIterator      getChildNodes();
>        public boolean           hasChildNodes();
>        public Node    getFirstChild();
>        public Node    getPreviousSibling();
>        public Node    getNextSibling();
>        public Node    insertBefore(Node newChild,
>                                              Node refChild) throws NotMyChildException;
>        public Node    replaceChild(Node newChild,
>                                              Node oldChild) throws NotMyChildException;
>        public Node    removeChild(Node oldChild) throws NotMyChildException;
>        public byte[]  getDigest(String digestAlgorithm);
>     };

## 4. Discussion

The definition described above can be efficiently implemented. XML for Java has a reference implementation with the source code.

## 5. References

- XML 1.0 Recommendation
- XML for Java
- The HTTP Distribution and Replication Protocol

## Contacts

Please forward any comments and suggestions to:

- Hiroshi MARUYAMA, Manager of Network Applications, Tokyo Research Laboratory. email: maruyama@jp.ibm.com, or
- Kent TAMURA, Advanced Internet Technology, Tokyo Research Laboratory, email: kent@trl.ibm.co.jp.
- Naohiko URAMOTO, Advanced Internet Technology, Tokyo Research Laboratory, email: uramoto@jp.ibm.com.