[bitcoin-dev] Message signing (again) - Karl-Johan Alm

From: Karl-Johan Alm <karljohan-alm@garage•co.jp>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Message signing (again)
Date: Thu, 1 Oct 2020 17:56:15 +0900	[thread overview]
Message-ID: <CALJw2w6cM7GH1yxW3Pc8rzoi-eezuf555GNB3OzBFyPfe2WL-w@mail.gmail.com> (raw)

Hello,

I have updated the signmessage proposal (BIP-322) to use the same
approach as signet uses, which brings out of the box support for psbt
and such, and removes the need for a custom signer and validator
(well, sort of anyway).

In the process, I've also replaced the concatenation approach
(hash("Bitcoin Signed Message || <message>")) with a
BIP340-tagged-hash approach (h/t @ajtowns).

Not much remains of the old BIP, so I am tentatively submitting this
as a replacement proposal. I'd be totally fine with submitting this as
an updated BIP-322 though, if people prefer that.

Pull request is here:

https://github.com/bitcoin/bips/pull/1003

Viewable version:

https://github.com/bitcoin/bips/blob/ce60832ef41301105a95c15dcd854d8ecbc53e00/bip-signmessage-redone.mediawiki

Inline version:

<pre>
BIP: ????
Layer: Applications
Title: Generic Signed Message Format
Author: Karl-Johan Alm <karljohan-alm@garage•co.jp>
Comments-Summary: No comments yet.
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-????
Status: Draft
Type: Standards Track
Created: 2020-10-01
License: CC0-1.0
Replaces: 322
</pre>

== Abstract ==

A standard for interoperable generic signed messages based on the
Bitcoin Script format.

== Background ==

* Assume two actors, a prover <code>P</code> and a verifier <code>V</code>.
* <code>P</code> wants to prove that they own the private key
<code>k</code> associated with a given address <code>A</code> (which
in turn is derived from the pubkey <code>kG</code>).
* Let <code>V</code> generate a message <code>M</code> and hand this
to <code>P</code>.
* <code>P</code> generates a signature <code>S</code> by signing the
message <code>M</code> using <code>k</code>. Given <code>S</code>,
<code>V</code> can prove that <code>P</code> has the private key
associated with <code>A</code>.

The astute reader will notice that the above is missing a critical
part, namely the pubkey <code>kG</code>, without which the verifier
cannot actually verify the message. The current message signing
standard solves this via a cryptographic trick, wherein the signature
<code>S</code> above is a special "recoverable signature" type. Given
the message <code>M</code> and the signature <code>S</code>, it is
then possible to recover the pubkey <code>kG</code>. The system thus
derives the address for the pubkey <code>kG</code>, and if it does not
match <code>A</code>, the proof is deemed invalid.

While this is a neat trick, it unnecessarily restricts and complicates
the message signing mechanism; for instance, it is currently not
possible to sign a message for a P2SH address, because there is no
pubkey to recover from the resulting signature.

== Motivation ==

The current message signing standard only works for P2PKH (1...)
addresses. By extending it to use a Bitcoin Script based approach, it
could be made more generic without causing a too big burden on
implementers, who most likely have access to Bitcoin Script
interpreters already.

== Specification ==

This BIP follows the specification of BIP-325 challenges and solutions.

Let there be two virtual transactions to_spend and to_sign.

The "to_spend" transaction is:

nVersion = 0
nLockTime = 0
vin[0].prevout.hash = 0000...000
vin[0].prevout.n = 0xFFFFFFFF
vin[0].nSequence = 0
vin[0].scriptSig = OP_0 PUSH32[ message_hash ]
vin[0].scriptWitness = []
vout[0].nValue = 0
vout[0].scriptPubKey = message_challenge

where message_hash is a BIP340-tagged hash of the message, i.e.
sha256_tag(m), where tag = "BIP????-signed-message", and
message_challenge is the to be proven (public) key script.

The "to_sign" transaction is:

nVersion = 0
nLockTime = 0
vin[0].prevout.hash = to_spend.txid
vin[0].prevout.n = 0
vin[0].nSequence = 0
vout[0].nValue = 0
vout[0].scriptPubKey = message_signature

It may include other inputs, to facilitate a proof of funds.

A message signature is considered valid, inconclusive, or invalid
based on whether the to_sign transaction is a valid spend of the
to_spend transaction or not, according to the following steps (also
see Consensus and standard flags section further down):

1. Valid, if it is a successful spend according to the current
consensus rules (sometimes called "policy").
2. Inconclusive, if it is a successful spend according to consensus
rules, but NOT according to policy rules
3. Invalid, if it is not a successful spend according to consensus rules

A proof is the base64-encoding of the message_signature as is. A
validator takes the to be proven pubkey and the proof and transforms
it to virtual transactions as described above.

== Legacy format ==

The legacy format is restricted to the legacy P2PKH address format.

Any other input (i.e. non-P2PKH address format) must be signed using
the new format described above.

=== Signing ===

Given the P2PKH address <code>a</code> and the message <code>m</code>,
and the pubkey-hash function <code>pkh(P) =
ripemd160(sha256(P))</code>:

# let <code>p</code> be the pubkey-hash <code>pkh(P)</code> for the
pubkey <code>P</code>, contained in <code>a</code>
# let <code>x</code> be the private key associated with <code>P</code>
so that <code>pkh(xG) = p</code>
# let <code>digest</code> be <code>SHA56d("Bitcoin Signed Message:\n"||m)</code>
# create a compact signature <code>sig</code> (aka "recoverable ECDSA
signature") using <code>x</code> on <code>digest</code>

The resulting proof is <code>sig</code>, serialized using the base64 encoding.

=== Verifying ===

Given the P2PKH address <code>a</code>, the message <code>m</code>,
the compact signature <code>sig</code>, and the pubkey-hash function
<code>pkh(P) = ripemd160(sha256(P))</code>:

# let <code>p</code> be the pubkey-hash <code>pkh(P)</code> for the
pubkey <code>P</code>, contained in <code>a</code>
# let <code>digest</code> be <code>SHA56d("Bitcoin Signed Message:\n"||m)</code>
# attempt pubkey recovery for <code>digest</code> using the signature
<code>sig</code> and store the resulting pubkey into <code>Q</code>
## fail verification if pubkey recovery above fails
# let <code>q</code> be the pubkey-hash <code>pkh(Q)</code> for the
pubkey <code>Q</code>
# if <code>p == q</code>, the proof is valid, otherwise it is invalid

== Compatibility ==

This specification is backwards compatible with the legacy
signmessage/verifymessage specification through the special case as
described above.

== Reference implementation ==

TODO

== Acknowledgements ==

Thanks to David Harding, Jim Posen, Kalle Rosenbaum, Pieter Wuille,
and many others for their feedback on the specification.

== References ==

# Original mailing list thread:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015818.html

== Copyright ==

This document is licensed under the Creative Commons CC0 1.0 Universal license.

== Consensus and standard flags ==

Each flag is associated with some type of enforced rule (most often a
soft fork). There are two sets of flags: consensus flags (which result
in a block being rejected, if violated), and policy flags (which
result in a transaction being accepted only if it is contained within
an actual block, and rejected otherwise, if violated). The policy
flags are a super-set of the consensus flags.

This BIP specifies that a proof that validates for both rulesets is
valid, a proof that validates for consensus rules, but not for policy
rules, is "inconclusive", and a proof that does not validate for
consensus rules is "invalid" (regardless of policy rule validation).

The ruleset sometimes changes. This BIP does not intend to be
complete, nor does it indicate enforcement of rules, it simply lists
the rules as they stand at the point of writing.

=== Consensus rules ===

* P2SH: evaluate P2SH
([https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki
BIP16]) subscripts
* DERSIG: enforce strict DER
([https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki
BIP66]) compliance
* NULLDUMMY: enforce NULLDUMMY
([https://github.com/bitcoin/bips/blob/master/bip-0147.mediawiki
BIP147])
* CHECKLOCKTIMEVERIFY: enable CHECKLOCKTIMEVERIFY
([https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki
BIP65])
* CHECKSEQUENCEVERIFY: enable CHECKSEQUENCEVERIFY
([https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki
BIP112])
* WITNESS: enable WITNESS
([https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
BIP141])

=== Policy rules ===

All of the above, plus (subject to change):

* STRICTENC: non-strict DER signature or undefined hashtype
* MINIMALDATA: require minimal encodings for all push operations
* DISCOURAGE_UPGRADABLE_NOPS: discourage use of NOPs reserved for upgrades
* CLEANSTACK: require that only a single stack element remains after evaluation
* MINIMALIF: Segwit script only: require the argument of OP_IF/NOTIF
to be exactly 0x01 or empty vector
* NULLFAIL: signature(s) must be empty vector if a CHECK(MULTI)SIG
operation failed
* LOW_S: signature with S > order/2 in a checksig operation
* DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM: v1-16 witness programs are
non-standard (i.e. forbidden)
* WITNESS_PUBKEYTYPE: public keys in segregated witness scripts must
be compressed
* CONST_SCRIPTCODE: OP_CODESEPARATOR and FindAndDelete fail any
non-segwit scripts

== Test vectors ==

TODO