Transaction

A transaction kernel consists of the following fields:

• inputs: Vec<RemovalRecord> The commitments to the UTXOs that are consumed by this transaction.
• outputs: Vec<AdditionRecord> The commitments to the UTXOs that are generated by this transaction.
• public_announcements: Vec<PublicAnnouncement> a list of self-identifying strings broadcasted to the world. These may contain encrypted secrets but only the recipient(s) can ascertain that.
• fee: NativeCurrencyAmount A reward for the miner who includes this transaction in a block.
• coinbase: Option<NativeCurrencyAmount> The miner is allowed to set this field to a mining reward which is determined by various variable network parameters.
• timestamp: Timestamp When the transaction took or takes place.
• mutator_set_hash: Digest A commitment to the mutator set that is to be updated by the transaction.

Note that while addition records and removal records are both commitments to UTXOs, they are different types of commitments. The removal record is an index set into the SWBF (with supporting chunk dictionary) whereas the addition record is a hash digest.

Validity

Transaction validity is designed to check four conditions:

1. The lock scripts of all input UTXOs halt gracefully
2. All involved typescripts halt gracefully
3. All input UTXOs are present in the mutator set's append-only commitment list
4. All input UTXOs are not present in the mutator set's sliding-window Bloom filter.

A transaction is valid if (any of):

• a) it has a valid witness (including spending keys and mutator set membership proofs)
• b) it has valid proofs for each subprogram (subprograms establish things like the owners consent to this transaction, there is no inflation, etc.)
• c) it has a single valid proof that the entire witness is valid (so, a multi-claim proof of all claims listed in (b))
• d) it has a single valid proof that the transaction originates from merging two valid transactions
• e) it has a single valid proof that the transaction belongs to an integral mempool, i.e., one to which only valid transactions were added
• f) it has a single valid proof that another single valid proof exists but under an older timestamp or mutator set accumulator
• g) it has a single valid proof that another single valid proof exists (but possibly with an older version of the proof system or different parameters).

For the purpose of describing computations and claims, the following notation is used. The symbol : denotes the type of an object, whereas :: denotes the type signature of a computation (interpreting the input and output streams as arguments and return values, respectively).

A: Witness Validity

The transaction witness represents all raw data necessary to prove a transaction valid. It does not contain any proof data. In the code this data structure is called PrimitiveWitness to highlight the fact that it does not elide any witness information.

A transaction witness is defined to be valid if, after deriving from it a set of claims as listed in (b) and nondeterminisms, all programs halt gracefully.

A transaction witness consists of the following fields:

• input_utxos: SaltedUtxos A wrapper object wrapping together a list of input Utxos and a salt, which is 3 BFieldElements.
• lock_scripts_and_witnesses: Vec<LockScriptAndWitness> The lock scripts determine the spending policies of the input UTXOs; in the simplest case, whether their owners approve of the transaction.
• type_scripts_and_witnesses: Vec<TypeScriptAndWitness> The scripts that authenticate the correct evolution of all token types involved.
• input_membership_proofs: Vec<MsMembershipProof> Membership proofs in the mutator set for the input UTXOs.
• output_utxos: SaltedUtxos A wrapper object wrapping together a list of output Utxos and a salt, which is 3 BFieldElements.
• output_sender_randomnesses: Vec<Digest> Senders' contributions to output commitment randomnesses.
• output_receiver_digests: Vec<Digest> Receivers' contributions to output commitment randomnesses.
• mutator_set_accumulator: MutatorSetAccumulator The mutator set accumulator, which is the anonymous accumulator.
• kernel: TransactionKernel The transaction kernel that this witness attests to.

Note that a (transaction, valid witness) pair cannot be broadcasted because that would undermine both soundness and privacy.

B: Standard Decomposition into Subclaims

The motivation for splitting transaction validity into subclaims is that the induced subprograms can be proved individually, which might be cheaper than proving the whole thing in one go. Also, it is conceivable that components of a transaction are updated and do not invalidate all subproofs but only a subset of them. The subprograms are as follows.

• RemovalRecordsIntegrity :: (transaction_kernel_mast_hash : Digest) ⟶ (inputs_salted_utxos_hash : Digest) Establishes that all removal records (which themselves are commitments to input UTXOs) are correctly computed and applicable. Specifically:

  • divine the input UTXOs
  • divine the salt
  • divine the mutator set accumulator and authenticate it against the given transaction kernel MAST hash
  • for each input UTXO:
    • divine the receiver preimage
    • divine the sender randomness
    • compute the canonical commitment
    • verify the membership of the canonical commitment to the AOCL
    • compute the removal record index set
    • verify that the calculated removal record index set matches the claimed index set
  • hash the list of removal record sets and authenticate it against the given transaction kernel MAST hash
  • output the hash of the salted input UTXOs.

  Checks ensuring that each AOCL index is unique and that the published authentication paths are valid, are delegated to the miner and do, for performance reasons, not belong here. Checks that the removal record has not already been applied (i.e. no double-spend) is also delegated to the miner.

• KernelToOutputs :: (transaction_kernel_mast_hash : Digest) ⟶ (outputs_salted_utxos_hash : Digest) Collects the output UTXOs into a more digestible format. Specifically:

  • divine the output UTXOs
  • divine the salt
  • for each output UTXO:
    • divine the commitment randomness
    • compute the canonical commitment
  • hash the list of canonical commitments
  • authenticate the list of canonical commitments against the given transaction kernel MAST hash
  • output the hash of the salted UTXOs.

• CollectLockScripts :: (inputs_salted_utxos_hash : Digest) ⟶ (lock_script_hashes : [Digest]) Collects the lock script hashes into a list. Specifically:

  • divine the input UTXOs
  • divine the salt
  • authenticate the salted UTXOs against the given hash digest
  • for each UTXO:
    • collect the lock script hash
  • output all lock script hashes.

• LockScript :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ Unlocks a single input UTXO. The concrete program value of a lockscript depends on the UTXO. By default, this program is created by a generation address, in which case it asserts knowledge of a preimage to a hardcoded digest. This lock script for every UTXO must halt gracefully.

• CollectTypeScripts :: (inputs_salted_utxos_hash : Digest) × (outputs_salted_utxos_hash : Digest) ⟶ (type_script_hashes : [Digest]) Collects the type scripts into a more digestible format. Specifically:

  • divine all input UTXOs
  • divine the salt for input UTXOs
  • authenticate the salted input UTXOs against the given hash digest
  • divine all output UTXOs
  • divine the salt for output UTXOs
  • authenticate the salted output UTXOs against the given hash digest
  • for each input or output UTXO:
    • collect the type script hash
  • filter out duplicates
  • output the unique type script hashes

• TypeScript :: (transaction_kernel_mast_hash : Digest) × (salted_input_utxos_hash : Digest) × (salted_output_utxos_hash : Digest) ⟶ ∅ Authenticates the correct evolution of all UTXOs of a given type. The concrete program value depends on the token types involved in the transaction. For Neptune's native currency, Neptune Coins, the type script asserts that a) all output amounts are positive, and b) the sum of all input amounts is greater than or equal to the fee plus the sum of all output amounts. Every type script whose hash was returned by CollectTypeScripts must halt gracefully.

Diagram 1 shows how the explicit inputs and outputs of all the subprograms relate to each other. Single arrows denote inputs or outputs. Double lines indicate that the program(s) on the one end hash to the digest(s) on the other.

Diagram 1: Transaction validity.

All subprograms can be proven individually given access to the transaction's witness. The next table shows which fields of the TransactionPrimitiveWitness are (potentially) used in which subprogram.

Note that none of the subprograms require that each removal record lists one SWBF index that does not yet live in the mutator set SWBF. This absence is required for the transaction to be confirmable, but not for it to be valid. If the transaction has an input whose index set is already entirely contained by the mutator set SWBF, then this transaction can never be confirmed. Even if there is a reorganization that results in the absence criterion being satisfied, the transaction commits to the mutator set hash and this commitment cannot be undone.

C: Multi-Claim Proof

Where (b) generates a separate proof for every individual subclaim, (c) generates one proof for the batch of claims. The set of claims established is identical; the main benefit comes from having only one execution of the Triton VM prover.

D: Transaction Merger

Two transactions can be merged into one. Among other things, this operation replaces two proofs with just one. The program TransactionMerger :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ verifies a transaction resulting from a merger as follows:

• divine txa : TransactionKernel
• verify proof for txa (proof is divined)
• divine txb : TransactionKernel
• verify proof for txb (proof is divined)
• for each removal record rr in txa.inputs
  • verify that rr is not a member of txb.inputs
• for each removal record rr in txb.inputs
  • verify that rr is not a member of tba.inputs
• verify that at most one of txa.coinbase and txb.coinbase is set
• verify that txa.mutator_set_hash == txb.mutator_set_hash
• compile a new TransactionKernel object kernel:
  • set kernel.inputs to txa.inputs || txb.inputs after shuffling randomly
  • set kernel.outputs to txa.outputs || txb.outputs after shuffling randomly
  • set kernel.public_announcements to txa.public_announcements || txb.public_announcements after shuffling randomly
  • set kernel.coinbase to txa.coinbase or txb.coinbase or to None
  • set kernel.fee to txa.fee + txb.fee
  • set kernel.timestamp to max(txa.timestamp, txb.timestamp)
  • set kernel.mutator_set_hash to txa.mutator_set_hash
• compute the mast hash of kernel
• verify the computed hash against the given transaction_kernel_mast_hash.

E: Proof of Integral Mempool Operation

A transaction is valid if it was ever added to an integral mempool. The motivating use case for this feature is that mempool operators can delete transaction proofs as long as they store and routinely update one

An integral mempool is an MMR containing transactions kernels, along with a proof of integral history. The integral mempool can be updated in only one way: by appending a valid transaction.

• append : (old_mmr : Mmr<TransactionKernel>) × (old_history_proof: StarkProof) × (tx : Transaction) ⟶ (new_mmr : Mmr<TransactionKernel>) × (new_history_proof : StarkProof)

The proof of integral history certifies that the MMR is the (left-hand side of the) output of some append operation. Specifically, the claim is the input-output-program triple

• input: mmr : Mmr<TransactionKernel>
• output: ∅
• program:
  • if mmr is empty, halt gracefully; otherwise
  • divine old_mmr
  • divine tx_kernel
  • verify tx_kernel with some divined transaction proof
  • append tx_kernel to old_mmr resulting in new_mmr
  • assert that new_mmr == mmr.

The claim for certifying the validity of transaction based on its inclusion in an integral mempool is induced by MemberOfIntegralMempool :: (transaction_kernel_mast_hash : Digest) ⟶ ∅, and the program executes the following logic:

• divine mmr : Mmr<TransactionKernel>
• verify mmr with some divined proof of integral history
• verify membership of transaction_kernel_mast_hash to mmr with a divined authentication path.

F: Transaction Data Update

A transaction is valid if another transaction that is identical except for fixing an older mutator set hash or timestamp, was valid. Specifically, the program TransactionDataUpdate :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ verifies the update of transaction data as follows:

• divine old_kernel : TransactionKernel
• verify old_kernel with some divined proof
• create a new TransactionKernel object new_kernel
• set all fields of new_kernel to the matching field of old_kernel except:
  • set new_kernel.timestamp such that new_kernel.timestamp >= old_kernel.timestamp
  • set new_kernel.mutator_set_hash =/= tx.mutator_set_hash only if the following instructions execute gracefully without crashing
    • divine the mutator set AOCL MMR accumulator new_kernel_aocl
    • authenticate new_kernel_aocl against the mutator set MAST hash new_kernel.mutator_set_hash using a divined authentication path
    • divine the mutator set AOCL MMR accumultar old_kernel_aocl
    • authenticate the old_kernel_aocl against the mutator set MAST hash old_kernel.mutator_set_hash using a divined authentication path
    • verify that there is a set of AOCL leafs whose addition sends old_kernel_aocl to new_kernel_aocl
  • set new_kernel.inputs to the following list:
    • each index set is identical to the matching index set from old_kernel
    • read the chunks dictionary
    • for every index in the inactive part of the SWBF, verify that it lives in some chunk
    • for every chunk in the chunk dictionary, verify its authentication path (either from divine_sibling or memory -- to be decided)

G: Transaction Proof Update

Triton VM allows proofs to be updated to a new version of the proof system or to new proof system parameters. However, this is a property of Triton VM proofs and not of Neptune transactions, so it is covered in the relevant documentation of Triton VM.

Putting Everything Together

Clauses (b)--(f) are presented as separate computations, but in reality the master program for transaction validity TransactionIsValid :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ is a disjunction of these clauses. Specifically:

• do any of:
  • verify all of the following claims, individually or via one multi-claim proof:
    • RemovalRecordsIntegrity :: (transaction_kernel_mast_hash : Digest) ⟶ (inputs_salted_utxos_hash : Digest)
    • CollectLockScripts :: (inputs_salted_utxos_hash : Digest) ⟶ (lock_script_hashes : [Digest])
    • LockScript :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ for each lock script hash
    • KernelToOutputs :: (transaction_kernel_mast_hash : Digest) ⟶ (outputs_salted_utxos_hash : Digest)
    • CollectTypeScripts :: (inputs_salted_utxos_hash : Digest) × (outputs_salted_utxos_hash : Digest) ⟶ (type_script_hashes : [Digest])
    • TypeScript :: (transaction_kernel_mast_hash : Digest) ⟶ ∅ for each type script hash;
  • verify claim TransactionMerger :: (transaction_kernel_mast_hash : Digest) ⟶ ∅
  • verify claim MemberOfIntegralMempool :: (transaction_kernel_mast_hash : Digest) ⟶ ∅
  • verify claim TransactionDataUpdate :: (transaction_kernel_mast_hash : Digest) ⟶ ∅.