Practical Attestation Technique (PAT)¶
The Practical Attestation Technique (PAT) is a Merkle-based post-quantum signature commitment scheme: it commits a batch of n ML-DSA-44 (Dilithium) signatures to a fixed 100-byte on-chain root, regardless of batch size. The signatures themselves remain in witness data, so the 100-byte proof is a constant-size commitment, not a replacement for the signature payload. PAT is patent pending (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 hashing. This produces a single root hash that commits to all signatures in the batch.
2. Rogue-Key Resistant Public Key Aggregation¶
Public keys are aggregated via collision-resistant hashing, preventing rogue-key substitution attacks where an adversary could forge a valid aggregate. The aggregation 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) |
On-Chain Footprint¶
The 100-byte proof is a commitment, not a replacement for the signatures. The signatures are carried in witness data as compact PAT triples (~96 bytes/signature) rather than full 2,420-byte signatures. The realistic end-to-end reduction versus carrying raw signatures inline is roughly constant at ~25× for batches of any meaningful size:
| Batch Size | Raw Signatures (inline) | PAT On-Chain Footprint | End-to-End Reduction |
|---|---|---|---|
| 1 | 2,420 bytes | ~2,520 bytes | ~1× |
| 100 | 242 KB | ~9.7 KB | ~25× |
| 1,024 | 2.4 MB | ~98 KB | ~25× |
The 100-byte root is what is permanently committed at the block level. The ~25× reduction comes from PAT's compact witness encoding and batch verification, not from discarding the signature data. (Commitment size alone is constant at 100 bytes, but that figure should not be read as the on-chain footprint.)
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 patent pending (Soqucoin Labs Inc.). The technique is licensed for use within the Soqucoin blockchain under the MIT license.