>> 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 nodes. 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 majord...@metzdowd.com