it's a linked list with an O(exp(n)) append cost and a O(r*exp(n)) rewrite cost where r how many from the tip you wish to rewrite.
other notable: the 32 bit nonce is exhausted very quickly with modern mining systems, so they roll the timestamp forwards and backwards by a limited amount, add, remove and reorder transactions and iirc twiddle some bits in the coinbase (the first transaction the miner is allowed to add to the block to pay for the mining) to twiddle the merkle root.
the implementations of the mining systems are actually pretty cool. the host will compute the first rounds of the compression function for the first 32 bytes, and then hardware acceleration will take over for the open hash for the remainder which includes a host computed merkle hash and 32 bits of nonce + 32 bits of timestamp (with some maybe 8-10 bits of entropy to play with). so the host computes these new merkle hashes and partial sha2 sums, but then farms out the open hash state to the hardware to spin and check on timestamps and nonce values. (although newer stuff may need to compute the merkle hashes in hardware too)
But "the" blockchain, as in Bitcoin blockchain, the most infamous one.
Title is misleading, but blog post is clear in being about Bitcoin.
I think the author's heart is in the right place and I'm thankful that it's being discussed on HN, as blockchain discussions can be a bit hit or miss here.
Does every device hold the chain of blocks?
One can run a pruned node where you only keep block info relating to your associated wallet, but you often keep the whole chain.
The lightweight solutions come in two flavors, the easy "good enough" solution and the much harder ideal/zero trust solution.
The easy solution (light clients) to avoiding carrying the full chain is to simply rely on some set of known/trusted "beacon" servers that you are willing to trust to relay you the chain state and send you what information you need.
The hard solution is called a "super light" client. One of the famous super light client implementations is called flyclient[1]. It relies on some tricks with proof of work to only store log2(n) blocks out of the n blocks in the whole chain. It gives you enough security to be able to verify that your chain is valid and constructed from the origin block as well as allowing it to use the longest chain rule to decide what chain is the current "official" chain for the network just like you would with a full chain history.
There's another approach called NiPiPoWs [2] (non-interactive proofs of proofs-of-work) which is conceptually similar but is a bit more generally useful (outside of just as a light client system). A few networks adopted it but idk how prevalent its use is nowadays.
Note that flyclient, NiPiPoWs and most super light clients tend to rely on properties of proof of work as well as UTxO accounting models which disqualify their use for most networks. Cardano at the very least seems to have figured their own version out [3][4] and it exists kind of as a conceptual redesign of NiPiPoWs but for stake based systems (and actually came out of NiPiPoW research).
And of course super light clients still require miners to hold the full chain state generally but there's work[5][6] on how to do "light mining" which of course would allow everybody to abandon old chain state and only keep the data they care about.
Note: a lot of the research I linked is inter related as these are the researchers I kept up more closely with last time I was deep in the ecosystem but there's a lot of work on the topic in general coming at these problems from different angles.
--------------------------
1. Flyclient: Super-Light Clients for Cryptocurrencies - https://eprint.iacr.org/2019/226
2. Compact Storage of Superblocks for NIPoPoW Applications - https://eprint.iacr.org/2019/1444
3. Mithril: Stake-based Threshold Multisignatures - https://eprint.iacr.org/2021/916
4. The velvet path to superlight blockchain clients - https://dl.acm.org/doi/abs/10.1145/3479722.3480999
5. Mining in Logarithmic Space - https://dl.acm.org/doi/abs/10.1145/3460120.3484784
6. SNACKs: Leveraging Proofs of Sequential Work for Blockchain Light Clients - https://eprint.iacr.org/2022/240
