Topic: chaum, offline coins vs BGP & bitcoin (Read 3809 times)

Not sure if there is maybe a literature survey paper but the people who came up with using PoW http://hashcash.org/papers/comp-chal.pdf have a number of references which you'd hope would be the best results if they were then going to claim to go further in comparison (by shifting the problem statement partly).

Probably you can find copies of those online.

Adam

Adam, could you point us to those other known algorithms? I'd like to have a look at them.

Greg is right I retract above.  Depending on the attack model 33% of the hashrate is the threshold above which the colluding miners start to gets an advantage arising from block withholding relative to non colluding miners.

That doesnt mean 33% can attack, it means eg something like they could 50% attack with 40% hashrate - or however the advantage works out (assuming the rest of the network does not collude in other groups).

I agree the 25% variant doesnt seem very convincing as that depends on racing the other miners to relay, and you have to imagine other miners also have an incentive to use low latency connectivity too.

Adam

Thats a misunderstanding about what the selfish mining paper is talking about.

The Bitcoin whitepaper talks about 51% being honest.  In the selfish mining paper, instead we assume that miners are greedy ("rational" in the BAR model, which calls honest parties that follow the rules no matter what "altruistic") and will do whatever makes them the absolute most money.  This is interesting because Bitcoin also has security in this more adversarial model, and you can handwave about those incentives as to why miners might be aligned in the honest bunch. Partly I say handwave because the BAR model really fails down when talking about Bitcoin. E.g. consider some move that gives a miner a bunch of bitcoins but immediately makes Bitcoin worthless by undermining trust in it faster than the participant could exist the system, is this a rational attack or a byzantine attack?

In the selfish mining paper they show given certain assumptions about informational advantages (they need to be able to partition much of the network in order to outrace blocks) the existence of a sufficiently large but minority dishonest cartel can behave in a way that rational parties would earn more mining income by joining with the cartel rather than following the rules.

The paper proposes an 'improvement' which isn't really an improvement. It eliminates the cartel advantage below 25% but at the cost of eliminating a need for an information advantage and guaranteeing success for cartels larger than 1/3rd.

If the selfish mining paper is correct that a miner with 1/3 of the network can pull off a successful attack, does that not imply that 2/3 of the hashrate must be honest to solve BGP?

Note while its not clear if Satoshi was aware of it or not, because its not cited, but this 2005 academic paper proposes the same PoW based symbil resistant BGP solution that bitcoin uses (this paper also cites hashcash):

http://www.cs.yale.edu/homes/aspnes/papers/tr1332.pdf

its seems quite plausible to me that Satoshi reinvented the proof-of-work based BGP solution though.

Adam

Well there were other known algorithms for BGP and the best of those required minimum 1/3 honest participants.  The issue is that hidden in that is the assumption that participants can only participate once, and that assumes identity (or is-a-person credentials and a central trusted issuer).

Identity is problematic on the internet, back when I published hashcash (1997) people were proposing identity centric ways to limit spam, and of course they were failing.  Some people still are proposing such things.  They start by assuming that the sender is reliably identifiable, and then design a protocol assuming that identifiable people would not spam, and/or plan to blacklist identified people who do spam.   This does two things: firstly it erodes privacy, and secondly it doesnt even work because the spammers just create lots of identities or borrow or steal them or whatever.  I view it as garbage in, garbage out: if you start with a false premise (that identity is a solved problem on the internet) you get garbage out: a protocol that doesnt work.  Furthermore it is bad for privacy, so as well as not working it has very undesirable side-effects affecting everyones privacy.

Hashcash was a rejection of identity, and tried to address the root-cause of the problem by adding sender cost in an anonymous/identityless, scalable way.

I'd say bitcoin appears to make a similar rejection of identity approach. 

The bitcoin solution is one BGP vote per hashrate.  ie rather than try to fight sybil, just go with it, and give people one vote per hash.  That imposes maybe a lower inflation of votes than pure network/identity sybil, or at least its approximately fair in electrical cost and equipment investment.

Its kind of curious that according to the selfish-mining paper, if that remains the conclusion, hashrate BGP is also assuming 1/3 honest hashrate (same ratio as previous BGP solutions, but just with "vote per hashrate" rather than "vote per participant".

Secure the bitcoins, dont secure an identity.  Security identity is hard, and if you try it anyway, then people can steal assets by identity theft, impersonation etc.  Where is identity rooted?  Its a human concept.  So then you have TTPs and CAs, and those have never proven to be particularly secure; the RA processes are a source of identity theft.

Adam

Thanks again for the detailed response. Much appreciated.

I think many consider Bitcoin's main "innovation" to be the practical solution to BGP, but your notes are making clear to me that inflation-control was also a big unsolved issue. Seems obvious, thinking about it more, that it's a tough problem, but that hasn't been the narrative; at least not the one I've been mostly exposed to. So thanks again for the observations. Interesting that Satoshi's solution solves both issues in a somewhat atomic way.

I think there are two things:

online chaum ecash, has central double spending protection.  that works very reliably right up until the central server goes offline (which it did when digicash went out of business).

offline chaum ecash, the double spending protection is weak because its just a deterrent.  all it does is identify who double spent (up to the limits of identification, which can be subject to identity fraud etc), following which presumably some sanction happens - person gets sued? conventional account frozen if assets in it to recoup losses or something.

not really compatible with an identityless model.


right so hashcash stamps are more like on-use stamps (for email postage, prevent server resource abuse etc).

people pretty much immediately after hashcash was released started observing that hashcash was like digital gold, and trying to work out how to control inflation.  No one really figured it out until Satoshi.  I think the difference is he didnt try to fix price inflation to zero (which seems to fail as it seems to require an outside data feed which becomes a point of centralisation or central rate setting policy) but rather controlled the supply inflation instead which is internally achievable without external reference.


right.  b-money was an idea only.   probably other non-trivial things to work out to make it practical.


they proposed it in the context of audit of a bank.  but because its keyless it is compatible with p2p use and people noticed that at the time as I recall.  so if you figure out a way to do p2p ecash (which satoshi did) then you can combine it with Sander & Ta-Shma to get cryptographic privacy via ZK set-membership proof, and this is what zerocoin did - use (and optimize) sander & ta-shma with bitcoin.  not fully implemented, but fully specified and practical if a bit inefficient.


its pretty easy to implement hashcash - I am not sure if he used the reference library (it is quite optimised in assembler so he may have) probably the RPOW code is online.  Hashcash is an algorithm (mathematical description) and there is a library/implementation focused at telnet protocols.  Easy to use the algorithm for non-telnet encoding.


Yes bit-gold proposed to use hashcash (I was unsure, but a while back found a clear reference on one of Nick Szabo's pages about it from a decade plus ago).


no not really.  There is a footnote in the thesis but I was unable to find the manuscript as its a masters thesis.  I could write it up a bit better some time, but for someone familiar with the protocol details they could probably make it work from what was said in OP.  The brands protocol itself is implemented eg http://cypherspace.org/credlib/ and links to papers there, and microsoft (who released the patents under a very open license) has an implementation also.

Adam

How about Truledger and Loom?

Expanding beyond Chaum's scheme, let me see if I've got the early attempts right:

eCash:
-- Pioneered digital signatures to do untraceable spending. "Good privacy".
-- Relied on a bank ("weak survivability"), and did not sufficiently solve double-spending

Hashcash:
-- Pioneered hashing-based proof-of-work. Built originally as an anti-DoS system that could be incorporated into a variety of projects.
-- Was not designed as a generalized digital-cash/monetary system

b-money:
-- Used Hashcash to generate coins
-- The practical-to-implement version still relied on a collection of authoritative servers to do double-spend protection.

Sander & Ta-Shma:
-- Auditable and anonymous cash
-- Still has a bank. From the paper's abstract: "The security of the system relies instead on the ability of the bank to maintain the integrity of a public database", which seems like a fatal survivability issue.

RPOW:
-- Used Hashcash (directly, or Hashcash "style"?) proofs-of-work and extended to be "reusable". Double-spend protection done via remote servers operating on trusted-computing platforms.
-- TCs can still have attack vectors pertaining to hardware manufacturers' original keys.

Bit gold:
-- Used a proof-of-work (was it actually Hashcash?) in the definition of coins as a chain of proofs-of-work
-- Described the idea of using distributed secure time-stamping to log these proofs in a "title registry".
-- Never adequately described how the distributed secure time-stamping and title-registry-appending could actually work in practice.


So none of the above sufficiently solve double-spending, and most also have economic problems with supply issuance and increasing computer hardware speed. Bitcoin is the first system to workably address both concerns...


Any corrections to the above (very) high-level description? I'm putting together an early history (designed to be very brief) for a non-technical audience, and am trying to convey the fact that people were working on this for a couple decades before Bitcoin, and that it was a gradual process, with Bitcoin finally putting the pre-existing pieces together in a new way that solves the prior problems through a mix of economic and technical approaches.

And do you have a link to your variant of Brand's work?

Thanks again for your above response to my initial question.

I remember the digicash wallet, as I recall I bought $20 worth in the '90s to spend 15 and never used the rest after reading about it in Wired magazine, but ended up using cybercash instead to do credit card processing for my homebrew ISP.

Ah - thanks. Sounds like the offline double spend protection had essentially no deterrent against identities double-spending exactly once (assuming identities did not somehow give away real-world location/ID info); clearly a systemic problem if identities are cheap to create.





Thanks for the outline - much appreciated. Fascinating how many of the pieces were in place for a decade or more. I suppose many important inventions are like that.

thanks, good summary

Moving this question into a new thread:


not solved at that time, it was only online double spend protection that was robust with Chaums scheme, and that was with respect to a central server that was the authority on which coins were spent.  Good privacy, but weak survivability as very centralised.

The offline double spending protection of Chaum was kind of weak because what it boils down to is you could actually double spend, but if you did that eventually someone would learn your identity, which they hoped would be sufficient deterrent.  (Eventually the double spent coins would get deposited at the bank and a simultaneous equation in the double-spenders identity revealed).  How it works is the coin has embedded in it your identity in a way the bank can verify, but which is kept private so long as you do not double spend.  Chaums offline double spend is a bit space inefficient as it involves cut-and-choose a generic proof mechanism, also used by zerocoin and which is the primary cause of the zerocoin bloat.

Hal Finney did a write up on this Chaum cut-and-choose scheme for more detail: https://w2.eff.org/Privacy/Digital_money/?f=double_spending.articles.txt

Stefan Brands ecash system has more space efficient offline double spend protection because the coins support (without cut-and-choose) multiple attributes directly.  However the default scheme is just delayed deposit (not offline respendable).  Actually I guess Chaums offline scheme has that property also.

I reinvented an offline respendable variant of Brands around 2000/2001 but when I asked him about it he pointed me at a footnote in his thesis / book referring to someone's masters thesis.  How that works is people have multiple spare 0-denomination coins, so when you accept a coin you use this 0-denomination coin as the initial witness (random value chosen by recipient as part of the ZKP).  In this way if someone downstream offline respends and does a double spend, its their 0-denomination coin with their identity in it that gets identified as the first double-spend.  A downside of this is the coins grow on each respend.  Its a bit like bitcoin as the respends are also pseudonymous but linked in their spend history (which I viewed as a not ideal limitation of the approach) where as the online coins are anonymous but more vulnerable to traffic analysis as you had to race to deposit to be guaranteed to receive.

The other paper from 1999 was Sander & Ta-Shma's auditable anonymous electronic cash which is extended by zerocoin (its zero knowledge proof of set membership based - the list of unspent coins is public but to spend you prove in zero knowledge that your coin is one of the unspent ones, but not which one).  Its kind of interesting as the "bank" doesnt have a private key, so its clearly p2p compatible.  So kind of a zerocoin precursor existed before bitcoin, zerocoin refers to this paper.

I think the main missing bits from Chaum/Brands/Sander & Ta-Shma/b-money/bitgold were how to do inflation control without reference to any central party or network external information and sybil resistant solution to byzantine generals problem (double spend problem - which spend of many comes first).  Plus a bunch of implementation level detail. 

You can see that Wei Dai's b-money & Nick Szabo's bitgold both 1998 offered some directions on ideas to vote on or have a market effect setting inflation, and both included hashcash mining as bitcoin does, but they did not connect a p2p (no enrolment/no identity) solution to sybil attack on byzantine generals problem (double spending, which spend comes first) with mining, nor arrive at the elegant solution of having an engineered supply function that can be measured internal to the network that bitcoin introduces.

Adam