Adding MulSub and SetReduced32 about go-ristretto HOT 8 CLOSED

Ok, I checked the reduction code and it works fine with negative entries.

from go-ristretto.

MulAdd is faster than a Mul followed by an Add because you don't need to reduce the coefficients twice.

Would the implementation you had in mind for MulSub be faster than a Neg (for c) followed by a MulAdd?

SetReduced32 (in the straight-forward way) would be unsafe: there would be a bias for low valued scalars as there would be two ways to get them (namely the low value itself and the low-value + l). Instead, to derive a scalar from 32 bytes, simply use SetReduced on it (which computes a hash to stretch it to 64 bytes and then uses SetReduced64, which is safe).

from go-ristretto.

Good point about stretching the 32 bytes with a hash.

For the MulSub vs Neg(c) then MulAdd.

I ran the benchmarks three times:

BenchmarkMulSub-8 10000000 151 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.686s

BenchmarkMulSub-8 10000000 152 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.689s

BenchmarkMulSub-8 10000000 150 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.671s

BenchmarkNegMulAdd-8 10000000 231 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 2.549s

BenchmarkNegMulAdd-8 10000000 232 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 2.570s

BenchmarkNegMulAdd-8 10000000 234 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 2.583s

I think the results can be explained because the Neg function subtracts the number from zero, while MulSub is identical to MulAdd except it adds a negative in front of c0-c11. This could also be a reason to not include it because there is not really a difference between MulAdd and MulSub and so we would have duplicate code.

What do you think?

from go-ristretto.

To be clear, in MulAdd this is the only difference:

	s0 := -c0 + a0*b0
	s1 := -c1 + a0*b1 + a1*b0
	s2 := -c2 + a0*b2 + a1*b1 + a2*b0
	s3 := -c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0
	s4 := -c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0
	s5 := -c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0
	s6 := -c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0
	s7 := -c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0
	s8 := -c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0
	s9 := -c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0
	s10 := -c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0
	s11 := -c11 + a0*b11 + a1*b10 + a2*b9 + a3*b8 + a4*b7 + a5*b6 + a6*b5 + a7*b4 + a8*b3 + a9*b2 + a10*b1 + a11*b0

from go-ristretto.

I'm not sure your code is correct: the inverse of c*2^something modulo l isn't (always) -c*2^something. Did you add a unittest?

I see now that the Scalar.Neg code is pretty slow. I'll add an improved version soon.

from go-ristretto.

Did you add a unittest?

Yeah I added unit tests, by taking the unit test from MulAdd and using Sub instead.

I'm not sure your code is correct: the inverse of c*2^something modulo l isn't (always) -c*2^something. 

I was under the impression that it did -c + ab instead of c+ab which is done in MulAdd, but I think my understanding was wrong. I will look for an edge case for it:

Code:
https://github.com/decentralisedkev/go-ristretto/blob/master/scalar.go#L583

Test:
https://github.com/decentralisedkev/go-ristretto/blob/master/scalar_test.go#L125

from go-ristretto.

I changed scalars from radix 8 to radix 32. This makes adding, subtracting, negating (etc) a lot faster. Could you check whether MulSub still makes a noticeable difference for you as compared to Neg(c) and then MulAdd? If it does make a difference, I'll do the math to check whether the implementation is correct.

from go-ristretto.

I changed scalars from radix 8 to radix 32. This makes adding, subtracting, negating (etc) a lot faster. Could you check whether MulSub still makes a noticeable difference for you as compared to Neg(c) and then MulAdd? If it does make a difference, I'll do the math to check whether the implementation is correct.

Git was playing up before.

It made a huge improvement:

BenchmarkNegMulAdd-8 10000000 167 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.857s

BenchmarkNegMulAdd-8 10000000 166 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.836s

BenchmarkNegMulAdd-8 10000000 163 ns/op 0 B/op 0 allocs/op
ok github.com/bwesterb/go-ristretto 1.804s

~31% decrease in time

MulSub stayed the same.

from go-ristretto.