Date: Fri, 04 Oct 2019 07:00:13 +0000
To: Jeremy <jlrubin@mit.edu>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <NVDIhcpuRV6VduUgfMNyGSU1U24ErWPuxpA07fMkIIgXqxEL2aX1_oYJ189Wf5ZigGDBa860gJ-p8d3iAMAWsjHx-5tZHZLjXr7gEmQbL0c=@protonmail.com>
In-Reply-To: <CAD5xwhi7=5eiv1jjf72-rUezZMfj3caR+PGfZEa8i8rjNjodFg@mail.gmail.com>
References: <87wodp7w9f.fsf@gmail.com>
	<20191001155929.e2yznsetqesx2jxo@erisian.com.au>
	<CR-etCjXB-JWkvecjDog4Pkq1SuLUgndtSrZo-V4f4EGcNXzNCeAHRvCZGrxDWw7aHVdDY0pAF92jNLb_Hct0bMb3ew6JEpB9AfIm1tSGaQ=@protonmail.com>
	<CAEM=y+XbP3Dn7X8rHu7h0vbX6DkKA0vFK5nQqzcJ_V+D4EVMmw@mail.gmail.com>
	<C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>
	<CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com>
	<CAD5xwhi7=5eiv1jjf72-rUezZMfj3caR+PGfZEa8i8rjNjodFg@mail.gmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>,
	"lightning-dev@lists.linuxfoundation.org"
	<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the
	discussion about noinput / anyprevout
Precedence: list

Good morning Jeremy,

> Awhile back, Ethan and I discussed having, rather than OP_CAT, an OP_SHA2=
56STREAM that uses the streaming properties of a SHA256 hash function to al=
low concatenation of an unlimited amount of data, provided the only use is =
to hash it.
>
> You can then use it perhaps as follows:
>
> // start a new hash with item
> OP_SHA256STREAM=C2=A0 (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
>
> <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM <-=
2> OP_SHA256STREAM
>
> Or it coul
>

This seems a good idea.

Though it brings up the age-old tension between:

* Generically-useable components, but due to generalization are less effici=
ent.
* Specific-use components, which are efficient, but which may end up not be=
ing useable in the future.

In particular, `OP_SHA256STREAM` would no longer be useable if SHA256 event=
ually is broken, while the `OP_CAT` will still be useable in the indefinite=
 future.
In the future a new hash function can simply be defined and the same techni=
que with `OP_CAT` would still be useable.


Regards,
ZmnSCPxj

> --
> @JeremyRubin
>
> On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail.com> wrote:
>
> > I hope you are having an great afternoon ZmnSCPxj,
> >
> > You make an excellent point!
> >
> > I had thought about doing the following to tag nodes
> >
> > || means OP_CAT
> >
> > `node =3D SHA256(type||SHA256(data))`
> > so a subnode would be
> > `subnode1 =3D SHA256(1||SHA256(subnode2||subnode3))`
> > and a leaf node would be
> > `leafnode =3D SHA256(0||SHA256(leafdata))`
> >
> > Yet, I like your idea better. Increasing the size of the two inputs to
> > OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
> > size of object on the stack seems sensible and also doesn't special
> > case the logic of OP_CAT.
> >
> > It would also increase performance. SHA256(tag||subnode2||subnode3)
> > requires 2 compression function calls whereas
> > SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3D3 compression
> > function calls (due to padding).
> >
> > >Or we could implement tagged SHA256 as a new opcode...
> >
> > I agree that tagged SHA256 as an op code that would certainty be
> > useful, but OP_CAT provides far more utility and is a simpler change.
> >
> > Thanks,
> > Ethan
> >
> > On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote=
:
> > >
> > > Good morning Ethan,
> > >
> > >
> > > > To avoid derailing the NO_INPUT conversation, I have changed the
> > > > subject to OP_CAT.
> > > >
> > > > Responding to:
> > > > """
> > > >
> > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a misdesig=
n, sadly
> > > >=C2=A0 =C2=A0 =C2=A0retained from the original BitCoin 0.1.0 Alpha f=
or Windows design, on
> > > >=C2=A0 =C2=A0 =C2=A0par with:
> > > >=C2=A0 =C2=A0 =C2=A0[..]
> > > >
> > > > -=C2=A0 =C2=A0`OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > >=C2=A0 =C2=A0 =C2=A0[..]
> > > >=C2=A0 =C2=A0 =C2=A0"""
> > > >
> > > >=C2=A0 =C2=A0 =C2=A0OP_CAT is an extremely valuable op code. I under=
stand why it was
> > > >=C2=A0 =C2=A0 =C2=A0removed as the situation at the time with script=
s was dire. However
> > > >=C2=A0 =C2=A0 =C2=A0most of the protocols I've wanted to build on Bi=
tcoin run into the
> > > >=C2=A0 =C2=A0 =C2=A0limitation that stack values can not be concaten=
ated. For instance
> > > >=C2=A0 =C2=A0 =C2=A0TumbleBit would have far smaller transaction siz=
es if OP_CAT was
> > > >=C2=A0 =C2=A0 =C2=A0supported in Bitcoin. If it happens to me as a r=
esearcher it is
> > > >=C2=A0 =C2=A0 =C2=A0probably holding other people back as well. If I=
 could wave a magic
> > > >=C2=A0 =C2=A0 =C2=A0wand and turn on one of the disabled op codes it=
 would be OP_CAT. Of
> > > >=C2=A0 =C2=A0 =C2=A0course with the change that size of each concate=
nated value must be 64
> > > >=C2=A0 =C2=A0 =C2=A0Bytes or less.
> > >
> > > Why 64 bytes in particular?
> > >
> > > It seems obvious to me that this 64 bytes is most suited for building=
 Merkle trees, being the size of two SHA256 hashes.
> > >
> > > However we have had issues with the use of Merkle trees in Bitcoin bl=
ocks.
> > > Specifically, it is difficult to determine if a hash on a Merkle node=
 is the hash of a Merkle subnode, or a leaf transaction.
> > > My understanding is that this is the reason for now requiring transac=
tions to be at least 80 bytes.
> > >
> > > The obvious fix would be to prepend the type of the hashed object, i.=
e. add at least one byte to determine this type.
> > > Taproot for example uses tagged hash functions, with a different tag =
for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-=
before-you-SHA256.
> > >
> > > This seems to indicate that to check merkle tree proofs, an `OP_CAT` =
with only 64 bytes max output size would not be sufficient.
> > >
> > > Or we could implement tagged SHA256 as a new opcode...
> > >
> > > Regards,
> > > ZmnSCPxj
> > >
> > >
> > > >
> > > >=C2=A0 =C2=A0 =C2=A0On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bit=
coin-dev
> > > >=C2=A0 =C2=A0 =C2=A0bitcoin-dev@lists.linuxfoundation.org wrote:
> > > >
> > > >
> > > > > Good morning lists,
> > > > > Let me propose the below radical idea:
> > > > >
> > > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a misdes=
ign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows desig=
n, on par with:
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A01 RETURN
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0higher-`nSequence` replacement
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0DER-encoded pubkeys
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0unrestricted `scriptPubKey`
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0Payee-security-paid-by-payer (i.=
e. lack of P2SH)
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0`OP_CAT` and `OP_MULT` and `OP_A=
DD` and friends
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0transaction malleability
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0probably many more
> > > > >
> > > > > So let me propose the more radical excision, starting with SegWit=
 v1:
> > > > >
> > > > > -=C2=A0 =C2=A0Remove `SIGHASH` from signatures.
> > > > > -=C2=A0 =C2=A0Put `SIGHASH` on public keys.
> > > > >
> > > > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH=
_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pu=
bkey coordinate).
> > > > > `OP_CHECKSIG` and friends then look at the public key to determin=
e sighash algorithm rather than the signature.
> > > > > As we expect public keys to be indirectly committed to on every o=
utput `scriptPubKey`, this is automatically output tagging to allow particu=
lar `SIGHASH`.
> > > > > However, we can then utilize the many many ways to hide public ke=
ys away until they are needed, exemplified in MAST-inside-Taproot.
> > > > > I propose also the addition of the opcode:
> > > > >
> > > > >=C2=A0 =C2=A0 =C2=A0<sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > > > >
> > > > >
> > > > > -=C2=A0 =C2=A0`sighash` must be one byte.
> > > > > -=C2=A0 =C2=A0`pubkey` may be the special byte `0x1`, meaning "ju=
st use the Taproot internal pubkey".
> > > > > -=C2=A0 =C2=A0`pubkey` may be 33-byte public key, in which case t=
he `sighash` byte is just prepended to it.
> > > > > -=C2=A0 =C2=A0`pubkey` may be 34-byte public key with sighash, in=
 which case the first byte is replaced with `sighash` byte.
> > > > > -=C2=A0 =C2=A0If `sighash` is `0x00` then the result is a 33-byte=
 public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > > > >
> > > > > This retains the old feature where the sighash is selected at tim=
e-of-spending rather than time-of-payment.
> > > > > This is done by using the script:
> > > > >
> > > > >=C2=A0 =C2=A0 =C2=A0<pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > > > >
> > > > >
> > > > > Then the sighash can be put in the witness stack after the signat=
ure, letting the `SIGHASH` flag be selected at time-of-signing, but only if=
 the SCRIPT specifically is formed to do so.
> > > > > This is malleability-safe as the signature still commits to the `=
SIGHASH` it was created for.
> > > > > However, by default, public keys will not have an attached `SIGHA=
SH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_A=
LL`).
> > > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, a=
s they are allowed only if the output specifically says they are allowed.
> > > > > Would this not be a superior solution?
> > > > > Regards,
> > > > > ZmnSCPxj
> > > > >
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > >
> > > > Lightning-dev mailing list
> > > > Lightning-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> > >
> > >
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev