[Bitcoin-development] ecash and revocability

[Bitcoin-development] ecash and revocability

[Adam Back]

So back in 1999, in an ecash thread on cypherpunks I claimed:

http://marc.info/?l=cypherpunks&m=95280154629900&w=2

> I wouldn't say ecash has to use blinding, but I would argue it would be a
> misuse of the word "ecash", if something which was revocable were dubbed
> ecash.

This was in the context of a discussion of digigold (e-gold stored the
physical gold, digigold offered "ecash" backed in that physical gold). 
Digigold ran on Systemics payment server/sox protocol.  Because of inferred
regulatory concerns and patent licensing issues digigold & systemics were
not using blind signatures.  However with systemics sox server, like
bitcoin, you could create multiple accounts on demand and shuffle payments
around for a degree of privacy.  The bitcoin analogy would be the
transaction log lived in the systemics server, so it had a central failure
point, but arguably more privacy as the log was not public.  Also systemics
SOX protocol (Ian Grigg & Gary Howland) had some aspect of bitcoins smart
contract concepts - ricardian contracts. 
http://iang.org/papers/ricardian_contract.html 

(Btw the anonymous reply itself was interesting -
http://marc.info/?l=cypherpunks&m=95280154629912&w=2 that could have been
Nakamoto, the only missing thing from the parts on the discussion room floor
to bitcoin is mathematical inflation control.)

The thread actually started here
http://marc.info/?l=cypherpunks&m=95280154629912&w=2 and then continues here
http://marc.info/?l=cypherpunks&m=95280154629900&w=2 because of a subject
line change and then http://marc.info/?l=cypherpunks&m=95280154629916&w=2
and http://marc.info/?l=cypherpunks&m=95280154629948&w=2
more subject line change confusion.

A related thread a few days later also covers Sander & Ta-Shma (which
zerocoin is based on):

http://marc.info/?l=cypherpunks&m=95280154630167&w=2

there were many more threads about various ecash technologies.

Adam

[Bitcoin-development] bitcoin taint & unilateral revocability (Re: ecash and revocability)

[Adam Back]

On Tue, May 14, 2013 at 01:51:51PM +0200, Adam Back wrote:
> Adam Back in Sep 1999, cypherpunks list:
>>I wouldn't say ecash has to use blinding, but I would argue it would be a
>>misuse of the word "ecash", if something which was revocable were dubbed
>>ecash.

So I still think that is an important point.  "Ecash should not be
revocable".  I think bitcoin currently has a partial problem because of
taint.

Now blinding based unlinkability, in a distributed cryptographic payer/payee
anonymous system like Sander & Ta Shma [1] and zerocoin has so far been
based on ZKP of set membership.  Of course that is somewhat expensive,
though zerocoin improved the ZKP with an relatively efficient (but still
cut-and-choose) proof.

Bitcoins relative lack of privacy creates a problem with tainted coins
risking becoming unspendable, or spendable only with some users, or at a
discount.  So while the policy coded says all coins are equally acceptable,
the information exists so people can unilaterally reject them, depending on
what the taint is.  So far revocability hasnt reared it's head that I heard,
nor taint inspection too much?  However people have the choice and technical
means to check the taint and send the bitcoins back.


Another aspect is that bitcoin, like systemics sox/digigold, makes a
different privacy tradeoff.  Somewhat private, but not very much.

But it creates the question: could the taint issue be fixed efficiently (eg
even without blinding or ZKP of set membership?)


One related concept is commitments.  I think its relatively easy to commit
to a payment and lock a coin without identifying yourself, until the
commitment is released.  You might do the commitment, wait 6-blocks for
confirmation, then reveal the commitment.  Then that is like a self-issued
green coin with no need for trust, that can be immediately cleared.  The
recipient has to be committed to at the same time to prevent double
spending.

So just commit = H( input-pub ) H( transaction ) and put it in the block
chain.  Where transaction the is usual ( input signature, output-pub,
script).  (Fee for the commit would have to come from an unlinked coin or
the input-pub reveals the coin).  Wait 6 blocks, send/reveal the transaction
(free because fee was already paid).  Validators check input-pub hash
against committed coins by hash, check the transaction hash, and the usual
ransaction validations = sum inputs, otherwise reject.  The user better pay
change if any to a different public key, as the inputs public keys are one
use - are after the reveal they are DoS lockable by other people reposting
H( input-pub ).

The input-pub coin is locked as normal transactions have their public key hash
validate as not being locked.

Adam

[1] Sander & Ta Shma "Auditable, Anonymous Electronic Cash"
     http://www.cs.tau.ac.il/~amnon/Papers/ST.crypto99.pdf

Re: [Bitcoin-development] bitcoin taint & unilateral revocability (Re: ecash and revocability)

[Simon Barber]

Adam,

Take a look at this privacy enhancing solution based on fair exchange 
implemented by bitcoin contracts and cut-and-choose. It would require a 
public pool of users willing to exchange in common denominations at 
moments in time together to ensure unlinkability. It also leave a trace 
of exchange activity in the chain. This could all be added to wallet 
software to become automatic.

http://robotics.stanford.edu/~xb/fc12/index.html

Simon


On 05/14/2013 07:09 AM, Adam Back wrote:
> On Tue, May 14, 2013 at 01:51:51PM +0200, Adam Back wrote:
>> Adam Back in Sep 1999, cypherpunks list:
>>> I wouldn't say ecash has to use blinding, but I would argue it would be a
>>> misuse of the word "ecash", if something which was revocable were dubbed
>>> ecash.
>
> So I still think that is an important point.  "Ecash should not be
> revocable".  I think bitcoin currently has a partial problem because of
> taint.
>
> Now blinding based unlinkability, in a distributed cryptographic payer/payee
> anonymous system like Sander & Ta Shma [1] and zerocoin has so far been
> based on ZKP of set membership.  Of course that is somewhat expensive,
> though zerocoin improved the ZKP with an relatively efficient (but still
> cut-and-choose) proof.
>
> Bitcoins relative lack of privacy creates a problem with tainted coins
> risking becoming unspendable, or spendable only with some users, or at a
> discount.  So while the policy coded says all coins are equally acceptable,
> the information exists so people can unilaterally reject them, depending on
> what the taint is.  So far revocability hasnt reared it's head that I heard,
> nor taint inspection too much?  However people have the choice and technical
> means to check the taint and send the bitcoins back.
>
>
> Another aspect is that bitcoin, like systemics sox/digigold, makes a
> different privacy tradeoff.  Somewhat private, but not very much.
>
> But it creates the question: could the taint issue be fixed efficiently (eg
> even without blinding or ZKP of set membership?)
>
>
> One related concept is commitments.  I think its relatively easy to commit
> to a payment and lock a coin without identifying yourself, until the
> commitment is released.  You might do the commitment, wait 6-blocks for
> confirmation, then reveal the commitment.  Then that is like a self-issued
> green coin with no need for trust, that can be immediately cleared.  The
> recipient has to be committed to at the same time to prevent double
> spending.
>
> So just commit = H( input-pub ) H( transaction ) and put it in the block
> chain.  Where transaction the is usual ( input signature, output-pub,
> script).  (Fee for the commit would have to come from an unlinked coin or
> the input-pub reveals the coin).  Wait 6 blocks, send/reveal the transaction
> (free because fee was already paid).  Validators check input-pub hash
> against committed coins by hash, check the transaction hash, and the usual
> ransaction validations = sum inputs, otherwise reject.  The user better pay
> change if any to a different public key, as the inputs public keys are one
> use - are after the reveal they are DoS lockable by other people reposting
> H( input-pub ).
>
> The input-pub coin is locked as normal transactions have their public key hash
> validate as not being locked.
>
> Adam
>
> [1] Sander & Ta Shma "Auditable, Anonymous Electronic Cash"
>       http://www.cs.tau.ac.il/~amnon/Papers/ST.crypto99.pdf
>
> ------------------------------------------------------------------------------
> AlienVault Unified Security Management (USM) platform delivers complete
> security visibility with the essential security capabilities. Easily and
> efficiently configure, manage, and operate all of your security controls
> from a single console and one unified framework. Download a free trial.
> http://p.sf.net/sfu/alienvault_d2d
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Re: [Bitcoin-development] bitcoin taint & unilateral revocability (Re: ecash and revocability)

[grarpamp]

> Bitcoins relative lack of privacy creates a problem with tainted coins
> risking becoming unspendable, or spendable only with some users, or at a
> discount.  So while the policy coded says all coins are equally acceptable,
> the information exists so people can unilaterally reject them, depending on
> what the taint is.  So far revocability hasnt reared it's head that I heard,
> nor taint inspection too much?  However people have the choice and technical
> means to check the taint and send the bitcoins back.

a) Is there a paper detailing bitcoin traceability issues?
Particularly when using various combinations of the often
advised 'use different address for every transaction', 'wash coins',
and 'use anonymity networks' privacy enhancement methods.

b) People would be nuts to reject tainted coins on the current
chain, or any chain. How many of the bills in your wallet passed
through 'illicit' transactions? How would you feel if your payee's
serial checker bounced yours, possibly forcing you to dispense
with them through other, possibly illicit, means? What about a
total blackball? Who's going to compensate you? How exactly do
you roll that all back? And are you going to KYC and scour the lives
of your every potential customer beforehand? What if someone has
money to burn and blackballs a million notes for fun. A currency of
common global adoption that you can't spend after some thieving
crackdealer bought an onion off your garden stand isn't of much use
to anyone, not even the purists who come up with such ideas.
Specialized currencies in special markets, sure, maybe, all still
fraught with the same dilemmas. But for a global common one? No.

[Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

So in a previous mail I described a simple, extremely efficient and easy to
implement symmetric key commitment that is unlinkable until reveal time (at
bottom).  I think this can help improve the byzantine generals problem, that
bitcoin only defends to simple majority (with one vote per CPU power), and
so assumes most nodes by cpu power are honest.  With this simple protocol
change you dont need any honest nodes, just some honest clients to spend to,
to have your transaction accepted.  

You can think of this in terms of a (somewhat distributed) server performing
validations, but in a way that it sufficiently blind to the details of the
validations that it can not selectively enforce a policy, it power is
limited to random DoS.

There are other situations where you can rely on a server for one property
but not another - eg a somewhat distributed encrypted backup (like Tahoe
LAFS) you rely on for availability, but not integrity nor confidentiality
(because you encrypt those, and some sharing scenarios still work.) So this
is in that class of protocols - zero-trust in server, but can extract
service and some guarantees from the (optionally distributed) server anyway.

(Bitcoin does not use known better than majority results for byzantine
generals based on fair coin toss, relying instead on simple majority and an
assumed largely unjammable network.  I notice Nick Szabo was complaining
about this on his blog and saying bitcoins majority is not even a standard
or proven byzantine voting protocol - something adhoc.  I think the bitcoin
unjammable network assumption is a false at the limit so that someone with
strong network hacking capabilities can create network splits long enough to
even overcome the network majority vote without having any compute power of
their own.  All they need is to have a split with enough power to plausibly
quickly get the victims their desired number of (split) confirmations.)

Anyway this should be a clear voting improvement, that is efficient.

Imagine a couple of big pools or ASIC miners started enforcing some
arbitrary coin policy, eg say coins must not have some taint according to
its list of black coins, or coins must be certified by some entity, be
traceable to some type of event etc.  Well call these miners/voters
"dishonest", in that they are not following the intended zero-policy
protocol.

If the coins dont match their chosen policy, the dishonest miners will
refuse to include transactions in blocks they issue.  If they see a
transaction which does not match their policy in a block by someone else
they will ignore it and try to make it into an orphan.  As they have say 75%
of the network power they can do that successfully.  Even with current
validation protocols in the clients, so the "but clients wont accept the
change" argument does not apply - the existing clients will accept the
policy change, because they cant detect it, nor prove it, and dont have the
voting power to impose honest policies.

(For realism of this risk, note that according to Kaminsky there already
exist multiple entities with reserve ASIC power each exceeding current
network difficulty who are holding part of their power in reserve for profit
maximisation reasons.  This is a coming to fruition of the concentration of
power issue I was talking about in my first bitcoin forum post.  People who
have that kind of power in reserve have clearly invested millions of
dollars, which probably makes them more vulnerable to political influence.)


Alright so the solution.  Use the commitment protocol (below) which even
though it is symmetric key strongly hides the committed transaction public
key.  (Symmetric in the sense that the validation steps are all highly
efficient symmetric key based).  Now send the transaction (which includes
the public key) direct to the receiver, over a secure channel, or an assumed
non-eavesdropped direct channel, with no p2p flood of the transaction.  The
receiver can check the hash to the commitment, and decide how many
confirmtions he needs.  Once he has eg 6 confirmations he reveals the
commitment to the transaction (by publishing it).  The sender may also send
the reveal/transaction to the network directly himself, if the recipient is
offline.  However there is no advantage to publishing early so it seems
better to let the recipient do it when he is ready to incorporate the
payment into his wallet.  

Now the powerful dishonest voters if they try to apply their policy when
they see the reveal triggers it, must redo the work of the 6-commitments
that they computed themselves.  This is like starting 6-steps behind in the
statstical gamblers ruin game that Nakamoto describes in the bitcoin paper. 
Consequently even with 75%, they will find it very hard to outcompete their
own prior work, to create a 6 chain long orphan while the 25% is moving
forward on the honest chain.  Each time they see transactions which violate
their policy, they have to restart their chain recalculation again from
scratch.  Often if simple lower powered intermittent recipient sends the
coin will be burried hundreds of blocks back.  In addition 6 chain long
branches are extremely unlikely with honest payers, so clients can (and
maybe already do?) act with suspicion of they see one.


Going further, I said for best security, the recipient should never even
reveal (to the network) until he is actually about to spend, but futher he
does not even have to reveal publicly ever, he can choose to reveal only to
the recipient with a direct connection (no p2p flood fill of transaction.)
And the direct spend argument composes, ie the 2nd recipient can not do the
same thing again.  (public key A sends to public key B sends to public key
C: B publishes COM( transaction B->C ), sends the reveal of COM( transaction
A->B ), and COM transaction B->C ) to C.  C waits 6 confirmations and is
convinced.  So its the approach is composable, and in fact the network
doesnt learn the size of the transaction even, though the spend grows each
time.  Eventually presumably someone will publish will the confirmations to
the network to trim the tansaction size, though it is not strictly
necessary, and the transaction flow is small and direct (no network scaling
issues), so that it wouldnt be a huge problem to have a 1MB payment
representing 1000s of hops of network blind transactions.  (For the
composable network blind respending the commitment has to commit publicly to
both the sender and next hop recipient keys, so the network can see how long
the chain is).

Probably you can cope with multiple inputs and outputs, and maybe given even
you can work with a 100% dishonest network mining network (all the dishonest
miner can do is selectively DoS transactions if they are all network blind
except the mining), maybe the mining can even be decoupled from the voting,
as you no longer demand much from the voting process.  That admits more
interesting things like pool free direct mining, low variance hashcash
coins, probably.  Many things to think through.

I suppose the commitment could be described as a blind symmetric commitment.

Adam

On Tue, May 14, 2013 at 04:09:02PM +0200, Adam Back wrote:
> [...]
>
>One related concept is commitments.  I think its relatively easy to commit
>to a payment and lock a coin without identifying yourself, until the
>commitment is released.  You might do the commitment, wait 6-blocks for
>confirmation, then reveal the commitment.  Then that is like a self-issued
>green coin with no need for trust, that can be immediately cleared.  The
>recipient has to be committed to at the same time to prevent double
>spending.
>
>So just commit = H( input-pub ) H( transaction ) and put it in the block
>chain.  Where transaction the is usual ( input signature, output-pub,
>script).  (Fee for the commit would have to come from an unlinked coin or
>the input-pub reveals the coin).  Wait 6 blocks, send/reveal the transaction
>(free because fee was already paid).  Validators check input-pub hash
>against committed coins by hash, check the transaction hash, and the usual
>ransaction validations = sum inputs, otherwise reject.  The user better pay
>change if any to a different public key, as the inputs public keys are one
>use - are after the reveal they are DoS lockable by other people reposting
>H( input-pub ).
>
>The input-pub coin is locked as normal transactions have their public key hash
>validate as not being locked.
>
>Adam

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1414 bytes --]

On Wed, May 15, 2013 at 12:25:09PM +0200, Adam Back wrote:

Protocols aren't set in stone - any attacker that controls enough
hashing power to pose a 51% attack can simply demand that you use a
Bitcoin client modified to provide the attack with the full transactions
from the beginning. Any blocks containing transactions with unknown
contents will be attacked into oblivion.

On the other hand if the "attacker" has less than 50% of the hashing
power, they have no choice but to let other blocks through, and provided
miners are free from regulation imposed on them you can bid to get your
transactions mined with fees. Anyone using a blockchain-based
crypto-currency simply has to accept that mining is a random process and
getting a transaction confirmed is inherently unreliable.

> So in a previous mail I described a simple, extremely efficient and easy to
> implement symmetric key commitment that is unlinkable until reveal time (at
> bottom).  I think this can help improve the byzantine generals problem, that
> bitcoin only defends to simple majority (with one vote per CPU power), and
> so assumes most nodes by cpu power are honest.  With this simple protocol
> change you dont need any honest nodes, just some honest clients to spend to,
> to have your transaction accepted.  

-- 
'peter'[:-1]@petertodd.org
00000000000001754b62829d854463fa72fe7d972a7b7d13d0c30fc86423773c

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

On Wed, May 15, 2013 at 07:19:06AM -0400, Peter Todd wrote:
>Protocols aren't set in stone - any attacker that controls enough
>hashing power to pose a 51% attack can simply demand that you use a
>Bitcoin client modified [to facilitate evaluation of his policy]

Protocol voting is a vote per user policy preference, not a CPU vote, which
is the point.  Current bitcoin protocol is vulnerable to hard to prove
arbitrary policies being imposable by a quorum of > 50% miners.  The blind
commitment proposal fixes that, so even an 99% quorum cant easily impose
policies, which leaves the weaker protocol vote attack as the remaining
avenue of attack.  That is a significant qualitative improvement.

The feasibility of protocol voting attacks is an open question, but you
might want to consider the seeming unstoppability of p2p protocols for a
hint.

Adam

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Caleb James DeLisle]

I can't see this working, if 51% of the mining power doesn't like your
coins, when you create the commitment they will reject it.
If the commitment is opaque at the time of inclusion in the block then
I will create multiple commitments and then after revealing the
commitment and spend to you I will reveal the earlier commitment which
commits the coins to an address I control.

On the topic of reversibility, I suspect in the long term the lack of
chargebacks will create issues as criminals learn that for the first
time in history, kidnap & ransom is effective. Suffice to say after the
first >= $10mn kidnapping-for-bitcoin heist, governments will be forced
to decide how they view the system. It will likely fall somewhere between
"arrest/question anyone identified holding tainted coins" to something
nonsensical and reactionary like "blocking" bitcoin as Iran does TOR.

Thanks,
Caleb



On 05/15/2013 07:49 AM, Adam Back wrote:
> On Wed, May 15, 2013 at 07:19:06AM -0400, Peter Todd wrote:
>> Protocols aren't set in stone - any attacker that controls enough
>> hashing power to pose a 51% attack can simply demand that you use a
>> Bitcoin client modified [to facilitate evaluation of his policy]
> 
> Protocol voting is a vote per user policy preference, not a CPU vote, which
> is the point.  Current bitcoin protocol is vulnerable to hard to prove
> arbitrary policies being imposable by a quorum of > 50% miners.  The blind
> commitment proposal fixes that, so even an 99% quorum cant easily impose
> policies, which leaves the weaker protocol vote attack as the remaining
> avenue of attack.  That is a significant qualitative improvement.
> 
> The feasibility of protocol voting attacks is an open question, but you
> might want to consider the seeming unstoppability of p2p protocols for a
> hint.
> 
> Adam
> 
> ------------------------------------------------------------------------------
> AlienVault Unified Security Management (USM) platform delivers complete
> security visibility with the essential security capabilities. Easily and
> efficiently configure, manage, and operate all of your security controls
> from a single console and one unified framework. Download a free trial.
> http://p.sf.net/sfu/alienvault_d2d
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

On Wed, May 15, 2013 at 08:40:59AM -0400, Caleb James DeLisle wrote:
>If the commitment is opaque at the time of inclusion in the block then
>I will create multiple commitments and then after revealing the
>commitment and spend to you I will reveal the earlier commitment which
>commits the coins to an address I control.

Bit-commitments are based on deterministic one-way functions eg like SHA1(
SHA256( public key ) ) Obviously it has to be a different one-way function
to the coin address calculation which is RIPEMD( SHA256( public key ) ) as
that is already public.  Alternatively it can be a different serialization
using the same hash eg RIPEMD( SHA256( 1 || public key ) ).

There is only one commitment possible per public key - so you can only
create one commitment that would validate to a receiver, or to the network. 
The network checks that there are no non-blind double spends of committed
coins which it can do as spends require disclosure of the public key, which
allows existing commitments to be verified, and it similarly qchecks that
there are no blind double-commitments.

Each committed coin would be:

one-spend-commit = Com( spender pub ), Com( transaction )

where Com is implemented as the above hash.  The network just places the
commitments in order as with conventional transactions.

The committed coins are not linkable to your non-blind coin because you did
not reveal your public key in the (largely passive) act of receiving to a
coin address.

>On the topic of reversibility, I suspect in the long term the lack of
>chargebacks will create issues as criminals learn that for the first
>time in history, kidnap & ransom is effective. 

The temporary unlinkability (until commitment reveal) is a necessary side
effect, not a cryptographic anonymity feature like zerocoin.  The
transactions are identical to bitcoins once revealed.  How long the
committed transaction chains can be between reveals is an implementation
choice could be 1 hop, or as long as you like.  (Actually it appears to be
up to the individual users how long the maximum chain they accept is - the
network itself, though ordering the committed spends (if there are multiple
spends on the same key) cant even tell how long the commitment payment
chains are).

Obviously the first coins in the network ordered committed coins on the same
key up to the coin value are spends as verified by the recipient, the rest
are double-spend and ignored.  If someone wants to waste fees by sending
more spends than there inputs thats up to them.

Probably the typical user doesnt care about long committed chains  other
than their wallet will bloat if the chains are too long, so probably they
would periodically compact it by revealing the long chains.  Committed coins
are probably a bit less SPV client friendly, though with correct formatting
in the merkle trees between blocks, probably a committed coin holder can
provide enough proof to an SPV client to verify even multi-spend committed
coins directly (without a network feed).

About privacy, up to the entire commitment chain can be opened at any time
(to other people or to the bitcoin network in general) with the cooperation
of any user on the chain (up to the point they saw it), so while the blind
commitment protocol is not vulnerable to a > 50% power quorum unilaterally
imposed policy (without even needing client updates), it is fully dependent
on the good will of the recipients for its temporary unlinkability.  Thats
the point: it puts policy control in the users hands not in the > 50% power
quorum.

If you want cryptographic anonymity its better to look to zerocoin.  You may
have noticed zero coin talked about optional fraud tracing.  Its usually
trivial to add tracing to an otherwise privay preserving protocol.

The blind commitment if implemented as described (and its not obvious how to
get more privacy from it) offers somewhat like community policing.  Users on
the chain can still themselves do fraud tracing, or any policy they choose,
on any blind committed coins that they receive.  If they dont like the
colour of them they can refund them.  The point is to enforce that this is a
free uncoerced community choice, by individual end users, not a > 50% cpu
power quorum choice surreptitiously imposed.

Adam

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Caleb James DeLisle]

On 05/15/2013 12:21 PM, Adam Back wrote:
> On Wed, May 15, 2013 at 08:40:59AM -0400, Caleb James DeLisle wrote:
>> If the commitment is opaque at the time of inclusion in the block then
>> I will create multiple commitments and then after revealing the
>> commitment and spend to you I will reveal the earlier commitment which
>> commits the coins to an address I control.
> 
> Bit-commitments are based on deterministic one-way functions eg like SHA1(
> SHA256( public key ) ) Obviously it has to be a different one-way function
> to the coin address calculation which is RIPEMD( SHA256( public key ) ) as
> that is already public.  Alternatively it can be a different serialization
> using the same hash eg RIPEMD( SHA256( 1 || public key ) ).


Ahh thanks for clearing that up, although it would limit the possibilities
of scripting it is silly of me not to think of it.


> 
> There is only one commitment possible per public key - so you can only
> create one commitment that would validate to a receiver, or to the network. The network checks that there are no non-blind double spends of committed
> coins which it can do as spends require disclosure of the public key, which
> allows existing commitments to be verified, and it similarly qchecks that
> there are no blind double-commitments.
> 
> Each committed coin would be:
> 
> one-spend-commit = Com( spender pub ), Com( transaction )
> 
> where Com is implemented as the above hash.  The network just places the
> commitments in order as with conventional transactions.
> 
> The committed coins are not linkable to your non-blind coin because you did
> not reveal your public key in the (largely passive) act of receiving to a
> coin address.
> 
>> On the topic of reversibility, I suspect in the long term the lack of
>> chargebacks will create issues as criminals learn that for the first
>> time in history, kidnap & ransom is effective. 
> 
> The temporary unlinkability (until commitment reveal) is a necessary side
> effect, not a cryptographic anonymity feature like zerocoin.  The
> transactions are identical to bitcoins once revealed.  How long the
> committed transaction chains can be between reveals is an implementation
> choice could be 1 hop, or as long as you like.  (Actually it appears to be
> up to the individual users how long the maximum chain they accept is - the
> network itself, though ordering the committed spends (if there are multiple
> spends on the same key) cant even tell how long the commitment payment
> chains are).
> 
> Obviously the first coins in the network ordered committed coins on the same
> key up to the coin value are spends as verified by the recipient, the rest
> are double-spend and ignored.  If someone wants to waste fees by sending
> more spends than there inputs thats up to them.
> 
> Probably the typical user doesnt care about long committed chains  other
> than their wallet will bloat if the chains are too long, so probably they
> would periodically compact it by revealing the long chains.  Committed coins
> are probably a bit less SPV client friendly, though with correct formatting
> in the merkle trees between blocks, probably a committed coin holder can
> provide enough proof to an SPV client to verify even multi-spend committed
> coins directly (without a network feed).
> 
> About privacy, up to the entire commitment chain can be opened at any time
> (to other people or to the bitcoin network in general) with the cooperation
> of any user on the chain (up to the point they saw it), so while the blind
> commitment protocol is not vulnerable to a > 50% power quorum unilaterally
> imposed policy (without even needing client updates), it is fully dependent
> on the good will of the recipients for its temporary unlinkability.  Thats
> the point: it puts policy control in the users hands not in the > 50% power
> quorum.


That is indeed interesting. If I understand this properly Alice commits coins
to pay to Bob and gives Bob the transaction, Bob then commits to pay to Charlie
and gives him the related transaction. If Charlie wants to collect the bitcoin
he then reveals Alice's transaction and Bob's.

I think what you're trying to do is *almost* possible now (ab)using BIP-0016
In the output of the previous tx you put:

OP_HASH160 [20-byte-hash-value] OP_EQUAL

and in the next tx you use a new type of input which specifies it's value but
not the output which is spent. In the input script you place:

OP_DUP OP_1ADD OP_HASH160 [20-byte-hash-value] OP_EQUALVERIFY

Then a serialized script containing the normal stuff as well as the last
transaction hash and output index would be passed around out of band and the
validating nodes would execute each script with a shared stack, beginning with
the out of band one, then the input one (the OP_EQUALVERIFY) then the output.
When the serialized sigscript reaches the bottom of the stack, having been
verified twice, it will now be evaluated as per the rules of P2SH.

None of this probably works in the real world since I'm not familiar with the
actual implementation of P2SH and it probably has quite a number of things
which will break if used this way but it is interesting to see that in theory
it is possible with little change to the protocol (just a new input format).

Thanks,
Caleb

> 
> If you want cryptographic anonymity its better to look to zerocoin.  You may
> have noticed zero coin talked about optional fraud tracing.  Its usually
> trivial to add tracing to an otherwise privay preserving protocol.
> 
> The blind commitment if implemented as described (and its not obvious how to
> get more privacy from it) offers somewhat like community policing.  Users on
> the chain can still themselves do fraud tracing, or any policy they choose,
> on any blind committed coins that they receive.  If they dont like the
> colour of them they can refund them.  The point is to enforce that this is a
> free uncoerced community choice, by individual end users, not a > 50% cpu
> power quorum choice surreptitiously imposed.
> 
> Adam
> 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

btw I posted some of this thread on the dev forum:

https://bitcointalk.org/index.php?topic=206303.msg2157994#msg2157994

A related idea is occuring to me that maybe these committed transactions
could actually as a side effect make bitcoin scale slightly better by
reducing the p2p flood filled transaction size.

As I said on the forum:

> Note committed transactions are more compact than regular transactions -
> they are just two hashes, so they reduce network bandwidth and make
> bitcoin more scalable to the extent that transaction reveals stay off
> network.  (As well as more secure against centralization policy risks). 

Surely its lower bandwidth for nodes to send only committed transactions to
the p2p network, and pass committed payment chains direct to recipients.

Say committed transaction size is c (20bytes+32bytes+16bytes +header ~ 72
bytes?) And full transaction smallest size is t (txin=20bytes, amount out
4bytes, sender pub key 32bytes, recip address 20bytes, change address
20bytes, formatting 5 bytes, ECDSA signature 64bytes, script 10 byte surely
~ 175bytes)?  Thats over twice the size.  Probably average more, and it is
sent to every node.  Its always going to be lower bandwidth to send
transactions to the recipients than to send to the network, even if you have
to increase the transaction size with each respend.  The alternative is for
the entire network to see the same transaction.

I think the commitment needs to bind the two parts together eg 

(blind-sender, auth-tag, tx-commit)

blind-sender = SHA1( SHA256( 1, pub ) )
auth = HMAC-SHA256-128( K, tx-commit )
tx-commit = SHA-256( tx )

Or some variantion, and you must not reuse the pub key, and must send change
if any to a different address, otherwise chain recipients or malicious
forwarders could lock your coin, by putting random junk onto the network
which would be unverifiable, and non-disclaimable - you cant prove you dont
know the preimage of some junk.  The MAC prevents it.  Maybe there's a more
compact way to do it even, but that works efficient demonstration of
security feasibility.

Other public key variants could be possible, P = xG is the ECDSA public key,
x the private key, G base point.  Sender could reveal P' = cP, c some fixed
constant (computing c from cP is ECDL problem considered oneway & hard), and
a signature by private key x' = cx over the tx-commit.  That is a publicly
auditable commitment also, but one tht can make an ECDSA signature over the
tx-commit hash, and can be revealed by revealing P later.  However that
imposes public key computation on the validation (which it already currently
does, but faster validation as above is nicer).  With that one you dont even
have to verify the transaction signature on reveal :)  You already did it,
just provide the tx that hashes to the signed hash, and P for the recipient
to verify the signature was made by cP.

Adam

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Gavin]

Busy with pre-conference stuff, not following details of this conversation...

... but it sounds a lot like the "guy fawkes" protocol Zooko was thinking about a year or so ago.

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Gregory Maxwell]

On Wed, May 15, 2013 at 6:24 PM, Gavin <gavinandresen@gmail.com> wrote:
> Busy with pre-conference stuff, not following details of this conversation...
>
> ... but it sounds a lot like the "guy fawkes" protocol Zooko was thinking about a year or so ago.

Sort of, but in a guy fawkes signature you use the commitment to hide
the preimage that proves you had authority to spend a coin.   Adam
proposes you do this in order to hide _which coin you're spending_.

This has obvious anti-DOS complications, but Adam deftly dodged my
initial attempts to shoot him down on these grounds by pointing out
that you could mix blinded and blinded inputs and have priority and
transaction fees come from only the unblinded ones.

Effectively,  it means that so long as you could convince the network
to let you spend some coins, you could also spend other ones along for
the ride and the network wouldn't know which ones those were until it
was too late for it to pretend it never saw them.

I think there are all kinds of weird economic implications to this— a
blinded payment would seem to have a different utility level to an
unblinded one: you can't use it for fees— except you can unblind it at
any time.  And the discontinuousness  ("two types of inputs") and that
it would enable mining gibberish (though perhaps not data storage, if
you see my preimage solution to that) seems awkward and I think I have
to spend some time internalizing it before I can really think through
the implications.

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 2556 bytes --]

Conceptually it sounds a lot like ZeroCoin (not in implementation)?

I'm not really convinced miner cartels that try to exclude transactions are
likely to be a big deal, but such schemes could I suppose be kept in a back
pocket in case one day I'm proven wrong.


On Wed, May 15, 2013 at 6:39 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Wed, May 15, 2013 at 6:24 PM, Gavin <gavinandresen@gmail.com> wrote:
> > Busy with pre-conference stuff, not following details of this
> conversation...
> >
> > ... but it sounds a lot like the "guy fawkes" protocol Zooko was
> thinking about a year or so ago.
>
> Sort of, but in a guy fawkes signature you use the commitment to hide
> the preimage that proves you had authority to spend a coin.   Adam
> proposes you do this in order to hide _which coin you're spending_.
>
> This has obvious anti-DOS complications, but Adam deftly dodged my
> initial attempts to shoot him down on these grounds by pointing out
> that you could mix blinded and blinded inputs and have priority and
> transaction fees come from only the unblinded ones.
>
> Effectively,  it means that so long as you could convince the network
> to let you spend some coins, you could also spend other ones along for
> the ride and the network wouldn't know which ones those were until it
> was too late for it to pretend it never saw them.
>
> I think there are all kinds of weird economic implications to this— a
> blinded payment would seem to have a different utility level to an
> unblinded one: you can't use it for fees— except you can unblind it at
> any time.  And the discontinuousness  ("two types of inputs") and that
> it would enable mining gibberish (though perhaps not data storage, if
> you see my preimage solution to that) seems awkward and I think I have
> to spend some time internalizing it before I can really think through
> the implications.
>
>
> ------------------------------------------------------------------------------
> AlienVault Unified Security Management (USM) platform delivers complete
> security visibility with the essential security capabilities. Easily and
> efficiently configure, manage, and operate all of your security controls
> from a single console and one unified framework. Download a free trial.
> http://p.sf.net/sfu/alienvault_d2d
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

[-- Attachment #2: Type: text/html, Size: 3339 bytes --]

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Gregory Maxwell]

On Wed, May 15, 2013 at 7:22 PM, Mike Hearn <mike@plan99.net> wrote:
> Conceptually it sounds a lot like ZeroCoin (not in implementation)?

Zerocoin conceals the connection from everyone forever, assuming the
underlying trapdoor problem is computational infeasible, but at great
cost.

Adamcoin, depending on how its done, at most conceals the transactions
from people who aren't a party to them... though as time goes on
eventually everyone becomes a party to a sufficiently old coin, and
avoiding publication creates quadratic costs in evaluating a private
clique's claims.... so instead an implementation would make the
identities public but only once they're burred a bit.

Perhaps an extreme version of the idea is easier to understand. Ignore
DOS attacks for a moment and pretend there is never any address reuse:

Everyone creates txouts paying a P2SH addresses that have a OP_PUSH
nonce in them and tell you recipient the nonce out of band.

When the recipients spend those coins they provide the script but not the nonce.

The recipient knows what coins he's spending, but the public does not.

The public can tell there is no double spend though, because they'd
see the same script twice. The person he's paying may be skeptical
that he actually has any coin and didn't just mine some gibberish, but
our spender tells that their receiver the nonce, and that person can
see the coin available for spending in the chain and also see that
there are no double spends.

This could actually go on forever with no ambiguity over who owns
what, but the out of band proofs that you have to give people when you
spend coins would grow with the history of the coins.

Since there wouldn't be much privacy once a transaction was
sufficiently split up in any case, you instead just publish the
unblindings once transactions are sufficiently buried. Thus bounding
the growth of the proofs.   The reason I say I need to internalize
this more is mostly that I need to think about attacks on the
publication for 'tained' transactions being more or less isomorphic
to just refusing to allow spending of the 'tainted' coins in any case.

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Caleb James DeLisle]

Not only does the size of the proof grow endlessly as the coin is
passed around, the size of the UTXO set grows endlessly as more and
more of the already spent coins cannot be proven to have been spent
because the proofs are passed out-of-band. I never said the idea was
good, just interesting :)

Thanks,
Caleb


On 05/15/2013 10:45 PM, Gregory Maxwell wrote:
> On Wed, May 15, 2013 at 7:22 PM, Mike Hearn <mike@plan99.net> wrote:
>> Conceptually it sounds a lot like ZeroCoin (not in implementation)?
> 
> Zerocoin conceals the connection from everyone forever, assuming the
> underlying trapdoor problem is computational infeasible, but at great
> cost.
> 
> Adamcoin, depending on how its done, at most conceals the transactions
> from people who aren't a party to them... though as time goes on
> eventually everyone becomes a party to a sufficiently old coin, and
> avoiding publication creates quadratic costs in evaluating a private
> clique's claims.... so instead an implementation would make the
> identities public but only once they're burred a bit.
> 
> Perhaps an extreme version of the idea is easier to understand. Ignore
> DOS attacks for a moment and pretend there is never any address reuse:
> 
> Everyone creates txouts paying a P2SH addresses that have a OP_PUSH
> nonce in them and tell you recipient the nonce out of band.
> 
> When the recipients spend those coins they provide the script but not the nonce.
> 
> The recipient knows what coins he's spending, but the public does not.
> 
> The public can tell there is no double spend though, because they'd
> see the same script twice. The person he's paying may be skeptical
> that he actually has any coin and didn't just mine some gibberish, but
> our spender tells that their receiver the nonce, and that person can
> see the coin available for spending in the chain and also see that
> there are no double spends.
> 
> This could actually go on forever with no ambiguity over who owns
> what, but the out of band proofs that you have to give people when you
> spend coins would grow with the history of the coins.
> 
> Since there wouldn't be much privacy once a transaction was
> sufficiently split up in any case, you instead just publish the
> unblindings once transactions are sufficiently buried. Thus bounding
> the growth of the proofs.   The reason I say I need to internalize
> this more is mostly that I need to think about attacks on the
> publication for 'tained' transactions being more or less isomorphic
> to just refusing to allow spending of the 'tainted' coins in any case.
> 
> ------------------------------------------------------------------------------
> AlienVault Unified Security Management (USM) platform delivers complete
> security visibility with the essential security capabilities. Easily and
> efficiently configure, manage, and operate all of your security controls
> from a single console and one unified framework. Download a free trial.
> http://p.sf.net/sfu/alienvault_d2d
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

On Wed, May 15, 2013 at 07:45:34PM -0700, Gregory Maxwell wrote:
>[committed coins] depending on how its done, at most conceals the
>transactions from people who aren't a party to them...  though as time goes
>on eventually everyone becomes a party to a sufficiently old coin, and
>avoiding publication creates quadratic costs in evaluating a private
>clique's claims....  so

I believe the coin size and verification cost is linear not quadratic, but
maybe it depends on the parameter you're measuing in.  The coin size is
linear with the number of committed (uncompacted) spends.  You can view
reveals as committed compaction.  For efficiency a recipient of a committed
coin may as well compact and spend in one transaction so no new messages are
created.

Btw I believe if one were concerned about the committed coin size, I can see
a small tweak that would keep the size of the committed coins small eg
256-bit regardless of number of spends (no longer grows), and let the block
store the encrytped & MACed commitment.  Then compaction is no longer a
concern.  However I think that is SPV -> SPV client unfriendly.  (A full
client -> SPV client should still be workable as the full client could
alternatively send the client the MACed data and key, rather than have him
look at it from his block history.)  (Crypto sketch below).

However I am not sure multi-spend committed coin size is really a concern
because to the extent people hold long commitments without revealing to the
network for the long term, that is a bandwidth saving to the network.

Overall about privacy it would be typically temporary, though the peers have
the technical means to react and defend themselves by using longer committed
chains if dishonest mining is detected on a significant scale.

>instead an implementation would make the identities public but only once
>they're burred a bit.

That was the seed idea.  The more aggressive "spend lots of times in
committed form" is just a technical threat that will keep dishonest mining
in check.  By definition the coin is already irrevocably spent before the
reveal (without the threat of having the dishonest miners endlessly redoing
their own deeply burried work).  The only person who could be punished by
policy by >50% dishonest miner (retroactively) is the recipient, not the
spender, and the punishment is very muted: all he can do is prevent coin
compaction.  If the committed coins are small, compact doesnt even hurt the
committed coin user, just network itself.  Therefore a dishonest miner is
wasting his time his dishonesty cant enforce his dishonest policy.

To store the commitments in the block chain replace:

> (blind-sender, auth-tag, tx-commit)
> 
> blind-sender = SHA1( SHA256( 1, pub ) )
> auth = HMAC-SHA256-128( K, tx-commit )
> tx-commit = SHA-256( tx )
> K = SHA-256( pub )

with:

(blind-sender, auth-tag, encrypted-tx-commit)

	blind-sender = SHA1( SHA256( 1, pub ) )
	auth = HMAC-SHA256-128( K, encrypted-tx-commit )
	encrypted-tx-commit = AES( K, tx-commit )   (*)
	K = SHA-256( pub )

then a reveal is just to send the recipient the public key (32 bytes)
per hop, still linear but ~3x smaller.

I suggested fixed size committed coin spends, that also you can do but with
public key crypto needed probably, and so dropping to the verification
efficiency of standard transactions.  Sketch 2:

(blind-sender, auth-tag, encrypted-tx-commit)

(pub key P = xG, G = base point)

	blind-sender = cP (public key EC multiplied by constant c)
	sig = ECDSA( cx, encrypted-tx-commit )
	encrypted-tx-commit = AES( K, tx-commit )
	K = random

as K is random, knowledge of P if stored unencrypted does not allow
committed spend-to-junk.  To reveal to a recipient just send them P and K at
each hop.  (Same K each time, anyone on the committed coin spend chain can
already chose to reveal at any time so no loss of security.)

You dont need to verify a second signature inside the tx-commit because you
already signed the encrypted-tx which binds to it (encryption with out MAC
is malleable but you cant change it at all without invalidating the
encryption).  Just need to check the input tx in the tx-commit has P as its
recipient.  P does not even need to go into tx-commit as its already bound
by cP and signature security (cant create a signature with someone elses
key).  So I think the commited coins of this form are the same size and
verification cost for the network.  And small and fixed size to spend
offline.  (32+32=64 bytes fixed).

Adam

(*) You should not as a principle re-use keys across algorithms, I omitted a
second key for simplicity.  Really K1 = SHA256( 1||pub ), K2 = SHA256(
2||pub ) encrypted-tx-commit = AES( K1, tx-commit ), auth = HMAC( K2,
encrypted-tx-committ ).  Or more simply a combined authenticated mode like
CCM or GCM and a single key managed by the mode.

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability)

[Adam Back]

More somewhat improved crypto stuff...

On Thu, May 16, 2013 at 01:32:22PM +0200, Adam Back wrote:
>I suggested fixed size committed coin spends [...]
>
>(blind-sender, auth-tag, encrypted-tx-commit)
>
>(pub key P = xG, G = base point)
>
>	blind-sender = cP (public key EC multiplied by constant c)
>	sig = ECDSA( cx, encrypted-tx-commit )
>	encrypted-tx-commit = AES( K, tx-commit )
>	K = random
>
>as K is random, knowledge of P if stored unencrypted does not allow
>committed spend-to-junk.  To reveal to a recipient just send them P and K at
>each hop.  (Same K each time, anyone on the committed coin spend chain can
>already chose to reveal at any time so no loss of security.)

Actually same K every time is not so hot, as then earlier in the committed
spend chain, can force a reveal for someone later.  A clearer requirement is
that each person should only be able to reveal committed coin chains up to
the point of their direct involvement.

So that is easily fixable, just include the K for the input committed coin
in the encrypted-tx-commit, as above but:

	encrypted-tx-commit = AES( K_i, K_{i-1} || tx-commit )
	K_i = random

(different K for each spend).

And actually for symmetric encrypted variant the coin as specified was
already evaluatable with fixed size committed spend (of the last public key)
- I just didnt realize it in the previous mail: the input public key is
necessarily revealed when processing the decrypted tx-commit, allowing
identification and validation of the txin, and validation recursively back
to the first non-committed coin.  With symmetric verification, the
limitation is one-use coin committed addresses (and inability to remove
spend to committed junk with public validation, though there is the tx fee
as a discouragement, it does bloat a recipients verification and so maybe
frustates SPV->SPV consumption of committed coins).

(blind-sender, auth-tag, encrypted-tx-commit)

         blind-sender = SHA1( SHA256( 1, pub ) )
         auth = HMAC-SHA256-128( K, encrypted-tx-commit )
         encrypted-tx-commit = AES( K, tx-commit )
         K = SHA-256( pub )

Adam

ps and it would be better and clearer to read also in terms of purpose of
hashes, to use a KDF like IEEE P1363 KDF2, or PKCS#5 PBKDF2 with 1
iteration, rather than adhoc hashes for key derivation.