Readers already familiar with how hashes, blockchain and digital trust services work may wish to skip to the second half of the article, straight to the Guardtime KSI Blockchain implementation.
Guardtime — An Overview
Guardtime is a blockchain company founded in 2007 in Tallinn, Estonia, with the goal of solving the problem of verifying the integrity of documents at large scale.
In 2008, they developed the Keyless Signature Infrastructure (KSI) Blockchain, which is a reliable way of creating “Proof-of-Existence” artefacts for digital records at large scale.
Today, governments, military and some of the largest companies in the world use the KSI Blockchain. It’s the first blockchain based trust-service accredited by EU-eIDAS.
What is Blockchain?
A blockchain is a distributed ledger that maintains a continuously growing list of data records, cryptographically chained together against revision and tampering.
A blockchain’s security relies on two fundamental properties:
- data is appended to a blockchain linearly, and all appended data is linked together,
- no single authority decides what gets appended to the blockchain: participants reach a consensus following a predetermined scheme on the next entry to the ledger.
Together they guarantee the immutability of records.
The first property ensures that tampering with data becomes obvious, i.e., if you add, remove, or change data, you break the blockchain.
The second property ensures that even if you alter a copy of the blockchain, other members of the distributed network will not accept it.
In short, a blockchain’s security relies on consensus rules and cryptography.
I should note that a blockchain by itself is rarely a solution to problems. Rather, it sees use as a component in building solutions.
Digital Trust Services
Traditional digital trust services work with the Public Key Infrastructure (PKI). In the simplest terms, you send your document or hash to the trust service; they sign the hash with their key, and then they give you back the signed hash. Essentially, he trust services act like digital notaries.
These services are “trusted” because they undergo audits and/or are publicly certified, which gives them credibility.
However, the traditional approach has two downsides:
- You need to trust a company,
- PKI has practical scalability limits: public key cryptography is simply too slow.
KSI cuts out the middleman: it uses no keys, no signatures, and this allows it to scale to millions and billions of timestamps per second.
This throughput may seem unnecessary, but when you have vast amounts of data to sign — logs, for example — the need becomes clear.
The trustworthiness of KSI comes from widely witnessed evidence: Guardtime publishes their hashes in the newspaper, Twitter, and other sources.
To understand why this works, let’s dig into the KSI blockchain.
Hash functions take arbitrarily sized data as input and generate a unique fixed-size string as an output, called a hash value, or hash. Three important properties of hash functions are:
- one way: data mustn’t be reconstructible from only its hash value,
- unique: no two inputs should produce the same hash value (no hash collisions),
- “pure”: given the same input, the function always gives the same hash value.
Hashes are akin to human fingerprints in that they are unique for everyone: you can identify a person with only their fingerprint. You also cannot know what the person looks like just from their fingerprint.
In 2004, Ahto Buldas and Märt Saarepera came up with the world’s first formal security proof on secure hash based time-stamping schemes.
The efficiency of the KSI infrastructure relies on Merkle trees, also called binary hash trees. A Merkle tree allows to “sum up” hash values into a single hash, called root hash.
A Merkle tree takes data blocks as inputs, hashes them together in pairs of two, and via repeated application of this method, generates a single hash value called the “root hash”. For the KSI case, the data blocks are already hashes.
To reconstruct the root hash (purple) from a specific leaf (yellow), concatenating intermediate hashes (red) to the leaf is enough. Reconstructing the entire tree is unnecessary.
Therefore, for a tree with N leaves, the owner of a hash (data) only needs to store log2(N) additional hash values to regenerate the root, thus saving memory.
While the concatenation order of hashes is important, it is not a problem: order bits guarantee the order within the hash chain.
KSI Aggregation Network
The KSI Aggregation Network receives and processes the input hashes of the clients.
Each second, the network receives hashes from the clients. It builds a Merkle tree out of them and forwards it to the KSI Core Network, which will add the root hash to the KSI Calendar Blockchain. The network does everything in real-time, with sub-second times.
Because the clients need the intermediate hashes to reach the root hash from their data, the network has to send the hash chains to their respective clients. Following that, it destroys the tree as it’s no longer needed, thus saving memory.
While the actual hashes of the clients’ data don’t end up in the blockchain, one can verify them by recomputing the root hash from the source. If the hash in the blockchain matches the recomputed root hash, the source data must therefore be unaltered.
The KSI Blockchain is a “calendar” blockchain: it has a single entry for each second since 1970-01-01 00:00:00 UTC (called the Unix Epoch), and each additional second, a new block gets added.
The new block contains the root hash of the Merkle tree of that second’s client data. If no client data is available that second, the blockchain uses a dummy value instead, as it must maintain the one second pace.
Essentially, each second, the KSI Aggregation Network builds a Merkle tree and the KSI Core Network appends its root hash to the blockchain.
This approach is not only effective because it’s fast but also because the blockchain cannot grow uncontrollably: it grows at the constant rate of one block per second.
The current hashing scheme used by Guardtime is SHA-256, meaning that the hash chain grows about 2GB per year. That’s slow growth.
There is still an issue, however, as the calendar blockchain doesn’t satisfy either of the requirements of a blockchain: cryptographic linking and rules of consensus.
Linking the Blocks
To link the blocks in the blockchain, the KSI blockchain uses another Merkle tree.
The KSI Calendar Blockchain is a perpetual Merkle tree: a tree is continuously being built from the blocks in the calendar blockchain.
Guardtime periodically publishes the top hash value (temporary root hash) of that tree in media, such as newspapers (ex: Financial Times, Postimees) or Twitter. The company calls these “Publication Codes”.
Guardtime also places these publication codes in a publications file, which is digitally signed and uploaded on the web.
In summary, Guardtime’s trustworthiness comes from widely witnessed evidence, evidence which no-one can backdate or deny. Public media is the trust anchor that guarantees the KSI Blockchain’s integrity.
To decentralise the blockchain and avoid a single point of failure, Guardtime uses their proprietary KSI Core Network.
The KSI Core Network nodes get the Merkle tree root values from the KSI Aggregation Network. They then agree on the root value and append it to their own copy of the ledger and distribute it downstream to the customers in real time.
The clients are therefore part of the distributed ledger, but not of the voting process. Guardtime also makes the ledger public, so that non-customers can also view the blockchain.
Concept of Extension
Due to how time and hashing works (both are one way), future hashes cannot be linked to a previous publication code. Therefore, a signature becomes “etched in stone” so to speak only after Guardtime has published the next publication code.
When a client registers a signature, it cannot yet be linked to the future publication code — additional data from the intervening period is not available. For this reason, the client must ask for the missing hashes (red) to the publication code at the next release.
This is what’s known as the concept of extension: extending your local copy of the blockchain / Merkle tree with the missing information to reach the publication code. This process is automatic for the clients.
Extension is crucial for independence. You can only link your source documents with the publication code by knowing your hash chains to the blockchain and having a copy of the extended blockchain. Given both, you can verify hashes by computing the chains.
By using the concept of extension, previously signed data is future proofed even if Guardtime were to turn malicious, go out of business, or any other unforeseen circumstance.
On the off-chance that Guardtime would go out of business overnight, their SLA would force them to make one last publication as soon as possible to cover their clients’ latest data.
The keyless signature comes from the fact that a client can now prove a document’s:
- existence and integrity — root hash in the blockchain,
- time of certification — calendar blockchain timestamp.
It is important to keep in mind that Guardtime verifies integrity and not authenticity of documents. It receives only the hashes of documents and therefore won’t and can’t validate their contents. The authenticity of documents sent to Guardtime is the responsibility of the client.
There you have it — a not too technical overview of the Guardtime KSI Blockchain. If this topic interests you, drop a comment or read more about it by checking the publications @ Guardtime. Thanks for reading!
- Guardtime.com blog posts & publications
- Conference by Guardtime Product Manager Ivo Lõhmus