PRIORITIES_ANALYSIS.md

Miden Recursive Proving: Critical Path Priority Analysis

Analysis Date: 2025-02-11 Repositories Analyzed: 0xMiden/crypto, 0xMiden/miden-vm, 0xMiden/p3-miden Total Issues Analyzed: 200 (45 crypto + 148 VM + 7 p3-miden)

---

Executive Summary

This document tiers all open issues from the 0xMiden/crypto, 0xMiden/miden-vm, and 0xMiden/p3-miden repositories against the critical path priorities for efficient recursive proving in Miden.

Critical Path Priorities (from Bobbinth discussions)

Priority	Description	Target Status
#1	Lifted FRI integration into the VM	Performance improvements, proof size optimization - target: February
#2	Plonky3 quality	Performance and proof sizes in Plonky3 backend
#3	Constraint evaluation and ACE circuit generation	Al's symbolic evaluator for AirBuilder
#4	Precompile VM development	Not yet started - 5 circuits: ECDSA, EDDSA, SHA-512, Keccak, +1

Tier Definitions

• S-tier: Directly critical to Lifted FRI integration, Plonky3 performance/proof sizes, constraint evaluation, or precompile VM
• A-tier: Important for performance/optimization or core processor functionality
• B-tier: Nice-to-have improvements, refactoring, or minor optimizations
• C-tier: Documentation, minor fixes, or low-priority cleanup

---

S-Tier Issues (Directly Critical to Critical Path)

0xMiden/crypto

Issue	Title	Summary	Mapped Priority
#24	Implement ECDSA over ECExt5	Move ECDSA keygen/sign/verify from test to crypto repo for precompile support	Precompile VM (#4)
#676	Add ECDSA signature support over secp256r1 curve	Support Ethereum Fusaka's secp256r1 precompile for hardware wallets	Precompile VM (#4)
#675	Implement canonical Falcon512 signature	Falcon512_Sha512 wrappers for Miden VM precompile support	Precompile VM (#4)
#659	Switch to Sponge2‑Style AEAD	AO-friendly construction reduces constraints in proof systems	Plonky3 quality (#2)
#771	Unified Felt type for on-chain/off-chain	Single field type across Rust and MASM for precompile circuits	Precompile VM (#4)
#732	Packed field operations for hash functions	SIMD acceleration for Poseidon2 via AVX2/AVX-512	Plonky3 quality (#2)
#802	Add validation to PartialMmr deserialization	Security/correctness fix for MMR operations	System reliability

0xMiden/miden-vm

Issue	Title	Summary	Mapped Priority
#2515	Proof size increase after migration to P3	300KB vs 100KB target - batching Merkle paths shows 30% reduction	Plonky3 quality (#2)
#2509	Restore AIR constraints using AirScript with P3	AirScript integration needed for Plonky3 backend	Constraint evaluation (#3)
#2508	FRI Domain Changes for Winterfell → P3	Domain changes for recursive verifier	Lifted FRI (#1)
#2518	Higher arity folding factors	Arity-8 enables 100KB proofs vs 195KB with arity-2	Plonky3 quality (#2)
#2342	Mock recursive verifier in stdlib	Precompile VM proof validation architecture	Precompile VM (#4)
#2282	Separate precompile crate	Foundational architecture for 5 precompile circuits	Precompile VM (#4)
#2389	Element-reads for HORNEREXT	AIR constraint decision affecting memory chiplet	Constraint evaluation (#3)
#2220	Alternative for hasher sibling table	AIR constraint optimization via clock-based nonce	Constraint evaluation (#3)
#2062	u32 operations' inputs not range checked	Fundamental AIR/constraint soundness issue	Constraint evaluation (#3)
#1559	Arithmetizing Keccak-p permutation	Keccak precompile AIR design (89,640 cycles)	Precompile VM (#4)
#1614	Element-addressable memory follow-up	32-bit range checks with ACE chiplet implications	Constraint evaluation (#3)
#1388	Refactor multiset checks	LogUp-GKR transition with Winterfell/P3 compatibility	Constraint evaluation (#3)
#1687	Evaluate offline memory argument	SP1-style bus construction for trace reduction	Constraint evaluation (#3)
#1182	Virtual Bus proposal	GKR protocol for sums of fractions, core AIR infrastructure	Constraint evaluation (#3)
#1185	Multiset running product column shift	Lagrange kernel transition constraints foundations	Constraint evaluation (#3)

S-Tier Count: 23 total (7 crypto + 14 VM + 2 p3-miden)

---

A-Tier Issues (Important for Performance/Core Functionality)

0xMiden/crypto

Issue	Title	Summary	Rationale
#799	Update RPO benchmarks	Re-run benchmarks post-Plonky3 migration	Performance baselines
#739	Update hash benchmarks	Target platforms: Apple Silicon, Graviton 4, Zen5	Performance measurement
#300	SimpleSmt insertion optimization	Avoid recomputing inner node hashes on bulk insert	Merkle performance
#339	Sparse Merkle subtree optimization	SMT hashing 4x slower than balanced trees	Merkle performance
#693	PartialMmr panic bug	Client stability issue (miden-client)	Production reliability
#593	Zeroizing deserialization reader	Security for sensitive key material	Security hygiene

0xMiden/miden-vm

Issue	Title	Summary	Rationale
#2486	Minimal trace length with p3-miden-fri	Enable optimization with lifted FRI	Plonky3 performance
#2521	Multiple security levels in P3	96-bit vs 128-bit for proof size reduction	Plonky3 proof size
#2661	Optimize HasherOp cloning	1.3x to 2.3x speedup by avoiding Vec clones	Processor performance
#2621	Specify calling conventions/ABIs	WebAssembly Canonical ABI, miden-exec, miden-call	Precompile interop
#2163	Parallel trace generation improvements	Tracking issue post-#1839	Prover throughput
#1763	Row-major trace generation	35-50% execution improvements proven	Cache performance
#1743	Trampoline-based dispatch	Computed goto for opcode handling	Branch prediction
#2276	FastProcessor memory write soundness	Multiple writes in same cycle is unsound	Soundness fix
#2292	MastForest TypeState deserialization	Robust serialization for distributed proving	Allocation safety
#2252	TraceGenerationContext serialization	Distributed proof generation foundation	Parallel proving
#2433	Improve in-VM AEAD	Sponge2 padding, associated data support	Crypto primitives
#1537	Non-empty stack overflow table	Reduce trace rows, save unnecessary population	Trace optimization
#1523	DYN: don't issue hash request	Save 8 hasher chiplet rows per DYN	Trace optimization
#1518	Kernel ROM to lookup table	Simplify recursive verifier via LogUp	Recursive verifier

A-Tier Count: 35 total (6 crypto + 27 VM + 2 p3-miden)

---

S-Tier Issues (Directly Critical to Critical Path)

0xMiden/p3-miden

Issue	Title	Summary	Mapped Priority
#4	Lifted FRI	Port Lifted FRI from 0xMiden Plonky3 fork to p3-miden repository	Lifted FRI (#1)
#6	Port aux boundary value handling	Enable air-script to target p3-miden (hard dependency)	Constraint evaluation (#3)

---

A-Tier Issues (Important for Performance/Core Functionality)

0xMiden/p3-miden

Issue	Title	Summary	Rationale
#5	Implement Security Level Estimator	Port security level estimator for proper FRI parameter selection	Parameter optimization
#12	Avoid allocations in quotient computation	Use FlatMatrixView to optimize prover hot path	Prover performance
#13	Parallelize quotient domain point collection	Use Plonky3's collect_n for parallelization	Prover performance

---

B-Tier Issues (Nice-to-Have Improvements)

0xMiden/p3-miden

Issue	Title	Summary
#11	Refactor: separate Airs for main/aux constraints	Simplification over AirWithBoundaryConstraints wrapper
#14	Improve structuring of periodic_table() return value	API improvement with validation (requires upstream Plonky3 change)

---

B-Tier Issues (Nice-to-Have Improvements)

0xMiden/crypto

Issue	Title	Summary
#809	Remove RandomCoin-s	Post-Plonky3 cleanup
#785	Compact Subtree storage	LargeSmt I/O optimization
#746	Optimize PartialSmt serialization	FPI API efficiency
#738	Expand Stark re-exports	API organization
#725	Decide RPO/RPX removal	Architectural decision
#678	PartialMmr::open() consistency	API consistency
#722	Refactor random samplers	Test infrastructure
#717	Const blake3 implementation	Compile-time optimization
#571	AlgebraicSponge from iterators	Hash API improvement
#518	Optimize LargeSmt Subtree	Bitmask + Vec representation
#527	Alternative subtree layout	I/O size investigation
#520	Smt/LargeSmt code duplication	Technical debt
#510	Remove Hc128Rng	Dependency cleanup
#472	Falcon key-recovery mode	15% signature size reduction
#376	Revisit Falcon implementation	rust-fn-dsa evaluation
#288	Smt generic over AsRef	miden-node UX

0xMiden/miden-vm

Issue	Title	Summary
#2657	Remove redundant clones	Minor allocation reduction
#2645	Move Processor methods to *Interface	Code organization
#2644	Remove NodeFlags from NodeEndData	Tracer simplification
#2641	Make core::math little-endian	Standardization completion
#2636	Remove Tracer methods except start/finalize	Semantic simplification
#2633	Remove execute_end_of_block_decorators	Decorator model simplification
#2620	Processor decorator immutability	API correctness
#2619	Complete math::u128 module	Stdlib completion
#2594	AssemblyOp decorators for JoinNode	Diagnostic quality
#2578	Operation index in system event errors	Error precision
#2577	Consolidate error variants	Error type simplification
#2576	Reduce stack footprint for errors	Stack usage
#2574	VecDeque for stack representation	Performance investigation
#2572	Remove push.a.b.c.d syntax	Language simplification
#2570	Remove reversew/mem_{store,load}w_be	Endianness cleanup
#2566	Advice map AST alignment	Code organization
#2565	Convenience instructions for adv stack	Programmer convenience
#2557	Introduce AdviceStack type	Core refactoring
#2552	Remove execute_sync()	API cleanup
#2550	Replace bincode with wincode	Blocked on #2515
#2501	Processor sync APIs	API design decision
#2504	get_size_hint for MastForest	Performance optimization
#2500	Constants in adv_map	Programmer convenience
#2495	Reorganize processor modules	Post-Process removal cleanup
#2473	Simplify MastForestBuilder	Fingerprint-based approach
#2454	hash_string_to_word as const fn	Compilation performance
#2417	PackageKind vs MastArtifact consistency	Code correctness
#2411	Remove Owned DecoratorStorage	Frontend TODO (low priority)
#2359	Smart copy for std::mem	Memory optimization
#2358	MastNode equality comparison	Code quality
#2355	Constants in recursive verifier	Minor cleanup
#2347	Element index for dupw	API improvement (breaking change)
#2341	Executable MastForest with Arbitrary	Fuzzing infrastructure
#2337	Don't assume valid inputs in build_trace	Distributed proving
#2319	smt::set multiple pairs optimization	SMT performance
#2256	Improve benchmarks	Infrastructure
#2250	HasherOp basic block handling	Performance optimization
#2241	debug.adv_map	Debug utility
#2222	EventHandlerRegister return	API ergonomics
#2221	Document constants with insta	Documentation
#2128	TraceFragmentContext.continuation replay	Fragment optimization
#2045	RFC: Recursive verification API	Design work
#1949	Cache MastForest sets	Performance optimization
#1918	Document recursive verifier advice layout	Documentation
#1891	Statically-link used AdviceMap	Memory optimization
#1962	Serde vs winterfell Serializable	Technical debt
#1871	Syscall index instead of MastNodeId	API stability
#1779	Rename ChipletsVTableColBuilder	Reflects bus architecture
#2109	Simplify basic block nodes	Processor efficiency
#1701	Fast processor improvements	Tracking issue
#1700	Append-only AdviceMap	Performance optimization
#1684	Do-while loops	Language ergonomics
#1672	Falcon norm polynomial s2	Post-quantum optimization
#1624	Miden Component Model MVP	Major architectural proposal
#1538	Refactor decoder control blocks	Code quality
#1356	Detect invalid stack access	Safety feature
#1308	MASM test runner	Developer productivity
#1278	Cargo.toml formatter	Tooling
#1220	adv.push_smtset/smtget	Convenience
#1210	Isolate Advice Provider by context	Security
#1202	BTreeMap for AuxColumnBuilder	Performance investigation
#1092	Restrict DYN operation	Security discussion
#1025	Read parent memory instructions	Core functionality
#948	Better caller instruction	Core functionality
#798	while.exec. syntax	Language ergonomics
#772	Procedure stack consumption	Static analysis
#642	Drop multiple elements	Language feature
#633	Additional integer representations	Language ergonomics
#519	Named breaks	Control flow
#297	Procedures with const parameters	Compile-time optimization
#249	RLP decode for stdlib	Ethereum compatibility
#218	u32 error type change	Error reporting

B-Tier Count: 96 total (16 crypto + 78 VM + 2 p3-miden)

---

C-Tier Issues (Documentation, Minor Fixes)

0xMiden/p3-miden

No C-tier issues identified in p3-miden.

0xMiden/crypto

Issue	Title	Summary
#806	Embed signature scheme in commitments	Exploratory design
#768	Generate RPO hash test vectors	Test infrastructure (may deprecate)
#758	Blake3-192 tracking	External dependency
#742	Remove LexicographicWord	Deferred (maintainers want to keep)
#733	Const Word::is_empty()	Blocked on P3, may not be feasible
#579	Send + Sync for FeltRng	Trait vs struct confusion
#314	Tracing for expensive operations	Debug instrumentation
#294	Falcon math module docs	Documentation
#284	Miden crypto documentation	Documentation
#255	deny(missing_docs)	Documentation enforcement
#253	ValuePath generic over leaf	Refactoring
#247	Replace MerkleError	Code quality
#233	Handle assert in merkle path	Code quality
#591	Partial SMTs in SmtForest	Feature enhancement
#670	PersistentSmtForest	Major feature effort
#353	Rename RPO-STARK signature	Naming

0xMiden/miden-vm

Issue	Title	Summary
#2668	Missing #[repr(u8)] on ConstantOp	Soundness (stable in practice)
#2666	Add hasher module docs	Documentation
#2663	Update README benchmarks	Documentation
#2660	Outdated mdBook references	Documentation cleanup
#2640	Include source files in debug info	Low priority
#2628	Hashless MastForest format	On hold (savings insufficient)
#2611	Fix prover log padding message	Diagnostic fix
#2610	Update root README	Documentation
#2601	Merge TestConsistencyHost and TestHost	Test cleanup
#2531	Populate .debug_functions at assembly	Debug info
#2511	Document FRI E2F4 snapshot tests	Documentation (on hold)
#2506	Fix NDIs operators formatting	Documentation
#2490	Reimplement miden repl	Tooling
#2489	Reimplement miden analyze	Tooling
#2434	Sponge2 padding (MASM)	Sub-issue of #2433
#2390	Disallow same (ctx,adr,clk) memory ops	Soundness investigation
#2388	Update HORNEREXT diagram	Documentation
#2256	Improve benchmarks	Infrastructure
#2241	debug.adv_map	Debug utility
#2221	Document constants with insta	Documentation
#1737	Capped Merkle tree for RV	Infrastructure
#1714	AssemblyOp::location dangling	Debug UX
#1713	Stack traces on error	Debug UX
#1698	TOML CLI input format	UX
#1693	Improve error messages	Debug UX
#1697	Add u256 div procedure	Library addition
#1655	AdviceMap testing	Testing
#1625	Operation trace	Debug tooling
#1618	Unit tests for private procedures	Testing
#1479	Pedantic warning mode	Tooling
#1469	MASM Linter	Tooling
#1919	miden-project.toml manifest	Developer experience
#1901	MASM parser CST rewrite	Tooling foundation
#1900	LSP and DAP servers	Tooling
#2061	Track called procedures	Potential duplicate
#2021	build_test stack order inconsistency	Test infrastructure
#1930	Rust crate re-exports	Code quality
#1890	Remove ParseOptions	Deferred on #1919
#1780	Generalize bus debugger	Tooling
#1774	Reinstate package tests	Test coverage
#1749	sdepth semantics	UX/documentation
#296	Stdlib documentation improvements	Documentation
#1330	Change constant values pre-execution	Test infrastructure
#699	Miden Debugger docs + logic	Documentation

C-Tier Count: 67 total (16 crypto + 51 VM + 0 p3-miden)

---

Critical Path Items Not Broken Down into Issues

Based on the analysis, the following priorities from Bobbinth's list are NOT adequately broken down into GitHub issues:

1. Al's Symbolic Evaluator for AirBuilder (Priority #3)

The constraint evaluation critical path mentions "Al's symbolic evaluator for AirBuilder" as nearly complete, but there is no dedicated issue tracking this work. This is foundational to the ACE circuit generation effort.

Recommendation: Create a tracking issue for the symbolic evaluator with:

• Integration status with AirScript
• Plonky3 backend compatibility
• Timeline for completion
• Dependencies on existing issues (#2509, #2220, #2062)

2. Lifted FRI Integration into VM (Priority #1)

While there are related issues (#2508, #2486, #2518), there is no comprehensive tracking issue for the full Lifted FRI integration effort including:

• Performance improvements (current performance worse than previous version per Bobbinth)
• Proof size optimization (memoized Merkle tree algorithm)
• February target milestone tracking

Recommendation: Create a milestone/tracking issue linking all Lifted FRI subtasks.

3. Precompile VM Specification (Priority #4)

The "Precompile VM development" is mentioned as "not yet started" but there is no RFC or specification issue defining:

• Complete set of required precompiles (ECDSA, EDDSA, SHA-512, Keccak, +1 mystery circuit)
• Precompile VM architecture
• Integration with MASM
• Testing strategy

Recommendation: Create an RFC issue for Precompile VM design before implementation.

4. Plonky3 Performance Baseline (Priority #2)

While proof size issues are tracked (#2515), there is no comprehensive performance benchmarking issue tracking:

• Prover time baselines
• Memory usage profiling
• Comparison with Winterfell
• Target metrics

Recommendation: Create a performance tracking issue with specific benchmarks.

---

Summary Statistics

Tier	Crypto	VM	p3-miden	Total
S-tier	7	14	2	23
A-tier	6	27	2	35
B-tier	16	78	2	96
C-tier	16	51	0	67
Total	45	170	6	221

Critical Path Mapping

Priority	S-tier Issues	A-tier Issues
#1 Lifted FRI	#2508, #2518, p3-miden#4	#2486, #2163, #1763, p3-miden#12, p3-miden#13
#2 Plonky3 Quality	#2515, #732, #659	#2521, #799, #739, p3-miden#5
#3 Constraints/ACE	#2509, #2389, #2220, #2062, #1559, #1614, #1388, #1687, #1182, #1185, p3-miden#6	#1518, #1701
#4 Precompile VM	#24, #676, #675, #771, #2342, #2282, #1559	#2621, #2276

---

Recommendations

Immediate Actions (S-tier)

1. Lifted FRI Foundation: Complete p3-miden#4 (Lifted FRI port) and p3-miden#6 (aux boundary handling) - these are blocking February target
2. Plonky3 Proof Size: Address #2515 as highest priority - 138KB vs 100KB gap is blocking production
3. Constraint Restoration: #2509 (AirScript with Plonky3) enables full constraint evaluation pipeline
4. Precompile Foundation: Complete #771 (Unified Felt) and #2282 (separate precompile crate) before starting precompile implementations
5. Keccak Precompile: #1559 has extensive design discussion - ready for implementation

High-Priority Follow-ups (A-tier)

1. p3-miden prover optimizations: p3-miden#12 (avoid allocations), p3-miden#13 (parallelize quotient domain) - quick wins
2. p3-miden security: p3-miden#5 (Security Level Estimator) for proper parameter selection
3. VM performance: #2661 (2.3x speedup), #1763 (35-50% improvement), #1743 (trampoline dispatch)
4. Distributed proving: #2292, #2252 enable parallel trace generation
5. Soundness fixes: #2276 (FastProcessor memory writes)

Create Missing Issues

1. RFC: Precompile VM Architecture and Specification
2. Milestone: Lifted FRI Integration (target February) - track p3-miden#4, p3-miden#6, #2508, #2518
3. Tracking: Al's Symbolic Evaluator for AirBuilder
4. Performance: Plonky3 Prover Time Baseline and Targets

---

Key Insight: p3-miden is the Critical Path

Unlike crypto and miden-vm which have many issues across all tiers, p3-miden's issue set is overwhelmingly high-priority:

• 2 of 7 issues are S-tier (29% - highest ratio of any repo)
• 3 of 7 issues are A-tier (43%)
• 0 C-tier issues - every open issue in p3-miden matters

This reflects p3-miden's role as the Plonky3 integration layer - it is the critical path itself. The top two issues:

• p3-miden#4 (Lifted FRI) - The core feature enabling Priority #1
• p3-miden#6 (aux boundary handling) - Hard dependency for air-script integration (Priority #3)

These are blocking the February Lifted FRI target.