A basic question I have is: what stops someone from re-writing history? With Bitcoin, it's the fact that it would be computationally hard. By the time you were able to "mine" more, the network has moved on. If we're talking about a private blockchain (like I see some companies pushing), what's stopping a malicious actor from simply recomputing on new data?

IBM talks about private blockchains, but it kinda seems like without spending a lot of computing power to make it infeasible to re-compute, you're relying on trusting that people won't. If I control all the machines in the private blockchain and the cost to compute the hashes is low, presumably I could replace nodes that I want to remove or alter and then just recompute.

For example, let's say that I'm trying to create an immutable ledger of emails sent for compliance purposes and I have 10,000 emails. Later, I want to hide 5 emails sent and alter 5 email's contents. I replace the remove/alter the nodes and then just re-compute the chain storing the new version of the chain on the servers I control. I then tell regulators that those emails never existed and we have the immutable block chain to prove it!

Even if a blockchain is public, what is protecting against someone disputing history? If it were computationally cheap, I could come up with a longer chain than the current Bitcoin chain with certain transactions altered to favor me. The reason I can't do that is because the proof-of-work makes it infeasible for me to re-compute a block before the network has already put a new block on the chain (presuming I control less than 51% of the compute power in the network). To recompute 10 blocks, I'd need to control an overwhelming majority of the compute power in the network.

But if the data is important and we're not giving people a big reward for mining the chain, it seems like it would be vulnerable to alteration. Sure, you could say "I saw the chain with 1,000 links and then I saw the chain with 1,100 links, but this new chain disagrees with some of the original 1,000 I had. Someone is doing something sketchy, but is it the first person trying to rewrite history and not being able to mine fast enough or is the second person rewriting history and has enough compute power to become the longest chain?" Again, with Bitcoin this isn't such a problem because PoW makes it infeasible to re-compute that stuff. However, if we're talking about a blockchain that isn't secured by PoW (or PoS), what is preventing that?

If I want to create a public ledger of all my shipments with blockchain and there are 10-50 shipments per day at various unknown times, it seems insecure. I put up a piece of shipment data to be added, and then it gets added to the chain. That's the good scenario. Now I want to rewrite history so I go back and re-compute some stuff and then for the next 20 shipments I privately compute the signatures before broadcasting to the network so that I'll have a chain 20 longer than everyone else which will replace the old chain (and with it the data I'm looking to alter).

I could just be missing a piece that makes this comment void, but it's always seemed like Bitcoin's resistance to history-rewriting is the PoW. Without that, I could simply re-compute the history, create a longer chain, and replace the current chain. Yes?