blind symmetric commitment for stronger byzantine voting resilience

[adam3us]

So in a previous mail

https://bitcointalk.org/index.php?topic=205533.msg2149057#msg2149057

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

[1713462132]

1713462132

[1713462132]

1713462132

[1713462132]

1713462132

[adam3us]

Here's two of my replies to comments on the above on on the dev mailing list.

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.

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:

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

[gmaxwell]

Or, you could just always pay to a _new_ address as the system was intended and specified and you achieve the same effect with no overhead, unless you propose to blind inputs and then miners cannot check _validity_, thus opening up tons of attacks.

[adam3us]

Or, you could just always pay to a _new_ address as the system was intended and specified and you achieve the same effect with no overhead, unless you propose to blind inputs and then miners cannot check _validity_, thus opening up tons of attacks.

Paying to a new address doesnt protect you from arbitrary policies being imposed by fiat by big miners based on the coin source or taint.  I described the example policies which users may find unsatisfactory but be powerless to robustly detect nor prevent with current protocols.  This is a solution to that "(cpu) might makes right" current problem.

The inputs are blinded (revealing SHA1( SHA256( public key ) ) and that does not associate with the public key hashed in the input transaction, until the commit is revealed.  There are no attacks because miners can check the validity because when a normal transaction is made the public key is revealed and can be verified against the committed key.  If multiple committed spends are made, the network just serves to order them.  How many of them are needed to add up to the input amount is verified by the recipient.  It is the spenders job to provide the revealed commitment (the committed transaction) to allow them to verify.  When the commitment is revealed back to the network, eg after 6-blocks, or when the recipient spends, or after a few commitment based spends, the network itself can do the value based validation also.  I dont see any attacks.

Adam

[iddo]

Why wouldn't the big miners cartel still be able to impose their greedy/malicious policies and deny your transaction, simply by refusing to put the commitment that you reveal in the blocks that they generate (and they'd reject blocks that others generate if your commitment is included). Do you mean that the commitments don't reside inside the blockchain and therefore there isn't any need to do PoW computation on them? If so, where would the commitments reside? If you don't see any attacks then you're highly optimistic.

[adam3us]

Why wouldn't the big miners cartel still be able to impose their greedy/malicious policies and deny your transaction, simply by refusing to put the commitment that you reveal in the blocks that they generate (and they'd reject blocks that others generate if your commitment is included).

The commitment is blind - the miner, nor anyone else other than the spender can tell which input the committed (blind) transaction relates to, nor who the sender is, nor who the recipient is, nor the amount.  When there is no information miners cant apply a selective policy - all they can do is random DoS which loses them fees.  If this is part of the protocol, which I argue it should be, and all payments happen this way they have no choice - they either have to play honestly or fork the protocol.  (Go form an alt-coin with a revised protocol, otherwise network continues without them.)

So the blind commitment goes into the block chain.  It sits there until the recipient discloses it, which will be after 6-blocks, or longer if they wait until they come to re-spend it, or maybe never even, because they can re-spend coins in committed form equally well.  If the recipient chooses to reveal the commitment (send the committed transaction) to the network, the network can either include it in later blocks or not.  If they do not, it does not alter the validity and irrevocability of the transaction, as the recipient can still re-spend committed transactions in the same way.  The only motive to even reveal commitments to the block chain is to compact your wallet (otherwise you have to keep the committed transaction chain as coins grow on each committed coin spend, you have to reveal the whole transaction history to the next recipient so they can check it relative to the commitments on the block chain for double spending).

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).

Do you mean that the commitments don't reside inside the blockchain and therefore there isn't any need to do PoW computation on them? If so, where would the commitments reside? If you don't see any attacks then you're highly optimistic.

The commitments do reside on the block chain, but they are blind.  So no selective policy can be applied to them.

The point is the transaction once revealed is already done in the eyes of the recipient, and everyone else, including the miner cartel.  You dont even need to reveal it to the network, thats just optional committed coin transaction chain compaction.

The only way for the cartel to undo a subsequently revealed committed transaction it is to redo all the work that piled on top of the commitment (which the cartel did the bulk of themselves!).  That might be 6-blocks or 100-blocks or 1000-blocks (a week).  Even if a cartel with 75% of the network power tried to do that its difficult.  In the time they compute a fresh 6-blocks, the rest of the network has 2-more blocks.  Also each time a new committed transaction is revealed that they wish to remove, they have to redo the work from scratch starting another chain fork.  I think it becomes hopeless for them fast, someone can commit a few hundred part payments, and reveal one every time the mining pool gets near 6-block chain fork.  The miners earn no new fees for this work.  I think its game over - they can be trivially made to fight their own compute power perpetually and unprofitably.  Users would become suspicious if a 6-block or 8-block fork formed, they may just reject it outright, or investigate manually to observe that whats going on is some revealed coins are deleted, and whats common about the coins.

A user who was concerned could wait thousands of blocks before revealing, or simply live perpetually with a bigger coin (eg a year, you can still re-spend it in its committed form).  Having to frequently fork a year of block work is untenable as a way to impose a policy.  The threat is minimal at this point, and the effort to revoke transactions herculean and un-winnable at volume.

Adam

[iddo]

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right? On the other hand, if Bob wishes to decommit and spend the coins before sending the product to Alice, then the big miners cartel can decide whether it fits their policies, and reject Bob's attempts if they'd like. Therefore Bob won't accept Alice's tainted coins in the first place, and we fail to achieve your objective because the big miners cartel still has control?

[gmaxwell]

So the blind commitment goes into the block chain.  It sits there until the recipient discloses it,

Right. Now I, GriefferMcEndYourCoin, produce 100 terabytes a second of junk commitment transactions with blinded inputs for you to mine.

Because they're blinded you cannot distinguish them from valid spends of existing coins, so you include them in the chain. (and if you can, then you can impose policy).

[adam3us]

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right?

No because an attempt to pre-spend a committed transaction, via a normal transaction, can be validated against committed transactions.  That is because a normal transaction necessarily includes the address public key, for validation of the ECDSA signature on the transaction.  Then the network can see that the hash of the public key has already been spent via an earlier commitment and so the pre-spend attempt is rejected.

On the other hand, if Bob wishes to decommit and spend the coins before sending the product to Alice, then the big miners cartel can decide whether it fits their policies, and reject Bob's attempts if they'd like. Therefore Bob won't accept Alice's tainted coins in the first place, and we fail to achieve your objective because the big miners cartel still has control?

As soon as the commit has reached 6-blocks the coin is spent, whether or not its revealed publicly.  That is because a recipient can spend it in committed form via a second commitment (with the address he received it with).  If Bob uses the same commit protocol with Carol, he can send her both the committed tx he received from Alice, and his own new committed tx.

Revealing the commitment to the network at all, ever is just to compact the committed coin size which grows with each committed spend. 

So even if or when the transaction is revealed to the network, the dishonest mining cartel has a choice: either ignore the compaction request (which doesnt stop it, just delays the owners attempt to compact his coin... eventually another mine will accept it),  or he can include it (desired outcome), or finally and very difficult the dishonest miner has to recompute the chain and create a fork back to the initial commitment which is at this point likely some weeks under.  That seems quite impractical and people can play games with the dishonest miner to waste all his compute fighting his own power by revealing fresh policy bait coins frequently enough that the dishonest miner never completes a fork.  He has to restart the fork attempt from the oldest coin depth each time!

You might think the coin growing each time is bad, but actually its saving the network bandwidth.  Consider if you are able to compact your coin, by having he miners accept it, all full  nodes in the network must receive it and process it.  If you spend it in committed fashion only the new commitment goes to the network, the payment happens direct between nodes.  Note the commitment is 2-3x smaller than an actual transaction.

Adam

[adam3us]

So the blind commitment goes into the block chain.  It sits there until the recipient discloses it,

Right. Now I, GriefferMcEndYourCoin, produce 100 terabytes a second of junk commitment transactions with blinded inputs for you to mine.

Because they're blinded you cannot distinguish them from valid spends of existing coins, so you include them in the chain. (and if you can, then you can impose policy).

The committed transactions have to include fees (in the clear outside of he commitment), like normal transactions, then if you do that the miners get rich and you get poor.

Clearly the spender needs to use coins that he thinks the miners are not going to have a policy against for his fees.

(Ideally we would have direct mineable shares, so that fees could be low enough you can mine them on your GPU without linking, and have them earn direct reward.  However that is a different topic.)

Adam

[gmaxwell]

(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.

All of them have either the problem of quadratic scaling or not being able to tolerate parties entering or leaving the process, or both. As soon as you have asynchronous processing can tolerate new parties being added the concept of beyond majority security starts becoming nonsensical: If most of the users say consensus X is right, and a minority says Y and your protocol could ever choose Y then it permits a _minority_ attack.

The Bitcoin consensus algorithim's properties are intuitively clear, but if you prefer a more a more formal description one is available.

[gmaxwell]

The committed transactions have to include fees (in the clear outside of he commitment), like normal transactions, then if you do that the miners get rich and you get poor.
Clearly the spender needs to use coins that he thinks the miners are not going to have a policy against for his fees.

Interesting notion that you'd mix blinded and unbinded inputs in order to create atomic transactions which still resists the most trivial DOS attacks.... but at the same time it seems a bit ugly: you'd effectively have two kinds of currency with different values, and policy could still be imposed by simply only mining coins which you've seen completely unblinded.  I'll have to digest that for a bit, but its interesting.

(Ideally we would have direct mineable shares, so that fees could be low enough you can mine them on your GPU without linking, and have them earn direct reward.  However that is a different topic.)

complicated scalability challenges there... and I don't really know that this helps: as you point out, a super-majority cabal can reject blocks. So I really do think thats totally orthogonal to policy behavior.

[iddo]

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right?

No because an attempt to pre-spend a committed transaction, via a normal transaction, can be validated against committed transactions.  That is because a normal transaction necessarily includes the address public key, for validation of the ECDSA signature on the transaction.  Then the network can see that the hash of the public key has already been spent via an earlier commitment and so the pre-spend attempt is rejected.
Adam

You wrote that the blind commitment is H(input-pub)H(transaction), what does that mean exactly? If the network can see Alice's hashed address just by looking at H(input-pub)H(transaction) before it's decommitted, then how is it blind? Meaning that if the regular hashed address of Alice was blacklisted as tainted, the network would see it and wouldn't allow Alice to spend her coins, with or without a blind commitment, no?

[adam3us]

You wrote that the blind commitment is H(input-pub)H(transaction), what does that mean exactly? If the network can see Alice's hashed address just by looking at H(input-pub)H(transaction) before it's decommitted, then how is it blind? Meaning that if the regular hashed address of Alice was blacklisted as tainted, the network would see it and wouldn't allow Alice to spend her coins, with or without a blind commitment, no?

It was too abbreviated there.  The more accurate version was in a later post in this thread:

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 ) ).

The idea is to use a different, but also one-way hash. Which can be the same hash function with a fixed prefix concatenated to make it different eg string "1" ( eg 1||public key ).  Then even though you see H( pub-key ) you cant compute H( 1||pub-key ) without computing the hash preimage which is hard.  And the coin address is just H( pub )  (actually RIPEMD160( SHA256( pub ) )) so you dont know pub until someone spends the coin either conventional transaction or committed transaction.  In both cases you can then verify double spend against normal transactions and committed transactions.

Also on the dev list I thought of and fixed a minor insider attack so it really needs to include also a MAC of the tx-commit value or someone can create fake committed transactions that look like you made, but you cant disprove (because you cant compute the hash preimage on junk).  The MAC allows you to believably disavow them because their MAC will be wrong.

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.

And it looks like I forgot to define K = SHA-256( pub ).

Also I suggested a public key variant, however the above is faster to verify for validators.

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 that 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

[gmaxwell]

As an aside: You should take care to not assume any specific signature mechanism. Bitcoin outputs are specified by 'script' and are signed by 'script'. The underlying asymmetric techniques used in script are flexible and can be replaced in a forward compatible way in the future. There are no assumptions about ECDSA anywhere in the blockchain protocol, except that our two existing CHECKSIG opcodes implement ECDSA over a particular curve right now. Baking in an assumption about ECDSA into how the blockchain works would be a major step backwards in terms of generality... and any better-bitcoin stuff should avoid doing so.

[adam3us]

The committed transactions have to include fees (in the clear outside of he commitment), like normal transactions, then if you do that the miners get rich and you get poor.
Clearly the spender needs to use coins that he thinks the miners are not going to have a policy against for his fees.

Interesting notion that you'd mix blinded and unbinded inputs in order to create atomic transactions which still resists the most trivial DOS attacks.... but at the same time it seems a bit ugly: you'd effectively have two kinds of currency with different values [...] I'll have to digest that for a bit, but its interesting.

The thing is you cant use blinded transactions for fees, because you dont know who the miner will be and the recipient needs to see the revealed transaction.  That could be fixable, but also you cant tell the value of a blinded transaction (nor validate the value even if it were public in the format) unless you're a party to the transaction.  Otherwise I would have liked to say you can use blinded fees also.

and policy could still be imposed by simply only mining coins which you've seen completely unblinded. 

I think the solution is to change the protocol pre-emptively so only blind coins are valid, other than for reward.  Then if dishonest miners block all transactions, they are not participating in the network, they are just DoSing it for no reward, expending massive amounts of compute and forgone profit, just to jam all transactions by releasing a chain of no-transaction blocks (or dummy transactions to self).  If that were their aim they might just more cheaply and effectively DDoS nodes. 

Non-blind for reward only should be client enforceable eg require pay from address to same address with balance to fee. If clients reject and dont forward non-blind transactions which try to abuse fee for payment, the miner cant do anything other than DoS the network.  Note the miner can already do that to the current network (someone with money to burn, >50% of network and no concern for profit or loss relating to his hardware can do a lot of damage).

(Ideally we would have direct mineable shares, so that fees could be low enough you can mine them on your GPU without linking, and have them earn direct reward.  However that is a different topic.)

complicated scalability challenges there... and I don't really know that this helps: as you point out, a super-majority cabal can reject blocks. So I really do think thats totally orthogonal to policy behavior.

I just meant that a hypothetical direct-mined share (if we could somehow figure out how to make them scale) is a low value reward coin so it has no input and no taint by definition as it has no input and no history.  Its completely anonymous and so not subjectable to policy.  Also as fees are low in relation to payments, it should be cheap enough that you could mine it yourself on demand on GPU or maybe even CPU.

Adam

[iddo]

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right?

No because an attempt to pre-spend a committed transaction, via a normal transaction, can be validated against committed transactions.  That is because a normal transaction necessarily includes the address public key, for validation of the ECDSA signature on the transaction.  Then the network can see that the hash of the public key has already been spent via an earlier commitment and so the pre-spend attempt is rejected.

So if a maclicious attacker somehow managed to obtain some pubkey pk0 of Alice, he could compute H(pk0)=SHA1(SHA256(pk0)) and create a blind commitment txn H(pk0)H(junk) and lock Alice's coins forever, because as you said here the network will detect and respect the SHA1(SHA256(pk0)) hash when Alice reveals pk0 as she attempts to spend her coins. In terms of security this will be a total disaster, because the pubkeys are stored unencrypted in walllet.dat

[adam3us]

So if a maclicious attacker somehow managed to obtain some pubkey pk0 of Alice, he could compute H(pk0)=SHA1(SHA256(pk0)) and create a blind commitment txn H(pk0)H(junk) and lock Alice's coins forever, because as you said here the network will detect and respect the SHA1(SHA256(pk0)) hash when Alice reveals pk0 as she attempts to spend her coins. In terms of security this will be a total disaster, because the pubkeys are stored unencrypted in walllet.dat

Actually (public) commit to junk was an attack that I fixed with this modification:

(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 )

however that doesnt change the picture that you need to keep your public key secure for committed transactions, and use it once only also.  So either the client needs to encrypt them, or you could consider the public key alternative I mentioned:

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 that 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)

and there x is already protected in the wallet.  However gmaxwell has a valid point that one cannot assume ECDSA because the CHECKSIG script action is generalized, pluggable and upgradeable.  And analogs of that particular trick may not be available for other signature schemes.  I guess that rather means that this blind coin has to involve a new script operation that provides the semantics which can then be implemented in a given way, and potentially themselves be upgraded.

Adam

[iddo]

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right?

No because an attempt to pre-spend a committed transaction, via a normal transaction, can be validated against committed transactions.  That is because a normal transaction necessarily includes the address public key, for validation of the ECDSA signature on the transaction.  Then the network can see that the hash of the public key has already been spent via an earlier commitment and so the pre-spend attempt is rejected.

So if a maclicious attacker somehow managed to obtain some pubkey pk0 of Alice, he could compute H(pk0)=SHA1(SHA256(pk0)) and create a blind commitment txn H(pk0)H(junk) and lock Alice's coins forever, because as you said here the network will detect and respect the SHA1(SHA256(pk0)) hash when Alice reveals pk0 as she attempts to spend her coins. In terms of security this will be a total disaster, because the pubkeys are stored unencrypted in walllet.dat

Actually (public) commit to junk was an attack that I fixed with this modification:

(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 )

I don't see how you fixed anything in the context that I described. You said here that the network won't allow Alice to double-spend because when Alice tries to double-spend she exposes her pubkey and then the network will detect and respect the earlier H(pubkey)H(txn) blind commitment transaction. So what's the difference between an attacker who knows the pubkey and creates H(pubkey)H(whatever), and Alice who creates the legitimate H(pubkey)H(txn) ? If when just the pubkey is exposed the network could somehow detect the difference between Alice's H(pubkey)H(txn) and the attacker's H(pubkey)H(whatever), then this isn't blind, in the sense that the pubkey is enough to un-blind it, which shouldn't be the case.

As far as I can see, if Alice wishes to buy a product from Bob in exchange for her tainted coins, then either the coins will be worthless to Bob because the network will reject Bob's attempts to decommit and spend those coins, or Alice can double-spend her (non-tainted) coins after receiving the product from Bob, or the network will prevent Alice from spending her tainted coins in the first place. If I'm wrong, please elaborate with exact details of your protocol on how the exchange of tainted coins for the product would work?

[adam3us]

You said here that the network won't allow Alice to double-spend because when Alice tries to double-spend she exposes her pubkey and then the network will detect and respect the earlier H(pubkey)H(txn) blind commitment transaction.

correct.

So what's the difference between an attacker who knows the pubkey and creates H(pubkey)H(whatever), and Alice who creates the legitimate H(pubkey)H(txn) ?

The attacker doesnt know Alice's pubkey - Alice and Bob keep it secret until the transaction is committed.  Alice & Bob should store it securely (eg encrypt it in their wallets).

As far as I can see, if Alice wishes to buy a product from Bob in exchange for her tainted coins, then either the coins will be worthless to Bob because the network will reject Bob's attempts to decommit and spend those coins

The point is the coins are already spent by the time of the decommit, because Bob can opt to spend them in committed form, and they are confirmed (eg left for 6-blocks of confirmation before decommitting).

or Alice can double-spend her (non-tainted) coins after receiving the product from Bob, or the network will prevent Alice from spending her tainted coins in the first place.

Note the coin address of the recipient is all that is seen before the commit by the network.  The coin address is

addr = RIPEMD-160( SHA-256( pub key )

that does not allow the network to calculate the committed value which is commit = SHA1( SHA-256( pub key ) ) because you cant do that without inverting the hash, which is hard to do.
Therefore the network (and anyone) can not correlate txout coin addresses with committed spends until the reveal (or a double spend).

However on a normal transaction spending from the address, the spenders actual pub key is revealed in order for the ECDSA signature to be verified as part of the existing bitcoin transaction format.  Because of that at that point, the committment (of txin pub key) can be reproduced by the network, and validated against both double spending, and committed double spending.


So as I said Bob could spend in committed form and so could Carol, Dave etc indefinitely. 

However if Bob decommits and a dishonest miner does not include the decommit, by doing that he has still not revealed his public key (only his coin address).  Consequently he can react to the dishonest miner and still spend his coin in committed form.  However he should probably wait until the decommit is accepted and confirmed in the block chain by some number of blocks (eg 6) until spending because by spending he reveals his public key, and loses the ability to spend in committed form because as soon as his public key is known to the dishonest miner, the miner can recognize the committed form payment.

Part of Bobs reason to commit is to compact his coin.  I suggested another variant on the bitcoin dev list in response to other comments which keeps the committed coin at 64 bytes, however many times it is respent in committed form.  In this way it is simpler for Bob and everyone else to just keep respending the coin in committed form indefinitely.  There maybe SPV costs associated with that however .

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.

Adam