Jim's Blog

A whole lot of shills have been posting a whole lot of mostly valid criticisms of Bitcoin, and I have been silently suppressing them, because I doubt their capability and willingness to have a genuinely informative discussion of Bitcoin, rather than randomly and unresponsively spewing fear, uncertainty, and doubt from scripts compiled by morons who did not understand these problems in the first place.

But the issues need discussion anyway.

When Bitcoin was just a gleam in Satoshi’s eye, the scaling problem was foreseen, and in 2016-2017, it bit.

If we don’t do anything to fix it, then Bitcoin scales by everyone having only a custodial wallet, because only banks and megacorporations can afford the transaction fees, and Bitcoin by slow and imperceptible degrees becomes a CBDC, as was foreseen from the beginning. And since Satoshi had his idea, we have been casting about for solutions. And since the scaling crisis started to bite, casting around for quick fixes to get a bit more scaling to postpone the crisis for a few more years, Lightning Bitcoin being one such quick fix, and L-BTC another.

But high transaction fees are biting Lightning. The number of channels has stopped growing, and more and more people are using custodial lightning wallets. (Partly because genuinely self custodial full routing lightning wallets are really bad, and are designed for someone with good linux administration skills who generally uses the command line, and has a dozen linux computers in his basement without screens or keyboard, with which he interacts over his home network by ssh and xrdp. Partly because setting up a bunch of routing channels is expensive, and rapidly getting more expensive. Partly because existing tools for setting up a useful set of channels are not very useful. These lightning tools are designed by a small group of insiders working full time at lightning related jobs to be used by a small group of insiders working full time at lightning related jobs.)

Lightning, like the bitcoin base layer, is turning into a custodial solution.

L-BTC works, and Blockstream plans to use it to take down SWIFT. But they have a permission and trust based consensus system, which centralisation makes a whole lot of scaling easy, but unlimited scaling hard. The more you scale that, the more it turns into a CBDC.

Well: Now we know in principle how to solve the problem. The final and permanent solution being recursive snarks, and the use of recursive snarks to shard the reliable broadcast channel. Which Polygon is planning to implement for the Ethereum ecosystem, but has not yet quite implemented.

Litecoin’s bulletproofs, which are almost snarks, and are based on the same technology (polynomial commitments) also support sharding in principle, though not in Litecoin as implemented today, but no one has quite figured out how to support contracts on bulletproofs, other than contracts which are purely scriptless scripts.

Polygon’s alarmingly centralised and anti privacy solution scales without limit.

Giap’s blog has the latest hot information about the latest and greatest techniques for polynomial commitments and all that stuff, but unfortunately very little information as to how fast these actually work on real world problems and how big the proofs are, because as yet very few of these techniques have actually been applied to the real world problems we need to solve.

There are three kinds of useful polynomial commitments. (I am ignoring DARKS as useless)

KZG10, used by Polygon, is based on pairing elliptic curves which have constant time scaling. Unfortunately operations on pairing curves are very slow, and operations on pairing curves with useful security are very very slow. So Polygon has gone with a pairing curve of only eighty bits security, which is not enough. Breaking this requires the breaker to search approximately 2⁸⁰ cases. Which is breakeable in reasonable time for a vast system of special purpose asics analogous to the bitcoin mining network.

Also KGZ10 requires trusted setup to establish a special trusted set of curve parameters. It is very difficult to do trusted setup in a way that anyone should trust, and Polygon has not even tried to do so.

FRI, also used by Polygon and Starkware to implement zkstarks, which are a kind of snark, are fast, because hashes are so much faster than elliptic curves and vastly faster than pairing curves, but inconveniently large. So you don’t want to communicate them over the internet as part of your protocol, and in Polygon’s implementation, they always get passed around in a big data center, hence centralisation. And they scale as log(d)², which for problems of interest is apt to get inconveniently larger, so Polygon combines them with KZG10 to control the size.

IPA uses ordinary elliptic curves, which are reasonably fast, even though vastly slower than FRI’s hashes, small enough to be passed around over the regular internet, though much bigger that KZG10, and need no trusted setup, and scale as log(d). These are used by Litecoin for bulletproofs.

The relevant libraries for IPA based proofs are Halo2 and NOVA. Which are not exactly libraries, more like technology demonstrations. You have to write your own library. The available source code is not really in a useful state. You have to pull it out of Litecoin and Elements. To implement recursive snarks over a Merkle tree with the snark recursion paralleling the Merkle tree recursion it would be necessary to extract Polygon’s code for doing hashes inside the proof engine, move it to IPA and HALO2, and then implement recursion using NOVA.

Monero does not scale. Litecoin’s mweb addresses are not scalable, but would not be hard to make scalable by sharding the hogex. It would be necessary to introduce yet another new form of address, which would be the same as an mweb address except that it would run on a sharded reliable broadcast channel.

Polygon’s aggregated blockchain is shardable because of recursive snarks, but Litecoin’s bulletproofs, though they have lesser capabilities that snarks (hard to do contracts in a bulletproof) have most of the capabilities of snarks, among them sharding.

You can prove anything with bulletproofs, including, as in Halo2, snarks, but it is apt to be slow and the proofs large. So you have to optimise for a particular use case, and when you have optimized, your bulletproof based system is no longer general purpose, thus its commits are no longer snarks. Which ties your hands if you want contracts.

Litecoin addresses the contract problem by pegging money into and out of the hogex. Which if combined with sharding would mean that contracts could only function within a single shard. But that is acceptable for a whole lot of contract applications, and you could always connect a regular contract to a scriptless script, which can operate between shards and between separate blockchains.

Litecoin’s bulletproofs have no trusted setup, and 126 bits cryptographic security, which should suffice for a few centuries. I have not really looked at Blockstream’s Elements yet.

From the very beginning of bitcoin, people worried that it could not scale to the required size.

It does not scale because it is a massively replicated public ledger. Thus any real solution means making the ledger not public. Which means either centralization, a central bank digital currency, which is the path Ethereum is walking, or privacy. You cure both blockchain bloat and blockchain analysis by not putting the data on the reliable public broadcast channel in the first place, rather than doing what Monero does, putting it on the blockchain in cleverly encrypted form, bloating the blockchain with chaff intended to obfuscate against blockchain analysis.

I have for some time remarked that recursive snarks make a fully private, fully scalable, currency, possible. But it seems this was not obvious to everyone, and I see recursive snarks being applied in complicated convoluted stupid ways that fail to utilize their enormous potential. This is in part malicious, the enemy pouring mud into the tech waters. So I guess need to explain.

A zk-snark or a zk-stark proves that someone knows something, knows a pile of data that has certain properties, without revealing that pile of data. Such that he has a preimage of a hash that has certain properties – such as the property of being a valid transaction. You can prove an arbitrarily large amount of data with an approximately constant sized recursive snark.

A recursive snark is a zk-snark that proves that the person who created it has verified a zk-stark that proves that someone has verified a zk-snark that proves that someone has verified …

This explanation is going to require you to know what a graph, vertex, edge, root, and leaf is, what a directed acyclic graph is, what a hash is, what a blockchain is, and how hashes make blockchains possible. And what an sql index is and what it does, and what a primary sql index is and what it does. You need to know what a transaction output is in the context of blockchains, and what an unspent transaction output (utxo) is. Other terms will be briefly and cryptically explained as necessary. All the crypto shills must do the homework that they have been so egregiously neglecting, or else will be silently blocked. I am heartily sick of crypto shills confidently dumping scripts prepared for them by scriptwriters almost as stupid and ignorant as themselves.

A struct is simply some binary data laid out in well known and agreed format. Almost the same thing as an sql row, except that an sql row does not have a well known and agreed binary format, so does not have a well defined hash, and a struct is not necessarily part of an sql table, though obvious you can put a bunch of structs of the same type in an sql table, and represent an sql table as a bunch of structs, plus at least one primary index. An sql table is equivalent to a pile of structs, plus at least one primary index of those structs.

A merkle graph is a directed acyclic graph whose vertices are structs containing hashes

A merkle vertex is a struct containing hashes. The hashes are the edges of the graph. So using recursive snarks over a merkle graph, each vertex has a proof that proved that its data was valid, given that the vertices that its edges point to were valid, and that the peer that created the recursive snark of that vertex verified the recursive snarks of the vertices that the outgoing edges (hashes) of this vertex points to.

So, you have a merkle chain of blocks, each block containing a merkle patricia tree of merkle dags. You have a recursive snark that proves the chain, and everything in it, is valid (no one created tokens out of thin air, each transaction merely moved the ownership of tokens) And then you prove that the new block is valid, given that rest of the chain was valid, and produce a recursive snark that the new block, which chains to previous block, is valid.

A blockchain is a merkle chain and a reliable broadcast channel. In Bitcoin the merkle vertices are very large, each block is a single huge merkle vertex, and each block lives forever on an ever growing public broadcast channel. It is impractical to produce a recursive snark over such huge vertices, and attempting to do so results in centralization, with the recursive snarks being created in a few huge data centers. So we need to structure the data as large dag of small merkle vertices, with all the paths through the dag for which we need to generate proofs being logarithmic in the size of the dag.

A merkle patricia tree is a representation of an sql index as a merkle tree. Each edge of a vertex is associated with a short bitstring, and as you go down the tree from the root (tree graphs have their root at the top and their leaves at the bottom, just to confuse the normies) you append that bitstring, and when you reach the edge (hash) that points to a leaf, you have a bitstring that corresponds to path you took through the merkle tree, and to the leading bits of the bitstring that make that key unique in the index.

So a merkle patricia tree and the structs that its leaf edges point to is an sql table that you can generate recursive snarks for, which can prove things about new transactions to be added to that table. We are unlikely to be programming the blockchain in sql, but to render what one is doing intelligible, it is useful to think and design in sql.

So with recursive snarks you can prove that that your transaction is valid because certain unspent transaction outputs were in the sql index of unspent transaction outputs, and were recently spent in the index of commitments to transactions, without revealing which outputs those were, or what was in your transaction.

It is a widely shared public index. But what it is an index of is private information about the transactions and outputs of those transactions, information known only to the parties of those transactions. It is not a public ledger. It is a widely shared public sql index of private ledgers. And because it is a merkle tree, it is possible to produce a single reasonably short recursive snark for the current root of that tree that proves that every transaction in all those private ledgers was a valid transaction.

Oops, what I just described is a whole sequence of complete immutable sql indexes, each new block a new complete index. But that would waste a whole lot of bandwidth. What you want is that each new block is only an index of new unspent transaction outputs, and of newly spent transaction outputs, which spending events will give rise to new unspent transaction outputs in later blocks, and that this enormous pile of small immutable indexes gets summarized as single mutable index, which gets complicated. I will get to that later – how we purge the hashes of used outputs from the public broadcast channel, winding up with a public broadcast channel that represents a mutable index of an immutable history, with a quite a lot of additional house keeping data that tells how to derive the mutable index from this pile of immutable indices, and tells us what parts of the immutable history only the parties to the transaction need to keep around any more, what can be dumped from the public broadcast channel. Anything you no longer need to derive the mutable index, you can dump.

The parties to a transaction agree on a transaction – typically two humans and two wallets, each wallet the client of a peer on the blockchain.

Those of them that control the inputs to the transaction (typically one human with one wallet which is a client of one peer) commits unspent transactions outputs to that transaction, making them spent transaction outputs. But does not reveal that transaction, or that they are spent to the same transaction – though his peer can probably guess quite accurately that they are.

In the next block that is a descendant of that block the parties to the transaction prove that the new transaction outputs are valid, and being new are unspent transaction outputs, without revealing the transaction or the inputs to that transaction.

You have to register the unspent transaction outputs on the public index, the reliable broadcast channel, within some reasonable time, say perhaps below block height (⌊h/32⌋+2)*32, where h is the block height on which the first commit of an output to the the transaction was registered. If not all the inputs to the transaction were registered, then obviously no one can produce a proof of validity for any of the outputs. After that block height you cannot register any further outputs, but if you prove that after that block height no output of the transaction was registered, you can create a new unspent transaction output for each transaction input to the failed transaction which effectively rolls back the failed transaction. This time limit enables us to recover from failed transactions, and, perhaps, more importantly, enables us to clean up the mutable sql index that the immense chain of immutable sql indexes represents, and that the public broadcast channel contains. We eventually drop outputs that have been committed to a particular transaction, and can then eventually drop the commits of that output without risking orphaning valid outputs that have not yet been registered in the public broadcast channel.

So that the public broadcast channel can eventually dump old blocks, and thus old spend events, every time we produce a new base level block containing new events (an sql index of new transaction outputs, and an sql index table with the same primary of spend commitments of past unspent transaction outputs to transactions) we also produce a consolidation block, a summary block that condenses two past blocks into one summary block, thus enabling the two past blocks that it summarizes to be dropped.

Immediately before forming a block of height 2n+1, which is a block height whose binary representation ends in a one, we use the information in base level blocks 2n-3, 2n-2, 2n-1, and 2n to produces a level one summary block that allows base level blocks 2n-3 and 2n-2, the two oldest remaining base level blocks to be dropped. When we form the block of height 2n+1, it will have an edge to the block of height 2n, forming a chain, and an edge to the summary block summarizing blocks 2n-3 and 2n-2, forming a tree.

At every block height of 4n+2. which is a block height whose binary representation ends in a one followed by a zero, we use the information in the level one summary blocks for heights 4n-5, 4n-3, 4n-1, and 4n+1, to produce a level two summary block that allows the level one summary blocks for 4n-5 and 4n-3, the two oldest remaining lever one summary blocks, to be dropped. The base level blocks are level zero.

At every block height of 8n+4. which is a block height whose binary representation ends in a one followed by two zeroes, we use the information in the level two summary blocks for heights 8n-10, 8n-6, 8n-2, and 8n+2, to produce a level three summary block that allows the level two summary blocks for 8n-10 and 8n-6, the two oldest remaining level two summary blocks, to be dropped.

And similarly, for every block height of 2^m+1*n + 2^m, every block height whose binary representation ends in a one followed by m zeroes, we use the information in four level m summary blocks to produce a level m+1 summary block than enables the two oldest level m summary blocks to be dropped.

We summarise the data in the earliest two blocks by discarding every transaction output that was, at the time those blocks were created, an unspent transaction output, but is now marked as used in any of the four blocks by committing it to a particular transaction. We discard commits which refer to outputs that have now been discarded by previous summary blocks and have timed out, which is to say, commits in a level m summary block being summarised into a level m+1 summary block that reference outputs in the immediately previous level m+1 summary block. However if, a commit references an output that is now in a summary block of level greater than m+1, that commit has to be kept around to prevent double spending of the previous output, which has not yet been summarised away.

We produce the summary block of past blocks just before we produce the base level block, and the base level block has an edge pointing to the previous base level block, a chain edge, and an edge pointing to the just created summary block a tree edge, a chain edge and a tree edge. And when we summarize two blocks into a higher level summary block, their chain and tree edges are discarded, because pointing to data that the reliable broadcast channel will no longer carry, and the newly created summary block gets a chain edge pointing to the previous summary block at the same level, and tree edge pointing to the previous higher level summary block.

We have to keep the tree around, because in order to register a commit for an output in the blockchain, we have to prove no previous commit for that output in any of the previous blocks in the tree, back to block or summary block in which the output is registered. Only the client wallets of the parties to the transaction can produce a proof that a commit is valid if no previous commit, but only a peer can prove no previous commit. Once all the necessary commits have been registered on the reliable broadcast channel, only the client wallets of the parties to the transaction can produce a proof for each of the outputs from that transaction that the transaction is valid. They do not need to publish on the reliable broadcast channel of what transaction that was, and what the inputs to that transaction were.

So we end up with the blockchain only carrying order log(h) blocks where h is the block height, and all these blocks are likely to be of roughly comparable sizes to a single base level block. So, a blockchain with as many transactions as bitcoin, that has been running as long as bitcoin, will only occupy a few dozen megabytes of disk storage, rather than near a terabyte. Bitcoin height is currently near a hundred thousand, at which height we will be keeping about fifty blocks around, instead of a hundred thousand blocks around.

And when it gets so big that ordinary people cannot handle the bandwidth and storage, recursive snarks allow sharding the blockchain. You cannot shard the bitcoin blockchain, because a shard might lie, so every peer has to evaluate every transaction of every shard. But with recursive snarks, a shard can prove it is not lying.

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.

As are many non FIPS compliant cryptographic libraries. We know from the Snowden leaks that the NSA has spent hundreds of millions of dollars trying to make sure that cryptographic implementations have backdoors supplied for the NSA.

A good way to make money is to construct a cryptographic library, and, if it gets to be widely used, a mysterious and secretive generous benefactor will show up.

To resolve the dragnet problem for passwords, since I cannot help using backdoored software, what I do is have a long master password, from which I generate for each account a ninety six bit random gibberish password.

Any one cryptographic algorithm is usually fine by itself – nothing is wrong with AES256 and SHA256, though there is something very wrong with AES128 as usually used. Used correctly, AES128 is fine, but it never is used correctly.

But any one cryptographic algorithm is useless by itself. To do anything useful, has to be integrated with several other algorithms, an api provided to access and use that integration, and then another library has to use the cryptographic library through that API. And that integration, api, and libraries using libraries, is where the mischief usually is.

Typically you have one flaw, which is obscure, complicated, relatively harmless by itself, and another flaw in something totally unrelated, which is also obscure, complicated, and relatively harmless by itself. You put all these flaws together, with industrial scale precomputation and industrial scale collection of hashes of secrets, and all the encryption falls apart. The Snowden slides would seem to suggest that the NSA has broken the SSL TLS algorithms used in most vpns.

Every major state spy agency, and several private agencies, attempt to collect every face that has ever appeared on the internet, every email address, every username, and every password, and link them together.

The mechanism that the fips compliant libraries, or rather the software that uses them, provide to collect the passwords, and to link them with usernames and email addresses is that they reveal the hashes of email addresses, passwords, and usernames to passive listeners. And the agency collections hundreds of millions of such hashes.

If you have one hash, and you want to try ten billion things to see if one of them gives the correct hash, takes a while. If you have a million hashes, and you want to try ten billion things to see which ones match one of your hashes, takes about the same amount of time. So this form of leakage is primarily useful to those that collect the leaks on an industrial scale. The backdoors are provided to be convenient to those that seek to sweep up all data, not convenient to those who want to eavesdrop a particular conversation.

Let us suppose you want to have free wifi wherever you go.

It used to be that whenever someone signed on with his wifi network, the unsalted hash of his password was transmitted in the clear. So every time someone goes in and out of range of his wifi network, his cell phone transmits the unsalted hash. (Actually it is more complicated than that, I oversimplify, but the end effect is that a passive listener gets the hash of the password.)

This was inconvenient for the agencies, since people do not sign into their wifi all that often, so the Wifi protocol was modified on some slender excuse to continually retransmit the hash all the time, regardless of whether anyone needs it, wants it, or can use it.

So, you have a background process on your laptop collecting these hashes, and once a week or so, you let a process run overnight that tries a hundred billion passwords against a every network you have been in range of. Most of the passwords will be revealed. And now your laptop can sign into a free wifi network wherever you are. Handy.

Which gets interesting if it is the network of a big corporation, because you are now inside their firewall, rinse and repeat similar tricks to get their administrative passwords. Then hold their data for ransom.

If you comment on a WordPress blog, the standard worpress avatar plugins give you an avatar. And somehow, for some entirely inexplicable reason, the blog sends the avatar image, the username, and a hash of the user email address to a central repository. Supposedly the WordPress plugin avatar privacy does not do this, but I was recently informed that it does the equivalent in a more roundabout way, which I have now fixed.

This post was inspired by Let’s talk about PAKE, a post on how to do login by password correctly – so that the server does not know, and cannot learn, the password. Using the opaque zero knowledge protocol, the server never knows the password or the hash of the password, and the client never knows the per user salt, or per user key stored on the server, no hashes of interesting information are exchanged. If the server is evil, or the bad guys seize the server, everything is still encrypted and they have to run, not a hundred million trial passwords against all users, but a hundred million passwords against each user. And user can make the process of trying a password far more costly and slow than just generating a hash. Opaque zero knowledge is designed to be as unfriendly as possible to big organizations harvesting data on an industrial scale. The essential design principle of this password protocol is that breaking a hundred million passwords by password guessing should be a hundred million times as costly as breaking one password by password guessing. So this post is not about the opaque password protocol. It is about why it is needed.