Sign with SHRIMPS in Rust. Verify in Cairo. Prove with Stwo STARK.
Post-quantum signature verification with 772-byte compact signatures and zero-knowledge proofs.
Pipeline kickoff with SHRIMPS parameters and keypair |
Rust & Cairo tests pass, signature verification begins |
Stwo STARK proof generation with prover trace logs |
All verifications passed — proof generated in ~91s |
flowchart LR
subgraph Rust["Rust Signer"]
KG[keygen] --> SIGN[sign]
SIGN --> TV["Test Vectors\n(JSON)"]
end
subgraph Python["Python Converter"]
TV --> CONV["convert_vectors.py"]
end
subgraph Cairo["Cairo Verifier"]
CONV --> |"Flat u32 hex"| BATCH["Batch Verify\n(lib.cairo)"]
BATCH --> WOTS["WOTS+ Chain\nCompletion"]
BATCH --> MERK["Merkle Path\nVerification"]
BATCH --> SHA["SHA-256\n(native Cairo)"]
end
subgraph Stwo["Stwo Prover"]
BATCH --> PROOF["STARK Proof"]
end
style Rust fill:#f4a460,color:#000
style Cairo fill:#9370db,color:#fff
style Stwo fill:#3cb371,color:#fff
style Python fill:#4682b4,color:#fff
1. Clone and run the full pipeline
git clone https://github.com/abdelstark/pq-provable-shrimps.git
cd pq-provable-shrimps
make all2. Or step through individually
make sign # Rust signer generates test vectors → test_vectors/shrimps_compact.json
make vectors # Python converts to Cairo batch format → test_vectors/cairo_input.json
make execute # Cairo verifies all signatures (no proof)Expected output:
Run completed successfully, returning []
3. Generate a STARK proof (optional)
make install-stwo # One-time: install stwo_run_and_prove (requires nightly Rust)
make prove # Generate and verify a Stwo STARK proofSHRIMPS is a compact SPHINCS+ variant combining two instances under one public key:
PK = SHA256(pk_seed || compact_root || pk_seed || fallback_root)
Each signature uses a one-time WOTS+ key inside a Merkle tree. Verification reconstructs the public key from the signature and checks it matches.
Message ──► SHA-256 ──► WOTS+ Chain Completion ──► Leaf PK ──► Merkle Root ──► PK Reconstruction ──► Match?
│ (270 steps avg) │ (12 levels)
└──── Domain-separated (ChainAdrs) ─────┘
| Parameter | Value | Effect |
|---|---|---|
n |
16 bytes | 128-bit post-quantum security |
w |
16 | 4-bit Winternitz digits, max 15 chain steps |
h |
12 | 4096 one-time key leaves |
d |
1 | Single Merkle tree (no hypertree) |
| Signature | 772 bytes | 10x smaller than SLH-DSA-SHA2-128s (7,856 B) |
| Verification | ~285 SHA-256 | 270 WOTS+ + 12 Merkle + 3 misc |
make signer-test # 26 integration + 7 property + 5 state tracker tests
make bench # Criterion benchmarks (keygen, sign, verify, wots_pk_from_sig)The Cairo entry point verifies multiple signatures in a single execution. Convert all valid test vectors to batch format:
make vectors # Batch mode: all valid vectors
make execute # Verify all in one Cairo runpython3 scripts/convert_vectors.py test_vectors/shrimps_compact.json 0 # Single vector (index 0)make run-tui # Launch the Go-based terminal dashboardpq-provable-shrimps/
├── signer/ Rust SHRIMPS (keygen, sign, verify)
│ ├── src/
│ │ ├── shrimps.rs Top-level API
│ │ ├── wots.rs WOTS+ chains
│ │ ├── merkle.rs Merkle tree
│ │ ├── hash.rs SHA-256 + domain separation
│ │ └── main.rs CLI test vector generator
│ ├── tests/ 26 integration + 7 property tests
│ └── benches/ Criterion benchmarks
│
├── packages/shrimps/ Cairo verifier (mirrors Rust module-for-module)
│ └── src/
│ ├── lib.cairo Batch verify entry point (#[executable])
│ ├── verify.cairo Signature verification logic
│ ├── wots.cairo WOTS+ chain completion
│ ├── merkle.cairo Merkle path verification
│ ├── sha256.cairo SHA-256 (native Cairo, from s2morrow)
│ └── hash.cairo Domain-separated hashing
│
├── tui/ Interactive TUI dashboard (Go + Charm)
├── scripts/ Python test vector converter
├── test_vectors/ Generated JSON test data
└── Makefile Build, test, convert, execute, prove
| Target | Description |
|---|---|
make all |
Full pipeline: Rust tests + Cairo batch verification |
make sign |
Generate test vectors with Rust signer |
make vectors |
Convert all valid vectors to batch Cairo format |
make build |
Build Cairo package |
make execute |
Run Cairo batch verification (no proof) |
make prove |
Generate Stwo STARK proof |
make signer-test |
Rust unit + integration tests |
make cairo-test |
Cairo unit tests |
make bench |
Criterion benchmarks |
make run-tui |
Launch interactive TUI |
make install-stwo |
Install Stwo prover (nightly Rust) |
make clean |
Remove build artifacts |
| Parameter | Value | Description |
|---|---|---|
channel_hash |
blake2s |
Hash function for FRI channel |
pow_bits |
26 |
Proof-of-work difficulty |
log_blowup_factor |
1 |
FRI blowup (2x) |
n_queries |
70 |
Number of FRI queries |
- SHRIMPS (Delving Bitcoin)
- SHRINCS (Delving Bitcoin)
- Hash-based Signature Schemes for Bitcoin (ePrint 2025/2203) -- Kudinov & Nick
- starkware-bitcoin/s2morrow -- SHA-256 in Cairo, Stwo prover integration
- feltroidprime/s2morrow -- Falcon-512 in Cairo