File Detail
Summary
text/markdown; charset=utf-8
A Protocol for Buying and Selling Proof-of-Work Embedded in Bitcoin Script
Daniel Krawisz - Chief Scientist, MatterPool Inc.
Contributors: Attila Aros, Dean Little, Josh Petty, Harrison Beckerich.
Document version 2.0.0
This paper describes a protocol whereby Bitcoin users can buy proof-of-work from miners by creating an output that miners can redeem with a nonce. The transaction can be used to verify that work was done. There are many applications to proof-of-work in Bitcoin beyond creating block headers[^1]. Value in Bitcoin is realized by superior cooperation. People in Bitcoin need to be able to communicate value to one another reliably. The Handicap Principle[^2][^3] says that the only reliable signal that can be transmitted over an adversarial channel is one that demonstrates opportunity cost. Proof-of-work is the most reliable way of ensuring that bad ideas die quickly. Bitcoin miners can increase their income by selling proof-of-work to Bitcoiners. This paper describes a protocol by which a Bitcoin user can create an output with a bounty in it for doing proof of work. This is called a Boost output. The script of a Boost output verifies that work has been done in a way that is compatible with the existing Hash256 (double SHA256) infrastructure. Providing such a service will make the Bitcoin economy more productive because less time and energy will be wasted on bad ideas.
Money is a way for people to cooperate. In order to increase the value of Bitcoin, Bitcoiners must cooperate better than other people. Hence, Bitcoiners have a need to find valuable information among a greater supply than they can process.
The Byzantine Generals Problem is that of a network of independent actors all arriving at a permanent state of agreement from an initially undetermined state.[^4] Bitcoiners can do this with every transaction they make and can create information. Each Bitcoiner can generate lots of information that is potentially viewed by all other Bitcoiners. It is unfeasible for most people to analyze all of it. Eventually it will be unfeasible for anyone. Bitcoiners face the problem of determining which information is relevant. With the large amount of data that Bitcoin has made accessible, there is not yet a reliable way for users to sift through it easily.
Suppose that a Bitcoiner has written open-source code that is useful or has opened a new service that people would want or has written a blog post that contains important information. How does one break through the noise of pumpers, traders, con artists, and anyone else who wants to attract all the attention?
At any given time, proof-of-work is proportional to spent energy. Proof-of-work is an application of the Handicap Principle. Therefore, it can be used by Bitcoiners to find relevant information. In addition to finding the latest block header, Bitcoiners can use proof of work to direct one another to important information within a block.
Proof-of-work requires generators of information to assess its value to other people. The better that people can assess their information, the better value they will receive for the energy spent doing proof-of-work. People who assess their information poorly will either receive too little attention or spend too much energy. People who organize information by proof-of-work will tend to pay more attention to better information. Proof-of-work limits information by creating an honest contest for attention. It is rational to pay more attention to relative winners in the proof-of-work contest because people with super knowledge are more likely to be able to have extra energy to spend.
Proof-of-work does not mean that any particular message is inherently superior. The use of proof-of-work makes destructive ideas riskier. It is still possible to say anything, no matter how horrible or stupid. Someone who chooses to use proof-of-work is deliberately choosing to be riskier than necessary. That does not mean his idea is good. It simply means that if his idea is not good, then he has spent energy that he cannot get back. Someone who would rather do that than stay quiet is either someone who has correctly assessed the value of his idea or someone who will run out of energy more quickly than he would have otherwise.
People who voluntarily choose to pay more attention to messages with more proof-of-work will tend to have better information because people who would otherwise be spreading stupid ideas would be more likely to have no energy. This does not relieve anyone of the job of assessing the value of information. It simply means that everyone will in general find more relevant information among that which they see.
It is possible to create a transaction output that is redeemed by proof-of-work identical to that which is already used to mine blocks. Existing ASIC machines can be used to apply proof-of-work to information a user desires. A miner who identifies such an output can choose to attempt to redeem the output rather than mine the next block. Whether this is a good value proposition and how much hashpower to assign to it depends on how many bitcoins are locked in the output.
Proof-of-work was originally proposed by Adam Back in HashCash[^5][^6] as a generalized spam filter. In the context of email, a difficulty target would be published with an email address. Anyone who wished to send email to the address must compute a proof-of-work string for that email. Spammers are disincentivised by this system because their profitability depends on being able to send many messages which only a small fraction of people will respond to. Under HashCash, a spammer would have to do work on every individual spam message. Any sender must think more about whether his message is worthwhile. On the other hand, if he does the work, he can be fairly certain that his message will be read because it is in the receiver's interest to set a difficulty that limits messages to an amount that he can handle. HashCash is thus the perfect spam filter.
Proof-of-work is a defense against any information that would waste your time. In HashCash, the recipient of a message selects the difficulty target and rejects the message if it is not satisfied. It is also possible for the sender to select the target. This is appropriate in a public setting where many messages are in competition with one another for attention. Proof-of-work then becomes a content ranker rather than a spam filter.
It is natural to use proof-of-work this way in Bitcoin. People who create content choose what target they want to satisfy. Everyone can have his own private target that he uses to filter content. Content with more proof-of-work will be viewed by more people.
The longer the time elapsed between the creation of two proof-of-work strings, the less valid the comparison between them. Proof-of-work is better for ranking information at similar times. Historical relationships of hashpower to energy can be used to make a better comparison. However, good past information will develop a good reputation. Recent information is less easily judged and therefore benefits more from proof-of-work as an aid to sift through it.
The expected number of hashes for two different proof-of-work strings is additive. Therefore, the same data can be associated with several proof-of-work strings and can be treated as if it has achieved a single effective difficulty target. A customer who wants to add more proof-of-work to a document that already has some can do so. All that is required is that the proof-of-work string contain meaningless data so that it is not identical to a previous one. The Boost Pow protocol has a sequence field for this purpose. This could be used to implement upvotes.
Proof-of-work can be used to distinguish a good offer from deception. A manipulator has an offer that is more likely to be rejected because his idea is actually no good. Proof-of-work is more costly for him than for someone with a good offer because manipulators must communicate more in order to find potential marks. Manipulators can be detected based on who wants to avoid doing proof-of-work. Thus, proof-of-work has security applications because it makes deception less profitable.
This can be understood in the context of spam filtering. Few people respond to spam messages but a spammer can still earn a profit by reaching many annoyed readers. This applies not just to inferior products but to scams. Most people can tell that they are not really corresponding with a Nigerian prince but a few fall for it and lose money. If all potential Nigerian princes were ignored until they demonstrate expended energy, they would not attempt to scam people in the first place.
In the past, Bitcoin was damaged by attacks that proof-of-work would have prevented. A danger in relying on trusted third parties is that the network is not resilient to degradation of the value of the trusted third party. If the trusted third party is corrupted, it can exploit its users for a long time before a viable alternative can be constructed. A trusted third party is thus a coveted prize of manipulators. Failing to grasp that this was the very problem that Bitcoin was designed to solve[^1], many Bitcoiners relied on trusted third parties for information about Bitcoin and were deceived into acting against their own investment on the basis of what they learned.
The BitcoinTalk forum, reddit.com/r/bitcoin, and the Bitcoin Core Github repository were all trusted by Bitcoiners to provide information about Bitcoin. When they were corrupted, Bitcoiners did not easily react to rely on new information sources. This resulted in ideas being adopted which were inimical to Bitcoin, such as small blocks and Segwit. Small blocks prevent Bitcoin from functioning as money because they make it impossible for anyone to expect that he can spend at any time or take profits without incurring prohibitively high fees. A block size limit incentivizes miners to mine passively rather than investing in the network to attract more business. As for SegWit, that was an attempt to manipulate miners into colluding in a way that benefits the earliest detractor. Under Segwit, miners agree to reinterpret anyone-can-spend outputs as something else. The moment their collusion fails, their interest is to spend as many SegWit outputs as they can before the other miners. Both small blocks and SegWit were adopted by BTC despite making the network unviable and serving interests very different from that of the Bitcoin investors.
Had Bitcoiners known to pay more attention to messages that demonstrated more proof-of-work, the damage from the Bitcoin Core developers would have been much smaller due to their inferior ability to create value. Had they been expected to provide proof-of-work strings every time they wanted to argue that Bitcoin did not work with big blocks, they would have run out of energy more quickly. Furthermore, other sources of information which were associated with genuine value creation would have attracted the attention of Bitcoiners more easily.
A design goal is to adapt existing technology to the needs of a proof-of-work service. The Bitcoin mining infrastructure is built around HASH256 (aka double SHA256) and the Bitcoin block structure, which is an 80 byte header.
{
int32: version,
digest256: previous,
digest256: merkle_root,
uint32: timestamp,
uint32: target,
uint32: nonce
}and a list of items such that the HASH256 hashes of the items in the list are the leaves of a Merkle tree which has merkle_root as its root. A header is valid if its HASH256 digest is less than the difficulty target, which is a 32 byte number given by a target in terms of a 4-byte exponential form, such that the last byte is an exponent and the rest are significant digits.
Miners and mining pools communicate with a protocol called Stratum[^7]. Stratum supports additional random input from both mining pool and miner beyond the 32 bits allowed in the Bitcoin block header, which is necessary for achieving higher difficulties. This additional data is inserted into the coinbase transaction. Thus, a Stratum job consists of the data in a Bitcoin block header other than the Merkle root and nonce, the Merkle path of the coinbase transaction, the mining pool's extra nonce, and the rest of the coinbase transaction. The miner reconstructs the coinbase transaction with his own extra nonce and when he has satisfied a work target, he replies to the mining pool with his Merkle root, nonce, and extra nonce.
In order to be compatible with this system, a Boost proof consists of a Merkle tree with one leaf. The tree is compatible with a Bitcoin block format from the standpoint of the Stratum protocol. There is an 80-byte Boost PoW string corresponding to a Bitcoin block header and a Boost metadata string corresponding to the coinbase. The Boost PoW string contains the hash of the content upon which work was done and the Boost metadata string contains metadata. The script of the output verifies that work was done using the same steps that would be used on a Bitcoin block with one transaction. The content can be stored in an OP_RETURN output, somewhere else in the transaction, or it can be kept secret.
The Boost PoW string has the following form
{
int32: category,
digest256: content_hash,
digest256: meta_hash,
uint32: timestamp,
uint32: target,
uint32: nonce
}As with the Bitcoin block header, the string is valid if the HASH256 digest is less than the difficulty target. Target and nonce are in the same locations as in the Bitcoin header. The new fields have the following meanings:
category - Whatever you want it to mean.
content_hash - The HASH256 digest of the content which the user wishes to associate with provably expended energy.
meta_hash - The HASH256 of the metadata string.
The Boost metadata string has the following structure
{
digest160: tag,
digest160: mining_pool_pubkey_hash,
uint32: extra_nonce_1,
uint32: extra_nonce_2,
uint32: user_nonce,
bytes: additional_data
}tag - information used to associate this work with data.
mining_pool_pubkey_hash - is required to be the hash of the public key that is used to sign the Bitcoin transaction used to redeem a Boost output. This requirement enables buyers of proof-of-work the option to contract with individual miners for proof-of-work. These buyers will receive the miner’s pubkey hash and put it in their output. There is also the option of creating a Boost output with a bounty that any miner can redeem. A miner redeems these outputs by giving his pubkey and pubkey hash together into his input.
extra_nonce_1 - additional entropy provided by the mining pool. Corresponds to ExtraNonce1 in Stratum, which is also the user id.
extra_nonce_2 - additional entropy provided by the miner. Corresponds to ExtraNonce2 in Stratum.
user_nonce - additional entropy provided by the user in the output.
additional_data - anything the buyer wants. This data, like the header, can be used to provide context to the message on which work is being done. However, this data will be associated only with this particular purchase of work, not with the message itself.
The Boost output script verifies the Merkle path of the metadata string. Any additional page can be verified as part of the work by reference to the information in the script. It is not an attack for a user to buy additional proof-of-work on a hash that already has work done on it under a different title and abstract page. Users are allowed to present an old work in a new way and the proof-of-work that can be verified in script is valid for the original work, which the buyer could not have changed.
In Boost, there are two types of scripts: Boost bounty scripts can be redeemed by anyone who finds a nonce; Boost contract scripts can only be redeemed by someone who controls the key corresponding to a given pubkey_hash. They follow the same Bitcoin script program except that:
There are two versions of the script depending on whether BIP 320: nVersion bits for general purpose use is supported. This BIP allows for ASIC Boost to be used without interfering with the timestamp. Implementations of Boost PoW should accept support both versions but should support BIP 320 for newly created scripts.
In Bitcoin script, a program is a concatenation of the input script that redeems the output with the output script. The full programs have the following form:
push{signature}
push{mining_pool_pubkey}
push(4){nonce}
push(4){timestamp}
push(8){extra_nonce_2}
push(4){extra_nonce_1}
push(2){general_purpose_bits}
// <---- split program here for Boost contract and include script marker ---- >
push(20){mining_pool_pubkey_hash}
// <---- split program here for Boost bounty and include script marker ---- >
push(4){category}
push(32){content_hash}
push(4){target}
push(<=20){tag}
push(4){user_nonce}
push{additional_data}
OP_CAT, OP_SWAP,
// copy mining pool’s pubkey hash to alt stack. A copy remains on the stack.
OP_5, OP_ROLL, OP_DUP, OP_TOALTSTACK, OP_CAT,
// expand compact form of target and push to altstack.
OP_2, OP_PICK, OP_TOALTSTACK,
OP_6, OP_ROLL, OP_SIZE, OP_4, OP_EQUALVERIFY, OP_CAT, // check size of extra_nonce_1
OP_6, OP_ROLL, OP_SIZE, OP_8, OP_EQUALVERIFY, OP_CAT, // check size of extra_nonce_2
// create metadata document and hash it.
OP_SWAP, OP_CAT, OP_HASH256,
// target and content + merkleroot to altstack.
OP_SWAP, OP_TOALTSTACK, OP_CAT, OP_TOALTSTACK,
// general purpose bits
push_hex("ff1f00e0"), OP_DUP, OP_INVERT, OP_TOALTSTACK, OP_AND,
OP_SWAP, OP_FROMALTSTACK, OP_AND, OP_OR,
OP_FROMALTSTACK, OP_CAT, // attach content + merkleroot
OP_SWAP, OP_SIZE, OP_4, OP_EQUALVERIFY, OP_CAT, // check size of timestamp.
OP_FROMALTSTACK, OP_CAT, // attach target
// check size of nonce. Boost POW string is constructed.
OP_SWAP, OP_SIZE, OP_4, OP_EQUALVERIFY, OP_CAT,
// Take hash of work string and ensure that it is positive and minimally encoded.
OP_HASH256, ensure_positive,
// Get target, transform to expanded form, and ensure that it is positive and minimally encoded.
OP_FROMALTSTACK, expand_target, ensure_positive,
// check that the hash of the Boost POW string is less than the target
OP_LESSTHAN, OP_VERIFY,
// check that the given address matches the pubkey and check signature.
OP_DUP, OP_HASH160, OP_FROMALTSTACK, OP_EQUALVERIFY, OP_CHECKSIG
push{signature}
push{mining_pool_pubkey}
push(4){nonce}
push(4){timestamp}
push(8){extra_nonce_2}
push(4){extra_nonce_1}
// <---- split program here for Boost contract and include script marker ---- >
push(20){mining_pool_pubkey_hash}
// <---- split program here for Boost bounty and include script marker ---- >
push(4){category}
push(32){content_hash}
push(4){target}
push(<=20){tag}
push(4){user_nonce}
push{additional_data}
OP_CAT OP_SWAP
// copy mining pool’s pubkey hash to alt stack. A copy remains on the stack.
OP_5 OP_ROLL OP_DUP OP_TOALTSTACK OP_CAT
// copy target and push to altstack.
OP_2 OP_PICK OP_TOALTSTACK
OP_5 OP_ROLL OP_SIZE OP_4 OP_EQUALVERIFY OP_CAT // check size of extra_nonce_1
OP_5 OP_ROLL OP_SIZE OP_8 OP_EQUALVERIFY OP_CAT // check size of extra_nonce_2
// create metadata string and hash it.
OP_SWAP OP_CAT OP_HASH256
OP_SWAP OP_TOALTSTACK OP_CAT OP_CAT // target to altstack.
OP_SWAP OP_SIZE OP_4 OP_EQUALVERIFY OP_CAT // check size of timestamp.
OP_FROMALTSTACK OP_CAT // attach target
// check size of nonce. Boost PoW string is constructed.
OP_SWAP OP_SIZE OP_4 OP_EQUALVERIFY OP_CAT
// Take hash of work string and ensure that it is positive and minimally encoded.
OP_HASH256 ensure_positive
// Get target, transform to expanded form, and ensure that it is positive and minimally encoded.
OP_FROMALTSTACK expand_target ensure_positive
// check that the hash of the Boost PoW string is less than the target
OP_LESSTHAN OP_VERIFY
// check that the given address matches the pubkey and check signature.
OP_DUP OP_HASH160 OP_FROMALTSTACK OP_EQUALVERIFY OP_CHECKSIGexpand_targetexpand_target - transforms the uint32 exponential (compact) format for the difficulty target into the full uint256 value.
expand_target = OP_SIZE OP_4 OP_EQUALVERIFY OP_3 OP_SPLIT
OP_DUP OP_BIN2NUM OP_3
21 // actually 33, but in hex
OP_WITHIN OP_VERIFY OP_TOALTSTACK
OP_DUP OP_BIN2NUM OP_0 OP_GREATERTHAN OP_VERIFY // significant must be positive
0000000000000000000000000000000000000000000000000000000000
OP_CAT OP_FROMALTSTACK OP_3 OP_SUB OP_8 OP_MUL OP_RSHIFTensure_positiveNumbers in Bitcoin script are in little endian and the last bit is a sign bit. However, the target and the hash digest are both supposed to be positive numbers. Thus, we have to attach an extra byte of zeros to numbers to ensure that they are positive.
ensure_positive = 00 OP_CAT OP_BIN2NUMThe optional marker for output scripts comes first in the output script and has the form
push{"boostpow"} DROPIn other words, it pushes the string of bytes {0x62, 0x6F, 0x6F, 0x73, 0x74, 0x70, 0x6F, 0x77} to the stack, and then drops it.
Alice wishes to buy proof-of-work that will be supplied by Bob, a miner.
Alice creates a Boost transaction that any miner can redeem and Bob is the lucky one who achieves it first.
In order to do this, Alice creates a Boost bounty output with enough bitcoins in it to incentivize someone to do the work. She creates a Bitcoin transaction with this output and lets the network process it.
When Bob sees Alice’s Boost output, he assesses whether the value of the output is a better reward for the time it would take to find the nonce than the expected income from working on the next block over that time. If he does, he selects a public key and searches for a nonce.
If he finds it, Bob redeems Alice's output with a Boost input script.
Alice may accidentally create too small of a bounty for any miner to find it worthwhile to redeem. In such an event, Alice can make an additional Boost output with an identical script. Additional funds in this new output will be an addition to the bounty for the same work target. The same nonce and pubkey can be used to redeem both outputs.
Alice contracts directly with Bob to do the work. Alice may want this because the price is lower. Bob may want this because he earns a more certain income. However, he must also provide a guarantee that the work will be done because the resulting output cannot be redeemed by any other miner. Thus, Bob provides Alice with an address that she puts in her Boost contract output. Bob then does the work without fear of being scooped, and when he is done he redeems Alice's output with his Boost input script.
Proof-of-work makes honesty optimal. This is achieved by associating visible risk with the transmission of information. All who presume to transmit information are rewarded with more attention for risking more. Those who can best assess the relative value of their information will achieve the best balance of risk and reward. As long as dishonesty still exists, honest actors can benefit by creating stiffer competition.
The potential customers of a proof-of-work service therefore include all platforms which broadcast information. Is a new novel something that people will want to read again and again or is it something that will be forgotten quickly? Readers who wish to know can see exactly what the publisher thinks of it by verifying proof-of-work. The same goes for movies and other forms of entertainment.
Social networks are also prone to attracting useless information. Facebook and Twitter are already so far gone that they are unsalvageable. With Boost, we can make a version of reddit in which the upvote actually means something. Dating services are an obvious application.
Advertisement is of course a very manipulative industry. Who is genuinely good? Proof-of-work tells you exactly what a service provider believes he can regain by attracting your attention. Over time, only someone competent can demonstrate more opportunity cost.
Literally everyone in the world needs a proof-of-work service whether they understand it or not. Spam is everywhere, not just in your email inbox. Furthermore, it is always cheaper for manipulators to gain attention using platforms in which proof-of-work is not used than if it is. Once anybody starts using it, competing services will have to follow suit or become relatively more hospitable to manipulators and risk being overrun with them. As Zahavi has shown[^2], in equilibrium, all bucks have antlers.
[^1]: Satoshi, “Bitcoin: A Peer-to-Peer Electronic Cash System”.
[^2]: Zahavi, The Handicap Principle: A Missing Piece of Darwin's Puzzle, Oxford University Press USA, 1999.
[^3]: Graffen, “Biological Signals as Handicaps,” Journal of Theoretical Biology, Volume 144, Issue 4, 21 June 1990, Pages 517-546.
[^4]: Leslie Lamport, Robert Shostak, and Marshall Pease, "[The Byzantine Generals Problem] (https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Byzantine-Generals-Problem.pdf)", ACM Transactions on Programming Languages and Systems , July 1982, pp. 382-401.
[^5]: Adam Back, "Hashcash - Amortizable Publicly Auditable Cost-Functions".
[^6]: Adam Back, “HashCash: A Denial of Service Countermeasure.”, Tech Report, Aug 2002.
[^7]: https://docs.google.com/document/d/1ocEC8OdFYrvglyXbag1yi8WoskaZoYuR5HGhwf0hWAY/edit?usp=drivesdk Stratum is poorly documented. This the best Stratum documentation I could find. There is no guarantee that real-world implementations follow this document exactly.