I am not sure the ASICs actually have any protocol choice power.  If bitcoin main developer branch for some reason decided to phase in a new mining algorithm, the choice is actually the users.  If the users agree, they will keep on the main branch and accept the algorithm phase in.  If they dont someone forks the code, and the users migrate over to a new fork.

If there was a code fork like that where both forks accepted the existing coins created up to the fork date as valid, that might be kind of strange sort of like an alt-coin that accepts bticoins up to a hard-fork point in time.

Adam

Btw I made a summary of the zerocoin paper here.  

http://www.mail-archive.com/cryptography@randombit.net/msg04117.html

Not sure it helps understand it or not, but there you go.

About ZKP of set-membership the first thing to understand is the RSA accumulator of Benaloh.  

http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf

Its like a commutative hash function but using RSA.  With discrete log (or EC discrete log) if i give you A = xG (G is base point x some random number) I can prove I know the discrete log by showing you x and G is fixed.  But if you are allowed to use any generator H then you can start with A divide it by some random number x and call the result H.  Now you can prove xH = A but that doesnt prove anything as anyone can do that if they can prove the discrete log to some random base its an x-th root not a discrete log, which is easy .  How you "divide" A by x is multiply by x^-1 mod n (n is the order of the curve a public known value for a EC parameter set).  And you can compute x^-1 mod n easily with euclidean algorithm (normal modular math, no EC).

However the analogous division is not possible with RSA, in RSA computing x-th roots is also hard (as well as discrete log).  eg If I give you A you cant compute A^(x^-1) because x^-1 has to be mod phi(n) = (p-1)*(q-1), and in the case of RSA phi(n) is secret and in the case of an accumulator p, q, phi(n) are supposed to be deleted after setup so no-one knows them.  So if I can show you H and x and H^x = A that proves you I had an influence in producing A.  

each step is done by the user after receiving the previous accum set.  Users can go in any order as exponentiation is commutative.

G and n is published, p, q deleted
step0: accum set = {G}
user1: private x1, accum set = {G,A"=G^x1}
user2: private x2, accum set = {G^x2,G^x1,A'=G^x1^x2}
user3: private x3, accum set = {G^x2^x3,G^x1^x3,G^x1^x2,A=G^x1^x1^x3}

The accum set is broadcast by each user and each user raises every element except the last to his private exponent xi, and appends the last element raised to his private exponent xi.

You notice that the base of each user is missing the exponent of his respective xi, user1 base is missing x1 (first item in set), user 2 is missing x2 (second item in set), user 3 is missing x3 (third item in set).  Consequently a user can raise his private base call it Bi for user i, to power xi and get A the global accumulator Bi^xi = A.  Because discrete log and x-th roots are hard in RSA he cant do that unless he was involved in this process.

That involves a lot of sending of sets.  If alternatively each user broadcasts his xi, everyone can compute his own Bi and the final A, however now anyone can compute any Bi and all xi are public.  Its a lot more communication efficient however.  To combat the fact that xi are public, xi has to be chosen eg as xi = H( yi ) where yi is secret.  Then a user can prove that by revealing yi and having the verifier check xi = H( yi ) and Bi^xi = A.

Or as its hard to efficiently make ZKP about (symmetric) one way hash functions a discrete log "hash" function could be used eg xi = H^yi.  Now the user could prove knowledge of yi without revealing yi (via a Schnorr signature see below).

So lots of people compute and pass those messages around then they can prove simply that their zerocoin is in the set until there is a final A that includes contributions from all users who produced zerocoins in this time period.  And each user knows a Bi such that Bi^xi = A for the single A value so they can prove membership.  The order is commutative so it doesnt matter which comes first.  A is small - just 2048 bits = 256bytes no matter how any serial numbers are provable against it.  Bi is also small 256bytes as well as is xi.  And the user need only store Bi and xi because he can compute A from it.

So that provides a proof that you had an influence on an accumulator (some non-secret value of yours was included "hashed" into an accumulator).  Its rather like a merkle tree except that you dont need to provide log n path in the three to prove, just prove you know Bi^xi = A.

So far thats not private as all Bi values are recognizable to anyone who saw them.  However using an extended blind schnorr signature like proof where you can prove you must know such an xi and Bi without actually revealing them.  Its ZKP because the verifier could even create a fake if he choose the challenge himself so therefore you can argue he couldnt learn anything about Bi nor xi from something he could've created yourself.  

A schnorr proof of knowledge to get an idea how you could prove something similar is related to a DSA signature and relatively simple eg here.  http://en.wikipedia.org/wiki/Schnorr_signature and its the same concept as DSA, ECDSA etc - ie you can prove you know the discrete log of something, without actually revealing the discrete log!

A schnorr proof only hides xi, the zerocoin enhanced proof also hides Bi but the basic idea is the same.

The efficiency problem in zerocoin is that each run of the ZKP has a 1/2 chance of being unconvincing.  So you have to run it like 128-times to get probability 1/2^128 kinds of cryptographic assurance.  This repetition is called cut-and-choose.  Fortunately it can be made non interactive (by fixing the challenges based on a one-way hash of the parameters), but thats still 128 x 2048-bit RSA things which is like 10s of kB.  Probably they are doing a bit less than 128 cut-and-choose rounds because they say that proof size is 45kB for 2048-bit and I presume a proof includes at least 2x 2048-bit values.  Actually I see they say 80x, so that comes out to 2.2 so maybe there is some auxilliary info, eg the serial number?

To prevent double spending they just keep a public list of spent zerocoin serial numbers, and you cant influence the serial number after the fact.

So I guess the other thing you can do if that is unnecessarily complicated is just say ok there's a ZKP of set membership which proves your coin is one of that set, but not which one and trust that people have figured out how to make that work.

btw Benaloh's accumulator paper is quite readable

[edit: fix error about xi vs Bi and give a small example]
[edit2: more communication efficient public xi = H^yi, secret yi or xi = H( yi ) version]

Adam

One issue I was noticing with committed coins is you cant send to someone who is offline as you need to direct-send them the decommittment.

Here's  a way to fix that while retaining compact addresses.  The address public key becomes no longer secret and not used for direct receiving, rather for self-signing further sub-keys only.  Then an encryption (public) sub-key can be signed with the address public key.  And a separate receive sub-address = H( receive-pub-key ) relating to corresponding (unpublished) receiv sub-pub-key. 
The self-signed set of sub-keys is broadcast and available for download from all peers, keyed by address (hash of public key). 

(This is quite analogous to looking up someone's PGP/GPG key based on fingerprint, where a PGP key includes a top-level DSA key and then one or more sub-keys for Elgamal etc.)

So in that way you still keep the compact address, and the sender can lookup:

pub-key, sig( enc-pub-key, receive-addr )

keyed by addr = H( pub-key )

Then blind committed transactions become:

receive-addr, PKE( enc-pub-key, sender-receive-pub-key ),
H( sender-receive-pub-key), E( sender-receive-pub-key, transaction )

PKE is public key encrypt, E is authenticated symmetric cipher mode.

probably could be optimized in some ways, but a proof of concept.  The
recipient is identified, which is a loss, but optionally can be fixed with
stego, at some cost; and recipient can and is encouraged to create new
recipient addresses is another defense.


Probably you could reuse the sig pub key as an encryption pub key, but as a
design principle that adds risk.

Both committed and non-committed transactions would have to use the receive-addr.

The mechanism of self-signed sub-keys could allow self-certified identity (eg put your email address as one of the attributes), and could allow you to change your receive-address, or update a set of receive addresses gradually without changing your identity and base address.

Adam

It seems at that point that all the block chain and miners are doing is helping users order transactions that it doesnt know much about.


Well thats true, however anyone can be a miner, so all full clients need the fee information, and the fee is used in the broadcast to prevent flooding/spamming, so probably the information that is broadcast needs to carry its own fee information.  It would not however have to go into the block, that is just to prevent spamming.

It does seem to be true that not much needs to go into the block (eg just the blind commitment in a merkle tree) and when you're validating information about a specific payment it is just a few small pieces of info that you need, not a whole block worth of validatable information.  For commitments it seems that its better not to require reveals go in the block as then there is no conflict with miners trying to exclude them.

Adam

Yes, I think censoring transaction reveals matters less because the transaction has actually already completed in blind form, and can continue to be spent in blind form.


If the dishonest miners have a lot more power than honest miners so that they could forcibly make any acceptance of honest reveals into orphans yes.  Though payments can continue.

Also I notice that there is no actual need for mining of reveals, they were already mined in blind form.  They can simply be made available p2p for download by user clients.  They can easily be verified as correct with out need for high hashing power confirmations, the only validation needed is that they hash to a previous blind commit in the block chain.


I think the wallet storage for a blind transaction even after a long chain is simply the set of public keys for the addresses in the last hop unspent output set.  That is because you can validate a blind coin by iterating backwards if you have the last hop public keys, you can decrypt the commitment.  Then you see the public key of the previous hop, so you fetch the previous committed transaction, decrypt it and get keys for next hop etc until you reach a mined coin or a non-blind transaction.  So the wallet itself doesnt really grow. 

The validation procedure becomes longer and eventually the privacy eroded if many users are party to it (each user only has visibility of the transactions before, not after; but a user being the last hop in a long chain sees a lot of history).  No worse than now, just not helping privacy that much long term.


I think the answer maybe above, to not require reveals to be hashed a second time into the block. 
Just have peers make them available for download, there is no DoS as they can be validated back to their hash which is already cemented into the block chain in blind form.  If no mining is required on reveals, then there is no need to trust miners to process them.  And users can reveal at their convenience without the need for cooperation from miners.


Its hard to allocate blame.  The dishonest miner may say it is the revealer that dropped the connection part way through and so falsely claim he never received it.

Adam

I tried to retain the existing bitcoin semantic that first spend is valid, later double-spends are invalid and rejected (whether the spend is blind or non-blind).

I think what you said was that it could be possible to have unblind transactions take priority over blind transactions.  You could define it that way but it might create problems I think.  Eg say you accept  a blind transaction after one confirmation then you pay it to someone else.  But the second block has a double-spend with a non-blind transaction in it.  Now according to the one block confirmation view the blind transaction is valid, but according to the two block confirmation view the non-blind transaction is valid (and the blind one invalid).  What if you try to spend it with someone who expects two block confirmations, and goes and looks and sees that according to that definition the blind coin should be rejected?

Its somewhat but not quite analogous with the confirmations required in bitcoin now, because those can only be undone by orphans which are expected to be increasingly rare (longer orphan chain is increasingly less likely) or require a lot of resources by a dishonest entity to create.

Conversely revealing a non-blind transaction has no cost and can be done at any time for no cost by the original owner.  Maybe it has no effect if it happens after a given number of confirmations.  eg if everyone agreed that six confirmations were always required, then it could work, as the recipient can just check that there are no overriding non-blind transactions during the six blocks that came after the blind transaction.  So I think the problem is if people have differing preferences for how many blocks of confirmation they require (of no double-spend event happening) then one type of transaction (non-blind) overriding another type of transaction (blind) becomes a problem.

Adam

Well I am saying the dishonest miners must not be able to guess with good confidence that the transaction involves tainted coins or other information like who is paying or receiving, or they can reject them even though they are blinded, ie if that happens the blinding was ineffective.

About necessity of using addresses & public keys: one clear requirement is that double spending must be prevented, and the way that works is that if you double spend a non-blind version of an unspent output then a signature is provided to prove ownership of the output.  And a signature always includes the public key to allow the signature to be verified.  The public key was previously unknown (before spending) and so could serve as a blinding factor

So the main trick is that if the public key is used as the only non-public blinding factor, then double spending in non-blind form will unblind and expose double spend attempts.

We cant use eg the recipients address in as the blinding-factor because we want one recipient to be able to tell that the sender tried to double spend an output with another recipient.  If the recipient doesnt know the other recipients address, he would be unable to detect double-spending.

So the commitment looks like

(com1,com2) = SHA1( SHA256( pub ) ), AES-CCM( key, transaction )

where key = SHA256( pub ).

There has to be separate blinding per unspent output used because the UTXOs could be double-spent separately.  So a blind transaction could include a list of blind commitments and a plaintext fee to pay for the processing of the blind transaction.  The fee should be extremely taint free.  The fee may optionally be paid by the recipient.

Adam

If the destination address is re-used that might be guessable, but people are discouraged from re-using addresses. 

I am not sure about scripts - I suppose scripts contain addresses or they become insecure also so the same applies?

Adam

Well they could iterate over UTXOs and amounts looking for a permutation and amount that results in that hash.  It might take a bit of computation but if you're talking about attacks you have to consider eg 2^50 operations and such things  the miner has a lot of CPU power as it is.

If there are one-use addresses in the commitment that becomes basically impossible.

Adam

If there are legitimate situations where scripts do not contain an address (that is disclosed by the corresponding signature during a spend) it maybe difficult to blind those scenarios.


Well if there is no non-public info (like the public key is not public even though the address which is the hash of it is public) then people can guess which transaction is hashed to form the commitment, and then they will not be effectively blind.  We want the transactions to be blind so that dishonest miners can not make taint or sender/recipient based policy decisions. 

The other key part is that the public key becomes public unavoidably as part of a non-blind spend.  Those two features are necessary seemingly to make blind commitments work and yet prevent double spending.

Adam

I think it maybe that it should more accurately commit an unspent transaction output and the address in control of it.  How would you identify or serialize that?

(I am taking it that balance is not on the address as such, but that each not yet spent transaction output is owned by an address, and can be spent in its entirety in a transaction?)

I think for privacy bitcoin discourages address reuse so it maybe that the difference is not much.  eg hash of transaction identifier, output number and public key (that is the basis for the address).  It is only the public key that is not already public, and something non-public has to go into the commitment.

Adam

I think one could make a mining function which was fairly hard to gain an advantage with using ASICs.  But I do think you have to target GPUs because a GPU is basically a better CPU.  The CPU has a lot of resources dedicated to optimizing the single thread execution speed (eg super scalarity, out-of-order execution etc).  Alternatively GPUs dont have that.  A 7970 has basically a 2048 RISC cores.  So I think you want to optimize for the characteristics of the GPU.  Memory line size, cache architecture, instruction set.  Make all of those things work hard, and dynamically, but in proportion to the resources the GPU has.  eg some integer instructions, some FP instructions, some memory.

Then a would be ASIC miner has to make a better GPU.  AMD is putting quite a lot of resources into that.

Also I think we could have automatically balanced algorithm mining, including mining parameters.  So the idea is anyone can introduce a new algorithm or new set of algorithm parameters.  Presumably with some public review process so that there is no trapdoor known only to the introducer.  Then each algorithm has a floating separate difficulty set by the network.  The difficulty inflation is set so that the algorithm which appears last susceptible empirically to inflation is he inflation target.  Other algorithms have their difficulty adjusted so that their inflation matches the minimum inflation algorithm.  So eg if SHA256 hashcash mining has a big batch of new fast ASICs come online, to the extent that difficulty gets much harder quickly, the difficulty is increased faster yet so that the proportion of coins producible with SHA256 mining falls and the other mining functions rise.

Adam

It was made by Dan Kaminsky in the comments section of his wired article.  See this thread:

https://bitcointalk.org/index.php?topic=194554.msg2078882#msg2078882


My view they cant do that.  If the client accepts only blind coins, or has a switch in it that can be toggled to only do so, then the dishonest miner either has to follow the protocol and mine blind coins, or leave and form their own alt-coin without blind coins (or join an existing alt-coin without blind coins).  It might be lonely and unprofitable on that network however if there are no users who want their coins subjected to dishonest miner policy

Lots of hash power doesnt mean an alt-coin becomes popular nor profitable to mine after all.  Popularity comes from the users, and profitability from the interest of users to buy the coins.

You can consider a network with miners that reject coins based on centrally applied policy as like a file sharing network that wont let you share files that have given hashes as enforced by a few big players for whatever reason.  Presumably people wont like that and will stick to the less restricted network.

Adam

I dont know the bitcoin script language well enough to have a good answer for that.  Someone on the dev list did comment on that aspect:


also:


I guess the next step unless iddo finds a flaw is to write up a BIP and get help with the simplest way to integrate from people who understand the script language well.  (And learn the script language myself!)  Well maybe a short white paper describing the detail wouldnt hurt before that even as so far the detail is spread out over a few posts on this thread.

Adam

Going back to the commit definition (symmetric version, with defense against insider commit to junk):


The point of the use of K = SHA-256( pub ) is that anyone in possession of the public key can decrypt, and verify the mac.  That means direct spend-to-junk is not possible by someone without knowledge of pub.  Now of course anyone with knowledge of pub could superficially spend to junk, however as pub allows decrypt and mac check, superficial junk is fast to detect and remove, just by validating the mac.  And a more subtle spend to junk (by someone knowing pub) cant work as the coin is ignored as junk unless the MAC passes, and unless the decrypted tx contains a valid signature from pub.


yes Bob accepts the blind commitment payment after waiting however many confirmations he requires.   He does have the decommitted value Alice sent him directly (without broadcasting) so he can validate.


if Alice double spends non-blind she definitionally reveals her public key, and so allows anyone to correlate with any blind commitments with the same key, and validate them, and so presuming the blind commitments are not all fakes, the secondary txn is rejected unless there are remaining sufficient funds on the address to fulfill it also.

Alternatively if Alice tried to double spend in blind committed form, the committed sender address would be the same and the recipient who needs to validate would receive the decomitted value over a private channel, and be able to validate the committed transactions.  (Validation includes discarding junk commitments).


No reversing.  See above the secondary (double-spent non-blind) txn is rejected.  So decommiting the first (committed) transaction just optionally exposes more details about the committed transaction.

Overall the picture with blind and non-blind transactions however you mix them and whichever comes first and how much money is left on the input address after processing, is just like standard transactions.  First is accepted, later are rejected as double spends.  Despite the blinding you can still tell because two blind committed transactions with the same input address are hashed deterministically so SHA1( SHA256( pub ) ) is the same in both cases.  If you send a non-blind transaction that is also correlatable to blind addresses because the public key is revealed as part of the signature.


OK this is a second issue - an insider who knows pub, was an issue with the straight hash-based commitment of the transaction.  This is why I said in a later mail (as quoted at the top of this message) encrypting and use of a MAC is more robust, and safely allows multiple use addresses, because it defends against that issue.

As you indicate preventing other users sending multiple times to the same address is problematic.


so lets say Alice is malicious, Eve is malicious but doesnt know pub, Mallory is malicious and does know pub (eg because she gave the committed coin to Alice) but Bob wants to send Alice her goods after 1 confirmation anyway provided there is no double spending within that time-period.

Com( pub, tx-commit ) = (blind-sender, auth, encrypted-tx-commit)

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

(A: indicates A broadcasts, A->B: indicates A sends to B private channel)

Alice: Com( A, "A spends 1BTC to B" )
Alice -> Bob: pub
Alice: Com( A, "A spends 1BTC to A" )
Eve: blind-sender, auth, junk    [blind-sender & auth copied from Alice commit]
Mallory: Com( A, "A spends 1BTC to M" )
Eve -> Bob     [cant send pub as doesnt know it]
Mallory -> Bob: pub

Bob can validate Alice's first spend as he has the pub.

Bob can also validate Alice's attempted double spend to herself.  However so long as the confirmation rejects the second one, it doesnt matter.  Normal bitcoin double spend semantics: first spend to reach the winning miner is valid.

now Bob can see that Eve's message is junk because the junk doesnt match the auth tag.

Bob cant tell as easily with Mallory's message as she has pub and so K; but still the tx-commit
decrypted from Mallory's message has no valid signature, as Mallory can not forge signature with Alice's key.

Bob waits 1 confirmation, and as the double spend from Alice to herself was not hashed by the winning miner, and the two fake commits from Eve and Mallory are the only other transactions relating to Alice's input, he accepts and sends the goods.

Bob nor Alice have to reveal.  They may opt to decommit after the transaction is long confirmed.

Bob can pay Carol who can pay Dave etc all without necessarily decommitting.

Each person in the chain of committed spends must see all transaction details earlier in the chain to verify its validity.  They learn this conveniently because they see the public key of the tx-commit, and from that can see the public key of the sender.  That in turn allows them to lookup the SHA1( SHA256( pub ) ) of the sender, and from that transaction learn the pub key of the previous sender and so on until they see a non-committed transaction, or a mined coin.

Adam

I dont think you need to prevent reuse.  It just means you have to allow duplicates (same committed send address).  And the recipient has to get reveals for all of the associated spends to validate.

If you wanted to it should be enough to have clients reject any other than the first on validation, and senders randomize it for you.


The recipient of the de-committed tx will have to go look at all of the matching inputs.  I think the recipients client needs to store and index by committed pub key all of the payments to him.  He can do that as they arrive (doesnt need to do it afterwards) looking backwards.  So he has like a pool of not yet decomitted received transactions.  Ones that he has processed he can probably combine into his UTXO if I get that concept.

Adam

That does make sense I see.  I get that you understand this but to note the committed value is the senders public key not the recipients.  [ Com( sender-pub ), Com( transaction ) ].  So the sender necessarily has to have access to his private key, and anyway at that point the sender-pub is fixed because it was a former recipient address.

The issue between committed coins and type-2 address generation you mention is with the recipient address generation.  Arent there already a pool of pre-generated addresses in the client design?  Or maybe the point is you dont need that with type-2.  You do need to store the random value r from P' = rP = rxG.  However so far with normal coins it is not security sensitive.  With committed coins it becomes semi-important (leak pub key, someone can link your committed coins).  However you can solve that with public key encryption of the r values.  ie generate random r, compute addr = RIPEMD160( SHA256( P' = rP ) ); store PKENC( pub, r ), delete r, P'.  PKENC some public key encryption.  You need to be be able to efficiently associate it with the address.  If there is an aspect of deterministically derive rather than encrypt (eg so no wallet backups need to be made or for brain wallets) then just generate r using that scheme and do not store it.  (You will need your seed then, or maybe you can store the head of a hash chain, and replace seed_{i+1} = H( seed_i ) and use r = seed_i.)


No because Bob can distinguish fake from real as for Bob to accept the transaction he will expect to receive the decommitted transaction.  Note to protect against fake commits needs the variant with a MAC of something eg the tx commit (so you can prove the fake is a fake, and not a double spend you refuse to disclose the pre-image of - you cant prove a negative ie that you dont know a pre-image).

Adam

Yes I said that myself also in the post you're referring to:


(It was an aside more about the size of committed payments).


I dont think it creates  backwards compatibility issue.  If the client is changed to store the public key in the encrypted section as if it were part of the private key, but  the coin address would be stored still in the public section, that would fix the problem in a backwards compatible way, because receiving coins only uses the coin address, not the public key.  Old keys (prior to a client upgrade) that had already had their public keys somewhat exposed by storage on the un-encrypted part of the wallet would need to be marked as not suitable for committed transactions (unless the user is convinced he never spent with the public keys, which the network or his tx log can tell him, and that his backups and machine are secure enough for his purposes without the encryption.)  The only threat from the old keys not being secret is unavailability of the policy defense of committed transactions for the affected coins, and that is the status quo without the fix dishonest miner power centralization fix provided by committed transactions.  If the user is unsure he can try a committed spend.  If it doesnt work as the miner is blocking it, he already had a problem because the miner would've blocked his uncommitted transaction.  He can still try again uncommitted but clearly that is also likely to be blocked.  His only remaining bet is to wait until another miner wins the lottery, includes his payment, and hope the dishonest but >50% miner isnt motivated enough to try to orphan the transaction; he might like to spend the coins in many small parts just to make life difficult for the dishonest miner (so he has to waste power creating many orphans). 

I think that might be fixable, but I am not sure it is worth the effort because the verify is slightly slower and if people dont like the problem, they should implement and deploy the solution, not focus on the boundary condition for legacy coins.   It might be possible to create a second different type of commitment that anyone who has seen both the public key and at least one a signature from the public key can verify, but someone who has seen only the public key can not.  That would still be safe because the coin can not be spent without revealing a signature.  That would be a secret key commitment (after secret key certificates that Stefan Brands credentials are based on).  Let me have a play with that it sounds interesting.  I am not sure yet if you can do it deterministically (ie so the recipient doesnt have to scan all secret key commitments is the issue.)  One problem is DSA sigs needlessly complicated Schnorr's base protocol, NIST/NSA did it to avoid paying Schnorr for his patent.  In most ways Schnorr signatures are superior and more flexible than DSA, eg it is easy to make threshold and split key where that gets quite complicated with DSA.  (The Schnorr patent expired in 2008.)

Anyway thats the problem committed transactions are trying to fix, that it doesnt work with as much assurance before people upgraded cant really be blamed on the protocol.

Also the committed coin cant be locked by someone malicious who knows the public key, because the fake committer doesnt know the private key so the transaction will be bogus.  The real owner of the private key can unlock the fake committed transactions to a committed payment receiver or to the list via decomitting, by posting his public key in a normal signature, which will immediately show there is no committed double spend as the only committed transactions are unsigned fakes.


See above, I think all attackers are powerless.  If you see a flaw I'll be interested to discuss it.

Adam

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

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