It was described how that works somewhere in this thread.  The short version is that the commitment contains SHA1(SHA256(public-key)) and a normal address is a different hash addr=RIPEMD160(SHA256(public-key)) and any public (non-committed) transaction reveals the public key (because that is necessary to validate signatures, and transactions contain a signature from the address public key), then if a public spend is done anyone can calculate the commitment based on the public key.

If another committed transaction is made RIPEMD160(SHA256(public-key)) is reused.

The actual details are a bit more complicated to prevent various attacks and corner cases but the above explains why you could prevent double spending of something you cant even correlate unless it is double-spent.

Adam

The limitation I see with Chaum credentials, for off-chain transactions backed by bitcoin is that the transaction server could issue more chaum-coins than there are bitcoins, and you will never know until you find your chaum-coin is irredeemable because the bank is out of bitcoins, having redeemed them itself under a pseudonym with extra unadvertised chaum-coins it minted for the purpose.  Because they are not linkable you cant make a chaum-coin lock an on-chain bitcoin nor collectively all issued chaum-coins also cant lock a claim to the pool of on-chain backing bitcoins.  (Or more likely the bank gets away with it for a while, like an over-leveraged fiat bank with off-book liabilities until there is a run on the bank).

(And I guess its been tried, monetas OpenTransactions system implements David Wagner's blind MAC (in the form of Ben Laurie's lucre library) something similar to Chaum and I think is flexible enough to issue Chaum-alike credentials for bitcoin).

Thats because while the Chaum bank can demonstrate it is holding some bitcoins, the coins are blind and not linkable.  So you cant tell when an extra coin is used (that was not backed by bitcoin) to claim a not yet spent bitcoin, rightly belonging collectively to the set of bitcoin backed chaum-coins.


That could be interesting, but the chaum-blinding doesnt directly work as the way bitcoin consensus is to put it inside a merkle hash inside a massive hashcash stamp.  Maybe you could put it inside an RSA accumulator instead, which is a more blinding friendly algebraic construct.  However that is basically what ZeroCoin is trying to optimize.

Adam

So apart from the political blather this bit seems to be like a potentially interesting idea, perhaps other people had the same idea before


ie why not as a design objective try to separate identity from coins.  So you make the coins payee and payer anonymous, and then each user has a wallet identity/pseudonym that maybe optionally disclosed to the other party, or revealed to other party or to the auditor in event of dispute.  In that way we avoid taint, and yet the privacy and anonymity of the payment system becomes more arbitrarily tunable and even negotiable between parties, or set by system default.  Taint and tracability of taint is bad because it affects fungibility (in a p2p respendable ecash system like bitcoin, random users end up holding retroactively tainted and reduced value or unspendable coins through no fault of their own, and this erodes confidence).  But a system may like to offer or aim for a specific privacy level or traceability of amounts and identities.  Those things thereby become separable.  Nice

Now all we have to do is find a way to make zerocoin efficient.  (And that seems to be the question of the hour - its not at all obvious how to do that).

Actually its an open question how far bitcoin direct chain transactions scale, so maybe there is some hierarchy of off-chain (or sub-chain) that evolves eg around miners, exchanges, or p2p sub-chains that offer lower value coins, that backed by the main chain but not detail validated by it.  The supposition being that if bitcoin does hit a scalability limit (fails to scale as fast as its adoption), the minimum effective transaction value amount that is economical to send due to fees will go up, a lot.  Maybe the main chain is used for inter-chain clearing and investment level bitcoin holdings.

So maybe the privacy policy types of things get decided by competing sub-chains and off-chain transactions in such a bitcoin world.  And seemingly its not obvious how to do sub-chains and off-chain transactions without trust for double-spend protection.  (Which is why things like fidelity bonds come up in this scenario).

Adam

You can get privacy without anonymity, eg as with the committed coins idea https://bitcointalk.org/index.php?topic=206303.0, only the sender and the recipient get to see the coins and who is spending to who.  (Unfortunately the committed coin privacy is not ideal because later people in the transaction chain of committed-form respends necessarily have to learn all previous details for validation reasons).

Some of the privacy focused ecash systems distinguished between payer anonymity and payee anonymity.  As a buyer you dont necessarily want all your payments to allow the public, the (ecash) bank nor the merchant to track which say ebooks you are reading.  It none of their business.

However the usual argument to blackmail crime scenario is that the criminal cant do that if there is only conditional payee anonymity (ie the spender colluding with the ecash bank can identify who the receiver is).  In bitcoin there is no bank to collude with, but you could imagine arbitrators in that role, or that the payee is identified to the payer (but no one else).  And of course the identify the recipient ignores identity theft, and assumes criminals are mindless non-adaptive automatons so its a fairly weak argument IMO.  In any system that strips privacy, the people who suffer loss of dignity and privacy invasion are the normal users, the criminals can still get privacy via identity theft, fake identities, buying fake identities from corrupt employees of government id issuers etc.  And criminals still launder money en-masse even with regular banks.   HSBC which reportedly laundered $880m of significantly dirty mexican drug cartel and even terrorist money and faces a $1.9b fine.  http://www.guardian.co.uk/business/2013/may/23/hsbc-court-threat-money-laundering-charges  Probably HSBC are going to walk away with the fine only (too big to jail despite the posturing).

Another possibility is it would be technically possible for the spender to be convinced who the recipient is without being able to prove it to other people eg with a ring signature, non-transferable signature, or designated verifier signature (the spender being the designated verifier).

Being able to sell things anonymously is a different and actually separable feature.  But people have also made pretty convincing arguments about why individuals should have the right to retain privacy while selling physical or virtual goods in a free society.

But I do think bitcoin ideally needs to find an efficient way to fix the fungibility problems with taint.  Payer privacy without payee privacy might not fully fix that as a payer who claims he didnt make the payment (claims the thief made the payment using the victims wallet to the thief) the victim would then identify the recipient.  If there were identities separate from coin addresses, you could imagine payee/recipient losing privacy on payer complaint, without the payee losing ability to make further payments with payment privacy.  ie the payee is expected to repay the value, not that the coins themselves become traceable.  However even then when identity is some random public key with no certification, its really not much of a threat to burn an identity.  Fidelity bonds perhaps are closer to network identities with some cost to losing.

Even in the physical world with conventional banks, once non-petty criminals are involved "identifying the perpetrator" becomes a fuzzy and useless fig-leaf fast as they identify a victim, or a fake identity bought from a corrupt government employee, or dupe the issuer - the RA stage is usually inherently pretty weak.  Criminals rent identities (money mule), buy or create fake identities, shell companies etc.

Finally to note a payment system could obviously have emergency tracability added to it as noted in the zerocoin paper.  Its typically easy technically to selectively weaken a protocol.  The problem is if you want it at all, you want emergency tracabiliy to be restricted to genuine emergencies, not drag-net fishing, not tracing of petty crimes.  Law enforcement are not always so clever about drawing lines there so you get mission creep until jay walking is an emergency.  eg in the UK I read a local council abused crime surveillance cameras to trace people who were bending the rules about which area they lived in to get their kids into a better school!  Next up people not pooper scooping their dog.  You know those things were weakly approved by society for terrorism clean up and maybe, arguably, serious organized crime.

Some ecash crypto papers have talked about system limits like payments are fully untraceable if they are under some amount (eg $10k like paper cash reporting limits) or under some amount per day per user.  Another limit can be the "emergency" access is limited to 1% of traffic period, more is not cryptographically possible.  Or I think alternatively and more simply access requires cooperation from involved users would be a nice balance.  Everyone has to transact with someone, and most transacting parties have no particular interest to protect some organized crime activity that rented a server or car from them.

Anyway the whole thing is a big mess.  And it's hard to maintain binary fungibility in the face of grey fuzzy privacy/traceability, and court ordered mission creep.  Computers do binary well so to me that is the natural physics of crypto and p2p virtual payments: irreverasable is cheaper than charge-backs (cash over credit cards), and there is no partially irrevocable.

Probably in an actual free society, people would understand that more people being killed by furniture falling on them than by terrorists should be sort of factored in in terms of spending and focus, and societal balance.  Obviously the people charged with cleaning up and infiltrating these things are too involved for perspective, but they work for society not the other way around.

The UK had its share of history with IRA blowing various stuff up, the US news typically in that era referred to the IRA as freedom fighters, some US factions even funded them, and yet the sky did not fall, eventually the UK lost their face of "we do not talk with terrorists", the IRA became involved  in the political process, some political prisoners were freed, and now things are not blowing up.  The UK government got up to some pretty shady things in the history of the troubles also.  Its just possible that the current problems have an element of blow-back and two sides to any argument also.  Its kind of interesting from inability to learn from history that the UK government finally admitted and will compensate victims of its past torture of kenyan resistance fighters and civilians including Obama's grandfather in kenya troubles, and here is Obama presiding over the next generation of the same picture (the powerful torturing the weak for attempting asymmetric and reactive warfare).  That still seems to me like a retrograde step, trials were heard at nuremberg about such activities in the past for good reason.

Adam

So what did the tweet say if you still have it.. enciphering minds need to know!  (and undetweetable.com says they've been asked to shutdown).

Adam

[edit used sup and sub for exponent and subscripts]
^ is power modulo some prime or RSA modulus depending on the situation and * is modular multiplication.

So the A=u^{c₁c₂...c_n} is modulo N an RSA modulus N=P*Q two primes P & Q.  A is the accumulator.   Note c₁c₂..c_k gets pretty big as users cant reduce it as they dont know phi(N) = (P-1)(Q-1) - no one does as its deleted after parameter generation.  u is some fairly chosen quadratic residue (square numbers mod N) ie there exists u' st u=u'² mod N.

This is the P & Q where you unfortunately get to trust someone to delete them.

Next for each coin c=g^sh^r mod p, where p is a fixed prime (not the same prime as P) actually a strong prime (where p = 2q+1, or even p=2^wq+1 for some integer w, to get a smaller q).  Because c=g^sh^r mod p c can be prime ie g^sh^r is clearly not prime by definition (it divides by g, h, g² etc) but g^sh^r mod p can be prime.  It quite a bit of work of trying random commitments to find a prime c though.  I tried coding it in openSSL and it wasnt that fast eg c=g^sh^r check if its prime, if not c'=c h mod p (so that c'=g^sh^r+1 mod p) and repeat.  Prime density is not so great at those sizes.

g and h are two generators in the shnorr group of size q.

So its curiously using two completely different groups - an RSA group for the accumulator and a Schnorr group for the pedersen commitment sounds odd but it doesnt really matter they are independent.

Now you can easily choose a c with two commitments in it (trying to get two zerocoins for the price of one bitcoin): prime c=g^s₁h^r₁ g^s₂h^r₂ mod p=g^s₁+s₂h^r₁+r₂ mod p.  

However to cheat and prove/spend two separate witnesses and zerocoins paid for with one bitcoin you need to prove you know A=w₁^c₁ mod N and also A=w₂^c₂ mod N with w1=u^{c₂c₃...c_n} mod N and w2=u^{c₁c₃...c_n} mod N.  However A=u^{c c₂c₃...c_n)} mod N because we paid for zerocoin c with our bitcoin.

So the only way to cheat is find c₁,c₂ such that c=c₁ c₂ or c=c₁c₂ mod phi(N).  You cant find c=c₁ c₂ because c is prime.  And you cant find c=c₁ c₂ mod phi(N) because you dont know phi(N) = (P-1)(Q-1) because P & Q are deleted during zercoin genesis.

If you could find such a c₁ and c₂ you would have found phi(N) by definition, and using that you can factor N trivially - ie thats impossible unless you can break RSA.  (You need phi(N) because you have to reduce the exponent by phi(N) with RSA ie A = u^c₁c₂ mod N = u^c₁c₂ mod N = u^{c₁c₂ mod phi(N))} mod N.

Now if you did know phi(N) = (P-1)(Q-1) you could clearly create multiple zerocoins for the price of one bitcoin.  So thats the trust in the person who sets up the value of N during zerocoin genesis.

Adam

The ZKP in zerocoin is able to prove you know a w and c such that A=w^c (where w=witness, c=commitment/coin and A is the global accumulator value at a given point in time) without revealing w and c.  c has the form c=g^s*h^r where s is the coin serial number (revealed) and r is a random number never revealed.  c=g^s*h^r is a pedersen commitment, you can think of it like a hash function c=H(s,r) in that its hard to find either s or r (because it one way).  Also its collision resistant so its hard to find another s,r value eg to find g^s*h^r==g^s'*h^r' even if you know what s and r are.  That like symmetric hash function also hard to find H(s,r)==H(s',r').  The difference is pedersen commitments involve algebraic operations on big numbers and the hardness of discrete logs and so are easier to prove things about (ie because you can usefully multiply them etc - hash functions like SHA256 just make a big mess of their inputs to achieve collision resistance.)

So putting that together zerocoin have a ZK signature of knowledge ZKSoK[tx]{(c,w,r):A==w^c and c==g^s*h^r} ie c,w,r are not revealed, tx is the transaction that is revealed and signed by the zerocoin spend/signature (eg tx = spend this zerocoin to this bitcoin address), s is revealed and stored and is the serial number that is recorded to avoid double-spending.  ie combining it shows that A==w^(g^s*h^r) and they were able to find a somewhat large way to prove that without revealing c,w,r.  Its large because it involves multiple cut-and-choose rounds as each round is only 50:50 convincing that what the prover claims is true.  After 80 rounds its security is 1/2^80 which is quite good.  (Though bitcoin aims for 2^128 which is more, they only used 80 to save space - 40kB was already unfortunately large for the zerocoin spend ZK "signature".

s is revealed and is the coin serial number, so its important that r is not revealed otherwise anyone could calculate c=g^s*h^r and just scan for that in the list of zerocoins de-anonymize the coin spends .  Fortunately because of the collision resistance of the pedersen commitment (hash function) not even the owner of the coin can create different s, r equal to the same c so he cant get two coins from one that way.  But to prevent the owner of the coin creating c=g^s'*h^r' * g^s * h^r and then proving two separate coins (and that would work because A = u^(c1*c2 *... cn) for all zerocoins ci) they further require that c be a prime number.  So you're not proving its prime via the ZKP when spending, but you are proving it when you create the zerocoin - all the miners check if c is prime (as c is revealed at that point).  So thats why c is prime.  (I had to ask Matthew Green that it was puzzling me as making c prime is moderately expensive, and why it takes 0.5 - 2 seconds to just create a zerocoin, and the Camenisch and Lysyanskaya paper the zerocoin accumulator comes from uses c prime only for  different reason that zero coin doesnt need - membership deletion).

It seems counter-intuitive that you can prove things without revealing them but thats what ECDSA does too - it proves that the signer knows the EC discrete log.  Its basically because you can see that only someone who knew the discrete log could have computed the signature, and yet anyone can see that the signature is valid.  The ZKP is the same just more complicated.

Adam

miners validate 3 things about other miners work:

a) that previous coins have the correct difficulty at the time of mining
b) that none of the transactions are double spends of previous transactions
c) that the input values are >= the output values (input > output means balance is fees)

with committed coins the last validation c) is delayed until the coin is decommitted (which could be 6 blocks later, or years later, after 0-follow-on transactions or 100s of follow-on transactions).  However the recipients receive the decommitment for all committed coins and so can validate it immediately for themselves in order to know whether they should accept.  Thats a bit more complicated for SPV clients, as they also need to see the committed coin decommitments which requires a bit more network activity and computation.

The other two validations a) and b) are still validatable by miners even though the coins are committed.

Adam

Its strange because as far as I can tell Ashish did not contribute to the hashcash library (and there were a few dozen people did).  Actually I had no idea who Ashish was other than the owner of hashcash.org (.com, .net) until reading this thread to realize he sounds like a pretty interesting open source crypto hacker and even involved with ecash related things at DMT which I was barely aware of though I had read some of the late J Orlin Grabbe's libertarian articles in the distant past.  I didnt realize he was an economist (see his wikipedia).

edit: Actually its not ambiguous the heading of the section on the above link is "As Seen On..." and includes sections for TV, news, magazines, and... code that mentions his name.  And hashcash certainly did that in the context of his giving the domain name, gratis.

Ashish did give me the domain - I think I offered $100 to have a better .org domain for the opensource project.  His counter-offer to give it to me free was a pleasant surprise.  He got me to make a PGP signed statement saying I wouldnt try to obtain hashcash.com nor hashcash.net.  I notice now hashcash.net is for sale by one of those resellers so maybe he accidentally didnt renew it.

The speculations about Ashish personality to be eschewing financial reward are interesting (re $100m of unclaimed BTC on the block chain).  I dont know Ashish so I cant help there.  But it is interesting that there are some cultures and religions that do intentionally forgo financial reward, and shy away from shows of wealth etc.  I noticed some indian sub-cultures have that, but they are certainly not alone.  Ashish apparently was/is involved in open source, and interesting projects like DMT where presumably most of the interest is the technology purist, or political freedom potential.

Adam

Taking a leaf from Meni Rosenfeld  https://bitcointalk.org/index.php?topic=121314 I figured I'd create a thread for people such as Serith (and he seems not alone) to dis me in. 

https://bitcointalk.org/index.php?topic=225463.msg2371674#msg2371674

Go for it


And now back to the ring signature sub-thread.  Ring signatures and accumulators are closely related with the convenient exception that ring signatures are directly anonymous (not requiring a ZKP of set membership like zerocoin and Sander & Ta-Shma's auditable electronic cash that predates zerocoin in its auditability.)

Most of the ring signatures are however also not compact (with signature size linear in the number of members of the ring).  With bitcoin thats the anonymity set size, analogous to the total number of zerocoins so in any real use thats probably worse than zerocoin.

This Shoup ring signature however has a small constant size:

http://www.shoup.net/papers/subring.pdf

(trying to decipher now) however it is based on an accumulator and sigma-proof (ZKP) not figured out how efficient that proof is yet to understand if its better or worse than zerocoins set membership proof, nor even if it could be directly used (membership proofs dont have to prevent multiple-uses, zerocoin does).

Adam

Taking a leaf from Meni Rosenfeld  https://bitcointalk.org/index.php?topic=121314 I figured I'd create a thread for people to dis me in.  Go for it

People seem to think I am trying to claim bitcoin is mostly hashcash with a small change (or it seems that that is what they assume I am saying, its hard to tell other than they find me annoying for some reason).  I'm not saying that.

A number of crypto people have asked me seriously over time if I was Satoshi, and I am not, and dont want to be mistaken to be because he has $100mil bitcoin shaped reasons to guard the physical security of his coins.  (And I dont even have coins which could be mistaken for really well hidden coins).

People also tell me I probably know Satoshi (ie that I know many of the applied & theoretical crypto privacy tech people and cypherpunks who worked on ecash technologies like digicash, brands ecash/credentials, lucre, wagner mac-based coins, b-money, rpow) though I am not so sure myself if Satoshi came from that background; my guesses are evolving based on the types of bitcoin crypto mistakes (the very few that there were).

So my tag line is actually serious.

Also while it is true that I invented hashcash (1997 hashcash.org), I am not claiming bitcoin is some simple extension, bitcoin has actually several key innovations that no one succeeded with before.  And not for lack of trying: there were a number of people on the cypherpunks list who were exceedingly interested in ecash, viewed it as the holy grail, and tried hard for many years (say 1995-2005 range) to figure out how to deploy ecash.  (All the central server ones failed, out of business, failed to reach critical mass).  And so there was interest in distributed ecash.  For example the 1999 Sander & Ta-Shma paper generated a lot of interest (pretty close to zerocoin - the zerocoin references that paper).  As far as that goes the bitcoin paper cites the hashcash paper for the proof-of-work, and uses it with small changes (not all of them positive).

Anyway before you say cypherpunks are grey beards trying to muscle into the bitcoin party, you might want to read some of these 1999 threads on the cypherpunks list. 

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

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

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

Eg Wei Dai's B-money and this thread talking about distributed mining.  There was an anonymous poster on there who seemed more convinced the B-money related very bitcoin like idea could work - that could have been a 1999 Satoshi:


The rest of us got stuck on inflation (moore's law) or deflation (fixed up-front supply of coins) and couldnt see a way to control it, other than human intervention.  You can see in hindsight that proposal in that thread is rather close to bitcoin and yet we stupidly abandoned the concept and spent years more trying to find other ways to get there.

Hashcash did have some concepts of inflation control but they were not implemented the proposal was to have some group of people estimate moore's law against a reference $1000 machine, and set hashcash difficulty so that the $ cost per hashcash stamp was constant.

I also propose an auditable namespace, I forget when probably around 1999 or so, and bitcoin is related to auditable namespaces.  https://bitcointalk.org/index.php?topic=220138.msg2317418#msg2317418


Another who is this annoying guy first post:

https://bitcointalk.org/index.php?topic=15672.msg1873483#msg1873483

Adam

Greg also said something like that:

https://bitcointalk.org/index.php?topic=139581.0

but as a multi-user/multi-input transaction to complicate simplistic tracing taint back to a the owner on the assumption that all inputs from spends are from the different addresses of the same sender.  So in that case there is no unsigned input statement, just a multisig with multiple inputs (from a variety of people) and multiple outputs, so there's not really any doubt about who put money into the mix or who took money out (presuming each person takes out what they put in), just that any tracing identities has to account for this existing mixed owner inputs possibility.

You could view the version when all the transactions in a block are mixed as something like zerocoin except with a fresh anonymity-set for every block.  And the output goes directly to the recipient which I guess could be done with zerocoin also (put recipients address rather than your own on cashing out of the pool).


Interesting but limitations with DoS vulnerability & also multi-round.  Also presumably if the amounts are uneven you can pair spends and change amounts that match to inputs, and conclude one is the recipient of that sender and on the change to self.  However I see that's what the ref to a post by Mike Hearn was about, splitting the payments to lot of keys in small enough payments to create ambiguity.

https://bitcointalk.org/index.php?topic=93390.msg1036406#msg1036406


Towards a more efficient solution, maybe we could use a ring signature scheme so that groups of users can spontaneously form groups, and sign on behalf of the group without revealing which user they are.  (Ring signatures are like 1 of n multisig but do not reveal which user signed).

When all the outputs are group signed, the users sign their respective inputs to fund the transaction and publish it.

http://people.csail.mit.edu/rivest/RivestShamirTauman-HowToLeakASecret.pdf


That same set of users can then sign (with normal ECDSA) the inputs to fund the transaction.  Doesnt completely solve the DoS problems, but you cant just spam you have to join or be elected as a group member by the initiator (just one user).  The process of choosing which users will be in the group is flexible from the ring signature perspective - the other users dont even have to cooperate.  The ring signature concept was extended by others to cover DL based signatures (and EC) so I think you could simply enough add ECDSA ring signatures.

The point is you dont want to know who proposed each output, but the inputs have to be signed to release the funds.  And yet you dont want a spam free-for-all of proposed inputs, the ring signature keeps the proposed outputs unidentified as to which user proposed them.  The sender retains control however as he wont sign the input unless the outputs match the requirements of his payment and change.  The group setup doesnt need to involve the miner in this way either so everything can be done in one round.

[edit] btw the ring signatures are exceedingly computationally efficient, barely any more than the underlying signature in the case of Rivest's and its actually a simple concept here's a simplified example RSA ring signature: something like if an RSA signature is presentation of a s=H(m)^d then a simplified 2 user ring signature could be eg s1,s2 where s2=r and s1=(H(m) xor r')^d, r = random, r' = r^e then to verify the verifier calculates s1^e=H(m) xor r' and s2^e = r' and test with (s1^e xor s2^e =? H(m)).  Now you cant tell if s1 or s2 is random, and so it could have been signed by either person.  The other person you implicate in this "could have signed" game doesnt even have to participate, but the verifier and anyone can be convinced that the message must have been signed by one of them.  (Technically r is an existential signature forgery of "message" r'.)

Adam

Yes the miners need to validate for double-spends and collect the anti-spam related fees that are not hashed/not encrypted (in the clear on the outside).

Adam

I am saying it is possible to leave the validation to the transacting parties.  The spender just reveals the input transactions to the recipient, the recipient checks the validation and that the transactions are on the block chain (in hashed form) accepts or not accordingly as usual.

You shouldnt ideally be relying on a few powerful miners to do validation anyway if the miner is dishonest or more likely hacked you can accept fictitious bitcoins that weren't mined.  SPV clients do rely on this because they dont have enough bandwidth.

You can decommit the hashed coins to help SPV clients as then most transactions can be validate by the miners (all the old decommitted ones).  The only coins that cannot be miner validated are the ones that have not yet been decommitted.  (How many times user respend in committed form without decommitting is up to them, though such coins are a bit less SPV friendly.)

Adam

Yes I had the same thought - seems awfully expensive for a mix.  You can view zerocoin as a private keyless p2p mix.  Several people have proposed non-p2p mixing protocols where the mix cant steal your coins.  Whats wrong with that?  I guess the main limit is the mix disappears and your coins get locked.  Probably that could be fixed with smart contracts/multisig.

Greg Maxwell also and others proposed taint mixing using multiple coin inputs.

(Other than mixing you may also aim to taint all, equally as a protocol).


I agree that is likely the end game for mixes.


The committed coins idea that temporarily keeps the taint decision private allows people to at least retain p2p decisions about taint without any a priori restrictions.  However the privacy is either short-lived (fairly immediately decommit the coin) or the privacy shrinks over time (if you keep spending the coin in committed form) as more people get to see the transaction history, as each recipient must see all details prior for validation.  A posteriori sanctions after decommit may come into play to if the user is identifiable - if your IP address is logged as posting the reveal of a tainted coin, maybe that matters also.

Fairly efficient/low overhead but still some limitations there.


It seems like users who are doing high value bitcoin things should be using ToR to hide their IP address which geolocates them.  And servers also should to add resistance to network split types of attacks.  Maybe in a 2.0 bitcoin it might include the minimal defenses of encryption, tunneled relaying and hard to influence remote connections for double-checking local claims.

Adam

Another time-related concept is a beacon - that is a broadcast, unpredictable and fairly chosen random value.  Eg like this weeks national lottery numbers, someone has gone to lengths to ensure they are chosen fairly, and they are published widely on TV, internet, newspapers etc.  You could view the latest bitcoin block hash as a bit like a beacon.  Even the miner cant control all the bits - it costs him enormous computation just to control the first 55 bits (current log2 target).  There are another 101 bits he cant control; he could control 1 bit by doubling his effort and reducing his mining reward by 1/2 etc.  To control them all is considered impossible.

Say each user, or users collaboratively store the sequence of beacons and vouch for the correctness.  (In the case of the a time-stamp merkle hash chain, used as a beacon it helps you verify that because each block hash includes the previous hash in its preimage.)

You might wander if one could use an abstract beacon for timestamping (beacon without preimage chain).  Could use a beacon to prove that you made a transaction, or mined a pool-sized mining share at a given point in time?  Not fully: if you include a hash of a beacon in your mined pool share, or transaction signature, then you do prove that you did that after the beacon.  However you can also back-date your operation.  Eg you could intentionally include an old beacon value.  Because bitcoin is more concerned about back-dating than forward dating, it doesnt help much.  (Bitcoin concerns itself with first to do something, not last).

To prevent backdating, bitcoin (and time-stamp servers, and auditable name-spaces) put the hash that you are dating into the "beacon".  That proves it was published then.  It may also have been published earlier (ignoring validation), but at least you cant create something and then try to change its date of publication.

Unfortunately to prevent backdating seems to require transmitting all values to the timestamper/namespace manager.  And in a distributed timestamper/namespace manager broadcasting to all full nodes.

A namespace manager also wants to enforce first come first served (no name reuse) so it enforces that it wont stamp names (or name hashes) that it has seen before.  (If the names are random looking like public keys, hashing names is secure against brute-force, unlike hashing domain names or email addresses, so with bitcoin, like with document time-stamping you are not revealing the document/public key at the time of publication).

Adam

I've been trying to understand the relationship between timestamping, namespaces and validation in bitcoin.

Bitcoin is described as relying on a timestamping service.  Now in existing (non-bitcoin) time-stamping service, merkle trees are used to hash a set of documents users want to time stamp during a period into a merkle tree.  The merkle tree root is published (assumed unchangeable)  The previous periods merkle root is also hashed into the current merkle tree, to prevent historic modification.  (Just like bitcoin in fact so far).  The time-stamp server may sign the merkle root; bitcoin substitutes a distributed attempt to create a proof-of-work for a signature that the current majority by CPU power agree is correct.

But bitcoin is more than a timestamping of transactions.  Timestamping does not guarantee uniqueness.  Users are allowed to stamp the same document more than once.

So lets consider a less distributed bitcoin where peers rely on a time stamping service.  Consider it has only full nodes for now.  To know transactions are not double spent they have to track all documents (transactions) hashed by the timestamp server each time period.  If the timestamp server signs its hash every period, if it ever cheated and issued a second merkle root for the same period, all peers would have a proof (and could migrate the timestamping over to a competing time-stamp service).

However that is not convenient for SPV nodes, the only way to know a transaction was not already spent is to look at all time-stamped documents (transactions) ever.

Namespaces have the missing property.  A namespace manages and allocates names on a first come first served basis.  The same name is not allowed to be issued twice.  For bitcoin purposes we'll consider names do not expire and so do not become available for recycling.

We could use a namespace to implement bitcoin.  Eg consider DNS name .bitcoin operated by a somehow trustworthy registrar with the first come first served, never expire policy.  Now we could mine by being the first to claim the name being a hashcash stamp (mined as bitcoin on the hash of a public key).  Stamps which dont match difficulty are ignored or rejected.  When we spend we claim the name being the public key and output.  As owner of the name we can attach txt records to it (eg the signed transaction including the public key hash of the new owner).  For bitcoin purposes transactions which are not signed are ignored or rejected and with names (public key+outputs) that dont correspond to previous txt records (public key hashes of coin owners) are ignored or rejected.

Namespaces can be some-what distributed but publicly auditable to reduce or even avoid any trust in the registrar.  

eg http://cypherspace.org/p2p/auditable-namespace.html

If no trustworthy registrar could be established, the protocol could fall back to current the full p2p bitcoin namespace of the list of transactions.


Bitcoin does one more thing beyond namespace management which is to expect the miner (distributed transaction namespace node) to validate transactions.  Meaning that the inputs have sufficient value to cover the outputs.  That implements coin splitting and combining.  SPV nodes even rely on that, full nodes check it themselves.

Note that with the exception of validation, a namespace manager (auditable and being distributed, somewhat-distributed, or even central) does not need to know the names nor documents.  ie It is normally the case that a time-stamping service does not know the contents of the documents it is stamping.  Eg because they are published in hash form, or hash of non-malleable encrypted form.  The same can be true for namespaces.  It reduces the need to trust a time-stamp server or name-space server if it doesnt know what it is timestamping/allocating names of.  That is because it cant apply apriori policies about whose documents it will process, nor what the documents can contain, nor who they can be addressed to if it doesnt see the document.  

And it can not undetectably revise history because of the published chain of merkle hash roots.  And if it does detectably revise history, other servers or peers in a p2p protocol can reconstruct the true history.  Consequently a mostly trustworthy server (say 99% of transactions have no attempt to modify history by the server) we can still leverage service from such a server.  Its easier to scale such a server and users can then concentrate on validation and reconstruction and repair of history revisions which is a 1% problem vs a 100% problem.

Adam

So one thing you could think of and I think it has been mentioned a few times is that you could replace the merkle tree in bitcoin with an accumulator based tree.  Now a problem with accumulators is someone or some set of n people only 1 of whom has to be trusted, have to create n = p*q two primes p, q and then delete p, q; which is not great but could be entertained perhaps if accumulators made some big saving.

Consider accumulator hashes: then an SPV client can be convinced a coin is in a block by receiving Bi and xi.  Each Bi is 384 bytes (3072bit RSA n is about the same security margin as the rest of bitcoin, considered about as secure as 128-bit symmetric keys and 256-bit EC keys).  Then a proof of membership within a block is 384 bytes + the hash say 20 bytes + the transaction detail whatever that is a hundred bytes say 512bytes.  

The merkle tree approach requires log2(k) hashes each 32 bytes, k the number of transactions in a block.  I guess a block could hold ~10,000 transactions best case with 1MB blocks.  However this page https://en.bitcoin.it/wiki/Scalability says transactions per second is currently limited to 7 = 4200/block.  log2(4200) ~12 and 12*32=384 bytes.  No saving for accumulators!

However another trick could be to not start a new accumulator with each block, just keep going, then you only need the last block in the chain.  (SPV clients download all blocks, or some set of recent blocks for confidence?)   So with accumulators to catch up an SPV client just download the latest block, cross-check a few peers agree its the latest block.  However someone (each full node?) would have to update Bi for all unspent coins.  Updating Bi is a 3072-bit to a 256-bit modexp operation which has some cost.   That might start to get unreasonably CPU expensive, unless the network shares out the work.  The benefit would be faster catchup for SPV clients.

I suppose alternatively blocks themselvs could be placed into a sorted merkle tree, and then SPV clients could download blocks as needed (log2(b) blocks where b is 23866 blocks so far http://blockexplorer.com/q/getblockcount) ~15 blocks to test a given block.  But its probably not a big saving because transactions are made from multiple outputs and an SPV client if it does a few transactions per day will soon have to download all blocks anyway.

Or you could have an accumulator tree of blocks, with the accumulator hashed in the latest block.  Then you can download any historic block and instantly check it belongs in the history of the current block without downloading the rest of the block chain, nor 15 blocks for log2(b) verification if the block were organized as a merkle tree.  Cost is each full node needs to update (or fullnodes cooperatively update) the Bi values for all 23866 blocks every block (10mins).

Some possibilities in there but nothing very impressive, plus the problem of there temporarily existing an accumulator private key that must be deleted (spread across the RAM of n users during accumulator genesis/generation, only one of which needs to be trustworthy).

Adam

Another thing CPU cores have going for them over GPU is they are independent.  AMD GPU cores are in SIMD groups, eg 7970 has 2048 cores, but groups of 16 of them have to execute the same instruction each clock on different data, that means if you force them to do dynamic work, there are only really 128 cores that can do independent dynamic work.  And the cores are about 32x slower than a CPU core.  So then a four core CPU matches a GPU for dynamic workloads.

However again that is not a good ASIC-hard direction because the SIMD nature of AMD GPUs is overcomeable eg http://www.adapteva.com with a MIMD (ie no SIMD restrictions) 28nm 64 core risc CPU and plans for 1024 even 4096 risc cores per chip.  And they are low energy too.

Adam

I can see the attraction of CPUs however if you optimized for the CPU to the detriment of the GPU, that leaks possible advantages to ASICs over GPUs.  I think about all you can say that a CPU has is faster single core performance (irrelevant for mining: more compute bandwidth is more important than per core speed).  And main memory readable over a narrow bus (DDR3 64-bit vs DDR5 over 384-bit).  GDDR5 in an AMD 7970 is quad-pumped at 1500MT with 384-bit data bus where as DDR3 is dual-pumped a 1333MT or 1600MT etc similar speed.  So if you are reading random chunks in CPU friendly 64-bit chunks the GPU ram is still 2x speed (quad vs dual pump) even though its 6x bus-width advantage is wasted for random access.  However i7s have two memory channels so they match the GPU for 64-bit reads.  Some CPUs eg 3930k have quad channels so they can do 2x that and beat a GPU.  i7 3930k rated at 51.2GB/sec memory, regular i7 at 25.6GB/sec bandwidth, amd 7970 rated at 288GB/sec but in terms of ability to read 64-bit chunks the 7970 would do 6x less = 48GB/sec.

However the peak figures are in sequential read, DDR3 and GDDR5 are both slower with random reads.  And thrashing RAM with reads for data intentionally too big to fit in L3 is going to bog your computer down for normal use.

Adam