Topic: blind symmetric commitment for stronger byzantine voting resilience - page 3. (Read 12256 times)

So I take it that you now agree with what I wrote in post #17 here, and that your auth=HMAC-SHA256-128(K,tx-commit) isn't relevant here and therefore doesn't fix anything in this context. This means that any malicious attacker who obtained any of Alice's pubkeys can broadcast H(pubkey)H(whatever) and instantly lock Alice's coins forever. We don't store the pubkeys encrypted in wallet.dat, otherwise the client would have to prompt for the AES passphrase all the time. So far it seems to me that this blind commitments scheme is totally impractical, in the sense that if we'd hardfork and roll out this scheme then huge amounts of coins will get destroyed in rapid rates by malicious attackers, or even greedy attackers who wish to deflate the total money supply.

I claim that there's an inherent contradiction between blind commitments which prevent the majority of the hashpower from imposing their policies, and protection from double-spendings. If Alice sends her coins to Bob in a blind fashion, then either the hashpower majority can impose their policies on Bob because he must decommit before sending his merchandise to Alice, or Alice can double-spend and defraud Bob.

correct.

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


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


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 .


Adam

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?

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


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:


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

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

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.


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


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

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.

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


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.


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.


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?

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.

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.

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.

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

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.


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

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

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?

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


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

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.

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

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.

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


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.


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.


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