Almost. Proof-of-work is an anti-spam mechanism (originally invented for email, as Hashcash). Bitcoin needs this, since it treats the longest chain as "correct".

For example, if we used a public-writable git repo to track our cryptocurrency transactions, it would have the Merkle structure required for append-only/immutable-history. However, we could get lots of diverging branches; e.g.

                  +--- Commit sending all my money to Alice
                  |
  Parent commit --+
                  |
                  +--- Commit sending all my money to Bob

Who gets my money? The consensus mechanism used by Bitcoin will choose the branch with the longest history. In the above case they're equal, so we wait until some more commits appear. If more commits appear on the Alice branch, then that's chosen as the "correct" one. However, Bob can later spam a bunch of commits on top of the other branch (e.g. just sending one coin back-and-forth), until that branch becomes the longest. The consensus will then change, to consider that branch as the "correct" one, and Alice loses all the money (as does anyone she previously sent it to!).

Proof-of-work makes this spamming much harder. All miners will be trying to add blocks to the longest branch they're aware of (picking arbitrarily, in case there are multiple), since it's unlikely any shorter chain will be able to overtake it (this is a largely self-fulfilling prediction!).

I know all this, thanks.

Preventing double spending is a feature of the consensus mechanism indeed, if it is augmented with other rules (longest chain wins), but immutability does not rely on it, as I said in the comment you are replying to.

EDIT: I've updated my previous comment to make it clearer that what I'm saying is "PoW is not an immutability mechanism" (to which answering "you are wrong, PoW prevents double spending" makes little sense).

You almost understand it, but are missing the actual role of proof of work.

Merkle tree makes verifying the blockchain datastructure easier, and enables older blocks to be further secured by newer blocks.

Proof for work however makes producing an entirely alternive blockchain expensive. When looking at the bitcoin blockchain, you can prove exactly how much energy was used to make it, and know that energy was not used for making any other variant. This means you can be confident the blockchain is not a altered forgery meant to defraud you, as this attack would require spending all of that energy again.

Yes, proof of work is a consensus mechanism. But modifying a block discreetly would require a full collision on its hash. Even without proof of work. This is what makes a blockchain immutable, and is not a specificity of blockchains, nor of PoW.

I'm not talking about a discreet modification of the blockchain. When you bootstrap a bitcoin client, you need to be use that the blockchain is the real one without having to trust another party, otherwise someone could give you a completely different version. By incorporating proof of work, you can prove that the copy of the blockchain you have needed X amount of energy to create. This is what I sort of agree with you that immutability is not the right technical word for this property, but that is what I was getting at.

Bootstrapping a client requires the same trust in the source from which you're getting the blockchain history, with or without PoW. PoW doesn't play a role here. But you're right that immutability does. What can give you confidence is that the version of the blockchain that you got is consistent with what others have and can show you (i.e., that you will be able to be a part of the network). This is the "distributed" part of what make immutability. The amount of energy spent until then plays no role here.

No, you do not have to trust the source when bootstrapping a client. The proof of energy needed to construct the blockchain is what ensures that the copy you receive is likely to be a held as the consensus, since it would be prohibitively expensive to have multiple versions. Without an energy expenditure, the source could fabricate the entire blockchain just to attack you.

I never said you had to trust the source, I said that the necessary level of trust is the same (and it is indeed zero).

So yes, PoW can give you confidence, but it is unnecessary in practice. Well, let's say it's an additional security measure where something else more trivial is already enough.

When you get a copy of the blockchain, verifying if all the Merkle tree structure (without even checking for the PoW) and comparing the last hash (or the few last hashes) with what you see on the network from other sources is enough to be sure that your copy is valid. Because providing you with a fake chain which still has the same last hash would require to have at some point (for the block the attacker –i.e., the source of your copy of the blockchain– wants to modify) found a full collision, which is much more difficult than computing alternative valid PoW.

So yeah, here PoW can give you confidence in the copy of the blockchain you get without having to even minimally interact (just looking at a blockchain explorer not controlled by your source for example) with others. But the whole point of the tech is to interact otherwise you don't need to bootstrap a client. So this refinement makes little to no sense.

I think you are just not getting it. In my scenario (downloading the blockchain from nothing and bitcoin not having any proof of work scheme), you would not need to find a full collision as you don't have any hash that you trust to check against anyway. The blockchain you downloaded could have been entirely made up by one person-- e.g. all of the addresses are opened and signed by them, etc. The entire thing is fake. This would be possible to construct with almost no energy, because we have removed proof of work. There would be no way to determine if the blockchain data is real

You keep referring to other consensus mechanisms that are not really trustable without the PoW foundation (looking at other copies on the network, blockchain explorer). The beauty of PoW is that it speaks for itself-- you could download the data over an untrusted network with just one peer, and still be confident you got the real thing, because you can prove energy was sacrificed for its construction.

PoW has other benefits beyond this quite silly scenario, I am just explaining it again as you don't seem to get it.

I'm an associate professor of computer science, and my PhD was in cryptology. I think I know a bit about what I'm talking about here. Please stop assuming people you are talking to are just "not getting it" and try to make an actual effort to think about the answers you get.

I'm not talking about other consensus mechanisms. We were first discussing what makes a blockchains immutable, I already explained why PoW is not necessary for that. Then you reframed the discussion to how can you trust that a copy of the blockchain you were just given by someone you don't trust is valid, and you are right that PoW is a solution to this specific problem. My point, again, is that it is an unnecessarily costly solution for this specific problem, because the properties that makes a blockchain immutable (Merkle structure + distribution) are already enough to ensure that in practice, because a fake blockchain copy, even without PoW, will have a different last hash from the real one, and it will be easy to see that by simply comparing it with others sources (if you trust no one, which is one of the requirements for blockchains to be useful, you just need to do that with multiple sources to gain enough confidence, typically ones that are very public and would be easily denounced if they lied). And anyway by participating in the blockchain protocol it will be obvious very soon that your copy doesn't match with everyone else's.

The only way this strategy won't work is if the last hash of the Merkle structure is valid while the blockchain copy is not, and the only way for this to happen is if a full collision has been found on the modified block. Which is way more costly than building a PoW valid hash.

Let me take an example with another technology that has the same immutability properties as blockchains do but don't use PoW: Git.

If you want to get a copy of the git repository of a project and you clone it from my version of the repository, either it is the real repository and everything is fine, or it is not —for example I could have introduced a backdoor somewhere in my version of the project— and then there is two possibilities:

1- Using the copy you downloaded from me you won't be able to participate (push or pull) in the project with anyone else than me because the commit log of the copy you got is incompatible with everyone else's version of the repository. You'll quickly understand that something's wrong with mine, and it will even be easy to see at which point the commit history diverges from the other copies of the repository that you attempt to collaborate with.

2- I've added my backdoor in a past existing commit, and found a collision in its hash to make it have the exact same hash as the original version of the commit (the one without my backdoor), and I have rebuild the exact same commit history from there. But here it requires me to have computed a full collision, which is actually impossible (at least much more so than computing a valid PoW hashes for a few commits after adding my backdoor), as long as there is no vulnerabilities discovered in the hashing algorithm.

Now, if you never interact with anyone else than me, I don't have to find a collision because my commits hashes won't be compared to any others, and then you are right to say that you won't be able to know about the backdoor and that using PoW would make this scenario less plausible (not impossible, but way less plausible) in terms of cost for me. But, even more in the case of bootstrapping a blockchain client, it is the very idea of only interacting with the person you got a copy of the blockchain from that makes no sense.

If you are going to draw attention to your identity and credentials, and also ask the other party to engage more kindly, maybe you shouldn't categorically call the people you are engaging with "idiots" on other platforms, especially given your profession is education. Credentials also are not a proof of understanding something.

Your analysis of git makes complete sense to me. I understand how git uses hashes and merkle trees to prevent tampering of data. It is also a good analogy in that bitcoin uses similar properties. I am furthermore perfectly happy to trust a single authoritative source (or trusted peer) when initializing a git repo, it works better that way. But git is not solving the same problem as bitcoin.

You concede that PoW is a solution to this problem, but that it is "unnecessarily costly". But you haven't given a solution to the problem that costs less, only argued that in practice the problem has assumptions that are in practice not necessary. You seem to believe that bitcoin without PoW could still in practice arrive at a consensus through either being able to check that a last block hash is the same as the "real hash", or that you would be able to compare your value to multiple sources. These ideas both rely on another consensus system outside of what is promised by bitcoin itself-- either a trusted third party to enshrine what hash is "real", or being able to rely on a consensus merely based on some number of network peers. Number of peers will not work by itself, because there is almost no cost for an attacker to create many dishonest peers. Note that the purpose of an attack of this kind is not merely to defraud users of bitcoin, but could also be a denial of service attack. Seeing peers with different blockchain history would make the network unusable.

I also don't understand the hangup over PoW and immutability. Immutability is the concept of data that is not changed. If you have a more precise definition, please give it. This could be split into the idea of a design principle, versus the idea of enforcement of immutability. E.g. using an immutable data structure in a trusted programming environment does not need enforcement. We are only talking about the enforcement aspect. A hash digest is a really strong, almost perfect enforcement-- finding a collision is in practice impossible. A digest hash only guarantees that "if trust the hash, I should trust data that matches the hash also". On the otherhand, PoW does act as a soft form of immutability, using economic barriers rather than cryptographic guarantees. PoW guarantees that "this data could not have been produced, and could not be further changed without expending some amount of physical power, and therefore there are unlikely to be variations of this". This effect is orthogonal to the internal immutability provided by hash digest / merkle trees.

> But you haven't given a solution to the problem that costs less, only argued that in practice the problem has assumptions that are in practice not necessary.

Aiming for solutions to problems that do not exist is a thing among blockchain aficionados, but I'm not one. Yet, remark that I also addressed the concern that if you do not interact with anyone else than the source of your blockchain copy, PoW makes it largely unlikely, but not impossible, that they would have tempered with the copy they provided you. So even in this scenario you partly rely on broader interactions.

> I also don't understand the hangup over PoW and immutability.

This whole discussion was started by my answer to your claim that “It [PoW] is not a waste, but a sacrifice made to make the blockchain strongly immutable.”.

I don't think it is worth discussing this further.

Cool, you haven't addressed any of the substance of my comment, and made a disparaging remark towards the group of people who think differently from you about blockchains.

Confidently incorrect.