Succinct blockchains

Technology
1

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
2

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
3

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.

4

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
5

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
6

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
7

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?

8

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
9

I want to share some of my thoughts about scalable blockchain based (at least payment) system, not sure if it the right place.

Nothing is correlated to Zcash official roadmap and technically deep. All the imaginary possible future. Just my personal opinions.

First step

Make blockchain succinct and smash distinction between light and full nodes. Blockchain weight won’t be a bottleneck anymore but network and block producers is.

Transaction confirmation time: few seconds.

Get rid of historical transactional data

With history proofs like in Mina, or organizationally (history expiration, snapshots).

Up to few times of scalability improvements

Get rid of the state

Make block production stateless. State should be maintained by wallets or off-chain otherwise. Minimum required data as a state roots, proofs need to be stored in a block header.

Wallets could create correct transaction with their data (previous outputs, data entries). Validators or block builders could validate transactions over the latest block header with state roots and create a new one.

OK, the blockchain is succinct now.

Second step

In the first step validators collect all the known transactions in the network and create a new blocks sequentially. Further scalability improvements will be require some sort of concurrent processing.

This part will require significant network improvements. Currently blockchain nodes not very network intensive, they get transactions from the network, usually dumb gossip network and verifies over the local database, then gossip the new correct block. But scalable P2P payment system will depend on synchronous communication more.

Transaction confirmations could be nearly instant.

I assume two possible options here but not limited.

Option 1: Transactions aggregation

A new role, an aggregator, will listen network for transactions and send aggregated summary to validators. Aggregated transactions is enough to create new block (header) if two of them don’t have conflicting transaction. With conflicts the network performance can degrade. So, aggregators should separate their duties, and exchange some short commitments about what they have. Bad behavior can be limited with fraud proofs and penalties. In the better case aggregated transactions with conflicting tx won’t prevent the block building as conflict can be separated from resulted block or state root.

Option 2: LN-like network with validity proofs

The current bitcoin Lightning Network has limitations: It uses fraud proofs and don’t send info about channel transactions to the blockchain. Better more trustless version should be possible if after every channel transaction emit an aggregatable proof about the channel state to the network. If a current LN channel is like a plasma, to in a future version it can be more like a validium. Safe fast uncooperative channel closing, updating, splicing would be possible as well as multiparty m-of-n channels. Better UX with great scalability.

Additions

Two-step transactions (building)

Some blockchain designs require interactive transactions building (MimbleWimble, Lightning Network). It often seems as a drawback for UX but it can be seen as an advantage.

A single-step tx:
Currently (in bitcoin) if Alice wants to send coins to Bob she moves coins to an address controlled by Bob’s private key (create new output controlled by Bob’s privkey). Maybe Bob will never know about the transaction, but Alice won’t get coins back. What if Alice send coins to a wrong address.

A two-step tx example:
Alice send coins to a new output which is a smart-contract where:

  1. Bob can redeem coins by his private key for a limited time.
  2. Alice can get a refund after that time (can be considered as auto-refund as Bob can get it anymore).

But what the advantages of this?

All the transfers consciously accepted by both parties. No more spams, airdrops, dusting attacks. Sending to wrong address and wrong networks is not a problem anymore as can be refunded. More clear payment acception (for example, now consumer can see that a payment is confirmed not only by the blockchain network but also by a merchant).

It even more important for a full stateless chain. Bob now need to know that tx exists, and get data (outputs) required to create new transactions with this coins. This can be done directly between wallets in a synchronous P2P messaging network.

Generalization of UTXO

I don’t know how good UX of stateless general-purposed blockchain with smart-contract can be in comparison with current stateful (or weak stateless) chains. But at least it should be very suitable to settle validiums.

My intuition tells me that UTXO and account models should be interchangeable. It is possible to make account abstraction on top of UTXO chain, and implement UTXO transactions as a contract on an account chain, to create an UTXO L2 on top of an account L1 and vice versa.

Generalized UTXO now looks like UTXO with turing-complete spending scripts. It can be multi-asset chain with spending scripts or private chain with confidential assets and turing-complete spending scripts. Anyway, it has some token transfer event as a core of an output.

But UTXO can be implemented over arbitrary data records without any transfer primitive with covenants discussed in the bitcoin community. And tokens can be implemented as custom covenants.

Account and address abstraction

I think addresses should not be a part of a blockchain protocol and implemented in wallets, maybe for communication purpose only. With interactive transactions they are not needed anyway. If Alice and Bob transacting over Signal they don’t need addresses. For sending between addresses is better to do with communication addresses of overlay messaging network similar to onion-addresses in tor/ And not with addresses derived from privkeys which control funds.

Blockchain protocol is better to keep minimalistic, simple, clean, succinct and universal as a basic low-level protocol.

1 Like
10

This seems contingent on switching to an account model. But then, transactions wouldn’t be as private as they are today.

1 Like