Immutable data without a blockchain

immutability.md

Immutable data without a blockchain

A careful read of the Nakamoto paper reveals that the original purpose of the blockchain is extremely specialized: A completely decentralized consensus among unreliable actors. I'd like to highlight the often overlooked fact that this is exactly what the blockchain is suitable for. Any change in the conditions and you are probably doing extra work. Data immutability is a good example. Recently, especially in the mainstream media, data immutability has been presented as something that has been pioneered by blockchain technology, though it's easier to achieve similar result with more conventional means.

This is a follow up of sorts to my fairly contentless rant that temporarily revived my interest in the topic. There is possibly nothing new here, but I don't hear a lot about trusted timestamping, so I thought it might be worth mentioning.

Trusted timestamping

The RFC 3161, dating back to 2001, describes trusted timestamping, where a third party, a Time Stamping Authority (TSA), confirms that certain data existed before a particular time. The salient points are the following:

1. A hash of data x is sent to a TSA.
2. The TSA timestamps the hash at time t and signs the timestamped hash. This signed data is then returned in the response.

Assuming that the TSA can be trusted, the signature is proves that the data x existed before t. This could equally well be interpreted as "immutable data x was created at t". Physical immutability is achieved by replicating the signed data to a large number of locations.

What if you can't trust the TSA? It's trivial to make this into a sort of semi-decentralized system by introducing multiple TSAs and repeating the above process. With enough signatures from independent TSAs, creating false data quickly becomes impractical. Even under the assumption that some TSAs may not be reliable in all situations.

Could you just ditch the blockchain?

It's tempting to take this a step further and play with the thought of deprecating the blockchain in favour of some sort of a multi-TSA scheme. It's not often highlighted that there is a middle ground between a completely decentralized system, such as bitcoin, and a completely centralized system, where the transactions live in a single central database.

Consider the following rough outline for transaction, where B pays A:

0. Each TSA stores a local copy of the entire transaction history and listens for transaction data to timestamp and sign. A transaction is only signed if there is sufficient balance.
1. A gives B a list L of TSAs to validate the transaction with.
2. B creates a transaction and signs it with their private key (demonstrate ownership)
3. B obtains a signature from each TSA in L (demonstrate no double-spending)
4. B sends the transaction to A and A validates all signatures against the public keys.

In this scheme, double-spending would require B to collude with exactly 100% of L. A single instance of transaction signed by B proves that some transaction was already made. As long as L is sufficiently similar across users, double-spending should not be practical.

I'm going to leave this section open-ended, because I'm not sure even if this could ever work; perhaps it still servers to create some discussion. What I'm absolutely certain about is that this would have a far more sustainable carbon footprint than the current PoW systems.

This has been on my contemplations for a long time. Thanks for referencing the RFC for TSA.
Great Work! Kudos @mapehe !

I really like the simplicity of what you're suggesting. IMHO there are two things missing here:

1. you would like to have some kind of traceability - you would like to know what transactions have been done by whom ("whom" here may be anonymous but unique ID). This is at least needed, in order to know if a person has enough assets for a transaction. An easy way to do that is to use a blockchain ("a chain of blocks"), or how we programmers would call it - linked lists. So in your example above, this would be like e.g. the TSA adding the signature of the last known transaction to the signed "block" by B, before signing the new structure by themselves. This way every TSA can trace back all transactions and guarantee their consistency.
2. proof of work (PoW) is not here only because someone just wanted to do it. Its meaning for cryptocurrencies is twofold. For non-currency blockchains only the second meaning makes sense. But the meanings are like this: 1) PoW is here to find the "winner" who should receive the price - some small amount of bitcoins, which is termed "mining". It's like in the real world - you go to work, in order to earn your money. That's what also is happening here - your machine is working hard in order to earn a small amount of money. If you skip this part, then how should the currency grow? How should the assets be distributed across the users? You can't just "print" 1B cryptocoins and distribute them evenly across 1B users. Well, there were such tries by some countries some 70 years ago to distribute assets evenly across their citizens, but look what happened to them in the end. But this is not so important. The important thing is: 2) PoW makes it hard to modify the blockchain. Let's assume your approach works and what is stated in my point 1 is also added - now you have a blockchain and signing each new block is super fast - signing a block of data with my private key takes less than a second on my modern machine. Now, let's assume I am the best hacker in the world and I find a vulnerability in your TSA software and am able to exploit it. I can now go and hack all TSA instances with an automated script and "resign" all transactions I did, substituting the amounts of let's say $1000 with $0.01. Effectively this means, that I've spent now instead of N x $1000 only N x $0.01, thus leaving me with still a lot of money. And I can do this blazingly fast - a script which connects and exploits all TSA instances and recalculates and re-signs all hashes can be very fast, especially if I have a bot net. And since I am the person "B" from your example, I also have my own private key to "re-demonstrate ownership". But, if there was PoW, which (last time I read about it) takes 10 minutes to finish on each block, my script will not be very fast. I would now have to do M x #TSA x 10 Minutes long calculations (where M is the amount of transactions since my first transaction). This is huge, I'll never make it, especially for large M. So, some kind of "slow-down" mechanism is needed. It must not explicitly be PoW, it could be something else, which is slow AND is not pure software, since I can hack software. I could also hack hardware, but hacking the hardware of several TSA instances at the same time is not really possible.

These are at least my layman's thoughts on the above concept :)