How to apply recursive snarks for a fully scalable, fully private, currency

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.