From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id E07BB256 for ; Thu, 19 May 2016 04:18:17 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-vk0-f49.google.com (mail-vk0-f49.google.com [209.85.213.49]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D1FF71AD for ; Thu, 19 May 2016 04:18:16 +0000 (UTC) Received: by mail-vk0-f49.google.com with SMTP id c189so88042606vkb.1 for ; Wed, 18 May 2016 21:18:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to; bh=7CtH+gLb7sO7ftA0NBzmTQQk+5pgaKa98+eJ3iBEfWM=; b=nPIpvmMJNyKMUJEXvUoJeD4iBZDJPPgw5CLhF0sj4iRqAJp4vuAL6LTmMfp6FdIloX ceywmM0oG2Q6X2aDWH3KhMJlm//c6xomgmPgFKgNgKQx/fleB4sjEuNn3mEco5uco7VK 0ueMP82AgMmnDPzImOMx1vPQnN3PNMe0ZfG5gm7wRZWTDw4XS7pcgQ774jOHFAMK3s0H aLWRfoVfzdoMjQ+bpZ7Gz9ihbOOKF46Yvanr5ahK6LEmfMgbOonBFocgKqFtqLj1cEKh slJSybcJ5s6o6NxpYynEMCb2M7YgvzbwjjjXPVwajtYmhxsDo0kSALugCPY+T3eYQ+5W 6rDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to; bh=7CtH+gLb7sO7ftA0NBzmTQQk+5pgaKa98+eJ3iBEfWM=; b=NUsWhpoZ+XrMQ9CCi9oGpjbItAtYPw15OvQhy8J6divsx3igcQrp4U9wuSSLeSnsxY yPEAzKGO0qaqE15bDXELPPCs/sL6hi14AoS2BN94lUmJoAkg0KSDbPsgjIxlGTwzG2er DVF///NciYP5oeMz3RvBBDHbPujOotQmaF3EKaTj0f/mkyn1mWDMCKtdouzfWmujRy0m 76TMSR7tF7wO6043JX/Wguy2jKk5pvl1uxUuQK5LsQjevATR7CASHR8kwXRDKs35JK+d zCK8srDMG87XlWK7t7hruMQdp5o2IfZDJ7/eSW2gPtodG0z9NfNEFVzDgnmI8//TjdE1 EPkQ== X-Gm-Message-State: AOPr4FX2VAQinC8NqCgH5vGCV0UvNyhykWgNMP45ThjoVZAKXhGj4NAj+MM0D7Ni7mWJYuY6WdRF40XD1uO5xg== MIME-Version: 1.0 X-Received: by 10.159.33.179 with SMTP id 48mr5339163uac.14.1463631495886; Wed, 18 May 2016 21:18:15 -0700 (PDT) Received: by 10.176.64.225 with HTTP; Wed, 18 May 2016 21:18:15 -0700 (PDT) In-Reply-To: References: Date: Thu, 19 May 2016 00:18:15 -0400 Message-ID: From: Kristov Atlas To: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a113aa96264fd5205332a43cd X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW 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: Thu, 19 May 2016 10:15:02 +0000 Subject: Re: [bitcoin-dev] RFC for BIP: Best Practices for Heterogeneous Input Script Transactions 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: Thu, 19 May 2016 04:18:18 -0000 --001a113aa96264fd5205332a43cd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable I've updated the language of the BIP. New version: 
  BIP: TBD
  Title: Best Practices for Heterogeneous Input Script Transactions
  Author: Kristov Atlas 
  Status: Draft
  Type: Informational
  Created: 2016-02-10
=3D=3DAbstract=3D=3D The privacy of Bitcoin users with respect to graph analysis is reduced when a transaction is created that contains inputs composed from different scripts. However, creating such transactions is often unavoidable. This document proposes a set of best practice guidelines which minimize the adverse privacy consequences of such unavoidable transaction situations while simultaneously maximising the effectiveness of user protection protocols. =3D=3DCopyright=3D=3D This BIP is in the public domain. =3D=3DDefinitions=3D=3D * '''Heterogenous input script transaction (HIT)''': A transaction containing multiple inputs where not all inputs have identical scripts (e.g. a transaction spending from more than one Bitcoin address) * '''Unavoidable heterogenous input script transaction''': An HIT created as a result of a user=E2=80=99s desire to create a new output with a value = larger than the value of his wallet's largest existing unspent output * '''Intentional heterogenous input script transaction''': An HIT created as part of a user protection protocol for reducing uncontrolled disclosure of personally-identifying information (PII) =3D=3DMotivations=3D=3D The recommendations in this document are designed to accomplish three goals= : # Maximise the effectiveness of user-protecting protocols: Users may find that protection protocols are counterproductive if such transactions have a distinctive fingerprint which renders them ineffective. # Minimise the adverse consequences of unavoidable heterogenous input transactions: If unavoidable HITs are indistinguishable from intentional HITs, a user creating an unavoidable HIT benefits from ambiguity with respect to graph analysis. # Limiting the effect on UTXO set growth: To date, non-standardized intentional HITs tend to increase the network's UTXO set with each transaction; this standard attempts to minimize this effect by standardizing unavoidable and intentional HITs to limit UTXO set growth. In order to achieve these goals, this specification proposes a set of best practices for heterogenous input script transaction creation. These practices accommodate all applicable requirements of both intentional and unavoidable HITs while maximising the effectiveness of both in terms of preventing uncontrolled disclosure of PII. In order to achieve this, two forms of HIT are proposed: Standard form and alternate form. =3D=3DStandard form heterogenous input script transaction=3D=3D =3D=3D=3DRules=3D=3D=3D An HIT is Standard form if it adheres to all of the following rules: # The number of unique output scripts must be equal to the number of unique inputs scripts (irrespective of the number of inputs and outputs). # All output scripts must be unique. # At least one pair of outputs must be of equal value. # The largest output in the transaction is a member of a set containing at least two identically-sized outputs. =3D=3D=3DRationale=3D=3D=3D The requirement for equal numbers of unique input/output scripts instead of equal number of inputs/outputs accommodates user-protecting UTXO selection behavior. Wallets may contain spendable outputs with identical scripts due to intentional or accidental address reuse, or due to dusting attacks. In order to minimise the adverse consequences of address reuse, any time a UTXO is included in a transaction as an input, all UTXOs with the same spending script should also be included in the transaction. The requirement that all output scripts are unique prevents address reuse. Restricting the number of outputs to the number of unique input scripts prevents this policy from growing the network=E2=80=99s UTXO set. A standar= d form HIT transaction will always have a number of inputs greater than or equal to the number of outputs. The requirement for at least one pair of outputs in an intentional HIT to be of equal value results in optimal behavior, and causes intentional HITs to resemble unavoidable HITs. =3D=3DAlternate form heterogenous input script transactions=3D=3D The formation of a standard form HIT is not possible in the following cases= : # The HIT is unavoidable, and the user=E2=80=99s wallet contains an insuffi= cient number or size of UTXOs to create a standard form HIT. # The user wishes to reduce the number of utxos in their wallet, and does not have any sets of utxos with identical scripts. When one of the following cases exist, a compliant implementation may create an alternate form HIT by constructing a transaction as follows: =3D=3D=3DProcedure=3D=3D=3D # Find the smallest combination of inputs whose value is at least the value of the desired spend. ## Add these inputs to the transaction. ## Add a spend output to the transaction. ## Add a change output to the transaction containing the difference between the current set of inputs and the desired spend. # Repeat step 1 to create a second spend output and change output. # Adjust the change outputs as necessary to pay the desired transaction fee= . Clients which create intentional HITs must have the capability to form alternate form HITs, and must do so for a non-zero fraction of the transactions they create. =3D=3DNon-compliant heterogenous input script transactions=3D=3D If a user wishes to create an output that is larger than half the total size of their spendable outputs, or if their inputs are not distributed in a manner in which the alternate form procedure can be completed, then the user can not create a transaction which is compliant with this procedure. --001a113aa96264fd5205332a43cd Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I've updated the language of the BIP. New version:
<pre>
=C2=A0 BIP: TBD
=C2=A0= Title: Best Practices for Heterogeneous Input Script Transactions
=C2=A0 Author: Kristov Atlas <kristov@openbitcoinprivacyproject.org>
= =C2=A0 Status: Draft
=C2=A0 Type: Informational
=C2=A0 = Created: 2016-02-10
</pre>

=3D=3DA= bstract=3D=3D

The privacy of Bitcoin users with re= spect to graph analysis is reduced when a transaction is created that conta= ins inputs composed from different scripts. However, creating such transact= ions is often unavoidable.

This document proposes = a set of best practice guidelines which minimize the adverse privacy conseq= uences of such unavoidable transaction situations while simultaneously maxi= mising the effectiveness of user protection protocols.

=
=3D=3DCopyright=3D=3D

This BIP is in the publ= ic domain.

=3D=3DDefinitions=3D=3D

<= /div>
* '''Heterogenous input script transaction (HIT)'= '': A transaction containing multiple inputs where not all inputs h= ave identical scripts (e.g. a transaction spending from more than one Bitco= in address)
* '''Unavoidable heterogenous input scrip= t transaction''': An HIT created as a result of a user=E2=80=99= s desire to create a new output with a value larger than the value of his w= allet's largest existing unspent output
* '''Inte= ntional heterogenous input script transaction''': An HIT create= d as part of a user protection protocol for reducing uncontrolled disclosur= e of personally-identifying information (PII)

=3D= =3DMotivations=3D=3D

The recommendations in this d= ocument are designed to accomplish three goals:

# = Maximise the effectiveness of user-protecting protocols: Users may find tha= t protection protocols are counterproductive if such transactions have a di= stinctive fingerprint which renders them ineffective.
# Minimise = the adverse consequences of unavoidable heterogenous input transactions: If= unavoidable HITs are indistinguishable from intentional HITs, a user creat= ing an unavoidable HIT benefits from ambiguity with respect to graph analys= is.
# Limiting the effect on UTXO set growth: To date, non-standa= rdized intentional HITs tend to increase the network's UTXO set with ea= ch transaction; this standard attempts to minimize this effect by standardi= zing unavoidable and intentional HITs to limit UTXO set growth.
<= br>
In order to achieve these goals, this specification proposes = a set of best practices for heterogenous input script transaction creation.= These practices accommodate all applicable requirements of both intentiona= l and unavoidable HITs while maximising the effectiveness of both in terms = of preventing uncontrolled disclosure of PII.

In o= rder to achieve this, two forms of HIT are proposed: Standard form and alte= rnate form.

=3D=3DStandard form heterogenous input= script transaction=3D=3D

=3D=3D=3DRules=3D=3D=3D<= /div>

An HIT is Standard form if it adheres to all of th= e following rules:

# The number of unique output s= cripts must be equal to the number of unique inputs scripts (irrespective o= f the number of inputs and outputs).
# All output scripts must be= unique.
# At least one pair of outputs must be of equal value.
# The largest output in the transaction is a member of a set conta= ining at least two identically-sized outputs.

=3D= =3D=3DRationale=3D=3D=3D

The requirement for equal= numbers of unique input/output scripts instead of equal number of inputs/o= utputs accommodates user-protecting UTXO selection behavior. Wallets may co= ntain spendable outputs with identical scripts due to intentional or accide= ntal address reuse, or due to dusting attacks. In order to minimise the adv= erse consequences of address reuse, any time a UTXO is included in a transa= ction as an input, all UTXOs with the same spending script should also be i= ncluded in the transaction.

The requirement that a= ll output scripts are unique prevents address reuse. Restricting the number= of outputs to the number of unique input scripts prevents this policy from= growing the network=E2=80=99s UTXO set. A standard form HIT transaction wi= ll always have a number of inputs greater than or equal to the number of ou= tputs.

The requirement for at least one pair of ou= tputs in an intentional HIT to be of equal value results in optimal behavio= r, and causes intentional HITs to resemble unavoidable HITs.

=
=3D=3DAlternate form heterogenous input script transactions=3D= =3D

The formation of a standard form HIT is not po= ssible in the following cases:

# The HIT is unavoi= dable, and the user=E2=80=99s wallet contains an insufficient number or siz= e of UTXOs to create a standard form HIT.
# The user wishes to re= duce the number of utxos in their wallet, and does not have any sets of utx= os with identical scripts.

When one of the followi= ng cases exist, a compliant implementation may create an alternate form HIT= by constructing a transaction as follows:

=3D=3D= =3DProcedure=3D=3D=3D

# Find the smallest combinat= ion of inputs whose value is at least the value of the desired spend.
=
## Add these inputs to the transaction.
## Add a spend outpu= t to the transaction.
## Add a change output to the transaction c= ontaining the difference between the current set of inputs and the desired = spend.
# Repeat step 1 to create a second spend output and change= output.
# Adjust the change outputs as necessary to pay the desi= red transaction fee.

Clients which create intentio= nal HITs must have the capability to form alternate form HITs, and must do = so for a non-zero fraction of the transactions they create.

<= /div>
=3D=3DNon-compliant heterogenous input script transactions=3D=3D<= /div>

If a user wishes to create an output that is large= r than half the total size of their spendable outputs, or if their inputs a= re not distributed in a manner in which the alternate form procedure can be= completed, then the user can not create a transaction which is compliant w= ith this procedure.

--001a113aa96264fd5205332a43cd--