MIME-Version: 1.0
In-Reply-To: <CAL3p6zqj7bc=qrayBBK=O6p2b2PBNO3n5EMFf_1dR1oMq581hg@mail.gmail.com>
References: <CAL3p6zpADtYFQnQUr3Efk6V59+K+bB3tPQQMGT9weiafU=43zA@mail.gmail.com>
	<20160808154707.GB2196@banane.informatik.uni-ulm.de>
	<CAL3p6zo1xBEu90MDHSK4TNX0DL2QXxq5vC48a2cFnX0JCD=RvQ@mail.gmail.com>
	<20160809072635.GA2178@banane.informatik.uni-ulm.de>
	<CAL3p6zqj7bc=qrayBBK=O6p2b2PBNO3n5EMFf_1dR1oMq581hg@mail.gmail.com>
From: Tony Churyumoff <tony991@gmail.com>
Date: Wed, 10 Aug 2016 10:52:11 +0300
Message-ID: <CAL3p6zqZC-mqCJ+qryYiYBZ3yCS2KmYPUE37xyt2KWg3=Y4Ngw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] Fwd: Hiding entire content of on-chain transactions
Precedence: list

> Instead of a hash function you may use a keyed hash function (HMAC) where
> the key is just the random string. They key needs to be stored in the
> history of the coin to allow for verification.

This is nearly equivalent.  The sole purpose of the blinding factor is
to increase the search space and make preimaging of the output
impossible.  While in many applications HMAC is superior to plain hash
of a concatenation of the input data and the key (key =3D blinding
factor in our case), its preimage resistance is the same as that of
the hash.


2016-08-09 10:26 GMT+03:00 Henning Kopp <henning.kopp@uni-ulm.de>:
>
> Hi Tony,
>
> > > Regarding the blinding factor, I think you could just use HMAC.
> > How exactly?
>
> I am not entirely sure if this works. You wrote:
>
> > 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.
>
> Instead of a hash function you may use a keyed hash function (HMAC) where
> the key is just the random string. They key needs to be stored in the
> history of the coin to allow for verification.
>
> Best
> Henning
>
> On Mon, Aug 08, 2016 at 07:03:28PM +0300, Tony Churyumoff wrote:
> > 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 txou=
t
> > > 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, w=
hich
> > > > 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 input=
s 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 mess=
age,
> > > 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 publ=
ic
> > > > 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 ano=
ther
> > > > hash, which is the hash of the output being spent.  We=E2=80=99ll c=
all this hash
> > > *spend
> > > > proof*.  Since the spend proof depends solely on the output being s=
pent,
> > > > 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 rejec=
t the
> > > > payment.  If there are several outputs consumed by the same transac=
tion,
> > > > 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, th=
en the
> > > > plaintexts of even earlier transactions that produced the outputs s=
pent
> > > in
> > > > those transactions, and so on, up until the issue (similar to coinb=
ase)
> > > > transactions that created the initial private coins.  Each new owne=
r 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 h=
is own
> > > > transaction.
> > > >
> > > > If we apply the existing bitcoin design that allows multiple inputs=
 and
> > > > multiple outputs per transaction, the history of ownership transfer=
s
> > > would
> > > > grow exponentially.  Indeed, if we take any regular bitcoin output =
and
> > > try
> > > > to track its history back to coinbase, our history will branch ever=
y 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.  Th=
ose
> > > > histories will branch again, and the total number of history entrie=
s
> > > grows
> > > > exponentially.  For example, if every transaction had exactly two i=
nputs,
> > > > the size of history would grow as 2^N where N is the number of step=
s 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 eac=
h
> > > > private transaction to have exactly one input (i.e. to consume exac=
tly
> > > one
> > > > previous output).  This means that when we track a coin=E2=80=99s h=
istory back in
> > > > time, it will no longer branch.  It will grow linearly with the num=
ber of
> > > > transfers of ownership.  If a user wants to combine several inputs,=
 he
> > > will
> > > > have to send them as separate private transactions (technically, se=
veral
> > > > 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 re=
quire
> > > > 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 denomin=
ation.
> > > > 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 f=
irst,
> > > > 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 histor=
ies
> > > > still grow, but only linearly, which should not be a concern in reg=
ard 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 o=
f
> > > > costs.  Regarding privacy, coin histories do expose private transac=
tions
> > > > (or rather parts thereof, since a typical payment will likely consi=
st of
> > > > several transactions due to one-input-per-transaction rule) of past=
 coin
> > > > owners to the future ones, and that exposure grows linearly with ti=
me,
> > > but
> > > > it is still much much better than having every transaction immediat=
ely on
> > > > the public blockchain.  Also, the value of this information for pot=
ential
> > > > adversaries arguably decreases with time.
> > > >
> > > > There is one technical nuance that I omitted above to avoid distrac=
tion.
> > > >  Unlike regular bitcoin transactions, every output in a private pay=
ment
> > > > must also include a blinding factor, which is just a random string.=
  When
> > > > the output is spent, the corresponding spend proof will therefore d=
epend
> > > on
> > > > this blinding factor (remember that spend proof is just a hash of t=
he
> > > > output).  Without a blinding factor, it would be feasible to pre-im=
age
> > > the
> > > > spend proof and reveal the output being spent as the search space o=
f 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 privat=
e
> > > 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 it=
s
> > > input,
> > > > directly to the payee over a private communication channel.  The fi=
rst
> > > > 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 outpu=
ts,
> > > 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 t=
he
> > > > payee.  If there is more than one, the one that comes in the earlie=
r
> > > 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 th=
e
> > > first
> > > > entry, which should be a valid burning transaction.
> > > >
> > > > To facilitate exchange of private transaction data, the bitcoin net=
work
> > > > protocol can be extended with a new message type.  Unfortunately, i=
t
> > > lacks
> > > > encryption, hence private payments are really private only when bit=
coin
> > > 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 m=
ore.
> > > >  Neither the new owner of the coin, nor its future movements will b=
e
> > > known
> > > > to A.
> > > > 2. Over time, larger outputs will likely be split into many smaller
> > > > outputs, whose amounts are not much greater than their denomination=
s.
> > > > You=E2=80=99ll have to combine more inputs to send the same amount.=
  When 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 transact=
ions, your
> > > > bitcoin transaction with so many OP_RETURNs will stand out, and the=
ir
> > > > number will roughly indicate the total amount.  This kind of privac=
y
> > > > 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 e=
ach
> > > > address.
> > > > 3. Exchanges and large merchants will likely accumulate large coin
> > > > histories.  Although fragmented, far from complete, and likely outd=
ated,
> > > 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 an=
d
> > > > addresses are used for both BBC and the base currency BTC.  Every B=
CC
> > > > transaction must be enclosed into by a small BTC transaction that s=
tores
> > > > 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
> > >
>
> --
> 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