Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 7A812CAC for ; Wed, 3 May 2017 19:41:10 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qt0-f179.google.com (mail-qt0-f179.google.com [209.85.216.179]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A1B36F0 for ; Wed, 3 May 2017 19:41:08 +0000 (UTC) Received: by mail-qt0-f179.google.com with SMTP id m36so146774153qtb.0 for ; Wed, 03 May 2017 12:41:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=gKhxNn2FliR/WdI48yvg1Sp9rQ94M39Vh5kbpRgbroc=; b=bvgrSFRyFTMTtLGegT56jOdX2s19IiBXpKRtD6mBbk0Y1vw2EjdqqqNb4Hi+M+8hEW T6ucmmauSprAnQzd/fNsm+tPyO0ZIxdtLikmwOVEFlMcFvPSEJ/dlCmcnciiH2FEERAI hsoNVkedmZij9DP6yih75CddS6AXmbRUIYSrsHSDXsm0OIp51d0vCwgGHcLfxgo/XEtM JyyPwMQxB19PrjWq264bKMVLEMJcTWB9bTYWqhKGYNf1ZRvsINpX/28pBWZpEvY+pu2q 0P4tVxHRasZxeAI8N+zLEC5ikKXT9MnAdlj/MlBFxkhDSQEPnXLYg/y1KuPempxUwH+W oc8g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=gKhxNn2FliR/WdI48yvg1Sp9rQ94M39Vh5kbpRgbroc=; b=ZjKZqeiJjPQDkqMz6EIthMwatuONvr8wfFmYlYKSb6CL78eVA0ekXvo+yh4vm0r3PB 0jWPVk6ipFvdUmxl/HL6t++9tPoRNOjRFr2z+EdT7HebIsMOaT7jdg84AlSt95HR73bA x3Cder3UMCg4qUA2PA1YFDMcVA2iAu7dMukzovhX/WXYnomBzbbC9gOUantA0vPj5blv SqXBVm4chQCVQoTdZ7YUfoJPEZksYQXaiFO27e4/a0Qa5javGWGqbaFS1Lfx4TvNid64 u3GRinZetDztUzEoxpq759iHEcQaYiIcVd+b4uUTljmzDDwImdGLnJbVg0roThs21t0P qFjQ== X-Gm-Message-State: AN3rC/5ZvlwGdE2HmDj9htALUicSDDWytwlrXPc208GaCc1yV21NMJCd faBOVXCVWuyavqRdMUSv6SNGdcuO4NdHaOVNAQ== X-Received: by 10.200.1.26 with SMTP id e26mr8770824qtg.75.1493840467734; Wed, 03 May 2017 12:41:07 -0700 (PDT) MIME-Version: 1.0 Sender: earonesty@gmail.com Received: by 10.200.39.43 with HTTP; Wed, 3 May 2017 12:41:07 -0700 (PDT) In-Reply-To: References: <1492554557.1625.4.camel@mmci.uni-saarland.de> From: Erik Aronesty Date: Wed, 3 May 2017 15:41:07 -0400 X-Google-Sender-Auth: rVwW8qHc7t2ayBckYO-xlbPYqUU Message-ID: To: Tim Ruffing Content-Type: multipart/alternative; boundary=f403045f41ee6e36fc054ea3d6bf X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM 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: Wed, 03 May 2017 19:48:33 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Transaction signalling 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: Wed, 03 May 2017 19:41:10 -0000 --f403045f41ee6e36fc054ea3d6bf Content-Type: text/plain; charset=UTF-8 BIP XXXX : User activated features (ROUGH OVERVIEW) A proposed change to a usage of the 'OP_RETURN' script opcode in Bitcoin transactions, allowing multiple changes (features) to be deployed in parallel. It relies on interpreting the output field as a bit vector, where each bit can be used to track an independent change. Like BIP9, once a consensus change succeeds or times out, there is a "fallow" pause after which the bit can be reused for later changes. ==Motivation== BIP 9 introduced a mechanism for doing soft-forking changes, relying on measuring miner support indicated by version bits in block headers. As it relies on miner support, any change which may conflict with miners but is acceptable to users may be difficult to deploy. The alternative, a flag-day deployment can cause issues for users of a feature that has failed to achieve adequate miner support. BIP XXXX, if used for deployment, can be used in conjunction with BIP 9, in order to more safely deploy soft-forking changes that do not require a supermajority of miners, but do require a large percentage of active users. Alternatively, BIP XXXX signalling can be used to gauge user support for "features" - independent of its use as a direct deployment mechanism. In this document a "feature" can be considered synonymous with "soft fork", but since this mechanism is "user activated", it is not necessarily restricted to soft-forks. ==Specification== Each "feature" is specified by the sames set of per-chain parameters as in BIP9, with the same usage and meaning (name, bit, starttime and timeout). ===Bit flags=== If the outputs contain a zero valued OP_RETURN, and the length of the key is 2 bytes, and if the first byte (prefix) of that OP_RETURN's key parameter is 0x012, then the remaining byte is to be interpreted as an 8-bit little-endian integer, and bits are selected within this integer as values (1 << N) where N is the bit number. This allows up to 8 features to be in the STARTED state at a time. ===Array determination=== In order for this to successfully be used for deployment, a lightweight UTXO must be maintained in memory. For each bit in STARTED state, a corresponding bit is set in a map entry for each input address. Each input address is hashed to a 24 bit value using SHA3-256(input)[0:24]. An array with 16777216 2-byte entries (~32MB RAM) is used to record the current activation state. The first byte contains the bit flags most recently associated with an entry. The second byte contains the log base 2 of the number of "1/100th" bitcoins most recently associated with this entry. This is computed by taking the value, multiplying by 100, converting to an unsigned 32 bit integer, and using the log2_32 function below (.... log2_32 func defined below ....). This array is initialized to zero. The array must be stored and maintained for each block. When a block is in the STARTED state for any bit, the array is updated for each transaction in the block according to the rules above: a[i][0]=bits, a[i][1]=log2_32(....) ===State transitions=== State transitions work the same as BIP9, however, the determination of the LOCKED_IN tally is as follows: For each bit in STARTED state, using the array above, the values are totaled (unsigned int)(2 << a[i][1]) for each entry where this bit is set in a[i][0]. In addition the total of all the entries in a, irrespective of bit, are computed. This can be done in a single pass, resulting in a vector of up to 8 32 bit entries containing the "feature totals" for the array, and one extra 32 bit entry for the sum total of observations since the start time. The percentage of observations is computed for each bit. Up to 8 features can be computed at a time, with reuse similar to BIP9. If 2016 sequential blocks have a value of 95% or greater, a feature is "LOCKED_IN", (75% on testnet) bit. Similar to BIP9, a block's state never depends on its own transactions set; only on that of its ancestors. ACTIVE and FAILED are terminal states, etc. On Thu, Apr 20, 2017 at 12:14 PM, Erik Aronesty wrote: > I agree, addresses create vulnerability, an OP_RETURN signal seems the > safest way to go for UA signalling. I can model a BIP after BIP9, with > some discussion of how to properly collect statistics, and the ability for > nodes to activate features based on an "economic majority" defined in this > way. > > On Tue, Apr 18, 2017 at 6:29 PM, Tim Ruffing via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> I don't have an opinion on whether signaling is a good idea in general. >> >> However I don't think that using addresses is a good idea, because this >> has privacy implications. For example, it makes it much easier to link >> the addresses, e.g., inputs with change address. (The change address >> votes for the same proposal as the input address.) >> >> Tim >> >> On Tue, 2017-04-18 at 18:07 +0000, Christian Decker via bitcoin-dev >> wrote: >> > I really like the idea of extending signalling capabilities to the >> > end-users. It gives stakeholders a voice in the decisions we take in >> > the network, and are a clear signal to all other involved parties. It >> > reminds me of a student thesis I supervised some time ago [1], in >> > which we explored various signalling ideas. >> > >> > I think we have a number of fields that may be used for such a >> > signalling, e.g., OP_RETURN, locktime, and output scripts. I think >> > OP_RETURN is probably not the field you'd want to use though since it >> > adds data that needs to be transferred, stored for bootstrap, and >> > outputs in the UTXO would need to be tagged with additional >> > information. Locktime has the advantage of being mostly a freeform >> > field for values in the past, but it clashes with other uses that may >> > rely on it. Furthermore, it is the transaction creator that specifies >> > the locktime, hence the signal trails one hop behind the current >> > owner, i.e., the actual stakeholder. >> > >> > I think probably the best field to signal would be the output >> > script. It is specified by the recipient of the funds, i.e., the >> > current owner, and is already stored in the UTXO, so a single pass >> > can >> > tally up the votes. We could for example use the last 4 bits of the >> > pubkey/pubkeyhash to opt in (3 leading 0 bits) and the vote (0/1 >> > depending on the stakeholders desired signal). We'd need to define >> > similar semantics for other script types, but getting the standard >> > scripts to be recognized should be simple. >> > >> > In the spirit of full disclosure I'd like to also mention some of the >> > downsides of voting this way. Unlike the OP_RETURN proposal, users >> > that do not intend to signal will also be included in the tally. I'd >> > expect the signals of these users to be random with a 50% chance of >> > either outcome, so they should not influence the final result, but >> > may >> > muddy the water depending on what part of the population is >> > signalling. The opt-in should make sure that the majority of votes >> > are >> > actually voluntary votes, and not just users that randomly select a >> > pubkey/pubkeyhash, and can be adjusted as desired, though higher >> > values require more grinding on behalf of the users. >> > >> > The grinding may also exacerbate some problems we already have with >> > the HD Wallet lookahead, since we now skip a number of addresses, so >> > we should not require too many opt-in bits. >> > >> > So there are some problems we'd need to tackle, but I'm really >> > excited >> > about this, as it could provide data to make informed decisions, and >> > should put an end to the endless speculation about the will of the >> > economic majority. >> > >> > Cheers, >> > Christian >> > >> > [1] http://pub.tik.ee.ethz.ch/students/2015-HS/SA-2015-30.pdf >> > _______________________________________________ >> > bitcoin-dev mailing list >> > bitcoin-dev@lists.linuxfoundation.org >> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > > --f403045f41ee6e36fc054ea3d6bf Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
BIP XXXX : User activated features (ROUGH OVERVIEW)
A proposed change to a usage of the 'OP_RETURN' script opcode= in Bitcoin transactions, allowing multiple changes (features) to be deploy= ed in parallel. It relies on interpreting the output field as a bit vector,= where each bit can be used to track an independent change. Like BIP9, once= a consensus change succeeds or times out, there is a "fallow" pa= use after which the bit can be reused for later changes.

=3D=3DMotiv= ation=3D=3D

BIP 9 introduced a mechanism for doing soft-forking chan= ges, relying on measuring miner support indicated by version bits in block = headers. As it relies on miner support, any change which may conflict with = miners but is acceptable to users may be difficult to deploy.=C2=A0=C2=A0 T= he alternative, a flag-day deployment can cause issues for users of a featu= re that has failed to achieve adequate miner support.=C2=A0=C2=A0

B= IP XXXX, if used for deployment, can be used in conjunction with BIP 9, in = order to more safely deploy soft-forking changes that do not require a supe= rmajority of miners, but do require a large percentage of active users.=C2= =A0

Alternatively, BIP XXXX signalling can be used to gauge user su= pport for "features" - independent of its use as a direct deploym= ent mechanism.=C2=A0=C2=A0 In this document a "feature" can be co= nsidered synonymous with "soft fork", but since this mechanism is= "user activated", it is not necessarily restricted to soft-forks= .

=3D=3DSpecification=3D=3D

Each "feature" is speci= fied by the sames set of per-chain parameters as in BIP9, with the same usa= ge and meaning (name, bit, starttime and timeout).

=3D=3D=3DBit flag= s=3D=3D=3D

If the outputs contain a zero valued OP_RETURN, and the l= ength of the key is 2 bytes, and if the first byte (prefix) of that OP_RETU= RN's key parameter is 0x012, then the remaining byte is to be interpret= ed as an 8-bit little-endian integer, and bits are selected within this int= eger as values (1 << N) where N is the bit number.=C2=A0 This allows = up to 8 features to be in the STARTED state at a time.

=3D=3D=3DArra= y determination=3D=3D=3D

In order for this to successfully be used f= or deployment, a lightweight UTXO must be maintained in memory.=C2=A0=C2=A0= For each bit in STARTED state, a corresponding bit is set in a map entry f= or each input address.=C2=A0=C2=A0 Each input address is hashed to a 24 bit= value using SHA3-256(input)[0:24].=C2=A0 An array with 16777216 2-byte ent= ries (~32MB RAM) is used to record the current activation state.=C2=A0=C2= =A0 The first byte contains the bit flags most recently associated with an = entry.=C2=A0=C2=A0

The second byte contains the log base 2 of the n= umber of "1/100th" bitcoins most recently associated with this en= try.=C2=A0=C2=A0 This is computed by taking the value, multiplying by 100, = converting to an unsigned 32 bit integer, and using the log2_32 function be= low (.... log2_32 func defined below ....).=C2=A0=C2=A0

This array = is initialized to zero.=C2=A0=C2=A0 The array must be stored and maintained= for each block.=C2=A0 When a block is in the STARTED state for any bit, th= e array is updated for each transaction in the block according to the rules= above: a[i][0]=3Dbits, a[i][1]=3Dlog2_32(....)

=3D=3D=3D= State transitions=3D=3D=3D

State transitions work the same as BIP9, = however, the determination of the LOCKED_IN tally is as follows:

For= each bit in STARTED state, using the array above, the values are totaled (= unsigned int)(2 << a[i][1]) for each entry where this bit is set in a= [i][0].=C2=A0 In addition the total of all the entries in a, irrespective o= f bit, are computed.=C2=A0=C2=A0 This can be done in a single pass, resulti= ng in a vector of up to 8 32 bit entries containing the "feature total= s" for the array, and one extra 32 bit entry for the sum total of obse= rvations since the start time.

The percentage of observations is com= puted for each bit.=C2=A0=C2=A0 Up to 8 features can be computed at a time,= with reuse similar to BIP9.=C2=A0=C2=A0

If 2016 sequential blocks = have a value of 95% or greater, a feature is "LOCKED_IN", (75% on= testnet)
bit.

Similar to BIP9, a block's state never depends= on its own transactions set; only on that of its ancestors.=C2=A0 ACTIVE a= nd FAILED are terminal states, etc.


On Thu, Apr 20, 2017 at 12:14 PM, Eri= k Aronesty <erik@q32.com> wrote:
I agree, addresses create vulnerability, an OP_RETU= RN signal seems the safest way to go for UA signalling.=C2=A0=C2=A0 I can m= odel a BIP after BIP9, with some discussion of how to properly collect stat= istics, and the ability for nodes to activate features based on an "ec= onomic majority" defined in this way.

On Tue, Apr 18, 2017 at 6:29 PM, Tim Ruffing via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wro= te:
I don't have an opinion on whethe= r signaling is a good idea in general.

However I don't think that using addresses is a good idea, because this=
has privacy implications. For example, it makes it much easier to link
the addresses, e.g., inputs with change address. (The change address
votes for the same proposal as the input address.)

Tim

On Tue, 2017-04-18 at 18:07 +0000, Christian Decker via bitcoin-dev
wrote:
> I really like the idea of extending signalling capabilities to = the
> end-users. It gives stakeholders a voice in the decisions we take in > the network, and are a clear signal to all other involved parties. It<= br> > reminds me of a student thesis I supervised some time ago [1], in
> which we explored various signalling ideas.
>
> I think we have a number of fields that may be used for such a
> signalling, e.g., OP_RETURN, locktime, and output scripts. I think
> OP_RETURN is probably not the field you'd want to use though since= it
> adds data that needs to be transferred, stored for bootstrap, and
> outputs in the UTXO would need to be tagged with additional
> information. Locktime has the advantage of being mostly a freeform
> field for values in the past, but it clashes with other uses that may<= br> > rely on it. Furthermore, it is the transaction creator that specifies<= br> > the locktime, hence the signal trails one hop behind the current
> owner, i.e., the actual stakeholder.
>
> I think probably the best field to signal would be the output
> script. It is specified by the recipient of the funds, i.e., the
> current owner, and is already stored in the UTXO, so a single pass
> can
> tally up the votes. We could for example use the last 4 bits of the > pubkey/pubkeyhash to opt in (3 leading 0 bits) and the vote (0/1
> depending on the stakeholders desired signal). We'd need to define=
> similar semantics for other script types, but getting the standard
> scripts to be recognized should be simple.
>
> In the spirit of full disclosure I'd like to also mention some of = the
> downsides of voting this way. Unlike the OP_RETURN proposal, users
> that do not intend to signal will also be included in the tally. I'= ;d
> expect the signals of these users to be random with a 50% chance of > either outcome, so they should not influence the final result, but
> may
> muddy the water depending on what part of the population is
> signalling. The opt-in should make sure that the majority of votes
> are
> actually voluntary votes, and not just users that randomly select a > pubkey/pubkeyhash, and can be adjusted as desired, though higher
> values require more grinding on behalf of the users.
>
> The grinding may also exacerbate some problems we already have with > the HD Wallet lookahead, since we now skip a number of addresses, so > we should not require too many opt-in bits.
>
> So there are some problems we'd need to tackle, but I'm really=
> excited
> about this, as it could provide data to make informed decisions, and > should put an end to the endless speculation about the will of the
> economic majority.
>
> Cheers,
> Christian
>
> [1] http://pub.tik.ee.ethz.ch/students/2015-HS/SA-2015-30.pdf
> ______________________________________________= _
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


--f403045f41ee6e36fc054ea3d6bf--