Succinct blockchains

Quoting from https://codaprotocol.com/static/coda-whitepaper-05-10-2018-0.pdf :

“A succinct blockchain is a blockchain with verification complexity essentially independent of chain length. Instead of preserving the entire chain, one merely holds onto the current state along with a SNARK proving that there exists a blockchain explaining the current state. In fact, it is even better: the SNARK certifies the existence of a blockchain explaining a state with Merkle root h. Then, users who are interested in only part of the state (e.g., their own balance) can be given this SNARK along with a small Merkle-path corresponding to root h into the part of the state that they are interested in.”

To what extent can ZCash be made succint?

4 Likes

A significant obstacle (probably not the only one) to making a Zcash-like block chain succinct, is Bitcoin scripting. It would be exceptionally difficult, and very inefficient, to verify Bitcoin-style scripts in a SNARK/NIZK circuit.

Pay-to-verification-key (P2VK) is a possible privacy-preserving alternative to scripting where an address specifies a verification key for a zk-SNARK circuit to be satisfied in order to spend from that address. It doesn’t have the above problem because the SNARK verification is a well-defined operation of a fixed size in the succinct-verification circuit.

So, the first thing I’d like to do to unblock the possibility of making the Zcash block chain succinct would be to remove transparent addresses. There are a few things that block that in turn; besides performance which is largely addressed by Sapling, you need to replace functionality that is currently only supported for transparent addresses such as multisig and scripting, and change parts of the consensus protocol that depend on them such as coinbase transactions and fees.

13 Likes

It seems to me that advantages of a succinct blockchain somewhat exaggerated.
All full nodes in such a system would still need to maintain the full UTXO set.
The biggest advantage is that light clients can avoid a lengthy IBD.

Nope!

A succinct block chain does not in fact need to maintain a UTXO set. Coda for example is not UTXO-based at all; it uses versioned accounts. There is a Merkle-tree accumulator over account states. If you own an account then you need to store and update its witness in that accumulator; this is essentially the same as updating note witnesses in Zerocash/Sprout/Sapling. You don’t need or have access to other people’s account witnesses. If the bound on the number of account updates is N, then the size of state you need to maintain per account is logarithmic in N, so effectively constant [*]. The information needed to update your account witnesses can be included in each block, and is also of size logarithmic in N (it’s just the frontier of the Merkle tree). No-one needs any account witnesses in order to verify the block chain.

TLDR; it’s magic, and thoroughly solves the scalability problem, both asymptotically and practically.

The only significant caveat is the zk-SNARK trusted setup issue (since you need fully succinct zk-SNARKs for recursive composition), but look for further improvements to the trust requirements there, soon.

[*] If I’m being picky, logarithmic in the number of supported state updates is not constant, and so the claim in the introduction of the Coda whitepaper should be revised. But N = 264, for instance, supports a practically unlimited number of updates.

5 Likes

Incidentally, a “partially succinct” block chain would not need to deprecate transparent addresses. It would be succinct wrt shielded transactions, so that blocks would only need to contain transparent transactions. That would be sufficient to solve the scalability problem — for example, if you freeze the transparent UTXO set and require further transfers from t-addresses to be shielding, then you have a bound on the total future size of the transparent part of the chain state. Even if you don’t freeze the UTXO set immediately, you’ve essentially reduced the scalability problem to discouraging use of transparent transactions in favour of shielded ones, which is a problem you had anyway.

In the case of Zcash, we’d also want to allow non-succinct shielded Sprout and Sapling transactions, but this doesn’t present any further obstacle. It would be also possible to allow shielded Sapling->succinct transfers, subject to concerns about monetary base auditing. One way to do this (potentially disruptive, but elegant) is to automatically convert all Sapling note commitments to initial account states.

(Note that discussing these ideas in the public domain essentially prevents them from being patented. ZcashCo hasn’t applied for any patents, and I’m not aware of O(1) Labs, the developers of Coda, having done so.)

5 Likes

I see. Indeed I got confused by their claim of constant space (rather than logarithmic space) clients, and concluded that those clients relied on full nodes to provide them with Merkle proofs of their balance.

I wonder what that means for wallet recovery. If you lose your wallet, could you still recover your funds from a master word list?

1 Like

Will it still be possible to implement an atomic swap scheme between Bitcoin & Zcash, if Zcash go succinct\ scriptless\ get rid of UTXO set? Currently, the only option is to use t-addresses, but there are rumors, as soon as Bitcoin implement Schnorr, swaps with Z-address become feasible?

I see that coda (now mina) is not the only succinct blockchain on the block: https://mirprotocol.org/
I wonder if there’s any more in the woodwork…

1 Like