The fundamental strength of the blockchain architecture is that it is a immutable public ledger. The fundamental flaw of the blockchain architecture is that it is an immutable public ledger.
This is a problem for privacy and fungibility, but what is really biting is scalability, the sheer size of the thing. Every full peer has to download every transaction that anyone ever did, evaluate that transaction for validity, and store it forever. And we are running hard into the physical limits of that. Every full peer on the blockchain has to know every transaction and every output of every transaction that ever there was.
As someone said when Satoshi first proposed what became bitcoin: “it does not seem to scale to the required size.”
And here we are now, fourteen years later, at rather close to that scaling limit. And for fourteen years, very smart people have been looking for a way to scale without limits.
And, at about the same time as we are hitting scalability limits, “public” is becoming a problem for fungibility. The fungibility crisis and the scalability crisis are hitting at about the same time. The fungibility crisis is hitting eth and is threatening bitcoin.
That the ledger is public enables the blood diamonds attack on crypto currency. Some transaction outputs could be deemed dirty, and rendered unspendable by centralized power, and to eventually, to avoid being blocked, you have to make everything KYC, and then even though you are fully compliant, you are apt to get arbitrarily and capriciously blocked because the government, people in quasi government institutions, or random criminals on the revolving door between regulators and regulated decide they do not like you for some whimsical reason. I have from time to time lost small amounts of totally legitimate fiat money in this fashion, as an international transactions become ever more difficult and dangerous, and recently lost an enormous amount of totally legitimate fiat money in this fashion.
Eth is highly centralized, and the full extent that it is centralized and in bed with the state is now being revealed, as tornado eth gets demonetized.
Some people in eth are resisting this attack. Some are not.
Bitcoiners have long accused eth of being a shitcoin, which accusation is obviously false. With the blood diamonds attack under way on eth, likely to become true. It is not a shitcoin, but I have long regarded it as likely to become one. Which expectation may well come true shortly.
A highly centralized crypto currency is closer to being an unregulated bank than a crypto currency. Shitcoins are fraudulent unregulated banks posing as crypto currencies. Eth may well be about to turn into a regulated bank. When bitcoiners accuse eth of being a shitcoin, the truth in their accusation is dangerous centralization, and dangerous closeness to the authorities.
The advantage of crypto currency is that as elite virtue collapses, the regulated banking system becomes ever more lawless, arbitrary, corrupt, and unpredictable. An immutable ledger ensures honest conduct. But if a central authority has too much power over the crypto currency, they get to retroactively decide what the ledger means. Centralization is a central point of failure, and in world of ever more morally debased and degenerate elites, will fail. Maybe Eth is failing now. If not, will likely fail by and by.
Eth is full of enemies, but it is also the leading edge of blockchain scaling technology.
Zk-starks and zk-snarks
Zk-snark stands for “Zero-Knowledge Succinct Non-interactive Argument of Knowledge.”
A zk-stark is the same thing, except “Transparent”, meaning it does not have the “toxic waste problem”, a potential secret backdoor. Whenever you create zk-snark parameters, you create a backdoor, and how do third parties know that this backdoor has been forever erased?
zk-stark stands for Zero-Knowledge Scalable Transparent ARguments of Knowledge, where “scalable” means the same thing as “succinct”
Ok, what is this knowledge that a zk-stark is an argument of?
Bob can prove to Carol that he knows a set of boolean values that simultaneously satisfy certain boolean constraints.
This is zero knowledge because he proves this to Carol without revealing what those values are, and it is “succinct” or “scalable”, because he can prove knowledge of a truly enormous set of values that satisfy a truly enormous set of constraints, with a proof that remains roughly the same reasonably small size regardless of how enormous the set of values and constraints are, and Carol can check the proof in a reasonably short time, even if it takes Bob an enormous time to evaluate all those constraints over all those booleans.
Which means that Carol could potentially check the validity of the blockchain without having to wade through terabytes of other people’s data in which she has absolutely no interest.
Which means that peers on the blockchain would not have to download the entire blockchain, keep it all around, and evaluate from the beginning. They could just keep around the bits they cared about.
Unfortunately producing a zk-stark of such an enormous pile of data, with such an enormous pile of constraints, could never be done, because the blockchain grows faster than you can generate the zk-snark.
So, zk-rollups, zeek rollups.
zk-stark rollups, zeek rollups
Zk-stark rollups are a privacy technology and a scaling technology.
Fundamentally a ZK-stark proves to the verifier that the prover who generated the zk-stark knows a solution to an np complete problem. Unfortunately the proof is quite large, and the relationship between that problem, and anything that anyone cares about, extremely elaborate and indirect. The proof is large and costly to generate, even if not that costly to verify, not that costly to transmit, not that costly to store.
So you need a language that will generate such a relationship. And then you can prove, for example, that a hash is the hash of a valid transaction output, without revealing the value of that output, or the transaction inputs.
But if you have to have such a proof for every output, that is a mighty big pile of proofs, costly to evaluate, costly to store the vast pile of data. If you have a lot of zk-snarks, you have too many.
So, rollups.
Instead of proving that you know an enormous pile of data satisfying an enormous pile of constraints, you prove you know two zk-starks.
Each of which proves that someone else knows two more zk-starks. And the generation of all these zk-starks can be distributed over all the peers of the entire blockchain. At the bottom of this enormous pile of zk-starks is an enormous pile of transactions, with no one person or one computer knowing all of them, or even very many of them.
Instead of Bob proving to Carol that he knows every transaction that ever there was, and that they are all valid, Bob proves that for every transaction that ever there was, someone knew that that transaction was valid. Neither Carol nor Bob know who knew, or what was in that transaction.
You produce a proof that you verified a pile of proofs. You organize the information about which you want to prove stuff into a merkle tree, and the root of the merkle tree is associated with a proof that you verified the proofs of the direct children of that root vertex. And proof of each of the children of that root vertex proves that someone verified their children. And so forth all the way down to the bottom of the tree, the origin of the blockchain, proofs about proofs about proofs about proofs.
And then, to prove that a hash is a hash of a valid transaction output, you just produce the hash path linking that transaction to the root of the merkle tree. So with every new block, everyone has to just verify one proof once. All the child proofs get thrown away eventually.
Which means that peers do not have to keep every transaction and every output around forever. They just keep some recent roots of the blockchain around, plus the transactions and transaction outputs that they care about. So the blockchain can scale without limit.
ZK-stark rollups are a scaling technology plus a privacy technology. If you are not securing peoples privacy, you are keeping an enormous pile of data around that nobody cares about, (except a hostile government) which means your scaling does not scale.
And, as we are seeing with Tornado, some people Eth do not want that vast pile of data thrown away.
To optimize scaling to the max, you optimize privacy to the max. You want all data hidden as soon as possible as completely as possible, so that everyone on the blockchain is not drowning in other people’s data. The less anyone reveals, and the fewer the people they reveal it to, the better it scales, and the faster and cheaper the blockchain can do transactions, because you are pushing the generation of zk-starks down to the parties who are themselves directly doing the transaction. Optimizing for privacy is almost the same thing as optimizing for scalability.
State of the art
We are not there yet.
In principle we know how to create a zk-stark that can prove successful execution of an arbitrary turing machine. In practice we do not.
In principle we know how to create a zk-stark that can prove verification of several other zk-starks. In practice we do not.
We have a vast multitude of zk-snark systems that can prove particular things, for example that the inputs to a transaction are equal to the outputs without revealing the transaction.
We need a turing complete zk-stark engine, one that can produce a proof that any algorithm was performed with the expected result, and do not yet have one. There are people that claim to have built them, but their source is closed.
correction added seventeenth of September
https://blog.polygon.technology/plonky2-is-now-open-source/
“Earlier this year, Polygon announced Plonky2, a zero-knowledge proving system that represents a major breakthrough for ZK tech. Plonky2 offers two main benefits: incredibly fast proofs and extremely efficient recursive proofs. It’s a huge leap forward for the ZK space, and we’ve been blown away by the response from the developer community: people want to build on Plonky2.
Today we’re proud to announce that Plonky2 and Starky are open source. They are now dual-licensed under the MIT license and Apache2.”
This is wonderful and unexpected news, but I am overwhelmed by real life events, and cannot take advantage of it until 2023
As of today, all blockchains that do not use zk-rollups are obsolete, all blockchains that rely on everyone verifying everything are obsolete. We now have the solution to the enormous and ever growing blockchain, and the enormous amount of private information it makes dangerously public.
Someone said when Satoshi first proposed what became bitcoin: “it does not seem to scale to the required size.” And ever since then people have been struggling to solve that problem. Now we have a solution.
A closed source zk-stark system is not a zk-stark system, because when Carol applies her verifier to Bob’s argument of knowledge, how can she know what it is verifying?
Further, closed source cryptography seldom actually works. When hostile outsiders take a look at it, usually falls over. They may think they have what they claim to have, but do not necessarily actually have it. They may think that their verifier is verifying the zk-stark produced by their prover, when it is actually verifying something far weaker.
We need a compiler, that, given code for an arbitrary algorithm in a language for the virtual machine, produces a prover that executes the code in virtual machine and also produces a zk-stark proving that the code was executed with the expected result, and the compiler also produces a verifier that verifies the zk-stark. And that compiler has to be open source, without magic secret unexplained codes in it.
A closed source blockchain is not a blockchain, but an unregulated bank, because those who have the closed source could do anything, and a closed source zk-stark system is not a zk-stark system, because not an argument of knowledge, but a mere claim of authority.
We know know in principle how to produce a fully scalable blockchain – but actually doing so is another thing altogether.
How a fully scalable blockchain running on zeek rollups would work
A blockchain is of course a chain of blocks, and at scale, each block would be far too immense for any one peer to store or process, let alone the entire chain.
Each block would be a Merkle patricia tree, or a Merkle tree of a number of Merkle patricia trees, because we want the block to be broad and flat, rather than deep and narrow, so that it can be produced in a massively parallel way, created in parallel by an immense number of peers. Each block would contain a proof that it was validly derived from the previous block, and that the previous block’s similar proof was verified. A chain is narrow and deep, but that does not matter, because the proofs are “scalable”. No one has to verify all the proofs from the beginning, they just have to verify the latest proofs.
Each peer would keep around the actual data and actual proofs that it cared about, and the chain of hashes linking the data it cared about to Merkle root of the latest block.
All the immense amount of data in the immense blockchain that anyone cares about would exist somewhere, but it would not have to exist everywhere, and everyone would have a proof that the tiny part of the blockchain that they keep around is consistent with all the other tiny parts of the blockchain that everyone else is keeping around.