gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 12:01:55 PM Last edit: August 20, 2013, 07:56:14 PM by gmaxwell |
|
First go read and understand CoinWitness, it describes an application for using proven computation in scripts, and also provides some background about the provable computation tools which I won't repeat here. In this message I describe another application for using provable computation (SCIP) as a script replacement, but this one isn't at all serious. It's downright amusingly bad. A checksig operation in a transaction script logically receives a pubkey, a signature, and a hash of the masked transaction (effectively a hash of the transaction with the scriptsigs removed; all this ignoring sighash flags for the purpose of discussion). In a world where we have a SCIP-script checksig operator it would work similarly: It would receive some optional additional public data, a public key (verification key), a signature (proof), and a hash of the masked transaction. To produce a signature for this system you would run the SCIP-script program corresponding to the verification key inside the SCIP prover, giving it as a public input the hash of the masked transaction and any extra public or non-public inputs. If the program accepts the result is the proof your transaction needs to be considered valid. Because the hash of the masked transaction itself is part of the public input, the SCIP-script could also require the unhashed masked transaction as a non-public input when it runs. The program could then test any of the non-masked data in the transaction, and only ACCEPT if it likes it. E.g. it could check the scriptpubkeys against a list or their output values against a range. It could choose to only sign if the transactions' nlocktime was high or low enough, or any mixture of these options. Because the inputs (which are themselves transaction hashes) are covered under the hash, the script could go further and require that you provide the input transactions— and it could apply whatever tests it wants on the inputs— potentially following them all the way back to an enormous number of coinbase transactions, imposing any computable rules it likes along the way. If you can't satisfy the rules, you can't spend the coin. A particular sort of rule could take the form of requiring any output scriptpubkey to be of the form THIS_VALIDATION_KEY && {whatever rules you want} and by doing so you have effectively created a coin which is forever subject to a covenant which will run with the coin and forever constrain the use of it and its descendants degrading and its fungibility. (Actually accomplishing this requires a bit of a hack: a SCIP program can't have its own validation key built into it, as that would be circular. But that is no fundamental limit here: the script can go read it out of the scriptpubkey of the input transaction that is being spent we can trust that its the right one because if it isn't transaction will be invalid even though the proof accepted). Any attempt to think of why someone might want to do this leaves me screaming in horror— Which you should expect as this is the robotic equivalent of a home owners association. (E.g. In a fit of tonal advocacy, Luke-Jr could start stamping coins with a covenant that only allows or makes their user pay higher txn fees unless the txout amounts were round tonal numbers.) A more serious point is that this kind of tool makes it rather difficult to intentionally exclude functionality from script— any data under the signature in a cryptographically strong way, even indirectly like all the data in prior transactions, its subject to testing by the script. What horrifying ways can you imagine covenants being used?
|
|
|
|
Peter Todd
Legendary
Offline
Activity: 1120
Merit: 1164
|
|
August 20, 2013, 01:46:34 PM |
|
Rick-roll bucks.
|
|
|
|
iddo
|
|
August 20, 2013, 02:50:15 PM |
|
(Actually accomplishing this requires a bit of a hack: a SCIP program can't have its own validation key built into it, as that would be circular. But that is no fundamental limit here: the script can go read it out of the scriptpubkey of the input transaction that is being spent we can trust that its the right one because if it isn't transaction will be invalid even though the proof accepted).
Bootstrapping this process works ok? The initial scriptpubkey of the input transaction didn't have this validation key, so the SCIP program should say that a standard input there is ok too? If I understand correctly, the user who receives the coin is the one who decides to add the extra THIS_VALIDATION_KEY rule that will be enforced forever from this point forward? So this user is restricting himself to receive a coin that can only be spent in the future if the extra validation rule holds? I suppose that this would make the coin less valuable in comparison to a regular coin that doesn't have this restriction, so why would the user decide to add this extra validation rule to the coin that he receives in the first place? For example the most extreme validation rule would be that this coin is destroyed and cannot be spent at all, and here obviously the user would prefer to receive a fully-functional coin instead of this destroyed coin.
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 03:26:38 PM |
|
Bootstrapping this process works ok? The initial scriptpubkey of the input transaction didn't have this validation key, so the SCIP program should say that a standard input there is ok too? Yep. Not a problem. The content of a scriptpubkey is not evaluated when its created, only when it's consumed. Assuming you have no covenants in effect when you create a transaction you can put whatever you want into the scriptpubkey. Later when someone goes to spend it, they'll have to cope with whatever covenants you added (which can then look back from their position in the consuming transaction and find themselves in the output of the prior transaction). If I understand correctly, the user who receives the coin is the one who decides to add the extra THIS_VALIDATION_KEY rule that will be enforced forever from this point forward? So this user is restricting himself to receive a coin that can only be spent in the future if the extra validation rule holds? I suppose that this would make the coin less valuable in comparison to a regular coin that doesn't have this restriction, so why would the user decide to add this extra validation rule to the coin that he receives in the first place? For example the most extreme validation rule would be that this coin is destroyed and cannot be spent at all, and here obviously the user would prefer to receive a fully-functional coin instead of this destroyed coin. The world is a weird and complicated place. Covenants on real property are common, at least in some places, it's not always easy to predict what people would do. Sometimes they do things which are simply crazy. If you really want you can cook up some actual applications: I'd like to pay your company contingent on performing something but have the ability to take the payment back if you fail. Likewise, your employees want to receive those funds right away (as they don't trust their bosses) but understand that the funds could be taken back if there is a default. A temporary (but still heritable) covenant could allow the coins to circulate but preserve the clawback. Perhaps even local vendors would accept these conditional coins— preferring to receive the business and tolerating the risk. Generally I don't think the idea of covenants is a good one, quite the opposite. I was hoping to see people suggest some more awful ways which people might use this ability because of insanity, greed, or simply because they are misguided.
|
|
|
|
EmperorBob
Member
Offline
Activity: 67
Merit: 10
|
|
August 20, 2013, 03:47:23 PM |
|
This is amazing in a terrible way. Some evil ideas:
- Coins with a self destruct counter. Each transaction decreases the counter, once it reaches zero you can only spend it as fees. - Freicoin embedded inside bitcoin, instead of being a separate currency. - Snowballing txouts: The tainted inputs verify that there's a tainted output stricktly bigger than all of them. So to spend 1BTC of tainted value you must turn make a 1.0001 output of tainted value. And so on until all the available bitcoins are locked into one big txout. - Spamcoins: To spend it you must make a one satoshi output in your transaction. Bloat that UTXO!
Obviously the risk is limited, everyone receiving these coins would know about the fact that there are rules governing them, and would need to know the rules to be certain that they're actually spendable at all. This could make them actually useful in certain cases (especially if the covenant eventually expires). Some less evil ideas:
- Trustfund coin: Instead of a ton of txouts, each with a different locktime, you get a coin that lets you unlock some of the value back to regular coins as a function of height. It also embeds the extended public key for the locked part, so you can't safely transfer it to someone else, as you'll always have the ability to spend it. - Antitheft coin: Variant of the above, you can only send < 1BTC of unlocked value per hour (or some other amount), or you can send all of the value to a prespecified address at any time. Limits how much of your money can be stolen as long as you retain a copy of your private keys.
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 04:22:20 PM Last edit: August 20, 2013, 04:33:57 PM by gmaxwell |
|
Ohhh. I like the katamari (snowballing) coin and the spamcoin.
Lemme power-up the spamcoin some and externalize its cost:
- Smashcoin: Any spend of a coin with this covenant must retain the covenant and provide proof of an attack on an alternative cryptocurrency. (e.g. SPV proof of bloating some other cryptocoin's UTXO, or mining multiple blocks at the same height (with some committed data))
(In particular, if it required that there be no payee at all beyond the covenant for one of its outputs. ... and it becomes a self-administering bounty for attacking something else 0_o spooky. Fortunately most attacks are not cryptographically provable)
I think both Trustfund and Antitheft need access to the blockchain headers (to read the height, and to read the time in a secure manner). One interesting thing is that no amount of following back the inputs can actually get you a connection to the chain headers. You could just provide them as additional inputs and it could have headers-only (SPVish) security. To more strongly bind in the headers you'd want to add a "CHECKPOINT" field to transactions: in that field you put a block header hash and a restriction for how far back in the chain that block is allowed to be. This data would be included in signatures (thus available to the SCIP-script), and if the value in it isn't in the chain the transaction is invalid. (SCIP verifies your execution was faithful, but you could be lying in your inputs, so care is required that you don't overly trust any of them, e.g. don't just ask them for the time)
|
|
|
|
d'aniel
|
|
August 20, 2013, 06:39:42 PM |
|
I was thinking a potentially useful application of this could be security deposits, where an output can be spent before a specified block height only if cryptographic proof of fraud is presented, and in this case, it can only be spent to a miner sacrifice output (anyone can spend 100 blocks after the specified block height). After the specified block height, the output can be spent like normal by the depositor.
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 06:41:47 PM |
|
I was thinking a potentially useful application of this could be security deposits, where an output can be spent before a specified block height only if cryptographic proof of fraud is presented, and in this case, it can only be spent to a miner sacrifice output (anyone can spend 100 blocks after the specified block height). After the specified block height, the output can be spent like normal by the depositor.
Indeed, redeeming a fraud proof is a canonical use of a SCIP-script (esp since it can keep the fraud proof itself private, preventing miners from taking it, which no simple on-chain fraud proof support can do). Though this doesn't require a covenant (a script that encumbers future coins), just a script.
|
|
|
|
d'aniel
|
|
August 20, 2013, 06:52:51 PM |
|
I was thinking a potentially useful application of this could be security deposits, where an output can be spent before a specified block height only if cryptographic proof of fraud is presented, and in this case, it can only be spent to a miner sacrifice output (anyone can spend 100 blocks after the specified block height). After the specified block height, the output can be spent like normal by the depositor.
Indeed, redeeming a fraud proof is a canonical use of a SCIP-script (esp since it can keep the fraud proof itself private, preventing miners from taking it, which no simple on-chain fraud proof support can do). Though this doesn't require a covenant (a script that encumbers future coins), just a script. Even if you want to ensure the deposit goes to a (fair) miner sacrifice? I'm thinking of this for the case of sybil attack prevention in p2p networks where the deposit isn't placed with anyone in particular. In this case, if the deposit is claimable by the first person to present the fraud proof, then it will simply be claimed by the attacker, as he will have the advantage of surprise.
|
|
|
|
Peter Todd
Legendary
Offline
Activity: 1120
Merit: 1164
|
|
August 20, 2013, 06:56:49 PM |
|
Even if you want to ensure the deposit goes to a (fair) miner sacrifice? I'm thinking of this for the case of sybil attack prevention in p2p networks where the deposit isn't placed with anyone in particular. In this case, if the deposit is claimable by the first person to present the fraud proof, then it will simply be claimed by the attacker, as he will have the advantage of surprise.
You split up the amounts: a portion goes to the finder to encourage people to look for fraud, and the rest of the deposit goes to a txout that can't be spent before a given block height far off in the future. Just make sure the amount that goes to the finder is low enough that there is no incentive to commit fraud to collect the fidelity deposit.
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 07:48:28 PM |
|
Reminder: this thread is supposed to be about a _bad_ idea.
- Identicoin covenant: some kinds of officially issued IDs have a smart chip in them that can response to signature challenges and also can return a signed copy of your name and other info. Any Identicoin scriptpubkey output is constrained to have the covenant, a regular script, and an extra PUSH with the real name, DOB, etc. of the party being paid, as proven by a signature of the masked transaction hash by the users' ID card provided in the SCIP private input.
- Adultcoin covenant: Like the above, but DOB and blockchain headers constrains any future recipient to be >18. (but without the other properties: people wouldn't want their names on their "adult" purchases, after all)
|
|
|
|
Peter Todd
Legendary
Offline
Activity: 1120
Merit: 1164
|
|
August 20, 2013, 08:59:31 PM |
|
- decaying-crypto covenant: Outputs are required to be of the following basic form: HASH160 <n> SHIFT-RIGHT <target> LESSTHAN IF TRUE ELSE (other conditions) (require all txout scriptPubKeys to follow this same form, but with n=n+1) ENDIF
Stealing the coins is possible by solving the PoW, and is made twice as easy every time the coins are spent. - piss-off-gmaxwell covenant: You must provide a message with one or more of the following words: "asshole", "fuck-off", or "distributed hash table" signed by Gregory Maxwell's public key. Uniqueness is enforced by a n-of-m digest timestamping oracle. - bloat covenant: Only spendable if n prior blocks are over 1MB in size. Also, anti-bloat. - it-feels-good-to-pretend-to-be-regular covenant: Spending block is required to have a timestamp exactly 600 seconds ahead of previous block. - delorean covenant: Only spendable if the timestamp on the spending block is prior to the timestamp on the block the txout was created in. - attack-all-the-pools covenant: Only spendable if difficulty less than a certain value. Also see "I am an ASIC manufacturer" covenant: only spendable if difficulty greater. (can increase on every transaction) - there-can-be-only-one covenant: Requires that the distinct scriptPubKeys / transactions ratio in the last n blocks be less than a given ratio. Further more, decrease that ratio every time the coins are spent. - panopticon covenant: Requires n prior blocks had only transactions following the identicoin covenant. - fidelity-bonded distributed-hash-table covenant: To spend, the prior block is scanned for "request" transactions with scriptPubKey's of the form "RETURN <magic> <digest>" and for every digest the corresponding message must be included in the scriptSig. - game-of-life covenant: Include a n*m bit buffer on scriptSig and scriptPubKey, prove that the transition rules of Conways Game of Life were applied. Note that because the Conways Game of Life is turing complete you can embed a tape machine and thus a PoW crypto-currency in the bit buffer given a sufficiently large blocksize. - nomic covenant: Given a txout included in block n, to spend it in block m the blocks n...m are scanned for "nomic" transactions containing scriptPubKeys of the form "RETURN <magic> <opcodes>", and those sub-scripts are appended to the master script to form the next scriptPubKey that all txouts must adhere too.
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1134
|
|
August 20, 2013, 09:59:38 PM |
|
Very creative
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 10:08:35 PM |
|
- it-feels-good-to-pretend-to-be-regular covenant: Spending block is required to have a timestamp exactly 600 seconds ahead of previous block.
I was going to say that you can't do this one: The SCIP-script can't have a completely free form input like "what time was the last block" because you must know all the inputs when you run the prover and the prover takes time and so does confirmation. But you actually could, with the right opcodes which would effectively be a transaction which requires the miner to lie about their time. In general ones which are the function of the _last_ blocks directly become tricky, because if you want the SCIP to actually process the block you have to have it. (Easier if you have script operations to test these things and just push their test ID and result onto the stack, so you can compute the proof in advance assuming those things to be true). And the rest? oyyy.. I am imagining a dark future where for laughs people had encumber a bunch of coins and then treated them as destroyed and largely forgotten. Then a long while later the coin's value increases tremendously and that 1 BTC output where you have to advance the game of life to use the coins... "well, the game of life isn't that bad". Adds new meaning to the gaudiness of the nouveau riche and the idea of "tainted" coins.
|
|
|
|
Carlton Banks
Legendary
Offline
Activity: 3430
Merit: 3080
|
|
August 20, 2013, 10:18:44 PM |
|
Without pretending that I fully comprehend all of this, I think this means that anyone with the ability to write such a covenant into a transaction manually could create all sorts of rules about how the coin (or even all coins from the originating coinbase?) can be used in the future? Could you write fully algorithmic rules? With recursive properties? Genetic algorithms? Cure my naivety, or at least try!
|
Vires in numeris
|
|
|
Peter Todd
Legendary
Offline
Activity: 1120
Merit: 1164
|
|
August 20, 2013, 10:23:09 PM |
|
- it-feels-good-to-pretend-to-be-regular covenant: Spending block is required to have a timestamp exactly 600 seconds ahead of previous block.
I was going to say that you can't do this one: The SCIP-script can't have a completely free form input like "what time was the last block" because you must know all the inputs when you run the prover and the prover takes time and so does confirmation. But you actually could, with the right opcodes which would effectively be a transaction which requires the miner to lie about their time. In general ones which are the function of the _last_ blocks directly become tricky, because if you want the SCIP to actually process the block you have to have it. (Easier if you have script operations to test these things and just push their test ID and result onto the stack, so you can compute the proof in advance assuming those things to be true). Well that's the thing really: you don't actually need SCIP to do covenants - SCIP just tends to make them a lot more efficient and easy. For instance consider this proposal of mine: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02602.html A overly complex joke yes, but the basic idea is a covenant. In fact OP_MAST gets you pretty close because of how it lets you reference whole fragments of code so easily by digest.
|
|
|
|
gmaxwell (OP)
Moderator
Legendary
Offline
Activity: 4298
Merit: 8818
|
|
August 20, 2013, 11:03:54 PM |
|
Well that's the thing really: you don't actually need SCIP to do covenants - SCIP just tends to make them a lot more efficient and easy. In my mind the biggest difference is that it makes them hard to _forbid_, if SCIP-scripts just were implemented in the most obvious way (add a OP_CHECKSCIP) we would have likely gotten the ability to create covenants without even realizing or intending it because the technology is just so _generally_ powerful. If I make it sound like a negative thing it's because covenants can screw up fungibility (as our whimsical examples show), so while they can be useful and important to some protocols, we might want to take care in how we enable them. (Or at least consciously decide that they're a net win! ... and yes, sure, I wouldn't turn down SCIP in order to avoid covenants) Without pretending that I fully comprehend all of this, I think this means that anyone with the ability to write such a covenant into a transaction manually could create all sorts of rules about how the coin (or even all coins from the originating coinbase?) can be used in the future? Could you write fully algorithmic rules? With recursive properties? Genetic algorithms? Cure my naivety, or at least try!
The work that ultimately inspires this discussion ( SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge by Eli Ben-Sasson et al.) lets you convert arbitrary C programs into compact proofs which show that the program in question was faithfully executed and accepted a set of public and private inputs. In the future we could potentially use this system (or its descendants) as an alternative to Bitcoin script and the checksig operator and do a lot of neat things with it. There are engineering challenges which will need to be overcome to make it a practical reality— their current implementation needs— say— two CPU hours to "sign" a transaction for a fairly modest set of program rules. But the validation is fast, and thats the biggest deployment hurdle. In the mean time, its a fun to think about while the tech matures. I posted a more serious application for it in another thread.
|
|
|
|
Carlton Banks
Legendary
Offline
Activity: 3430
Merit: 3080
|
|
August 20, 2013, 11:23:26 PM |
|
The idea that cryptography can be applied like this is insanely brilliant, and so these pre-emptive thought experiments are vital. To think that the power of cryptographic/computational discoveries will not cease to improve cryptocurrency implementation is... I cannot find a superlative, Nakamotish? I will attempt to understand the posted links! A whole new generation should be encouraged to do the same, the whole cryptocurrency concept is so much more important than I even thought possible
|
Vires in numeris
|
|
|
jtimon
Legendary
Offline
Activity: 1372
Merit: 1002
|
|
August 21, 2013, 07:44:45 PM |
|
Visa/Mastercard covenant: every transaction moving the coins must be also signed by a public key controlled by visa or mastercard, thus restoring their financial censorship privileges.
Contact covenant: You can only spend the coin after proving that you've discovered a messsage probably created by extraterrestrial intelligence (according to whatever language complexity rules) when running a SETI@home work unit.
Curecoin covenant: You can only spend the coin after proving that you've solved a folding@home work unit.
Which brings me to the off-topic...Why there's so many people in the altchain subforum looking for proof of work schemes that make ASICs harder to build and no one seems to be looking for a way to use SCIP to substitute SHA256 and make miners help cure cancer while they secure the network? Maybe with proof stake to vote on the elegible work units or something, I don't know. I remember saying to newbies reusing the proof of work for useful stuff was probably impossible, but I didn't knew about SCIP then... That would remove the mining wastefulness argument against proof of work once and for all.
|
|
|
|
iddo
|
|
August 22, 2013, 07:02:08 PM |
|
- it-feels-good-to-pretend-to-be-regular covenant: Spending block is required to have a timestamp exactly 600 seconds ahead of previous block.
I was going to say that you can't do this one: The SCIP-script can't have a completely free form input like "what time was the last block" because you must know all the inputs when you run the prover and the prover takes time and so does confirmation. But you actually could, with the right opcodes which would effectively be a transaction which requires the miner to lie about their time. In general ones which are the function of the _last_ blocks directly become tricky, because if you want the SCIP to actually process the block you have to have it. (Easier if you have script operations to test these things and just push their test ID and result onto the stack, so you can compute the proof in advance assuming those things to be true). I failed to understand (for example I have no idea why you said "lie about their time"), could you please try to explain the above in a way that might be more clear? One thing that I can see is that the Bitcoin script language could be extended to include a new opcode (unrelated to SCIP) that puts on the stack the timestamp of the block in which this transaction resides, and similarly an opcode that puts on the stack the timestamp of the previous block (relative to the block in which this transaction resides), and then bind the SCIP program to use these two public inputs, and the SCIP program would be completely trivial i.e. it would just check the difference between its two inputs. So except for enforcing the covenant, SCIP isn't needed here, because the regular Bitcoin script can directly check the condition on the difference between the two timestamp values. Another thing that I can see is that the specified SCIP program (verification key) will have the hash of the genesis block (or a more recent checkpoint block hash) hardcoded into it, and will receive non-public input which is the all the next blocks, and the SCIP program checks that the entire hash chain is valid, and fetches the timestamp value from the last block that it hashed. But this way you can only fetch the timestamp of the previous block, not the current block?
|
|
|
|
|