Categories
Block chain

Blockchain as understood from an Expert

I have been working in distributed systems for decades. The fundamental problem when we have multiple active sources of information is finding a way to achieve consensus – agreement about what has happened. The simplest way to reach a consensus is to have one decision-maker. If there is only a single source of “truth” as to what happened, anyone else that wants to know queries that truth.

However, disparate decision-makers often control individual resources in the real world. The challenge is to ensure that all decision-makers involved in a given event agree on the outcome. In Computer Science, it is databases that first had to face this problem.

A single database can practice techniques that ensure the consistency of events. What this means is that even if multiple pieces of information within the database need to be modified to carry out a particular operation, it is possible to ensure that even in the face of failures, the information within the database is consistent and thus definitive.

A typical model I have used when teaching this basic concept is a bank machine that dispenses cash. If you walk up to that machine, insert your card, enter your pin, and ask to withdraw $20, multiple distinct bits of information must all happen, or none happen:

  • You need to authenticate yourself (card + pin)
  • Your account needs to be debited $20
  • You need to be given $20 in currency

If anything fails in any of these steps, nothing should change: your card is returned to you, your account is not debited, and you don’t receive your cash. Such an “in balance” system is said to be consistent.

Let’s suppose that you use the ATM of a different bank than where your money is stored. Now we have distinct actors:

  • You, with your card and pin
  • The bank machine you are using
  • The bank that owns the bank machine you are using
  • The network that coordinates between the bank that owns the bank machine you are using
  • Your bank, notably your account with that bank.

Everything needs to work correctly, but now you have distinct actors. Each bank trusts the network and has presumably been vetted so that the banks and the network are all trusted. So, when the bank machine you are using verifies that you have the card and know the PIN, however, that is done is enough for the network and your bank to trust that you are who you say you are. Then the steps to dispense your funds are the same. You don’t get any cash if anything goes wrong, and your account isn’t debited.

I chose a bank as the example because banks routinely use ledgers – a list of transactions that move funds between accounts – or into your hand. Electronic ledgers are a bit different than paper ledgers in that the latter is more difficult to change after the fact since that often leaves marks. Indeed, the best practice is not to change an incorrect entry but rather to add another transaction to the ledger to correct the previous error. So, for example, we might void a transaction by posting the inverse transaction to the ledger.

How can we know when an electronic ledger has been modified? First, we could record it in something difficult to change after the fact, such as write-once media. Another approach we can use is to break our ledger up into sets of transactions. Logically, you can think of this as being like a page within a ledger. For a computer, we can then compute a “checksum” over the values within that ledger. I won’t bore you with the details, but it is possible to calculate such checksums to make it very difficult to change the records within the set and still end up with the same checksum. So, one way to protect an electronic ledger is to compute an additional value, called the “hash” or “checksum,” that depends upon all of the ledger entries within a given set. If we publish the checksums in some fashion, we now have a way to know that the ledger has not been modified after the point the checksum has been published.

A blockchain adds one more bit of information to the ledger entries: it also incorporates the checksum of the prior set of ledger entries. In other words, if we think of our ledger as being a series of pages, the first entry on each new page happens to be the checksum of the previous page. Then we compute a checksum for the new page with all the transactions. This “chains together” these sets of transactions. Now, to change the value of an older ledger page requires changing every page after it. So we actually only need to publish the most recent checksum to verify the entire chain.

This is what creates a “blockchain.” A “block” consists of:

  • The checksum of the previous block
  • A set of transactions;
  • Any other data we want in the block;

From this, we can compute the checksum of the current block. The key to “preserving” this “blockchain” is publishing those checksums. That is (more or less) how blockchains like Bitcoin and Ethereum function. They have some additional steps, but they work by publishing the ledger pages with their checksums – the blocks that make up the chain. When enough “nodes” (computers) in the network accept a new block, it becomes “confirmed” and challenging to change. Since it is easy to compute those checksums, the blocks are easy to confirm. Changing an existing block on this chain does not work because nodes do not permit changing history. Anyone with the blockchain can confirm it. The other nodes will ignore someone that attempts to change it since the changes won’t match the published information.

Thus, the real benefit of using a blockchain is that it provides a way to reach consensus and then confirm that consensus that is resilient in the face of bad actors. The simple implementations of blockchain generally require at least a majority of the participants to collude in order to rewrite the blockchain. On top of that, the cost of re-computing the blockchain, which is required to “change the past,” goes up as the blockchain proceeds.

There is a fair bit of hype around blockchain; some are deserved. In future posts, I will discuss more about some of those uses, with an eye towards how I consider them as an expert.

Categories
Claims Litigation Patents

US7,069,546

Generic framework for embedded software development

Each morning I receive an e-mail detailing the patent legal cases that have been filed from the fine folks at RPX Corporate, part of their RPX Insight service. I generally don’t have time to review all the cases, but I often pick several complaints to read. The morning as I write this (June 28, 2019) I noticed a lawsuit against Microsoft. Since I am involved in the technology space, cases involving technology companies pique my interest.

As I began to read the basic description of the case – the use of modular software development practices in embedded systems – the more it piqued my curiosity. After all, I did quite a lot of work with Windows NT starting before it was released in 1993. One of its key features was the use of it in embedded systems. Since I had intended on describing how I do patent analysis, I thought this would be a good one with which to start, as I have some expertise in this area, having co-authored Windows NT Device Driver Development, a book that is still commonly available and still relevant today.

The place to start is at the actual original patent: this is the definitive document on what this patent covers. It includes the specification, which is text and art that explain the problem as well as the general intent of the techniques of the patent itself. In my experience, having been involved in about a dozen patent applications and patent prosecutions, the specification is generally drafted with the input of both the inventor(s) and the patent attorney. This isn’t a requirement – someone familiar with the structure and drafting of patent applications as well as the technology could certainly do both. In my experience those skill sets seldom show up in a single person.

The actual patent is, however, the claims of the patent. These describe what is claimed by the inventors. The specification can explain existing technologies or alternative solutions, but those are background, not the invention. Thus, the claims set forth the specifics of the invention claimed by the patent.

Patents consist of independent claims and dependent claims. The independent claims stand on their own, while dependent claims rely upon an independent claim or another dependent claim. For example, dependent claims might specify particular details of a specific embodiment (implementation or realization) of the patent relative to some prior claim of the patent.

So I start by looking at the claims. If you have not read a patent before, you might find the format of it peculiar; that’s because it is shaped by many years of legal precedent, custom, and so forth. As the law regarding patents evolves, so does the language used in patents, so over time you will notice a shift in how patents are drafted.

This patent has two independent claims and 43 dependent claims. Claim 1 is an independent claim:

A method for producing embedded software, comprising:
providing one or more generic application handler programs, each such program comprising computer program code for performing generic application functions common to multiple types of hardware modules used in a communication system; generating specific application handler code to associate the generic application functions with specific functions of a device driver for at least one of the types of the hardware modules, wherein generating the specific application handler code comprises defining a specific element in the specific application handler code to be handled by one of the generic application functions for the at least one of the types of the hardware modules, and registering one of the specific functions of the device driver for use in handing the defined specific element; and compiling the generic application handler programs together with the specific application handler code to produce machine readable code to be executed by an embedded processor in the at least one of the types of the hardware modules.

Ideally, it is good if someone familiar with the field of the patent can read the claims and understand the invention. In reality, it is common to find that the patent uses language which is not immediately obvious. The general rule then is that if the specification defines the terms, then that is the meaning we should give that term. If the specification does not define the term, then we should give it the ordinary meaning that someone who knows the field would ascribe to it (“one of ordinary skill in the art”).

One of the challenges of patent litigation can actually be figuring out what the patent means. This often involves trying to understand the context of terminology within their historical context. So, if you’re trying to prove you understand what some term that “everybody knew” actually meant you will find yourself looking through old reference materials: books, dictionaries, devices, you name it. An easy mistake to make is to assume the current meaning is, in fact, the meaning at the time the patent was filed. Many terms do retain their meaning, but some terms shift over time as the field of the invention evolves.

So what does this mean? The term “embedded software” to me means “software that operates on a device and is inherently involved in the functionality of that device”. We use embedded software all the time – it is in numerous things, including televisions, refrigerators, cars, wearable devices, etc. Thus, this is not a particularly limiting term to use at this point. Operating systems software is typically one of the essential parts of embedded systems.

So to my first read, “A method for producing embedded software” seems like a broad sweeping statement. If you have an embedded device, you need to be able to produce the embedded software, assuming there is a computational device of some sort involved (e.g., a central processing unit).

Let’s move on then: “providing one or more generic application handler programs”. Here is where the terminology starts to narrow down what this invention is about. I’m not quite sure yet what a “generic application handler program” is (remember, I haven’t read the specification yet – I’m trying to understand the patent from the claims). My mental model at this point is that we have some programs that provide a range of functions. The term generic suggests to me that there is some mechanism for providing specialization – the idea of using a “plug-in” model. This is surprisingly common in systems software; in fact it is a common technique in software in general. The first time you sit down to write the software to talk to the very first printer, you really don’t know what that software should look like. By the time you are writing the same software for your 5th or 10th printer, you’ll have noticed that there is quite a lot of commonality about how they operate, though there are typically some sections that are specific to the device. Thus, you can extract “common functionality” and separate it from “device specific functionality”. To me, this would mesh with the term generic.

I must admit, I’m still a bit vague on the significance of “generic application handler programs” because it seems broad. But let’s continue further, perhaps things will become clearer from context: “each such program comprising computer program code for performing generic application functions common to multiple types of hardware modules used in a communication system”. Well, programs in my area do correspond to computer program code for performing… something. This is one of those points where I start thinking about what one means by “computer program code”. I suspect it won’t matter, but this is one of the areas that can quickly become fuzzy. I’ll save that for a more theoretical blog post at some point.

Anything that consists of a series of instructions that can be carried out by a computer likely falls into the category of “computer program code”; having said that, I suspect in this case they mean “binary code that corresponds to the instruction set of the computer”. I will run with that for now. That leads to “… for performing generic application functions…” This use of generic still leaves me feeling this is quite broad. The next bit helps narrow it a bit: “… to multiple types of hardware modules…” This is why I was interested. Hardware! Now we are talking about an area in which I’m steeped in experience, having written my first Ethernet driver back in 1987. If you are not familiar with Ethernet (IEEE 802.1), that is one of the earliest standardized computer communications mechanisms. And then the last bit “… used in a communication system;” I’m feeling warm and fuzzy now, because “communication system” to me normally means “network” and, as I observed earlier, that’s an area which which I’m familiar well before 2001. In fact, one of the earliest examples of noticing commonality of hardware devices was networking. Rather than ask every network device vendor to write a separate device driver for their device, we could construct a common code module that implemented the things that were common across devices (hence making it generic) and leave the much smaller bits of interacting directly with the hardware, which often varies according to the specific hardware, to a developer familiar with that hardware. For programs using the network, this is also beneficial because it means we don’t need to rewrite those programs to use different network hardware. One early example of this was the Network Device Interface Specification (NDIS) developed by Microsoft and 3COM and included in various Windows versions, including Windows NT.

At least the picture is getting clearer at this point. Let’s see where we go from here: “… generating specific application handler code to associate the generic application functions with specific functions of a device driver for at least one of the types of the hardware modules”. I think this sounds like the invention wants to generate the code so that the developer can “fill in the blanks”. This would ease the burden on the developer building the hardware specific code – much like giving them a template with comments that say “add code here to get your device to do X”. This sounds like meta-programming to me. The idea of doing this is certainly not new, but perhaps it was novel in 2001. I’d need to do more research to find out.

Fortunately, a model of what this patent means is forming for me.

Next we have “wherein generating the specific application handler code comprises defining a specific element in the specific application handler code to be handled by one of the generic application functions for the at least one of the types of the hardware modules”. Remember when I was talking about the language of patents? This is a great example of it. The goal here, as I understand it, is to try and be inclusive with the language. If we start with a communications device, we usually start simply: we have a send operation and a receive operation. But if I have a communications device that only wants to receive, perhaps because it is only monitoring network traffic, I wouldn’t need a send operation at all. Rather than list all the possible operations and the various permutations, the intent here is to capture the idea that “we have a list of ‘generic functions’ that might be implemented, but don’t all need to be implemented”.

Another example? You don’t need any support for writing to a CD-ROM. It’s a waste of time. If you look at the Windows CDFS file systems code for example, you will note that it has routines for handling reading from a CD-ROM, but not writing to a CD-ROM. Makes sense. So the intent of this language is to capture the broad range of possibilities that occur in the device space. While that CDFS code is fairly recent, it is not remarkably different than the version that Microsoft publicly distributed in 1994 (the first time I saw it).

One benefit of breaking this wall of text up into smaller bite sized chunks is that we have an opportunity to breath because the sentence continues: “wherein generating the specific application handler code comprises defining a specific element in the specific application handler code to be handled by one of the generic application functions for the at least one of the types of the hardware modules”. I admit, I had to read (and re-read) this several times to try and make sense of it. So I’ll try to translate it back: we have some code that we need to talk to the hardware. We have to have some way to map the relevant parts of that hardware specific code to the generic operation being performed. In other words, to return to my hypothetical network device, I have to have some way to map from the generic send operation to the hardware specific send operation bits – after all, I can’t call the hardware specific receive code, since it can’t send a message. That makes sense to me.

We’re making progress! Next fragment: “and registering one of the specific functions of the device driver for use in handing the defined specific element”. I’m quite familiar with the concept of registering specific functions – this is a common model for layering abstraction in systems. For example, I’ve done a fair bit of file systems work over the years and it is quite common to find that file systems “insert” themselves into the system by registering the functions they provide to perform particular operations. This sort of decomposition of functionality into “common” (or generic) and “specialized” has been around for quite a long time; certainly longer than I’ve been building systems software.

Now the last fragment: “and compiling the generic application handler programs together with the specific application handler code to produce machine readable code to be executed by an embedded processor in the at least one of the types of the hardware modules.” We have some very specific bits at this point. Note that it says compiling. That would immediately eliminate (at least for this claim) the possibility that this code is not compiled – so this wouldn’t apply if the code were interpreted. I could nit-pick the point about “together”. Would this exclude the case in which you just linked the code together (e.g., you used a pre-existing library), but I’ll defer considering that further for now. I don’t really have much problem with “machine readable code”. The limitation that it is “to be executed by an embedded processor…” is similarly not really very limiting. Essentially most, if not all, the CPUs we used in 2001 (or today) can be used as embedded processors. In fact, we normally use the same device drivers for desktop computers, which are not embedded systems, and stand-alone devices, which are embedded systems. Thus, again, not really very limiting. The last bit just says it has to have something to do with at least one piece of hardware. That makes sense to me – why bother compiling code for hardware, if that hardware isn’t present in the system?

I’ll likely re-read this again, but breaking it down in this fashion helps me better understand the general scope – of the first claim.

Actually, the second claim is much easier, since it just builds upon the first claim:

A method according to claim 1, wherein providing the generic application handler programs comprises providing an application program interface (API) to enable a system management program in the communication system to invoke the generic application functions.

So, this claim just specifies one of the generic interfaces is some sort of management operation. To allow a program to access this, we need an API. APIs are certainly not new, nor are system management programs. This claim is much easier to understand. In my experience, dependent claims typically provide these sorts of small, focused instances of the broader claim upon which they are based.

At this point I’ll break. There’s more analysis that can be done here, but I’ve made a good start. I am a bit surprised at the breadth of this patent. Such breadth is a two-edged sword for the patent holder when it comes to enforcement: the broader the claims, the more likely they are to find many people potentially infringing upon the patent, but also the more difficult it is to defend the patent against work that might anticipate this. Narrow patents, in my experience, are more difficult to enforce but when you find an instance where someone is practicing the patent, the narrow patent is more difficult for them to challenge successfully.

Lucio Development LLC v Microsoft Corp, Case 6:19-cv-283.