October 25, 2015

Three fundamental types of identifiers: Local ID, Global ID, and Provable ID

Identifiers are crucial in information technology and in our society in general. There seems to be three fundamentally distinct types of identifiers. Surprisingly, I could not find any prior text on these identifier types, so I will describe them in this blog post.
  1. Local ID. Local IDs are unique, but only within a specific context. They require an ID issuer to attain unique IDs within the context. For example, an integer can be used as an ID of a row in a database table (primary key). This ID can be used to pick one row in the specific table. The database manager is the ID issuer that ensures that each row of the table has a unique ID. Uniqness of the ID is not guaranteed outside the ID context (the database table in the example).

    Local IDs are common. Examples include: domain names, passport numbers, email addresses, variable names and US social security numbers.
  2. Global ID. Global ID schemes require no central ID issuer. An ID can be 16 random bytes for example. Version 4 UUIDs, and GUIDs are other examples of global IDs. A checksum of byte content can be used as a global ID of the content as long as the content is static.

    Global IDs are (in practice) globally unique, but they can be forged. Anyone can create a specific global ID and claim that it identifies something.
  3. Provable ID. A provable ID is an identifier that in itself can be used to prove what it identifies. The identification (id -> entity) is provable. A provable ID cannot be forged like a global ID or a local ID. No one can create a different ID and claim that it identifies the same thing. Also, no one can use a particular provable ID and claim that it identifies something else.

    A provable ID is a cryptographic construction -- a public key or a secure hash or similar. A secure hash can be used to as a provable ID of static content (content-addressable storage [3]). The GIT version control system uses a secure hash (Merkle tree) to identify commits. This is one example of a provable ID.

    To identify entities that are "live" (can compute) their public key can be used as a provable ID. An entity identified with its public key can prove possession of the corresponding private key.
Some IDs have other information included in them beyond the data needed to identify an element. Such identifiers are not considered in this blog post.

That is my take on identifiers.

[1] UUID, https://en.wikipedia.org/wiki/Universally_unique_identifier
[2] GUID, https://en.wikipedia.org/wiki/Globally_unique_identifier
[3] Content-addressable storage, https://en.wikipedia.org/wiki/Content-addressable_storage

No comments:

Post a Comment