[Barker, Elaine B.] NIST Publication Announcements

James A. Donald jamesd at echeque.com
Wed Sep 30 16:38:03 EDT 2009

 >> The Haber & Stornetta scheme provides a timestamping
 >> service that doesn't require terribly much trust,
 >> since hard to forge widely witnessed events delimit
 >> particular sets of timestamps. The only issue is
 >> getting sufficient granularity.

 > I don't know if their scheme was patented in Germany.
 > It was in the U.S., though I think that at least some
 > of the patents expire within the year.

In looking this up, I have noticed a pile of patents
that patent something equivalent or near equivalent to a
patricia hash tree, or elaborately disguised patricia
trees, or something suspiciously similar to a patricia
hash tree, and various special cases of it, and
applications of it, without using the name "patricia
hash tree"

Since they seem reluctant to use the name "patricia hash
tree" I suspect  that there is already a pile of prior
art, but I could not find any, though I am fairly sure
the method is widely known.  Also, wherever there is a
pile of patents, there is usually a pile of prior art.

Lest even more patents of the patricia hash tree be
published, I would like to describe the method here,
though it surely must be described somewhere else,
probably long ago.

Suppose we have a lot of records, each with a key that
makes collision improbable or impossible,  We assemble
them in a patricia tree, with each node of the patricia
tree containing a hash of its child nodes.  The root of
the patricia tree then, like a tiger hash, uniquely
identifies the complete data set.  If we have multiple
copies of the data set, this data structure allows us to
not only ensure that both copies are identical, but if
there are small differences between them, such as
recently added records, it allows us to efficiently find
the differences, and thus efficiently bring the two data
sets into agreement.

It also allows us to prove that a given record was part
of a particular data set at a particular time.

Suppose the high order part of the key identifies the
high order part of the time, followed by the id of the
particular organization holding those records.  The
upper parts of the patricia hash tree are partially
shared, peer to peer, similarly to file sharing with a
tiger hash.  Each participating organization keeps the
nodes that relate to it. The lower parts are not shared
except as needed.

In this case, there will be a small set of top nodes of
the tree that cease to change, because they only rely on
keys earlier than a certain date, and this small and
very slowly growing set of top nodes proves the complete
state of the tree at all earlier dates.

Then each organization can prove to all or any of the
others that it had a particular record, or particular
set of records, at a particular time, to the granularity
of the time that is the high order part of the key.

Where some or all of the data needs to be shared by some
or all of the organizations, organizations can rapidly
and efficiently identify any disagreements, and when
they are in agreement, rapidly and efficiently prove to
themselves, and to everyone else, and record for all
time, that they are in agreement, since a small number
of the topmost nodes of the tree proves the state of the
tree at each and all times that contributed to those

The structure serves for attestation and sharing, and
since attestation usually involves sharing, and sharing
attestation, the scope for patenting this structure over
and over again in one disguise or another to be applied
to one task or another that involves sharing and or
attestation is limited only by the boundless imagination
of patent lawyers.  One can also add horizontal and
backwards hash relationships between nodes that serve
little practical purpose other than allowing one to have
a single rapidly changing node node attesting instead of
a small set of nodes, and allowing it to be nominally
something other than a patricia hash tree.

Thus, for example, instead of using forty or so nodes to
attest for the state of million organizations over a
billion time periods, one can use a hash of those forty
nodes, and there are no end of different ways one can
hash those forty or so nodes together.  But under that
hash, it is still a patricia hash tree doing the actual
work of gluing the data together.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list