Let me assess each approach's viability given the constraints:
1. Breaking linearity: Low likelihood
- The document explicitly states that a pairing-based generalization suffers the same attack
- Any group-homomorphic evaluation structure enables similar linear algebra attacks
- Bitcoin script severely constrains available operations (no pairings, limited field arithmetic)
- Non-linear operations that resist this attack likely can't be verified in Bitcoin script
2. Restricting to tree circuits: Technically viable but practically useless
- Would definitively prevent the attack (no adaptors needed)
- SNARK verifiers require circuits with massive fanout for efficiency
- Converting to tree form causes exponential blowup in circuit size
- Makes the approach impractical for the intended use case
3. Changing algebraic structure: Very low likelihood
- Bitcoin script limitations are severe: essentially only arithmetic and hash functions
- Any alternative algebraic structure must:
- Support efficient evaluation in script
- Resist linear algebra attacks
- Enable garbling
- These constraints appear mutually incompatible
4. Adding randomization barriers: Moderate likelihood (Robin's approach?)
- Can break the deterministic input-output relationship
- Loss of rerandomizability suggests fresh randomness per evaluation
- Key challenge: proving security without the linear reduction argument
- Must ensure randomness can't be eliminated through clever combinations
- Bitcoin script can verify randomized computations via hash commitments
The most promising direction appears to be carefully designed randomization that preserves Bitcoin script compatibility while breaking the linear structure. However, this sacrifices the elegant rerandomizability property that made BitVM3 attractive for multi-party scenarios.
The document's mention of teams working on "alternative schemes" using established CDS primitives suggests a potential fifth approach: abandoning the RSA-based design entirely for modified versions of classical garbling schemes adapted to Bitcoin's constraints.