Shielded transaction aggregates

[daira]

Is your feature request related to a problem? Please describe.

If Zcash achieves significantly higher usage, then the overall verification and transaction bandwidth cost will become a problem. In other cryptocurrencies this has led to high and less predictable fees, increases in latency of transactions being mined, and obstacles to adoption — both immediate and due to concerns about future scalability.

Even without a scalability "crunch" that would require an immediate solution, existing bandwidth usage and latency present problems for clients on mobile devices, especially in parts of the world where Internet data is expensive.

Describe the solution you'd like

A "shielded transaction aggregate" is a compact representation of a set of non-conflicting, fully shielded Orchard transactions. (For uses of Orchard here and below, read the most recent shielded protocol, which is assumed to be Orchard-like.) Aggregates and individual transactions can be combined off-chain, and then included on-chain with much lower bandwidth usage and verification cost.

This approach is essentially a "rollup" in the terminology Vitalik uses here, but note that most other rollup protocols do not support transaction graph privacy, and most do not use recursive proofs. The significance of recursive proofs here is that they potentially allow aggregates to be created in a distributed, decentralised way and then combined.

To measure storage and bandwidth costs, we make a distinction between fields of an aggregate that are necessary to check long-term consensus, and fields that transaction senders and recipients need temporarily or when recovering from data loss (i.e. when they only have their long-term seed). We call the former "non-trimmable" and the latter "trimmable". Deleting the latter from node state would be called "trimming".

Bitcoin has a superficially similar distinction between "non-prunable" and "prunable" information. However, pruning in Bitcoin deletes information that would be necessary to verify historical chain validity, including verifying balances. Trimming in this proposal, however, only affects the ability to directly check that the trimmable data was available at the time (and you still get indirect assurance of that from the PoW consensus). So, objections to pruning on the basis of being unable to verify historical chain validity would not apply to trimming.

An aggregate consists of:

• non-trimmable: a single Halo 2 proof which recursively validates a tree of transactions;
• non-trimmable: a single Merkle root to a subtree of note commitments, to be added to the global note commitment tree;
• non-trimmable: a list of nullifiers, to be added to the global nullifier set;
• trimmable: a list of note commitments, forming the subtree with the Merkle root above;
• trimmable: a list of note ciphertexts (encoded in such a way that it is possible to tell which note commitment each corresponds to);
  • optionally, note ciphertexts can be split from memo ciphertexts.

The proposal is parameterized by a value N which is simultaneously, for any aggregate:

• the maximum size of the note commitment subtree;
• the maximum number of nullifiers;
• the maximum number of note ciphertexts.

For simplicity and reduction of attack surface, only fully shielded transactions spending Orchard notes to Orchard addresses are supported. No new shielded pool or address type is introduced, and no transparent or TZE functionality is supported for aggregated transactions. This does not introduce any immediate compatibility problem because single transactions can be mixed with aggregates in a block (see "Inclusion in blocks" below).

Scalability

This doesn't by itself change the asymptotic bandwidth or verification costs of the protocol:

• the bandwidth of transaction broadcast is asymptotically the same because a tx aggregate still contains all the nullifiers of spent notes, the note commitments, and some of the note ciphertexts;
• scanning of the remaining note ciphertexts is still necessary;
• it is still necessary to check that nullifiers are unique.

However, it can significantly reduce the concrete bandwidth use.

This proposal also greatly reduces verification cost: the cryptographic cost of checking an aggregate is O(1) regardless of the number of transactions it contains. The cost of checking nullifier uniqueness is very cheap in practice (and could potentially be reduced asymptotically by using a non-membership accumulator).

On-chain bandwidth [updated]

The size of a nullifier is 32 bytes, a note commitment is also 32 bytes, and the total size of a note+outgoing ciphertext including epk and memo is 692 bytes (for both Sapling and Orchard). If the memo is split into a different ciphertext, then the non-memo+outgoing part would be ~180 bytes.

The size of a fully shielded Orchard transaction with two "actions" (up to two spends and two outputs) is 9160 bytes. The corresponding Sapling transaction would be 2756 bytes.

Define the total footprint of a transaction to be the size of its fields that are included on chain. Define non-trimmable footprint and trimmable footprint to be the sizes of the corresponding non-trimmable and trimmable fields. A Sapling or Orchard transaction included in an aggregate would have a non-trimmable footprint, for the two nullifiers, of 32*2 = 64 bytes. It would have a trimmable footprint of 32*2 + 692*2 = 1448 bytes, if both outputs are sent in-band, or 32*2 = 64 bytes if both are sent out-of-band. It would have a total footprint of between 128 and 1512 bytes.

So, the potential reduction of total transaction bandwidth relative to Sapling is in the range roughly ~45.1% (all outputs in-band) to ~95.3% (all outputs out-of-band). Relative to Orchard, it is in the range roughly ~83.5% (all outputs in-band) to ~98.6% (all outputs out-of-band). The "all outputs in-band" savings would be improved if we implement the fewer-memos-than-outputs optimization, at the cost of additional information leakage of the number of memos.

The potential reduction in chain size after trimming is 97.7% relative to Sapling, and ~99.3% relative to Orchard.

Light client bandwidth (sending)

The bandwidth needed by a light client to send an aggregated transaction depends on whether it is sending notes out-of-band or in-band.

If the client is creating a note to send out-of-band and trusts the aggregator not to burn its funds, it can choose to rely on getting a receipt from the aggregator that includes a Merkle path to its note commitment within the aggregate. It checks that this path is correct, and then sends it, along with the note, privately to the recipient. The recipient then only needs to verify that the aggregate exists in the chain — for which it only needs the non-trimmable data. (It would be a privacy hazard for the recipient to fetch commitments for a block only when they have received an out-of-band note in that block, which is why the sender should do it.)

The aggregator might try to burn the funds by putting the aggregate on-chain but refusing to send the receipt. (This could also happen accidentally due to a communication failure, if the aggregator does not wait for confirmation from the client that it got the receipt.) In that case, the light client can recover the funds by computing the Merkle path to the note from the on-chain commitment list.

If the client is creating a note to send in-band, it doesn't need any additional bandwidth beyond sending the transaction and confirming that it exists on-chain.

Light client bandwidth (receiving)

The client has to scan the chain for note ciphertexts, commitments, and nullifiers as it does now, so in the worst case the bandwidth would be the same. However, if many notes are sent out-of-band then the bandwidth needed for scanning will be reduced accordingly.

Verification cost

The main bottleneck to increasing transaction capacity is arguably full-node verification cost rather than on-chain bandwidth. An aggregate of up to N transactions can be verified faster than a single Orchard transaction (because verifying the recursive proof is also verifying signatures, which have to be verified separately for single Orchard transactions).

This proposal is also a pragmatic step toward a succinct block chain, if the latter turns out to be needed. Transaction aggregation would be a necessary part of a succinct block chain design in any case. It is complementary to sharding or other potential scaling approaches. It's also complementary to using a more succinct nullifier non-membership accumulator.

Fees

Recall that the footprint of a transaction is the size of its fields that are included on chain. A fee is paid by each transaction creator to the eventual miner, at fixed rates per trimmable footprint byte and per non-trimmable footprint byte. That is, an aggregate pays a miner fee that is the sum of the miner fees from the aggregated transactions.

It would be possible to allow the aggregators to also take some fraction of the fees. However this is tricky to define because there can be multiple levels of aggregation by different parties, and so I'm omitting it from this initial proposal.

Note that aggregators may have external incentives to perform their task even without fees. For example, I expect it would be common for exchanges to aggregate their users' transactions. In that case the exchange already typically takes a fee, and does not need another one to cover the aggregation cost, which is part of the service they are providing to their users.

If we decide that full decentralization of aggregate creation is a requirement, then we should look at other proving pool designs such as Mina's "SNARKetplace".

Receipts

The creator of a transaction that is sent via an aggregator can tell that a spend (and therefore the transaction that included it) has been included in the block chain, by scanning all nullifiers and commitments. It can do this independently of receiving confirmation from the aggregator.

In the Light client bandwidth (sending) section above, we mentioned the possibility of an aggregator giving the sender a receipt to show that it has accepted the transaction, and promises to submit it to the block chain in some aggregate. The transaction creator SHOULD set an expiry height so that it knows when to resubmit the tx (either to another aggregator, or directly as a single tx) in case it has not been included.

Output discovery

Including a note ciphertext for an output is optional. The proof ensures that all note ciphertexts that were intended to be included by tx creators are actually included (using a Merkle tree over the ciphertexts). The recipient can compute the Merkle witness for the received note because it has all of the commitments in the aggregate.

In the case of an out-of-band ciphertext, the aggregator can compute the Merkle path and give it to the sender (as part of the receipt mentioned above), who passes it on to the recipient.

This is intended to allow a gradual switch from broadcast note ciphertexts on the block chain, to point-to-point communication of notes over privacy-protecting or local networks.

Inclusion in blocks

An aggregate would be represented in a block as a different transaction version. Single transactions and aggregates compete for block space. There might be a case for reserving some portion of the block space that is guaranteed to be available for aggregates.

Alternatives you've considered

My presentations at Zcon1 and at the Amsterdam zkproof event describe the most comprehensive straw design for scaling in Zcash that had previously been proposed. This design addresses a lot of issues that are arguably not necessary to solve in an initial deployment of scalability improvement. It included transaction aggregation as one of the ideas, but this ticket lays out that part in more detail, and with some simplifications.

[Revised on 2021-01-17; see comment below.]

[Revised on 2022-08-18; the estimated size of a 2-in 2-out Orchard transaction was too small, because the Halo 2 proofs for the Orchard circuit turned out to be larger than anticipated. Also, I had included the saving from having only one memo per recipient rather than per output, but that is a separate optimization that shouldn't be attributed to the aggregation.]

[nathan-at-least]

This sounds like an excellent building block for further capacity improvements. Nice work! :-)

Miner Aggregation Question

Question: Is it possible for a miner to perform aggregation over their entire mempool? This would allow the current p2p broadcast mechanism to function identically yet all nodes would benefit from this "full mempool scope" aggregation. Miners may even have an innate incentive to do so when the mempool is larger than block size, because they'd be able to gather more txn fees per block.

IIUC, if we also assume blocks contain only the coinbase and these aggregates, then this should notably improve validation time per block. Correct?

Use Case Impact Brainstorm

In the case that this feature notably improves per-block validation time for full nodes, this could be a notable improvement for:

• Miners, where block validation delays present a substantial opportunity cost to PoW effort. Miners either must validate an incoming block fully, or begin performing PoW work on a block that is not yet fully validated, so lowering the validation time makes miners more resilient against the cost of invalid blocks.
• Low compute / high bandwidth scenarios such as for special purpose full node devices, point-of-sale kiosks, "full node in a box" products (ex: Casa, Nodl, …).
• Any "embedded consensus" clients, such as:
  • Ethereum smart contracts that replicate Zcash validation (ex: Keep tBTC does this for BTC).
  • Potentially embedded / nested ZKP proofs about Zcash blocks.
• Potentially "SPV-style" light wallets which are doing block validation.

Further Improvements

There are some potential further improvements which could build off of this feature:

• cross-block aggregation: There seems to be a spectrum between Zcash NU4 era design and fully succinct block chains. (This also seems to be the easiest next step in this list to me, with notable benefits to bootstrap/sync time and light wallet security.)
• nullifier / commitment aggregation, combined with a different approach to payment detection: if done well this would enable substantial capacity improvements that might look like ZKP roll-ups (which maintain strong privacy).
• sharding: I am increasingly curious about the relationship between sharding and ZKP roll-ups.

[daira]

Is it possible for a miner to perform aggregation over their entire mempool?

Yes (for supported, i.e. fully shielded Orchard, transactions and aggregates). It might be concretely quite expensive though. Typically miners want to include new transactions (or aggregates) in the template they're mining as soon as they have been validated, which is why I didn't assume that miners would do the aggregation.

IIUC, if we also assume blocks contain only the coinbase and these aggregates, then this should notably improve validation time per block. Correct?

Yes.

[daira]

The original proposal had a bug — the recipient of a note found by scanning outputs would not have had sufficient information to construct its witness. The fix is to include commitments, which slightly reduces the bandwidth savings. This also helps in the case of an aggregator that includes a transaction but does not send a receipt, when the tx is to be sent out-of-band, because the sender can compute the note witness from the chain.

I have also added the distinction between non-trimmable and trimmable fields. Note that it is the total footprint (along with validation cost) that affects throughput, but trimming does help for node storage costs and catch-up bandwidth.

[daira]

If we wanted to retrofit the trimmable/non-trimmable distinction onto the existing shielded protocols, the fields that are trimmable in Sprout, Sapling, and Orchard, are the note ciphertexts and outgoing ciphertexts.

[daira]

@nathan-at-least wrote:

sharding: I am increasingly curious about the relationship between sharding and ZKP roll-ups.

I think that the approach I outlined in my Zcon1 and Amsterdam talks, in which the nullifier set is sharded but there is a single address space and anonymity set, is the best way to do sharding for Zcash. But I'm also increasingly of the opinion that sharding is complex and more disruptive to the protocol than other scaling techniques, and so we should not do it unless and until it becomes clear that other techniques are not sufficient.

[kranzj]

This sounds massively cool :)