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

mmagician · 2023-05-04T18:08:12Z

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

Repeated-selection 5.1, O(n):

expecting2^(k-1) - 1 constraints

cond_select takes: 63 constraints, 347 non-zeros

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

at the cost of introducing two extra methods on the implementers

Pratyush

Leaving an initial review for the time being, but if the selection methods are not generic, maybe we can add the methods to FpVar as inherent methods for the time being?

Pratyush · 2023-05-04T21:08:56Z

src/fields/fp/mod.rs

+    fn allocate_to_lc(
+        var: Variable,
+        val: &Self,
+        cs: &ConstraintSystemRef<F>,
+    ) -> Result<Self, SynthesisError> {
+        let v = val.value()?;
+        Ok(AllocatedFp::new(Some(v), var, cs.clone()).into())


Hm not sure what this method is doing; is it just a clone of the variable?

There's a chance I'm doing something wrong here. The way I understand it is that I have an LC that corresponds to some Variable in the constraint system, and I need to fix it to some value. But I need to retrieve something of type Self (CondSelectGadget) that is equal to that LC, since the repeated_selection sub-routine (which used to be the main routine before this PR) operates on CondSelectGadget elements.

Perhaps the method name isn't great... what I thought of doing was, as mentioned in the PR description, adding a trait bound for AllocVar so that I could call AllocVar>::new_variable, but I'm not really sure of how to do this.

Pratyush · 2023-05-04T21:09:31Z

src/fields/fp/mod.rs

+    fn add_lc(
+        val: &Self,
+        lc: &LinearCombination<F>,
+    ) -> Result<LinearCombination<F>, SynthesisError> {
+        let root: LinearCombination<F> = LinearCombination::zero();
+        let v = val.value()?;
+        Ok(root + (v, lc))


Why doesn't it suffice to just use addition on FpVar?

I simplified this slightly.

mmagician · 2023-05-04T22:10:54Z

src/fields/fp/mod.rs

+        lc: LinearCombination<F>,
+    ) -> Result<LinearCombination<F>, SynthesisError> {
+        let v = val.value()?;
+        Ok(lc * v)


I'm not sure what this method will look like for ECVar points.

mmagician · 2023-05-04T22:12:24Z

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.

call it `hybrid_selection`

fmt update docs

…s_of_two`

mmagician · 2023-05-09T01:59:15Z

@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 · 2023-05-09T02:44:06Z

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

Pratyush · 2023-05-17T15:35:03Z

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

mmagician · 2023-05-17T15:49:55Z

@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 · 2023-05-17T15:52:49Z

Sure!

mmagician added 15 commits May 1, 2023 21:42

merge_imports rustfmt option is deprecated

39c111e

fmt

e5291a0

Add an extra test for conditionally selecting an FpVar

c0e6ca2

move the Repeated Selection method logic to its own fn

6c93fb6

start the implementation of SumOfConditions method

3e817f2

update trait doc: we allow for selecting between many values, not just 2

e7db1c0

Implement sum of conditions helper method

e60df9d

override condionally_select_power_of_two_vector for FpVar

d9dd651

make count_ones a local function inside sum_of_conditions

f5617fa

Make conditionally_select_power_of_two_vector generic

80dfddf

at the cost of introducing two extra methods on the implementers

replace usage of FpVar<F> with Self in FpVar's allocate_vars fn

aff5fe0

replace unwraps with error propagation

bd5eb43

place the bulk of the allocat_vars logic in a standalone generic fn

0952ab0

temp: add bench for cond_select for FpVar

995463f

format links

db7b97d

Pratyush approved these changes May 4, 2023

View reviewed changes

mmagician added 3 commits May 4, 2023 16:07

simplify add_lc for FpVar

f7e8abc

rename fn to allocate_with_value

d5f3a34

remove dead code

6939d3f

mmagician commented May 4, 2023

View reviewed changes

mmagician added 9 commits May 8, 2023 17:25

combine type-specific logic from two new trait methods into one

1ea679d

call it `hybrid_selection`

Add some initial docs for hybrid selection method

760b045

fmt update docs

implement hybrid selection for AllocatedBool and Boolean

3ca576b

implement hybrid_selection for AllocatedFp

b5f88b8

Implement hybrid selection for ProjectiveVar for SW

777da9c

Refactor: inline hybrid_selection into `conditionally_select._power…

6c4e56f

…s_of_two`

update the docs for the default and implementors of improved method

74ce483

Add bench macro to encompass both Boolean and FpVar select methods

f165d68

Add further support for ProjectiveVar

2f79c48

mmagician marked this pull request as ready for review May 9, 2023 01:52

Merge branch 'master' into hybrid-method

7ce86de

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

mmagician commented May 4, 2023

Pratyush left a comment

Pratyush May 4, 2023

mmagician May 4, 2023

Pratyush May 4, 2023

Pratyush May 4, 2023

mmagician May 4, 2023

mmagician May 4, 2023

mmagician commented May 4, 2023

mmagician commented May 9, 2023 •

edited

Loading

mmagician commented May 9, 2023

Pratyush commented May 17, 2023

mmagician commented May 17, 2023

Pratyush commented May 17, 2023

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

Are you sure you want to change the base?

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

Conversation

mmagician commented May 4, 2023

Description

Benches:

Pratyush left a comment

Choose a reason for hiding this comment

Pratyush May 4, 2023

Choose a reason for hiding this comment

mmagician May 4, 2023

Choose a reason for hiding this comment

Pratyush May 4, 2023

Choose a reason for hiding this comment

Pratyush May 4, 2023

Choose a reason for hiding this comment

mmagician May 4, 2023

Choose a reason for hiding this comment

mmagician May 4, 2023

Choose a reason for hiding this comment

mmagician commented May 4, 2023

mmagician commented May 9, 2023 • edited Loading

mmagician commented May 9, 2023

Pratyush commented May 17, 2023

mmagician commented May 17, 2023

Pratyush commented May 17, 2023

mmagician commented May 9, 2023 •

edited

Loading