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 4AA4AE7A for ; Wed, 10 Feb 2016 21:36:08 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ob0-f176.google.com (mail-ob0-f176.google.com [209.85.214.176]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 461A9B0 for ; Wed, 10 Feb 2016 21:36:06 +0000 (UTC) Received: by mail-ob0-f176.google.com with SMTP id wb13so48151439obb.1 for ; Wed, 10 Feb 2016 13:36:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=d010QR1yrIYpTgsdJ2chlx4z8kyeIHLZbw3chN0zt9g=; b=l1hMsFHby0vKJkz9NW1GzWKBz/zQjUSzwzSgbRCQ6omSj5/U0PcJpkuDw1Pg21ZqJA XWTH1dii4c1//gxCzfqMOiEGsncyqgRbzh9BvELfukVVZSCibRHhTr1w7wFuOI8ey5te 2tbQiQ2R76iDm6UXeD1Tfd2i9UBOgGbH/62mDYsMwaGJLRnZ2BM7Us9SjFSpy7nOSvJZ KWm2JG5P87fISmyTfR1b58Dk8nnFqBe9hDebMNACC38vrY7hhk+LFEBW0uMu9+ujxo/f I9WVJWgbG1IwafSVlNTZ+Dp8dVRMVP6U6dhgBiijjXyoURbGy7cP4D5muSBrTYzw2skq CPXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to :content-type; bh=d010QR1yrIYpTgsdJ2chlx4z8kyeIHLZbw3chN0zt9g=; b=SWoG/NbZAFIQD5zxu5Z1oj+QVFMdubxlb91k2hQjtaFi7ebtWw4Sg81e4m2lK/2Gv4 g9vJOPmE3XikAvVMJkJ9de9K1JYVcnWLrONAcnIhPnag0JQvjCc5UU4O/sgI8hTqjv83 EcI0yVTkhNMmKPq0gj4YTn+NdVp5NscWT9ffmwL+gycI1sXVpBfK49V6PQj12TGMK28c bdDqoZfJSSDqF+A8RR2O6YWeHtnoIsVHujg9SvxvJb0zbM49lCTct8WZPlLXmDDnu3tR AQ64OYTdweYviYOqKLBu5gmhDKWemCaeMiLzj0+fb9ck1+BycgWqgcuVLMKY+wt6YDL0 u+Bg== X-Gm-Message-State: AG10YOSBe+OlJN+0td0UarXGpplOkQYikaDDShIWkqJ5bgyMz34oc2N/8Yfi1Kvtjf+ZTmtK0T7SjAS9+4gUHw== MIME-Version: 1.0 X-Received: by 10.60.46.102 with SMTP id u6mr42362370oem.78.1455140165556; Wed, 10 Feb 2016 13:36:05 -0800 (PST) Received: by 10.202.235.15 with HTTP; Wed, 10 Feb 2016 13:36:05 -0800 (PST) Date: Wed, 10 Feb 2016 16:36:05 -0500 Message-ID: From: Kristov Atlas To: Bitcoin Dev Content-Type: multipart/alternative; boundary=089e01294798aaa26f052b713832 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: Wed, 10 Feb 2016 21:59:02 +0000 Subject: [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 Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 10 Feb 2016 21:36:08 -0000 --089e01294798aaa26f052b713832 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable BIP: TBD Title: Best Practices for Heterogeneous Input Script Transactions Author: Kristov Atlas Status: Draft Type: Informational Created: 2016-02-10 # Abstract The privacy of Bitcoin users with respect to graph analysis is reduced when a transaction is created that merges 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 privacy-improving techniques such as CoinJoin. # Copyright This BIP is in the public domain. # Definitions 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 large= r than the value of his wallet's largest unspent output Intentional heterogenous input script transaction: An HIT created as part of a protocol for improving user privacy against graph analysis, such as CoinJoin # Motivations The recommendations in this document are designed to accomplish three goals= : 1. Maximise the effectiveness of privacy-enhancing transactions: Privacy-sensitive users may find that techniques such as CoinJoin are counterproductive if such transactions have a distinctive fingerprint which enables them to be censored or subjected to additional scrutiny. 2. Minimise the adverse privacy 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. 3. 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 and render the two types indistinguishable to the maximum extent possible. In order to achieve this, two forms of HIT are proposed: Standard form and alternate form. # Standard form heterogenous input script transaction ## Rules An HIT is Standard form if it adheres to all of the following rules: 1. The number of unique output scripts must be equal to the number of unique inputs scripts (irrespective of the number of inputs and outputs). 2. All output scripts must be unique. 3. At least one pair of outputs must be of equal value. 4. The largest output in the transaction is a member of a set containing at least two identically-sized outputs. ## Rationale The requirement for equal numbers of unique input/output scripts instead of equal number of inputs/outputs accommodates privacy-enhancing 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 privacy 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 to be of equal value results in optimal join transactions, and causes intentional HITs to resemble unavoidable HITs. Outside controlled laboratory conditions, join transactions will not involve identically-sized inputs due to a lack of accommodating volume. Without the ability to cryptographically blind output values on the blockchain, every join transaction leaks information in the form of output sizes. Requiring a pair of identically sized outputs creates the desired ambiguity for spend outputs, but in most cases makes change outputs linkable to inputs. # Alternate form heterogenous input script transactions 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 insuffici= ent 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: ## Procedure 1. Find the smallest combination of inputs whose value is at least the value of the desired spend. i. Add these inputs to the transaction. ii. Add a spend output to the transaction. iii. Add a change output to the transaction containing the difference between the current set of inputs and the desired spend. 2. Repeat step 1 to create a second spend output and change output. 3. 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. # Non-compliant heterogenous input script transactions 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. ---- A working draft of this document is here: https://github.com/OpenBitcoinPrivacyProject/rfc/blob/master/bips/obpp-03.m= ediawiki A few points of anticipated discussion: 1. It's possible for a CoinJoin transaction to decrease privacy by adhering to the Standard Form in this BIP, depending on the utxos available for creating it. For example, a typical two-person CoinJoin might look like: input_A, input_B =3D> spend_A, change_A, spend_B, change_B In order to comply with the standard form, one or more parties would have to add inputs to make this something like: input_A_1, input_A_2, input_B_1, input_B_2 =3D> spend_A, change_A, spend_B, change_B. If spend_A and spend_B are the same value, then input_A_1 and input_A_2 may be linked based on the value of change_A and input_B_1 and input_B_2 may be linked based on the value of change_B via sudoku analysis. In that situation, wallets can opt to use the alternate form instead, or stick with the standard form but enjoy a non-utxo set increase and a significantly increased inter-transactional privacy set from other BIP adherents. 2. In a naive simulation of a wallet randomly containing 1 to 10 utxos of random value 1 to 10 and a desired spend of random value between 1 and the sum of the utxos, the simulated wallet is able to create an alternate form HIT 40% of the time. If we assume that half of all desire spends are a value half or less of the total wallet balance, this improves to around 60%. Unfortunately, I don't have any good data on what values are found in average wallets and what desired spends look like on average. 3. In the long-run it's better for all clients to participant in CoinJoin-like operations, but this should significantly increase the cost and decrease the signal of passive blockchain analysis attacks until that becomes feasible. Thanks in advance for your feedback. --089e01294798aaa26f052b713832 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
BIP: TBD
Title: Best Practices for Heter= ogeneous Input Script Transactions
Author: Kristov Atlas=C2=A0 <kristov@openbitcoinpriv= acyproject.org>
Status: Draft
Type: Informational
Created: = 2016-02-10

# Abstract

The privacy of Bitcoin users with respe= ct to graph analysis is reduced when a transaction is created that merges i= nputs 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 unavoida= ble transaction situations while simultaneously maximising the effectivenes= s of privacy-improving techniques such as CoinJoin.

# Copyright
<= br>This BIP is in the public domain.

# Definitions

Heterogeno= us input script transaction (HIT): A transaction containing multiple inputs= where not all inputs have identical scripts (e.g. a transaction spending f= rom more than one Bitcoin address)
Unavoidable heterogenous input script= transaction: An HIT created as a result of a user=E2=80=99s desire to crea= te a new output with a value larger than the value of his wallet's larg= est unspent output
Intentional heterogenous input script transaction: An= HIT created as part of a protocol for improving user privacy against graph= analysis, such as CoinJoin

# Motivations

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

1. Maximis= e the effectiveness of privacy-enhancing transactions: Privacy-sensitive us= ers may find that techniques such as CoinJoin are counterproductive if such= transactions have a distinctive fingerprint which enables them to be censo= red or subjected to additional scrutiny.
2. Minimise the adverse privacy= consequences of unavoidable heterogenous input transactions: If unavoidabl= e HITs are indistinguishable from intentional HITs, a user creating an unav= oidable HIT benefits from ambiguity with respect to graph analysis.
3. L= imiting the effect on UTXO set growth: To date, non-standardized intentiona= l HITs tend to increase the network's UTXO set with each transaction; t= his 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 heterogenou= s input script transaction creation. These practices accommodate all applic= able requirements of both intentional and unavoidable HITs and render the t= wo types indistinguishable to the maximum extent possible.
In order to a= chieve this, two forms of HIT are proposed: Standard form and alternate for= m.

# Standard form heterogenous input script transaction

## R= ules

An HIT is Standard form if it adheres to all of the following r= ules:

1. The number of unique output scripts must be equal to the nu= mber of unique inputs scripts (irrespective of the number of inputs and out= puts).
2. All output scripts must be unique.
3. At least one pair of = outputs must be of equal value.
4. The largest output in the transaction= is a member of a set containing at least two identically-sized outputs.
## Rationale

The requirement for equal numbers of unique input/= output scripts instead of equal number of inputs/outputs accommodates priva= cy-enhancing 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 privacy consequenc= es of address reuse, any time a UTXO is included in a transaction as an inp= ut, all UTXOs with the same spending script should also be included in the = transaction.

The requirement that all output scripts are unique prev= ents address reuse. Restricting the number of outputs to the number of uniq= ue input scripts prevents this policy from growing the network=E2=80=99s UT= XO set. A standard 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 to be of equal value results in optimal join = transactions, and causes intentional HITs to resemble unavoidable HITs.
=
Outside controlled laboratory conditions, join transactions will not in= volve identically-sized inputs due to a lack of accommodating volume. Witho= ut the ability to cryptographically blind output values on the blockchain, = every join transaction leaks information in the form of output sizes. Requi= ring a pair of identically sized outputs creates the desired ambiguity for = spend outputs, but in most cases makes change outputs linkable to inputs.
# Alternate form heterogenous input script transactions

The fo= rmation of a standard form HIT is not possible in the following cases:
<= br>The HIT is unavoidable, and the user=E2=80=99s wallet contains an insuff= icient number or size of UTXOs to create a standard form HIT.
The user w= ishes 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 ex= ist, a compliant implementation may create an alternate form HIT by constru= cting a transaction as follows:

## Procedure

1. Find the smal= lest combination of inputs whose value is at least the value of the desired= spend.
=C2=A0 i. Add these inputs to the transaction.
=C2=A0 ii. Add= a spend output to the transaction.
=C2=A0 iii. Add a change output to t= he transaction containing the difference between the current set of inputs = and the desired spend.
2. Repeat step 1 to create a second spend output = and change output.
3. 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-z= ero fraction of the transactions they create.

# Non-compliant hetero= genous input script transactions

If a user wishes to create an outpu= t 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 p= rocedure can be completed, then the user can not create a transaction which= is compliant with this procedure.

----

A working draft= of this document is here:
https://github.com/OpenB= itcoinPrivacyProject/rfc/blob/master/bips/obpp-03.mediawiki

A few points of anticipated discussion:

1. It's pos= sible for a CoinJoin transaction to decrease privacy by adhering to the Sta= ndard Form in this BIP, depending on the utxos available for creating it. F= or example, a typical two-person CoinJoin might look like:
in= put_A, input_B =3D> spend_A, change_A, spend_B, change_B

In order to comply with the standard form, one or more parties would hav= e to add inputs to make this something like:

input_A_1, i= nput_A_2, input_B_1, input_B_2 =3D> spend_A, change_A, spend_B, change_B= .

If spend_A and spend_B are the same value, then input_A= _1 and input_A_2 may be linked based on the value of change_A and input_B_1= and input_B_2 may be linked based on the value of change_B via sudoku anal= ysis.

In that situation, wallets can opt to use the alter= nate form instead, or stick with the standard form but enjoy a non-utxo set= increase and a significantly increased inter-transactional privacy set fro= m other BIP adherents.

2. In a naive simulation of a wall= et randomly containing 1 to 10 utxos of random value 1 to 10 and a desired = spend of random value between 1 and the sum of the utxos, the simulated wal= let is able to create an alternate form HIT 40% of the time. If we assume t= hat half of all desire spends are a value half or less of the total wallet = balance, this improves to around 60%. Unfortunately, I don't have any g= ood data on what values are found in average wallets and what desired spend= s look like on average.

3. In the long-run it's bette= r for all clients to participant in CoinJoin-like operations, but this shou= ld significantly increase the cost and decrease the signal of passive block= chain analysis attacks until that becomes feasible.

Thanks in advance for your feedback.
--089e01294798aaa26f052b713832--