MIME-Version: 1.0
Reply-To: tony.991@gmail.com
In-Reply-To: <20160808154707.GB2196@banane.informatik.uni-ulm.de>
References: <CAL3p6zpADtYFQnQUr3Efk6V59+K+bB3tPQQMGT9weiafU=43zA@mail.gmail.com>
	<20160808154707.GB2196@banane.informatik.uni-ulm.de>
From: Tony Churyumoff <tony991@gmail.com>
Date: Mon, 8 Aug 2016 19:03:28 +0300
Message-ID: <CAL3p6zo1xBEu90MDHSK4TNX0DL2QXxq5vC48a2cFnX0JCD=RvQ@mail.gmail.com>
To: Henning Kopp <henning.kopp@uni-ulm.de>
Content-Type: multipart/alternative; boundary=089e01177b1994c3770539918eab
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Hiding entire content of on-chain transactions
Precedence: list

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

Hi Henning,

1. The fees are paid by the enclosing BTC transaction.
2. The hash is encoded into an OP_RETURN.

> Regarding the blinding factor, I think you could just use HMAC.
How exactly?

Tony


2016-08-08 18:47 GMT+03:00 Henning Kopp <henning.kopp@uni-ulm.de>:

> Hi Tony,
>
> I see some issues in your protocol.
>
> 1. How are mining fees handled?
>
> 2. Assume Alice sends Bob some Coins together with their history and
> Bob checks that the history is correct. How does the hash of the txout
> find its way into the blockchain?
>
> Regarding the blinding factor, I think you could just use HMAC.
>
> All the best
> Henning
>
>
> On Mon, Aug 08, 2016 at 06:30:21PM +0300, Tony Churyumoff via bitcoin-dev
> wrote:
> > 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 an=
d
> > 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 sam=
e
> > spend proof, and the payee will be able to see that, and will reject th=
e
> > 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 t=
he
> > 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 o=
wn
> > 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 ti=
me
> > 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 input=
s,
> > the size of history would grow as 2^N where N is the number of steps ba=
ck
> > in history.
> >
> > To avoid such rapid growth of ownership history (which is not only
> > inconvenient to move, but also exposes too much private information abo=
ut
> > 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 histo=
ry back 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, severa=
l
> > 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 requir=
e
> > 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 transferred,
> the
> > input and output amounts must therefore be divisible by the denominatio=
n.
> > For example, an input of amount 700, denomination 100, can be split int=
o
> > 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 own=
er
> > of the coin, not every bitcoin node.  This is a fairer allocation of
> > costs.  Regarding privacy, coin histories do expose private transaction=
s
> > (or rather parts thereof, since a typical payment will likely consist o=
f
> > several transactions due to one-input-per-transaction rule) of past coi=
n
> > 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 potenti=
al
> > 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.  Wh=
en
> > the output is spent, the corresponding spend proof will therefore depen=
d
> 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 al=
l
> > possible outputs is rather small.
> >
> > To issue the new private coin, one can burn regular BTC by sending it t=
o
> > 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 wha=
t
> > 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.  Wh=
en you
> 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=
, your
> > 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 avoi=
d
> 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 store=
s
> > 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
>
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> --
> Henning Kopp
> Institute of Distributed Systems
> Ulm University, Germany
>
> Office: O27 - 3402
> Phone: +49 731 50-24138
> Web: http://www.uni-ulm.de/in/vs/~kopp
>

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

<div dir=3D"ltr">Hi=C2=A0Henning,<div><br></div><div>1. The fees are paid b=
y the enclosing BTC transaction.</div><div>2. The hash is encoded into an O=
P_RETURN.</div><div><br></div><div>&gt; Regarding the blinding factor, I th=
ink you could just use HMAC.<br></div><div>How exactly?</div><div><br></div=
><div>Tony</div><div><br><div class=3D"gmail_extra"><br><div class=3D"gmail=
_quote">2016-08-08 18:47 GMT+03:00 Henning Kopp <span dir=3D"ltr">&lt;<a hr=
ef=3D"mailto:henning.kopp@uni-ulm.de" target=3D"_blank">henning.kopp@uni-ul=
m.de</a>&gt;</span>:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">H=
i Tony,<br>
<br>
I see some issues in your protocol.<br>
<br>
1. How are mining fees handled?<br>
<br>
2. Assume Alice sends Bob some Coins together with their history and<br>
Bob checks that the history is correct. How does the hash of the txout<br>
find its way into the blockchain?<br>
<br>
Regarding the blinding factor, I think you could just use HMAC.<br>
<br>
All the best<br>
Henning<br>
<br>
<br>
On Mon, Aug 08, 2016 at 06:30:21PM +0300, Tony Churyumoff via bitcoin-dev w=
rote:<br>
&gt; This is a proposal about hiding the entire content of bitcoin<br>
&gt; transactions.=C2=A0 It goes farther than CoinJoin and ring signatures,=
 which<br>
&gt; only obfuscate the transaction graph, and Confidential Transactions, w=
hich<br>
&gt; only hide the amounts.<br>
&gt;<br>
&gt; The central idea of the proposed design is to hide the entire inputs a=
nd<br>
&gt; outputs, and publish only the hash of inputs and outputs in the<br>
&gt; blockchain.=C2=A0 The hash can be published as OP_RETURN.=C2=A0 The pl=
aintext of<br>
&gt; inputs and outputs is sent directly to the payee via a private message=
, and<br>
&gt; never goes into the blockchain.=C2=A0 The payee then calculates the ha=
sh and<br>
&gt; looks it up in the blockchain to verify that the hash was indeed publi=
shed<br>
&gt; by the payer.<br>
&gt;<br>
&gt; Since the plaintext of the transaction is not published to the public<=
br>
&gt; blockchain, all validation work has to be done only by the user who<br=
>
&gt; receives the payment.<br>
&gt;<br>
&gt; To protect against double-spends, the payer also has to publish anothe=
r<br>
&gt; hash, which is the hash of the output being spent.=C2=A0 We=E2=80=99ll=
 call this hash *spend<br>
&gt; proof*.=C2=A0 Since the spend proof depends solely on the output being=
 spent,<br>
&gt; any attempt to spend the same output again will produce exactly the sa=
me<br>
&gt; spend proof, and the payee will be able to see that, and will reject t=
he<br>
&gt; payment.=C2=A0 If there are several outputs consumed by the same trans=
action,<br>
&gt; the payer has to publish several spend proofs.<br>
&gt;<br>
&gt; To prove that the outputs being spent are valid, the payer also has to=
 send<br>
&gt; the plaintexts of the earlier transaction(s) that produced them, then =
the<br>
&gt; plaintexts of even earlier transactions that produced the outputs spen=
t in<br>
&gt; those transactions, and so on, up until the issue (similar to coinbase=
)<br>
&gt; transactions that created the initial private coins.=C2=A0 Each new ow=
ner of the<br>
&gt; coin will have to store its entire history, and when he spends the coi=
n, he<br>
&gt; forwards the entire history to the next owner and extends it with his =
own<br>
&gt; transaction.<br>
&gt;<br>
&gt; If we apply the existing bitcoin design that allows multiple inputs an=
d<br>
&gt; multiple outputs per transaction, the history of ownership transfers w=
ould<br>
&gt; grow exponentially.=C2=A0 Indeed, if we take any regular bitcoin outpu=
t and try<br>
&gt; to track its history back to coinbase, our history will branch every t=
ime<br>
&gt; we see a transaction that has more than one input (which is not uncomm=
on).<br>
&gt; After such a transaction (remember, we are traveling back in time), we=
=E2=80=99ll<br>
&gt; have to track two or more histories, for each respective input.=C2=A0 =
Those<br>
&gt; histories will branch again, and the total number of history entries g=
rows<br>
&gt; exponentially.=C2=A0 For example, if every transaction had exactly two=
 inputs,<br>
&gt; the size of history would grow as 2^N where N is the number of steps b=
ack<br>
&gt; in history.<br>
&gt;<br>
&gt; To avoid such rapid growth of ownership history (which is not only<br>
&gt; inconvenient to move, but also exposes too much private information ab=
out<br>
&gt; previous owners of all the contributing coins), we will require each<b=
r>
&gt; private transaction to have exactly one input (i.e. to consume exactly=
 one<br>
&gt; previous output).=C2=A0 This means that when we track a coin=E2=80=99s=
 history back in<br>
&gt; time, it will no longer branch.=C2=A0 It will grow linearly with the n=
umber of<br>
&gt; transfers of ownership.=C2=A0 If a user wants to combine several input=
s, he will<br>
&gt; have to send them as separate private transactions (technically, sever=
al<br>
&gt; OP_RETURNs, which can be included in a single regular bitcoin transact=
ion).<br>
&gt;<br>
&gt; Thus, we are now forbidding any coin merges but still allowing coin<br=
>
&gt; splits.=C2=A0 To avoid ultimate splitting into the dust, we will also =
require<br>
&gt; that all private coins be issued in one of a small number of<br>
&gt; denominations.=C2=A0 Only integer number of =E2=80=9Cbanknotes=E2=80=
=9D can be transferred, the<br>
&gt; input and output amounts must therefore be divisible by the denominati=
on.<br>
&gt; For example, an input of amount 700, denomination 100, can be split in=
to<br>
&gt; outputs 400 and 300, but not into 450 and 250.=C2=A0 To send a payment=
, the<br>
&gt; payer has to pick the unspent outputs of the highest denomination firs=
t,<br>
&gt; then the second highest, and so on, like we already do when we pay in =
cash.<br>
&gt;<br>
&gt; With fixed denominations and one input per transaction, coin histories=
<br>
&gt; still grow, but only linearly, which should not be a concern in regard=
 to<br>
&gt; scalability given that all relevant computing resources still grow<br>
&gt; exponentially.=C2=A0 The histories need to be stored only by the curre=
nt owner<br>
&gt; of the coin, not every bitcoin node.=C2=A0 This is a fairer allocation=
 of<br>
&gt; costs.=C2=A0 Regarding privacy, coin histories do expose private trans=
actions<br>
&gt; (or rather parts thereof, since a typical payment will likely consist =
of<br>
&gt; several transactions due to one-input-per-transaction rule) of past co=
in<br>
&gt; owners to the future ones, and that exposure grows linearly with time,=
 but<br>
&gt; it is still much much better than having every transaction immediately=
 on<br>
&gt; the public blockchain.=C2=A0 Also, the value of this information for p=
otential<br>
&gt; adversaries arguably decreases with time.<br>
&gt;<br>
&gt; There is one technical nuance that I omitted above to avoid distractio=
n.<br>
&gt;=C2=A0 Unlike regular bitcoin transactions, every output in a private p=
ayment<br>
&gt; must also include a blinding factor, which is just a random string.=C2=
=A0 When<br>
&gt; the output is spent, the corresponding spend proof will therefore depe=
nd on<br>
&gt; this blinding factor (remember that spend proof is just a hash of the<=
br>
&gt; output).=C2=A0 Without a blinding factor, it would be feasible to pre-=
image the<br>
&gt; spend proof and reveal the output being spent as the search space of a=
ll<br>
&gt; possible outputs is rather small.<br>
&gt;<br>
&gt; To issue the new private coin, one can burn regular BTC by sending it =
to<br>
&gt; one of several unspendable bitcoin addresses, one address per denomina=
tion.<br>
&gt;=C2=A0 Burning BTC would entitle one to an equal amount of the new priv=
ate coin,<br>
&gt; let=E2=80=99s call it *black bitcoin*, or *BBC*.<br>
&gt;<br>
&gt; Then BBC would be transferred from user to user by:<br>
&gt; 1. creating a private transaction, which consists of one input and sev=
eral<br>
&gt; outputs;<br>
&gt; 2. storing the hash of the transaction and the spend proof of the cons=
umed<br>
&gt; output into the blockchain in an OP_RETURN (the sender pays the<br>
&gt; corresponding fees in regular BTC)<br>
&gt; 3. sending the transaction, together with the history leading to its i=
nput,<br>
&gt; directly to the payee over a private communication channel.=C2=A0 The =
first<br>
&gt; entry of the history must be a bitcoin transaction that burned BTC to =
issue<br>
&gt; an equal amount of BCC.<br>
&gt;<br>
&gt; To verify the payment, the payee:<br>
&gt; 1. makes sure that the amount of the input matches the sum of outputs,=
 and<br>
&gt; all are divisible by the denomination<br>
&gt; 2. calculates the hash of the private transaction<br>
&gt; 3. looks up an OP_RETURN that includes this hash and is signed by the<=
br>
&gt; payee.=C2=A0 If there is more than one, the one that comes in the earl=
ier block<br>
&gt; prevails.<br>
&gt; 4. calculates the spend proof and makes sure that it is included in th=
e<br>
&gt; same OP_RETURN<br>
&gt; 5. makes sure the same spend proof is not included anywhere in the sam=
e or<br>
&gt; earlier blocks (that is, the coin was not spent before).=C2=A0 Only tr=
ansactions<br>
&gt; by the same author are searched.<br>
&gt; 6. repeats the same steps for every entry in the history, except the f=
irst<br>
&gt; entry, which should be a valid burning transaction.<br>
&gt;<br>
&gt; To facilitate exchange of private transaction data, the bitcoin networ=
k<br>
&gt; protocol can be extended with a new message type.=C2=A0 Unfortunately,=
 it lacks<br>
&gt; encryption, hence private payments are really private only when bitcoi=
n is<br>
&gt; used over tor.<br>
&gt;<br>
&gt; There are a few limitations that ought to be mentioned:<br>
&gt; 1. After user A sends a private payment to user B, user A will know wh=
at<br>
&gt; the spend proof is going to be when B decides to spend the coin.<br>
&gt;=C2=A0 Therefore, A will know when the coin was spent by B, but nothing=
 more.<br>
&gt;=C2=A0 Neither the new owner of the coin, nor its future movements will=
 be known<br>
&gt; to A.<br>
&gt; 2. Over time, larger outputs will likely be split into many smaller<br=
>
&gt; outputs, whose amounts are not much greater than their denominations.<=
br>
&gt; You=E2=80=99ll have to combine more inputs to send the same amount.=C2=
=A0 When you want<br>
&gt; to send a very large amount that is much greater than the highest avai=
lable<br>
&gt; denomination, you=E2=80=99ll have to send a lot of private transaction=
s, your<br>
&gt; bitcoin transaction with so many OP_RETURNs will stand out, and their<=
br>
&gt; number will roughly indicate the total amount.=C2=A0 This kind of priv=
acy<br>
&gt; leakage, however it applies to a small number of users, is easy to avo=
id by<br>
&gt; using multiple addresses and storing a relatively small amount on each=
<br>
&gt; address.<br>
&gt; 3. Exchanges and large merchants will likely accumulate large coin<br>
&gt; histories.=C2=A0 Although fragmented, far from complete, and likely ou=
tdated, it<br>
&gt; is still something to bear in mind.<br>
&gt;<br>
&gt; No hard or soft fork is required, BBC is just a separate privacy prese=
rving<br>
&gt; currency on top of bitcoin blockchain, and the same private keys and<b=
r>
&gt; addresses are used for both BBC and the base currency BTC.=C2=A0 Every=
 BCC<br>
&gt; transaction must be enclosed into by a small BTC transaction that stor=
es<br>
&gt; the OP_RETURNs and pays for the fees.<br>
&gt;<br>
&gt; Are there any flaws in this design?<br>
&gt;<br>
&gt; Originally posted to BCT <a href=3D"https://bitcointalk.org/index.php?=
topic=3D1574508.0" rel=3D"noreferrer" target=3D"_blank">https://bitcointalk=
.org/index.<wbr>php?topic=3D1574508.0</a>,<br>
&gt; but got no feedback so far, apparently everybody was consumed with bit=
finex<br>
&gt; drama and now mimblewimble.<br>
&gt;<br>
&gt; Tony<br>
<br>
&gt; ______________________________<wbr>_________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l=
ists.<wbr>linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wb=
r>org/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<span class=3D""><font color=3D"#888888"><br>
<br>
--<br>
Henning Kopp<br>
Institute of Distributed Systems<br>
Ulm University, Germany<br>
<br>
Office: O27 - 3402<br>
Phone: +49 731 50-24138<br>
Web: <a href=3D"http://www.uni-ulm.de/in/vs/~kopp" rel=3D"noreferrer" targe=
t=3D"_blank">http://www.uni-ulm.de/in/vs/~<wbr>kopp</a><br>
</font></span></blockquote></div><br></div></div></div>

--089e01177b1994c3770539918eab--