Add sage script for generating scalar_split

real-or-random commented at 1:15 PM on November 25, 2020: contributor

sage: Reorganize files

 * Move curve parameters to separate file
 * Rename main prover script for clarity

f554dfc708

roconnor-blockstream commented at 1:40 PM on November 25, 2020: contributor

I recommend trying LLL to replace find_split_constants_explicit_tof.

Add/replace the BETA and LAMBDA assertions with an assertion that the value is a root of X^2 + X + 1.

real-or-random force-pushed on Nov 25, 2020

real-or-random commented at 3:26 PM on November 25, 2020: contributor

I recommend trying LLL to replace find_split_constants_explicit_tof.

I think the current one is more instructive... I don't know, I don't want to spend a lot of time on this.

I added root assumptions for BETA and LAMBDA.

real-or-random force-pushed on Nov 25, 2020

roconnor-blockstream commented at 7:33 PM on November 25, 2020: contributor

I'm not really familiar with sage, and I haven't tested this PR, but it is okay by me.

in sage/gen_split_lambda_constants.sage:56 in 0854198a86 outdated

  51 | +A1, B1, A2, B2 = find_split_constants_explicit_tof()
  52 | +
  53 | +# For extra fun, use an independent method to recompute the constants
  54 | +assert (A1, B1, A2, B2) == find_split_constants_gauss()
  55 | +
  56 | +assert A1*B2 - B1*A2 == N

roconnor-blockstream commented at 3:47 AM on November 27, 2020:

If you want to add a comment, I think it would be that this determinant check is verifying that the vectors, um, bound? surround? a fundamental domain (of the ring homomorphism from Z[-1/2+i*sqrt(3)/2] to Zn).

roconnor-blockstream commented at 3:50 AM on November 27, 2020:

If you move this assertion below the next two you could argue that this is proving that the two vectors are not only in the kernel but generate the kernel as well and phrase the comment that way.

(note the determinant also proves the vectors are linearly independent by being non-zero).

real-or-random commented at 8:04 AM on November 27, 2020:

If you want to add a comment, I think it would be that this determinant check is verifying that the vectors, um, bound? surround? a fundamental domain (of the ring homomorphism from Z[-1/2+i*sqrt(3)/2] to Zn).

Can you suggest a wording? I hadn't heard "fundamental domain" before in my life.

If you move this assertion below the next two you could argue that this is proving that the two vectors are not only in the kernel but generate the kernel as well and phrase the comment that way.

(note the determinant also proves the vectors are linearly independent by being non-zero).

Indeed, that's easier. But we could still say why it's exactly n.

roconnor-blockstream commented at 3:53 PM on November 27, 2020:

I don't know. Maybe I'd say, "Check that he parallelogram generated by <A1, A2> and <B1,B2> is a fundamental domain by containing exactly N points." (editted)

roconnor-blockstream commented at 4:46 PM on November 27, 2020: contributor

Another check to add is that lambda*P = <beta*P.x, y>. Checking for P := G is probably sufficient. The point is that the two roots of X^2+X+1 in Zn and Zp need to be matched up in accordance to the group operation on the secp256k1 curve. e.g. all the current assertions would pass if BETA were replaced by BETA^2.

(It will also be the case that all the assertions would pass if both LAMBDA and BETA were replaced with LAMBDA^2 and BETA^2, but there is no helping that because that would be a valid, but different, implementation.)

in sage/gen_split_lambda_constants.sage:12 in 0854198a86 outdated

   7 | +def gauss_reduction(i1, i2):
   8 | +    v1, v2 = i1.copy(), i2.copy()
   9 | +    while True:
  10 | +        if inf_norm(v2) < inf_norm(v1):
  11 | +            v1, v2 = v2, v1
  12 | +        m = round( (v1[0]*v2[0] + v1[1]*v2[1]) / inf_norm(v1)**2 )

sipa commented at 7:58 PM on November 29, 2020:

Can you use (v1[0]*v2[0] + v1[1]*v2[1]) // inf_norm(v1)**2 instead?

in sage/gen_split_lambda_constants.sage:14 in 0854198a86 outdated

   9 | +    while True:
  10 | +        if inf_norm(v2) < inf_norm(v1):
  11 | +            v1, v2 = v2, v1
  12 | +        m = round( (v1[0]*v2[0] + v1[1]*v2[1]) / inf_norm(v1)**2 )
  13 | +        if m == 0:
  14 | +            return (v1, v2)

sipa commented at 8:00 PM on November 29, 2020:

No need for parentheses.

in sage/gen_split_lambda_constants.sage:26 in 0854198a86 outdated

  21 | +
  22 | +    # We use related vectors in secp256k1_scalar_split_lambda
  23 | +    A1, B1 = -v21, -v11
  24 | +    A2, B2 = v22, -v21
  25 | +
  26 | +    return (A1, B1, A2, B2)

sipa commented at 8:00 PM on November 29, 2020:

No need for parentheses.

real-or-random force-pushed on Dec 2, 2020

real-or-random commented at 5:02 PM on December 2, 2020: contributor

I addressed all of your comments.

in sage/gen_split_lambda_constants.sage:17 in 4e4158e653 outdated

  12 | +def gauss_reduction(i1, i2):
  13 | +    v1, v2 = i1.copy(), i2.copy()
  14 | +    while True:
  15 | +        if inf_norm(v2) < inf_norm(v1):
  16 | +            v1, v2 = v2, v1
  17 | +        m = round( (v1[0]*v2[0] + v1[1]*v2[1]) // inf_norm(v1)**2 )

sipa commented at 8:11 PM on December 2, 2020:

No need to round anymore with //.

real-or-random commented at 10:55 AM on December 3, 2020:

Oh, I thought / vs // is just a python2 compatibility thing but I think what you had in mind is to avoid floating-point arithmetic. But this changed the semantics.

The correct thing is to round (to the nearest int) and not floor (for a reason), so that's why I used / and round instead of //. (It just happens that the output is the same for our specific input.)

So I now changed this to a version which

rounds to the nearest integer (what the textbooks do TM [1]),
relies integer arithmetic instead of floating-point arithmetic, and
should work in Python 2 and Python 3 because it does not use /.

[1] https://en.wikipedia.org/wiki/Lattice_reduction#In_two_dimensions Ok not a book but you get the point.

roconnor-blockstream commented at 11:33 AM on December 3, 2020:

Just saying, you could delete the whole thing and call LLL where all this has been worked out.

in sage/gen_split_lambda_constants.sage:20 in 4e4158e653 outdated

  15 | +        if inf_norm(v2) < inf_norm(v1):
  16 | +            v1, v2 = v2, v1
  17 | +        m = round( (v1[0]*v2[0] + v1[1]*v2[1]) // inf_norm(v1)**2 )
  18 | +        if m == 0:
  19 | +            return v1, v2
  20 | +        v2[0] = v2[0] - m*v1[0]

sipa commented at 8:11 PM on December 2, 2020:

-= ?

sipa commented at 8:13 PM on December 2, 2020: contributor

Looks good, ACK 4e4158e653d902f7f2c619d8a76ddf658f200d9e

sage: Add script for generating scalar_split_lambda constants 329a2e0a3f

real-or-random force-pushed on Dec 3, 2020

sipa commented at 8:25 PM on December 4, 2020: contributor

ACK 329a2e0a3f2d9e936179cbf079773538f95bee33

CI failure is unrelated.

jonasnick merged this on Dec 7, 2020

jonasnick closed this on Dec 7, 2020

Fabcien referenced this in commit aa49e83726 on Apr 8, 2021

deadalnix referenced this in commit 4a7f57a433 on Apr 9, 2021

Add sage script for generating scalar_split_lambda constants #852