From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <karljohan-alm@garage.co.jp>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 73E7CC1787
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:45:28 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id 5B02387C99
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:45:28 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id Bq1dlgP6wlFF
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:45:26 +0000 (UTC)
X-Greylist: delayed 00:07:21 by SQLgrey-1.7.6
Received: from mta65.mta.hdems.com (mta65.mta.hdems.com [3.112.23.32])
 by hemlock.osuosl.org (Postfix) with ESMTPS id 1629787C96
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:45:26 +0000 (UTC)
Received: from mo.hdems.com (unknown [10.5.84.207])
 by mta65.mta.hdems.com ('HDEMS') with ESMTPSA id 4CzpCb0Llxzlfbkk
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:38:03 +0000 (UTC)
X-HDEMS-MO-TENANT: garage.co.jp
Received: from mail-lf1-f69.google.com (mail-lf1-f69.google.com.
 [209.85.167.69]) by gwsmtp.prod.mo.hdems.com with ESMTPS id
 gwsmtpd-trans-835a9263-d61c-4ffd-8430-11da7697cd2d
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 21 Dec 2020 05:37:57 +0000
Received: by mail-lf1-f69.google.com with SMTP id m20so8559254lfl.20
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 20 Dec 2020 21:37:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=garage.co.jp; s=google;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :content-transfer-encoding;
 bh=l5gCbUqvcSgYSr5DdT/X5faNXIXc7lPIs1Gqp5NooIo=;
 b=KoTvNCHFlLm7GARx3e0hJeGkSMKKbJBLURJ4Hk9TebniJRoYt0CTA1ErySHjkZhgcg
 0UO1f706Z+UxIcCCujRqxw7vHoT1GXa4lcNucPc+81dX8jBl8aiMZXMT/ji2Ok+QnI40
 ocqpGV2TJumQzWZAE+FLksISUAW3IdSRviXb8=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:content-transfer-encoding;
 bh=l5gCbUqvcSgYSr5DdT/X5faNXIXc7lPIs1Gqp5NooIo=;
 b=iZx0J9P3lPQHRGXxvDqfFFdO3HsMMNF5QxIoGKs/d484hgLbtzVu0NXHGfVIBF29QK
 qHsNcZRxmq7AwapNpjCWZaHXjclYgyZ9Ym1wvqsfSlaKoDt8dlcTdX+yyrrdjcD53yFf
 aav+XR2IYpsLXZBAEIq2VocJuw6iRamaz83Gdv1GuKGRj8pR+KmnWh/ecIz24sDdZABi
 vOQIJkQk0/jNh3XdYF9165UGajfNjZmPYYioJQlqk/gNM7x/hg2aVmcorDaNNa5pe6ca
 +egzVUOQ4wAK9VBNiM/31gxeb1skWILaXhGImLqx9+fCN7hqlN1LosPKddtWlM6XzAKw
 HMCQ==
X-Gm-Message-State: AOAM530i+w5SUMrwaIC+P1vAtU52ssnu6e/iG7gb7FVCSG3EGsjdSFSu
 CE7lS+lxjaGYjG+mP4v7LWBp6S5K1edTbv+6X0gCSQ2mt2uCuNH+T85FBbAZfr8MlaCW3lNQD2x
 EHhQ4XwoVjPe4YsU4Ryjykmdi5tE0xFg3tq+SwVUykPgNohcdl7SBnH8aSYu03EW4C72YX7fRlo
 0o/TtDHhK60kAziLczQeq3WaNBSUvG5Y20ocUVLDow4wzDbH/R8pN/9e0IrXAB/c65w/P+YO4H/
 zviWNwtR7oDK1xfkUBN2fZaCGabvmIq/Z+rhMRsBMCJTIAO2pDxd00Sjjx88SCZP9opjpUr46a4
 PixdGnesTC3e7fx9x/rl+xf5SRef
X-Received: by 2002:a2e:7e05:: with SMTP id z5mr6924723ljc.353.1608529074654; 
 Sun, 20 Dec 2020 21:37:54 -0800 (PST)
X-Google-Smtp-Source: ABdhPJxon795iHAn/FirStw0G0XaN9hc5zVUjiRFFpzVe3o7g/yULbYddiMoodvkwXjp+RJUkB6mDg3kD8+wy4OGsyE=
X-Received: by 2002:a2e:7e05:: with SMTP id z5mr6924705ljc.353.1608529074120; 
 Sun, 20 Dec 2020 21:37:54 -0800 (PST)
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 21 Dec 2020 05:45:28 -0000

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