3

Workshop link: https://github.com/bitcoinops/taproot-workshop/

In the section 0.2.4 Programming Exercise: Distributivity of scalar operations we implement the following code:

a_key = ECKey().set(a)

b = random.randrange(1, SECP256K1_ORDER)
b_key = ECKey().set(b)

c = random.randrange(1, SECP256K1_ORDER)
c_key = ECKey().set(c)

# Left: Compute a - b as ints (modulo the sepc256k1 group order)
a_minus_b =  (a - b) % SECP256K1_ORDER# TODO: implement

# Left: Compute (a - b) * c as ints (modulo the sepc256k1 group order)
left =  (a_minus_b * c) % SECP256K1_ORDER# TODO: implement

# Right: Compute a * c - b * c as ECKeys
right = (a * c % SECP256K1_ORDER) - (b * c % SECP256K1_ORDER) # TODO: implement 
#if you dont modulo curve order in both parenthesis your number (probably) becomes too large for the curve
#therefore calling .secret on it will not work even if you cast it to ECKey Object (so the assertion cannot even happen in this case)
#you would only be able to call .secret on a value within the curve order

print("Left: {}".format(left))
print("Right: {}".format(right))


right = ECKey().set(right)
# Left/Right: Assert equality
assert left == right.secret
print("\nSuccess!")

Note that the lines with #TODO: implement are the only ones I have modified.

When trying this code block a few times I noticed that it fails occasionally with:

Left: 84229569338898829804715923445734053841060795723920762893503652295039608159004
Right: -31562519898417365618855061562953854011776768555154141489101510846478553335333
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[32], line 28
     26 right = ECKey().set(right)
     27 # Left/Right: Assert equality
---> 28 assert left == right.secret
     29 print("\nSuccess!")

AttributeError: 'ECKey' object has no attribute 'secret'

The attribute error suggests that the generated secret is outside the curve order and was not properly turned into the ECKey

But for at least 50% of the time it returns something like:

Left: 51082417157028894624564857296082907029625179491897309339882235219613900809295
Right: 51082417157028894624564857296082907029625179491897309339882235219613900809295

Success!

What is causing this inconsistency?

1 Answer 1

4

Your right is calculated with (a * c % SECP256K1_ORDER) - (b * c % SECP256K1_ORDER). There's no guarantee that one side of the - will always be bigger than the other side, so it's possible that (b * c % SECP256K1_ORDER) is bigger than (a * c % SECP256K1_ORDER) which results in right being a negative number. As a negative number, it cannot be a valid scalar, and so its secret is not set. Since all of the numbers are random, this happens with 50% probability.

To resolve this, you just need to handle the negatives correctly. A negative number in a prime is just its absolute value subtracted from the prime (SECP256K1_ORDER). How you achieve that is left as an exercise to the reader :)

1
  • That makes tons of sense thank you for the clear explanation!
    – Poseidon
    Mar 13, 2023 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.