amortizable hashcash & zero-trust poolfree

[adam3us]

Hi Bitcoiners

A few topics:

1. amortizable hashcash and zero-trust bitcoin pooling

It occurs to me that my 2002 paper on "amortizable hashcash" could be used to make zero-trust bitcoin pooling possible.

http://hashcash.org/papers/amortizable.pdf

While pools are held honest  by reputation, always smart contracts and cryptography and end to end self-determinable security are preferable to gameable reputation, particularly where the cheating is only detectable in the long run, and the pool could skim based on non-transparent statistics.  How do you know what the real pool statistics are.  From their stats page?  Etc I'm sure others have worked through the possibilities.  Maybe some pools are skimming right now above their advertised commissions, and could perhaps get away with that for months.  Possibly even the largest pools.  Eventually the stats add up, but who is doing the manual statistical auditing back to the blockchain?  No one probably.

Amortizable hashcash (my later 2002 variation following on from hashcash) means that you could mine two hashcash microcoins (corresponding approximately to the pool "share" microcoin but directly ownable by the individual miner without possibility for cheating, skimming etc by the pool), and the amortization function is that you yourself can add them together offline by yourself, with the resulting coin having a fixed modest size regardless of how many coins you added together and have anyone publicly audit and accept that resulting coin.  The pool has no trap door, no computational advantage arising, so you dont have to trust the pool at all.


No change to the core mining function is necessary, as amortizable hashcash is still based on the same mining function (which I used to call a hashcash cost function - others later called them proof-of-work functions) so it works on ASICs and GPUs etc though some minor changes would be needed in the serialization of what gets hashed and the definition of the value of coins.  Well thats the idea, the crypto is sitting there and a good hacker could put that together in a few days IMO. 

(To elaborate for clarity, the serialization and definition changes I mean each microcoin would hash its owners coin address as part its self-chosen challenge.  If the pool uses the clients hash - and it has an incentive to if it wants to win the pending 10 minute full-sized coin strip, and collect the bounty - then the pool contributor unavoidably gets the microcoin.  The pools reward can be encoded also as a smart contract into the format so that if the pool is due the tx fees but not a coin share (like eligious fee structure) or a percent that can be in the smart contract.)

So there's the brain dump, do with the suggestion as you wish.  Alt-coiners might like it.  Bitcoin itself maybe has more energy right now for scalability engineering.  But thats part of the value of alt-coiners -- innovation jumping ahead in different directions.


2. pool auditing?

Maybe an alt-coiner or a pool contributor with enough at stake might like to audit the main pools and publish their findings.  If pools have been skimming it could lend credibility to an alt-coin that uses amortizable hashcash and fair micro smart contracts based pooled mining.

Its not an accusation btw from what I saw the pools seem to be friendly, and some of the published % fees are fairly steep so maybe they can be profitable enough without entertaining it.  More to lose than gain?  etc.


3. reducing coin mining time variance

Oh yes something else, though I am not sure it is necessary with microcoins as I commented in another thread they are inherently smoothed mining randomness due to their size, but it is also easy to make a much more deterministic mining definition with hashcash.  Just collect more smaller hashes in a list and define the value to be the logsum of the coin values in bits.  The expected work as the same but the variance falls fast.  Juels et al proposed that in their client puzzles paper.  Microsoft also did it in their hashcash mail stamp fork. 

You can optimize the storage size, though obviously they will be bigger than single mining event coins.  In the case of bitcoin the size is mostly dominated by the transaction log so maybe that is a negligible effect.


4. even flatter network (maybe.. proto-thought in progress)

I havent thought about it enough yet, but there might be a way to use amortizable hashcash at the whole network level (I mean the amortizable hashcash protocol itself is 100% scalable)  but use it to somehow benefit the network scalability, and/or even need for pools to exist and yet without spamming the network with microcoin commits.  For example the pool (symmetric) blinding value (you'll have to read the paper to understand what that is) could alternatively be chosen after the fact via a fair beacon based on the network aggregate mining events.  Then the all the micro clients can have a look through candidate microcoins and see if they scored with any of them.  Kind of like lots of little lottery tickets rather than one big lottery ticket.  I do appreciate that all the miners need to either directly validate the anti-double spend properties of the block chain, either directly, or indirectly; and that the miner effectively acts as a super node doing that for users, and charging a fee.  (If the pool fails or cheats on the block chain validation and is well below 50% or exceptionally lucky, he will lose the bounty anyway as everyone else will declare his coin invalid).  Anyway I suppose the main point is the miner doesnt have to wait for a delayed payout nor trust the pool, he has his own coin and can validate it and claim it himself.  But at that stage pool would be doing so little - just sending you the current claimed hash, that perhaps there is a trick that could remove the need for them.  Thats where I havent thought enough yet

Adam

[1714152985]

1714152985

[1714152985]

1714152985

[1714152985]

1714152985

[1714152985]

1714152985

[Zeilap]

There's a lot of shoulds, cans and coulds but no how.

Also, I know that Hashcash is your baby and you're rightly proud of it, but Bitcoin isn't Hashcash and your insistence on crowbarring its terminology into your posts make them all the more difficult to read.

[misterbigg]

There's a lot of shoulds, cans and coulds but no how. Also, I know that Hashcash is your baby and you're rightly proud of it, but Bitcoin isn't Hashcash and your insistence on crowbarring its terminology into your posts make them all the more difficult to read.

We are of the same mind in this.

[TierNolan]

Amortizable hashcash (my later 2002 variation following on from hashcash) means that you could mine two hashcash microcoins (corresponding approximately to the pool "share" microcoin but directly ownable by the individual miner without possibility for cheating, skimming etc by the pool), and the amortization function is that you yourself can add them together offline by yourself, with the resulting coin having a fixed modest size regardless of how many coins you added together and have anyone publicly audit and accept that resulting coin.  The pool has no trap door, no computational advantage arising, so you dont have to trust the pool at all.

So, the pool sends a header with a random miner id embedded, which cannot be changed.  The miner tries to find the nonce that gives the lowest result from the hash function.

You can only submit one share back for the id.  The difficulty can be estimated as 1/(min result)?  This can be done in parallel easily.

If you have the miner submit back the n best nonces instead of the best, then variance is even lower. 

From later in your post, in that case, the work is sum(log(H(...,nonce,...))).  I'll take your work for it, gives a result in bits presumably.

This could be used by p2pool for example in their sharechain.  Is anyone familiar with p2pool, is the higher variance causing miners to reject it?  Maybe pool variance dominates share-chain variance.

(To elaborate for clarity, the serialization and definition changes I mean each microcoin would hash its owners coin address as part its self-chosen challenge.  If the pool uses the clients hash - and it has an incentive to if it wants to win the pending 10 minute full-sized coin strip, and collect the bounty - then the pool contributor unavoidably gets the microcoin. 

This doesn't help with variance, which is the whole point of the pool.  It just shows a list of winners, right?

I made a proposal to allow proving work.  A node submits a claim and then a few blocks later submits proof.  A number of hashes are pseudo-randomly selected based on block chain hashes for the next few block.  The node submits the nonces for those hashes.  The node must submit the proof in order to unlock their id token.  In fact, now that I think about it, they could just include the proof with their next claim.  The id token would just be a proof of work and is reused if they are honest.  The value of the id token must be greater than the probability of being caught times the value of the hash claim. 

[adam3us]

I know that Hashcash is your baby and you're rightly proud of it, but Bitcoin isn't Hashcash and your insistence on crowbarring its terminology into your posts make them all the more difficult to read.

"amortizable hashcash" is the title of the 2002 paper I wrote so some of the terminology comes from that. 
If you read what I just wrote (and I just re-read it to be sure) I did not mix the terminology - except in one place as a slip.   I called hypothetically directly claimable micro (low denominatoin) bitcoins microcoins.  The rest of the terminology is specific to the paper.

I know someone prattling about historic stuff can be irritating, there is one such fellow on the crypto list and it irritates the heck out of me; I am not trying to be obnoxious, really.  My main interest is to help improve bitcoin itself (eg scalability, security, pool security etc) or to have altcoins test or innovate if any of the old things I point out they might have not been aware of.  Sometimes a new person can see a new innovation, that everyone else missed.  (eg an altcoin might see some trick with amortizing coins to achieve a scalability jump that no one including me has thought of - thats how innovations happen).

But yes I know bitcoin isnt hashcash anymore than SHA256 isnt bitcoin.

You also have to understand there is some history to ecash and cryptocurrencies stretching back to David Chaums 1982 paper on blind signatures for untraceable payments.  Some of us got pretty excited about this stuff on the cypherpunks list for a period of years on and off - maybe 1992 - 2005 or something of that range.   Of the aspirations or dreams for what privacy technology could do to improve society ecash was pretty much the holy grail one that was tantalizingly out of reach.  There were even books written about this hunt eg Neal Stephenson's cryptonomicon.  People were talking about ecash for a few decades and excited about the social implications, so that is not new to bitcoin.  So I am not trying to falsely claim any satoshi glory, nor rename anything, but you cant stop me joining the party   Alright.  Otherwise flame on.

Believe me, the fact that Satoshi invented the key missing parts that tantalizingly eluded everyone else for about 20 years is pretty damn cool to me.  It wasnt that we werent trying to figure out how to do this, some of the smartest applied and theoretical crypto people tried their damnest and failed.  So yes bitcoin is the biggest news for a couple of decades in my technical favorite area of interest.

There were prior attempts to control inflation in hashcash.  Otherwise it inflates away at the rate of Moore's law (once it caught up to GPUs then ASICs).  One was to use to broadcast an increased difficulty periodically resetting the number of bits back in line with moore's law (plus a beacon to prevent anticipatory epoch skipping).  The hashcash of this type would have included the epoch beacon and the difficulty in the hashcash service string.  But it would have had no re-spendability, so of use only for anti-DoS and metering applications.  I never implemented it, but the above was discussed on mailing lists as I recall.  Also it would have no supply limitations other than computational resources, but as it was not respendable it was intended as a cost-break on DoS so that didnt matter.

However there was no mathematical enforcement some "trusted" authority would have to estimate and increase the difficulty (eg rate achievable on  equipment costing $1000 every few months).  Wei Dai's B-money and Nick Szabo's bit-gold extended those ideas with respendability and distributed but still based on human markets.  Maybe Szabo envisaged computer mediated markets it was unclear to me.  They all failed to find the elusive deployable pure mathematics/crypto solution without human intervention.  Hal Finney actually built his idea RPOW, and that provided re-spendability and proper blind cryptographic privacy (that bitcoin does not), but it was centralized, and relied on hardware security which has to trust the manufacturer as they are the CAs for the keys involved an could bypass the HW assurance).

I tried to find ways to design an offline ecash system over quite a few years and I failed, most of the discussion is on old crypto lists.  The best I came up with was to find a way to create offline multiply transferable Brands cash.  But it turned out someone already invented it, there was a tiny obscure footnote in his book he pointed me to.

An experiment with controlled scarcity was the digicash (chaum cash) betabucks server.  They issued some number of coins and I think you could just go claim them.  As they were in limited supply people started trading them.  I sold a few perl-rsa t-shirts for beta-bucks.  Blind ecash, fixed supply, but central; and it went under when digicash did!

Adam

[TierNolan]

I called hypothetically directly claimable micro (low denominatoin) bitcoins microcoins.  The rest of the terminology is specific to the paper.

Hmm, so the difficulty would determine the exchange rate between proof of work and bitcoins.  Other than that you can use the proof directly as a transaction input?

An alt chain like that could have POW determined by all the transactions in the block.  The difficulty re-targetting could happen after a certain amount of work was done and updated based on the timestamp between snapshots.

One of the advantages of the blockchain is that you can check the proof of work for the entire block by just looking at the header.  Dropping a transaction doesn't reduce it.

At 1MB per transactions, you need to constantly download 1MB every 10 mins.  Increasing that requires more bandwidth per full node.

[adam3us]

So, the pool sends a header with a random miner id embedded, which cannot be changed.  The miner tries to find the nonce that gives the lowest result from the hash function.

Sorry that part was unclear, what I had in mind was the pool would send a header with a random number embedded, the miner himself would append his bitcoin address to it, and then mine that.  There would be a new (alt) bitcoin coin format which would include multiple hashcash outputs, eg say 100 outputs.  That means that the first 100 or so (not an exact number mind as bitcoins have different values) first 100 or so miners of the pool to hit the minimum share difficulty get their part bitcoins added up by the pool, and the pool publishes the bitcoin.

I think my idea was a bit half-baked.   Apart from that lack of clarity, there are two aspects of the amortizable hashcash concept - being able to add them (very approximately) and a metering function.  Its probably the case that the metering function which requires under/over contribution prevention is irrelevant for pool related use, everyone wants to over-contribute, and thats encouraged.  So lets say we remove the contribution protection (ie blinding value and u part).  Then whats left?  Just an alt bitcoin formed of a list of part-bitcoins, which has lower variance, and the owners of the parts can be different owners.  The pool cant benefit from its miners work without revealing their coin addresses, so the pool cant skim.  The downside is the coin gets bigger.  However I do not think that initial mining events form a big part of the network traffic - isnt the transaction log the big deal, with all the fractional bitcoin change and combining?

The difficulty can be estimated as 1/(min result)?  This can be done in parallel easily.

Correct the pool would set some minimum work factor to limit the network traffic from miners sending it part-bitcoins.  I work in log2 of difficulty because thats the way hashcash was expressed, I think it clearer to think about really.  The log difficulty right now is 55.1 bits (logdiff = log2( difficulty ) + 32 is the bitcoin formula its easy to see the difficulty visually in the hashes eg http://blockexplorer.com/block/00000000000000bf11ad375a87a5670571ee432fbf629ba0e69e33860461bf84 then by counting leading 0s and multiplying by 4 bits per nibble - yes its 56 bit - you get lucky with an extra bit 1/2 time and two extra 1/4 time etc.)

In this idea the pool is mainly saving the miners the network overhead of keeping up with the transaction log traffic, otherwise they could just post their part-coins to the p2p network directly.  Alternatively miners could broadcast their coins if they preferred.  eg the whole network in a p2p sense could grab the first set of broadcast part-coins that added up to the current difficulty and hash them into the transaction log.  In that way your part-bitcoins could go straight to the network bypassing the pool.  Because the part-bitcoins are smaller and released faster that may create some micro forks, but perhaps the p2p voting can handle that.

If you have the miner submit back the n best nonces instead of the best, then variance is even lower. 

You got it -  could have the part-bitcoins themselves be composed of even smaller subpart-bitcoins (eg 32 of them) and then the miner has lower variance, and actually can measure progress, even print a progress bar that means something.  (With single hash bitcoin mining there is no progress as they are like trying to toss 55 tails in a row with a coin - the coin has no memory).

Then while eg 1/128 of the difficulty is massive for most miners, the variance for mining is reduced, which is part of the miners problem.  eg Say 128-part coins = 7 bits, which would make a mining share 48 bits (thats huge even for a 1500MH gpu even it would only have a 1/436 chance of creating a valid share in 10 mins - thats not good because no share = no direct payout).

(To elaborate for clarity, the serialization and definition changes I mean each microcoin would hash its owners coin address as part its self-chosen challenge.  If the pool uses the clients hash - and it has an incentive to if it wants to win the pending 10 minute full-sized coin strip, and collect the bounty - then the pool contributor unavoidably gets the microcoin. 

This doesn't help with variance, which is the whole point of the pool.  It just shows a list of winners, right?

Correct.  However you could use it recursively to have the miner create subpart-coins but each time you increase the number of parts the coins grow.

But I think there maybe a potential problem with multi-part coin low variance concept, imagine the extreme case where there are 1million part-coins, now there is practically NO variance; its almost completely deterministic and 100% related to your CPU power.  Now the guy with the biggest GPU/ASIC farm is going to get the coin 100% of the time - for hashcash stamp anti-DoS that determinism is good, but for bitcoin however with its 10min lottery thats very bad - winner takes all with almost complete certainty.  Even with modest numbers of part-coins the effect exists and stacks the reward in favor of the biggest CPU players, arguably the opposite of what you need if anything (in terms of centralization resistance).  If its recursive with first 100 part-bitcoins past the post sharing the 25 bitcoins, with low variance part-bitcoins in the race (themselves made of subpart-bitcoins) you still have the same issue, fastest CPUs win.

A loose analogy imagine currently bitcoin miners are race cars.  Some are fast (ferrari) and some are slow (citroen 2cv) but they are all very very unreliable.  So who wins the race?  The ferrari mostly, but the 2cv still has a fair chance relative to its speed because the ferrari is really likely to break down.  With low variance coins, you have well maintained cars, and they very rarely break down.  So the ferrari wins almost always.  Now if you have a line of 20 cars of varying speeds, well maintained (low variance) the first 5 that are going to get past the post are almost certainly going to be the 5 fastest.  No one else stands a chance hardly.

So I think the take away is you cant use low variance techniques for the underlying coins in any first (or top 10 etc) past the post race, which is what bitcoin 10min CPU lottery is in effect, because it is inherently unfairly stacked in favor of the fastest CPUs.

Thats kind of inconvenient and as you noted the only other variance reduction method discussed (that I saw) has been to reduce the difficulty (unpooled) or the share size (pooled).  But that can increase bandwith requirements because there are lots of small coins flow up to the pool, or if direct to the whole network.

I made a proposal to allow proving work.  A node submits a claim and then a few blocks later submits proof.  A number of hashes are pseudo-randomly selected based on block chain hashes for the next few block.  The node submits the nonces for those hashes.  The node must submit the proof in order to unlock their id token.  In fact, now that I think about it, they could just include the proof with their next claim.  The id token would just be a proof of work and is reused if they are honest.  The value of the id token must be greater than the probability of being caught times the value of the hash claim. 

I think I have to read about p2pool before I can understand what you wrote on that thread.  It sounds like you plan a bit commitment to be later revealed.

This might be the same as what you meant but I was thinking about coin compactness and maybe it works for pools too that you could demand from the pool a hash including the main bitcoin transaction log hash plus the merkle hash tree of miner coin addresses using the pool, plus a log( #shares ) hash chain proof to the miner that his address is in the tree.  That would seem to allow proof of contribution, however the generated bitcoin would be quite big as it would need to include ALL of the shares, but spends of the bitcoin would be compact just referencing the offset of their address in the generation coin.  Alternatively the generated bitcoin could be compact, and the miner could be responsible to disclose the claim to the bitcoin at time of first use, which would bloat spends, and I believe thats worse because coins get created once but spent many times.

(And now I need to go read p2pool and then your other post.  So much to catchup on!)

Adam

[TierNolan]

I think I have to read about p2pool before I can understand what you wrote on that thread.  It sounds like you plan a bit commitment to be later revealed.

P2pool creates a "share-chain".  The difficulty is dropped so that a new "block" is found every 10 seconds.  If you win a link on the share-chain, you get a share in all p2pool winnings for a while.  If the header is valid for the main chain, you submit it.  A link in the share chain has to pay out according to the p2pool rules to be accepted.

They remember the ledger for 24 hours.  The addresses with the highest debt from the pool are paid first down to a dust limit.  My understanding is that a random selection of the addresses that fall off the chain are paid a fixed amount, so the expected value is what they are owned.  That brings back in variance, but it would be lower than if they were targeting a full block.

However, even 10 seconds is a pretty high target for small miners.  Having said that, I don't know if that is something they get complaints about.

The advantage of a parallel chain like that is that you can modify the rules for the chain.

I believe thats worse because coins get created once but spent many times.

No coins are always destroyed and then new coins are created.  Technically, a transaction consumes transaction outputs and creates new transaction outputs.

If anything bloat on spend is better than block on creation.  The reason is that spend bloat may not happen if the coin ends up lost.  This would be important if there were lots of small payments.