Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id DF753AA5 for ; Sat, 27 Jul 2019 20:03:52 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm1-f65.google.com (mail-wm1-f65.google.com [209.85.128.65]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ABB3EFE for ; Sat, 27 Jul 2019 20:03:51 +0000 (UTC) Received: by mail-wm1-f65.google.com with SMTP id g67so46145519wme.1 for ; Sat, 27 Jul 2019 13:03:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ib.tc; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=U9RoGdms3kyVRSwsi98WWfCy9f9KCZKDfzK7wCU0Rz8=; b=gVuyEbxQcuriFqW98HMdwcvfZ2uGPUNUn/gZZm/v4pa/HJc+1M53OBILkl8/x4etw9 r4qQZQAHhn41wC4jr6V+g2TAjIsQIVEEdZdGt2SGNp2MPoJaXcOqtmXWf9wTUeYyoPkK n/IawyzQDXpk0tDnC6wLlztC7fhMe1GqpDjhi6zjByseunOX88Vh78mQV079OwuhtBC2 YYRQgIq7JJP4ZB5xoKJdUR6WF/KMAQHucNC5TZ8R0dSgKsd2Rrf5bZ0Ysb2eB2XyMjdE dAaEHHWhMCyy9BG5pNxOB3MsZwPUltbSuaOdRpRM2pYY0rYsi5cpVCF4bUTvmbWDGKsJ +i+A== 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:cc; bh=U9RoGdms3kyVRSwsi98WWfCy9f9KCZKDfzK7wCU0Rz8=; b=iOSWjHNKneH5KMEviSeeXyCwxOIrtp/gg9vrBegNUgwQ+ckPplL5vdjeeXCu91pcHr XC7IEHqZuX8EgfifztwjYzpANTMkx3mRXpiqnGf43wgvAWWszj7jRbBwbrNF6zVYf9zf gNBKvNvGtcJpmJgofQu9sgf6Sr648PAxL12MP2THdSM+AfQSFhxaatnzx6SYCGPMIuSa 2ULiS2GJ7ITznRbU8LT/dJFc7WLByY4I7odaFS7zXUEgH3O8nxfHvdjpqTKNWpW1xcX2 LQdwgHexiGGQwX/eG8hNoz4GGpiVA3CHKiZ4Kra4HOWqecSSxuw7EZwubp6z1aiJDQo2 EfvQ== X-Gm-Message-State: APjAAAWb2Fjlr/k9ZTePNcfItEk/3FFbxRvE55MilniXqcT+dk2671+z v3WAXncQ8ppCEu/HrB9ouf6Bde8C5p1iHqeOxkFef6iTNBc= X-Google-Smtp-Source: APXvYqzLmzfL7SpXQ+I5Acm5flUEv1r2a2cnRsfGKhJfyNEpY88JoFWrNjVEVcZ4awAwKZPMtaSH2NIEotg+TTYLXNg= X-Received: by 2002:a7b:cae9:: with SMTP id t9mr90558443wml.126.1564257830130; Sat, 27 Jul 2019 13:03:50 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Mike Brooks Date: Sat, 27 Jul 2019 13:03:39 -0700 Message-ID: To: ZmnSCPxj , pieter.wuille@gmail.com Content-Type: multipart/alternative; boundary="0000000000004d6c3c058eaf28a9" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Sat, 27 Jul 2019 20:17:43 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 27 Jul 2019 20:03:53 -0000 --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 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
Hey ZmnSCPxj,

As to your first point.= =C2=A0 I wasn'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'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 'consensus checkpoint&#= 39; when a re-org is no longer possible? This is a very interesting topic.<= /div>

=C2=A0> * 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.=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.
<= /div>

=C2=A0> * 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 arithmeti= c to refer back to the dictionary or a larger application state.=C2=A0 If B= itcoin'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't free.=C2=A0 There is a cost in supporti= ng this opcode.

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

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 blockcha= in 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 t= ransaction that triggers its execution.
=C2=A0 In particular, it cannot access data in the block the transaction is= in, or in past blocks.
=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.
=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.
=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.

> 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.

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 previ= ous block data.

We would need to have another new database containing every `PUSHDATA` in e= xistence.
And existing pruning nodes would need to restart from genesis, as this data= base would not exist yet.

Regards,
ZmnSCPxj
--0000000000004d6c3c058eaf28a9--