What is a wallet?

Cryptocurrency users ^{[citation needed]} have "spending keys" that authorize their funds to be spent, from which addresses can be derived for receiving funds. A wallet manages these spending keys, as well as tracking all the information needed to enable spending the funds controlled by those keys.

More specifically, what a wallet needs to do (in order to be useful) is:

1. Manage the user's spending keys, address generation, etc.
2. Maintain a correct balance of funds.
3. Enable funds to be spent.

The status quo

There are four operations that a Zcash wallet needs to perform in order to maintain a correct balance:

• Trial-decrypting all on-chain notes to detect new funds.
• Creating new witnesses for newly-detected notes.
• Updating existing witnesses for our notes, so we can spend them.
• Looking for nullifiers to detect spends of our notes.

These are generally implemented (for example in zcashd and the mobile SDKs) in a simple and very linear way: as each block is fetched (from other zcashd peers, or as a compact block from lightwalletd), all these operations happen together and in sequence.

It's been a long-term goal to split these operations up, for example by trial-decrypting in parallel, or updating existing witnesses separately from the rest in order to spend existing funds more quickly. Since mid-2021 we have started to see wallets implement these performance improvements (e.g. the BlazeSync algorithm, and zcashd 5.2.0 implementing batched and parallelised trial decryption).

Another area that affects performance is note management. The number of parallel transactions that can be in-flight (waiting to be mined) is limited by the number of spendable notes, as notes can't be spent until they are mined. If the user makes one large deposit to a wallet and then makes transactions within that balance, they will only ever have one spendable note at a time. Wallets can improve this by splitting up large notes into smaller ones, either actively or as part of existing user transactions (by creating multiple change outputs). Similarly, wallets can merge smaller notes together optimistically to reduce future transaction sizes. No wallet implements these techniques yet, but this is a previously-known optimisation that can be deployed when necessary.

Wallet UX speedrunning

To go beyond the status quo, we need to more closely examine how wallets are used in practice:

• Imagine that I'm in line at a coffee shop, I see they accept ZEC, and I pull out my wallet that I haven't used in a month. I don't actually care about being able to spend my entire balance. What matters to me, in that moment, is that I can spend enough funds to pay for a coffee.
• Imagine my phone dies, so I buy a new one, install a new wallet app, and start recovering from my backed-up seed phrase. While I would like for my past transaction history to be recovered (which could be years of data), my primary goal is to regain access to my funds so that I can continue to use them.

We can leverage these UX observations for a speed hack: if the wallet can ensure that some funds are guaranteed to be spendable, the user can potentially get on with whatever transaction they want to make, without having to wait for the wallet to be fully synced.

Let's refine our earlier definition of a wallet:

1. Manage the user's spending keys, address generation, etc.
2. Maintain a correct lower bound on the balance of funds.
3. Enable funds up to the lower bound to be spent.
4. Eventually determine the correct balance of funds.

Learning an exact lower bound on a wallet's balance obviously can't be slower than learning the correct balance, for any scanning protocol. The question is, how can we make it faster, beyond running more operations in parallel?

What we need is some extra information to guide our wallet, so that it prioritises work that enables notes to be made spendable quickly. And we alone have that information: our personal transaction graph.

An aside, the usefulness of which will become apparent shortly

A Directed Acyclic Graph (DAG) is a datastructure with three key features:

• Graph-ness: it is a set of nodes (also known as vertices) connected by edges.
• Directed-ness: each edge has an arrow indicating a "direction of travel" through the graph.
• Acyclic-ness: starting at any node, and moving between nodes along edges in their direction of travel, it is impossible to end up where you started.

Each node in a DAG has an "in-degree" (the number of edges arriving at it) and an "out-degree" (the number of edges leaving it). In the example DAG above, node d has an in-degree of 3, and an out-degree of 1.

We can constrain the structure of a graph by assigning labels (known as "colours") to the nodes, such that no two adjacent nodes have the same colour. The example graph above cannot be coloured with fewer than 5 colours, because node a is connected to every other node. Meanwhile, a Petersen graph has 10 nodes and 15 edges, but can be coloured with three colours:

The personal DAG

Imagine that you have an empty wallet, and you receive some funds in a transaction. Let's represent that transaction as a pair of nodes in a two-colour graph: a box for the transaction, and a circle for the note, with a directed edge showing that the note is created by the transaction:

┌──┐
│S0├─►O U0
└──┘

Since a note only exists between a pair of transactions (the one that creates it, and the one that consumes it), they will have an in-degree and out-degree of at most 1.

We could also just use the edges themselves as the notes, and represent unspent notes as "dangling edges", but whenever I suggested this to people who understood graphs, they would scream.

Next, you use those funds to pay for coffee. This consumes the note that you received in the previous transaction, and creates a new note containing your change (as well as the note for the coffee shop, but we'll ignore that one for now). We can represent this as:

┌──┐     ┌──┐
│S0├─►O─►│I0├─►O U1
└──┘     └──┘

Now let's assume your wallet also performs note management. In addition to paying for coffee, it split the change into three separate notes:

           ┌──►O U2
           │
┌──┐     ┌─┴┐
│S0├─►O─►│I0├─►O U1
└──┘     └─┬┘
           │
           └──►O U3

Following this with a few more spends, and more received funds, we end up with a more complex diagram:

           ┌──►O───┐ ┌──►O────────┐
           │       │ │            │
┌──┐     ┌─┴┐     ┌▼─┴┐           │    ┌──┐
│S0├─►O─►│I0├─►O─►│I1 ├─►O        └────►I4├────►O U9
└──┘     └─┬┘     └───┘  │             └▲─┘
           │            ┌▼─┐     ┌──┐   │
           └──►O───────►│I2├─►O─►│I3├──►O ┌──┐
                        └▲─┘     └─┬┘     │S2├─►O U10
                ┌──┐     │         │      └──┘
                │S1├─►O──┘         └───────────►O U11
                └──┘               

This is, by definition, the transaction graph. More precisely, it's the subset of the global transaction graph that involves your wallet.

We can break down the wallet's transaction graph into three kinds of nodes:

• Source nodes with in-degree 0. These are always transactions that introduce new funds to the wallet (labeled S# above).
• Sink nodes with out-degree 0. These are either our unspent notes (labeled U# above), or transactions that consume all their inputs and have no change outputs (such as when moving funds out of the shielded pool).
• Internal nodes (everything else). These are previously-spent notes (with out-degree 1), and historical transactions.

From this, we can draw several key insights:

• Our current balance is exactly the sum of all notes with out-degree 0. Therefore, finding those as quickly as possible is the fastest way to enable users to spend their existing funds.
• Given that the most expensive operation is trial decryption, the optimal path selection will be where paths are weighted by the number of outputs on each transaction.
  - Weighting by out-degree is insufficient; we need to trial-decrypt all transaction outputs in order to discover what its out-degree is (how many outputs are for us).
• In the simplest case, we do not need to store witnesses for any notes with out-degree 1. If we can identify them more quickly than updating their witnesses, we can save on computation.
  - In practice, we need witness data up to 100 blocks back (the maximum reorg distance in zcashd and zebrad). Note that the protocol doesn't require this, although it documents and allows it (see section 3.3 of the Zcash protocol spec).
• We only need to do "scan-everything" trial-decryption to discover source nodes in the graph. All other nodes exist downstream of these, and can be discovered with targeted decryption.

We now have everything we need to describe a wallet sync algorithm that exploits our personal transaction graph.

The DAGSync algorithm

The wallet starts with several sets:

• note-set: A set of potentially-unspent notes.
• tx-set: A set of transactions that need to be trial-decrypted.
• calc-set: A set of notes that we know are unspent but can't spend yet.
• spendable-set: The set of spendable notes. The sum of these notes' values is the wallet's lower bound on balance.

The wallet initialises note-set with the previously-unspent notes from the last time we synced the wallet. If we are recovering a seed phrase, all sets start empty.

The wallet then runs several tasks in parallel:

1. Nullifier Tracking: For each note in note-set, look for its nullifier in an on-chain transaction.
   - If we don't find the nullifier, the note is unspent! Add it to calc-set.
   - If we find the nullifier, and the wallet does not know about the transaction, add it to tx-set (and also to the wallet).
2. Targeted Decryption: For each transaction in tx-set, trial-decrypt all of its outputs. If any outputs can be decrypted, add the nullifiers for those notes to note-set.
3. Witness Calculation: For each note in calc-set, calculate its witness (either by updating an existing witness or calculating a new one), and then add the note to spendable-set.
4. Source Discovery: Starting from the latest block and going backwards, for each on-chain transaction that the wallet does not know about, trial-decrypt all of its outputs. If any outputs can be decrypted, add the nullifiers for those notes to note-set.
   - This task stops once we see a "marker" in a decrypted change output (if supported, see below), or it catches up to the history-discovery task.
5. History Discovery: Starting from the point we were previously synced to and going forwards, for each on-chain transaction that the wallet does not know about, trial-decrypt all of its outputs. If any outputs can be decrypted, add the nullifiers for those notes to note-set.
   - This task stops once it catches up to the source-discovery task.

Syncing completes once all sets except spendable-set are empty, and all tasks have completed. However, at any point the wallet can take notes from spendable-set and use them to create transactions!

Efficiency

This syncing process traverses the graph from the known state to the leading edge as quickly as possible, via sequences of nullifer-tracking and targeted-decryption tasks that traverse the shortest path of sequential spends.

This algorithm is efficient for several reasons:

• Nullifier tracking (a database lookup) is much cheaper than output decryption (variable-base scalar multiplication). This means that we are enabling the most effective parallel work, by discovering useful transactions to decrypt at multiple points in chain history simultaneously (as nullifier tracking for longer historic paths of spends can be occuring alongside shorter newer paths).
• We know that many earlier paths are likely to rejoin (or could be artificially encouraged to do so via the wallet's note selection algorithm), so with a small amount of synchronisation between the sets, most nullifiers can be eliminated as spent fairly quickly after the shortest path has been explored.
• The trial-decryption operations can be prioritised based on how the outputs were discovered, with targeted-decryption having the highest priority, and history-discovery having the lowest priority.

The upshot of this is that a wallet with random access to chain data, where accessing that data is much cheaper than trial-decryption, can very quickly establish a lower bound on its balance, and make it spendable, while having an eventually-consistent balance that is guaranteed to discover the same set of spendable notes as the existing linear scans.

You also get very fast recovery from seed in this model: as soon as you find the very first source, you can "surf" the DAG to find your most recently-unspent notes. This is much more efficient that backwards-linear scanning (as the notes might have been created tens of thousands of blocks earlier than the current chain tip) and way more efficient than forwards-linear scanning (as the wallet might be hundreds of thousands of blocks old). Wallets generally already make finding this first source easier by asking users to back up the "wallet birthday" alongside the seed phrase.

Note the restriction "random access to chain data". Unlike a linear scan, this sync process requires multiple passes over the chain, in non-sequential order. However, for a wallet that already performs a linear scan, this shouldn't be much of a constraint: they can fetch blocks linearly as they currently do, but cache them instead of scanning and dropping. The wallet has a "window of access" its scanning requires, stretching from the oldest output-decryption task to the most recent nullifier-tracking task. The wallet could potentially tune this cache by tracking the progress of the output-decryption tasks triggered by the new blocks queue, and only fetching more blocks as older ones are complete. Some tasks (primarily nullifier-tracking) would need to block until the blocks they require are available; there would therefore be a trade-off between task queue sizes and the block cache size.

Even more efficiency: wallet markers and knitting

Once we have a wallet that is cognizant of its own transaction graph, we can start actively influencing the shape of that DAG to get even more speed!

While performing note management, a wallet that is DAG-aware can additionally explicitly select newly-received non-change notes to be part of a transaction. This has an interesting effect on the structure of the DAG. Consider two transaction graphs, where the source S1 is either left unselected (because it was unnecessary for the values of other transactions), or actively selected for I2:

           ┌──►O───┐ ┌──►O────────┐
           │       │ │            │
┌──┐     ┌─┴┐     ┌▼─┴┐           │    ┌──┐
│S0├─►O─►│I0├─►O─►│I1 ├─►O        └────►I4├────►O U9
└──┘     └─┬┘     └───┘  │             └▲─┘
           │            ┌▼─┐     ┌──┐   │
           └──►O───────►│I2├─►O─►│I3├──►O ┌──┐
                        └──┘     └──┘     │S2├─►O U10
                ┌──┐                      └──┘
                │S1├───────────────────────────►O U11
                └──┘               

           ┌──►O───┐ ┌──►O────────┐
           │       │ │            │
┌──┐     ┌─┴┐     ┌▼─┴┐           │    ┌──┐
│S0├─►O─►│I0├─►O─►│I1 ├─►O        └────►I4├────►O U9
└──┘     └─┬┘     └───┘  │             └▲─┘
           │            ┌▼─┐     ┌──┐   │
           └──►O───────►│I2├─►O─►│I3├──►O ┌──┐
                        └▲─┘     └─┬┘     │S2├─►O U10
                ┌──┐     │         │      └──┘
                │S1├─►O──┘         └───────────►O U11
                └──┘               

Imagine that we are currently synced up to transaction I0 (and know its outputs):

• In the first case, the only way we can discover U11 is with source-discovery or history-discovery scanning (whichever happens to reach S1 first). This could potentially require trial-decrypting tens of thousands of blocks.
• In the second case, we can reach U11 directly from the outputs of I0 (as there is a path through the DAG from those outputs to U11). We never actually need to discover S1 except for historical purposes, so we want it to be discovered by the history-discovery task (which has the lowest priority).

The key insight here is that given a set of unspent notes at some point in time, there is a high probability that they are connected to almost your entire DAG at a later point in time. A wallet can therefore improve sync performance by actively "knitting in" new sources as they are discovered, by preferentially selecting them as transaction inputs.

Once a wallet is doing this, it can store "markers" in the memo fields of change outputs, to tell its future self that all funds relevant to the wallet have been discovered and knitted in as of this transaction. These markers provide stopping points for the Source Discovery task above: any further scanning prior to the latest marker is only going to improve the history displayed in the wallet (by finding the source transactions), but not change the wallet's balance.

Depending on how much space is available in the change output memo fields, wallets could even store back-references to the source transactions alongside the marker information. This would remove the need for the History Discovery task entirely: the regular DAGSync process finds all the marker transactions, and these would in turn point to the source transactions. Technically that is introducing cycles into what is otherwise an acyclic graph, but we're going for efficiency here, and only people with the wallet's viewing key will see them. We can have a few cycles, as a treat 😁

Stay tuned!

The ECC core team is working on implementing DAGSync in the Zcash Rust crates. Once that is complete, anyone using the Android and iOS mobile SDKs will benefit from this.