Randomizable / Randomized distinction

[hdevalence]

I'm trying to update the R1CS benchmark code for #277 and I'm a bit confused by the Randomized / Randomizable distinction introduced in #268, #270.

The documentation for RandomizableConstraintSystem says

Gadgets that do not use randomization should use trait bound CS: ConstraintSystem, while gadgets that need randomization should use trait bound CS: RandomizedConstraintSystem. Gadgets generally should not use this trait as a bound on the CS argument: it should be used by the higher-order protocol that composes gadgets together.

But the RandomizableConstraintSystem trait is the one with the specify_randomized_constraints, so aren't gadgets that need randomization forced to use the "able" trait, not the "ized" trait?

[oleganza]

I'll try to clarify, but by all means do not consider this an apology for the current design. I hope to find a better name/structure for these things.

If you look into implementation of Shuffle gadgets in Spacesuit, the gadgets are composed as follows:

padded_shuffle(value_shuffle(scalar_shuffle))

The trait bounds for these gadgets are:

padded_shuffle<CS: RandomizableConstraintSystem>
 value_shuffle<CS: RandomizableConstraintSystem>
scalar_shuffle<CS: RandomizedConstraintSystem>

Rationale:

1. Padded Shuffle does not use challenges, but needs to be composed with the Value Shuffle, so it uses the same trait bound as Value Shuffle. Upstream Cloak gadget uses RandomizableCS trait bound for the same reason.
2. Scalar Shuffle uses challenges, but also wants to be composable with various input types (such as Value tuples). Therefore, it uses RandomizedCS bound and defers to the upstream code to provide an already randomized CS. It also requires the upstream code to guarantee soundness of the inputs (meaning, guarantee that the inputs cannot be freely chosen after the challenge is computed).
3. Value Shuffle uses challenges, and does not want to be composable with other challenge-using gadgets, so it can guarantee soundness of the inputs all by itself. It does so by using RandomizableCS bound and calling specify_randomized_constraints itself. This way, all input variables are guaranteed to be committed before challenges are generated. Users of Value Shuffle then do not have to worry whether the inputs are low-level or high-level variables, and type system makes it impossible to accidentally use Value Shuffle inside already randomized CS because we intentionally do not implement RandomizedCS trait (2nd-phase) for RandomizableCS (1st-phase).