MIME-Version: 1.0
References: <20201218152720.GW106279@boulet>
In-Reply-To: <20201218152720.GW106279@boulet>
From: Karl-Johan Alm <karljohan-alm@garage.co.jp>
Date: Mon, 21 Dec 2020 14:37:38 +0900
Message-ID: <CALJw2w4bFp8qcxNzz7hn_ZeGG8WWTPu-mRv6A4cPt66EHimyeg@mail.gmail.com>
To: Andrew Poelstra <apoelstra@wpsoftware.net>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] BIP-0322 (generic signmessage) improvements
Precedence: list

Thanks a lot for taking the time to brush up the BIP. For what it's
worth, I am all for these changes, and I see them as clear
improvements all around.

IIRC Pieter was the one who originally suggested the two-checks
approach (invalid, inconclusive, valid) which is being modified here,
so would be good if you chimed in (or not -- which I'll assume means
you don't mind).

On Sat, Dec 19, 2020 at 12:27 AM Andrew Poelstra via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> I have gone over BIP-0322 and substantially rewritten the text.
> Everything I did is (I think) simply clarifying the existing
> protocol, which felt like it was written by committee and wasn't
> easy to follow, EXCEPT:
>
> 1. I rewrote the motivation section, which I believe originally
>    was a paraphrase of Luke-jr's general objections to having any
>    signmessage functionality. I hope Luke in particular can take
>    a look at what I wrote under "Motivation" and see if it
>    captures his concerns.
>
> 2. I merged the "consensus" and "upgradeable" rules to simply be
>    one set of rules, consisting of consensus checks plus additional
>    restrictions, all of which must be included. The new "Extensions"
>    section allows validators to output the state "consensus-valid"
>    if they really don't want to check the additional restrictions.
>
> 3. The "inconclusive" state, which was originally used for what I've
>    called "consensus-valid", now indicates that a validator does not
>    understand the script that it is checking (also described in the
>    new "Extensions" section). The goal is that implementors are able
>    to be meaningfully BIP-0322 while only supporting a subset of
>    Script, e.g. the templates that their own software supports, or
>    Miniscript, or the non-raw non-address set of output descriptors,
>    or whatever.
>
>    We have seen opposition to supporting BIP-322, e.g. [1] because
>    of the requirement that you either have a full script interpreter
>    (plus an open-ended list of Core's standardness flags, which is
>    not even available through libbitcoinconsensus) or nothing. On
>    the other hand, the vast majority of outputs are single-key p2pkh,
>    p2pkwh or p2sh-wpkh.
>
> The new text is here (and for posterity I will also include it
> inline below, though unless Github deletes it it will be easier
> to read in rendered form):
>
> https://github.com/apoelstra/bips/blob/2020-12--bip322-overhaul/bip-0322.=
mediawiki
>
> I'll also PR this to the BIPs repo in the next day or two, and
> comments on Github are then welcome.
>
>
> [1] https://bitcointalk.org/index.php?topic=3D5261605.0
>
>
>
> * * * * * Full text of the above link * * * * *
>
> <pre>
>   BIP: 322
>   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-0322
>   Status: Draft
>   Type: Standards Track
>   Created: 2018-09-10
>   License: CC0-1.0
> </pre>
>
> =3D=3D Abstract =3D=3D
>
> A standard for interoperable signed messages based on the Bitcoin Script =
format, either for proving fund availability, or committing to a message as=
 the intended recipient of funds sent to the invoice address.
>
> =3D=3D Motivation =3D=3D
>
> The current message signing standard only works for P2PKH (1...) invoice =
addresses. We propose to extend and generalize the standard by using a Bitc=
oin Script based approach. This ensures that any coins, no matter what scri=
pt they are controlled by, can in-principle be signed for. For easy interop=
erability with existing signing hardware, we also define a signature messag=
e format which resembles a Bitcoin transaction (except that it contains an =
invalid input, so it cannot be spent on any real network).
>
> Additionally, the current message signature format uses ECDSA signatures =
which do not commit to the public key, meaning that they do not actually pr=
ove knowledge of any secret keys. (Indeed, valid signatures can be tweaked =
by 3rd parties to become valid signatures on certain related keys.)
>
> Ultimately no message signing protocol can actually prove control of fund=
s, both because a signature is obsolete as soon as it is created, and becau=
se the possessor of a secret key may be willing to sign messages on others'=
 behalf even if it would not sign actual transactions. No signmessage proto=
col can fix these limitations.
>
> =3D=3D Types of Signatures =3D=3D
>
> This BIP specifies three formats for signing messages: ''legacy'', ''simp=
le'' and ''full''. Additionally, a variant of the ''full'' format can be us=
ed to demonstrate control over a set of UTXOs.
>
> =3D=3D=3D Legacy =3D=3D=3D
>
> New proofs should use the new format for all invoice address formats, inc=
luding P2PKH.
>
> The legacy format MAY be used, but must be restricted to the legacy P2PKH=
 invoice address format.
>
> =3D=3D=3D Simple =3D=3D=3D
>
> A ''simple'' signature consists of a witness stack, consensus encoded as =
a vector of vectors of bytes, and base64-encoded. Validators should constru=
ct <code>to_spend</code> and <code>to_sign</code> as defined below, with de=
fault values for all fields except that
>
> * <code>message_hash</code> is a BIP340-tagged hash of the message, as sp=
ecified below
> * <code>message_challenge</code> in <code>to_spend</code> is set to the s=
criptPubKey being signed with
> * <code>message_signature</code> in <code>to_sign</code> is set to the pr=
ovided simple signature.
>
> and then proceed as they would for a full signature.
>
> =3D=3D=3D Full =3D=3D=3D
>
> Full signatures follow an analogous specification to the BIP-325 challeng=
es and solutions used by Signet.
>
> Let there be two virtual transactions to_spend and to_sign.
>
> The "to_spend" transaction is:
>
>     nVersion =3D 0
>     nLockTime =3D 0
>     vin[0].prevout.hash =3D 0000...000
>     vin[0].prevout.n =3D 0xFFFFFFFF
>     vin[0].nSequence =3D 0
>     vin[0].scriptSig =3D OP_0 PUSH32[ message_hash ]
>     vin[0].scriptWitness =3D []
>     vout[0].nValue =3D 0
>     vout[0].scriptPubKey =3D message_challenge
>
> where <code>message_hash</code> is a BIP340-tagged hash of the message, i=
.e. sha256_tag(m), where tag =3D <code>BIP0322-signed-message</code>, and <=
code>message_challenge</code> is the to be proven (public) key script.
>
> The "to_sign" transaction is:
>
>     nVersion =3D 0 or as appropriate (e.g. 2, for time locks)
>     nLockTime =3D 0 or as appropriate (for time locks)
>     vin[0].prevout.hash =3D to_spend.txid
>     vin[0].prevout.n =3D 0
>     vin[0].nSequence =3D 0 or as appropriate (for time locks)
>     vin[0].scriptWitness =3D message_signature
>     vout[0].nValue =3D 0
>     vout[0].scriptPubKey =3D OP_RETURN
>
> A full signature consists of the base64-encoding of the to_spend and to_s=
ign transactions concatenated in standard network serialisation.
>
> =3D=3D=3D Full (Proof of Funds) =3D=3D=3D
>
> A signer may construct a proof of funds, demonstrating control of a set o=
f UTXOs, by constructing a full signature as above, with the following modi=
fications.
>
> * <code>message_challenge</code> is unused and shall be set to <code>OP_T=
RUE</code>
> * Similarly, <code>message_signature</code> is then empty.
> * All outputs that the signer wishes to demonstrate control of are includ=
ed as additional outputs to <code>to_sign</code>, and their witness and scr=
iptSig data should be set as though these outputs were actually being spent=
.
>
> Unlike an ordinary signature, validators of a proof of funds need access =
to the current UTXO set, to learn that the claimed inputs exist on the bloc=
kchain, and to learn their scriptPubKeys.
>
> =3D=3D Detailed Specification =3D=3D
>
> For all signature types, except legacy, the <code>to_spend</code> and <co=
de>to_sign</code> transactions must be valid transactions which pass all co=
nsensus checks, except of course that the output with prevout <code>000...0=
00:FFFFFFFF</code> does not exist.
>
> We additionally require the following restrictions be met.
>
> * All signatures must use the SIGHASH_ALL flag.
> * The use of <code>CODESEPARATOR</code> or <code>FindAndDelete</code> is =
forbidden.
> * The use of NOPs reserved for upgrades is forbidden.
> * The use of segwit versions greater than 1 are forbidden.
> * <code>LOW_S</code>, <code>STRICTENC</code> and <code>NULLFAIL</code>: v=
alid ECDSA signatures must be strictly DER-encoded and have a low-S value; =
invalid ECDSA signature must be the empty push
> * <code>MINIMALDATA</code>: all pushes must be minimally encoded
> * <code>CLEANSTACK</code>: require that only a single stack element remai=
ns after evaluation
> * <code>MINIMALIF</code>: the argument of <code>IF</code>/<code>NOTIF</co=
de> must be exactly 0x01 or empty push
>
> Future versions of this BIP may relax these rules, in particular those ar=
ound NOPs and future Segwit versions, as they are deployed on Bitcoin.
>
> =3D=3D=3D Verification =3D=3D=3D
>
> Validation consists of the following steps. A validator is given as input=
 an address ''A'' (which may be omitted in a proof-of-funds), signature ''s=
'' and message ''m'', and outputs one of four states (although validators a=
re only required to be able to output the first and last):
> * ''valid'' indicates that the signature passed all checks described belo=
w
> * ''valid at time t and age s'' indicates that the signature has set time=
locks but is otherwise valid (see "Extensions" below)
> * ''consensus-valid'' indicates that the signature passed validation exce=
pt for the additonal restrictions in the above section (see "Extensions" be=
low)
> * ''inconclusive'' means the validator was unable to check the scripts (s=
ee "Extensions" below)
> * ''invalid'' means none of the other states
>
> # Decode ''s'' as the transactions <code>to_sign</code> and <code>to_spen=
d</code>
> # Confirm that <code>message_hash</code> is the correct hash of ''m''
> # Confirm that <code>message_challenge</code> is the scriptPubKey corresp=
onding to ''A'' if ''A'' is present, and otherwise must be <code>OP_TRUE</c=
ode>
> # Confirm that all other fields are set as specified above; in particular=
 that
> ** <code>to_spend</code> has exactly one input and one output
> ** <code>to_sign</code> has at least one input and its first input spends=
 the output of </code>to_spend</code>
> ** <code>to_sign</code> has exactly one output, as specified above
> # Confirm that the two transactions together satisfy all consensus rules,=
 except for <code>to_spend</code>'s missing input, and except that ''nSeque=
nce'' of <code>to_sign</code>'s first input and ''nLockTime'' of <code>to_s=
ign</code> are not checked.
> # Confirm that all of the above restrictions are met.
>
> If the above conditions are met, the signature is considered ''valid''. O=
therwise the signature is ''invalid''.
>
> =3D=3D=3D Signing =3D=3D=3D
>
> Signers who control an address ''A'' who wish to sign a message ''m'' act=
 as follows:
>
> # They construct <code>to_spend</code> and <code>to_sign</code> as specif=
ied above, using the scriptPubKey of ''A'' for <code>message_challenge</cod=
e> and tagged hash of ''m'' as <code>message_hash</code>.
> # Optionally, they may set nLockTime of <code>to_sign</code> or nSequence=
 of its first input.
> # Optionally, they may add any additional outputs to <code>to_sign</code>=
 that they wish to prove control of.
> # They satisfy <code>to_sign</code> as they would any other transaction.
>
> They then encode their signature, choosing either ''simple'' or ''full'' =
as follows:
>
> * If they added no inputs to <code>to_sign</code>, left nSequence and nLo=
ckTime at 0, and ''A'' is a Segwit address (either pure or P2SH-wrapped), t=
hen they may base64-encode <code>message_signature</code>
> * Otherwise they must base64-encode the concatenation of <code>to_spend</=
code> followed by <code>to_sign</code>.
>
> =3D=3D Extensions =3D=3D
>
> To ease implementation, we allow some additional states to be output rath=
er than ''valid'' or ''invalid''. Users who do not understand or who do not=
 wish to deal with these states may treat them as ''invalid''.
>
> =3D=3D=3D Timelocks =3D=3D=3D
>
> If the nLockTime of <code>to_sign</code> is set to ''t'', and the nSequen=
ce of the first input of <code>to_sign</code> is set to ''s'', the validato=
r may output the state ''valid at time t and age s''.
>
> If both ''t'' and ''s'' are 0, the validator must instead output ''valid'=
'.
>
> Users may then wish to interpret this state as ''valid'' or ''invalid'' r=
elative to the state of the current blockchain, but the rules for doing so =
are out of scope of this BIP.
>
> =3D=3D=3D Incomplete Validation =3D=3D=3D
>
> Some validators may not wish to implement a full script interpreter, choo=
sing instead to support only specific script templates, or only Miniscript,=
 for example. In this case, if they are unable to execute the scripts used =
by <code>to_sign</code>, they should output the state ''inconclusive''.
>
> Users should interpret this state as the same thing as ''invalid'', altho=
ugh take it as a sign that they should find more capable software.
>
> =3D=3D=3D Consensus-Only Validation =3D=3D=3D
>
> Validators which are only able to check consensus-correctness of witnesse=
s, but not the additional restrictions imposed by this BIP, may output the =
state ''consensus-valid'' to indicate that a signature has passed all conse=
nsus and structural checks.
>
> Users should interpret this state as the same thing as ''valid'' but be a=
ware that other software may fail to validate the same signature.
>
> =3D=3D Compatibility =3D=3D
>
> This specification is backwards compatible with the legacy signmessage/ve=
rifymessage specification through the special case as described above.
>
> =3D=3D Reference implementation =3D=3D
>
> TODO
>
> =3D=3D Acknowledgements =3D=3D
>
> Thanks to David Harding, Jim Posen, Kalle Rosenbaum, Pieter Wuille, Andre=
w Poelstra, and many others for their feedback on the specification.
>
> =3D=3D References =3D=3D
>
> # Original mailing list thread: https://lists.linuxfoundation.org/piperma=
il/bitcoin-dev/2018-March/015818.html
>
> =3D=3D Copyright =3D=3D
>
> This document is licensed under the Creative Commons CC0 1.0 Universal li=
cense.
>
> =3D=3D Test vectors =3D=3D
>
> TODO
>
> * * * * * End full text * * * * *
>
> --
> Andrew Poelstra
> Director of Research, Blockstream
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
>     -Justin Lewis-Webster
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev