Penumbra Payment Links

[hdevalence]

Payment links, originally proposed for Zcash, are a mechanism that allow sending shielded funds over any secure channel, without requiring the payee to have already installed wallet software.

This mechanism could be useful for a shielded payment app built on top of Penumbra, which already has all of the required protocol features for private payments as a side effect of protocol features for private DeFi.

At a high level, payment links work as follows. The payer creates an ephemeral spending key, moves funds into the control of that key, and sends the key to the payee over a private channel. The payee (or the payer, or anyone who observes the payment) can sweep the funds to a key they control.

Because payment links don’t require the payee to already have wallet software installed (the payee can generate a wallet after onboarding with the payment link), they’re extremely useful for onboarding, as demonstrated by Payy Network. As noted in the Zcash proposal, and productized by Payy, they can also potentially improve scalability, as they can potentially allow recipients to avoid scanning the chain. (This has other system design tradeoffs, however; Penumbra instead chooses to make scanning fast).

This post describes a construction of payment links for Penumbra based around bearer notes, and describes differences from the Zcash proposal.

Shielded Notes

Recall that in Penumbra, value is recorded in notes, consisting of the following data:

• a typed value, consisting of a (u128) amount and an asset ID;
• a control address;
• a random seed rseed.

Notes have two different cryptographic identifiers: a note commitment, which can be computed from the note contents alone, and a nullifier, which can only be computed with knowledge of the viewing key corresponding to the control address.

Notes are never published on-chain. Instead, when new notes are created, the creator reveals only the note commitment onchain, and encrypts the note to the recipient. The note commitment is then included in the State Commitment Tree (SCT). The recipient learns about the note and tracks its position in a local copy of the SCT. To spend a note, the recipient proves that the note was previously included in the SCT (via a ZK proof of Merkle tree inclusion), proves that they have control over the note (via a randomized signature), and proves that the note has not already been spent (by revealing the note’s nullifier).

Bearer Notes

The core of the payment link construction is the concept of a bearer note: a note that can be spent by anyone who observes it.

To create a bearer note, a value is given and the random seed rseed is chosen randomly as normal. However, the control address is chosen to be the default address for the spending key derived from using rseed as the input to the standard BIP39 key derivation process.

This construction is different from the one originally proposed for Zcash, which started from a randomly selected spending key and used it to derive rseed. The key advantage of deriving the address from rseed rather than the other way around is that it provides an easily checkable criteria to statelessly determine whether any given note is a bearer note: does the address in the note match the one that would be expected if it were a bearer note?

This property simplifies client implementations, by allowing them to determine whether a given note was/is a bearer note without tracking any extra information about its provenance.

Auth Paths

As described above, spending a note requires:

1. Proving that the note’s commitment was previously included in the SCT;
2. Proving control over the note via a randomized signature;
3. Proving that the note was not previously spent, by revealing the note’s nullifier.

Bearer notes make (2) and (3) trivial given knowledge of the note. However, (1) remains a challenge.

The claimer of the bearer note must witness an auth path from that note’s commitment up to some historical root of the SCT. This historical root is called the anchor, as it anchors the (stateless) ZK proofs to the chain state.

However, this poses a challenge. Normally, each Penumbra client’s embedded ultralight node syncs a local, filtered instance of the SCT that forgets all leaves and nodes except the ones necessary to track that wallet’s notes. The claimer of a bearer note will not already have the auth path for a particular note commitment, since the point of this construction is that they aren’t required to have already been running a Penumbra client.

In the Zcash design, the client was supposed to query a server to learn the auth path. But querying the server for an auth path is suboptimal because it means that the claimer reveals precisely which note they are trying to claim. Since note commitments are revealed when they are created, this allows the server to link the sender and the receiver of the payment, defeating the privacy. (I’m not sure what Payy does here, but as an L2 with a centralized sequencer, this choice would be particularly problematic, as the sequencer would have privileged visibility into the complete transaction graph).

This could be avoided if the payer includes the auth path in the data they send to the payee. Penumbra’s SCT is a 3-tiered stack of depth-8 quadtrees, so there are 3 sibling field elements at each position along the auth path, for 3 * 8 * 3 * 32 = 2304 bytes total. This is sizeable, but probably workable to include in a payment URL (which should not exceed 8KB).

Payment Link Lifecycle

The bearer note contained in a payment link is created by the payer and claimed by the payee. The payer can also (re)claim the bearer note at any point until the payee claims it, but this is not discussed separately since it’s just the payer acting as if they were the payee.

Payer Computation

As mentioned above, Penumbra clients’ SCT instances automatically forget all nodes other than the ones that track notes they control. This process happens automatically, and ideally the payer would be able to obtain auth paths for bearer notes they create without alterations to the core client logic. However, the tiered structure of the SCT does provide a way to do this:

Eternity┃           ╱╲ ◀───────────── Anchor
    Tree┃          ╱││╲               = Global Tree Root
        ┃         * ** *           ╮
        ┃      *   *  *   *        │ 8 levels
        ┃   *     *    *     *     ╯
        ┃  ╱╲    ╱╲    ╱╲    ╱╲
        ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Global Tree Leaf
                        ▲             = Epoch Root
                     ┌──┘
                     │
                     │
   Epoch┃           ╱╲ ◀───────────── Epoch Root
    Tree┃          ╱││╲
        ┃         * ** *           ╮
        ┃      *   *  *   *        │ 8 levels
        ┃   *     *    *     *     ╯
        ┃  ╱╲    ╱╲    ╱╲    ╱╲
        ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Epoch Leaf
                 ▲                    = Block Root
                 └───┐
                     │
                     │
   Block┃           ╱╲ ◀───────────── Block Root
    Tree┃          ╱││╲
        ┃         * ** *           ╮
        ┃      *   *  *   *        │ 8 levels
        ┃   *     *    *     *     ╯
        ┃  ╱╲    ╱╲    ╱╲    ╱╲
        ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Block Leaf
                                      = Note Commitment

To create a bearer note, the payer creates a transaction with a bearer note as an output but otherwise as normal, with an encrypted memo describing the purpose of the transaction and the sender’s return address.

As long as this transaction has at least one change note controlled by the payer, the payer’s client will have tracked an auth path for a note in the same block. The first two parts of this note’s auth path will be the same as the desired auth path for the bearer note. The payer (separately from the core sync logic) can then fetch the CompactBlock containing all of the note commitments created in that block, identify the commitment for the bearer note, and assemble the block-scoped portion of the auth path.

The payer can then transmit the bearer note and its auth path to the payee, along with the memo plaintext consisting of the text memo and sender return address.

Payee Computation

After receiving a bearer note, auth path, and memo plaintext, a payee can claim the payment by sweeping its funds into an address they control. The standard transaction planning logic is intended for use with notes controlled exclusively by the transaction creator, and it’s better not to modify it. Instead, they should use a special-purpose transaction creation method specifically for claiming a bearer note. This method would take as input:

• The bearer note;
• The bearer note’s auth path;
• The (user’s) address to claim funds into;
• The sender-provided memo plaintext;

and manually construct a transaction with:

• The root of the provided auth path as the anchor;
• A single Spend action whose spend auth signature is created with the bearer spend key;
• A single Output action assigning change to the user’s claim address;
• The sender-provided memo plaintext;

Data Recovery

The downside of a purely P2P data transmission system is that the P2P nodes may lose data. What happens when either the payer or payee lose their local state and need to recover it? A key design principle of Penumbra is that knowledge of a seed phrase alone should be sufficient to recover all of a user’s funds and also all relevant historical data. This is important not just for backups but also to allow the user to seamlessly synchronize views of the same wallet state on different devices.

On the payer side, a payer who syncs with the chain will detect all of the transactions they created, including the transactions that created any bearer notes used for payment links. Those transactions will have the memo text the payer sent to the payee, allowing them to understand the purpose of the transaction. The payer’s client can also identify that the transaction was creating a bearer note for a payment link (as distinct from being a finalized payment to an external wallet) because bearer notes can be statelessly identified as such. Having identified the transaction outputs as bearer notes, the payer’s client can then query to learn whether they were claimed. This prevents a user from losing funds in unclaimed payment links after they restore from a seed phrase.

On the payee side, a payee who syncs with the chain will detect the sweep transaction they used to claim a payment. This transaction replicates the sender-provided memo plaintext and return address, allowing them to understand the purpose of the transaction and who sent it.

Payment Links

This design doesn’t address the details of what exactly should go into the payment link itself and how that data should be encoded. Since this is off-chain, this seems best to leave up to an individual client, and just specify common notions of bearer notes, transaction flows, etc.

For a complete payload, the size is bounded by:

• 16 + 32 + 80 + 32 = 160 bytes for the note plaintext;
• 3 * 8 * 3 * 32 = 2304 bytes for the auth path;
• 80 + 432 = 512 bytes for the memo plaintext,

or 2976 bytes total. This is somewhat large to put in a URL, but at the point that a user is copy-pasting a URL, the exact size may not matter. An alternative would be to encrypt this payload, upload it to some relay service, and have a payment link containing only an encryption key – but this creates the problem that the relay service can then observe the sender and receiver of the payment, which is undesirable.

[colludingnode]

if 2976 bytes turns out to be too large for a URL, then a copy-paste redemption code sent via Signal wouldn’t be too inceonvenient

[colludingnode]

why can’t you simply transfer funds to a new wallet and use its spending key as the payment link, then require the recipient to sync (or resync) from genesis?

[hdevalence]

The first part (“transfer funds to a new wallet and use its spending key as the payment link”) is basically the bearer note construction. The tweak is that by deriving the spending key from the note, rather than the other way around, various frictions in the software stack are smoothed over. For instance, it means that creators of payment links can later recover info about the payment links they create.

The second part (“require the recipient to sync (or resync) from genesis”) is exactly what we’re trying to avoid. We want the claimer of a bearer note to not have to sync, for two reasons:

1. This takes more work than not syncing;
2. The sync code is designed to sync a single full viewing key, but bearer notes aren’t viewed by that viewing key, so they would need to sync twice.

However, it’s worthwhile to examine whether we could avoid the need to transmit the auth path and also avoid requiring the bearer to sync.

One starting point is the observation that if claiming a bearer note uses a fixed auth path, it will always be made relative to a specific anchor (the one just after the bearer note was created), so unless the note is claimed immediately, the claim tx will be distinguishable and this will reveal the block height the bearer note was created in. (Future transactions, however, remain completely indistinguishable).

If we accept that the bearer note creation height will be revealed, we could potentially omit the auth path from the payment link by replacing it with the note creation height.

A claimer could then ask a server for an auth path from a current anchor down to that height’s block root, and fill in the block level portion of the path the same way that the payer would construct it. This server could infer that the user was trying to claim a note created in that block, but wouldn’t know which one. (Though, if there aren’t many transactions, this might not be much different).

This RPC doesn’t currently exist but wouldn’t be too hard to create. Ideally, it would be lightweight enough that it could be added to a fullnode, so that any pd instance could serve it, and the claimer could request info from their preferred RPC, rather than a single server that would see all requests.

With that change, we’d replace 2304 bytes of auth path with 8 bytes of block height. Taking the memo field as variable length, this would result in links between 248 - 680 bytes of fragment data, substantially smaller.

[cronokirby]

Just a quick idea: because the creator of the payment link also has the ability to spend, why couldn’t they just go ahead and create the SpendProof required to spend it, and transmit that in the link instead?

To get the exact path of the note, the process for creating a payment link could involve waiting until that particular transaction is finalized, and then scanning the note commitments of the block for the particular bearer note, and then using that path and the other data to create the proof.

[nuttycom]

In Zcash, our light wallet servers provide the light wallets with a vector of the roots of the subtrees of the overall note commitment tree, each containing 2^16 notes. So for Zcash it would require just a partial witness up to height 16; the witness nodes above that height can be computed locally from the subtree roots, and then you would just need the subtree index (which is two bytes) along with the witness components within the subtree. Then, all you need is to have scanned the most recent subtree, and you have enough information to construct a witness corresponding to an anchor close to the chain tip. In Zcash we also take advantage of this design to allow scanning the chain out of order; all you need are the subtree roots plus to have scanned the subtree within which your note lives and the subtree at the chain tip in order to construct a witness.

[hdevalence]

@cronokirby

Just a quick idea: because the creator of the payment link also has the ability to spend, why couldn’t they just go ahead and create the SpendProof required to spend it, and transmit that in the link instead?

This is a neat idea! The proof would be just 192 bytes, so it would fit in the link.

However, I think it hits on a tradeoff in information disclosure. A spend proof is made with respect to a specific anchor (a historical root of the state commitment tree). Ideally, this is the most recent anchor, so that the anonymity set is “all notes made up to that point”.

If the claim transaction is made with a proof created when the bearer note was created, then the longer the payee waits to claim, the more distinguished the claim transaction will be from any other claim transaction.

On the other hand, if the payee queries an RPC to learn an auth path, they disclose some information to the RPC, but they can conceal that information from the immutable onchain data. That seems like a better tradeoff.

[finch]

@hdevalence

This RPC doesn’t currently exist but wouldn’t be too hard to create. Ideally, it would be lightweight enough that it could be added to a fullnode, so that any pd instance could serve it, and the claimer could request info from their preferred RPC, rather than a single server that would see all requests.

With that change, we’d replace 2304 bytes of auth path with 8 bytes of block height. Taking the memo field as variable length, this would result in links between 248 - 680 bytes of fragment data, substantially smaller.

Some thoughts on the implementation of this RPC:

The RPC, if thoughtfully designed, could be useful for a variety of purposes, not merely payment links. In particular, having an API to request an authentication path down to a block, alongside the block contents themselves, lends itself well to building a future “DAG sync” algorithm which traverses the user’s transaction graph to quickly find (some) notes, much faster than ordinary block-by-block sync.

It is not necessary to insert a witness for the payment link into the recipient’s commitment tree in order to sweep the payment link — with the aid of the auth path down to a compact block and the contents of that block, the recipient can compute a full auth path by joining the path to the block with a computed path created by witnessing the note commitment in the block-level tree dynamically constructed from the commitments in the block.

A note for the future: If reusing the same API for DAG sync, however, it is necessary to be able to insert commitments into the tree out of order. This functionality already exists internally in the deserialization API of the tree, but is not exposed in a safe public interface. Of particular note is that a safe public interface to insert a witnessed commitment out-of-order (1) must accept only auth paths relative to the current root of the tree (paths in the future or past of the tree cannot be inserted due to the “frontier sealing” property of the hashing construction employed), and (2) must verify the validity of the witness prior to inserting it into the tree, to prevent a third party from arbitrarily corrupting the tree with invalid hashes.

These considerations lead to a design for the RPC which is something like:

service WitnessedBlockService {
  // Returns the requested compact block, alongside its
  // authentication path relative to the most recent
  // global commitment tree root.
  rpc WitnessedBlock(WitnessedBlockRequest) returns WitnessedBlockResponse;
}

message WitnessedBlockRequest {
  // The height of the block to fetch.
  uint64 height = 1;
}

message WitnessedBlockResponse {
  // The most current anchor of the commitment tree.
  bytes anchor = 1;
  // An auth path of the block to this anchor, length
  // 2 tiers * 8 levels * 3 siblings * 32 bytes = 1,536 bytes.
  bytes block_auth_path = 2;
  // The compact block itself.
  CompactBlock compact_block = 3;
}

Of note in this design is that the RPC always returns the most up-to-date anchor (and its concomitant auth path to the block), which makes it possible to use the same RPC for a future implementation of DAG sync, while also making it more difficult to distinguish payment link spends on-chain by ensuring that clients are building spends relative to recent roots (a spend relative to a very old root stands out, and could be used to link the creation and consumption of a payment link).

As a development strategy, this RPC could be first created as a standalone service which requires access to the RPC of a pd fullnode, and then loosely integrated into pd afterwards. Some design considerations for this plan:

• Providing this API requires only the CompactBlock query service of the pd fullnode. In particular, the standalone RPC process in essence needs merely to consume an endless CompactBlock stream, using it to populate a local commitment tree which witnesses all block roots, then provide access to authentication paths for those roots.
• A naive implementation of this functionality will run into scaling issues, in particular related to memory: the TCT is designed to be incrementally serialized, but not incrementally deserialized — unlike the JMT, it is assumed that the TCT fits in memory and no facility is currently provided that lets it be mutated while only partially materialized in memory. Holding a witness for every block root would require a lower bound of (napkin math) 40 bytes per block amortized, or a memory leak of 256 MiB / year. While not enormous, it would be better not to program into pd a memory leak at all, and this is indeed possible: instead of holding all the witnessed block roots in memory, we can hold only the latest in memory, and use the incremental serialization API to persist the tree every block and then immediately forget the witnessed block root in-memory. Here, a small amount of implementation work on the TCT is required, to permit forgetting block roots at all — this is perfectly possible, but it is not exposed in the public API. Additionally, the persistence backend should be configured so as to drop any “forgessions” requested by the incremental serialization API — we want to persist blocks, then forget them in memory without dropping them on disk to match. Finally, a custom deserialization filter will be necessary to prevent re-materializing all the block roots when restarting the process: only the frontier of the tree should be read from storage, the bare minimum to construct a correct TCT for further use.
• When providing a witness for a block root, this should be read from the serialized data on disk, by a custom query that pulls the relevant hashes out. The witness will not be found in the in-memory TCT, because it will have been forgotten in-memory.
• pd uses RocksDB for backend storage, so when building an initial standalone proof-of-concept with intent to integrate eventually with pd, RocksDB could be used for persistence off the bat to avoid later refactoring to a different DB backend.
• The RPC does not need to itself cache a copy the content of each CompactBlock; it can instead proxy a query to the backing pd it is pulling data from, then attach its own augmented information.
• The data to be persisted when representing a TCT consists of a mapping from the pair (Position (= Index * 4^Height), Height (u64)) to Hash (32 bytes) (and we don’t need to track a commitments table because we will never actually persist any). In a K-V store like RocksDB, using the catenation of Position and Height (in that order) can ensure that writes are sequential, which likely will improve write performance (this likely matters only when “catching up”).
• Once integrated to pd, it is probably desirable for this information to be “backfillable”, so that the option can be flipped on (or a new version of pd released which makes it default) and the index created in retrospect. In other words, this shouldn’t be in hard lockstep with block production, because if it’s built that way, it requires doing gnarly work to handle historical chain upgrades. Doing things this way means keeping the RPC and its backing store loosely coupled to pd, likely continuing to use a separate column family for storage, and continuing to consume a (now in-memory) gRPC connection to pd’s CompactBlock query service.

As a final note, I’m interested in personally performing on this work because as the author of the TCT I have approximately all the technical context to pull it off effectively.