Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 55F9921F7 for ; Fri, 19 Jul 2019 06:05:56 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f50.google.com (mail-wr1-f50.google.com [209.85.221.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 28F1412E for ; Fri, 19 Jul 2019 06:05:54 +0000 (UTC) Received: by mail-wr1-f50.google.com with SMTP id p17so30948507wrf.11 for ; Thu, 18 Jul 2019 23:05:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ib.tc; s=google; h=mime-version:from:date:message-id:subject:to; bh=5b/fnZv9u8hWwytN7nE+plTI8m4ReHpaFuqOCjk1Fdo=; b=fNAmJpLCdjXIEMLNuOBZ6at6lQx0lrF5SK2/XirovrhIYxzG/t/+87bhDxT2vjTKfB daVK8C41z5jXC0e4MTuFl8wVKccJmar8t9zoyP+LGS4SMAciTd0qKoKVxFCP8pv7mUk/ XkElfgAMf5hO3BFBHWsK4cPS10QQHiXsjntNhFGDiab4JFpTC7+Di50q8XUOETgcy9/9 ICJ+0xWEa/8GJngdmSUirOajZR6uSX23wWTNCJhrUOMNxVIMEmG8YmCUAxztanQpLGdo gqdZpkw6sBulK79NpU6Eu9rqrda4CrvMJV+gDNWavT7P5PUorHhoYsJc0Bw1Ept5bam/ jcfg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=5b/fnZv9u8hWwytN7nE+plTI8m4ReHpaFuqOCjk1Fdo=; b=FegtvFJBMsDdBMlEYLVTg+E7DJudecqkewecFMkvy3ikT241/RjKormAWmNa0Dcet7 VEgVTHvNZtbobdLxGcuNh6FiK/qO9icmbkObkPt+zNBZxHTKeO+z6C+kBcSf+0KvbtDL lienep/AS6aDFacIYjSIaqMOrtbwot1usXBukvNzxKb9qLBPBmj9tB3Iim5xjJAOmqHM sG/qilY77bK0RhNxPoAguZWdVFvXgHhglKiuuCIJwKlLMbTMrf/UIB3GU3kbjyBdiqZG 6g92CNYUKCasmvjoR1GaYLMVYIhB36tZCrkkfM2MwHuvc+BGIjcfd7MDbvpjdKDgEwqU cslA== X-Gm-Message-State: APjAAAV867J9Ms7KIXZ5nWgB3UE+fZBCSF3nTK75qV+nYKEb5DmqTtKO X+c2dtOVczJfx5LplQYuSYBdCXbU0SeZziRAiB19pyuJHig= X-Google-Smtp-Source: APXvYqy28hkfreZqyIAmUPMUoL24NSXtjKqUNaIK19hwBhi3Ggw4VMMJaBqyy4+yPaqqz8SrUEEOOJrn7MegcuanoWg= X-Received: by 2002:adf:dfc4:: with SMTP id q4mr52786288wrn.54.1563516353480; Thu, 18 Jul 2019 23:05:53 -0700 (PDT) MIME-Version: 1.0 From: Mike Brooks Date: Thu, 18 Jul 2019 23:05:42 -0700 Message-ID: To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary="000000000000d99b6e058e02846c" 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: Fri, 19 Jul 2019 13:54:36 +0000 Subject: [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: Fri, 19 Jul 2019 06:05:56 -0000 --000000000000d99b6e058e02846c Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I noticed that this Merkle tree we are building is made more expensive by including repetitive data. So, this proposal draws inspiration from LZ78, an algorithm which constructs a dictionary of repetitive strings which are then referred to by their index. What if the blockchain already built a dictionary for us, and now we just need to index it? --- Abstract This BIP describes how a new OP code can be used to construct smaller, more compact transactions. With a public reference (PubRef), a newly created transaction can reuse elements of a previously confirmed transaction by representing this information with a smaller numeric offset or =E2=80=9Cpoi= nter=E2=80=9D. Motivation Giving scripts the ability to refer to data on the blockchain will reduce transaction sizes because key material does not have to be repeated in every Script. Users of the network are rewarded with smaller transaction sizes, and miners are able to fit more transactions into new blocks. Pointers are a common feature and it felt like this was missing from Bitcoin Script. Specification This BIP defines a new Script opcode that can be introduced with BIP-0141 (Segregated Witness (Consensus layer)). This new opcode is as follows: Word Opcode Hex Input Output Description OP_PUBREF4 TBD TBD uint4 data The next four bytes is an integer reference to a previously defined PUSHDATA Let there be an ordered list of all invocations of PUSHDATA (OP codes; 0x4c,0x4d,0x4e) across all scripts starting from the genesis block: [t0,t2,...,tn]. With this list a newly created script can refer to a specific PUSHDATA that was used in any previously confirmed block. The values referenced by this list are immutable and uniform to all observers. Lets assume there is some transaction containing a ScriptSig and outputScript pair, here is what an input and an output script would look like: ScriptSig PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918= f066269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd3= 42d3101] PUSHDATA (65)[04bca69c59dc7a6d8ef4d3043bdcb626e9e29837b9beb143168938ae8165848bfc788d= 6ff4cdf1ef843e6a9ccda988b323d12a367dd758261dd27a63f18f56ce77] outputScript DUP HASH160 PUSHDATA(20)[dd6cce9f255a8cc17bda8ba0373df8e861cb866e] EQUALVERIFY CHECKSIG The ScriptSig of an input typically contains the full public key which is ~65 bytes. Outputs will typically contain a hash of the public key which is 20 bytes. Using PubRef, the public-key material shown above no longer need to be repeated, instead the needed values can be resolved from previously confirmed transaction. The signature of the input must still be unique, however, the public key can be replaced with a call to PUBREF, as shown below: ScriptSig PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918= f066269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd3= 42d3101] PUBREF[43123] outputScript DUP HASH160 PUBREF[12123] EQUALVERIFY CHECKSIG The above call to PUBREF removed the need to include the full public-key, or hash of the public key in a given transaction. This is only possible because these values where used previously in a confirmed block. If for example a user was sending Bitcoins to a newly formed address, then no PUBREF can be created in this case - and a outputScript using PUSHDATA would need to be used at least once. If a newly created wallet has never been used on the Bitcoin network, then the full public-key will need to be included in the ScriptSig. Once these transactions have been confirmed, then these values will be indexed and any future script can refer to these public-key values with a PUBREF operation. PubRef is not susceptible to malleability attacks because the blockchain is immutable. The PUSHDATA operation can store at most 520 bytes on the stack, therefore a single PUBREF operation can never obtain more than 520 bytes. 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 indexed 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 relieving the need to store repetitive data on the blockchain. --000000000000d99b6e058e02846c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

I noticed= that this Merkle tree we are building is made more expensive by including = repetitive data.=C2=A0 So, this proposal draws inspiration from LZ78, an al= gorithm which constructs a dictionary of repetitive strings which are then = referred to by their index. What if the blockchain already built a dictiona= ry for us, and now we just need to index it?


---


Abstract

This BIP describes how a new OP code can be used to const= ruct smaller, more compact transactions.=C2=A0 With a public reference (Pub= Ref), a newly created transaction can reuse elements of a previously confir= med transaction by representing this information with a smaller numeric off= set or =E2=80=9Cpointer=E2=80=9D.


Motivation

Giving scripts the ability to refer to data on the blockch= ain will reduce transaction sizes because key material does not have to be = repeated in every Script. Users of the network are rewarded with smaller tr= ansaction sizes, and miners are able to fit more transactions into new bloc= ks.=C2=A0 Pointers are a common feature and it felt like this was missing f= rom Bitcoin Script.


Specification


This BIP defines a new Script opcode that can be introduced with = BIP-0141 (Segregated Witness (Consensus layer)). This new opcode is as foll= ows:


=

Opcod= e

<= p dir=3D"ltr" style=3D"line-height:1.38;text-align:center;margin-top:11pt;m= argin-bottom:11pt">Descri= ption

Word

Hex

Input

= Output

OP_PUBREF4

TBD

TBD

uint4

data

The next four by= tes is an integer reference to a previously defined PUSHDATA=C2=A0


Let there be an ordered list of all invocations of PUSHDATA (OP= codes; 0x4c,0x4d,0x4e) across all scripts starting from the genesis block:= [t0,t2,...,tn]. =C2=A0 With this list a newly created script can refer to = a specific PUSHDATA that was used in any previously confirmed block. The v= alues referenced by this list are immutable and uniform to all observers.


Lets assume t= here is some transaction containing a ScriptSig and outputScript pair, here= is what an input and an output script would look like:


ScriptSig

PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918f066= 269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd342d3= 101] PUSHDATA(65)[04bc= a69c59dc7a6d8ef4d3043bdcb626e9e29837b9beb143168938ae8165848bfc788d6ff4cdf1e= f843e6a9ccda988b323d12a367dd758261dd27a63f18f56ce77]

outputScript<= /p>

DUP H= ASH160 PUSHDATA(20)[dd= 6cce9f255a8cc17bda8ba0373df8e861cb866e] EQUALVERIFY CHECKSIG

The ScriptSig of an input typ= ically contains the full public key which is ~65 bytes. Outputs will typica= lly contain a hash of the public key which is 20 bytes.=C2=A0 Using PubRef,= the public-key material shown above no longer need to be repeated, instead= the needed values can be resolved from previously confirmed transaction. = =C2=A0 The signature of the input must still be unique, however, the public= key can be replaced with a call to PUBREF, as shown below:

ScriptSig

PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918f066= 269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd342d3= 101] PUBREF[43123]

o= utputScript

DUP HASH160 PUBREF[12123] EQUALVERIFY CHECKSIG

The above call to PUBREF removed the need to include= the full public-key, or hash of the public key in a given transaction.=C2= =A0 This is only possible because these values where used previously in a c= onfirmed block. If for example a user was sending Bitcoins to a newly form= ed address, then no PUBREF can be created in this case - and a outputScript= using PUSHDATA would need to be used at least once.=C2=A0 If a newly creat= ed wallet has never been used on the Bitcoin network, then the full public-= key will need to be included in the ScriptSig. Once these transactions hav= e been confirmed, then these values will be indexed and any future script c= an refer to these public-key values with a PUBREF operation.


=

= PubRef is not susceptible = to malleability attacks because the blockchain is immutable. The PUSHDATA o= peration can store at most 520 bytes on the stack, therefore a single PUBRE= F operation can never obtain more than 520 bytes.


In order for a client to make use of = the PUBREF operations they=E2=80=99ll need access to a database that look u= p public-keys and resolve their PUBREF index.=C2=A0 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 indexed as an ordered list, resolution of= a PUBREF index to the intended value 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, additional computational effort is needed to= build and maintain these indices - a tradeoff which provides smaller trans= action sizes and relieving the need to store repetitive data on the blockch= ain.

--000000000000d99b6e058e02846c--