Topic: Decentralized Bitcoin scratch-off cards (Read 6552 times)

That's not the point. The point is to prevent the Bitcoins from being spent back into the network by malicious parties, whether the party is the person holding the card or a malicious third party who shoulder surfs it.

IMO, the whole point of having scratch-off cards is if you don't trust the person handing you the coupon. I don't see any way to fix that short of having a (or many running the same open-source webservice) central trusted authority issuing the scratch-off cards.

See https://bitcointalksearch.org/topic/patch-bitcoin-scratch-off-cards-4555 for an implementation of scratch-off cards.

I presume you got your 279 byte figure from the start of key.h. Regardless of what that says the private keys are actually a maximum of 256 bits long. This is because Bitcoin uses the secp256k1 curve. I have also done the maths and it checks out.

The private key is just a number and like a number, the smaller it is, the fewer digits are required to specify it. Therefore, a scratch-off card manufacturer would choose a private key short enough to type but long enough not to be brute forced.
Note that an attacker would not be able to distinguish a scratch-off card generating transaction from a normal transaction in the block chain and so they would have to brute force all suspected unspent coins.

A 13 character case insensitive password of such as WTUYZFK64BOAD would imply a search space of about 2^66 curves. The last characters digits might be exhaustively searched by your client program as you typed it in by exhausting about 50k possibilities so you'd have to enter about 10 characters.


ByteCoin

I thought you wanted to brute-force a publicly-released private key and use that as the security. I read it wrong; sorry. Bitcoin private keys are much too large (279 bytes) to be typed in their entirety, so that wouldn't work, even if you could cut off ~2 bytes with brute-force.

I've just looked at Artforz scheme which is simpler than yours but my scheme is simpler still and looks like a normal transaction so is less likely to be speculatively brute-forced by an attacker. You say it's horribly insecure. How so?

ByteCoin

So what we need is an extension to the client that permits the import and export of keypairs to a standardized file format, that could then be sent to anyone in any other way that files can be transfered.  The export process should automaticly assign the keypair the desired amount of money and destroy it from the wallet, while the import process should automaticly transfer the funds to a new keypair and destroy the keypair.  This would also permit long term storage of funds in the like maner for the same person in such a way that the exported keypair did not need to ever be accesable from the internet, nor stored with an entire wallet.dat backup.  It could be encrypted by PGP and sent over email, or loaded onto a floppy and stored in a saftey deposit box.  For that matter, it could even be printed onto a paper hardcopy with the 2D scancode format and placed into a  firesafe.

ArtForz on IRC came up with a much simpler solution with the same result.


The private key is encrypted with AES-256. To create a code:
1. Get 60 bits of random data.
2. Generate a new ECDSA keypair.
3. Encrypt the private portion of the keypair with a hashed version of the random numbers.
4. Create the transaction shown above.
5. Write down the random numbers and transaction hash in base64.

To redeem:
1. Find the transaction in the block chain using the transaction hash (only a small portion of it is needed).
2. Hash the "password" that you received and use it to decrypt the private key.
3. Use the private key to sign a new transaction to yourself.
4. Get coins.

That's only 15-18 characters that you have to type in order to redeem! I believe that's less than a Tracfone card code.

The private key is used as a hash, not for authentication. I don't care if people can create a valid signature: I only care that doing this will take them a few minutes with the proof-of-work scheme.

Consider that Bitcoin blocks could be done in the same way. The hash is replaced with a signature. Signatures less than than the target are valid, and people publish the public+private key in the block for verification (the private key isn't necessary, but it does no harm when public-key cryptography is used like this). There would be no point in doing it this way of course, but it would be possible. The reason I'm doing it like this here is that only OP_CHECKSIG can read the transaction outputs.


Of course this isn't done for normal transactions. They're using the keys for authentication; I'm using it as a proof-of-work.

Why would you include a keypair in a transaction? Just to clarify - what private key do you use to generate the signature in the above transaction. Do you sign the transaction containing the private key with the same private key?

The moment you reveal the private key, you lose the ability to stop someone from impersonating you. If you send your card creating transaction to a bad node first, what's to stop the bad node from using the private key to create a new transaction crediting him and then sending that racing across the network?

Is this "private key revelation" just something you've introduced for your scratch-off card scheme or do you think that normal transactions reveal the private key?

ByteCoin

The person creating the card generates an ECDSA keypair. This consists of two pieces of data: a public key and a private key. Anyone who has the private key can make signatures that validate with the public key.

The card creator creates a transaction that contains both the public key and the private key. The private key is no longer really private, though it is still considered the "private key" portion.

The card creator also generates some random numbers. They write these down. They append to these numbers the first few bytes of this public key (or private key). They hash this and add it to the transaction.

The person redeeming the transaction gets a piece of paper with the transaction hash and the random numbers that were written down above. They find the transaction in the block chain. Reading the transaction, they find the public key. They append this to the random numbers on the piece of paper. This is the code.

The person redeeming the transaction also looks at the transaction and finds the private key (which is totally revealed any not really "private"). Using this pair, he creates and signs a new transaction to himself. He now has the coins (after some proof-of-work retries).

The keypair used here is public and not really owned by anyone. We are not using it as intended. It is just a method of delaying attackers. It is used very much like a hash. Surely a more elegant solution could be used if Script supported it.

Ok thanks for the prompt reply. There are just a couple of points I still don't get.


Please let me know exactly how the private key can be known to both card creator and redeemer.

The normal meaning of keypair is "public key and private key". The private key can't be made public, that's why it's called a private key. Please explain very carefully precisely who knows about which private keys and how you propose to use them.
 
It's the redeemer's keypair which signs the transaction which spends the scratch-off card. If it has just been generated by the redeemer then the network doesn't know the public key which should be used to check the signature hence you have to tell the network about it hence it's the redeemer's public key not the card creator's public key.

I very much suspect that you have some fundamental misconceptions about how public key cryptography works. Please think carefully and be excruciatingly clear in your reply to show where I am mistaken if you still think I am wrong.


ByteCoin

Perhaps you would find it useful to read:
http://www.bitcoin.org/wiki/doku.php?id=transactions


That's right. I think it would be very convenient to give/sell simple codes that can be redeemed instead of sending to an address. It follows the more traditional model of receiving money instead of sending it.

Various schemes such as this have been discussed, but they all entail either an electronic device or such a large amount of data that a QR code is required. The OP is about a way to do it with codes small enough to type.


Almost right, but replace "public key" with "transaction hash". The redeeming person is not taking over a keypair. They are collecting the output of a transaction. A similar collection process is done whenever you send a transaction -- you collect the coins that you're sending. In this case you would actually want to collect the output right away (make a transaction to yourself) so that the sender can't take it back. With the hash, you are able to verify that an appropriate output exists and has not been collected already.


The security of this would be horrible. I am definitely not proposing anything like this. Somehow, the rest of your post is an accurate summary, even though you believed this.


All current scripts check that you have knowledge of the private key for the public key which the output of a transaction was intended to credit.

OP_CHECKSIG checks that you've signed the entire transaction -- input and output. The output signature is the important part: it prevents a MITM from rewriting your transaction. Just a hash wouldn't give this protection, which is why the signature is necessary.

- The real code is on the card. The hashed version of it is in the publicly-available transaction that you will collect.
- The provided code is provided by someone when they try to collect the transaction.
- The private key is in the publicly-available transaction that you will collect. Maybe part of it is on the card.
- The target is specified by the person creating the card/transaction/code. A lower target is more secure, but it will take longer to process the proof-of-work for the redemption.
- The signature is made using the private key in the publicly-available transaction.


You can use part of the private key or part of the public key. Anything random that is known by both the card creator and the redeemer. It's added to the code given to the network. So if the code on the card is 1122 and the salt is 4, the real code is 41122. The hash of this is the hash in the transaction. This salted code is the code as the network sees it.


It's the key made public in the transaction. This keypair, being public, should be freshly-generated by the person making the card.


The card creator supplies the public key, not the redeemer.


The output is also signed. If this was not the case, all current Bitcoin transactions could also be stolen in the same way.


I'm working on a page on the wiki (to be named "script") that will list them all. It's all specified in script.cpp. You can't do that, though.

Thanks for going into a bit more detail. Unfortunately I believe you expect readers to have a lot of shared context to understand your explanation and I for one am still unclear. I'd very much like to understand though.

Please correct me if I'm wrong in any way in the following summary.

What we're discussing is minimizing the amount of typing required to redeem Bitcoin scratch-off cards. I imagine that a basic card shows the public key (or address) credited with Bitcoins so that anyone can check the value and that it's unspent once they type in enough characters into their card-savvy client to uniquely identify it from the block chain. The scratch-off bit protects the private key, most of which needs to be entered but the last few digits can be bruteforced by the client program to save you typing. It does this by trying all possible values of the rest of the private key until it matches the public key. Alternatively, if you've already accepted the card or you just really hate typing, you don't bother typing in any of the public key, you just type enough of the private key until the computer brute-forces the rest of the digits to find they match some public key in the block chain.

The point of your post is that a normal private key is too long to make it easy to enter, and your scheme involves less typing.
In order for the Bitcoin network to accept your transactions, you have to make sure that you can satisfy the conditions stipulated by the script of the "In" transactions that you're using. The vast majority of scripts effectively check that you have knowledge of the private key for the public key which the "In" transaction was intended to credit. The script checks this by making you sign something. What exactly? The idea being that only the holder of the private key can generate such a signature.

In your scheme the card references a transaction with a non-standard script. Since anyone can spend the card on recipt, the script can't require you to demonstrate knowledge of a private key. Instead you have to satisfy some other condition involving "the signature", "the code", "the real code", "the target".

The scratch-off portion reveals a shortish code, the hash of which is included in the script. The hash in the script is salted with something else in the script or otherwise publicly available to discourage "rainbow tables" attacks. What is it? The length of the code must sufficient to prevent exhaustive search by attackers in the time interval between the card-creating transaction being distributed to peers for inclusion in the block chain and the time when the card recipient is able to enter the code into his card-understanding Bitcoin client application.

You say the salt is "the first few bytes of the private key". Whose private key? If it's yours how does the card generator know it. If it's anyone else's how do you know it?

Then the script requires you to provide a signature less than a target value and provide the public key that allows people to check that it's a real signature and not some numbers you just made up. So the person spending the card has to increment a nonce and repeatedly generate signatures until they're good enough.

So, when you spend the card, your transaction provides enough information to allow the Bitcoin nodes to verify that your transaction satisfies the conditions of the script. The problem is that you can't send the transaction to all nodes at the same time and, if the first node you send it to is "bad" it could take the information in your transaction and use it as an "In" for a transaction crediting itself. It would then be a race across the network between the two transactions. The idea of forcing the client to generate a certain quality of signature is that the "bad" node can't generate a signature of sufficient quality before your transaction has reached enough honest nodes and is most likely to be hashed into the block chain first. This depends critically on exactly what is signed. The "bad" node can see the non-standard script in the block chain since the card-creating transaction was distributed. Could it generate the good quality signatures for all cards in advance? (And sell them to other "bad" but lazier nodes ) Could you tell us what information is signed please?

Note that part of the problem was that we couldn't send the transaction to all the peers at the same time. If you could send the transaction a byte at a time in round robin fashion then the problem would disappear! Another way around it is if you could make the satisfaction of the script depend on another transaction which has to be in the block chain - the details are hard to explain.

What numbers are available for pushing on to the stack and what operations work a the moment? Can you specify for example that a transaction using yours as an "In" must have another "In"?  

ByteCoin

I have mentioned this personally, as others before and after: We need to be able to import private keys into the running bitcoin process. This way you have your own bitcoin process, your wallet already there. You import the keys and the coins are yours. This does nothing to prevent double spending, of course, but make it really simple to transfer coins physically using usb keys or emails or whatever.

To prevent double spending, the import method would automatically transfer the coins in that key to a new bitcoin address from your pool. If it confirms, good, if not someone scammed someone, and you'll be playing the role of the latter

That's a great idea, but how would the receiver ever be certain that the wallet was unique without the need to immediately transfer the funds away from the wallet, destroy the wallet, and transfer them back?

That would be fun:  download money from a website, in the form of a file (bitcoin wallet).

Or more likely, some text encoding format of a wallet, similar to exporting a PGP key to an ASCII file.

The script functionality is limited. Some commands are disabled. It's still possible to do some interesting things with it, though.


I realized that the OP_DUP in my script is redundant. Take that out.

When you redeem, you publish the signature and the code (in that order). They are prepended to the script I wrote. To determine whether your transaction is valid, nodes go through these steps (moving left-to-right through the full script):
1. The signature, code, and private key are put on the stack.
2. The private key is discarded (OP_DROP). This is just data meant to be read by the person making the transaction, and is not necessary for verification.
3. The top code is replaced by a hashed version (OP_HASH256).
4. The real hashed code is put on the stack.
5. The the top two items on the stack (the hash of the real code and the hash of the provided code) are compared, and then these items removed (OP_EQUALVERIFY).
6. The public key is put on the stack.
7. The signature is compared to the public key (OP_CHECKSIG).

The script will evaluate to true if the provided signature is valid for the public key in the later part of the script (scriptPubKey) and the hash of the provided code is equal to the hash in the scriptPubKey.


Yes. Only the sender and recipient need to upgrade, though.


An attacker probably would win at that point usually. However, the question is whether the full private key can be recovered with a cost less than the cost of the number of bitcoins transmitted, and in less time than it takes for the code to be used by the intended recipient. Hopefully any attack would be too expensive. I am not familiar with partial-key attacks, though; it could very well be a trivial matter to recover a private key when you have 90% of it.


I'm trying to figure out the required length for the code. This is a similar case to figuring out appropriate password length, but with the important difference that each byte has much more entropy.


I just realized that this is possible now! I thought that all of the arithmetic functions were disabled, but actually only some of them are. You would use a script like this:

The person redeeming provides a signature and a code (in that order). It would evaluate like this:
1. The signature, code, and private key are put on the stack.
2. The private key is removed (OP_DROP).
3. The code is hashed (OP_HASH256).
4. The real code is put on the stack.
5. The real code is compared to the provided code, and both are removed (OP_EQUALVERIFY).
6. The signature is duplicated on the stack (OP_DUP).
7. The target is put on the stack.
8. If the signature is less than the target, 1 is put on the stack. Otherwise 0. Both items are removed.
9. If 1 is the the top item on the stack, go to 10 and 11. Otherwise, the transaction will not be valid.
10. The public key is put on the stack.
11. The signature is compared to the public key (OP_CHECKSIG).

This is assuming the signature can be converted into a bignum. Otherwise I think we'd need OP_SUBSTR, which is disabled.

So I believe it is right now possible (with a modified client) to transfer bitcoins using an ~8-character code! It'd probably even be safe to reduce that to 6 characters.

I wonder if we have already passed the point where a user-typed-in-arbitrary-key can be both secure from brute-force attacks and convenient to use.

If you make the key long enough to prevent brute-force try-every-possible-key attacks then typing it in gets really painful.

You can add proof-of-work, but attackers tend to have lots of CPU power (think botnets) and lots of time, and if you make the proof-of-work take more than a few seconds per attempt on a low-CPU device it gets really painful again.

I'm thinking some variation of wallet-on-a-USB-stick might be a more convenient and practical way of physically exchanging bitcoins.

I wonder if Ebay would let you sell USB sticks pre-loaded with Bitcoin, a snapshot of the block chain, and a "starter wallet" with X bitcoins in it...

That sounds fascinating. So the scripting language is fully enabled at the moment? I thought it was present but lobotomized.
Could you talk us through the little script you published?
I presume that this requires new clients? If not, how do you do this?


I disagree very strongly. I believe the computations you mention could be done in much less time than network latancies. There must be a cryptographic way of enabling secure cards or else they will fail. Your proof-of-work signature is a good start. What scripting functions would need to be added to support it?


I don't understand how this links with the previous bit of your post. Please explain.

ByteCoin