Introduce `mul_by_inverse_unchecked`, and use it

arkworks-rs / r1cs-std

R1CS constraints for bits, fields, and elliptic curves

https://www.arkworks.rs

Apache License 2.0

137 stars 59 forks source link

Introduce `mul_by_inverse_unchecked`, and use it #75

Closed Pratyush closed 3 years ago

Pratyush commented 3 years ago

Description

Resolves https://github.com/arkworks-rs/r1cs-std/pull/70#issuecomment-874472795.

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.

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

Pratyush commented 3 years ago

Do you have a good way to add a regression test for this behaviour?

Pratyush commented 3 years ago

Ok I added a check to make sure domain.offset is non-zero by construction. I don't know if this is a good idea: is there ever a case where domain.offset is supposed to be zero? If so, then I can change it to enforce the check inside lagrange_interpolate_with_non_constant_offset, instead of in Radix2DomainVar::new

cc @ValarDragon @tsunrise

ValarDragon commented 3 years ago

domain.offset should never be zero for multiplicative domains, but I don't think that needs to be proven in circuit. Thats about the circuit definition being valid. (The circuit definition has defined an invalid codeword domain if its zero, the offset derivation shouldn't allow construction of zero domain offsets)

Pratyush commented 3 years ago

I think @tsunrise's code require offset to be a variable, so we have to enforce non-zeroness at some point.

ValarDragon commented 3 years ago

Oh I see. If necessary as a temporary defense in depth for correctness seems like an alright fix then.

What I'd rather see is we assert this on the DomainVar itself (that its offset and generator are non-zero). Basically in the constructor for DomainVar, include an argument for the inputs being guaranteed to be non-zero. If false, then do the non-zero checks once there.

Pratyush commented 3 years ago

What I'd rather see is we assert this on the DomainVar itself (that its offset and generator are non-zero). Basically in the constructor for DomainVar, include an argument for the inputs being guaranteed to be non-zero. If false, then do the non-zero checks once there.

Yeah, that's what I changed it to do: https://github.com/arkworks-rs/r1cs-std/blob/213e53d6c33fc3eb4c77791a90dc8b5bb5f549aa/src/poly/domain/mod.rs#L28

ValarDragon commented 3 years ago

I meant explicitly including an argument to not get a constraint created. Currently it seems like a constraint is always created if offset is not a constant?

Pratyush commented 3 years ago

Ah so like a new_unchecked method? For the time being I'm fine with keeping the new method and using that, because I assume the domain is constructed only a few times (< 10?) in the entire circuit

ValarDragon commented 3 years ago

Its constructed once per query per round, so ~200 times.

Pratyush commented 3 years ago

I see, with a different offset each time?

ValarDragon commented 3 years ago

Yeah. The offset is based on the query coset

Pratyush commented 3 years ago

I think I addressed all comments, except for the new_unchecked for DomainVar. I think for the time being it's fine to use new, as it only adds a couple hundred constraints, which would be dominated by the rest of the circuit.

Technically, this is a breaking change due to the changes to the DomainVar API, but since the only consumer of that is ark-ldt, I believe, I think it's fine to do that.

(Maybe we should have "in-flux" features hidden behind a unstable feature flag?)