How are Bitcoin Signed Messages generated?

Question

Ledger Nano S and other pieces of Bitcoin software and hardware can sign messages using the private key associated with an address.

Doing this, I get the following output:

-----BEGIN BITCOIN SIGNED MESSAGE-----
Test
-----BEGIN SIGNATURE-----
1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR
ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
-----END BITCOIN SIGNED MESSAGE-----

What exactly is being signed? How is the signature generated? What is the hash preimage that goes into the ECDSA signing algorithm?

Answer 1

The message that is signed is prepended with

"\x18Bitcoin Signed Message:\n" + compactSizeEncoding( len(message) )

\x18 is Python syntax for unicode character 0x18. This new text string is then converted into a byte array by interpreting the string as UTF8. This will give you the correct hash preimage which is:

SHA256(SHA256(utf8.to_bytes("\x18Bitcoin Signed Message:\n" + compactSizeEnc( len(message) + message )) = 
559766ea41f2bc4125e5449200dbf7e902b724b66104820ca5b7fc59f30a19e0

You can see a Python code example here. The function msg_magic generates the hash preimage from the message. This Python code example does not correctly implement compactSizeEnc, however. So it only works with a message length up to 253 bytes.

The correct way of handling compactSizeEncoding is documented here.

Answer 2

The message that was signed is "Test". Will use https://github.com/libbitcoin/libbitcoin-explorer/wiki/bx-message-validate command line interface below.

As you can see, I clearly do not have the private keys nor did I have access to the BTC blockchain, but I can validate the message was digitally signed by a person in control of the private key for BTC address 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR without the need for possessing the associated BTC public key.

% echo -n "Test" | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=

The signature is valid.

Result when the message is changed:

% echo -n "Tested wrong message" | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=

The signature is not valid.

Result when the wrong public address is applied:

% echo -n "Test" | bx message-validate 1FZHv7fubXkMcgbDBUeehgPf28cHP86f7V ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=

The signature is not valid.

This is the magic of Internet money. The math is documented a bit in the Andreas' Mastering Bitcoin Book. Also see How is Public Key extracted from (message, digital signature, address).