Intrinsic worth brainstorming: Difference between revisions

From Bitcoin Wiki
Jump to navigation Jump to search
Sgornick (talk | contribs)
Add Second Level for Topics.
DanielH (talk | contribs)
 
(3 intermediate revisions by 3 users not shown)
Line 75: Line 75:


oh, i got it. choose the bid winner stochastically.
oh, i got it. choose the bid winner stochastically.
==== more ruminations on paying for computation ====
http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773169 brings up the idea of "programming" a market to solve an NP-complete problem for you by placing a series of orders. This inspires a better idea than holding an auction to see whose NP-complete problem will be solved next; instead, the system should allow everyone's NP-complete problem to be put out there, and other participants solve the ones they can, being paid for it by the person issuing the question.
Also, the low transaction costs of BTC make one wonder if this is already the case; are there ways that one could make offers to the market such that, by their nature, the market is incentivized to solve NP-complete problems for you? Maymin describes one way (which he terms OCO-3) which is a rather direct encoding of 3-SAT, but it's rather unnatural -- but surely there are others.
One difference is that, in Maymin's scenario, the market can silently yield the "wrong answer" simply by being inefficient, whereas in BTC, nodes either claim to have reversed a given hash, or they don't.
-- BayleShanks
=== Alternative where it doesn't matter who knows the answer already ===
Most of the proposals so far have problems or potential problems when a miner already knows the solution, and where solving a problem happens in a deterministic way making the miner with the most computing power always "win". Both of these problems can be solved using techniques already used in Bitcoin. It turns out that there is a computational problem which is extremely important to Bitcoin but where everybody already knows many answers: "What is a nonnegative integer that is less than the current target?".  The reason Bitcoin survives even though everybody knows the answer is because they are required to find it in a special way which is very slow, namely trying a bunch of different guesses in a random order with repetition. This is a poor strategy if you actually want to find small numbers, but it's a pretty good (though not perfect, as there may be repetition) strategy for solving certain NP-complete problems. Thus, I suggest that a block's hash can be checked not only for whether it's greater than or less than a given target, but also for whether it solves any of the existing problems. For example, perhaps one could take the several least significant bits of the hash and see if they happen to solve any of the proposed 3-SAT problems. Obviously, if the miners determine that it is not worth their computing time to check for certain problems (maybe ones which don't pay enough for the size of the problem), then they are free to ignore those problems. Solving a problem (or more than one) could give a partial discount on the rest of the hash (it would need to be a partial discount to prevent people from attacking the network by repeatedly posing trivial problems where every possibility is a solution).  Thus, my proposal is as follows:
# Allow a new script operator which pops the last three items off the stack, interprets the top one as a 3-SAT problem (PROBLEM), the middle ones as an integer (OFFSET), and the bottom one as a sequence of bits (SOLUTION). It puts TRUE on the stack if the bits of SOLUTION, starting at bit OFFSET, are a solution to PROBLEM. The usual way to use it would be in the scriptPubKey of a transaction output, the whole output taking the form "<PROBLEM> <OP_3SAT>". A valid transaction which uses this type of output as a transaction input is said to solve the problem.
# Make a separate portion of a block, which doesn't change the block header when it's changed (so as not to affect the hash), which is a single transaction. This transaction may be of any type, but under most circumstances will only have inputs from transactions of the type mentioned above. Every transaction input will be have an implied operation which pushes the block's hash onto the stack, so the scriptSig will usually only push an offset onto the stack. Since the transaction is already included in a block, it SHOULD NOT include a transaction fee. Obviously it MUST NOT include any of the same inputs as are already used in the main part of the block.
# A block is valid iff the transaction above (if any) is valid, the block's hash is less than the sum of the target and some "score" (to be determined) calculated from the set of all problems the transaction above solves, and any other conditions on whether a block is valid. This score SHOULD have some maximum to prevent spamming the network with trivial problems, and SHOULD be zero if no problems are solved. It may be based on such things as the number of variables involved, the size of the problem, and the age of the problem in the block chain. If the score increases with each of these, then more complex problems will usually have higher scores to indicate that they are harder to solve, and older problems will have higher scores to ensure that every problem is eventually solved if possible and because an old problem has been shown to be difficult.
# IF POSSIBLE, current blocks SHOULD be considered valid but with no solved problems. I do not know enough about the specifics of the block format to know if this is possible.
This way, miners may work on any or all problems they see fit, it doesn't matter who knows the answer, and problems will not be deterministically solved by whoever has the most computing power. If somebody figures out the answer but does not solve a block with it, they can submit it as a regular transaction, but then must pay transaction fees. The price for computing power will be determined by the miners and by anybody who's willing to solve the problems without mining. The score should be such that miners will be likely to try to figure out the answer and anybody who may want to devote computing power to solving the problems would be better served by mining.
==See Also==
* [[Ideal Properties of Digital Commodities]]


==References==
==References==
<references />
<references />

Latest revision as of 19:47, 27 August 2012

This page is for brainstorming ways to endow Bitcoin with "backing", that is, some sort of near-fundamental or near-intrinsic worth to BTC (that does NOT derive merely from their scarcity or their use as a medium of exchange). This would provide a price floor independent of speculators or BTC's use as a medium of exchange.

This page is not the place to discuss DoesBtcNeedBacking, or to argue if speculation or usage of medium of exchange should be included in the definition of "backing". This page is for brainstorming other kinds of backing.

Topics

BitX

See https://bitcointalk.org/index.php?topic=1790.0 . The worth of bitcoins would be the maximum of the worth of any of the services built on top of bitcoin.

Many of the following ideas are a specialization of the BitX idea.

Publishing

Bitcoin is fundamentally a global censorship-resistant memory system, similar to FreeNet. It just happens that what it is remembering is the log of Bitcoin transactions.

Information can be encoded in the transaction log, and the speed with which it can be encoded is limited by the ability to encode information into the blockchain. Encoding information into the blockchain requires BTC (or, while BTC are mineable, computing power, which has a price floor).

Publishing services could be setup which encode information into the blockchain (that is, to perpetually, globally publish, in a censorship-resistant way), and read out encoded information, for a price. Like FreeNet, for pay. This sort of service is more valuable if it is done on top of something like Bitcoin (because the network effects of Bitcoin provide stronger incorruptibility). This inherent value provides backing.

Marked coins

Because BTC is traceable, other alternative currency systems could be built on top of BTC. For example, if I had a lot of gold, and assuming that 1 BTC was worth less than an ounce of gold, then I could buy 1000 BTC and then say, "My BTC address is XYZ. Any BTC which was has passed thru this address is equivalent to a transferrable IOU for one ounce of gold from me.". Then I sell those BTC for whatever an ounce of gold is worth. This provides a standardized way to electronically transfer gold IOUs.

This would mean that those bitcoins would be backed by gold. It wouldn't mean that ALL bitcoins would be backed by gold. But, the fact that all alternative currency issuers utilizing this "marked coins" scheme on top of bitcoin first need to acquire bitcoins provides a backing for all bitcoins (the value of this backing would be much less than the value of the alternative currencies themselves, of course). In other words, bitcoin's inherent usefulness as a layer underlying other alternative currencies would be the backing.

Triple Entry Accounting

Bitcoin functions as a triple-entry accounting system that provides a transaction register that can be publicly audited. Ian Grigg has published on this topic[1] and on Bitcoin being the first wide-scale application of it[2].

This property has already been used in differing ways -- for instance, to verify how much in donations have been collected[3] and the full list of tickets sold for each weekly and monthly BitLotto draw.

Namecoin

https://bitcointalk.org/index.php?topic=6017.0 , https://bitcointalk.org/index.php?topic=30294.0

Voting

BTC could provide the substrate for an anonymous transitive proxy voting system. Simply give tiny amounts of BTC to the voters, then create a deposit address for each ballot alternative and tell the voters to send their votes thru a mixer before depositing.

The need for the authority holding the vote to buy the BTC initially endows BTC with intrinsic worth.

Goods and services which are ONLY buyable with BTC, for set prices

Mere usage of BTC as a medium of exchange isn't backing. But if some merchants sell something which (a) may ONLY be purchased with BTC (similar to "petrodollars"; a lot of oil can only be purchased with dollars), (b) are made available to sell at a set BTC price, INDEPENDENT OF THE EXCHANGE RATE OF BTC VS ANY OTHER CURRENCY, then this provides backing.

An example would be an MMORPG in which the in-game currency were Bitcoin, and in which the prices of some in-game things were set by the creator of the game without reference to BTC's current price on currency exchanges (specifically, if the price of BTC in dollars fell, the game maker would NOT drop the in-game price of items).

Something which satisfied (a) but not (b) wouldn't quite be backing, but it would be better than nothing.

A club which demands dues in BTC

Consider how the U.S. dollar is the only currency that is accepted for payment of U.S. taxes. This creates a demand for dollars to pay taxes with.

The U.S. gov allows you to transact business in some other currency, but you still have to pay a percentage of the net income generated by those transactions in dollars.

This isn't quite backing but it would be better than nothing.


Alternatives to BTC which would have intrinsic worth

This section is for discussing things that can't be done ON TOP of BTC, but which could be done by creating something very similar to BTC.

pseudo-BTC that uses computational power in service of some problem

If there were a way for someone to purchase a large amount of pseudo-BTC and then use them to "buy" computing power, in the form of specifying an NP-complete problem, such that solving that problem then becomes a way to encode additional transactions into the blockchain (instead of meaningless hashes), then the price of computing power would be the intrinsic worth of pseudo-BTC.

Obviously, the issue that must be solved is: whoever poses the question (the purchaser of the computing power) may already know the answer. Therefore, we cannot assume that there is a lower bound on the computational difficulty of the problem posed.

If the problem is NP-complete and is posed in a standard NP-complete format, however, we can assume an upper bound on the computational difficulty.

One idea: combine this with the current "meaningless hash" system as follows: in order to mine BTC (or, later, to insert transactions into the block chain), nodes must do both of (a) do some hashing, (b) solve an NP-complete problem whose difficulty is upper bounded at 1000 times the amount of hashing that needs to be done. The system would include a way for computing buyers to bid BTC for the right to pose the problem in (b). Bids are encoded into the blockchain, and the highest already-encoded bid is chosen. The money from the bid is transferred partially to the node that solves the problem (b), but partially to a different node(s) that also solved the hash (a); the money is divided up in proportion with the 1000 constant (this is so that a rich miner can't just make up problems with known answers and bid huge amounts on them, allowing them to always win the bid for computing power and pose the problem, allowing them to undercut everyone else because, knowing the answer to the problem they posed, they only have to solve (a), whereas everyone else would have to solve (a) and (b); this ensures that if they do that, the money they bid doesn't all go back to them, but in fact is bled off to give to other miners too).

Now (a) provides a floor for the difficulty, which is needed to keep the blockchain un-pwnable, and and (b) provides a floor for the value of BTC.

I dunno is 1000 is the right value for the proportionality constant.

Are there any flaws in this? Seems to me that the current BTC ecology could be transitioned to this pretty easily if more than 50% of the miners (weighted by computing power) agreed.

I'm not sure if this would actually cause computing power auctions or not. It may cause:

Miner Q bids unreasonably highly for computing power, then poses a problem for which only they already know the solution; but then eventually, miner R outbids them, then does the same. The prices are too high for others to actually buy computing power. But Q and R themselves generate an enormous demand for bitcoins, because they need to outbid the other in order to monopolize mining.

Hmmm... we don't want mining monopolized.. needs a bit more work..

oh, i got it. choose the bid winner stochastically.

more ruminations on paying for computation

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773169 brings up the idea of "programming" a market to solve an NP-complete problem for you by placing a series of orders. This inspires a better idea than holding an auction to see whose NP-complete problem will be solved next; instead, the system should allow everyone's NP-complete problem to be put out there, and other participants solve the ones they can, being paid for it by the person issuing the question.

Also, the low transaction costs of BTC make one wonder if this is already the case; are there ways that one could make offers to the market such that, by their nature, the market is incentivized to solve NP-complete problems for you? Maymin describes one way (which he terms OCO-3) which is a rather direct encoding of 3-SAT, but it's rather unnatural -- but surely there are others.

One difference is that, in Maymin's scenario, the market can silently yield the "wrong answer" simply by being inefficient, whereas in BTC, nodes either claim to have reversed a given hash, or they don't.


-- BayleShanks

Alternative where it doesn't matter who knows the answer already

Most of the proposals so far have problems or potential problems when a miner already knows the solution, and where solving a problem happens in a deterministic way making the miner with the most computing power always "win". Both of these problems can be solved using techniques already used in Bitcoin. It turns out that there is a computational problem which is extremely important to Bitcoin but where everybody already knows many answers: "What is a nonnegative integer that is less than the current target?". The reason Bitcoin survives even though everybody knows the answer is because they are required to find it in a special way which is very slow, namely trying a bunch of different guesses in a random order with repetition. This is a poor strategy if you actually want to find small numbers, but it's a pretty good (though not perfect, as there may be repetition) strategy for solving certain NP-complete problems. Thus, I suggest that a block's hash can be checked not only for whether it's greater than or less than a given target, but also for whether it solves any of the existing problems. For example, perhaps one could take the several least significant bits of the hash and see if they happen to solve any of the proposed 3-SAT problems. Obviously, if the miners determine that it is not worth their computing time to check for certain problems (maybe ones which don't pay enough for the size of the problem), then they are free to ignore those problems. Solving a problem (or more than one) could give a partial discount on the rest of the hash (it would need to be a partial discount to prevent people from attacking the network by repeatedly posing trivial problems where every possibility is a solution). Thus, my proposal is as follows:

  1. Allow a new script operator which pops the last three items off the stack, interprets the top one as a 3-SAT problem (PROBLEM), the middle ones as an integer (OFFSET), and the bottom one as a sequence of bits (SOLUTION). It puts TRUE on the stack if the bits of SOLUTION, starting at bit OFFSET, are a solution to PROBLEM. The usual way to use it would be in the scriptPubKey of a transaction output, the whole output taking the form "<PROBLEM> <OP_3SAT>". A valid transaction which uses this type of output as a transaction input is said to solve the problem.
  2. Make a separate portion of a block, which doesn't change the block header when it's changed (so as not to affect the hash), which is a single transaction. This transaction may be of any type, but under most circumstances will only have inputs from transactions of the type mentioned above. Every transaction input will be have an implied operation which pushes the block's hash onto the stack, so the scriptSig will usually only push an offset onto the stack. Since the transaction is already included in a block, it SHOULD NOT include a transaction fee. Obviously it MUST NOT include any of the same inputs as are already used in the main part of the block.
  3. A block is valid iff the transaction above (if any) is valid, the block's hash is less than the sum of the target and some "score" (to be determined) calculated from the set of all problems the transaction above solves, and any other conditions on whether a block is valid. This score SHOULD have some maximum to prevent spamming the network with trivial problems, and SHOULD be zero if no problems are solved. It may be based on such things as the number of variables involved, the size of the problem, and the age of the problem in the block chain. If the score increases with each of these, then more complex problems will usually have higher scores to indicate that they are harder to solve, and older problems will have higher scores to ensure that every problem is eventually solved if possible and because an old problem has been shown to be difficult.
  4. IF POSSIBLE, current blocks SHOULD be considered valid but with no solved problems. I do not know enough about the specifics of the block format to know if this is possible.

This way, miners may work on any or all problems they see fit, it doesn't matter who knows the answer, and problems will not be deterministically solved by whoever has the most computing power. If somebody figures out the answer but does not solve a block with it, they can submit it as a regular transaction, but then must pay transaction fees. The price for computing power will be determined by the miners and by anybody who's willing to solve the problems without mining. The score should be such that miners will be likely to try to figure out the answer and anybody who may want to devote computing power to solving the problems would be better served by mining.

See Also

References