search

zcash / halo2

The Halo2 zero-knowledge proving system
https://zcash.github.io/halo2/
Other
712 stars 487 forks source link

`pow_vartime([n, 0, 0, 0]` => `pow_vartime([n]` #792

Open zhiqiangxu opened 1 year ago

zhiqiangxu commented 1 year ago

pow_vartime([n, 0, 0, 0] == pow_vartime([n] always holds, so it seems there's no point in wasting resource computing pow_vartime([n, 0, 0, 0] instead of pow_vartime([n].

str4d commented 1 year ago

This is probably left over from when pow_vartime was on FieldExt and took a fixed-length array (IIRC). Generally +1 on the PR, but I'm on PTO and am not reviewing Zcash PRs currently.

zhiqiangxu commented 1 year ago

This is probably left over from when pow_vartime was on FieldExt and took a fixed-length array (IIRC). Generally +1 on the PR, but I'm on PTO and am not reviewing Zcash PRs currently.

No hurry:)

BTW, it seems pow_vartime and pow are almost the same, is the difference really that big or another left over to be unified?

UPDATE

I see what constant time means here now: it doesn't mean it's faster, just that the time is constant no matter which branch is chosen, to anti timing attack.

E.g:

            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
                // if choice = 0, mask = (-0) = 0000...0000
                // if choice = 1, mask = (-1) = 1111...1111
                let mask = -(choice.unwrap_u8() as to_signed_int!($t)) as $t;
                a ^ (mask & (a ^ b))
            }