Offline ZK-STARK P2P Payment System

[damip]

Offline ZK-STARK P2P Payment System

0. Scope

This document defines a spec-complete protocol for an offline,
single-currency, note-based payment system in which:

• each user maintains local state on their own device,
• each state update is justified by a recursive ZK proof,
• value is transferred between users by exchanging NotePackages offline, and
• a secure element with a monotonic counter prevents replay and rollback.

This specification defines:

• the secure-element interface,
• the local state and wire formats,
• the recursive proof statements,
• the transition rules,
• the mandatory preflight and crash-recovery behavior, and
• the security and privacy properties of the protocol itself.

This specification does not define:

• transport encryption or transport authentication,
• encryption of local state, journals, or cached outbound notes at rest,
• online reconciliation, device revocation, or key rotation,
• user-interface or wallet UX details.

Those omitted controls are outside the protocol definition, but they are
important in practice. In particular, implementations SHOULD protect local
storage and SHOULD use a confidential and authenticated transport when
possible, because the NotePackage itself carries privacy-sensitive content.

The key words MUST, MUST NOT, SHOULD, SHOULD NOT, and MAY
are to be interpreted as normative requirements.

---

1. Overview

Each device owns a secure element with:

• a unique device_id,
• secret signing material certified under a global root of trust, and
• a monotonic device_counter.

Each successful state transition consumes exactly one counter tick. The secure
element signs a challenge that binds that tick to the transition's full public
output. The device then produces a recursive ZK proof that the new local state
results from a valid transition from the old state.

Payments are performed by emitting notes. A sender creates one or more
notes inside a transition, generates a note proof for each emitted note, and
transmits the resulting NotePackage to the receiver. The receiver later
consumes the note in their own transition.

The proof architecture has two layers:

• Transition proofs prove correct state evolution, note consumption,
  balance conservation, mint authorization, and hardware attestation.
  Transition proofs are stored locally and are never transmitted to other
  users.
• Note proofs prove that a specific note hash appears in the output-notes
  Merkle tree of some valid transition proof. Note proofs are the only proofs
  transmitted between users.

This separation gives proof-level privacy for sender identity and fan-out while
keeping the receiver's verification material compact.

---

2. Notation, Hashing, and Constants

2.1 Canonical Encoding

safe_concat(items) is a deterministic, injective serialization of a list
of values into bytes. Distinct input lists MUST produce distinct outputs. A
compliant implementation MAY use fixed-width encodings, length-prefixed
encodings, or another injective scheme.

All composite objects in this specification MUST have a canonical serialized
form.

2.2 Hash Helper

H(tag, ...args) means:

hash(safe_concat([tag, ...args]))

The tag provides domain separation.

2.3 Domain Tags

Domain tag	Purpose
"cnt"	Secure-element counter attestation
"state"	User state hash
"note"	Note content hash
"target"	Receiver targeting
"challenge"	Secure-element challenge derivation
"blind"	Output-notes Merkle padding leaf

2.4 Helper Functions

For a state s:

state_hash(s) = H("state", s.device_id, s.device_counter, s.consumed_notes_smt_root, s.balance)

For a receiver device ID and note nonce:

note_target(receiver_device_id, nonce) = H("target", receiver_device_id, nonce)

For a note n:

note_hash(n) = H("note", n.nonce, n.target, n.amount)

2.5 Protocol Constants

Constant	Meaning
ROOT_OF_TRUST	Hardware root public key
NOTE_SLOTS	Fixed number of leaves in each output-notes Merkle tree; MUST be a power of 2
MAX_INPUT_NOTES	Fixed number of input note slots in a transition
MINTERS	Set of device IDs authorized to mint
CONSUMED_SMT_EMPTY_ROOT	Canonical root of the empty consumed-notes SMT
ZERO_PROOF	Reserved sentinel representing absence of a previous transition proof
ZERO_HASH	Reserved all-zero sentinel for genesis chain data
EMPTY_SLOT	Witness-only sentinel used to pad fixed-size arrays

ZERO_PROOF MUST NOT be accepted by proof verifiers as a valid proof encoding.

2.6 Ranges and Freshness

• device_id MUST be 32 bytes of random-looking data.
• nonce MUST be sampled fresh and uniformly for every emitted note.
• amount, device_counter, and all intermediate arithmetic values MUST be
  range-checked inside the circuit before comparison or subtraction.
• Every blinding nonce used for Merkle padding MUST be sampled fresh
  independently.
• All fixed-size arrays are padded with EMPTY_SLOT so the circuit shape does
  not reveal how many notes are actually present.

---

3. Secure Element

Each device contains a tamper-resistant secure element provisioned at
manufacture with a unique identity and signing keys certified under
ROOT_OF_TRUST.

3.1 Persistent State

device_id        -- 32-byte immutable identifier
device_secrets   -- hardware signing key material, never exposed
device_counter   -- monotonic counter, initially 0
last_certificate -- last emitted certificate, initially NULL

3.2 Interface

Function increment(challenge) -> certificate:
    device_counter += 1
    last_certificate = certify(
        device_secrets,
        H("cnt", device_counter, device_id, challenge)
    )
    return last_certificate

Function get_last_certificate() -> (counter, certificate):
    return (device_counter, last_certificate)

Function get_device_id() -> device_id:
    return device_id

3.3 Required Semantics

• increment() is irreversible.
• device_counter MUST never decrease.
• get_last_certificate() MUST be side-effect free.
• The secure element MUST sign exactly the tuple
  (device_counter, device_id, challenge) under domain tag "cnt".

---

4. State, Notes, and Wire Objects

4.1 Local State

Local state is stored outside the secure element and consists of core state
plus chain data.

Core state

device_id
device_counter       -- mirrors hardware counter at last successful transition
consumed_notes_smt   -- sparse Merkle tree keyed by note hash, value = 1 if consumed
balance              -- non-negative integer, single-currency balance

The empty consumed-notes tree MUST have root CONSUMED_SMT_EMPTY_ROOT.

The state hash is:

state_hash(state) = H("state", state.device_id, state.device_counter, state.consumed_notes_smt_root, state.balance)

Chain data

previous_transition_proof    -- proof of prior transition, or ZERO_PROOF at genesis
previous_output_notes_merkle -- output-notes root of prior transition, or ZERO_HASH at genesis
previous_output_state_hash   -- state hash of prior transition, or ZERO_HASH at genesis

4.2 Note

A note is the atomic unit of transferred value.

nonce    -- fresh random value
target   -- H("target", receiver_device_id, nonce)
amount   -- positive integer

Its hash is:

note_hash(note) = H("note", note.nonce, note.target, note.amount)

The sender's identity does not appear in the note itself.

4.3 NotePackage

This is the object transmitted from sender to receiver.

note
note_proof

No transition proof, sender identity, Merkle authentication path, or sender
state hash is transmitted directly.

4.4 Transition Journal

Before touching the secure element, the wallet MUST persist a journal entry that
is sufficient to retry the exact same transition after a crash.

The journal entry MUST contain at least:

input_state
previous_transition_proof
previous_output_notes_merkle
previous_output_state_hash
input_notes[MAX_INPUT_NOTES]
output_notes[NOTE_SLOTS]
mint_amount
blinding_nonces[NOTE_SLOTS]
output_notes_merkle
output_state_hash
challenge

The journal is privacy-sensitive because it contains full transition witnesses.

---

5. Unified Recursive Proof Architecture

The protocol uses a single recursive circuit with a public mode selector:

mode ∈ { TRANSITION, NOTE }

This is a flag-based, Mina-like construction: both proof statements live inside
one larger circuit, and recursive verification always targets that same unified
circuit. This avoids circular verification-key dependencies at the cost of a
larger circuit than either statement alone.

5.1 Public Statements

For mode = TRANSITION, the public inputs are:

mode = TRANSITION
output_notes_merkle
output_state_hash

For mode = NOTE, the public inputs are:

mode = NOTE
note_hash

5.2 Verifier Interfaces

Function verify_transition_proof(proof, output_notes_merkle, output_state_hash):
    return verify_unified_proof(proof, public_inputs={
        mode: TRANSITION,
        output_notes_merkle: output_notes_merkle,
        output_state_hash: output_state_hash,
    })

Function verify_note_proof(proof, note_hash):
    return verify_unified_proof(proof, public_inputs={
        mode: NOTE,
        note_hash: note_hash,
    })

5.3 Operational Consequences

• Transition proofs are local-only artifacts.
• Note proofs are the only proofs sent to other users.
• A transition consuming received notes verifies subproofs with mode = NOTE.
• A note proof verifies a subproof with mode = TRANSITION.

The chosen proof system MUST support recursive verification of this unified
mode-flagged circuit.

---

6. Transition Mode (mode = TRANSITION)

6.1 Public Inputs

mode = TRANSITION
output_notes_merkle
output_state_hash

device_id is intentionally not a public input. It is committed inside
output_state_hash and remains hidden from any party that does not possess the
full witness.

6.2 Secret Inputs

device_id
input_state
previous_transition_proof
previous_output_notes_merkle
previous_output_state_hash
input_notes[MAX_INPUT_NOTES]   -- NotePackages, padded with EMPTY_SLOT
output_notes[NOTE_SLOTS]       -- Notes to emit, padded with EMPTY_SLOT
mint_amount                    -- 0 for non-minting transitions
device_cert
blinding_nonces[NOTE_SLOTS]

6.3 Circuit Logic

CONST ROOT_OF_TRUST = [hardware root public key]
CONST MINTERS       = [authorized minter device IDs]

// ---------------------------------------------------------------
// 1. Verify chain continuity
// ---------------------------------------------------------------

if previous_transition_proof == ZERO_PROOF:
    assert(input_state.device_counter == 0)
    assert(input_state.consumed_notes_smt_root == CONSUMED_SMT_EMPTY_ROOT)
    assert(input_state.balance == 0)
    assert(previous_output_state_hash == ZERO_HASH)
    assert(previous_output_notes_merkle == ZERO_HASH)
else:
    verify_transition_proof(
        previous_transition_proof,
        previous_output_notes_merkle,
        previous_output_state_hash
    )
    assert(previous_output_state_hash == state_hash(input_state))

assert(input_state.device_id == device_id)

// ---------------------------------------------------------------
// 2. Start output state
// ---------------------------------------------------------------

let output_state = input_state.clone()
output_state.device_counter = input_state.device_counter + 1

// ---------------------------------------------------------------
// 3. Consume input notes
// ---------------------------------------------------------------

let total_received = 0

for note_pkg in input_notes:
    if note_pkg == EMPTY_SLOT:
        continue

    let nh = note_hash(note_pkg.note)

    assert(note_pkg.note.amount > 0)
    assert(note_pkg.note.target == note_target(device_id, note_pkg.note.nonce))

    assert(!output_state.consumed_notes_smt.contains(nh))
    output_state.consumed_notes_smt.insert(nh)

    verify_note_proof(note_pkg.note_proof, nh)

    total_received += note_pkg.note.amount

// ---------------------------------------------------------------
// 4. Mint authorization
// ---------------------------------------------------------------

assert(mint_amount >= 0)
if mint_amount > 0:
    assert(device_id in MINTERS)

// ---------------------------------------------------------------
// 5. Build output notes tree
// ---------------------------------------------------------------

let total_sent = 0
let leaves[NOTE_SLOTS]
let emitted_hashes[NOTE_SLOTS]

for i in 0..NOTE_SLOTS:
    if output_notes[i] == EMPTY_SLOT:
        emitted_hashes[i] = EMPTY_SLOT
        leaves[i] = H("blind", blinding_nonces[i])
    else:
        assert(output_notes[i].amount > 0)
        emitted_hashes[i] = note_hash(output_notes[i])
        leaves[i] = emitted_hashes[i]
        total_sent += output_notes[i].amount

for i in 0..NOTE_SLOTS:
    for j in (i + 1)..NOTE_SLOTS:
        if emitted_hashes[i] != EMPTY_SLOT and emitted_hashes[j] != EMPTY_SLOT:
            assert(emitted_hashes[i] != emitted_hashes[j])

assert(output_notes_merkle == build_merkle(leaves))

// ---------------------------------------------------------------
// 6. Balance conservation
// ---------------------------------------------------------------

output_state.balance =
    input_state.balance + total_received + mint_amount - total_sent

assert(output_state.balance >= 0)

// ---------------------------------------------------------------
// 7. Hardware attestation
// ---------------------------------------------------------------

let challenge = H("challenge",
    state_hash(input_state),
    output_state_hash,
    output_notes_merkle
)

assert(device_cert.verify(
    ROOT_OF_TRUST,
    device_id = device_id,
    data = H("cnt", output_state.device_counter, device_id, challenge)
))

// ---------------------------------------------------------------
// 8. Finalize
// ---------------------------------------------------------------

assert(output_state_hash == state_hash(output_state))

6.4 Enforced Properties

Transition mode enforces:

• append-only chaining to the previous transition,
• one counter tick per transition,
• note consumption only by the targeted receiver,
• no local re-consumption of the same note hash,
• no unauthorized minting,
• balance conservation, and
• unique non-empty emitted notes within a single transition.

---

7. Note Mode (mode = NOTE)

7.1 Public Inputs

mode = NOTE
note_hash

This is the only protocol-level statement visible to an external verifier.

7.2 Secret Inputs

transition_proof
transition_output_notes_merkle
transition_output_state_hash
note_merkle_proof

7.3 Circuit Logic

verify_transition_proof(
    transition_proof,
    transition_output_notes_merkle,
    transition_output_state_hash
)

assert(verify_merkle_proof(
    root  = transition_output_notes_merkle,
    leaf  = note_hash,
    proof = note_merkle_proof
))

Because note leaves use domain tag "note" and padding leaves use domain tag
"blind", a blinding leaf cannot masquerade as a real note except via a hash
collision.

7.4 What a Note Proof Means

A valid note proof says:

"There exists a valid transition proof whose output-notes Merkle tree contains
this note_hash as a leaf."

It does not reveal:

• the sender device ID,
• the sender balance,
• any sibling notes emitted in the same transition, or
• the sender's transition proof public outputs.

---

8. Mandatory Preflight and Transition Planning

8.1 Untrusted Input Rule

Every received NotePackage MUST be treated as adversarial input.

The wallet MUST NOT call increment() for a transition that depends on
unverified external data.

This rule is mandatory because once increment() succeeds, the counter tick is
burned. Calling it for an infeasible transition can permanently desynchronize
the account from its local state.

8.2 Required Preflight for Received Notes

Before journaling or calling increment(), the receiver MUST perform:

Function preflight_received_note(note_pkg, self_device_id, current_state):
    let nh = note_hash(note_pkg.note)

    assert(note_pkg.note.amount > 0)
    assert(note_pkg.note.target == note_target(self_device_id, note_pkg.note.nonce))
    assert(!current_state.consumed_notes_smt.contains(nh))
    assert(verify_note_proof(note_pkg.note_proof, nh))

    return nh

If multiple received notes are consumed in one transition, the wallet MUST also
check that all preflighted note hashes in that batch are distinct and that the
batch length does not exceed MAX_INPUT_NOTES.

If any preflight step fails, the wallet MUST abort the operation without
touching the secure element.

8.3 Required Planning Before increment()

Before calling increment(), the wallet MUST:

1. Construct the exact witness for the intended transition.
2. Verify all received notes with the mandatory preflight above.
3. Verify local feasibility:
   • all counts fit within MAX_INPUT_NOTES and NOTE_SLOTS,
   • all note amounts are positive,
   • all arithmetic is in range,
   • the resulting balance will be non-negative,
   • all non-empty output notes are pairwise distinct.
4. Compute output_notes_merkle.
5. Compute the post-transition output_state_hash.
6. Compute the secure-element challenge.
7. Persist the full transition journal.
8. Only then call increment(challenge).

This ordering is normative.

8.4 Proof Generation After increment()

After increment(challenge) returns a certificate, the wallet MUST:

1. generate the transition proof,
2. generate one note proof for each emitted note,
3. atomically persist the new local state and chain data,
4. retain outbound NotePackages until they are safely delivered or otherwise
   acknowledged by the implementation's transport layer.

The protocol does not define acknowledgements, but retaining outbound notes is
important to avoid stranding funds due to delivery failure.

---

9. User Operations

Every user operation follows the same lifecycle:

1. plan the exact transition,
2. run all mandatory preflight checks,
3. journal the transition,
4. call increment(challenge),
5. generate the transition proof,
6. generate note proofs for emitted notes,
7. atomically commit local state.

9.1 Create Account

1. Obtain a provisioned secure element.
2. Read device_id.
3. Initialize local state:
   • device_id = get_device_id()
   • device_counter = 0
   • empty consumed_notes_smt with root CONSUMED_SMT_EMPTY_ROOT
   • balance = 0
   • chain data set to ZERO_PROOF, ZERO_HASH, ZERO_HASH
4. Plan a genesis transition with:
   • no input notes,
   • no output notes,
   • mint_amount = 0
5. Execute the standard lifecycle above.

The genesis transition consumes the first counter tick. After successful account
creation, local device_counter = 1.

9.2 Send Money

To send amount to receiver_device_id:

1. Ensure amount > 0.

2. Ensure the planned transition will leave a non-negative balance.

3. Construct one output note:

   Note:
       nonce  = random()
       target = note_target(receiver_device_id, nonce)
       amount = amount
   

4. Place that note in output_notes; pad remaining slots with EMPTY_SLOT.

5. Sample fresh blinding nonces for every empty output slot.

6. Plan the transition with:

   • input_notes = []
   • output_notes = [the new note]
   • mint_amount = 0

7. Execute the standard lifecycle.

8. Transmit the resulting NotePackage(note, note_proof) to the receiver.

9. Keep a cached copy of the outbound NotePackage until delivery is confirmed
   or the implementation's transport policy allows deletion.

9.3 Receive Money

To consume one received NotePackage:

1. Receive (note, note_proof) from the sender.
2. Run the mandatory preflight in Section 8.2.
3. Plan a transition with:
   • input_notes = [note_package]
   • output_notes = []
   • mint_amount = 0
4. Sample fresh blinding nonces for all NOTE_SLOTS output positions, because
   the output tree still has fixed size even when no notes are emitted.
5. Execute the standard lifecycle.

If the preflight fails, the wallet MUST reject the note without consuming a
counter tick.

9.4 Mint

Only a device whose device_id is in MINTERS may mint.

To mint mint_amount:

1. Ensure mint_amount > 0.
2. Plan a transition with:
   • zero or more input notes,
   • zero or more output notes,
   • mint_amount = desired minted value
3. Ensure the transition satisfies all normal planning checks.
4. Execute the standard lifecycle.

Minted value may be retained in local balance, sent out as notes, or split
between both, subject to the balance equation.

---

10. Crash Recovery and Atomic Commit

10.1 Why Recovery Is Required

If the app crashes after increment() but before proof generation and commit,
the hardware counter advances while local state does not. Without recovery, the
account can no longer produce a valid next transition.

10.2 Recovery Procedure

On startup:

1. Check whether a transition journal exists.
2. If no journal exists, continue normally.
3. If a journal exists, call get_last_certificate() and obtain
   (counter, certificate).
4. Compare the returned values with the journal:
   • If counter == journal.input_state.device_counter + 1 and certificate
     matches journal.challenge, resume the exact planned transition.
   • If counter == journal.input_state.device_counter, increment() never
     happened; discard the stale journal and restart planning from scratch.
   • Otherwise, stop and require explicit recovery logic or operator
     intervention because the secure element and local state are inconsistent.
5. If resuming, regenerate:
   • the transition proof using the recovered certificate,
   • each outbound note proof,
   • the final atomic commit.

10.3 Atomic Commit Requirements

After a transition and all required outbound note proofs are produced
successfully, the wallet MUST atomically persist:

device_id                     = output_state.device_id
device_counter                = output_state.device_counter
consumed_notes_smt            = output_state.consumed_notes_smt
balance                       = output_state.balance
previous_transition_proof     = transition_proof
previous_output_notes_merkle  = output_notes_merkle
previous_output_state_hash    = output_state_hash

The journal MUST be cleared as part of the same atomic commit boundary.

---

11. Security Properties

Property	Mechanism
No replay / rollback	Every transition consumes one monotonic counter tick, and the certificate binds that tick to the transition challenge. The proof chain also links each transition to the previous one.
No local double-consumption	consumed_notes_smt is part of proven state. Re-inserting the same note hash fails.
Receiver-only note consumption	Transition mode requires note.target == note_target(device_id, nonce). A note can only be consumed by its intended receiver.
No note forgery	A received note is accepted only if its note proof verifies, and that note proof recursively anchors to a valid transition proof.
No unauthorized minting	mint_amount > 0 is allowed only when secret device_id ∈ MINTERS.
No inflation by ordinary users	The transition circuit enforces output_balance = input_balance + received + minted - sent with output_balance >= 0.
No accidental duplicate outputs	The transition circuit requires all non-empty emitted note hashes in one transition to be pairwise distinct.
Crash safety	Journaling plus get_last_certificate() allows replay of the exact planned transition after a crash.

---

12. Privacy Properties and Privacy Limits

12.1 Proof-Level Privacy

Property	Mechanism
Sender identity hidden from note observers	device_id is secret inside both proof modes and is not a public input of note proofs.
Sender balance hidden from note observers	Balance appears only inside the sender's local transition witness and the hidden output_state_hash secret carried inside note mode.
Fan-out hidden from note observers	Output trees have fixed size NOTE_SLOTS and are padded with blinding leaves.
Cross-note unlinkability at the proof interface	Two note proofs from the same transition reveal different note_hash values and do not expose the common transition root publicly.
Receiver unlinkability against blind observers	target = H("target", receiver_device_id, nonce) uses a fresh nonce, so notes to the same receiver do not share a stable visible target value.

12.2 Privacy Limits

The protocol's privacy guarantees are about proof statements, not about the
raw contents of a transported NotePackage.

The following limits apply:

• The receiver necessarily learns the note amount.
• Any party that obtains the NotePackage can read the note fields unless an
  external confidentiality layer protects them.
• A targeted observer who already knows a candidate device_id can test
  whether that device is the receiver by recomputing
  H("target", candidate_device_id, nonce).
• Sender and receiver may learn each other's identities through the surrounding
  application or in-person exchange, even though the proof layer does not
  publish them.

12.3 Operational Privacy Requirements

Although out of scope for the cryptographic protocol itself, implementations
SHOULD:

• encrypt local state, journals, cached outbound notes, and stored transition
  proofs at rest,
• use a confidential and authenticated transport whenever possible,
• avoid exposing raw device_id values except to intended counterparties.

These controls are important because they protect the note contents and local
wallet history, which the proof system by itself does not hide from a device or
transport compromise.

---

13. Trust Assumptions

• The secure element is tamper-resistant: its counter cannot be rewound and its
  signing keys cannot be extracted.
• ROOT_OF_TRUST is authentic and distributed securely.
• The chosen ZK proof system is computationally sound under recursion,
  including self-recursive verification of the unified mode-flagged circuit.
• The hash function and Merkle construction are collision-resistant.
• Wallet software has access to good randomness for note nonces and blinding
  nonces.

---

14. Known Limitations

• No device revocation offline: a compromised secure element cannot be
  revoked by this protocol alone.
• Static minter set: MINTERS is a circuit constant. Changing it requires a
  circuit upgrade and state migration strategy.
• Unbounded consumed-notes tree: proof cost grows as the consumed-notes SMT
  grows.
• No real-time fraud detection: if the hardware trust assumption fails,
  conflicting histories are only detectable when compared externally.
• Note proof cost scales with fan-out: each emitted note requires its own
  recursive note proof.
• No expiry or built-in acknowledgement layer: the protocol does not define
  note expiration, cancellation, or delivery receipts.
• Outbound delivery reliability is an application concern: if a sender does
  not retain an outbound NotePackage until confirmed delivery, value may be
  stranded operationally even though the note remains valid.
• Transport confidentiality is external: the protocol does not itself hide
  note contents from a party that captures the NotePackage.
• Unified circuit overhead: the Mina-like flag-based recursion removes
  verification-key circularity but makes the single recursive circuit larger
  than either statement alone.

---

15. Summary of Compliance Requirements

A compliant implementation MUST, at minimum:

1. implement the secure-element API exactly as specified,
2. maintain local state and chain data in the specified form,
3. use the unified recursive circuit with mode ∈ {TRANSITION, NOTE},
4. keep transition proofs local and transmit only NotePackages,
5. perform mandatory preflight on all received notes before increment(),
6. fully plan and journal the transition before increment(),
7. generate note proofs for all emitted notes,
8. commit state atomically and support crash recovery,
9. enforce all circuit constraints described in Sections 6 and 7.

An implementation that calls increment() before successful preflight and
transition planning is not compliant with this specification.