Practical Attestation Technique (PAT)¶
The Practical Attestation Technique (PAT) is a Merkle-based post-quantum signature commitment scheme that compresses n ML-DSA-44 (Dilithium) signatures into a fixed 100-byte proof, regardless of batch size. PAT is protected under U.S. Provisional Patent Application No. 64/022,954 (Soqucoin Labs Inc.).
The Problem¶
ML-DSA-44 signatures are 2,420 bytes each — 37× larger than Bitcoin's 65-byte ECDSA signatures. A block with 2,000 transactions would require ~4.84 MB for signatures alone, severely impacting throughput, storage, and propagation latency.
No prior system combines post-quantum security with efficient aggregation and consensus-level on-chain verification.
How PAT Works¶
PAT produces a fixed-size 100-byte proof through three innovations:
1. Merkle-Based Signature Commitment¶
Each (signature, public key, message) tuple is committed as a leaf node in a complete binary Merkle tree using domain-separated SHA3-256 hashing:
LeafHash(i, sig, pk, msg) = SHA3-256(0x00 || i_le32 || sig || pk || msg)
NodeHash(left, right) = SHA3-256(0x01 || left || right)
0x00prefix = leaf node (prevents second-preimage attacks)0x01prefix = internal node- Canonical ordering by
SHA3-256(message)ensures deterministic proofs
2. Rogue-Key Resistant Public Key Aggregation¶
Public keys are aggregated via collision-resistant hashing (not XOR):
This prevents rogue-key substitution attacks where an adversary computes pk_rogue = pk_target ⊕ pk_honest. SHA3-256 is non-linear — algebraic manipulation is infeasible.
3. Consensus-Level Verification (OP_CHECKPATAGG)¶
PAT proofs are validated directly in the script execution engine via a dedicated opcode:
Supports two modes:
| Mode | Operation | Use Case |
|---|---|---|
| Full | Rebuild Merkle tree, verify all 3 commitments | Independent validation |
| Simple | Compare commitments against proof fields | Trusted prover (block producer) |
Proof Structure¶
The PAT proof is exactly 100 bytes, constant regardless of batch size:
| Offset | Size | Field | Description |
|---|---|---|---|
| 0 | 32 | merkle_root |
Root of Merkle tree over (sig, pk, msg) tuples |
| 32 | 32 | pk_agg |
SHA3-256 hash aggregation of all public keys |
| 64 | 32 | msg_root |
SHA3-256 hash of concatenated messages |
| 96 | 4 | count |
Number of signatures (uint32, little-endian) |
Compression Ratio¶
| Batch Size | Raw Signatures | PAT Proof | Compression |
|---|---|---|---|
| 1 | 2,420 bytes | 100 bytes | 24:1 |
| 100 | 242 KB | 100 bytes | 2,420:1 |
| 1,024 | 2.4 MB | 100 bytes | 9,661:1 |
| 1,048,576 | 2.4 GB | 100 bytes | 24,780,800:1 |
Performance¶
| Operation | Complexity |
|---|---|
| Proof creation | O(n log n) |
| Full verification | O(n) |
| Simple verification | O(1) |
| Proof size | O(1) — always 100 bytes |
Security Properties¶
- Post-quantum safe — all operations use SHA3-256 and ML-DSA-44
- Rogue-key resistant — hash-based aggregation prevents key substitution
- Replay resistant — canonical ordering + message binding
- Tamper-evident — independent Merkle root and message root commitments (defense-in-depth)
Patent Status
PAT is protected under U.S. Provisional Patent No. 64/022,954, assigned to Soqucoin Labs Inc. The technique is licensed for use within the Soqucoin blockchain under the MIT license.