Bitcoin Forum
December 04, 2016, 06:18:21 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Decentralized Bitcoin scratch-off cards  (Read 5735 times)
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 20, 2010, 03:55:18 AM
 #1

When talking about physical Bitcoin cards/tokens, most people assume that either a central server or use of QR codes would be needed to redeem the bitcoins. However, it is possible to use Bitcoin's scripting system to make bitcoin transactions redeemable with a short code, without any centralized server.

The person who is creating the physical Bitcoin card creates a transaction with an output like this:
Code:
<most of private key> OP_DROP OP_DUP OP_HASH256 <hashed code> OP_EQUALVERIFY <public key> OP_CHECKSIG

Then to redeem this transaction, the person who receives the card creates a transaction to himself with an input containing the code and signature. The code and the rest of the private key are on the card.

I imagine that a Bitcoin scratch-off would have the full transaction hash on the front and the code/key under the scratch-off portion in base58. To redeem, start typing the hash into your Bitcoin client until it tells you that it has enough to identify a single transaction (only 4-8 bytes are necessary). Then type the code/key. The money is instantly yours, with no central server necessary. If you have a computer handy while buying the card, you can verify that a card is still valid by looking at the hash on the front (the code could be fake, of course).

The first few bytes of the private key can be used as a salt.

Without the public/private keys, it would be easy for any man-in-the-middle (including any Bitcoin node) to rewrite your transaction to himself after receiving it. It's still possible for him to do this, but he would have to preemptively brute-force the full private key from the portion in the transaction, and then he would have to re-sign his new transaction on-the-fly in less than a few seconds. I think this makes the attack difficult enough for the scheme to be usable.

This can be significantly improved if the mathematical script functions are enabled (alternatively, I believe OP_SUBSTR could do the same thing):
- The output of the first transaction contains the full private key, but it requires that the provided signature start/end with some number of zeroes.
- To redeem, you need to modify and re-sign your transaction (using a nonce value with OP_DROP) many times to get a signature that meets the requirement. The number of zeroes required should be set so that this calculation takes only 5-10 minutes on most computers.
- To modify your transaction, the attacker needs to re-sign the transaction. However, he can't do it in less than the 5 seconds or so required because of the proof-of-work.

An 8-byte code would probably be sufficient. Each byte has 256 different possible combinations instead of the 96 with standard ASCII, so this would be stronger than a 16-character totally-random password. I'm unsure about the security of giving away a partial private key; if it's only possible to brute-force, 16 bytes would probably be enough, though I'd probably err on the side of caution with 32 bytes.

So if the arithmetic functions are enabled in Bitcoin, that's less than 20 characters you'd have to type: 8-10 characters for the transaction hash and 8-10 characters for the code. Anyone could generate these codes. It might be a useful cash-alternative among people who already trust each other, and it'd be very convenient for selling bitcoins at physical shops.

(Edit: realized how to use a salt without OP_CAT.)

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
1480875501
Hero Member
*
Offline Offline

Posts: 1480875501

View Profile Personal Message (Offline)

Ignore
1480875501
Reply with quote  #2

1480875501
Report to moderator
1480875501
Hero Member
*
Offline Offline

Posts: 1480875501

View Profile Personal Message (Offline)

Ignore
1480875501
Reply with quote  #2

1480875501
Report to moderator
1480875501
Hero Member
*
Offline Offline

Posts: 1480875501

View Profile Personal Message (Offline)

Ignore
1480875501
Reply with quote  #2

1480875501
Report to moderator
Each block is stacked on top of the previous one. Adding another block to the top makes all lower blocks more difficult to remove: there is more "weight" above each block. A transaction in a block 6 blocks deep (6 confirmations) will be very difficult to remove.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480875501
Hero Member
*
Offline Offline

Posts: 1480875501

View Profile Personal Message (Offline)

Ignore
1480875501
Reply with quote  #2

1480875501
Report to moderator
1480875501
Hero Member
*
Offline Offline

Posts: 1480875501

View Profile Personal Message (Offline)

Ignore
1480875501
Reply with quote  #2

1480875501
Report to moderator
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 28, 2010, 03:20:51 PM
 #2

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?
Code:
<most of private key> OP_DROP OP_DUP OP_HASH256 <hashed code> OP_EQUALVERIFY <public key> OP_CHECKSIG

....

 To redeem, start typing the hash into your Bitcoin client until it tells you that it has enough to identify a single transaction (only 4-8 bytes are necessary). Then type the code/key.
I presume that this requires new clients? If not, how do you do this?

Without the public/private keys, it would be easy for any man-in-the-middle (including any Bitcoin node) to rewrite your transaction to himself after receiving it. It's still possible for him to do this, but he would have to preemptively brute-force the full private key from the portion in the transaction, and then he would have to re-sign his new transaction on-the-fly in less than a few seconds. I think this makes the attack difficult enough for the scheme to be usable.

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?

An 8-byte code would probably be sufficient. Each byte has 256 different possible combinations instead of the 96 with standard ASCII, so this would be stronger than a 16-character totally-random password.

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

ByteCoin
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
October 28, 2010, 06:48:09 PM
 #3

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...

How often do you get the chance to work on a potentially world-changing project?
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 28, 2010, 07:04:56 PM
 #4

Quote
That sounds fascinating. So the scripting language is fully enabled at the moment? I thought it was present but lobotomized.

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

Quote
Could you talk us through the little script you published?

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.

Quote
I presume that this requires new clients?

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

Quote
I disagree very strongly. I believe the computations you mention could be done in much less time than network latancies.

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.

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

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.

Quote
What scripting functions would need to be added to support it?

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:
Code:
<private key> OP_DROP OP_HASH256 <hashed code> OP_EQUALVERIFY OP_DUP <target that the sig must be below> OP_LESSTHAN OP_IF <pubkey> OP_CHECKSIG OP_ENDIF

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1470


View Profile
October 28, 2010, 09:45:55 PM
 #5

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

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.


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
October 28, 2010, 10:51:11 PM
 #6

II'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'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?

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
nelisky
Legendary
*
Offline Offline

Activity: 1554


View Profile
October 28, 2010, 11:18:51 PM
 #7

II'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'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?

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 Sad
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 29, 2010, 01:42:36 AM
 #8

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 Wink ) 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
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 29, 2010, 02:26:45 AM
 #9

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

Quote
What we're discussing is minimizing the amount of typing required to redeem Bitcoin scratch-off cards.

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.

Quote
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.

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.

Quote
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.

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.

Quote
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?

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.

Quote
Could you could clairfy what these things are and where they come from please?
- 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.

Quote
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?

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.

Quote
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?

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

Quote
and provide the public key that allows people to check that it's a real signature

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

Quote
Could it generate the good quality signatures for all cards in advance?

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

Quote
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"?

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 29, 2010, 02:59:26 AM
 #10

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

Quote
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?
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.

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

Quote
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?
It's the key made public in the transaction. This keypair, being public, should be freshly-generated by the person making the card.
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.
 
The card creator supplies the public key, not the redeemer.
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
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 29, 2010, 03:10:20 AM
 #11

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 29, 2010, 03:26:49 AM
 #12

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.
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?

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).
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
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 29, 2010, 03:34:20 AM
 #13

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.

Quote
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?

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 29, 2010, 09:10:51 PM
 #14

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

Code:
<encrypted private key> OP_DROP <pubKey> OP_CHECKSIG

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
October 29, 2010, 11:48:43 PM
 #15

II'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'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?

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 Sad

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
November 18, 2010, 02:32:28 AM
 #16


Quote
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.

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.

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
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
November 18, 2010, 02:47:20 AM
 #17

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?

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
November 18, 2010, 03:24:51 AM
 #18

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?

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 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
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1470


View Profile
March 17, 2011, 09:05:57 AM
 #19

See http://bitcointalk.org/index.php?topic=4555.0 for an implementation of scratch-off cards.

Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
March 17, 2011, 08:12:24 PM
 #20

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.

Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!