MIME-Version: 1.0
References: <CAD5xwhjmu-Eee47Ho5eA6E6+aAdnchLU0OVZo=RTHaXnN17x8A@mail.gmail.com>
 <CAMZUoK=-jrH+fr=tUTHmLojm2-Ff99KYm9H97yhd=7bcOVG=fg@mail.gmail.com>
 <CAD5xwhg0N1byx-G2tk=jjmZSHSBirpaX6OHTnh_x9iDEVF8PrQ@mail.gmail.com>
 <CAMZUoKnYAKum63fRUNJD-zAZX_p3MoFULGWRE7J2QkO69nOe8g@mail.gmail.com>
 <CAD5xwhgtsqAX99NJRU6t-s14aF7frGZxFCL3-c9iBOYrkN_A_w@mail.gmail.com>
In-Reply-To: <CAD5xwhgtsqAX99NJRU6t-s14aF7frGZxFCL3-c9iBOYrkN_A_w@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Sun, 4 Jul 2021 15:03:40 -0400
Message-ID: <CAMZUoKmWqSnWhTUmTXRuAsrgd0KsQ+XjPw1s+XsZWARhsDcGsA@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>
Content-Type: multipart/alternative; boundary="0000000000008201d305c650d9ae"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
Precedence: list

--0000000000008201d305c650d9ae
Content-Type: text/plain; charset="UTF-8"

On Sun, Jul 4, 2021 at 1:30 PM Jeremy <jlrubin@mit.edu> wrote:

> I don't really see the point of CHECKSIGFROMSTACKADD since it's not bound
> to the txdata? When might you use this?
>

I don't feel strongly about *ADD.  I just figured it might be useful to do
a 2-of-3 between Alice, Bob and an Oracle signed value.  But I don't have
any particular use case in mind.  Either way the *ADD functionality can be
replicated by various SWAPs and ADDs etc, so we could just leave it out
until it is wanted.


> And yes -- "Add OP_CHECKSIGFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to
> follow the semantics from bip340-342 when witness program is v1." is a bit
> light on detail for what the BIP would end up looking like. If you're able
> to open up the design process a bit more on that it would be good as I
> think there are some topics worth discussing at large before things proceed
> with Elements (assuming feature compatibility remains a goal).
>

I'm certainly open to a wider design process.  We can open a specific issue
on the Elements repo.  That said, I don't see a particularly wide design
space on this front.


> The non-prehashed argument seems OK (at the cost of an extra byte...) but
> are there specific applications for !=32 arguments? I can't think of a
> particular one beyond perhaps efficiency. Can we safely use 0-520 byte
> arguments?
>

One of the reasons given in the issue (yes, the thread there is very long)
was that hashing the message requires the hash to be collision resistant
while if you give the message directly it only requires the hash to be
"random-prefix" collision / preimage resistant.  For example SHA-1 is
clearly not collision resistant but it appears to still be random-prefix
collision resistant AFAIU.  Another reason is that it allows for extremely
fast signing oracles because and R value and the midstate of the hash can
be precomputed all the way upto the application prefix, and if the message
being signed is less than 55 bytes or so, the signing cost can be as low as
one compression function and a little bit of non-EC modular arithmetic to
compute S.  If the message were required to be prehashed, then it would
take a minimum of 2 compression function calls to sign, nearly doubling the
signing time needed for the fast oracle.

Even if BIP-0340 kept its requirements that the message be exactly 32
bytes, I would still be inclined to design CHECKSIGFROMSTACK for tapscript
to take the 32-byte message from the stack instead of hashing a message
itself (BIP-0340 does it's own hashing, so prehashing the message isn't a
security concern in the same way it is for ECDSA.)  This would keep the
message off the blockchain, saving space and adding some amount of privacy
and making the operation compatible with rolling SHA256 opcodes.  But given
that BIP-0340 is going to be extended to support non-32 byte messages, then
there is no reason to impose a message length restriction on
CHECKSIGFROMSTACK.  Yes the operation will still be subject to stack item
length restrictions.  This is something script writers will have to be
aware of, but I see little reason to support messages split across multiple
stack items when we expect, by far, most messages to be 32-bytes, and I
expect those rare non-32 byte messages are expected to be reasonably short.


> Also do you have thoughts on the other questions i posed above? E.g.
> splitting R/S could be helpful w/o CAT.
>

Regarding  internal pubkeys and invalid pubkeys, I see no reason to deviate
from whatever tapscript CHECKSIG* do.

Regarding splitting R/S, This is harder because Elements does have CAT and
I think we should add CAT to Bitcoin too.  This game of trying to prevent
covenants by restricting script to the point where we are not even allowed
to have a CAT operation is a losing game.  It's just a matter of time
before we accidently introduce some way to enable covenants anyways, and it
is not worth cutting off vast amounts of functionality in pursuit of this
questionable goal.  And I say this as someone who was originally of the
opinion that we should be very very cautious before enabling new
expressivity such as covenants.  All the scary scenarios of covenants that
I am aware of can be more easily, cheaply, and flexibility implemented by
just having a counterparty in a multi-party signature that enforces their
own policy that they only sign transactions that pay to outputs that they
remain a party to.  And even if scary covenants were scarier than what can
already be done by multisig and policy, I still don't think they are scary
enough to warrant keeping CAT disabled.

So I don't think we should get fancy with CHECKSIGFROMSTACK.  Just take a
normal 64-byte signature value as a stack item.  But I don't feel strongly
about this, and I wouldn't oppose splitting R and S in Bitcoin if that is
where consensus lies.

--0000000000008201d305c650d9ae
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Sun, Jul 4, 2021 at 1:30 PM Jeremy &lt;<a href=3D"mailto:jlrubin@=
mit.edu">jlrubin@mit.edu</a>&gt; wrote:<br></div><blockquote class=3D"gmail=
_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204=
,204);padding-left:1ex"><div dir=3D"auto"><div dir=3D"ltr"><div dir=3D"ltr"=
>I don&#39;t really see the point of CHECKSIGFROMSTACKADD since it&#39;s no=
t bound to the txdata? When might you use this?<br></div></div></div></bloc=
kquote><div><br></div><div>I don&#39;t feel strongly about *ADD.=C2=A0 I ju=
st figured it might be useful to do a 2-of-3 between Alice, Bob and an Orac=
le signed value.=C2=A0 But I don&#39;t have any particular use case in mind=
.=C2=A0 Either way the *ADD functionality can be replicated by various SWAP=
s and ADDs etc, so we could just leave it out until it is wanted.<br></div>=
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"auto"><div dir=3D"ltr"><div dir=3D"ltr">And yes -- &quot;Add OP_CHECKSI=
GFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to follow the semantics from bip3=
40-342 when witness program is v1.&quot; is a bit light on detail for what =
the BIP would end up looking like. If you&#39;re able to open up the des<sp=
an class=3D"gmail_default">ign process a bit more on that it would be good =
as I think there are some topics worth discussing at large before things pr=
oceed with Elements (assuming feature compatibility remains a goal).</span>=
</div></div></div></blockquote><div><br></div><div>I&#39;m certainly open t=
o a wider design process.=C2=A0 We can open a specific issue on the Element=
s repo.=C2=A0 That said, I don&#39;t see a particularly wide design space o=
n this front.<br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pad=
ding-left:1ex"><div dir=3D"auto"><div dir=3D"ltr"><div dir=3D"ltr"><div>The=
 non-prehashed=C2=A0argument seems OK (at the cost of an extra byte...) but=
 are there specific applications for !=3D32 arguments? I can&#39;t think of=
 a particular one beyond perhaps efficiency. Can we safely use 0-520 byte a=
rguments?</div></div></div></div></blockquote><div><br></div><div>One of th=
e reasons given in the issue (yes, the thread there is very long) was that =
hashing the message requires the hash to be collision resistant while if yo=
u give the message directly it only requires the hash to be &quot;random-pr=
efix&quot; collision / preimage resistant.=C2=A0 For example SHA-1 is clear=
ly not collision resistant but it appears to still be random-prefix collisi=
on resistant AFAIU.=C2=A0 Another reason is that it allows for extremely fa=
st signing oracles because and R value and the midstate of the hash can be =
precomputed all the way upto the application prefix, and if the message bei=
ng signed is less than 55 bytes or so, the signing cost can be as low as on=
e compression function and a little bit of non-EC modular arithmetic to com=
pute S.=C2=A0 If the message were required to be prehashed, then it would t=
ake a minimum of 2 compression function calls to sign, nearly doubling the =
signing time needed for the fast oracle.<br></div><div><br></div><div>Even =
if BIP-0340 kept its requirements that the message be exactly 32 bytes, I w=
ould still be inclined to design CHECKSIGFROMSTACK for tapscript to take th=
e 32-byte message from the stack instead of hashing a message itself (BIP-0=
340 does it&#39;s own hashing, so prehashing the message isn&#39;t a securi=
ty concern in the same way it is for ECDSA.)=C2=A0 This would keep the mess=
age off the blockchain, saving space and adding some amount of privacy and =
making the operation compatible with rolling SHA256 opcodes.=C2=A0 But give=
n that BIP-0340 is going to be extended to support non-32 byte messages, th=
en there is no reason to impose a message length restriction on CHECKSIGFRO=
MSTACK.=C2=A0 Yes the operation will still be subject to stack item length =
restrictions.=C2=A0 This is something script writers will have to be aware =
of, but I see little reason to support messages split across multiple stack=
 items when we expect, by far, most messages to be 32-bytes, and I expect t=
hose rare non-32 byte messages are expected to be reasonably short.<br></di=
v><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div d=
ir=3D"auto"><div dir=3D"ltr"><div dir=3D"ltr"><div>Also do you have thought=
s on the other questions i posed above? E.g. splitting R/S could be helpful=
 w/o CAT.</div></div></div></div></blockquote><div><br></div><div>Regarding=
=C2=A0 internal pubkeys and invalid pubkeys, I see no reason to deviate fro=
m whatever tapscript CHECKSIG* do.</div><div><br></div><div>Regarding split=
ting R/S, This is harder because Elements does have CAT and I think we shou=
ld add CAT to Bitcoin too.=C2=A0 This game of trying to prevent covenants b=
y restricting script to the point where we are not even allowed to have a C=
AT operation is a losing game.=C2=A0 It&#39;s just a matter of time before =
we accidently introduce some way to enable covenants anyways, and it is not=
 worth cutting off vast amounts of functionality in pursuit of this questio=
nable goal.=C2=A0 And I say this as someone who was originally of the opini=
on that we should be very very cautious before enabling new expressivity su=
ch as covenants.=C2=A0 All the scary scenarios of covenants that I am aware=
 of can be more easily, cheaply, and flexibility implemented by just having=
 a counterparty in a multi-party signature that enforces their own policy t=
hat they only sign transactions that pay to outputs that they remain a part=
y to.=C2=A0 And even if scary covenants were scarier than what can already =
be done by multisig and policy, I still don&#39;t think they are scary enou=
gh to warrant keeping CAT disabled.<br></div><div><br></div><div>So I don&#=
39;t think we should get fancy with CHECKSIGFROMSTACK.=C2=A0 Just take a no=
rmal 64-byte signature value as a stack item.=C2=A0 But I don&#39;t feel st=
rongly about this, and I wouldn&#39;t oppose splitting R and S in Bitcoin i=
f that is where consensus lies.<br></div><div>=C2=A0</div></div></div>

--0000000000008201d305c650d9ae--