Discussion:
[Bitcoin-development] Coinbase TxOut Hashcash
(too old to reply)
Peter Todd
2013-05-11 04:53:42 UTC
Permalink
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
= 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 <digest> 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 = 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 = 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 = 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: (*)

<nonce> 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 compatible
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 <***@petertodd.org> -
bitcoin-development email list

2) "Purchasing fidelity bonds by provably throwing away bitcoins" -
https://bitcointalk.org/index.php?topic=134827.0 - Peter Todd

3) "Re: 32 vs 64-bit timestamp fields" - 2013-06-09 - John Dillon
<***@gmail.com> - bitcoin-development email list
--
'peter'[:-1]@petertodd.org
0000000000000039e49118426bbe6739360d35116e920d6502dcacd8e51bc74c
Adam Back
2013-05-11 10:22:09 UTC
Permalink
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 provdes 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
Post by Peter Todd
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
= 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 <digest> 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 = 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 = 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 = 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: (*)
<nonce> 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 compatible
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
bitcoin-development email list
2) "Purchasing fidelity bonds by provably throwing away bitcoins" -
https://bitcointalk.org/index.php?topic=134827.0 - Peter Todd
3) "Re: 32 vs 64-bit timestamp fields" - 2013-06-09 - John Dillon
--
0000000000000039e49118426bbe6739360d35116e920d6502dcacd8e51bc74c
------------------------------------------------------------------------------
Learn Graph Databases - Download FREE O'Reilly Book
"Graph Databases" is the definitive new guide to graph databases and
their applications. This 200-page book is written by three acclaimed
leaders in the field. The early access version is available now.
Download your free book today! http://p.sf.net/sfu/neotech_d2d_may
_______________________________________________
Bitcoin-development mailing list
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
John Dillon
2013-05-13 07:31:21 UTC
Permalink
Post by Adam Back
I didnt quite understand the writeup and the references were ambiguous.
No you didn't. :)

What is special about what Peter is proposing is that it is *not* merge-mining.
You see, merge-mining is essentially where you use one PoW for two purposes,
two different blockchains. So you are getting more value from just one unit of
work.

But Peter's coinbase hashcash protocol carefully ensures that the act of mining
the hashcash is guaranteed to cost the miner at least some well-defined amount,
and that amount can be easily calculated by considering the probability that a
block could have been found with the effort required to generate the proof of
work, and the amount of value the miner would have then given away in a
"anyone-can-spend" output. (you may not realize this, but a scriptPubKey with a
single pushdata opcode is always evaluated as true, which means it can be
respent by anyone)

Don't feel bad though, I had to ask him to explain it to me too. :)
Post by Adam Back
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.
I think you are misremembering. I just checked the paper and PayWord is based
on chains of hashes and you give the receiver a digest and if after n repeated
hashes it is considered to have been worth n*k It is not a probabalistic
scheme.

Incedentally while it is an obvious enough idea, though I didn't see a
reference to it, PayWords can be easily extended with a time-bandwidth
trade-off by using a structure similar to a merkle tree. The roots could be
created from some fixed nonce K and a increaing integer, H(K | n) Then you
would provide a merkle path to the previously agreed upon final digest. So
proof size for your payment would be log(n), and time to check the proof
log(n). Unfortunately setting up the scheme is still 2*n however that only
needs to be done once.
Post by Adam Back
So let say each email client sends in an email header the head of the
I have to respect a man who after all these years is still thinking
about anti-spam for email. :)
Post by Adam Back
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.
Peter actually made a blockchain headers over DNS system, and a blockchain
headers over twitter system as an April fools joke. See
https://twitter.com/blockheaders
Post by Adam Back
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.
Blockchain header data may very well be one of the most widely distributed
single data sets in the history of mankind, and most of its closest cousins are
definitions such as the ASCII table or near definitions like the DNS root
servers. Not something with new data every 10 minutes.
Adam Back
2013-05-13 10:54:08 UTC
Permalink
[with] merge-mining [you get] more value from just one unit of work.
correct.
But Peter's coinbase hashcash protocol carefully ensures [...] the amount
of value the miner would have then given away in a "anyone-can-spend"
output.
I think there are 3 choices:

1. merged-mine (almost zero incremental cost as the bitcoin mining return is
still earned)

2. destroy bitcoin (hash of public key is all 00s so no computible private
key)

3. anyone-can-spend (= first to spend gets coin?)

Surely in 3 if you mine the bitcoin its no particular assurance a you will
do your best to make sure that it is *you* tht spends it, so it devolves to
merged-mine. (Eg delay revealing it for 10 seconds while you broadcast your
spend widely)

Peter talks about value, but the proof only proves cost equal to bitcoin.
Those are not the same thing. And they are so-far non-respendable.

I still dont understand what he was saying. If you do please speakup.


I think potentially a publicly auditable pooled mining protocol would be a
place to start thinking about respendble micropayments. I made a post
on the bitcointalk forum outlining how that could be done:

https://bitcointalk.org/index.php?topic=1976.msg2035637#msg2035637

if you have a publicly auditable pool, where users can prove to each other
outside of the bitcoin transaction log that they contributed a number of
shares to a block, those could be traded somehow. Possibly eg with the pool
keeping a double-spend db. If the payments are low value, people maybe
happy trusting a pool. If the pool cheats, everyone stops using the pool.
You rely on the pool not to spend the backing bitcoin blocks. But it
remains possible for the pool to cashout people who collected enough shares.
Probably you could do that with blinding if desired.
[probabilistic micro-payments]
I think you are misremembering [...] It is not a probabalistic scheme.
You are right I was thinking of Rivest's peppercoin.
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.
Blockchain header data may very well be one of the most widely distributed
single data sets in the history of mankind, and most of its closest cousins are
definitions such as the ASCII table or near definitions like the DNS root
servers. Not something with new data every 10 minutes.
Well there doesnt need to be a one-true-blockchain DNS, though the power to
output a hash at any reasonable rate is a big proportion of the network
power. And the outputs are instantly verifiable, so it forms a kind of
trapdoor hashchain (where the trap door is not a secret but havng a huge
amount of CPU power). And there can and should be many blockchain via DNS.

For namesaces in general another approach other than DHT/flood is numerous
competing hierarchical, heavily cached, but publicly auditable. Cheaters
are shunned. Same effect, more scalable, most people are not cheating most
of the time.

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

Adam
Jeff Garzik
2013-05-13 18:38:15 UTC
Permalink
Post by Adam Back
[with] merge-mining [you get] more value from just one unit of work.
correct.
But Peter's coinbase hashcash protocol carefully ensures [...] the amount
of value the miner would have then given away in a "anyone-can-spend"
output.
1. merged-mine (almost zero incremental cost as the bitcoin mining return is
still earned)
2. destroy bitcoin (hash of public key is all 00s so no computible private
key)
3. anyone-can-spend (= first to spend gets coin?)
Don't forget: 4. destroy-via-miner-fee, which is useful because it
provides funding for a public service (bitcoin transaction
verification).

(a tangent, but related)

I've been thinking about a decentralized way to create an anonymous
identity, something I think it key to any number of decentralized, P2P
and anonymous markets. My main focus, for this identity project, is
to develop a decentralized protocol for generating a UUID-like unique
identifier (bitstring), in a way that has some amount of creation cost
attached (to prevent creating a billion of such tokens etc.). I call
it a system identifier, or SIN.

Once you have a SIN, you may associate the SIN with a GPG fingerprint,
email address, real name, login credentials, etc. eBay-like
marketplaces publish SIN ratings (though it displays on screen as
"jgarzik" not "1234-abcd-5678-def0"). Standard-and-Poors style
ratings agencies would similarly rate a business's SIN. SIN's build a
reputation and trust over time, while controlling their own anonymity
(or lack thereof). Anybody may abandon a SIN at any time. Ownership
of a SIN is cryptographically proven via digital signature.

Getting back on topic, somewhat, one idea I had for creation cost of a
SIN was associating the creation cost of a SIN with a bitcoin
transaction's miner fee. Anybody in the world could, therefore,
create a SIN in a decentralized fashion, simply by following a
published protocol for burning a specified amount of bitcoins via
miner fee. It can be cryptographically proven with 100% certainty who
made such a transaction, and the miner fee attaches a creation cost to
ensure that SINs are not -too- cheap.

Burn-via-miner-fee is a useful tool outside of this example. It funds
a public service, providing a positive feedback loop for miners who
receive fees via such services.
--
Jeff Garzik
exMULTI, Inc.
***@exmulti.com
Adam Back
2013-05-13 21:12:44 UTC
Permalink
Some musings about the differences between Peter's proof-of-sacrifice (you
did the work but elected to make the small reward chance unclaimable), vs
conventional actually doing the work but then destroying the bitcoin!

- proof-of-sacrifice seems similiar to hashcash except its difficulty is
time stamped and measured against the bitcoins dynamic difficulty,
(coordinated inflation control being something posited but never
implemented in hashcash). So thats kind of interesting, particularly if
you can do it with very low bandwidth, and decentralized; unclear.

- with proof-of-sacrifice its more offline because you do not need an on
block-chain double spend protection (via flood-fill, validation, and block
chain mining) because it is simply "unspendable", though you could show
the same proof to multiple people. In any case the values are far too low
to spam the block chain with.

- because proof-of-sacrifice is small you can afford to mine them on the
spot and make them payable to the identity of the recipient, like cheques:
they identify the recipient, so they are automaticaly non-respendable in
the eyes of the recipient (he keeps his own double-spend db, and people
wont accept cheques made payabe to other people). This is how hashcash
works for email. Also a time-stamp ensures you dont even need a big
double-spend db, as you can prune it if you reject expired cheqes.

- you could give a proof-of-sacrifice a private key, just like bitcoins;
then they could be pre-mined and identity or other info could be signed
later. However then you have double spending issues again. You can

- I mentioned amortizable hashcash under-contribution feature you can make
it so the recipient uncovers the actual value of the coin (if it is
merge-mined). (Put recipient public key in coinbase, hash for min share
size eg 32-bits leading 0s call that "collision"; send to recipient, he
decrypts the hash with private key, so the decryption is verifiable with
public key. Then the full value of the coin is
zerobit( collision ) + zerobits( decrypt( collision ) )
if that alternate validation was allowed in bitcoin.

- what about if a pool could lock the reward (rather than receive it or
destroy it) eg some kind of merkle root instead of a public key hash in
the reward recipient address field in the coinbase. Then the miners who
created that block have actual share proofs that are claims against
something eventually redeemable. Maybe if they collect enough
share-proofs to reach a minimum bitcoin transaction size, they can redeem
a big strip of shares for a few mBTC, but claims below that are rejected
by the network due to tx fee. (btw I think it seems possible to have a
publicly auditable pool so it cant skim nor disclaim shares.)
Post by Jeff Garzik
I've been thinking about a decentralized way to create an anonymous
identity, something I think it key to any number of decentralized, P2P
and anonymous markets.
There were some systems that charged hashcash for pseudonyms i2p names (i2p
is a ToR like system)... see htp://www.i2p2.e/naming.html then there was of
course namecoin. There was some remailer/email nymserver integration as
well.
Post by Jeff Garzik
Getting back on topic, somewhat, one idea I had for creation cost of a
SIN was associating the creation cost of a SIN with a bitcoin
transaction's miner fee. Anybody in the world could, therefore,
create a SIN in a decentralized fashion, simply by following a
published protocol for burning a specified amount of bitcoins via
miner fee. It can be cryptographically proven with 100% certainty who
Yes it seems that having a proof-of-sacrifice that hardens the block chain
is the important part.
Post by Jeff Garzik
Don't forget: 4. destroy-via-miner-fee, which is useful because it
provides funding for a public service (bitcoin transaction
verification).
Is that directly possible? Because the reward transaction has no source,
and no fee? Or can you put a 25BTC fee in the reward transaction in the
coinbase?

If so that seems like the best option for proof-of-sacrifice rather than
proving destroying the possibility of reward. But alternatively the bitcoin
foundation as recipient, or EFF etc. 25BTC is a big reward might have some
double roll-over lottery effects - everyone piles in for the occasional
25BTC!

Adam
Post by Jeff Garzik
Post by Adam Back
[with] merge-mining [you get] more value from just one unit of work.
correct.
But Peter's coinbase hashcash protocol carefully ensures [...] the amount
of value the miner would have then given away in a "anyone-can-spend"
output.
1. merged-mine (almost zero incremental cost as the bitcoin mining return is
still earned)
2. destroy bitcoin (hash of public key is all 00s so no computible private
key)
3. anyone-can-spend (= first to spend gets coin?)
Don't forget: 4. destroy-via-miner-fee, which is useful because it
provides funding for a public service (bitcoin transaction
verification).
(a tangent, but related)
I've been thinking about a decentralized way to create an anonymous
identity, something I think it key to any number of decentralized, P2P
and anonymous markets. My main focus, for this identity project, is
to develop a decentralized protocol for generating a UUID-like unique
identifier (bitstring), in a way that has some amount of creation cost
attached (to prevent creating a billion of such tokens etc.). I call
it a system identifier, or SIN.
Once you have a SIN, you may associate the SIN with a GPG fingerprint,
email address, real name, login credentials, etc. eBay-like
marketplaces publish SIN ratings (though it displays on screen as
"jgarzik" not "1234-abcd-5678-def0"). Standard-and-Poors style
ratings agencies would similarly rate a business's SIN. SIN's build a
reputation and trust over time, while controlling their own anonymity
(or lack thereof). Anybody may abandon a SIN at any time. Ownership
of a SIN is cryptographically proven via digital signature.
Getting back on topic, somewhat, one idea I had for creation cost of a
SIN was associating the creation cost of a SIN with a bitcoin
transaction's miner fee. Anybody in the world could, therefore,
create a SIN in a decentralized fashion, simply by following a
published protocol for burning a specified amount of bitcoins via
miner fee. It can be cryptographically proven with 100% certainty who
made such a transaction, and the miner fee attaches a creation cost to
ensure that SINs are not -too- cheap.
Burn-via-miner-fee is a useful tool outside of this example. It funds
a public service, providing a positive feedback loop for miners who
receive fees via such services.
--
Jeff Garzik
exMULTI, Inc.
Jeff Garzik
2013-05-13 22:00:27 UTC
Permalink
Post by Adam Back
Post by Jeff Garzik
Don't forget: 4. destroy-via-miner-fee, which is useful because it
provides funding for a public service (bitcoin transaction
verification).
Is that directly possible? Because the reward transaction has no source,
and no fee? Or can you put a 25BTC fee in the reward transaction in the
coinbase?
When a transaction's input value exceeds its output value, the
remainder is the transaction fee. The miner's reward for processing
transactions is the 25 BTC initial currency distribution + the sum of
all per-transaction fees. A destroy-by-miner fee transaction is a
normal bitcoin transaction sent by any user, that might look like

Input 1: 1.0 BTC
Output 1: 0.5 BTC

(the miner fee is implicitly 0.5 BTC, paid to whomever mines the
transaction into a block)

Sadly the bitcoin protocol prevents zero-output,
give-it-all-to-the-miner transactions.
--
Jeff Garzik
exMULTI, Inc.
***@exmulti.com
Adam Back
2013-05-14 09:25:07 UTC
Permalink
Post by Jeff Garzik
When a transaction's input value exceeds its output value, the
remainder is the transaction fee. The miner's reward for processing
transactions is the 25 BTC initial currency distribution + the sum of
all per-transaction fees. A destroy-by-miner fee transaction is a
normal bitcoin transaction sent by any user, that might look like
Input 1: 1.0 BTC
Output 1: 0.5 BTC
(the miner fee is implicitly 0.5 BTC, paid to whomever mines the
transaction into a block)
Sadly the bitcoin protocol prevents zero-output,
give-it-all-to-the-miner transactions.
Well if it is a later transaction, not an integral part of the reward
transaction (that is definitionally mined by being serialized into the
coinbase), the user may elect to withhold the promised transaction
give-to-miner, so thats not so good.

Or do you mean to say you could have (implicit reward 25BTC) and reward
transaction .001 BTC to self and 24.999 BTC with existing bitcoin format and
validation semantics? That would be close enough to give-to-miner. Also
the output sum > 0BTC limitation could be changed to >= maybe... (just one
well placed character :)

Adam
Jeff Garzik
2013-05-14 16:50:27 UTC
Permalink
Post by Adam Back
Post by Jeff Garzik
When a transaction's input value exceeds its output value, the
remainder is the transaction fee. The miner's reward for processing
transactions is the 25 BTC initial currency distribution + the sum of
all per-transaction fees. A destroy-by-miner fee transaction is a
normal bitcoin transaction sent by any user, that might look like
Input 1: 1.0 BTC
Output 1: 0.5 BTC
(the miner fee is implicitly 0.5 BTC, paid to whomever mines the
transaction into a block)
Sadly the bitcoin protocol prevents zero-output,
give-it-all-to-the-miner transactions.
Well if it is a later transaction, not an integral part of the reward
transaction (that is definitionally mined by being serialized into the
coinbase), the user may elect to withhold the promised transaction
give-to-miner, so thats not so good.
That evaluation largely depends on the needs of the service in question.

In my decentralized identity (SIN) example, you merely need to prove
to the cloud that you sacrificed some bitcoins to any-miner. The
confirmed, in-chain, non-coinbase transaction becomes the root node
for off-chain identity data.

The penalty for the user withholding the sacrifice transaction is that
their SIN is not created. That incentive may not exist in that way,
in another service.
Post by Adam Back
Or do you mean to say you could have (implicit reward 25BTC) and reward
transaction .001 BTC to self and 24.999 BTC with existing bitcoin format and
validation semantics? That would be close enough to give-to-miner. Also
the output sum > 0BTC limitation could be changed to >= maybe... (just one
well placed character :)
Just referring to a standard, fee-bearing, user-created bitcoin
transaction, where output_value < input_value. The fee is paid to the
first miner who includes that transaction in a block, as part of the
protocol.
--
Jeff Garzik
exMULTI, Inc.
***@exmulti.com
Adam Back
2013-05-14 20:07:31 UTC
Permalink
Post by Jeff Garzik
Post by Adam Back
Well if it is a later transaction, not an integral part of the reward
transaction (that is definitionally mined by being serialized into the
coinbase), the user may elect to withhold the promised transaction
give-to-miner, so thats not so good. [...]
[...]
Just referring to a standard, fee-bearing, user-created bitcoin
transaction, where output_value < input_value. The fee is paid to the
first miner who includes that transaction in a block, as part of the
protocol.
Yes but thats inferior in the sense that it is spamming the bitcoin payment
protocol slightly, to the small reward of miners, and involves actual money
and traceability to real-name (where did you get the coin from to spend).

If alternatively you just proof you direct mined on a block with a coinbase
that immediately makes payment to future miners its better because: a) you
can do that with no new traffic for the bitcoin network (except when you
mine a whole block, you'll post it); and b) anyone with a reasonable
verification on the blockchain head (even if the spender has to give it to
them!) can verify it without any other network traffic; and c) if its
micro-mined on the spot it can be bound to the service whereas if you give
it to fees as an on network transaction you are limited to values above the
min tx fee.

So idealy I think you need to be able to simultanously mine and give reward
to future block miners.

What you could do with out that is d) mine for the reward of bitcoin
foundation/software author/or service provider. In the last case (service
provider) its an extreme form of Rivests peppercoin probabilistic payment

Adam

John Dillon
2013-05-14 02:30:18 UTC
Permalink
Post by Adam Back
- what about if a pool could lock the reward (rather than receive it or
destroy it) eg some kind of merkle root instead of a public key hash in
the reward recipient address field in the coinbase.
Sorry I don't have time for a full reply due to some other commitments, but you
remind me of an idea bouncing around to use a Merkle Sum tree as a way to split
one sacrifice among an arbitrarily large set of users. Credit goes to Gregory
Maxwell (according to the wiki) and the idea is to have the roots of the tree
be account "numbers" (pubkeys here) and account amounts. He proposed it for
off-chain transaction account ledgers, but the idea works equally well here to
split some initial sacrifice into lots of little bits. For instance a on-chain
sacrifice to an anyone-can-pay output could be split into enough parts to make
it useful even when tx fees become large.

Incidentally all this stuff about rivest paywords is probably silly, why not
just commit your sacrifice to a pubkey and make signatures saying what your new
balance is for each message and how much you intended to spend? This allows for
easy fraud proof creation, and gives you a choice of either lying to some
nodes, and getting poor propagation, or being honest and spending the amount
you should have.

For DoS protection it seems to me that mostly trusting nodes to give accurate
balances, enforced with a fraud proof system to halt double-spending, is
perfectly adequate. But no sense implementing so much complexity right at the
start of the effort! Just a thought for where things can go in the future.
Mike Hearn
2013-05-14 17:25:36 UTC
Permalink
Post by Jeff Garzik
I've been thinking about a decentralized way to create an anonymous
identity
This is the fidelity bond/anonymous passport idea that has been kicked
around in the forums quite a few times. I mentioned it on the tor-talk once
as a solution to the problem that you cannot create Google accounts via Tor
without a phone number. It's a good idea but not new. I have encouraged
people to implement a server that does it and then some integration for
MediaWiki, Wordpress or phpBB, as they're both quite common software that
gets a lot of spam and abuse. For instance we could use it on our own wiki
instead of paying the wiki operator (does anyone know what happens to those
funds by the way?).

You don't need GPG or anything like that - the transactions that spend to
fees also contain pubkeys in the inputs, which you own the private keys
for. So you can sign a challenge nonce from the server to prove ownership
of the "passport"/fidelity bond.
Continue reading on narkive:
Loading...