Smart Ledger Patents & Prior Smarts

Wednesday, 27 May 2020
By Michael Mainelli & Henry Price

Introduction

Patents exist to encourage inventors to share their techniques in exchange for being granted a temporary monopoly on an item of useful novelty. Frequently, the period of greatest invention is not well-patented, but precedes a wave of patents for lesser additions, combinatorial patents, as well as patents for blocking alternative avenues or emerging standards. This observation partially undermines the idea of inventors needing patents in order to innovate.

blockchain patents 2.jpg

However, when a field begins to attract investors, investors are often more interested in innovations backed by patents. Investors are not investing in innovation so much as the potential for a defensible monopoly. Investors often exhibit a touching faith in inventors’ patents, any patent, rarely able to distinguish between strong, weak, or even useless patents.

Smart ledgers (aka blockchains) are multi-organisational data structures (aka distributed ledgers) with a superb audit trail and some embedded code. The constituent technologies include:

  1. Cryptography – how to exchange information in secret;
  2. Distributed Systems – how to transfer files and replicate databases across multiple computers;
  3. Distributed Consensus & Time Protocols – how to agree on the state of shared data and sequence of events, even when bad actors have access to the data;
  4. Distributed Embedded Coding (smart contracts) – how to store and execute code in line with a set of rules agreed on by participants.

The field is undergoing a wave of patenting. This short paper sets out the scale of patenting with a view to the likelihood of patent wars. The paper then surveys a few of ‘prior art’ cases that might indicate many patent submissions will be vulnerable once people begin to seek antecedents. If nothing else, some of these prior art cases are historically interesting for those who place too much credence in the widespread notion that these technologies emerge from the 2009 introduction of Bitcoin. Finally, this paper makes some broad brush observations about the desirability or usefulness of patents for smart ledger technologists.

Smart Ledger Patents

The World Intellectual Property Organization (WIPO) database contains patents that comply with the Patent Cooperation Treaty (PCT) signed by 152 states. Analysis conducted in October 2019, shows the WIPO database holds more than 3,500 patents containing the words ‘block chain’ or ‘distributed ledger’, ‘mutually distributed ledger’, ‘cipher block chaining’, ‘smart contract’, or ‘smart ledger’.

Figure 1.JPG
Figure 1 - Smart Ledger Patent Filings

The US and China are the biggest patentors of smart ledger technology, but corporate battle lines are also being drawn up. nChain (341 patents), IBM (186), Alibaba (170), Mastercard (154), Accenture (84), Intel (61), Microsoft (50), Coinplug (50), Siemens (42) and British Telecom (32) are the leading players.

Historical Digging

Since the mid-1990s Z/Yen has built multi-organisational data structures that provide tamper-proof functionality based on chaining cryptographic hashes together, i.e. blockchains. Further, some of our team were aware of such approaches being proposed, if not used, in the late 1970’s. As part of Z/Yen’s Distributed Futures technology knowledge hub, we commissioned research into some of the origins of smart ledger technology. This research will be published in full later this year. Some highlights are already worth sharing.

To file a patent, an applicant must prove their idea is novel, non-obvious, and useful. Prior to filing for a patent, applicants must prove their patent is new by comparing the novelty of their idea against various databases for prior art across jurisdictions. Such work is conducted by patent attorneys, and matters. For example, in the 2014 case of Alice Corp vs. CLS Bank International, the US Supreme Court invalidated a patent “directed to an abstract idea of employing an intermediary to facilitate simultaneous exchange of obligations in order to minimize risk”. The Electronic Frontier Foundation commented that the Supreme Court had reaffirmed that merely adding "a generic computer to perform generic computer functions" is unpatentable.

Merriam-Webster defines ‘prior art’ as “knowledge that is publicly available … before the date of filing a claim for a patent for an invention”. Below is our research timeline followed by some extracts of ‘prior smarts’, i.e. available smart ledger knowledge before this wave of patent applications.

Figure_2.width-800 (2).png
Figure 2: Smart Ledger Innovation Timeline

Checksums

A checksum is a simplified calculation that allows for the quick verification of data. Checksums were certainly used for this purpose since the 1950s. Checksums and hashes (a unique signature of a data file) can blend to be the same thing. A very detailed checksum approximates a unique signature. An overly simple hash can provide great confidence that two files are the same yet have a high-collision rate. In the 1990s there is evidence of a rise of proposals for digital cash employing hashing, and around the same time rising interest in distributed time-stamping services (DTSS) and logging systems. These ideas, including hash-chaining, originated at IBM in the 1950s.

Figure 3.JPG

Checksums and error-correcting code are examples of algorithms that can verify the integrity of information without the need to check the entirety of a data set. An example comes from Hans Luhn’s Key Word in Context (KWIC) Index (1954), which was an early system for cataloguing books in an automated manner that used unique summary digests (see below). These kinds of summary functions were later formalised and became known as hash functions in the 1960s. The KWIC is an example of the principles of verifiability and immutability which became a core component of smart ledger technology.

Hans Peter Luhn (1896 -1964) developed a methodology and computer that could construct a Key Word in Context (KWIC) Index from articles of 500 to 5,000 words. Prior to KWIC, experienced archivists had to document and log these texts. Luhn’s method uniquely tagged articles to identify the text up to collision resistance (a ‘collision’ is when two differing documents have the same reference index). By the 1960s, KWIC had been adopted in numerous use cases for scientific documents and computer indexing systems. Luhn’s checksum device was able to verify the correct information was sent; this could even be by telegram or voice, without needing to send the information again or verify the data itself – similar to a hash function.

Around 1953, Amdahl, Boehme, Rochester and Samuel implemented hashing for the IBM 701 computer. Dumey (1956)[1] and Peterson (1957)[2], appear to be the first to formalise searches with hashed data structures showing its efficiency. These were later used by Merkel in “Merkel trees”, which are a specific case of hash-chaining, and in hash-chaining for passwords by Lamport (1981)[3]. Notably, Knuth attributed hash-chaining to Luhn in an internal IBM memorandum from January 1953, suggesting that discussion of an effective “blockchain” may have predated Satoshi Nakamoto’s Bitcoin whitepaper (2008) by 55 years[4].

Cryptographic Checksums For Integrity Protection

Fred Cohen’s 1987 paper discussed the use of checksums for integrity protection. The paper describes “a cryptographic … technique for verifying the integrity of information in computer systems”, using the RSA cryptosystem.

figure 4.JPG
Figure 4: From Cohen (1987), Showing The Use Of Comparing Checksums To Verify File Integrity[5]

The checksum-like function A is applied with K. This is used sequentially to determine if anything has been altered to file F by producing Checksum C. Comparison can be made with a log file to track changes to the databases while also being succinct and time-efficient compared to verifying all the data.

Block Ciphers

A hash function can ensure each document is correct given that the probability of two different records having the exact same hash becomes extremely small. The recirculating block cipher was one of the first advanced methods for enciphering a block of binary data. Data is taken in chunks and encrypted through some nonlinear transformations. When cryptographers began to develop nonlinear and ‘irreversible’ functions, cryptography became much more powerful, as any linear combination of encryption can be represented as one transformation.

Example: x2 is a ‘nonlinear’ function, as an output of 9 could have been derived from an input of either -3 or 3.

[The Rabin cryptosystem uses squaring for encryption. See: Rabin, M. (1979). Digitalized Signatures and Public-Key Functions as Intractable as Factorization. Cambridge, MA: MIT Laboratory for Computer Science.]

Figure 5.JPG

Block Chaining

Block cipher patents begin to appear in 1974 and 1975, but they had to wait for the formulation of a hash dependence, which would create a blockchain type data structure. Tamper-resistant structures were the subjects of research in the 1970s as well as encryption.

Figure 6.JPG
Figure 6: Illustration Of The Block Chain Patent From The Patent Filing

The system described in the patent above (see box) forms an effective hash dependent data structure, which comes to form the core idea of immutability in later smart ledger technology. The dependence on the preceding cipher block, creates a tamper-resistant chain that can spot any errors in the transmission. The patent refers back to other examples of block ciphering developed by IBM: US No. 3,796,830, US No. 3,798,359 and US No. 552,685.

Immutable Ledgers

Schneier & Kelsey: In 1998, Bruce Schneier and John Kelsey wrote a paper entitled ‘Secure audit logs to support computer forensics’[6], which uses a cryptographic hash function to develop a tamper-resistant ledger. The critical problem is how to hold log files on an untrusted computer. How can these log files, even if the machine is captured, be set to hold little or no useful information to the attacker? In the paper, the authors additionally show that the log files produced would be “impossible” to read or undetectably modify/destroy any data. This comes very close to blockchain and smart ledger technology as we know it.

Fast & Secure Distributed Read-only File System: David Mazières, currently a professor at Stanford University and Chief Scientist at Stellar, proposed a read-only distributed file system in 2002[7]. Clients store files in a replicated database, and use private key encryption to secure files. In Mazières’ schema, the server hashes data and transmits it to each client; the client hashes the untrusted copy and compares the hash to the server’s trusted hash to verify the copy’s integrity. The scheme was pitched as having very simple server offloads, low cryptographic costs to clients (using mainly well-known cryptographic primitives), and a universal interface, in line with the development of Bitcoin later. The Bitcoin protocol forms a universal ledger but can be accessed through any number of interfaces and in any language or wallet software as long as the transactions all obey the consensus protocols and established rules.

Figure 7: Surety Hashes Placed In The New York Times

Figure 7: Surety Hashes Placed In The New York Times

Surety & AbsoluteProof: Surety[8] was founded in 1994, and its founders were Haber and Stornetta (authors of their 1991 paper on digital timestamping). Surety placed hashes in the New York Times, appearing once a week from 1995[9]. This was more common than simply one company, and the New York Times and the field involved in the production of such tamper logs is called linked timestamping, linking creating an append only log with dependence on previous links.

Discussion

Future publications from Distributed Futures will further explore prior art from John Nash’s thoughts on cryptography, to the origins of ‘smart contracts’ in Lisp, to earlier attempts to create digital money, and the origins of ‘mining’.

blockchain patents.jpg

Cryptocurrency applications since 2009 have introduced and hastened the development of various verification methods and protocols for writing blocks to smart ledgers, ‘mining’, but it is not yet clear that this technology is economically viable on its own for widespread digital monies. Digital money applications are more about being first with a workable scheme than patenting and licensing. Being first means being able to allocate digital money to the founders to reward successful implementation and take-up.

From just the limited extracts of our historical research in this short paper, it is clear that there is a tremendous amount of prior art for the four constituent technologies behind smart ledgers. This means that people too quick to patent may find their patents rejected, or awarded but unenforceable. The heightened interest in patenting may prove more lucrative for the legal community than the smart ledger community.

For non-cryptocurrency smart ledger applications, one perplexing thought about patenting smart ledger technologies is that the very purpose of the ledgers is to share data and code among many organisations. To some degree, the quasi-monopoly that patents give, the ability to extract rents from users, goes against the mutuality inherent in economically useful applications.

Professor Michael Mainelli is Executive Chairman of Z/Yen Group. Henry Price is CEO of SI Units and a doctoral candidate at Imperial College.


References

[1] A. I. Dumey. Indexing for rapid random-access memory systems. Computers and Automation, 5(12):6–9, 1956.

[2] Peterson, W.W., 1957. Addressing for random-access storage. IBM journal of Research and Development, 1(2), pp.130-146.

[3] Lamport, L. (1981). Password authentication with insecure communication. Communications of the ACM, [online] Volume 24(11), pp. 770-772. Available at: https://dl.acm.org/doi/10.1145/358790.358797 [Accessed 15 Jan. 2020].

[4] Mehta, D. and Sahni, S. (2004). Handbook of data structures and applications. Boca Raton, FL: Chapman and Hall/CRC.

[5] Cohen, F. 1987. A cryptographic checksum for integrity protection. Computers & Security, [online] Volume 6(6), pp. 505-510. Available at: https://www.sciencedirect.com/science/article/pii/0167404887900319 [Accessed 16 Jan. 2020].

[6] Schneier, B. and Kelsey, J. (1999). Secure audit logs to support computer forensics. ACM Transactions on Information and System Security (TISSEC), [online] Volume 2(2), pp. 159-176. Available at: https://dl.acm.org/doi/10.1145/317087.317089 [Accessed 16 Jan. 2020].

[7] Fu, K., Kaashoek, M. and Mazières, D. (2002). Fast and secure distributed read-only file system. ACM Transactions on Computer Systems (TOCS), [online] Volume 20(1), pp. 1-24. Available at: https://dl.acm.org/doi/10.1145/505452.505453 [Accessed 16 Jan. 2020].

[8] Surety.com. Long-Term and Independent Proof of Record Integrity. [online] Available at: http://surety.com/digital-copyright-protection/prove-ownership [Accessed 16 Jan. 2020].

[9] Oberhaus, D. (2018). The World’s Oldest Blockchain Has Been Hiding in the New York Times Since 1995. Vice.com [online]. Available at: https://www.vice.com/en_us/article/j5nzx4/what-was-the-first-blockchain [Accessed 16 Jan. 2020].

[10] See ChainZy for the current instantiation of a smart ledger 'blockchain' designed in 1995 and implemented in 1996.