# PVUGC (Trustless) — Deterministic, Public-Authenticated One-Shot Rows for BitVM3 with **CTV + CAT + GC**

**License:** CC-BY 4.0
**Assumes:** Taproot/Tapscript with `OP_CAT` and `OP_CHECKTEMPLATEVERIFY` (new tapscript version)

**Intent.** Keep BitVM3 choreography (off-chain bad-row search; on-chain single-row predicate), eliminate operator keys/pre-sigs. **GC proves correctness** (the assignment satisfies all gates and binds public I/O); **CAT** authenticates row operands to the committed assignment; **CTV** makes exits keyless & deterministic.

* **Correctness:** GC attests full circuit satisfaction & public I/O binding.
* **Authenticity:** CAT-Merkle membership for `(w,b)` at L, R, O.
* **Row binding:** Each row **Merkle-proves** `(row_id, gate_type, wL, wR, wO)` from `GateRoot`.
* **Keyless exits:** **CTV** enforces canonical Cancel/Finalize parents (RBF) and CSV-gated Finalize.
* **Determinism:** `(state_hdr, row_table)` → unique P2TR.

---

## 0. Threat Model & Goals

* **Zero operator trust.** No runtime keys/adaptors/pre-sigs.
* **Permissionless challenges.** Anyone can open a contradictory row.
* **Deterministic funding.** Canonical P2TR derived from `(state_hdr,row_table)`.
* **Public authenticity.** L/R/O bits proven from public commitments using CAT.
* **Script minimality.** Equality/arithmetic + `CAT` + `CTV` + `SHA256`.

**Non-goals:** on-chain SNARK recursion; covenants beyond CTV; private labels/MACs (GC remains off-chain proof of correctness).

**Network policy assumption (liveness):** BIP125 **opt-in RBF** honored by miners/topology.

---

## 1. Notation, Encodings, Tags (consensus-critical)

* `H = SHA256`.
* Big-endian: `enc_u64_be`, `enc_u32_be`, `enc_u8`.
* **Booleans:** `enc_bool ∈ {0x00,0x01}` (size **exactly 1**); Script truth minimal (`true=0x01`, `false=""`).
* List-Merkle internal: `H("pvugc/merkle/node" || left32 || right32)`; dup-last shaping.
* Leaves: `H("pvugc/merkle/leaf" || <payload>)`.
* All pushes minimal; **exact sizes**; **no trailing bytes**.

**Tags (ASCII exact):**
`"pvugc/doc-hash"`, `"pvugc/statehdr"`, `"pvugc/gate"`, `"pvugc/merkle/leaf"`, `"pvugc/merkle/node"`, `"pvugc/row/opctx"`.

---

## 2. Objects & Commitments (consensus)

### 2.1 Gate table (list-Merkle; **mandatory**)

gate_leaf = H("pvugc/gate" || enc_u64_be(row_id) || enc_u8(gate_type)  # 0=AND, 1=XOR
                        || enc_u64_be(wL) || enc_u64_be(wR) || enc_u64_be(wO))
GateRoot  = merkle_dup_last(gate_leaf[*])   # rows sorted by row_id; row_id unique

### 2.2 Assignment (one bit per wire)

Use a fixed-depth SMT (depth 64, 64-bit wire IDs) committing **exactly one** bit per wire. On-chain we accept only `b ∈ {0,1}`; **GC proves completeness & correctness** (§8).

assign_leaf    = H("pvugc/merkle/leaf" || enc_u64_be(w) || enc_bool(b))
AssignmentRoot = smt_root({ w → b })     # path is exactly 64 steps (MSB→LSB)

### 2.3 Deterministic state header

doc_hash  = H("pvugc/doc-hash" || circuit_IR || param_json || InputMap)
state_hdr = H("pvugc/statehdr" || doc_hash || enc_u64_be(epoch)
                           || GateRoot || AssignmentRoot)

---

## 3. Canonical TapTree & Funding (deterministic P2TR)

* One TapLeaf **per row** (`row_id` ascending).
* Branch children sorted; dup-last; BIP-341 tagged hashing.
* Internal key: fixed x-only NUMS; **script-path only**.
* Tweak with root → canonical P2TR for `(state_hdr,row_table)`; watchers verify pre-funding.

---

## 4. Row Leaf (consensus)

### 4.1 Leaf constants (embedded)

<const_state_hdr:32>
<const_doc_hash:32> <const_epoch:8>   # needed to recompute state_hdr
<const_GateRoot:32>
<const_AssignmentRoot:32>
<const_row_id:8>
<const_CancelTemplateHash:32>         # CTV template for Stage-1 Cancel parent

*(Finalize leaf separately embeds `<const_FinalizeTemplateHash>`; see §6.)*

### 4.2 Witness (top→…; minimal pushes)

**(A) Gate membership (row binding)**

<row_id_w:8> <gate_type_w:1> <wL_w:8> <wR_w:8> <wO_w:8>
# per Merkle level j (exact Dg steps):
<dirbit_j:1 ∈ {0,1}> <sibling_j:32>

**(B) For each operand i ∈ {L,R,O}: Assignment SMT lookup (exactly 64 steps)**

<key_w_i:8>     # wire id
<val_b_i:1>     # bit in {0x00,0x01}
# for k = 0..63:
<dirbit_k:1 ∈ {0,1}> <sibling_k:32>

*(Note: your earlier 19-byte `"pvugc/wire"||w||b` preimage is **20 bytes**; to avoid size traps we drop it and rebuild leaves from `<key_w_i, val_b_i>`.)*

**(C) Optional operand fence (context binding)**
If used: push `<state_ctx[i]>` (preimage checked to `H_bind[r,i]` in §4.3(2.3)).

### 4.3 Script (straight-line outline)

**(0) Recompute & bind `state_hdr` (anti split-commitment)**

hdr' = H("pvugc/statehdr" || <const_doc_hash> || enc_u64_be(<const_epoch>)
                        || <const_GateRoot> || <const_AssignmentRoot>)
hdr' OP_EQUALVERIFY <const_state_hdr>

**(1) GateRoot membership & row tuple**

* Rebuild `gate_leaf(row_id_w, gate_type_w, wL_w, wR_w, wO_w)`; fold with CAT to `<const_GateRoot>` (consume **exact** path).
* `row_id_w OP_EQUALVERIFY <const_row_id>`; **clamp** `gate_type_w ∈ {0,1}`.
* Keep `(gate_type_w, wL_w, wR_w, wO_w)`.

**(2) Assignment membership & row binding (three operands)**
For each `i ∈ {L,R,O}`:

1. **Clamp** `val_b_i` (size==1; value ∈ {0,1} or fail).
2. `assign_leaf = H("pvugc/merkle/leaf" || <key_w_i> || <val_b_i>)`.
3. **Exactly 64 folds**: each step consumes `(dirbit:1, sibling:32)`; clamp `dirbit ∈ {0,1}`; fold via `"pvugc/merkle/node"`.
4. `OP_EQUALVERIFY` vs `<const_AssignmentRoot>`.
5. **Bind to row:** `key_w_i == wL_w / wR_w / wO_w`.
6. Convert to Script bool: `OP_0NOTEQUAL`. After L,R,O → stack `bL bR bO`.

**(2.3) Optional fence (if enabled)**

H_bind[r,i] = SHA256("pvugc/row/opctx" || <const_state_hdr> || <const_row_id> || enc_u8(i))
SHA256(state_ctx[i]) OP_EQUALVERIFY H_bind[r,i]

*(If unused, omit entirely—don’t leave a dead check.)*

**(3) Predicate-first contradiction**

OP_0NOTEQUAL OP_SWAP OP_0NOTEQUAL OP_SWAP OP_0NOTEQUAL   # normalize bits

OP_DUP 0 OP_NUMEQUAL OP_IF           # AND
  OP_OVER OP_OVER OP_BOOLAND
  OP_SWAP OP_NUMEQUAL
  OP_NOT
OP_ELSE                               # XOR
  OP_OVER OP_OVER OP_ADD 1 OP_NUMEQUAL
  OP_SWAP OP_NUMEQUAL
  OP_NOT
OP_ENDIF
OP_VERIFY                             # must contradict to proceed

**(4) CTV to Stage-1 Cancel parent**

<const_CancelTemplateHash> OP_CHECKTEMPLATEVERIFY

---

## 5. Finalize Leaf (consensus; **CSV-gated** + **RBF-signaling parent**)

<csv_window> OP_CHECKSEQUENCEVERIFY OP_DROP
<const_FinalizeTemplateHash> OP_CHECKTEMPLATEVERIFY

* `csv_window` is **mandatory** (non-zero challenge window).
* Finalize parent’s `nSequence` encodes this CSV and is **committed by CTV** (non-final pre-window).

---

## 6. Exits — Canonical **CTV** Templates (keyless; RBF)

**CTV scope (normative for all Stage-1 parents):** the preimage **MUST commit** to
`nVersion`, `nLockTime`, **input count = 1**, **`nSequence < 0xFFFFFFFF` (opt-in RBF)**, and **all outputs** (value + script bytes, in order).

* **Cancel/Challenge parent:** runs §4 (membership + predicate) then CTV.
* **Finalize parent:** CSV gate then CTV.
* Implementations **SHOULD** ship multiple Stage-1 parent templates at ascending fees (effective now that parents are RBF).

**Liveness guidance:** Each parent SHOULD be **standalone-feerate-sufficient** (not dependent on package relay).

---

## 7. Sizes & Policy

* **Per operand proof:** `(1B dir + 32B sibling) × 64` + constants.
* **Three operands:** low 10s of KB per contradiction.
* **Row script:** ~6–9 KB (impl-dependent).
* **All pushes minimal**; reject non-minimal/trailing bytes.
* **Parents:** opt-in RBF; publish a max parent vsize bound to keep BIP125 replacement deltas practical.

---

## 8. GC Statement (normative, REQUIRED before funding)

**Public inputs:** `(doc_hash, GateRoot, AssignmentRoot, state_hdr, InputMap, ClaimDigest C, {all parent/child CTV template hashes if used off-chain})`

The prover must show:

1. **State/template binding**

* `state_hdr = H("pvugc/statehdr" || doc_hash || enc_u64_be(epoch) || GateRoot || AssignmentRoot)`.
* (If verified off-chain) Parent templates equal the published hashes.

2. **Completeness (no read gaps)**

* For **every** row `(row_id, wL, wR, wO)` in `GateRoot`, the assignment defines `b(wL), b(wR), b(wO) ∈ {0,1}`.

3. **Full circuit correctness**

* For each row:

* `AND`: `b(wO) = b(wL) ∧ b(wR)`
* `XOR`: `b(wO) = b(wL) ⊕ b(wR)`

4. **Public I/O binding**

* `InputMap` designates which wires encode public inputs/outputs.
* Let `IO_bits` be those bits read from the assignment in the order defined by `InputMap`.
* `C = H(InputMap || IO_bits)` (or your app-specific digest defined precisely).

> With (2–4), **false claims force a contradictory row**; a challenger can reveal it and win on-chain.

**Operational requirement:** Funders/watchers **MUST** verify a GC proof satisfying §8 before funding the deterministic P2TR.

---

## 9. Test Vectors (normative)

1. **Header binding:** flip `<const_doc_hash>` / `<const_epoch>` / `<const_GateRoot>` / `<const_AssignmentRoot>` → recompute mismatch → fail.
2. **Gate binding:** mutate any gate field or path → GateRoot check fails; `gate_type ∉ {0,1}` → reject.
3. **SMT depth:** supply ≠64 `(dirbit,sibling)` pairs → fail.
4. **Operand clamp:** `val_b_i` size≠1 or value∉{0,1}` → fail.
5. **Row→wire equality:** `key_w_i` ≠ `wL_w/wR_w/wO_w` → fail.
6. **Predicate table:** all 9 `(bL,bR,bO)` cases behave; only contradictions pass.
7. **CTV parents:** change any committed field (version/locktime/seq/outputs) → CTV rejects.
8. **Finalize CSV:** attempt Finalize pre-CSV → non-final; post-CSV → allowed.
9. **GC enforcement:** missing a row operand (completeness) or wrong output bit (I/O binding) → GC invalid; funding must not proceed.

---

## 10. Conformance Checklist

* **In-leaf `state_hdr` recompute** binds `doc_hash`, `epoch`, `GateRoot`, `AssignmentRoot`.
* **GateRoot membership;** parse & use `(row_id, gate_type, wL, wR, wO)`; **clamp** `gate_type ∈ {0,1}`.
* **Assignment SMT:** exactly **64** folds; `b ∈ {0,1}` on chain; `key_w_i` equals the row’s wire.
* **Optional fences** either enforced exactly or omitted.
* **Predicate-first:** `OP_VERIFY` before CTV.
* **Parents (Cancel & Finalize):** **opt-in RBF** (`nSequence < 0xFFFFFFFF`); Finalize is **CSV-gated**; CTV commits to all required fields.
* **Deterministic TapTree:** canonical order; fixed internal key; script-path only.
* **Pre-funding GC proof:** implementations MUST verify §8.

---

## 11. PVUGC vs BitVM3 (labels/MACs)

| Dimension | **PVUGC (CTV+CAT+GC)** | **BitVM3 (labels+MACs)** |
| --------------------: | --------------------------------------------- | ---------------------------- |
| Operators / pre-sigs | **None** (keyless CTV exits) | Often required |
| Correctness proof | **GC** (full circuit + I/O binding) | GC |
| On-chain authenticity | **CAT-Merkle** `(w,b)` + GateRoot membership | Labels/MACs opened & checked |
| Deterministic funding | **Yes** (canonical P2TR) | Varies |
| Dispute input size | **Low 10s KB** per contradiction | 10s–100s KB |
| Challenge access | **Permissionless** | Permissionless

---

## 12. Summary

This PVUGC keeps **GC for correctness**, uses **CAT** for compact public membership, and **CTV** for keyless, deterministic exits (operator-free). With **GateRoot membership**, **in-leaf `state_hdr` binding**, you get **soundness** (bad claims expose a contradictory row).