MIME-Version: 1.0
References: <CALFqKjQkQwuxjeYkGWO_Y_HhNQmJgrjqF3m04hbORV7FSbsi3Q@mail.gmail.com>
	<nk8ihWbf71QT6w-wVbnunppF_DjS8ywDoDAugBj5mYM_LCpSzec0j6lkaTKBK4t3CsXwRSXWmzbWiW7nmqT4y0W2fn8X-3oXv-TAYXwP1R4=@protonmail.com>
In-Reply-To: <nk8ihWbf71QT6w-wVbnunppF_DjS8ywDoDAugBj5mYM_LCpSzec0j6lkaTKBK4t3CsXwRSXWmzbWiW7nmqT4y0W2fn8X-3oXv-TAYXwP1R4=@protonmail.com>
From: Mike Brooks <m@ib.tc>
Date: Sat, 27 Jul 2019 13:03:39 -0700
Message-ID: <CALFqKjQoA+4XKGePHEK9OAZv2+qg=Q669v=f=MpDtg4F3Fx4kQ@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, pieter.wuille@gmail.com
Content-Type: multipart/alternative; boundary="0000000000004d6c3c058eaf28a9"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References
Precedence: list

--0000000000004d6c3c058eaf28a9
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hey ZmnSCPxj,

As to your first point.  I wasn't aware there was so much volatility at the
tip, also 100 blocks is quite the difference!  I agree no one could
references a transaction in a newly formed blocks, but I'm curious how this
number was chosen. Do you have any documentation or code that you can share
related to how re-orgs are handled? Do we have a kind of 'consensus
checkpoint' when a re-org is no longer possible? This is a very interesting
topic.

 > * It strongly encourages pubkey reuse, reducing privacy.
Privacy-aware users are free to have single-use p2sh transactions, and they
are free to use the same SCRIPT opcodes we have now.  Adding an extra
opcode helps with the utility of SCRIPT by compressing the smallest SegWit
transactions by a further 40% from 233 bytes to 148 bytes.  Cost savings is
a great utility - and it need not undermine anyones privacy. The resulting
p2sh SCRIPT could end up using public key material that could be compressed
with a PubRef - everyone wins.

 > * There is a design-decision wherein a SCRIPT can only access data in
the transaction that triggers its execution.
In order for a compression algorithm like LZ78 to be written in a
stack-based language like SCRIPT, there needs to be pointer arithmetic to
refer back to the dictionary or a larger application state.  If Bitcoin's
entire stack was made available to the SCRIPT language as an application
state, then LZ78-like compression could be accomplished using PubRef. If a
Script can reuse a PUSHDATA, then transactions will be less repetitious...
and this isn't free.  There is a cost in supporting this opcode.

Giving the SCRIPT language access to more data opens the door for
interesting algorithms, not just LZ78.  This is interesting to discuss how
this application state could be brought to the language.  It strikes me
that your concerns(ZmnSCPxj), as well as the topic of pruning brought up by
others (including Pieter Wuille) could be fixed by the creation of a
side-chain of indexes.  A validator would not need a hash table which is
only needed for O(1) PUBREF creation, these nodes need not be burdened with
this added index.  A validator only needs an array of PUSHDATA elements and
can then validate any given SCRIPT at O(1).

Just a thought.

Best Regards,
Mike


On Fri, Jul 19, 2019 at 11:08 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Mike,
>
> > PubRef is not susceptible to malleability attacks because the blockchai=
n
> is immutable.
>
> This is not quite accurate.
> While very old blocks are indeed immutable-in-practice, chain tips are
> not, and are often replaced.
> At least specify that such data can only be referred to if buried under
> 100 blocks.
>
> --
>
> There are a number of other issues:
>
> * It strongly encourages pubkey reuse, reducing privacy.
> * There is a design-decision wherein a SCRIPT can only access data in the
> transaction that triggers its execution.
>   In particular, it cannot access data in the block the transaction is in=
,
> or in past blocks.
>   For example, `OP_CHECKLOCKTIMEVERIFY` does not check the blockheight of
> the block that the transaction is confirmed in, but instead checks only
> `nLockTime`, a field in the transaction.
>   * This lets us run SCRIPT in isolation on a transaction, exactly one
> time, when the transaction is about to be put into our mempool.
>     When a new block arrives, transactions in our mempool that are in the
> block do not need to have their SCRIPTs re-executed or re-validated.
>
> > In order for a client to make use of the PUBREF operations they=E2=80=
=99ll need
> access to a database that look up public-keys and resolve their PUBREF
> index.  A value can be resolved to an index with a hash-table lookup in
> O(1) constant time. Additionally, all instances of PUSHDATA can be indexe=
d
> as an ordered list, resolution of a PUBREF index to the intended value
> would be an O(1) array lookup.  Although the data needed to build and
> resolve public references is already included with every full node,
> additional computational effort is needed to build and maintain these
> indices - a tradeoff which provides smaller transaction sizes and relievi=
ng
> the need to store repetitive data on the blockchain.
>
> This is not only necessary at the creator of the transaction --- it is
> also necessary at every validator.
>
> In particular, consider existing pruning nodes, which cannot refer to
> previous block data.
>
> We would need to have another new database containing every `PUSHDATA` in
> existence.
> And existing pruning nodes would need to restart from genesis, as this
> database would not exist yet.
>
> Regards,
> ZmnSCPxj
>

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

<div dir=3D"ltr">Hey ZmnSCPxj,<div><br></div><div>As to your first point.=
=C2=A0 I wasn&#39;t aware there was so much volatility at the tip, also 100=
 blocks is quite the difference!=C2=A0 I agree no one could references a tr=
ansaction in a newly formed blocks, but I&#39;m curious how this number was=
 chosen. Do you have any documentation or code that you can share related t=
o how re-orgs are handled? Do we have a kind of &#39;consensus checkpoint&#=
39; when a re-org is no longer possible? This is a very interesting topic.<=
/div><div><br></div><div>=C2=A0&gt; * It strongly encourages pubkey reuse, =
reducing privacy.<br></div><div>Privacy-aware users are free to have single=
-use p2sh transactions, and they are free to use the same SCRIPT opcodes we=
 have now.=C2=A0 Adding an extra opcode helps with the utility of SCRIPT by=
 compressing the smallest SegWit transactions by a further 40% from 233 byt=
es to 148 bytes.=C2=A0 Cost savings is a great utility - and it need not un=
dermine anyones privacy. The resulting p2sh SCRIPT could end up using publi=
c key material that could be compressed with a PubRef - everyone wins.<br><=
/div><div><br></div><div>=C2=A0&gt; * There is a design-decision wherein a =
SCRIPT can only access data in the transaction that triggers its execution.=
<br></div><div>In order for a compression algorithm like LZ78 to be written=
 in a stack-based language like SCRIPT, there needs to be pointer arithmeti=
c to refer back to the dictionary or a larger application state.=C2=A0 If B=
itcoin&#39;s entire stack was made available to the SCRIPT language as an a=
pplication state, then LZ78-like compression could be accomplished using Pu=
bRef. If a Script can reuse a PUSHDATA, then transactions will be less repe=
titious...=C2=A0 and this isn&#39;t free.=C2=A0 There is a cost in supporti=
ng this opcode.</div><div><br></div><div>Giving the SCRIPT language access =
to more data opens the door for interesting algorithms, not just LZ78.=C2=
=A0 This is interesting to discuss how this application state could be brou=
ght to the language.=C2=A0 It strikes me that your concerns(ZmnSCPxj), as w=
ell as the topic of pruning brought up by others (including Pieter Wuille)=
=C2=A0could be fixed by the creation of a side-chain of indexes.=C2=A0 A va=
lidator would not need a hash table which is only needed for O(1) PUBREF cr=
eation, these nodes need not be burdened with this added index.=C2=A0 A val=
idator only needs an array of PUSHDATA elements and can then validate any g=
iven SCRIPT at O(1).=C2=A0=C2=A0</div><div><br></div><div>Just a thought.</=
div><div><br></div><div>Best Regards,</div><div>Mike</div><div><br></div></=
div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On=
 Fri, Jul 19, 2019 at 11:08 AM ZmnSCPxj &lt;<a href=3D"mailto:ZmnSCPxj@prot=
onmail.com">ZmnSCPxj@protonmail.com</a>&gt; wrote:<br></div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid =
rgb(204,204,204);padding-left:1ex">Good morning Mike,<br>
<br>
&gt; PubRef is not susceptible to malleability attacks because the blockcha=
in is immutable.<br>
<br>
This is not quite accurate.<br>
While very old blocks are indeed immutable-in-practice, chain tips are not,=
 and are often replaced.<br>
At least specify that such data can only be referred to if buried under 100=
 blocks.<br>
<br>
--<br>
<br>
There are a number of other issues:<br>
<br>
* It strongly encourages pubkey reuse, reducing privacy.<br>
* There is a design-decision wherein a SCRIPT can only access data in the t=
ransaction that triggers its execution.<br>
=C2=A0 In particular, it cannot access data in the block the transaction is=
 in, or in past blocks.<br>
=C2=A0 For example, `OP_CHECKLOCKTIMEVERIFY` does not check the blockheight=
 of the block that the transaction is confirmed in, but instead checks only=
 `nLockTime`, a field in the transaction.<br>
=C2=A0 * This lets us run SCRIPT in isolation on a transaction, exactly one=
 time, when the transaction is about to be put into our mempool.<br>
=C2=A0 =C2=A0 When a new block arrives, transactions in our mempool that ar=
e in the block do not need to have their SCRIPTs re-executed or re-validate=
d.<br>
<br>
&gt; In order for a client to make use of the PUBREF operations they=E2=80=
=99ll need access to a database that look up public-keys and resolve their =
PUBREF index.=C2=A0 A value can be resolved to an index with a hash-table l=
ookup in O(1) constant time. Additionally, all instances of PUSHDATA can be=
 indexed as an ordered list, resolution of a PUBREF index to the intended v=
alue would be an O(1) array lookup.=C2=A0 Although the data needed to build=
 and resolve public references is already included with every full node, ad=
ditional computational effort is needed to build and maintain these indices=
 - a tradeoff which provides smaller transaction sizes and relieving the ne=
ed to store repetitive data on the blockchain.<br>
<br>
This is not only necessary at the creator of the transaction --- it is also=
 necessary at every validator.<br>
<br>
In particular, consider existing pruning nodes, which cannot refer to previ=
ous block data.<br>
<br>
We would need to have another new database containing every `PUSHDATA` in e=
xistence.<br>
And existing pruning nodes would need to restart from genesis, as this data=
base would not exist yet.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--0000000000004d6c3c058eaf28a9--