In search of specification of signmessage and verifymessage

[AvL42]

For the sake of my own understanding, I'm trying to do my own signmessage and verifymessage
implementation.

Things I've found out so far are that the message gets a string "Bitcoin Signed Message:\n" prepended to
it and then hashed (sha256? whatever CHashWriter produces), and for the result a flag-byte (e.g. 1B) and
then the "r" and "s" are concatenated (not sure yet about endianness of those) and the resulting
65-bytestring is base64-encoded.

The flag "1B" is supposed to mean: "first key with even y".

Now, I'm signing message "foo" for address http://blockchain.info/fb/15mjvo  a couple of times
and the signature (after base64-decoding) randomly starts with 1b or 1c.  But the pubkey
corresponding to the address (as can be verified from existing spends from that address)
definitely has an odd y coorddinate. 

What public key does the signmessage implementation actually use?

PS: with google and also with this site's and bitcoin.it/wiki's search feature I failed to find
  a decent description of the algorithm used, and all my attempts to verify bitcoind's
  signatures with my own code failed so far.  For now, I'm using the real pubkey for
  verification, not yet reconstructing anything from flag,r,s.

[jackjack]

I'm in the train so it's not really practical to write something, but you can look at pywallet's way to sign/verify
I'm not sure about how compressed public keys are handled though

[AvL42]

I'm in the train so it's not really practical to write something, but you can look at pywallet's way to sign/verify
I'm not sure about how compressed public keys are handled though

Picked the latest version (it said 3 days ago on https://github.com/jackjack-jj/pywallet), and
examined it.  All the signing-related stuff had some "DER"-stuff around it, and on hashing the
message no preamble is added, so I wonder, if this signing/verifying is even compatible with
the satoshi client.  The Satoshi-client produces signatures that don't show any sign of "DER"-
encoding.

The basic sign/verify math I've already implemented. My problem is the "conventions" for
the interface that satoshi-client is using.

PS: upon reading in your source, I noticed that you do "r = p1.x()".
  That should really be "r = p1.x() % n".  The probability for r >= n
  are actually "much" higher than that of it being zero.

Still searching for official satoshi-client sign&verify technical documentation.

[jackjack]

I'm sure the satoshi client uses the DER format because it uses it for transactions
DER is "\x30\x02"+len(r)+r+"\x02"+len(s)+s

Also, I don't use the sign and verify fonctions that are in KEY class, it's sign_digest and verify_digest

[AvL42]

I'm sure the satoshi client uses the DER format because it uses it for transactions
DER is "\x30\x02"+len(r)+r+"\x02"+len(s)+s

Also, I don't use the sign and verify fonctions that are in KEY class, it's sign_digest and verify_digest

Well, it doesn't.  Just check it.  satoshi-client's signmessage output (after decoding away the
base64 wrapper) doesn't start with \0x30.

They decoupled the message signing from transaction signing, so a naive user couldn't
inadvertedly sign a payment when signing some "random" data given by someone. That's
also the reason why satoshi-client adds a fixed preamble to the text.

See satoshi-source: file: "rpcwallet.cpp"  search for "signmessage"/"verifymessage".

PS: On looking at the source again, I'm now quite confident, that the preamble+message
  are indeed sha256'ed twice.  I'm still having trouble to understand CKey::SetCompactSignature().
 

[Mike Hearn]

The bitcoinj implementation might be easier to understand?

https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/core/ECKey.java#510

[AvL42]

The bitcoinj implementation might be easier to understand?
https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/core/ECKey.java#510

Yes!  Thanks!   My head was quite aching on the C-API of openssl with all the BN_* and
EC_* functions and every simple operation wrapped with an "if" for error-handling...

There is some thing I don't yet understand: Why is there a test to multiply some
ECGroup element times ECGroup-order and check that its the Infinity element?
Isn't that always so? Checking that the point is on the curve would be much faster/
simpler: just apply the coordinates to the EC-equation.

My previous question on why the flag was "1b" for a pubkey with odd Y was solved meanwhile:
the Flag is not about the public key, but about that point reconstructed from "r", the "k*G"
originally generated from the random number k.

PS: pub-key recovery from flag,r,s now works for signatures I created myself, but not yet with
  signatures created from satoshi client, so I guess there's another gotcha I've yet to find.

[Mike Hearn]

It ends up not being infinity if the recId is not correct. It's possible to do key recovery just by incrementing the recId, though that isn't how we use it in Bitcoin text signatures.

[AvL42]

It ends up not being infinity if the recId is not correct. It's possible to do key recovery
just by incrementing the recId, though that isn't how we use it in Bitcoin text signatures.

Incrementing the recId should really never be necessary, when we have
either the public key directly at hand (as in transaction's secScripts),
or the flag-byte (1b-22) from the short sig (as in message-signing).

My point is, that while P**n==O is some CPU-costly test for "point on curve",
(y_P)^2 == (x_P)^3 + 7  is also a test for it, and by orders of magnitude
faster to evaluate.

Also, the satoshi code (as well as bitcoinj) both multiply n by (recId/2),
where (recId/2) is never anything else than 0 or 1. So instead of
"x = (recId/2)*n + r", there could be saving the BN_mul and do
"x=r; if (recId/2) { x += n }" (pseudocode, here). This snippet is
merely undoing the "r=x(mod n)" part of signing, afterall.

I'm primarily wondering if that piece of code just hasn't ever been reviewed
after first sketch, or if I am far off on the wrong track...

[Mike Hearn]

I don't think you're on the wrong track. The code was written just by following the algorithm laid out in the SEC documents. Once it worked, we stopped and moved on to other things. Verifying text signatures is not a common operation so there's no reason to optimise it.

[AvL42]

I don't think you're on the wrong track. The code was written just by following the algorithm laid out in the SEC documents. Once it worked, we stopped and moved on to other things. Verifying text signatures is not a common operation so there's no reason to optimise it.

Makes sense.  Thanks for answering

[Pieter Wuille]

I think you are right. The check for verifying whether multiplying by the order ended up at infinity is part of the algorithm specified in the SEC specification, but is actually mathematically trivial for curves with cofactor=1 (which is the case for secp256k1).

[AvL42]

I think you are right. The check for verifying whether multiplying by the order ended up at infinity is part of the algorithm specified in the SEC specification, but is actually mathematically trivial for curves with cofactor=1 (which is the case for secp256k1).

I'm not sure I understand you... The cofactor==1 primarily means that the group doesn't have any other members than powers of G.
Is the "mathematically trivial" part just that the multiplication algorithm can decide to calculate P**exp or equivalently  (- P **(n - exp)),
the latter of which for exp==n turns into immediate infinity (maybe falling back to a mere point-on-curve check),

or is there something I've missed?

[Pieter Wuille]

I mean that for curves with cofactor==1, for every point that lies on the curve n*point will be infinity, thus that check can indeed be skipped.

[AvL42]

I mean that for curves with cofactor==1, for every point that lies on the curve n*point will be infinity, thus that check can indeed be skipped.

I read the comments in that part of bitcoin-source as saying that they use P*n==O as
a check for "P is valid", in order to weed out wrong guesses of recId as early as possible.

Unless the openssl-function does a point-on-curve check beforehand (if it does, then
it seemingly doesn't document so for EC_POINT_mul), that "early weedout" might
just be a dummy.  It wouldn't matter for overall correctness, anyway.

The whole checking is only done on *generating* the signature, as the openssl-
function for obtaining r and s doesn't provide the information for the flag.

Why isn't pub-key-extraction also used in transactions?  It seems to me, that
this could be used even retro-actively for old blocks. It just needs to be stated
(and controlled by an extra flag in the flag-byte) that to recalculate tx-hashes or
block-hashes, the signScripts would need to be "patched" to old format. That's
like they already get temporarily patched upon signing, too.

[Mike Hearn]

It could have been used on transactions but Satoshi did not know it was possible and/or was unable to implement it. He had several misconceptions about elliptic curve cryptography and generally treated OpenSSL has a block box (as evidenced by the fact that signatures don't have their DER padding removed when the rest of the protocol is so tight and optimized).