path: root/b1/b2e0a7f1776192ad10cda8389f9eef698e4a49

Return-Path: <tony991@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9B650722
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  8 Aug 2016 15:30:25 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f46.google.com (mail-wm0-f46.google.com [74.125.82.46])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9E9871F3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  8 Aug 2016 15:30:23 +0000 (UTC)
Received: by mail-wm0-f46.google.com with SMTP id i5so147006045wmg.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 08 Aug 2016 08:30:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:reply-to:from:date:message-id:subject:to;
	bh=EqBEUNl1mX3Ce39odHZhcrmADr8lZDzAP8Or/xFN+Hs=;
	b=b0kPPPGdxRKkGeZ0VAO2iOWWMeeef6yQySsEQyB2VG4Lcof8/cvkzecpmm/yIwYhFl
	YDPa2guuj8f+xIEmJKzcfnTUcuPWe+pyLFeUf2f/6x0DybTV1APb22YHpay+nqw4nddL
	SxxHi9R09n/nBxxybp9wmxMtZyVVSRHKVXYwArQ7jZMHTsEvLdWJRBJS0amXI03kAnnM
	ZyftNig9r1lQ2P3VEThSYb9QTBZc27CH82tnSShxKfnFXEBHXXNhu5ee5QseqtVFtFHJ
	of9IZKDUQbV2xGiWMQ6Mqi2bsXPSMEIKZrSLKI2qGNiyqDQxh/awLQMMGpxVs9ddwHu7
	Ok6g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:reply-to:from:date:message-id
	:subject:to;
	bh=EqBEUNl1mX3Ce39odHZhcrmADr8lZDzAP8Or/xFN+Hs=;
	b=CV5y+w8xNuhOwrm1wRUYX/8KAPfAVy4VokEemdTOvYZEQVVHueb4cupWv7TGjTjMEY
	kkl1zWE45/muZiYLg28m4EoJLGcDZEnlzi1dJqH+mASS56IH4qkmTBdls1cHArwyvEHI
	cZeiGs8nFsxX8yvOAq3hovCRA0qhx6QTgHHLXfwgJFSloF9YsxurYtIaR3iv2WIvs46m
	4IfQggTWLFS95AzI3tPbeSfnxfW+8CnYNf0GfHGFOrBytrX7LqTCq2OXSGFSL/UVoqWm
	6bA9mB5wt86O74uHkp+kof6Q4qwpOzeHCQSLQMemavVnXy8shPHBeJMkO9bE+n16dAdn
	I0SA==
X-Gm-Message-State: AEkoouuQFPGdT4ayETD956gLvPXya5sR0H7jrQIo55Xl+8+3ccR+f6fwpeoxDhkN9Veex31WpmOhuODRBF7P3w==
X-Received: by 10.28.223.139 with SMTP id w133mr17093705wmg.90.1470670221800; 
	Mon, 08 Aug 2016 08:30:21 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.194.100.161 with HTTP; Mon, 8 Aug 2016 08:30:21 -0700 (PDT)
Reply-To: tony.991@gmail.com
From: Tony Churyumoff <tony991@gmail.com>
Date: Mon, 8 Aug 2016 18:30:21 +0300
Message-ID: <CAL3p6zpADtYFQnQUr3Efk6V59+K+bB3tPQQMGT9weiafU=43zA@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a114b0aa826fbe00539911808
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
	FREEMAIL_REPLYTO, HTML_MESSAGE,
	RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 08 Aug 2016 15:31:29 +0000
Subject: [bitcoin-dev] Hiding entire content of on-chain transactions
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 08 Aug 2016 15:30:25 -0000

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

This is a proposal about hiding the entire content of bitcoin
transactions.  It goes farther than CoinJoin and ring signatures, which
only obfuscate the transaction graph, and Confidential Transactions, which
only hide the amounts.

The central idea of the proposed design is to hide the entire inputs and
outputs, and publish only the hash of inputs and outputs in the
blockchain.  The hash can be published as OP_RETURN.  The plaintext of
inputs and outputs is sent directly to the payee via a private message, and
never goes into the blockchain.  The payee then calculates the hash and
looks it up in the blockchain to verify that the hash was indeed published
by the payer.

Since the plaintext of the transaction is not published to the public
blockchain, all validation work has to be done only by the user who
receives the payment.

To protect against double-spends, the payer also has to publish another
hash, which is the hash of the output being spent.  We=E2=80=99ll call this=
 hash *spend
proof*.  Since the spend proof depends solely on the output being spent,
any attempt to spend the same output again will produce exactly the same
spend proof, and the payee will be able to see that, and will reject the
payment.  If there are several outputs consumed by the same transaction,
the payer has to publish several spend proofs.

To prove that the outputs being spent are valid, the payer also has to send
the plaintexts of the earlier transaction(s) that produced them, then the
plaintexts of even earlier transactions that produced the outputs spent in
those transactions, and so on, up until the issue (similar to coinbase)
transactions that created the initial private coins.  Each new owner of the
coin will have to store its entire history, and when he spends the coin, he
forwards the entire history to the next owner and extends it with his own
transaction.

If we apply the existing bitcoin design that allows multiple inputs and
multiple outputs per transaction, the history of ownership transfers would
grow exponentially.  Indeed, if we take any regular bitcoin output and try
to track its history back to coinbase, our history will branch every time
we see a transaction that has more than one input (which is not uncommon).
After such a transaction (remember, we are traveling back in time), we=E2=
=80=99ll
have to track two or more histories, for each respective input.  Those
histories will branch again, and the total number of history entries grows
exponentially.  For example, if every transaction had exactly two inputs,
the size of history would grow as 2^N where N is the number of steps back
in history.

To avoid such rapid growth of ownership history (which is not only
inconvenient to move, but also exposes too much private information about
previous owners of all the contributing coins), we will require each
private transaction to have exactly one input (i.e. to consume exactly one
previous output).  This means that when we track a coin=E2=80=99s history b=
ack in
time, it will no longer branch.  It will grow linearly with the number of
transfers of ownership.  If a user wants to combine several inputs, he will
have to send them as separate private transactions (technically, several
OP_RETURNs, which can be included in a single regular bitcoin transaction).

Thus, we are now forbidding any coin merges but still allowing coin
splits.  To avoid ultimate splitting into the dust, we will also require
that all private coins be issued in one of a small number of
denominations.  Only integer number of =E2=80=9Cbanknotes=E2=80=9D can be t=
ransferred, the
input and output amounts must therefore be divisible by the denomination.
For example, an input of amount 700, denomination 100, can be split into
outputs 400 and 300, but not into 450 and 250.  To send a payment, the
payer has to pick the unspent outputs of the highest denomination first,
then the second highest, and so on, like we already do when we pay in cash.

With fixed denominations and one input per transaction, coin histories
still grow, but only linearly, which should not be a concern in regard to
scalability given that all relevant computing resources still grow
exponentially.  The histories need to be stored only by the current owner
of the coin, not every bitcoin node.  This is a fairer allocation of
costs.  Regarding privacy, coin histories do expose private transactions
(or rather parts thereof, since a typical payment will likely consist of
several transactions due to one-input-per-transaction rule) of past coin
owners to the future ones, and that exposure grows linearly with time, but
it is still much much better than having every transaction immediately on
the public blockchain.  Also, the value of this information for potential
adversaries arguably decreases with time.

There is one technical nuance that I omitted above to avoid distraction.
 Unlike regular bitcoin transactions, every output in a private payment
must also include a blinding factor, which is just a random string.  When
the output is spent, the corresponding spend proof will therefore depend on
this blinding factor (remember that spend proof is just a hash of the
output).  Without a blinding factor, it would be feasible to pre-image the
spend proof and reveal the output being spent as the search space of all
possible outputs is rather small.

To issue the new private coin, one can burn regular BTC by sending it to
one of several unspendable bitcoin addresses, one address per denomination.
 Burning BTC would entitle one to an equal amount of the new private coin,
let=E2=80=99s call it *black bitcoin*, or *BBC*.

Then BBC would be transferred from user to user by:
1. creating a private transaction, which consists of one input and several
outputs;
2. storing the hash of the transaction and the spend proof of the consumed
output into the blockchain in an OP_RETURN (the sender pays the
corresponding fees in regular BTC)
3. sending the transaction, together with the history leading to its input,
directly to the payee over a private communication channel.  The first
entry of the history must be a bitcoin transaction that burned BTC to issue
an equal amount of BCC.

To verify the payment, the payee:
1. makes sure that the amount of the input matches the sum of outputs, and
all are divisible by the denomination
2. calculates the hash of the private transaction
3. looks up an OP_RETURN that includes this hash and is signed by the
payee.  If there is more than one, the one that comes in the earlier block
prevails.
4. calculates the spend proof and makes sure that it is included in the
same OP_RETURN
5. makes sure the same spend proof is not included anywhere in the same or
earlier blocks (that is, the coin was not spent before).  Only transactions
by the same author are searched.
6. repeats the same steps for every entry in the history, except the first
entry, which should be a valid burning transaction.

To facilitate exchange of private transaction data, the bitcoin network
protocol can be extended with a new message type.  Unfortunately, it lacks
encryption, hence private payments are really private only when bitcoin is
used over tor.

There are a few limitations that ought to be mentioned:
1. After user A sends a private payment to user B, user A will know what
the spend proof is going to be when B decides to spend the coin.
 Therefore, A will know when the coin was spent by B, but nothing more.
 Neither the new owner of the coin, nor its future movements will be known
to A.
2. Over time, larger outputs will likely be split into many smaller
outputs, whose amounts are not much greater than their denominations.
You=E2=80=99ll have to combine more inputs to send the same amount.  When y=
ou want
to send a very large amount that is much greater than the highest available
denomination, you=E2=80=99ll have to send a lot of private transactions, yo=
ur
bitcoin transaction with so many OP_RETURNs will stand out, and their
number will roughly indicate the total amount.  This kind of privacy
leakage, however it applies to a small number of users, is easy to avoid by
using multiple addresses and storing a relatively small amount on each
address.
3. Exchanges and large merchants will likely accumulate large coin
histories.  Although fragmented, far from complete, and likely outdated, it
is still something to bear in mind.

No hard or soft fork is required, BBC is just a separate privacy preserving
currency on top of bitcoin blockchain, and the same private keys and
addresses are used for both BBC and the base currency BTC.  Every BCC
transaction must be enclosed into by a small BTC transaction that stores
the OP_RETURNs and pays for the fees.

Are there any flaws in this design?

Originally posted to BCT https://bitcointalk.org/index.php?topic=3D1574508.=
0,
but got no feedback so far, apparently everybody was consumed with bitfinex
drama and now mimblewimble.

Tony

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

<div dir=3D"ltr">This is a proposal about hiding the entire content of bitc=
oin transactions.=C2=A0 It goes farther than CoinJoin and ring signatures, =
which only obfuscate the transaction graph, and Confidential Transactions, =
which only hide the amounts.<div><br></div><div>The central idea of the pro=
posed design is to hide the entire inputs and
 outputs, and publish only the hash of inputs and outputs in the=20
blockchain.=C2=A0 The hash can be published as OP_RETURN.=C2=A0 The plainte=
xt of=20
inputs and outputs is sent directly to the payee via a private message,=20
and never goes into the blockchain.=C2=A0 The payee then calculates the has=
h=20
and looks it up in the blockchain to verify that the hash was indeed=20
published by the payer.<br><br>Since the plaintext of the transaction is
 not published to the public blockchain, all validation work has to be=20
done only by the user who receives the payment.<br><br>To protect=20
against double-spends, the payer also has to publish another hash, which
 is the hash of the output being spent.=C2=A0 We=E2=80=99ll call this hash =
<b>spend proof</b>.
 =C2=A0Since the spend proof depends solely on the output being spent, any=
=20
attempt to spend the same output again will produce exactly the same=20
spend proof, and the payee will be able to see that, and will reject the=20
payment.=C2=A0 If there are several outputs consumed by the same transactio=
n,
 the payer has to publish several spend proofs.<br><br>To prove that the
 outputs being spent are valid, the payer also has to send the=20
plaintexts of the earlier transaction(s) that produced them, then the=20
plaintexts of even earlier transactions that produced the outputs spent=20
in those transactions, and so on, up until the issue (similar to=20
coinbase) transactions that created the initial private coins.=C2=A0 Each n=
ew
 owner of the coin will have to store its entire history, and when he=20
spends the coin, he forwards the entire history to the next owner and=20
extends it with his own transaction.<br><br>If we apply the existing=20
bitcoin design that allows multiple inputs and multiple outputs per=20
transaction, the history of ownership transfers would grow=20
exponentially.=C2=A0 Indeed, if we take any regular bitcoin output and try =
to
 track its history back to coinbase, our history will branch every time=20
we see a transaction that has more than one input (which is not=20
uncommon).=C2=A0 After such a transaction (remember, we are traveling back =
in
 time), we=E2=80=99ll have to track two or more histories, for each respect=
ive=20
input.=C2=A0 Those histories will branch again, and the total number of=20
history entries grows exponentially.=C2=A0 For example, if every transactio=
n=20
had exactly two inputs, the size of history would grow as 2^N=C2=A0where N =
is the number of steps back in history.<br><br>To
 avoid such rapid growth of ownership history (which is not only=20
inconvenient to move, but also exposes too much private information=20
about previous owners of all the contributing coins), we will require=20
each private transaction to have exactly one input (i.e. to consume=20
exactly one previous output).=C2=A0 This means that when we track a coin=E2=
=80=99s=20
history back in time, it will no longer branch.=C2=A0 It will grow linearly=
=20
with the number of transfers of ownership.=C2=A0 If a user wants to combine=
=20
several inputs, he will have to send them as separate private=20
transactions (technically, several OP_RETURNs, which can be included in a
 single regular bitcoin transaction).<br><br>Thus, we are now forbidding
 any coin merges but still allowing coin splits.=C2=A0 To avoid ultimate=20
splitting into the dust, we will also require that all private coins be=20
issued in one of a small number of denominations.=C2=A0 Only integer number=
=20
of =E2=80=9Cbanknotes=E2=80=9D can be transferred, the input and output amo=
unts must=20
therefore be divisible by the denomination.=C2=A0 For example, an input of=
=20
amount 700, denomination 100, can be split into outputs 400 and 300, but
 not into 450 and 250.=C2=A0 To send a payment, the payer has to pick the=
=20
unspent outputs of the highest denomination first, then the second=20
highest, and so on, like we already do when we pay in cash.<br><br>With=20
fixed denominations and one input per transaction, coin histories still=20
grow, but only linearly, which should not be a concern in regard to=20
scalability given that all relevant computing resources still grow=20
exponentially.=C2=A0 The histories need to be stored only by the current=20
owner of the coin, not every bitcoin node.=C2=A0 This is a fairer allocatio=
n=20
of costs.=C2=A0 Regarding privacy, coin histories do expose private=20
transactions (or rather parts thereof, since a typical payment will=20
likely consist of several transactions due to one-input-per-transaction=20
rule) of past coin owners to the future ones, and that exposure grows=20
linearly with time, but it is still much much better than having every=20
transaction immediately on the public blockchain.=C2=A0 Also, the value of=
=20
this information for potential adversaries arguably decreases with time.<br=
><br>There
 is one technical nuance that I omitted above to avoid distraction.=20
=C2=A0Unlike regular bitcoin transactions, every output in a private paymen=
t=20
must also include a blinding factor, which is just a random string.=20
=C2=A0When the output is spent, the corresponding spend proof will therefor=
e=20
depend on this blinding factor (remember that spend proof is just a hash
 of the output).=C2=A0 Without a blinding factor, it would be feasible to=
=20
pre-image the spend proof and reveal the output being spent as the=20
search space of all possible outputs is rather small.<br><br>To issue=20
the new private coin, one can burn regular BTC by sending it to one of=20
several unspendable bitcoin addresses, one address per denomination.=20
=C2=A0Burning BTC would entitle one to an equal amount of the new private=
=20
coin, let=E2=80=99s call it <b>black bitcoin</b>, or <b>BBC</b>. =C2=A0<br>=
<br>Then BBC would be transferred from user to user by:<br>1. creating a pr=
ivate transaction, which consists of one input and several outputs;<br>2.
 storing the hash of the transaction and the spend proof of the consumed
 output into the blockchain in an OP_RETURN (the sender pays the=20
corresponding fees in regular BTC)<br>3. sending the transaction,=20
together with the history leading to its input, directly to the payee=20
over a private communication channel.=C2=A0 The first entry of the history=
=20
must be a bitcoin transaction that burned BTC to issue an equal amount=20
of BCC.<br><br>To verify the payment, the payee:<br>1. makes sure that the =
amount of the input matches the sum of outputs, and all are divisible by th=
e denomination<br>2. calculates the hash of the private transaction<br>3.
 looks up an OP_RETURN that includes this hash and is signed by the=20
payee.=C2=A0 If there is more than one, the one that comes in the earlier=
=20
block prevails.<br>4. calculates the spend proof and makes sure that it is =
included in the same OP_RETURN<br>5.
 makes sure the same spend proof is not included anywhere in the same or
 earlier blocks (that is, the coin was not spent before).=C2=A0 Only=20
transactions by the same author are searched.<br>6. repeats the same steps =
for every entry in the history, except the first entry, which should be a v=
alid burning transaction.<br><br>To
 facilitate exchange of private transaction data, the bitcoin network=20
protocol can be extended with a new message type.=C2=A0 Unfortunately, it=
=20
lacks encryption, hence private payments are really private only when=20
bitcoin is used over tor.<br><br>There are a few limitations that ought to =
be mentioned:<br>1.
 After user A sends a private payment to user B, user A will know what=20
the spend proof is going to be when B decides to spend the coin.=20
=C2=A0Therefore, A will know when the coin was spent by B, but nothing more=
.=20
=C2=A0Neither the new owner of the coin, nor its future movements will be=
=20
known to A.<br>2. Over time, larger outputs will likely be split into=20
many smaller outputs, whose amounts are not much greater than their=20
denominations.=C2=A0 You=E2=80=99ll have to combine more inputs to send the=
 same=20
amount.=C2=A0 When you want to send a very large amount that is much greate=
r=20
than the highest available denomination, you=E2=80=99ll have to send a lot =
of=20
private transactions, your bitcoin transaction with so many OP_RETURNs=20
will stand out, and their number will roughly indicate the total amount.
 =C2=A0This kind of privacy leakage, however it applies to a small number o=
f=20
users, is easy to avoid by using multiple addresses and storing a=20
relatively small amount on each address.<br>3. Exchanges and large=20
merchants will likely accumulate large coin histories.=C2=A0 Although=20
fragmented, far from complete, and likely outdated, it is still=20
something to bear in mind.<br></div><div><br></div><div>No hard or soft for=
k is required, BBC is just a separate privacy preserving currency on top of=
 bitcoin blockchain, and the same private keys and addresses are used for b=
oth BBC and the base currency BTC.=C2=A0 Every BCC transaction must be encl=
osed into by a small BTC transaction that stores the OP_RETURNs and pays fo=
r the fees.</div><div><br></div><div>Are there any flaws in this design?</d=
iv><div><br></div><div>Originally posted to BCT=C2=A0<a href=3D"https://bit=
cointalk.org/index.php?topic=3D1574508.0">https://bitcointalk.org/index.php=
?topic=3D1574508.0</a>, but got no feedback so far, apparently everybody wa=
s consumed with bitfinex drama and now mimblewimble.</div><div><br></div><d=
iv>Tony</div><div><br></div></div>

--001a114b0aa826fbe00539911808--