commit 65d896be5a646e9c0650feaba0ddd36de4833918
parent 49a2dbb0214ef9d3d405b9487082f5f128b1c057
Author: SomberNight <somber.night@protonmail.com>
Date: Mon, 16 Sep 2019 20:43:13 +0200
ecc: also use libsecp256k1 for point addition
time taken to add points changes to around 35% of what it was with python-ecdsa
-----
# benchmark runs before:
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 3.7693 seconds
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 3.8123 seconds
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 3.7937 seconds
# benchmark runs after:
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 1.3127 seconds
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 1.3000 seconds
> python3.7-64 ..\wspace\201909_libsecp256k1_point_addition\bench.py
time taken: 1.3128 seconds
-----
# benchmark script:
import os
import time
from electrum.ecc import generator
from electrum.crypto import sha256
rand_bytes = os.urandom(32)
#rand_bytes = bytes.fromhex('d3d88983b91ee6dfd546ccf89b9a1ffb23b01bf2eef322c2808cb3d951a3c116')
point_pairs = []
for i in range(30000):
rand_bytes = sha256(rand_bytes)
rand_int = int.from_bytes(rand_bytes, "big")
a = generator() * rand_int
rand_bytes = sha256(rand_bytes)
rand_int = int.from_bytes(rand_bytes, "big")
b = generator() * rand_int
point_pairs.append((a,b))
t0 = time.time()
for a, b in point_pairs:
c = a + b
t = time.time() - t0
print(f"time taken: {t:.4f} seconds")
Diffstat:
2 files changed, 54 insertions(+), 17 deletions(-)
diff --git a/electrum/ecc_fast.py b/electrum/ecc_fast.py
@@ -7,7 +7,8 @@ import traceback
import ctypes
from ctypes.util import find_library
from ctypes import (
- byref, c_byte, c_int, c_uint, c_char_p, c_size_t, c_void_p, create_string_buffer, CFUNCTYPE, POINTER
+ byref, c_byte, c_int, c_uint, c_char_p, c_size_t, c_void_p, create_string_buffer,
+ CFUNCTYPE, POINTER, cast
)
import ecdsa
@@ -84,6 +85,9 @@ def load_library():
secp256k1.secp256k1_ec_pubkey_tweak_mul.argtypes = [c_void_p, c_char_p, c_char_p]
secp256k1.secp256k1_ec_pubkey_tweak_mul.restype = c_int
+ secp256k1.secp256k1_ec_pubkey_combine.argtypes = [c_void_p, c_char_p, POINTER(POINTER(c_char_p)), c_size_t]
+ secp256k1.secp256k1_ec_pubkey_combine.restype = c_int
+
secp256k1.ctx = secp256k1.secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY)
r = secp256k1.secp256k1_context_randomize(secp256k1.ctx, os.urandom(32))
if r:
@@ -109,28 +113,23 @@ def _prepare_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
_patched_functions.orig_sign = staticmethod(ecdsa.ecdsa.Private_key.sign)
_patched_functions.orig_verify = staticmethod(ecdsa.ecdsa.Public_key.verifies)
_patched_functions.orig_mul = staticmethod(ecdsa.ellipticcurve.Point.__mul__)
+ _patched_functions.orig_add = staticmethod(ecdsa.ellipticcurve.Point.__add__)
curve_secp256k1 = ecdsa.ecdsa.curve_secp256k1
curve_order = ecdsa.curves.SECP256k1.order
point_at_infinity = ecdsa.ellipticcurve.INFINITY
- def mul(self: ecdsa.ellipticcurve.Point, other: int):
- if self.curve() != curve_secp256k1:
- # this operation is not on the secp256k1 curve; use original implementation
- return _patched_functions.orig_mul(self, other)
- other %= curve_order
- if self == point_at_infinity or other == 0:
- return point_at_infinity
+ def _get_ptr_to_well_formed_pubkey_string_buffer_from_ecdsa_point(point: ecdsa.ellipticcurve.Point):
+ assert point.curve() == curve_secp256k1
pubkey = create_string_buffer(64)
- public_pair_bytes = b'\4' + self.x().to_bytes(32, byteorder="big") + self.y().to_bytes(32, byteorder="big")
+ public_pair_bytes = b'\4' + point.x().to_bytes(32, byteorder="big") + point.y().to_bytes(32, byteorder="big")
r = _libsecp256k1.secp256k1_ec_pubkey_parse(
_libsecp256k1.ctx, pubkey, public_pair_bytes, len(public_pair_bytes))
if not r:
- return False
- r = _libsecp256k1.secp256k1_ec_pubkey_tweak_mul(_libsecp256k1.ctx, pubkey, other.to_bytes(32, byteorder="big"))
- if not r:
- return point_at_infinity
+ raise Exception('public key could not be parsed or is invalid')
+ return pubkey
+ def _get_ecdsa_point_from_libsecp256k1_pubkey_object(pubkey) -> ecdsa.ellipticcurve.Point:
pubkey_serialized = create_string_buffer(65)
pubkey_size = c_size_t(65)
_libsecp256k1.secp256k1_ec_pubkey_serialize(
@@ -139,7 +138,39 @@ def _prepare_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
y = int.from_bytes(pubkey_serialized[33:], byteorder="big")
return ecdsa.ellipticcurve.Point(curve_secp256k1, x, y, curve_order)
- def sign(self: ecdsa.ecdsa.Private_key, hash: int, random_k: int):
+ def add(self: ecdsa.ellipticcurve.Point, other: ecdsa.ellipticcurve.Point) -> ecdsa.ellipticcurve.Point:
+ if self.curve() != curve_secp256k1:
+ # this operation is not on the secp256k1 curve; use original implementation
+ return _patched_functions.orig_add(self, other)
+ if self == point_at_infinity: return other
+ if other == point_at_infinity: return self
+
+ pubkey1 = _get_ptr_to_well_formed_pubkey_string_buffer_from_ecdsa_point(self)
+ pubkey2 = _get_ptr_to_well_formed_pubkey_string_buffer_from_ecdsa_point(other)
+ pubkey_sum = create_string_buffer(64)
+
+ pubkey1 = cast(pubkey1, POINTER(c_char_p))
+ pubkey2 = cast(pubkey2, POINTER(c_char_p))
+ ptr_to_array_of_pubkey_ptrs = (POINTER(c_char_p) * 2)(pubkey1, pubkey2)
+ r = _libsecp256k1.secp256k1_ec_pubkey_combine(_libsecp256k1.ctx, pubkey_sum, ptr_to_array_of_pubkey_ptrs, 2)
+ if not r:
+ return point_at_infinity
+ return _get_ecdsa_point_from_libsecp256k1_pubkey_object(pubkey_sum)
+
+ def mul(self: ecdsa.ellipticcurve.Point, other: int) -> ecdsa.ellipticcurve.Point:
+ if self.curve() != curve_secp256k1:
+ # this operation is not on the secp256k1 curve; use original implementation
+ return _patched_functions.orig_mul(self, other)
+ other %= curve_order
+ if self == point_at_infinity or other == 0:
+ return point_at_infinity
+ pubkey = _get_ptr_to_well_formed_pubkey_string_buffer_from_ecdsa_point(self)
+ r = _libsecp256k1.secp256k1_ec_pubkey_tweak_mul(_libsecp256k1.ctx, pubkey, other.to_bytes(32, byteorder="big"))
+ if not r:
+ return point_at_infinity
+ return _get_ecdsa_point_from_libsecp256k1_pubkey_object(pubkey)
+
+ def sign(self: ecdsa.ecdsa.Private_key, hash: int, random_k: int) -> ecdsa.ecdsa.Signature:
# note: random_k is ignored
if self.public_key.curve != curve_secp256k1:
# this operation is not on the secp256k1 curve; use original implementation
@@ -148,15 +179,17 @@ def _prepare_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
nonce_function = None
sig = create_string_buffer(64)
sig_hash_bytes = hash.to_bytes(32, byteorder="big")
- _libsecp256k1.secp256k1_ecdsa_sign(
+ r = _libsecp256k1.secp256k1_ecdsa_sign(
_libsecp256k1.ctx, sig, sig_hash_bytes, secret_exponent.to_bytes(32, byteorder="big"), nonce_function, None)
+ if not r:
+ raise Exception('the nonce generation function failed, or the private key was invalid')
compact_signature = create_string_buffer(64)
_libsecp256k1.secp256k1_ecdsa_signature_serialize_compact(_libsecp256k1.ctx, compact_signature, sig)
r = int.from_bytes(compact_signature[:32], byteorder="big")
s = int.from_bytes(compact_signature[32:], byteorder="big")
return ecdsa.ecdsa.Signature(r, s)
- def verify(self: ecdsa.ecdsa.Public_key, hash: int, signature: ecdsa.ecdsa.Signature):
+ def verify(self: ecdsa.ecdsa.Public_key, hash: int, signature: ecdsa.ecdsa.Signature) -> bool:
if self.curve != curve_secp256k1:
# this operation is not on the secp256k1 curve; use original implementation
return _patched_functions.orig_verify(self, hash, signature)
@@ -180,6 +213,7 @@ def _prepare_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
_patched_functions.fast_sign = sign
_patched_functions.fast_verify = verify
_patched_functions.fast_mul = mul
+ _patched_functions.fast_add = add
_patched_functions.prepared_to_patch = True
@@ -195,7 +229,7 @@ def do_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
ecdsa.ecdsa.Private_key.sign = _patched_functions.fast_sign
ecdsa.ecdsa.Public_key.verifies = _patched_functions.fast_verify
ecdsa.ellipticcurve.Point.__mul__ = _patched_functions.fast_mul
- # ecdsa.ellipticcurve.Point.__add__ = ... # TODO??
+ ecdsa.ellipticcurve.Point.__add__ = _patched_functions.fast_add
_patched_functions.monkey_patching_active = True
@@ -208,6 +242,7 @@ def undo_monkey_patching_of_python_ecdsa_internals_with_libsecp256k1():
ecdsa.ecdsa.Private_key.sign = _patched_functions.orig_sign
ecdsa.ecdsa.Public_key.verifies = _patched_functions.orig_verify
ecdsa.ellipticcurve.Point.__mul__ = _patched_functions.orig_mul
+ ecdsa.ellipticcurve.Point.__add__ = _patched_functions.orig_add
_patched_functions.monkey_patching_active = False
diff --git a/electrum/tests/test_bitcoin.py b/electrum/tests/test_bitcoin.py
@@ -152,6 +152,8 @@ class Test_bitcoin(SequentialTestCase):
self.assertEqual(inf, A + 2 * G)
self.assertEqual(inf, D + (-1) * G)
self.assertNotEqual(A, B)
+ self.assertEqual(2 * G, inf + 2 * G)
+ self.assertEqual(inf, 3 * G + (-3 * G))
@needs_test_with_all_ecc_implementations
def test_msg_signing(self):
