Validity of patent on Merkle Trees

Question

Patent US4309569, published in 1982 and expiring 20 years later, describes an algorithm for creating hash trees (known as Merkle trees, after its inventor), used for data validation. How is this patentable?

The US has granted "software patents" since the 70s, but my understanding is that this does not extend to obvious/trivial algorithms or mathematical formulae. In my view, hash trees -- and, thereupon, the application of the mathematical formulae presented in the patent -- are entirely obvious and non-novel. I believe this would be the view of any computer scientist or seasoned programmer; it therefore strikes me as unlikely that it was never independently reinvented (before or since), hence invoking a legal challenge.

Answer 1

I don't know the specifics of this invention, but it's important to remember that the novelty and non-obviousness of an invention is made as of the date of the patent application (or earlier priority date, not applicable here). In this case, that would be September 5, 1979. So you'd have to look specifically at what art existed as of that date (actually, one year prior to that date) and show that the invention was obvious and not novel in light of that prior art. It would take more than a general claim that it's obvious, for example.

The practices followed by the PTO in determining novelty and obviousness in accordance with the law is set out in the Manual of Patent Examination Procedure, chapter 700 ("Examination of patents"). You might find that an interesting read. The current release (Ninth Edition, Revision 07.2015) is here; the edition in effect in 1979 would have been the Fourth Edition, here.

As an aside, the term of the patent is not 20 years from publication. The term under today's law is 20 years from initial filing date, not from publication. Had that law been in effect for this patent, it would have expired in September 5, 1999 (which it actually did, as noted below). Prior to June 8, 1995, US patent term was based on the date of issue plus 17 years; in this case to January 5, 1999. But under terms of the 1995 law, any patent applied for prior to June 8, 1995 got the greater of those two terms; so we're back to September 5, 1999 again.

(And just for completeness, there is also the matter of periodic maintenance fees that today need to be paid to keep a patent in force; but that didn't start until December 1980, and wouldn't have applied to this patent, which was filed prior to the institution of maintenance fees.)