Notes, Commitment Tree, Nullifiers, and JoinSplits

An introduction to Nocturne's anonymous bookkeeping primitives

Just like ZCash Sprout, Nocturne performs all bookkeeping through a UTXO system of notes stored in a commitment tree. Notes are spent via JoinSplits and double-spends of notes prevented via nullifiers. Before we dive further into the protocol, we must first understand these concepts.

Notes

A note can conceptually be thought of as a "dollar bill" with an owner. It takes the form of a record with three fields:

1. owner: an anonymous stealth address for the note's owner (we will cover these in the next section)

2. asset: a field indicating the asset the note is for. Currently, Nocturne has the capability to support ERC20 (fungible tokens), ERC721 (NFTs), and ERC1155 (semi-fungible tokens).

3. value: a number indicating how much of the asset this note is for.

A note commitment is the cryptographic hash of the note. That is, H(note).

Notes can be acquired in one of three ways:

1. By depositing funds into the Nocturne contracts (i.e. "wrapping" them)

2. By receiving a "refund" containing all of the unspent assets left over at the end of an "operation"

3. By receiving a note through a JoinSplit (i.e. a "confidential payment")

Commitment Tree

On-chain, the Handler contract maintains a Merkle tree of the note commitments for all "valid" notes - that is, notes that were created by one of the above three events (deposits, refunds, and confidential payments). We refer to this tree as the commitment tree. In the process of spending a note, one must prove that the note commitment is in the commitment tree and is thus a valid UTXO in the system.

Nullifiers

To spend a note, one needs the owner's viewing key and spending key, the spending key is used to sign the transaction, and the viewing key is used to derive a secret number called a nullifier.

Every note has one nullifier, and every nullifier corresponds to one note. Nullifiers can only be derived using the owner's viewing key.

On-chain, the Handler contract keeps track of a set of nullifiers. Each time a note is spent, its nullifier is revealed and the contract will check if the revealed nullifier is in the set:

• If it's not in the set, the contract will accept the note, proceed with the transaction, and add the nullifier to the set.

• If it is in the set, then the contract will reject the note and revert.

Since each nullifier is uniquely tied to a note, nullifiers prevent double-spends. The set of all spendable notes in the tree is the set of all notes in the note commitment tree that have not yet been nullified.

JoinSplits

All Notes are spent via an operation called a JoinSplit. A JoinSplit is an operation through which two input notes are spent by revealing their nullifiers, and two output notes are created. The notes' owner must sign this operation with their spending key. They can choose the owners and amounts of the output notes, subject to the following constraints:

1. The total value of the input notes equals the total value of the output notes plus an additionally-declared public spend amount, which may be 0.

2. The input notes and output notes all have the same asset

3. Both notes' commitments are in the commitment tree

If the second input note's value is 0, the merkle proof for it is ignored by the JoinSplit circuit. This makes it so that the user isn't forced to spend two notes.

Only the following information is revealed on-chain:

• the asset to spend, unless the public spend amount is 0

• the public spend amount (can be 0)

• the nullifiers for both input notes

• the commitments for both output notes

An example JoinSplit

By choosing the values/owners of the output notes, we can use a JoinSplit to perform a wide variety of tasks:

• We can "merge" together small notes by one of the output note values to 0 and the other to the total input value. Going with the "dollar bill" analogy, this is like combining 2 $1 bills into a single $2 bill.

• We can pay another user within the protocol without revealing the amount by setting the owner to another user's stealth address. We call this a "confidential payment"

• We can unwrap assets from within the pool for usage in an operation by setting the total output amount to be less than the total input amount and specifying a nonzero public spend amount.

• We can do a combination of the above - for instance, in a single JoinSplit, I can unwrap some ETH for a Uniswap transfer AND send a confidential ETH payment to a friend.