Pure python EC #15826

pull sipa wants to merge 2 commits into bitcoin:master from sipa:201904_pythonec changing 5 files +389 −230
  1. sipa commented at 7:27 am on April 16, 2019: member
    This removes the dependency on OpenSSL for the interaction tests, by providing a pure-Python toy implementation of secp256k1.
  2. fanquake added the label Tests on Apr 16, 2019
  3. jonasschnelli commented at 7:35 am on April 16, 2019: contributor
    Concept ACK
  4. practicalswift commented at 8:53 am on April 16, 2019: contributor

    Concept ACK

    Excellent work! Thanks for doing this!

  5. MarcoFalke commented at 11:44 am on April 16, 2019: member
    :heart: Makes it easier to run the tests on native windows, where I couldn’t figure out how to install that library. Will give it a try…
  6. in test/functional/test_framework/key.py:245 in b567f723b9 outdated 
    409+        if self.compressed:
410+            return bytes([0x02 + (p[1] & 1)]) + p[0].to_bytes(32, 'big')
411+        else:
412+            return bytes([0x04]) + p[0].to_bytes(32, 'big') + p[1].to_bytes(32, 'big')
413+
414+    def verify_ecdsa(self, sig, msg, low_s=True):
    MarcoFalke commented at 11:47 am on April 16, 2019:

    Looks like this is never called. Could either:

    • Remove it
    • Update the python linter
    • Call it in a smoke test
  7. sdaftuar commented at 11:56 am on April 16, 2019: member

    Makes it easier to run the tests on native windows, where I couldn’t figure out how to install that library

    That seems like a good motivation for making a change like this, but I’m curious if there are other reasons as well?

  8. sipa commented at 5:07 pm on April 16, 2019: member
    @sdaftuar The original motivation was that for testing a Schnorr signature implementation we’ll want a Python version to test against, which needs much of this logic anyway, and it felt silly to maintain two independent versions just for testing (especially as one relies on OpenSSL we’re trying to get rid of as a dependency). @MarcoFalke I added the verify_ecdsa function to test the sign_ecdsa code while writing it, but expect it may be useful to test against the Bitcoin Core signing code. I can either make the linter ignore it, or at a simple test that invokes it. Up to you.
  9. MarcoFalke commented at 7:26 pm on April 16, 2019: member
    Yeah, having a test that verify_ecdsas a Bitcoin Core generated signature would be nice
  10. in test/functional/p2p_segwit.py:12 in b567f723b9 outdated 
     8@@ -9,7 +9,7 @@
 9 import time
10 
11 from test_framework.blocktools import create_block, create_coinbase, add_witness_commitment, get_witness_script, WITNESS_COMMITMENT_HEADER
12-from test_framework.key import CECKey, CPubKey
13+from test_framework.key import ECKey, ECPubKey
    jnewbery commented at 7:46 pm on April 16, 2019:
    unused import ECPubKey
    sipa commented at 8:00 pm on April 16, 2019:
    Gone.
  11. jnewbery commented at 7:47 pm on April 16, 2019: member
    Concept ACK!
  12. sipa force-pushed on Apr 16, 2019
  13. sipa commented at 8:02 pm on April 16, 2019: member
    I’ve added ecdsa_verify to the ignore list. I’ll try to write a test that actually uses it, but it’s not that trivial either.
  14. sipa force-pushed on Apr 16, 2019
  15. sipa force-pushed on Apr 16, 2019
  16. sipa force-pushed on Apr 16, 2019
  17. sipa force-pushed on Apr 16, 2019
  18. gmaxwell commented at 1:15 am on April 17, 2019: contributor
    At a glance this looks fine, I was going to urge you to put a really strong warning on it, but the warning looks adequate. I’m not going to give this any cryptographic review because I don’t think it needs/deserves any.
  19. in test/functional/test_framework/key.py:35 in 048cbc4868 outdated 
     95 
 96+    See http://en.wikipedia.org/wiki/Jacobi_symbol
 97+    """
 98+    if n == 0:
 99+        return 0
100+    t = 1 if n > 0 else 0
    jnewbery commented at 2:11 pm on April 17, 2019:

    Not that it matters for this application since you only call this with +ve n, but I believe this should be:

    0t = 1 if n > 0 else -1
    sipa commented at 3:04 pm on April 17, 2019:
    That would not be correct (I represent the “t” variable from the Wikipedia article as 0/1 rather than 1/-1, so that I can use xor operations to flip it).
    jnewbery commented at 4:57 pm on April 17, 2019:

    As discussed on IRC, I believe this (and the wikipedia Lua code that it’s based on) is incorrect when passed -ve a (I believe the bug probably stems from the misunderstanding that % in python and lua represents the remainder, not the modulus, so a % n is negative when n is negative).

    Simplest fix is:

    0    assert k > 0 and k % 2
1    n = n % k
2    t = 1
    sipa commented at 5:26 pm on April 17, 2019:

    @jnewbery Nice catch, fixed. You’ve inadvertently fixed another bug, I suspect, namely that jacobi_symbol(0,1) is supposed to be 1, not 0.

    Note to reviewers: this bug doesn’t affect our use, as we never invoke with n<0 or k=1.

  20. sipa force-pushed on Apr 17, 2019
  21. sipa force-pushed on Apr 17, 2019
  22. MarcoFalke commented at 6:29 pm on April 17, 2019: member
    This will be merged next Monday unless there are objections
  23. in test/functional/test_framework/key.py:84 in c01a1b9e1e outdated 
    144+    def on_curve(self, p1):
145+        """Determine whether a Jacobian tuple p is on the curve (and not infinity)"""
146+        x1, y1, z1 = p1
147+        z2 = pow(z1, 2, self.p)
148+        z4 = pow(z2, 2, self.p)
149+        return z1 != 0 and (pow(x1, 3, self.p) + self.a * x1 * z2 + self.b * z2 * z4 - pow(y1, 2, self.p)) % self.p == 0
    jnewbery commented at 7:57 pm on April 17, 2019:

    Again, not a problem for this application since a=0 in secp256k1, but I think this should be:

    0return z1 != 0 and (pow(x1, 3, self.p) + self.a * x1 * z4 + self.b * z2 * z4 - pow(y1, 2, self.p)) % self.p == 0

    (ie the self.a term should be multiplied by z4 so that all terms in the eliptic curve equation have a common z^6 factor that can be cancelled)

    sipa commented at 10:03 pm on April 17, 2019:
    Fixed.
  24. in test/functional/test_framework/key.py:344 in c01a1b9e1e outdated 
    539+        R = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, k)]))
540+        r = R[0] % SECP256K1_ORDER
541+        s = (modinv(k, SECP256K1_ORDER) * (z + self.secret * r)) % SECP256K1_ORDER
542+        if low_s and s > SECP256K1_ORDER_HALF:
543+            s = SECP256K1_ORDER - s
544+        rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
    jnewbery commented at 9:06 pm on April 17, 2019:
    Note that you can also do ceiling division with -(-r.bit_length() // 8). I’m not sure if that’s any more readable though.
    sipa commented at 9:13 pm on April 17, 2019:
    I don’t want a ceiling division; i want a flooring one plus 1 (255 should become 32, but 256 should become 33).
    jnewbery commented at 5:13 pm on April 18, 2019:
    oops. Thanks!
  25. in test/functional/test_framework/key.py:1 in c01a1b9e1e outdated 
    0@@ -1,226 +1,343 @@
1-# Copyright (c) 2011 Sam Rushing
2-"""ECC secp256k1 OpenSSL wrapper.
3+# Copyright (c) 2019 Pieter Wuille
    jnewbery commented at 9:07 pm on April 17, 2019:
    Does the project have a policy on individual contributors’ copyright notices in source files? Do you also want to include the MIT license boilerplate here too?
    sipa commented at 9:47 pm on April 17, 2019:
    There are a few files with individual author’s names. As the “Copyright The Bitcoin Core contributors” is likely meaningless I think listing actual authors is preferable when it’s a well-defined set of people, but I don’t feel strongly.
  26. sipa force-pushed on Apr 17, 2019
  27. in test/functional/test_framework/key.py:113 in 8cc786094f outdated 
    173+        s = (4*x1*y1_2) % self.p
174+        m = 3*x1_2
175+        if self.a:
176+            m += self.a * pow(z1, 4, self.p)
177+        m = m % self.p
178+        x3 = (m**2 - 2*s) % self.p
    jnewbery commented at 5:38 pm on April 18, 2019:
    I’d have a slight preference for these to be named x2, y2, z2
    sipa commented at 6:58 pm on April 18, 2019:
    Done.
  28. in test/functional/test_framework/key.py:140 in 8cc786094f outdated 
    200+        h_2 = (h**2) % self.p
201+        h_3 = (h_2 * h) % self.p
202+        u1_h_2 = (x1 * h_2) % self.p
203+        x3 = (r**2 - h_3 - 2*u1_h_2) % self.p
204+        y3 = (r*(u1_h_2 - x3) - y1*h_3) % self.p
205+        z3 = (h*z1*z2) % self.p
    jnewbery commented at 5:39 pm on April 18, 2019:
    nit: You could remove z2 here (since it’s 1 for an affine point)
    sipa commented at 6:59 pm on April 18, 2019:
    Done.
  29. jnewbery commented at 5:50 pm on April 18, 2019: member

    Looks good to me. A couple of nits inline, but otherwise ACK 8cc786094fb55907a25a4b46caa7f1f8fb512363

    I added copious comments and notes for myself as I was reviewing. They’re here: https://github.com/jnewbery/bitcoin/commit/af36c8ad5ac3369c05c3e832fe28fd9c45b254b3. Feel free to take that commit for this PR.

  30. laanwj commented at 6:34 pm on April 18, 2019: member

    good to lose this dependency on an external library w/ ctypes, this makes porting the tests easier

    ACK 8cc786094fb55907a25a4b46caa7f1f8fb512363 (though would be good to integrate @jnewbery’s comments)

  31. Pure python EC 
    This removes the dependency on OpenSSL for the interaction tests, by providing a pure-Python
toy implementation of secp256k1.
    8c7b9324ca
  32. sipa force-pushed on Apr 18, 2019
  33. sipa commented at 7:31 pm on April 18, 2019: member
    I’ve rewritten the extgcd/modinv functions to be a bit faster, and also included @jnewbery’s comments (after rebasing that commit).
  34. jnewbery commented at 8:07 pm on April 18, 2019: member

    Nice find for the quicker modinv().

    utACK ac050deca0227fe44346f3f91c79d733ed5705d8

  35. Add comments to Python ECDSA implementation b67978529a
  36. sipa force-pushed on Apr 18, 2019
  37. jnewbery commented at 8:56 pm on April 18, 2019: member

    utACK b67978529ad02fc2665f2362418dc53db2e25e17

    Only change is correcting two small code comments.

  38. MarcoFalke merged this on Apr 22, 2019
  39. MarcoFalke closed this on Apr 22, 2019
  40. MarcoFalke referenced this in commit 08bd21a3bd on Apr 22, 2019
  41. sidhujag referenced this in commit d6998af219 on Apr 24, 2019
  42. MarcoFalke referenced this in commit d9fc969e71 on Jun 21, 2019
  43. MarcoFalke referenced this in commit af25a757e0 on Jun 26, 2019
  44. HashUnlimited referenced this in commit 00d8ea22a2 on Aug 23, 2019
  45. HashUnlimited referenced this in commit 2c4d5808d9 on Aug 23, 2019
  46. Bushstar referenced this in commit fefba58944 on Aug 24, 2019
  47. Bushstar referenced this in commit 5830e5b432 on Aug 24, 2019
  48. Bushstar referenced this in commit 0e94e71e47 on Aug 24, 2019
  49. Bushstar referenced this in commit f9c2111bda on Aug 24, 2019
  50. Bushstar referenced this in commit e4e5c1a993 on Aug 24, 2019
  51. Bushstar referenced this in commit ddee472465 on Aug 24, 2019
  52. Bushstar referenced this in commit df9a063170 on Aug 24, 2019
  53. Bushstar referenced this in commit 98771b9e71 on Aug 24, 2019
  54. laanwj referenced this in commit 6393da8fdc on Sep 25, 2019
  55. deadalnix referenced this in commit fb0ea54f2e on May 6, 2020
  56. ftrader referenced this in commit 7025e91ee1 on Aug 17, 2020
  57. PastaPastaPasta referenced this in commit 9565f4795a on Jun 27, 2021
  58. PastaPastaPasta referenced this in commit 1cb4a96635 on Jun 28, 2021
  59. PastaPastaPasta referenced this in commit 8aa73dcb1a on Jun 29, 2021
  60. PastaPastaPasta referenced this in commit 4c5e0add6f on Jul 1, 2021
  61. PastaPastaPasta referenced this in commit e24d40394c on Jul 1, 2021
  62. PastaPastaPasta referenced this in commit 7926be588d on Jul 12, 2021
  63. PastaPastaPasta referenced this in commit a947638130 on Jul 13, 2021
  64. vijaydasmp referenced this in commit c4913f39fb on Oct 23, 2021
  65. vijaydasmp referenced this in commit 4be1a71f6d on Oct 23, 2021
  66. vijaydasmp referenced this in commit 80fa0018bf on Oct 23, 2021
  67. vijaydasmp referenced this in commit 24779e36d8 on Oct 26, 2021
  68. vijaydasmp referenced this in commit ffe73aa19a on Oct 26, 2021
  69. vijaydasmp referenced this in commit 394689a23c on Oct 26, 2021
  70. vijaydasmp referenced this in commit 7f3940cd40 on Oct 29, 2021
  71. vijaydasmp referenced this in commit 7f8b4dce52 on Oct 30, 2021
  72. vijaydasmp referenced this in commit 2ab6f67bf3 on Nov 2, 2021
  73. vijaydasmp referenced this in commit 9b8131690f on Nov 7, 2021
  74. vijaydasmp referenced this in commit c7a6caec8e on Nov 11, 2021
  75. vijaydasmp referenced this in commit da58321301 on Nov 12, 2021
  76. vijaydasmp referenced this in commit d18976eff1 on Nov 13, 2021
  77. vijaydasmp referenced this in commit 83840754fd on Nov 14, 2021
  78. vijaydasmp referenced this in commit 790c9e784b on Nov 14, 2021
  79. MarcoFalke locked this on Dec 16, 2021


sipa jonasschnelli practicalswift MarcoFalke sdaftuar jnewbery gmaxwell laanwj

Labels
Tests

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-01-27 06:13 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me