MIME-Version: 1.0
In-Reply-To: <CAGH37SLBesCESaAY60UUc=B=0szZjL1KS6=oqWDBeTbdYKqEfw@mail.gmail.com>
References: <CAGH37SKQ_Ny1WjgosNUvObkD0PSyKmLdt4ejHb4f-AM+n4LLUQ@mail.gmail.com>
	<CAGH37SLBesCESaAY60UUc=B=0szZjL1KS6=oqWDBeTbdYKqEfw@mail.gmail.com>
Date: Mon, 23 May 2016 18:44:05 +0100
Message-ID: <CAFkJPWLGLMKxipLD1F4cXb=x9yst3RJ4PygEgZ4Yw+JQRgVPBQ@mail.gmail.com>
From: "T. DeV D" <dev@samouraiwallet.com>
To: Kristov Atlas <kristovatlas.lists@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=94eb2c0c035ea81554053385fc26
Subject: Re: [bitcoin-dev] RFC for BIP: Best Practices for Heterogeneous
 Input Script Transactions
Precedence: list

--94eb2c0c035ea81554053385fc26
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

ACK

We have already started work on Coinjoin simulated transactions and are
very interested in working on an implementation of this proposal with a
view towards making wallet footprints less identifiable.

On Thu, May 19, 2016 at 5:18 AM, Kristov Atlas via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I've updated the language of the BIP. New version:
>
> <pre>
>   BIP: TBD
>   Title: Best Practices for Heterogeneous Input Script Transactions
>   Author: Kristov Atlas <kristov@openbitcoinprivacyproject.org>
>   Status: Draft
>   Type: Informational
>   Created: 2016-02-10
> </pre>
>
> =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 differen=
t
> 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 situatio=
ns
> 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 valu=
e 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 disclosur=
e
> 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 bes=
t
> 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 an=
d
> 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 a=
t
> 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 stand=
ard 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 HIT=
s
> 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 insuf=
ficient
> 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 i=
n
> 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.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>


--=20

dev@samouraiwallet.com

PGP public key fingerprint:

ED1A 1280 DEFC A603 14CD  15BF 72B5 BACD FEDF 39D7

--94eb2c0c035ea81554053385fc26
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">ACK<div><br></div><div>We have already started work on Coi=
njoin simulated transactions and are very interested in working on an imple=
mentation of this proposal with a view towards making wallet footprints les=
s identifiable.</div></div><div class=3D"gmail_extra"><br><div class=3D"gma=
il_quote">On Thu, May 19, 2016 at 5:18 AM, Kristov Atlas via bitcoin-dev <s=
pan dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org=
" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wr=
ote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border=
-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">I&#39;ve updated th=
e language of the BIP. New version:<div><br></div><div><div>&lt;pre&gt;</di=
v><span class=3D""><div>=C2=A0 BIP: TBD</div><div>=C2=A0 Title: Best Practi=
ces for Heterogeneous Input Script Transactions</div><div>=C2=A0 Author: Kr=
istov Atlas &lt;<a href=3D"mailto:kristov@openbitcoinprivacyproject.org" ta=
rget=3D"_blank">kristov@openbitcoinprivacyproject.org</a>&gt;</div><div>=C2=
=A0 Status: Draft</div><div>=C2=A0 Type: Informational</div><div>=C2=A0 Cre=
ated: 2016-02-10</div></span><div>&lt;/pre&gt;</div><div><br></div><div>=3D=
=3DAbstract=3D=3D</div><div><br></div><div>The privacy of Bitcoin users wit=
h respect to graph analysis is reduced when a transaction is created that c=
ontains inputs composed from different scripts. However, creating such tran=
sactions is often unavoidable.</div><div><br></div><div>This document propo=
ses a set of best practice guidelines which minimize the adverse privacy co=
nsequences of such unavoidable transaction situations while simultaneously =
maximising the effectiveness of user protection protocols.</div><div><br></=
div><div>=3D=3DCopyright=3D=3D</div><span class=3D""><div><br></div><div>Th=
is BIP is in the public domain.</div><div><br></div></span><div>=3D=3DDefin=
itions=3D=3D</div><div><br></div><div>* &#39;&#39;&#39;Heterogenous input s=
cript transaction (HIT)&#39;&#39;&#39;: A transaction containing multiple i=
nputs where not all inputs have identical scripts (e.g. a transaction spend=
ing from more than one Bitcoin address)</div><div>* &#39;&#39;&#39;Unavoida=
ble heterogenous input script transaction&#39;&#39;&#39;: An HIT created as=
 a result of a user=E2=80=99s desire to create a new output with a value la=
rger than the value of his wallet&#39;s largest existing unspent output</di=
v><div>* &#39;&#39;&#39;Intentional heterogenous input script transaction&#=
39;&#39;&#39;: An HIT created as part of a user protection protocol for red=
ucing uncontrolled disclosure of personally-identifying information (PII)</=
div><div><br></div><div>=3D=3DMotivations=3D=3D</div><span class=3D""><div>=
<br></div><div>The recommendations in this document are designed to accompl=
ish three goals:</div><div><br></div></span><div># Maximise the effectivene=
ss of user-protecting protocols: Users may find that protection protocols a=
re counterproductive if such transactions have a distinctive fingerprint wh=
ich renders them ineffective.</div><div># Minimise the adverse consequences=
 of unavoidable heterogenous input transactions: If unavoidable HITs are in=
distinguishable from intentional HITs, a user creating an unavoidable HIT b=
enefits from ambiguity with respect to graph analysis.</div><div># Limiting=
 the effect on UTXO set growth: To date, non-standardized intentional HITs =
tend to increase the network&#39;s UTXO set with each transaction; this sta=
ndard attempts to minimize this effect by standardizing unavoidable and int=
entional HITs to limit UTXO set growth.</div><div><br></div><div>In order t=
o achieve these goals, this specification proposes a set of best practices =
for heterogenous input script transaction creation. These practices accommo=
date all applicable requirements of both intentional and unavoidable HITs w=
hile maximising the effectiveness of both in terms of preventing uncontroll=
ed disclosure of PII.</div><span class=3D""><div><br></div><div>In order to=
 achieve this, two forms of HIT are proposed: Standard form and alternate f=
orm.</div><div><br></div></span><div>=3D=3DStandard form heterogenous input=
 script transaction=3D=3D</div><div><br></div><div>=3D=3D=3DRules=3D=3D=3D<=
/div><span class=3D""><div><br></div><div>An HIT is Standard form if it adh=
eres to all of the following rules:</div><div><br></div></span><div># The n=
umber of unique output scripts must be equal to the number of unique inputs=
 scripts (irrespective of the number of inputs and outputs).</div><div># Al=
l output scripts must be unique.</div><div># At least one pair of outputs m=
ust be of equal value.</div><div># The largest output in the transaction is=
 a member of a set containing at least two identically-sized outputs.</div>=
<div><br></div><div>=3D=3D=3DRationale=3D=3D=3D</div><div><br></div><div>Th=
e requirement for equal numbers of unique input/output scripts instead of e=
qual number of inputs/outputs accommodates user-protecting UTXO selection b=
ehavior. Wallets may contain spendable outputs with identical scripts due t=
o intentional or accidental address reuse, or due to dusting attacks. In or=
der 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.</div><span class=3D""><d=
iv><br></div><div>The requirement that all output scripts are unique preven=
ts 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 will always have a number of inputs g=
reater than or equal to the number of outputs.</div><div><br></div></span><=
div>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 HI=
Ts to resemble unavoidable HITs.</div><div><br></div><div>=3D=3DAlternate f=
orm heterogenous input script transactions=3D=3D</div><span class=3D""><div=
><br></div><div>The formation of a standard form HIT is not possible in the=
 following cases:</div><div><br></div></span><div># The HIT is unavoidable,=
 and the user=E2=80=99s wallet contains an insufficient number or size of U=
TXOs to create a standard form HIT.</div><div># The user wishes to reduce t=
he number of utxos in their wallet, and does not have any sets of utxos wit=
h identical scripts.</div><span class=3D""><div><br></div><div>When one of =
the following cases exist, a compliant implementation may create an alterna=
te form HIT by constructing a transaction as follows:</div><div><br></div><=
/span><div>=3D=3D=3DProcedure=3D=3D=3D</div><div><br></div><div># Find the =
smallest combination of inputs whose value is at least the value of the des=
ired spend.</div><div>## Add these inputs to the transaction.</div><div>## =
Add a spend output to the transaction.</div><div>## Add a change output to =
the transaction containing the difference between the current set of inputs=
 and the desired spend.</div><div># Repeat step 1 to create a second spend =
output and change output.</div><div># Adjust the change outputs as necessar=
y to pay the desired transaction fee.</div><span class=3D""><div><br></div>=
<div>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 transac=
tions they create.</div><div><br></div></span><div>=3D=3DNon-compliant hete=
rogenous input script transactions=3D=3D</div><span class=3D""><div><br></d=
iv><div>If a user wishes to create an output that is larger than half the t=
otal size of their spendable outputs, or if their inputs are not distribute=
d 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 procedur=
e.</div></span></div><div><br></div></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br><br clear=3D"all"><div><br></div>-- <br><div cla=
ss=3D"gmail_signature"><div dir=3D"ltr"><div><div dir=3D"ltr"><div dir=3D"l=
tr"><pre style=3D"color:rgb(0,0,0)"></pre><pre style=3D"color:rgb(0,0,0)"><=
a href=3D"mailto:dev@samouraiwallet.com" style=3D"font-family:arial,sans-se=
rif;font-size:13px" target=3D"_blank">dev@samouraiwallet.com</a></pre><pre =
style=3D"color:rgb(0,0,0)">PGP public key fingerprint:</pre><pre style=3D"c=
olor:rgb(0,0,0)">ED1A 1280 DEFC A603 14CD  15BF 72B5 BACD FEDF 39D7</pre><p=
re style=3D"color:rgb(0,0,0)"><br></pre></div></div></div></div></div>
</div>

--94eb2c0c035ea81554053385fc26--