search

HarryR / ethsnarks

A toolkit for viable zk-SNARKS on Ethereum, Web, Mobile and Desktop
GNU Lesser General Public License v3.0
241 stars 57 forks source link

Number of rows in the Pedersen lookup table #121

Closed sanchopansa closed 5 years ago

sanchopansa commented 5 years ago

Hey @HarryR,

I've been looking at the implementation of the Pedersen hash here. I noticed that you're using 62 rows in the lookup table, but I believe the number according to the Zcash specification should be 63. Some pointers that I'm using for this assumption are:

I am pretty sure that this does not affect adversely the security of the implementation, but I still thought it's worth clarifying.

Thanks, Valentin

HarryR commented 5 years ago

Hi,

I will collate some of the notes, mainly from https://github.com/HarryR/ethsnarks/blob/master/ethsnarks/pedersen.py

I think you might be onto something, I remember adding a note to calculate it depending on the field parameters rather than hard-coding.

It is looking up 3bit chunks in a 2bit table (3rd bit denotes sign).

E.g:
    (b2, b1, b0) = (1,0,1) would look up first element and negate it.

Row i of the lookup table contains:

    [2**(4*i) * base, 2 * 2**(4*i) * base, 3 * 2**(4*i) * base, 4 * 2**(4*i) * base]

E.g:

    row_0 = [base, 2*base, 3*base, 4*base]
    row_1 = [16*base, 32*base, 48*base, 64*base]
    row_2 = [256*base, 512*base, 768*base, 1024*base]

Following Theorem 5.4.1 of the zCash Sapling specification, for baby jub_jub
we need a new base point every 62 windows. We will therefore have multiple
tables with 62 rows each.

We can generate the sequence (denoted as row_0, row_1...) using:

>>> n = 21
>>> rows = [[(j+1)*2**(4*i) for j in range(4)] for i in range(n)]
>>> rows
[[1, 2, 3, 4], [16, 32, 48, 64], [256, 512, 768, 1024], [4096, 8192, 12288, 16384], [65536, 131072, 196608, 262144], [1048576, 2097152, 3145728, 4194304], [16777216, 33554432, 50331648, 67108864], [268435456, 536870912, 805306368, 1073741824], [4294967296, 8589934592, 12884901888, 17179869184], [68719476736, 137438953472, 206158430208, 274877906944], ...]

We can then transform this into the 3-bit windows, where one-bit negates:

>>> rows_3bits = [(a + [-1 * _ for _ in a]) for a in rows]
>>> rows_3bits
[[1, 2, 3, 4, -1, -2, -3, -4], [16, 32, 48, 64, -16, -32, -48, -64], ...]

Then if we take two groups of 3-bits as an example, we can see the values they map to:

>>> results_6bits = [(rows_3bits[0][i] + rows_3bits[1][j]) for i in range(1<<3) for j in range(1<<3)]
>>> results_6bits
[17, 33, 49, 65, -15, -31, -47, -63, 18, 34, 50, 66, -14, -30, -46, -62, 19, 35, 51, 67, -13, -29, -45, -61, 20, 36, 52, 68, -12, -28, -44, -60, 15, 31, 47, 63, -17, -33, -49, -65, 14, 30, 46, 62, -18, -34, -50, -66, 13, 29, 45, 61, -19, -35, -51, -67, 12, 28, 44, 60, -20, -36, -52, -68]
>>> assert len(results_6bits) == len(set(results_6bits))
>>> min(results_6bits), max(results_6bits)                                                                                                                      
(-68, 68)
>>> sorted(results_6bits)                                                                                                                                       
[-68, -67, -66, -65, -63, -62, -61, -60, -52, -51, -50, -49, -47, -46, -45, -44, -36, -35, -34, -33, -31, -30, -29, -28, -20, -19, -18, -17, -15, -14, -13, -12, 12, 13, 14, 15, 17, 18, 19, 20, 28, 29, 30, 31, 33, 34, 35, 36, 44, 45, 46, 47, 49, 50, 51, 52, 60, 61, 62, 63, 65, 66, 67, 68]

We can then generalise this to be a permutation over an arbitrary number of 3-bit chunks, and derive some rules for the minimum and maximum values to see what a safe range is in relation to the field and the order of the curve etc.

n_elements = [1<<_ for _ in range(3,3*n,3)]
def powersum(rows):
    for i in rows[0]:
        if len(rows) == 1:
            yield i
        else:
            for j in powersum(rows[1:]):
                yield i + j
for i in range(3): 
     assert len(list(powersum(rows_3bits[:i+1]))) == n_elements[i]
assert results_6bits == list(powersum(rows_3bits[:2]))

Then we can see the ranges of an arbitrary number of chunks of 3-bits:

>>> from math import log2
>>> for _ in range(9): 
...     x = list(powersum(rows_3bits[:_+1])) 
...     ax, ix = max(x), min(x) 
...     print(3*(_+1), ix, ax, log2(ax), log2(ax*2))                                                                                  
3 -4 4 2.0 3.0
6 -68 68 6.087462841250339 7.087462841250339
9 -1092 1092 10.092757140919852 11.092757140919852
12 -17476 17476 14.093087390444218 15.093087390444218
15 -279620 279620 18.093108028529617 19.093108028529617
18 -4473924 4473924 22.093109318400153 23.093109318400153
21 -71582788 71582788 26.093109399017024 27.093109399017024
24 -1145324612 1145324612 30.09310940405558 31.09310940405558

So, we want to make sure that log2(2*max(x)) < log2(curve_order/twist_coefficient) so that all points it generates will be on the prime-ordered curve (or... something equivalent to that).

There is a clear rule which we can use to determine the maximum of the range, e.g.:

68 - ((1<<6)) == 4
1092 - ((1<<9)*2) == 68
17476 - ((1<<12)*4) == 1092
279620 - ((1<<15)*8) == 17476

Or forwards:

1<<2 == 4
(1<<6) + (1<<2) == 68
(1<<9)*2 + (1<<6) + (1<<2) == 1092
(1<<12)*4 + (1<<9)*2 + (1<<6) + (1<<2) == 17476
(1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6) + (1<<2) == 279620

Meaning we can derive a function which generates the sequence of maximums for the range, which is really useful:

>>> r = 1<<2 
... x = '(1<<2)' 
... i = 2 
... j = 1 
... print(3, x, '=', r) 
... for _ in range(21): 
...     r += (1<<(i*3)) * j 
...     x = ('(1<<%d)*%d + ' % (i * 3, j)) + x 
...     print(3*(_+2), x, '=', r) 
...     i += 1 
...     j += j                                                                                                                                                                                    
3 (1<<2) = 4
6 (1<<6)*1 + (1<<2) = 68
9 (1<<9)*2 + (1<<6)*1 + (1<<2) = 1092
12 (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 17476
15 (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 279620
18 (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 4473924
21 (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 71582788
24 (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 1145324612
27 (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 18325193796
30 (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 293203100740
33 (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 4691249611844
36 (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 75059993789508
39 (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 1200959900632132
42 (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 19215358410114116
45 (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 307445734561825860
48 (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 4919131752989213764
51 (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 78706108047827420228
54 (1<<54)*65536 + (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 1259297728765238723652
57 (1<<57)*131072 + (1<<54)*65536 + (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 20148763660243819578436
60 (1<<60)*262144 + (1<<57)*131072 + (1<<54)*65536 + (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 322380218563901113254980
63 (1<<63)*524288 + (1<<60)*262144 + (1<<57)*131072 + (1<<54)*65536 + (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 5158083497022417812079684
66 (1<<66)*1048576 + (1<<63)*524288 + (1<<60)*262144 + (1<<57)*131072 + (1<<54)*65536 + (1<<51)*32768 + (1<<48)*16384 + (1<<45)*8192 + (1<<42)*4096 + (1<<39)*2048 + (1<<36)*1024 + (1<<33)*512 + (1<<30)*256 + (1<<27)*128 + (1<<24)*64 + (1<<21)*32 + (1<<18)*16 + (1<<15)*8 + (1<<12)*4 + (1<<9)*2 + (1<<6)*1 + (1<<2) = 82529335952358684993274948

If we refer back to the Baby-JubJub parameters:

JUBJUB_E = 21888242871839275222246405745257275088614511777268538073601725287587578984328    # #E is the order of the curve E
JUBJUB_C = 8        # Cofactor
JUBJUB_L = JUBJUB_E//JUBJUB_C   # L*B = 0, and (2^C)*L == #E

We want to make sure that the whole range will fit into the prime-ordered group, so if 2*max(the_range) < JUBJUB_L then the range of bits won't overlap, as in it'l be an injective mapping from input bits to curve points.

By limiting it to 63 bits the range will be between (+/-)5158083497022417812079684, which is far below the JubJub prime-order group parameter. However, the distinction we need to look at is at which point does the range for the number of bits exceed the prime-order group?

With 186 bits (62 rows), the maximum is 120616759622204370232886442717383237347156234026708920874434983341576176708 With 189 bits (63 rows), the maximum is 1929868153955269923726183083478131797554499744427342733990959733465218827332

So we can see:

>>> (2*1929868153955269923726183083478131797554499744427342733990959733465218827332) < JUBJUB_L
False

>>> (2*120616759622204370232886442717383237347156234026708920874434983341576176708) < JUBJUB_L
True

So... by having 62 rows, we ensure that any base point is only ever multiplied by a number which is less than the prime-ordered sub group. (as in, the range is less than -(L/2)...L/2, so any result will never be multiplied by infinity or end up on the twist of the curve)

Apologies for the long-winded explanation, does that make sense though?

HarryR commented 5 years ago

The aim is to avoid the result being a low-ordered point.

By constraining the absolute of the range to be less than L we can never do bit-fiddling to multiply the base point by the order of the group to reach infinity (which would be super bad, collisions ahoy etc.)

Then because we switch to another point, with unknown dlog after that, finding the next set of bits which when then two points are added together negate each other (or add up to one of the other infinities/low-order-points in the twist) is about as difficult as breaking the dlog of a point of unknown order, right?

fleupold commented 5 years ago

Hi, you are right that 63 is the correct number of rows for zCash jub_jub and 62 is the correct number of rows for baby jub_jub.

More generally, it's important that the highest possible sum of scalars in a window does not "wrap around" the prime order subgroup r of our curve as otherwise the mapping might not be injective.

For any row i, the scalars are defined as {-4 * 2**(4(i-1)), ..., 4 * 2**(4(i-1))} \ {0}.

Thus, according to the proof for Theorem 5.4.1. of the Sapling Spec the following condition has to be met:

        4 * ∑2**(4(i-1)) <= (r-1)/2                  // where ∑ from 1..c
<=>    4/15 * 2**(4 * c) <= (r-1)/2
<=>                  4*c <= log2((r-1)*15/8)
<=>                  4*c <= log2(r-1) + log2(15) - 3
 ≈                     c <= log2(r-1)/4 + .3

which for baby jub_jub (r=0x60c89ce5c263405370a08b6d0302b0bab3eedb83920ee0a677297dc392126f1) is 62 and jub_jub (r=0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb7) is 63.

daira commented 4 years ago

Kobi Gurkan pointed out a minor error in Theorem 5.4.1 which was fixed in version 2019.0.7 of the spec (published in September 2019). 4 ∑i = 1..c 24(i-1) = 4 44c - 1 / 15, not 4 * 44c / 15. But it doesn't affect the conclusion here.