Intro
Timestamp
A timestamp is used to prove that certain information existed at a certain point in time. For example, newspapers and magazines timestamp all their content at publish time as they guarantee that the information existed before the publication. Timestamps can exist in digital or physical forms.
Blockchain
A blockchain is a growing list of blocks. Similarly to newspapers and magazines that are published periodically, blocks are published periodically. The time interval depends on the underlying protocol. Each block has a unix time that indicates when the block was published and a reference to the previous block. Several transactions can be included in a block.
Blockchain Timestamps
In our case a transaction contains the data that we would like to timestamp. In almost every public permissionless blockchain based technology transactions require fees. Fees increase as the data increase. In addition, transactions have data size limitations. Therefore, instead of our actual data we can timestamp their hash function output.
Hash Function
A hash function is a function that is used to map data of arbitrary size onto data of a fixed size. The output of a hash function is called a digest. In all the examples we use the SHA-256 hash function, which is one of the most widely used hash functions. The output of the SHA-256 is 256 bits (32 bytes) long.
sha256('Hello') =
185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
sha256('Hello, this input can be 1000 words. The output will have the same length with the previous example.') =
23129a6cf69bcb4d8a95416c0f576767996c0c1e27de5dfe06b9e73e4dda9be7
Instead of plain text, files can also be used as input.
A hash function must be deterministic, the same input several times will produce the same result.
sha256('Hello') =
185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
sha256('Hello') =
185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
Even a small change to the input should result in a digest that is uncorrelated to the initial input.
sha256('Hello') =
185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
sha256('Hello!') =
334d016f755cd6dc58c53a86e183882f8ec14f52fb05345887c8a5edd42c87b7
By knowing the digest it should be computationally infeasible to find the input (preimage resistance). Therefore, the digest can be used to demonstrate data existence without revealing the actual data.
??? =
dc72e4f96c6d3e238e7f67dce3073df8c0de1551d22d3ce662738803c9f4ea86
The actual data can be presented if a conflict arises to prove that they were used to generate the digest.
sha256('The proof') =
dc72e4f96c6d3e238e7f67dce3073df8c0de1551d22d3ce662738803c9f4ea86
Furthermore, given an input it has to be computationally infeasible to find a second input that produces the same digest (second-preimage resistance). In addition, it must be computationally infeasible to find two distinct inputs that produce the same digest (collision resistance). Collision resistance implies second-preimage resistance because the attacker can choose any input. Finally, a hash function has to be computed quickly for any given data.
Merkle Tree
A Merkle tree is a data structure. In Merkle trees every leaf node is the hash of a data block and every other node is the hash of its child nodes. The root node is called Merkle root. Merkle tree is a nice data structure to combine multiple data blocks into a single digest and prove that a data block is included in the digest.