Encoding a transaction in a point of the curve y^2=x^3+7 and Bitcoin Core

[arulbero]

Where should I look at in Bitcoin Core source code to figure out how the signature process trasform a message in a curve point?

To sign a transaction (message) in Bitcoin system, you need to encode the message to a point of the curve y^2=x^3+7. I read this Koblitz's paper. There are three encoding schemes. I read this question too.

If I look at in Bitcoin Core source code I can't see any of these encoding schemes, it seems to me that message M is directly encoded in a point ( --> hash(M) ) without check; obviously that is not possible, there is roughly a 50% chance that a random 256 bit string don't correspond to a point of the curve. I can't find out how/if the ECDSA library checks if hash(M) is on the curve or not and especially what it does if the hash(M) is not on the curve.

What encoding scheme does Bitcoin-ECDSA implement and where is it in the source code?

[andytoshi]

Hi arulbero,

I like this question. The short answer is that messages are not encoded as curvepoints, but as scalars. There are ways to encode data as curvepoints, as is presumably described in Koblitz's paper, and some cryptosystems require this, but ECDSA does not.

A longer answer is that there are three types of objects used in ECDSA: group elements, scalars and field elements. The group elements are points on the curve, which form a mathematical group, which simply means that any pair of elements can be added or subtracted in a coherent way. (Note that "addition" and "subtraction" for curvepoints is very different from addition and subtraction of numbers! To add two curvepoints, you run through a series of algebraic transformations on their coordinates; these have deep algebraic reasons to be what they are, but they're technical and unenlightening to write out.) Scalars are just integers; field elements are elements of the mathematical field over which the group is defined. They act similarly to numbers, are an implementation detail of the group, and it's usually OK to forget they exist.

Given group elements that can be added, for any element G in the group you can look at G, G + G, G + G + G, etc., and in general "n times G" for any integer n. These integers are the scalars, and they have no structure beyond that. A cryptographic property of elliptic curve groups is that these scalars are somehow hidden by the multiplication process. That is, for any n and G, you can compute nG pretty easily, but given G and nG, it's very hard to figure out n. (This is how signing (secret) and verification (public) keys are related, by the way: a signing key is some scalar d, and its verification key is dG for a specific G which is a property of Bitcoin.)

The ECDSA algorithm interprets H(m) as a scalar, not a curvepoint. It does this in the most straightforward way: by reading the hash as a big-endian 256-bit number.

If you are curious, the full algorithm is as follows: given a secret key d, message hash h, and random scalar k, it outputs a signature (r, s) consisting of two field elements:

• r is the x-coordinate of the curvepoint kG
• s is (h + dr) * inv(k)

(In calculating s, we treat all the scalars as field elements, which can be done by taking them modulo the size of the field. Then "inv(k)" means the field element j such that k*j = 1 in the field.)


This is a bit more technical than I meant it to be, but I hope it helps clarify some things.

Andrew

[altcoinex]

What encoding scheme does Bitcoin-ECDSA implement and where is it in the source code?

This depends which branch you are using. I will assume we are discussing 0.10 or master.

You will find the majority of what you are looking for inside src/secp256k1/src
https://github.com/bitcoin/bitcoin/tree/master/src/secp256k1/src mostly inside of https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/src/secp256k1.c Also, please see https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/include/secp256k1.h

The OpenSSL EC Wrapper is https://github.com/bitcoin/bitcoin/blob/master/src/ecwrapper.cpp

Lastly, a small amount of checking is located in https://github.com/bitcoin/bitcoin/blob/master/src/eccryptoverify.cpp

You can find the calls being made inside key.cpp, main.cpp, but I don't know if you care about those or not...

[arulbero]

Thank you both for your answers.

I thought that 'r' was a curvepoint, and then I misunderstood  '+' in this formula:

   s = (h + dr) * inv(k)  

as addition of group elements, not as addition of field elements. So I guessed that 'h' was a curvepoint (group element) too.

This one was the reason why I couldn't understand ECDSA library source code.

[...] there are three types of objects used in ECDSA: group elements, scalars and field elements

[...]In calculating s, we treat all the scalars as field elements, which can be done by taking them modulo the size of the field

In my opinion, there are only two types of objects used in ECDSA: group elements and field elements (scalars elements = field elements). What would the difference be between scalar and field elements?

[...]
a signature (r, s) consisting of two field elements:

    r is the x-coordinate of the curvepoint kG
    s is (h + dr) * inv(k)

In a signature (r, s), 'r' and 's' are two field elements:  a signature corresponds (or not) to a curvepoint?   'r' is the x-coordinate of the curvepoint kG, but I guess 's' is not the y-coordinate of kG, because 's' is not equal to sqrt(r^3 + 7) mod p.
 

[gmaxwell]

In my opinion, there are only two types of objects used in ECDSA: group elements and field elements (scalars elements = field elements). What would the difference be between scalar and field elements?

There are group elements, these are the points on the curve, a finite abelian group of order N where the discrete log problem is assumed hard.

There are field elements, which are values in the field F(P) which the curve above is constructed over. These are used inside the group code but are mostly not seen directly by the signature algorithm.

Then there are scalars which are ordinary numbers mod N (same order as the group), which are used to multiply group elements; these are most of the objects used in signing.

In ECDSA the X coordinate (which is a F(P) field element) of a point R  (R =kG) is coerced into a scalar ( r = R.xy()[0] mod N)-- which makes keeping the types straight harder.

(A common but not universal convention is to make point variables upper case and scalars lower case)


If you're just trying to understand signatures for your personal enrichment; schnorr is easier to understand.

[arulbero]

Thank you for your clear and helpful explanation. I have a lot to study