Coinbase TxOut Hashcash and off-chain, anonymous, probabalistic, micro-payments

adam3us

sr. member

Activity: 404

Merit: 362

in bitcoin we trust

Quote from: mmeijeri on May 11, 2013, 05:37:17 AM

So do you think there is still a role for hashcash as a separate (pseudo-)currency, albeit a merge-mined one, rather than using a hashcash-derived system with BTC postage?

Well its not really a separate pseudo-currency, because it not spendable, nor respendable by the recipient - its basically emailing failed direct mined shares with the extraNonce containing the recipients email address as an offline verifiable proof to convince the email recipient that you tried for 10 seconds (or whatever) to mine a coin for them.

Very infrequently someone will actually win $3000 (25*$120) as a result of this - when the lottery ticket wins.

Adam

Zeilap

full member

Activity: 154

Merit: 100

1) "Re: [Bitcoin-development] Discovery/addr packets (was: Service bits
for pruned nodes)" - 2013-06-06 - Peter Todd -
bitcoin-development email list

All instances of =3D should simply be =.

mmeijeri

hero member

Activity: 714

Merit: 500

Martijn Meijering

So do you think there is still a role for hashcash as a separate (pseudo-)currency, albeit a merge-mined one, rather than using a hashcash-derived system with BTC postage?

adam3us

sr. member

Activity: 404

Merit: 362

in bitcoin we trust

Quote from: mmeijeri on May 11, 2013, 03:42:36 AM

Sorry, I still don't understand what that means.

I didnt quite follow the write up either, but it revolves around bitcoin/hashcash merged mining. Here's my reply from bitcoin-dev:

Quote from: adam3us

I didnt quite understand the writeup and the references were ambiguous.

But if you are talking about bitcoin/hashcash merged mining for email: it is
something I think should possible. Of course for email the scale means
bitcoin style flood-fill and direct tiny payments are completely out of the
question, thats why hashcash itself has no communication overhead other than
a header in the mail - its only scalability limit is email itself.

Rivest's PayWord for people who dont know the reference in this context is
the observation that for a low value micro-payment, you dont mind if you
only receive a payment 1 time in k so long as the expected payment is n
after receiving n (eg satoshi sized) payments. Eg like a penny tip jar so
long as your expected payment is correct long term (win as often as you
lose) you dont mind. And a fair 100% payout lottery can be fun of itself.

So let say each email client sends in an email header the head of the
bitcoin hash chain, it has seen via other emails, which can be offline
verified back to the genesis hash. Maybe some clients even have bitcoin
installed and ask the bitcoin client for the hash chain head. The client
also generates an address on setup, and sends its bitcoin address in a
header. If you send to a new address you dont know their address, so you
send to eg me (Adam;) as a default, or the bitcoin foundation, or an invalid
address to destroy the coin - the recipient assumes that is not the sender
as those address are in the client. A sender can under-contribute but makes
no gain. Under-contributing is fixable if desired (see under-contribute in
amortizable hashcash paper, but using PK decryption with recipients private
key x as its non-interactive b'=D(x,share).)

Then clients merge mine involving the recipients bitcoin address (or one of
the default addresses).

Even if the merged stamp proves to be an orphan, even a very old one, its
valid in a hashcash anti-spam sense, meeting the same purpose as destroyed
coin.

Maybe one can put the bitcoin hash in DNS with a 5min TTL and have mail
clients read that to reduce scope for stale mining.

In this way one can merge mine bitcoin & hashcash to the benefit of the
recipient (or some beneficiary trusted not to be paying the proceeds to the
spammer). And in a way that scales to email scale, and does not involve
installing a bitcoin client in every client, nor mail server.

Adam

mmeijeri

hero member

Activity: 714

Merit: 500

Martijn Meijering

Quote from: Peter Todd on May 11, 2013, 03:32:51 AM

It's two parts: Coinbase TxOut Hashcash and the PowPay system.

Sorry, I still don't understand what that means.

Peter Todd

legendary

Activity: 1120

Merit: 1152

Quote from: mmeijeri on May 11, 2013, 03:27:42 AM

Quote from: Peter Todd on May 11, 2013, 03:13:54 AM

It has been previously(1) proposed that hashcash using the same PoW
function as the Bitcoin block hashing algorithm be used to create
hashcash whose value is denominated in Bitcoins.

What was the goal of that proposal? It reminded me of the idea of using Bitcoin postage for Bitmessage, but in the rest of your post you appear to be talking about something ese.

It's two parts: Coinbase TxOut Hashcash and the PowPay system.

I need a snappy name for the former... proof of work proof of sacrifice, PowPos, is pretty good.

mmeijeri

hero member

Activity: 714

Merit: 500

Martijn Meijering

Quote from: Peter Todd on May 11, 2013, 03:13:54 AM

It has been previously(1) proposed that hashcash using the same PoW
function as the Bitcoin block hashing algorithm be used to create
hashcash whose value is denominated in Bitcoins.

What was the goal of that proposal? It reminded me of the idea of using Bitcoin postage for Bitmessage, but in the rest of your post you appear to be talking about something else.

Peter Todd

legendary

Activity: 1120

Merit: 1152

Reposting http://www.mail-archive.com/[email protected]/msg02159.html

It has been previously(1) proposed that hashcash using the same PoW function as the Bitcoin block hashing algorithm be used to create hashcash whose value is denominated in Bitcoins. This poses two problems however: widespread use of such hashcash would harm overall network security and determining the value of the hashcash requires knowing the revenue miners can gain from transaction fees at a given block height - a non-computable function. However, with some modifications we can extend the idea to directly denominate the hashcash in Bitcoins at the cost of a small increase in proof size. Recall that the fundemental problem is the need to do some work to make digest D have value V, resulting in a proof that can be given to a third party. We want V to be denominated in Bitcoins, and we want the actual economic cost to create P to be as close as possible to the face-value V. Finally should computing P result in a valid Bitcoin block header, the creator of the proof should have a strong incentive to publish their header to the P2P network and extend the current best chain. # Proof structure Lets look at the elements of the proof from the block header to the digest. ## PoW Block Header This must be a valid block header. It is particularly important to ensure that the header can be linked to the actual blockchain, although the header itself does not need to be a part of the chain, and hence the block hash does not need to meet the difficulty requirements. ### Previous Block Headers The proof may optionally include one or more previous block headers in the event that the PoW block header's previous block is an orphan. Unlike the PoW block header, these block headers MUST meet the difficulty requirements although an implementation MAY skip actually checking the difficulty if a difficulty retarget has not happened or the PoW is timestamped. (see below) ## Partial Transaction and Merkle Path The partial transaction consists of a SHA256 midstate followed by exactly one transaction output. The merkle path to the PoW block header MUST prove the transaction was the coinbase transaction and not any other transaction. ## Transaction Output The last transaction output must have a scriptPubKey consisting of exactly one PUSHDATA op which pushes H(D | N) to the stack. Its value, V', is the basis for determining the value of the proof of work. V' must satisfy V' < k*Vi(h) where Vi is the inflation reward for the PoW block height and k < 1 For a number of reasons, including making sure there are strong incentives for broadcasting succesful PoW solutions, the value of k should be chosen fairly conservatively; the author suggests k =3D 1/10 as a ballpark figure. Finally N is some fixed value specific to hashcash of this form to ensure the txout proof can-not be reused. Vi can also be calculated as the median of the last n "anyone-can-spend" outputs seen in coinbases when the value of the inflation reward falls low enough that using the inflation reward is impractical. ## Timestamp If the proof-of-work is used after a difficulty retarget the PoW needs to be timestamped in the block chain with a merkle path leading to a valid block header. The difficulty used for calculating the value of the PoW then becomes the minimum of the difficulties of the PoW previous block and the timestamp. # Determining the actual value of the PoW The proof proves that work was done to find a valid block header. That block header, had it met the difficulty threshhold, could have created a valid block worth at least the inflationary reward Vi(h) to the miner. The coinbase transaction output and merkle path shows that were such a block found, the miner would have then given away V' to whomever managed to create a transaction spending it when the coinbase matured. The coinbase takes 100 block to mature, so the chance of any one miner collecting it is proportional to the hashing power they control.(*) *) As with fidelity bonds we make the assumption that no party controls more than 50% of the hashing power - the assumption underlying Bitcoin's security anyway. If this assumption is proven incorrect or insufficiently strong, possibly due to a cartel of miners banding together to create low-cost PoW's, the output can use the provably unspendable/prunable OP_RETURN scriptPubKey instead with a non-zero value. With P(block hash, target), the expected probability of a valid PoW being found given the work required to create the block hash with the given difficulty target, we can finally calculate the value of the PoW in terms of expected cost: V =3D P(hash, target) * V' # Pool implementation and 51% attack security Because doing the work required to create coinbase txout hashcash is sufficient to also create a valid block a pool can safely rent out hashing power to create hashcash of this form on demand without making it possible to rent large amounts of hashing power directly on short notice. (though some extensions to GetBlockTemplate for hashers verifying it may be required) Because the anyone-can-spend txout is the basis for the value of the hashcash the value remains computable even if transaction fees become a larger proportion of the block reward in the future. Unlike announce-commit sacrificies(2) proofs with very small values can be easily created; the pool operator can make a trade-off between the profit varience - remember that a block header with a valid PoW represents a loss - and latency by adjusting the proof of work difficulty and V'. As an aside, note how the mechanism of a anyone-can-spend txout in a coinbase can replace the announce portion of an announce-commit sacrifice; a coinbase transaction is the only case where a single merkle path proves that the transaction output was possible to spend in a subsequent block, but was not yet spent; also an argument for allowing coinbase transaction inputs. # Application: Paying for additional flood-fill bandwidth Additional messaging applications built on top of the Bitcoin P2P network would be useful, yet there needs to be some general mechanism to make DoS attacks expensive enough that they are impractical. For instance a useful P2P network feature would be a mechanism to propose trust-free coin mixes transaction outputs, propose specific txout sets, and finally a mechanism to broadcast valid ANYONECANPAY signatures so the inputs and outputs can become a valid transaction. By separating the txout and signature broadcasts, who is paying for what output is made very difficult to determine. Of course such a mechanism will likely come under attack by those trying to combat anonymity. However with the coinbase txout hashcash mechanism those attackers are forced to either contribute to the security of the Bitcoin network or incur much higher opporuntity costs for conducting their attack than honest nodes pay. (remember how the choice of k =3D 10 makes for a large ratio of maximum V' value to Vi(h) inflation reward) To reduce amortized proof size one proof can be used for multiple payments with Rivest PayWords and similar techniques. # PowPay - Off-chain, anonymous, probabalistic payments By setting the special txout to a scriptPubKey spendable by the recipient we can prove to a third party that work was done that with probability P(hash,target) could have resulted in a txout spendable by them of value V' Thus the expected value of the payment is V =3D P(h,t)*V' The recipient needs to make the proof non-reusable, either by recording all proofs submitted, or by requiring a nonce in the scriptPubKey: (*) DROP {additional ops} *) Note the implications for the IsStandardInput() test. Because the recipient has no way of knowing how the sender paid to have the hashing done on their behalf the source of the funds is unknown to them. Additionally the payment can be of any amount less than a full block reward, and the time varient between actual payments can be reduced to, in theory, as little as the block interval itself with 100% miner participation. ## Maximum Payment amount Unlike coinbase txout hashcash the maximum value of a PowPay transaction is strictly limited by the inflation reward; the trick of calculating actual cost by prior sacrifices doesn't work because no honest sacrifice is involved. In any case it is desirable for the mechanism to account for a large percentage of total transaction value. The issue is that should a valid block be found either the miner must still have a strong incentive to broadcast that block that can be proven to the recipient, or the miner must not be the one who controls that decision. The latter option is possible by inverting the relationship: now the recipient constructs the block, and the sender simply arranges for a valid PoW to be created - essentially the recipient acts as a mining pool with an extremely high minimum work, and the sender provides hashing power. With the 1MB blocksize the cost to operate the full validating node required is low and attacks on block propagation are difficult to successfully pull off. ### Supporting PowPay volume in excess of inflation reward + tx fees To support overall PowPay volumes that are in excess of the inflation reward and transaction fees the sender can provide the recipient with signed transaction inputs subject to the constraint that only blocks with PoW's generated by the sender can be used to spend them. For instance a nonce in a well-known place can be provided by the sender and included in a modified block header. By modifying the block hashing algorithm so that PoW-withholding is not possible - a significantly more serious problem in this application - the sender still is forced to send all potential solutions to the recipient, including possible winning ones. Provided that attacking block propagation is difficult the sender can't prevent the reciver from spending their transaction inputs. ## Scalability PowPay can provide much greater scalability than Bitcoin itself, in terms of payments per second, however it is still limited in terms of actual fund transfers to recipients per second. A naive implementation would give a actual transfer every ten minutes maximum, and a highly sophisticated solution 7/second. (albeit probably requiring a hardfork to solve PoW withholding and/or use of third parties) At the same time the proofs required become large with an increased blocksize, and in the case of the inverted "recipient builds blocks" mode the recipients either incur large costs running full nodes, or greatly disrupt transaction flow for on-chain users by mining blocks with no transactions in them at all. (remember that a recipient who trusts someone else to construct the blocks for them is trusting that third-party to do so correctly) The latter is especially problematic because as the blocksize is increased a higher percentage of the cost of mining goes to the overhead required to run a validating node, rather than hashing, which has the perverse effect of decreasing the cost of mining blocks with no transactions in them at all. (or transactions that the miner knows have not been revealed to other miners) The analysis of this strange mixed bag of incentives is highly complex. # Paying for mining TxOut HashCash and PayPow both require the sender to somehow get someone to mine on their behalf. The exact nature of these relationships will vary and are beyond the scope of this paper. # Eliminating PoW withholding While the above examples have used economic incentives possible within the existing Bitcoin system a structural incentive is possible as well. A nonce N is chosen by the party paying for the PoW, such as a pool or PowPay recipient, and H(n) is included in the block header.(*) The PoW function is then modified to consider the PoW valid if the sum of the expected hashes required to find H(B) and H(B | n) exceeds the current difficulty target. *) Note how the block header can be extended, while remaining fairly compat= ible with existing ASIC mining hardware, by taking advantage of the fact that ASIC's use the SHA256 midstate at a starting point for their PoW calculations.(3) 1) "Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)" - 2013-06-06 - Peter Todd <[email protected]> - bitcoin-development email list 2) "Purchasing fidelity bonds by provably throwing away bitcoins" - https://bitcointalk.org/index.php?topic=3D134827.0 - Peter Todd 3) "Re: 32 vs 64-bit timestamp fields" - 2013-06-09 - John Dillon <[email protected]> - bitcoin-development email list

Topic: Coinbase TxOut Hashcash and off-chain, anonymous, probabalistic, micro-payments (Read 1990 times)