Inside Bitcoin

251
252    def to_bytes_xonly(self):
253        """Convert (the x coordinate of) a non-infinite group element to 32-byte xonly encoding."""
254        assert not self.infinity
255        return self.x.to_bytes()
256
257    @staticmethod
258    def lift_x(x):
259        """Return group element with specified field element as x coordinate (and even y)."""
260        y = (FE(x)**3 + 7).sqrt()
261        if y is None:
262            return None
263        if not y.is_even():
264            y = -y
265        return GE(x, y)
266
267    @staticmethod
268    def from_bytes(b):
269        """Convert a compressed or uncompressed encoding to a group element."""
270        assert len(b) in (33, 65)
271        if len(b) == 33:
272            if b[0] != 2 and b[0] != 3:
273                return None
274            x = FE.from_bytes(b[1:])
275            if x is None:
276                return None
277            r = GE.lift_x(x)
278            if r is None:
279                return None
280            if b[0] == 3:
281                r = -r
282            return r
283        else:
284            if b[0] != 4:
285                return None
286            x = FE.from_bytes(b[1:33])
287            y = FE.from_bytes(b[33:])
288            if y**2 != x**3 + 7:
289                return None
290            return GE(x, y)
291
292    @staticmethod
293    def from_bytes_xonly(b):
294        """Convert a point given in xonly encoding to a group element."""
295        assert_equal(len(b), 32)
296        x = FE.from_bytes(b)
297        if x is None:
298            return None
299        return GE.lift_x(x)
300
301    @staticmethod
302    def is_valid_x(x):
303        """Determine whether the provided field element is a valid X coordinate."""
304        return (FE(x)**3 + 7).is_square()
305
306    def __str__(self):
307        """Convert this group element to a string."""
308        if self.infinity:
309            return "(inf)"
310        return f"({self.x},{self.y})"
311
312    def __repr__(self):
313        """Get a string representation for this group element."""
314        if self.infinity:
315            return "GE()"
316        return f"GE(0x{int(self.x):x},0x{int(self.y):x})"
317
318# The secp256k1 generator point
319G = GE.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
320
321
322class FastGEMul:
323    """Table for fast multiplication with a constant group element.
324
325    Speed up scalar multiplication with a fixed point P by using a precomputed lookup table with
326    its powers of 2:
327
328        table = [P, 2*P, 4*P, (2^3)*P, (2^4)*P, ..., (2^255)*P]
329
330    During multiplication, the points corresponding to each bit set in the scalar are added up,
331    i.e. on average ~128 point additions take place.
332    """
333
334    def __init__(self, p):
335        self.table = [p]  # table[i] = (2^i) * p
336        for _ in range(255):
337            p = p + p
338            self.table.append(p)
339
340    def mul(self, a):
341        result = GE()
342        a = a % GE.ORDER
343        for bit in range(a.bit_length()):
344            if a & (1 << bit):
345                result += self.table[bit]
346        return result
347
348# Precomputed table with multiples of G for fast multiplication
349FAST_G = FastGEMul(G)
350
351class TestFrameworkSecp256k1(unittest.TestCase):
352    def test_H(self):
353        H = sha256(G.to_bytes_uncompressed()).digest()
354        assert GE.lift_x(FE.from_bytes(H)) is not None
355        self.assertEqual(H.hex(), "50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0")
356