[riptheworld]

> But it is not PoW that makes the blockchain immutable. A lot of people are saying that, but they're wrong, I'm sorry.

You are incorrect. The proof of work mechanism is central to ensuring the immutability of the blockchain.

As a concrete example, suppose there are N blocks in the blockchain, and I want to change a transaction in the (N - 2) block. Obviously, this will change the hash of the (N - 1) and N-th blocks, so the decentralized network will not accept this arbitrary change.

However, if I can produce four PoWs corresponding to the new (N - 2), (N - 1), N, and (N + 1)th blocks, then I can convince the network to accept. Of course, I have to produce these four PoWs before the honest users on the network mine the next block at index (N + 1). This is extremely difficult by design. In theory, you would need the majority of the network’s computing power to carry out this attack.

In other words, the security level of the proof of work is directly related to the difficulty in modifying the blockchain.

[p4bl0]

Okay so now suppose that some one finds a way to break the hash function used in a way that allows to quickly compute partial collisions.

This person is able to mine valid blocks very quickly because they can have a number of zeros at the beginning of their hashes thanks to the vulnerability they found.

So they do what you're saying and rewrite history. In a few minutes, they start with block (N - 10), and rebuild an alternative chain up to block N and then add two new blocks so their version of the chain in longer.

Yes, what is supposed to happen, in theory and according to you, is that their version of the chain will prevail.

What would happen in practice? People would notice. A fork will be decided. Such things have happened with blockchains already, either the community, or worse, the developers, decided against the rogue version to hard switch to the original version. And everyone except the attacker will agree…

So I repeat: the only way to actually modify the recorded history is to do so discretely. And that requires computing full hashes collision. Even for a single one it is much much expensive than mining hundreds if not thousands of blocks.

Another point: if PoW is what guarantees immutability, what about PoS blockchains?

The truth is: PoW and PoS are not immutability mechanisms, they're adversarial distributed consensus mechanisms: i.e., complex ways of selecting someone at random such that no one else can dispute the choice.

[riptheworld]

> What would happen in practice? People would notice. A fork will be decided.

There's nothing in the Bitcoin protocol that explicitly prevents a longer and valid chain from being accepted. Forks happen every day where miners are competing to construct the longest accepted chain on the network (it's part of the protocol).

However, the difficulty in maliciously changing previous blocks in the Bitcoin blockchain is explicitly parameterized by the security level of the PoW mechanism. There are undergrad CS courses where this analysis is probably a homework problem.

In PoS, immutability is baked into the protocol since the block selection algorithm doesn't explicitly cause forking as it does in PoW based blockchains.

Decentralization creates trust that newly added blocks contain valid transactions, not to ensure that previous blocks don’t change. This is why the finality times of Bitcoin are strictly worse than the finality times of Algorand, or other PoS blockchains. Not because one network is more decentralized than the other, but because Bitcoin’s immutability property is hamstringed by the PoW security level.

EDIT: Anticipating your response requesting citations - here are the lecture notes from the "Foundations of Blockchain Systems" course at the University of Washington, Seattle [1]. From section 3.2, I quote:

"One property of the blockchain is immutability. This means that the chain cannot be changed given the last block in the chain. This is because it is difficult to find a hash of x that is equal to hash of y in computationally feasible time (collision-resistance). We add the qualifier “given the last block” because if we disagree on which is the last block, we may have problems. With distributed mining, there is a possibility of simultaneous mining, however these ties should be resolved quickly with proper tuning of parameters. Therefore, although we may not agree on the last block all of the time, all blocks will lead back to the genesis, starting block, and the large majority of the chain will be in agreement."

[1] https://ece595uwseattle.github.io/Scribe_notes_Lecture_3.pdf

[p4bl0]

Your citations proves my point, not yours.

> This is because it is difficult to find a hash of x that is equal to hash of y in computationally feasible time (collision-resistance).

This is exactly what I was explaining.

[riptheworld]

This is literally proof of work. I don’t know what else I can do to explain that Bitcoin’s immutability property is directly parametrized by the security level in the PoW mechanism.

You are arguing that decentralization creates immutability. Decentralization has nothing to do with hashing.

[p4bl0]

I'm sorry, it seems you really don't understand neither what I'm saying nor the citation you used.

Collision and proof of work are really not the same thing.

Here are some Python code that compares the two. If you're not convinced, I suggest you try using it to time what is actually harder and what makes a blockchain immutable. Then come back here when you found a collision :).

    import hashlib
    def h (d): return hashlib.sha256(d).hexdigest()
    
    def mine_for_PoW (d):
        nonce = 0
        while True:
            blk = f"{d}{nonce}".encode()
            sha = h(blk)
            if sha[0:6] == '000000':   ## PoW
                return sha, nonce
            nonce += 1
    
    def find_collision (d, original):
        nonce = 0
        while True:
            blk = f"{d}{nonce}".encode()
            sha = h(blk)
            if sha == original:        ## collision
                return nonce
            nonce += 1

[riptheworld]

No one is arguing that collision resistance and proof-of-work are the same things? The security of a PoW relies on collision resistance. Do you see the difference? It's subtle. Changing a block in the blockchain explicitly requires exploiting the collision-resistance property of a cryptographic hash. Why? BECAUSE YOU NEED TO PRODUCE VALID PROOFS OF WORK FROM INVALID TRANSACTIONS.