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)
I'd say the majority of the modern non-fork networks don't use proof of work and sha256. I'm on a team building one at the moment and we're using sha3.sum512 and no proof of work for production. Some "blockchains" aren't even blockchains of sequential blocks, they are forest DAGs of just transactions.
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.
Cool, is it open sourced? how are you guys achieving consensus for different nodes? DHT over gossip protocol? Just thought Nostr over BitTorrent and/or tor network night be a good way to go.
It's not open source, we use a system that is similar to delegated proof of stake with a deterministic leader selection algorithm. dht via libp2p.
Bittorrent would be a cool way to do it. The trials I've seen with other networks over tor work in practice, however, its more fit for slower proof of work block driven networks with slower block times and less expectation for fast finality.
The shift away from PoW is largely driven by the need/expectation for semi-instant finality, which isn't feasible in 1st generation networks, systems where your transaction goes to a tx pool, waits for fee market acceptance, and then is mined into a block in an interval based in minutes with multiple confirms needed. There are pros and cons and use cases for both strategies, however the trend in defi, which is our niche, is finality in under a second, so that's the motivator behind that design decision. It's not without its faults, you're trading mining and difficulty adjustment algorithms for deterministic leader selection and absence/latency plans.
Not necessarily. There exists a concept of light mining. It's largely a research topic more than anything deployed currently AFAIK but it's certainly possible and theory wise is secure up to more or less the same bounds as blockchain consensus in general.
The partial collision is easy to verify but hard to generate, consensus is defined as "longest chain is the source of truth". If some p2p node can present you a longer chain you switch your source of truth to that one.
Generally, yes. But remember that there are difficulty adjustments, and it's conceivable that there are two chains, one being a bit shorter but with higher difficulty, and that can have precedence over the longer but easier one. The point is that you want the chain embodying most work, no matter how long.
(And note that a) the difficulty is included in the header that gets hashed, and b) it is easy to check that the block conforms to the specified difficulty.)
That's why "heavier-chain-rule" would be a better name than "longest-chain-rule", strictly speaking.
It depends on the implementation. The naive solution is to have every client hold the full 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.
Yeah at it's core a blockchain based cryptocurrency is a consensus system and decentralised resource market where the resource in question is space in the blocks within some time bound and verifiable proof of the time and state they were accepted in.
That core feature of "providing a total ordering for state changes and events with formal trust bounds" turns out to have a lot of potential uses.
Now of course truly providing correct timestamps or really any clock mechanism in a trustless way turns out to be massively difficult. And not just in a blockchain but really in any decentralised/distributed system. It's a famously unsolved problem.
There's some research[1] on how to go about providing a "global time"/"global clock" for cryptocurrencies without external trust assumptions but it's extraordinarily academic and most if not all systems just assume trusted time within some bound and hope for the best.
In a sense, a POW blockchain such as bitcoin can convey global time/global clock if all participants understand the average block propagation is 10 "minutes"? Sometimes longer, sometimes shorter but converges to 10 minutes in aggregate.
Over great distances this breaks down given limits on the speeds of transmition (speed of light), however, if transmission was instantaneous (quantum entanglement?), that would solve the dilemma of what does "now" mean light-years away given our relativistic idea of time between here and there.
Oh yeah. Sorry I misspoke a bit. I should have said that global time/clocks are an unsolved problem in non-proof-of-work systems.
Proof of work does a decent job approximating a monotonic clock but that only works when you are expending obscene amounts of energy on a global scale. And like you said it breaks down over longer distances (however luckily we don't have to deal with that too much now).
But in any non-PoW system, a "trustless" global clock is extremely non-trivial.
Thats because POW solves the Byzantine Generals problem as I understand it. Before POW, that problem was intractable (extremeley non-trivial). Its always lammented that so much energy is needed to solve the problem, although that seems to be the nature of the problem. Maybe time and energy are inexorably linked.
Well it's a bit more complex than that but the two are certainly linked given that POW is framed in the context of time complexity of the problem and the adjusting difficulty is just an equation to approximate a clock from the rate of solutions produced for a problem of a given time complexity with an approximate X amount of available resources.
There's certainly application outside of currencies. Bluesky/atproto for example is built on DIDs (decentralised IDs) and IPLD (the data format/standard of IPFS). Both are very heavily rooted in cryptocurrency tech.
There's a joke in the atproto community that it's a blockchain but without the currency because of this.
IPLD is literally a merkle tree data structure format standardised by IPFS which is heavily rooted in cryptocurrency and in fact has its own cryptocurrency created by the IPFS devs: Filecoin.
DIDs were created by cryptocurrency orgs. The standard was created by a bunch of cryptocurrency groups working with the W3C and the entire time it was being developed, it was derided by non-cryptocurrency people as just another way for cryptocurrency to scam people. It doesn't stop being related to cryptocurrency once you realise it's useful.
the joke i like to make:
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)
Not "a blockchain", since e.g. Hyperledger Fabric and other blockchains do not have the sha256 hashing and proof of work parts.
But "the" blockchain, as in Bitcoin blockchain, the most infamous one.
Title is misleading, but blog post is clear in being about Bitcoin.
I'd say the majority of the modern non-fork networks don't use proof of work and sha256. I'm on a team building one at the moment and we're using sha3.sum512 and no proof of work for production. Some "blockchains" aren't even blockchains of sequential blocks, they are forest DAGs of just transactions.
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.
Cool, is it open sourced? how are you guys achieving consensus for different nodes? DHT over gossip protocol? Just thought Nostr over BitTorrent and/or tor network night be a good way to go.
It's not open source, we use a system that is similar to delegated proof of stake with a deterministic leader selection algorithm. dht via libp2p.
Bittorrent would be a cool way to do it. The trials I've seen with other networks over tor work in practice, however, its more fit for slower proof of work block driven networks with slower block times and less expectation for fast finality.
The shift away from PoW is largely driven by the need/expectation for semi-instant finality, which isn't feasible in 1st generation networks, systems where your transaction goes to a tx pool, waits for fee market acceptance, and then is mined into a block in an interval based in minutes with multiple confirms needed. There are pros and cons and use cases for both strategies, however the trend in defi, which is our niche, is finality in under a second, so that's the motivator behind that design decision. It's not without its faults, you're trading mining and difficulty adjustment algorithms for deterministic leader selection and absence/latency plans.
"The" blockchain is still "a" blockchain. There are many possible blockchain instantiations and Bitcoin is one of them.
Literally anyone can make up a Blockchain. That's why there's a convoluted mess of crypto.
This is true in theory, but to make anything novel with any viability is a long and unclear process.
And more importantly, zero purpose other than to enrich themselves.
Good luck getting actors to spend electricity to participate in Nakamoto consensus though
I wouldn't bother. I've got no use for crypto.
Sure but how is this distributed?
Does every device hold the chain of blocks?
Yes, at least if you want to verify the whole chain.
Not necessarily. There exists a concept of light mining. It's largely a research topic more than anything deployed currently AFAIK but it's certainly possible and theory wise is secure up to more or less the same bounds as blockchain consensus in general.
The partial collision is easy to verify but hard to generate, consensus is defined as "longest chain is the source of truth". If some p2p node can present you a longer chain you switch your source of truth to that one.
In terms of Bitcoin consensus, it is actually the chain with the most work, not the longest chain.
Isn't the longest chain assumed to be the chain with the most work? Not an expert.
Generally, yes. But remember that there are difficulty adjustments, and it's conceivable that there are two chains, one being a bit shorter but with higher difficulty, and that can have precedence over the longer but easier one. The point is that you want the chain embodying most work, no matter how long.
(And note that a) the difficulty is included in the header that gets hashed, and b) it is easy to check that the block conforms to the specified difficulty.)
That's why "heavier-chain-rule" would be a better name than "longest-chain-rule", strictly speaking.
Gossip protocol.
One can run a pruned node where you only keep block info relating to your associated wallet, but you often keep the whole chain.
It depends on the implementation. The naive solution is to have every client hold the full 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
has there been any useful application of this outside of bitcoin as currency? Seems like a solid technical idea with lots of woo-woo on top of it.
You could argue the useful application has been that of a time-stamping service, which is what you need to order a transaction history.
Yeah at it's core a blockchain based cryptocurrency is a consensus system and decentralised resource market where the resource in question is space in the blocks within some time bound and verifiable proof of the time and state they were accepted in.
That core feature of "providing a total ordering for state changes and events with formal trust bounds" turns out to have a lot of potential uses.
Now of course truly providing correct timestamps or really any clock mechanism in a trustless way turns out to be massively difficult. And not just in a blockchain but really in any decentralised/distributed system. It's a famously unsolved problem.
There's some research[1] on how to go about providing a "global time"/"global clock" for cryptocurrencies without external trust assumptions but it's extraordinarily academic and most if not all systems just assume trusted time within some bound and hope for the best.
1. Permissionless Clock Synchronization with Public Setup - https://eprint.iacr.org/2022/1220
In a sense, a POW blockchain such as bitcoin can convey global time/global clock if all participants understand the average block propagation is 10 "minutes"? Sometimes longer, sometimes shorter but converges to 10 minutes in aggregate.
Over great distances this breaks down given limits on the speeds of transmition (speed of light), however, if transmission was instantaneous (quantum entanglement?), that would solve the dilemma of what does "now" mean light-years away given our relativistic idea of time between here and there.
Oh yeah. Sorry I misspoke a bit. I should have said that global time/clocks are an unsolved problem in non-proof-of-work systems.
Proof of work does a decent job approximating a monotonic clock but that only works when you are expending obscene amounts of energy on a global scale. And like you said it breaks down over longer distances (however luckily we don't have to deal with that too much now).
But in any non-PoW system, a "trustless" global clock is extremely non-trivial.
Thats because POW solves the Byzantine Generals problem as I understand it. Before POW, that problem was intractable (extremeley non-trivial). Its always lammented that so much energy is needed to solve the problem, although that seems to be the nature of the problem. Maybe time and energy are inexorably linked.
Well it's a bit more complex than that but the two are certainly linked given that POW is framed in the context of time complexity of the problem and the adjusting difficulty is just an equation to approximate a clock from the rate of solutions produced for a problem of a given time complexity with an approximate X amount of available resources.
Which part? Blockchain in general?
Blockchain and smart contracts.
There's certainly application outside of currencies. Bluesky/atproto for example is built on DIDs (decentralised IDs) and IPLD (the data format/standard of IPFS). Both are very heavily rooted in cryptocurrency tech.
There's a joke in the atproto community that it's a blockchain but without the currency because of this.
Neither DID nor IPLD have anything to do with cryptocurrency from a technical perspective. At least no more than do X.509 and ssh.
IPLD is literally a merkle tree data structure format standardised by IPFS which is heavily rooted in cryptocurrency and in fact has its own cryptocurrency created by the IPFS devs: Filecoin.
DIDs were created by cryptocurrency orgs. The standard was created by a bunch of cryptocurrency groups working with the W3C and the entire time it was being developed, it was derided by non-cryptocurrency people as just another way for cryptocurrency to scam people. It doesn't stop being related to cryptocurrency once you realise it's useful.
[dead]