Hybrid method for random access/conditional selection from 2^k values

[mmagician]

Description

Create O(sqrt(n)) instead of O(n) constraints as per https://github.com/mir-protocol/r1cs-workshop/blob/master/workshop.pdf.

By trying to make this as generic as possible, I had to add two extra methods on the trait, which for now are only implemented for FpVar for testing. @arkworks-rs/maintainers do you see a way to NOT introduce these extra methods? I tried adding a trait bound for AllocVar to CondSelectGadget, but going down that rabbit hole hasn't worked so far.

Benches:

for k=7, 2^7=128 values

1. Repeated-selection 5.1, O(n):

• expecting2^(k-1) - 1 constraints

  cond_select takes: 63 constraints, 347 non-zeros

2. Hybrid method 5.3, O(sqrt(n)):
   • expect 2^m + 2^l - l - 2 constraints
   • m = k/2 = 3; l = 4; 2^3 + 2^4 - 4 - 2 = 18

cond_select takes: 18 constraints, 184 non-zeros

as expected.

closes: #118

---

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [ ] Targeted PR against correct branch (master)
• [ ] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests
• [ ] Updated relevant documentation in the code
• [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [ ] Re-reviewed Files changed in the Github PR explorer

[mmagician]

The selection methods should be generic. I don't know yet how the implementation would look for EC points, where I can't just get a single underlying value F. Possibly I'll need to adapt the interface or generic impl.

[mmagician]

@Pratyush I couldn't find an intuitive interface for abstracting away the repeated part of the logic, so in the end I've followed your suggestion and have default implementation use the repeated-selection method. My best attempt is here, but then even I quickly get lost in what the method is supposed to be doing 🤣 I've implemented the improved version for:

• Boolean & AllocatedBool
• FpVar & AllocatedFp
• ProjectiveVar

I've benched some of the new ones too: before:

FpVar_select takes: 63 constraints, 347 non-zeros
Boolean_select takes: 56 constraints, 260 non-zeros
SWProjective_select takes: 189 constraints, 945 non-zeros

after:

FpVar_select takes: 18 constraints, 184 non-zeros
Boolean_select takes: 22 constraints, 130 non-zeros
SWProjective_select takes: 54 constraints, 428 non-zeros

[mmagician]

Also @dlubarov @bpfarmer in case you're interested in having a look at this implementation based on your workshop doc.

[Pratyush]

@mmagician Do you have recommendations on how I should go about reviewing the PR?

[mmagician]

@Pratyush I can share my circom reference impl with you and maybe we can go through this PR during the maintainers' call next week?

[Pratyush]

Sure!