No what I am saying is Satoshi did know about and use hashcash, because he cited it (and wrote to me in aug 2008 to ask for the correct citation).  But seemingly he didnt know about B-money from what he told me & Wei Dai, and seemingly didnt know about bit-gold either from what he told Wei.  I put links to those things above in the OP, which were collected by Gwern on his blog.

My point is lots of smart internet protocol aware / programmer type people knew about hashcash for 11 years before bitcoin was announced.  If hashcash was the only novel required building block (other than very widely known things like digital signatures and hash functions) then the number of people who can code, are interested in internet technology and knew about hashcash is hard to enumerate but must be in the 10,000s if not 100,000s range.

To be clear Satoshi solved some difficult problems that others had tried and failed to find answers for (how to build a distributed ecash system with hashcash mining without creating a centralised mining inflation rate control, ie how to control inflation (bitcoin solves a different problem supply side inflation which is mathematically controlled - others tried to design around price inflation, which seems impossible).  But there were others who tried, and independently thought of the problem that needed to be solved.  The sybil resistant consensus system reusing the proof-of-work is a neat innovation too.

Adam

the lack of that supply fedback could be engineered into bitcoin somewhat (though bitcoin cant measure price as thats external, it can measure other indicators, like rate of difficulty increase/decrease, and also more slowly and manually adapt supply to community super-majority consensus), see: https://bitcointalk.org/index.php?topic=907157.msg9969697#msg9969697

(I had been meaning to post those two topics and your comment reminded me but I started it in a separate thread).

Adam

Some hypothetical thoughts about price stability, (lack of) price/supply feedback and long run electrical cost.
Not a call to change anything just some thoughts.

One observation people often make about the difference between bitcoin & gold is that gold reacts to price changes, by rate of supply increasing when price is high, and rate of supply decreasing when price is low.  This effect has some positive feedback loop in the direction of stabilising gold price.  Products with an inelastic supply function (like bitcoin or farming with long production lead times) result in gluts and shortages which take longer to self-correct than something with an elastic supply function.

While bitcoin cant directly know its price as that is an externality, one related thing it does know is the rate of difficulty change.  An indication that supply is too high would be that difficulty is slowing, or similarly an indication that supply is too high difficulty increasing too fast.  

So we could (hypothetically) change bitcoin to decrease subsidy per block if difficulty increase is above 10% per 2016 block period (2 week retarget).  What could we do with the unclaimed subsidy?  We could defer it so that bitcoin subsidy lasts for longer, and/or we could bring it forward again if difficulty slowed, eg for example increase the subsidy per block if difficulty increase falls below 0%.

If subsidy is not deferred, just deleted, that saves electricity and reduces the supply.

One might even speculate that the absence of price or rate of difficulty change feedback is currently causing price drops as mining difficulty is falling for the first time while the production cost (mining) is efficient (close to market price of coins) even for the most efficient operators.  Or put it another way miners in todays market would be happy to get another 5% at 13.125 btc/block over 12.5 btc/block.


A second question is if bitcoin is $10,000/btc or $100k or $1mil which would be supported by various real-life uses eg see page 5 of report comparing to different aspects of gold ownership https://cdn.panteracapital.com/wp-content/uploads/Bitcoin-vs-Gold.pdf then at those prices, what happens to electrical use and mining investment.  Is the result sustainable.

Now one argument is more security is needed for higher market cap $21 tril?  And another argument is you cant have mining cost artificially pulled below market price or people will expend that amount of money anyway to bypass, bribe, hack etc the artificial factor.  (eg Paul Sztorc makes that argument in his blog post http://www.truthcoin.info/blog/pow-and-mining/)  I notice Nick Szabo made a similar point in an old blog post also.  The cynic may like to think of the lack of mining for USD (or other fiat) leading to huge expended effort for people to lobby, bribe etc to get access to government funds, where those funds partly come from inflation (which is a form of taxation) and also quantitative easing and bailouts.  The resources arent actually saved, they they just go into lobbying efforts and create cost via inefficient allocation of capital that arises as a cost of moral hazard.

Maybe at these prices subsidy ends up being too high for the needed security and transaction fees cant go negative!  Anyway it would also be possible to voluntarily shrink subsidy per block (phased in over time to respect mining investments).

Adam

More early bitcoin-like what-ifs:

http://cypherpunks.venona.com/date/1997/07/msg01268.html


Adam

I mean did it occur to you that it might be possible to have digital scarcity (and perhaps that this was interesting towards having a deployed ecash system).  The closest physical analog in terms of usage being gold.

Adam

Here's some apr 2007 stuff on decentralised ecash requirements and using hashcash (pre b-money).

http://cypherpunks.venona.com/date/1997/04/msg00822.html


(there's more read the link).  Sounds like b-money/bit-gold line of thinking.

Adam

See also (continuing from) https://bitcointalk.org/index.php?topic=906865.msg9965116#msg9965116 first poll question #1 did you learn about hashcash before bitcoin?

There is an implied secondary assumption about oh but who would think of using hashcash for electronic cash.  Well actually hashcash was proposed as a form of electronic cash and the announce itself compares features with Chaum's ecash http://hashcash.org/papers/announce.txt.  Also at the time of hashcash initial announce multiple people independently commented immediately that hashcash was like digital gold (and punned about bits) and then a number of people explored (unsuccessfully) how to control inflation which would run at moore's law etc.  The idea of trying to control inflation wasnt new either (but succeeding is!)  I discussed some hierarchical variant to  control inflation (eg a group of people could benchmark equipment and push out a new difficulty level via DNS), however that was unsatisfying as that would make them the central-bank.  In the end I opted to leave that to recipient policy (recipients would gradually increase their minimum stamp size over time so there was a decentralised consensus on what is appropriate to curtail spam).  This was possible because hashcash was mainly used to increase the non-spam score - lower required was fuzzy so you'd still receive the email with a lower than required (if it was relatively non-spammy).  

Wei's b-money relates to that in proposing to make hashcash respendable and one of the inflation control proposals and Nick Szabo's bit-gold has a different inflation control proposal.


Anyway I claim the hard part about bitcoin is the decentralised secure inflation control (and sybil resistant byzantine generals solution.)  But the idea that PoW is some kind of virtual gold and it would be useful to figure out how to control inflation to make it respendable seem to have been ideas that immediately reached out and grabbed many people.  Or thats my claim!

What do you think, what do you recall your thought process being if you heard about hashcash before bitcoin.

Adam

see also second question of poll https://bitcointalk.org/index.php?topic=906867.0 #2 did it occur to you hashcash was like virtual gold

A recurring sub-topic in the who could Satoshi be debate is what knowledge would have been required and what communities discussed and were exposed to the required building blocks before bitcoin.

The assumption about the need to have known about b-money (because it is cited in the bitcoin paper), is seemingly invalid as from various Satoshi emails it seems he wasnt aware of b-money until after the paper was written and added the citation after it was pointed out to him (by me).  See eg https://www.gwern.net/docs/2008-nakamoto   Similarly bit-gold isnt cited, and the same Gwern post quotes Wei Dai saying Satoshi didnt seem to know about bit-gold either.  See also footnote 34 of gwern's blog article http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better  Similarly Hal Finney's RPOW wasnt cited either.  (b-money was announced originally in 1998 on the cypherpunks list.)

One of my contentions with people who asked me what I thought about that line of thinking (must have been on this or that mailing list) has been that well lots of people knew about hashcash before bitcoin, going back to 1997.  In the context of anti-spam (much tech news and tech magazines online and offline, discussion forum coverage existed at that time, probably suffered some bitrot since) and blog-spam (wp-hashcash) and namespace protection (in i2c tor-like FOSS competitor) and anti-DoS protection (in tangler, in interactive protocols etc) but I suspect that many 10,000s of internet programmers & technically minded people knew about it.  Eg. It was a fairly common experience for me to recognised by name at security conferences "hey you're the guy who did hashcash".

There is an implied secondary assumption about oh but who would think of using hashcash for electronic cash.  Well actually hashcash was proposed as a form of electronic cash and the announce itself compares features with Chaum's ecash http://hashcash.org/papers/announce.txt.  Also at the time of hashcash initial announce multiple people independently commented immediately that hashcash was like digital gold (and punned about bits) and then a number of people explored (unsuccessfully) how to control inflation which would run at moore's law etc.  The idea of trying to control inflation wasnt new either (but succeeding is!)  I discussed some hierarchical variant to  control inflation (eg a group of people could benchmark equipment and push out a new difficulty level via DNS), however that was unsatisfying as that would make them the central-bank.  In the end I opted to leave that to recipient policy (recipients would gradually increase their minimum stamp size over time so there was a decentralised consensus on what is appropriate to curtail spam).  This was possible because hashcash was mainly used to increase the non-spam score - lower required was fuzzy so you'd still receive the email with a lower than required (if it was relatively non-spammy).  

Wei's b-money relates to that in proposing to make hashcash respendable and one of the inflation control proposals and Nick Szabo's bit-gold has a different inflation control proposal.


Anyway I claim the hard part about bitcoin is the decentralised secure inflation control (and sybil resistant byzantine generals solution.)  But the idea that PoW is some kind of virtual gold and it would be useful to figure out how to control inflation to make it respendable seem to have been ideas that immediately reached out and grabbed many people.  Or thats my claim!  That is topic of following poll.


It would be interesting to see if the assumption that many people heard about hashcash before bitcoin is valid.  The few people I asked informally said yes they'd heard of hashcash long before bitcoin.

Adam

ps the answer to what's hashcash http://en.wikipedia.org/wiki/Hashcash and https://en.bitcoin.it/wiki/Hashcash and http://hashcash.org

OK never mind I think it must be this:

3.2 t=random(0,n)
3.3 user sends z=H(m), P=tG
3.4 signer sets u=random(0,n),r=[uP].x
3.5 signer sends s'=(z+rd)/u,r
3.6 user sets s=s'/t (so that k=ut and s=(H(m)+rd)/k)
3.7 user verifies sR=?zG+rQ

that seems pretty good, two moves only, nice hhanh00.

Adam

eh what happened to the message from hhanh00 that this was quote from?  Seems to have been deleted from the thread?

Someone want to reinstate that or retype the missing protocol steps from it?


Adam

Well presuming we're talking compressed points, thats 256-bits per point or value, then I think doing what I said should be 1x 256-bit point homomorphic value, 2x 256-bit elgamal encryption, a proof of discrete log equivalence signature (2x 256-bit) so 4 values.  4 vs 6, net saving?  Maybe I missed a point not sure without writing out the protcool.  And the CRT scheme while interesting is kind of shiny and new and slowish to decrypt.  It looks ok to me, in terms of crypto-conservatism; but I think this elgamal equivalence proof etc is even more conservative.  (And so is the schoenmaker's range proof IMO).

Adam

There are variants of schnorr proof of knowledge (DSA is a variant of schnorr) where you can prove that encrypted values are the same by combining with Elgamal.  So I think you should be able to prove that the sender sent the recipient in a way decryptable by their advertised public key, an encrypted value which matches the (non-decryptable) second encryption.  eg if you look at Brands is a more complicate version but there are a few survey papers showing all the common things you can easily prove using schnorr variants.

ie so prove that the plaintext under the encryption would result in the recipient knowing a value that would allow it to spend the coin.  in your labelling make a schnorr-related proof that y=y' and r=r'.

I did think of this going back a few weeks in my comments on your original scheme but maybe neglected to say it.

Adam

The EDH idea seems not bad.  Have to check the math but that sounds like it should be possible to make work.


Yeah imagine armory usb, and other limited comms mechanisms: at hardware or human interactive level these can be basically untenable with a 4-move protocol.  Worth working hard to make that a 2-move protocol.


State is a bit risky, hard to make cheap devices storage database transactional, where each nonce is used 0 or 1 times maximum.

Adam

[The url is b0rken for the additively homomorphic Elgamal variant you mentioned.  Should be http://ecewp.ece.wpi.edu/wordpress/crypto/files/2012/10/main.pdf]

Their additive Elgamal variant seems interesting, but I am not sure why you need it to be simultaneously decryptable and additive: instead you can have additive simply with vG+xH for two EC bases G and G, value v, and random value x, and presuming the owner knows his own decryption, he can do the addition, and communicate the value & new x value to the recipient using ECIES or normal Elgamal?

Adam

You're referring to another scheme committed transactions http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02184.html and detail on https://bitcointalk.org/index.php?topic=206303.msg2157994#msg2157994, your description is correct.  

There is an unsolved problem with it though - how to prevent hostile miners censoring the keys instead (by pretending they never saw them)... there needs to be a second stage validation to say ok, this is the disclosed key and the signatures are good & values add up.  You cant directly impose consensus on not disclosing that because it creates a DoS risk - that someone really doesnt reveal the key at all, or keeps it to themselves, like a selfish-mining type of attack.

The homomorphic encrypted transaction values is different, just encrypting the value.  So the payments are still as traceable as without them, just the values are hidden from the miners and from the ledger.  Miners and anyone else can still verify that the amounts add up, just they cant tell how much they actually are.

Adam

public key encryption can do that fine, and the user has key(s) to control coins or balances.


As far as I can see this is all (including the matrix proofs) modulo n the order of the curve (or p the field).  Consider if I prove balance a == a'+b+t where t is the transaction fee, a is alice's initial balance, a' alice's revised balance and b bob's additional balance.  

Alice and Bob can collude to create instead a' > a eg say n = 13 then the honest version is t=1, a=6, a'=3, b=2 (6=3+2+1)
but a dishonest version is t=1, a=6, a'=11,b=7 and 6=11+7+1 mod 13 = 19 mod 13 = 6.  So Alice and Bob can add n to their balance and the ZKP still passes.

Adam

I agree, the values seem to wrap rendering the scheme insecure unless I'm missing something about the ZK matrix additions - those are also modulo one of the fields right?

What Greg said re Elgamal is how I did it in this homomorphic value scheme https://bitcointalk.org/index.php?topic=305791.msg3294618#msg3294618 note use of Berry Schoemakers ZK range proof to prove the values dont wrap.  It ends up being basically a pedersen commitment because you dont need to be able to encrypt, just verify.  The sender can send the Pedersen nonce to the recipient so the recipient can see how much he received and be in a position to respend it.

I would personally prefer to avoid adding the Paillier security assumptions, while they seem fairly conservative and reasonable, unless it was necessary.

The hard part is the ZK range proof (aka ZK less than) - that is where the largest part of the verification cost and worse, the coin size comes from.  As you see on the above link it comes to 1KB per value.  I am not sure that would actually be worse than this scheme because for 128-bit security with Paillier you need 3kbit keys and 6kbit ciphertexts.

Adam

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

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

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