Off-chain anonymous transactions by secure transfer of private keys

[piotr_n]

So you already have an implementation?
Good for you, man!

If you need developers experienced in both; bitcoin and smartcards, let me know
It all can be done - the hardest part IMO is to find an authority that this community would trust.
Normally banks do it - but these people in here are all about not trusting banks

Most of the smartcard code is complete, yes (I would say around 80% of it). There's no code on the wallet side yet, I want to complete the smartcard part and freeze the functionality before I move on to the wallet side. I'm in the process of trying to raise some seed funds to allow me to work on this full time (getting it to this point took about 3 months of me working weekends and in-between other projects).

About the issuing authority, I mentioned a bit earlier that I intend to have multiple authorities/issuers certifying cards. The code cannot be open-sourced due to the NDA restrictions put in place by the hardware manufacturers (if you're worked with NXP before you know what I mean ), but I guess we can always share information and source with a third party / issuer if they are also under an NDA.

I could use some help with the development, just need to figure out the financials first, doing this part-time is annoyingly slow.

Yes, NXP tells me something.
Where I used to work we abandoned them, for Infineon.
Though it was probably more of a political decision, rather than a security concern

Working on "the wallet", think more about a terminal that can transfer keys from one card to another - something that can work offline.
A terminal might have two smartcard slots, but one (swapping cards) can work just as well.

IMHO, reliable offline card-to-card or card-to-wallet transaction is the key to a success of such an enterprise.
Because people who are online can live without such a solution.

[drazvan]

Is the tamper-resistance mostly hardware related, i.e. which of these 2 things
- read raw memory data from card and disassemble the chip, comprehend how the chip works and emulate it in software
and
- hack the resulting (probably still encrypted and highly obfuscated) executable
would be more difficult for the attacker?

In other words, I wonder if a pure software implementation of OtherCoin is possible (in principle).

I would say extracting the key is the hard part. The protocol is open, so once you have the key there's nothing stopping you from emulating a card. We're actually going to do just that as a way for users to try out the system before buying a real hardware card - instead of talking to a local smartcard (microSD inserted into the phone), they would establish an HTTPS connection to a server and send/receive data that way - it would work like a remote smartcard accessible over HTTPS.

This obviously doesn't offer the same guarantees (the entity running the server would see your requests to the virtual smartcard, so it could theoretically tell when you're paying someone and who you're paying - based on their public RSA key). So you would have to trust them considerably more than you would if you had a physical card in your phone, under your complete control.

[gmaxwell]

Taking the idea further— something which couldn't be done in the current othercoin design as I understand it but perhaps interesting for the future (e.g. if othercoin used 2of2 instead of additive homomorphism):

It would be interesting that when you load a coin into an othercoin if the device couldn't help you establish an nlocktimed refund that releases the coins back to you at some far future date. E.g. the device was willing sign a refund but only with the locktime established far out after the load time but less than the current refund time if there is one.  The existence of this refund would, of course, be communicated with the coin so you wouldn't accept a coin which was about to return to sender.

This would provide an incentive to periodically refresh your othercoins, as while doing so you could reset the refund clock.

The advantage of this is that the coins aren't lost if the hardware is lost, instead they eventually return to the last party to have collected a refund transaction from them.  It would be a way of achieving backup for these coins which doesn't compromise their non-doublespendability.

[piotr_n]

The problem with smart cards is that they don't have a calendar.
If you want a card to know what time it is, you need to tell it after each power on.
Normally people do it via a signed messages - in this case it would need to be signed by the issuing authority, I would say.
So a locktime, or basically anything time related, complicates stuff pretty much.

[solex]

Drazvan, excellent project!

The problem with smart cards is that they don't have a calendar.

Could this be done with an inbuilt micro-receiver for a GPS signal?

[piotr_n]

Could this be done with an inbuilt micro-receiver for a GPS signal?

You mean the same GPS signal that Iran spoofed, to land the US drone on their airfield?
Trust me, you don't want it Not to mention details like: GPS does not work inside buildings.

As I see it, the card shall only trust messages signed by its issuing authority, or messages from others cards (but only because they have public keys signed by a trusted issuing authority).

There is also a fairly easy solution to pop up a card, without a need for it to know time, parse blocks, check difficulty, or play with SPV.

1. The card generates a new bitcoin private key and outputs its public address, signed with the unique card RSA key - gives you this data via a terminal.
2. You send this information to the issuing authority and transfer the coins to the address.
3. The authority verifies the origin of the message and checks the balance at the bitcoin address. Likely they would charge a fee for it, to have a business case.
4. The authority sings a message (with its master key) confirming the balance at the given public address and sends this message to you.
5. Using your terminal again, you forward the signed message to your card, effectively popping up its balance, since by verifying the message the card confirms that the key contains a certain amount already.

But it is all about the trust to the authority and how well they can protect the master key.
This would be the weakest link and the master key leaking out would have been a deal breaker, for all the cards out there.
These kind of applications should normally have a life cycle - like a banking card; you just throw it away after a few years.
And the master keys should cycle - so even if some old master key leaks out, the new cards shall be safe.
Usually there is an even and an odd key - only one is used in a certain period, while the other one is being updated by any possible chance (e.g. while adding more balance to the card).

[drazvan]

A lot of things can be done by using an external oracle (in this case the issuing authority of the cards) - setting the time, confirming balances, etc. The problem with that is that it would make the system dependent on that authority and its uptime. It would also require signature master keys to be present on an Internet-connected server (or a separate set of keys that are only used to sign balance confirmations or the current time). I would like to keep the keys offline as much as possible (all cards will be certified completely offline and the master keys will never leave the computer used to sign/certify the cards).

Of course, there will have to be a server that hosts the CRL (Certificate Revocation List) but updates to that list would be very infrequent and the list itself could just be generated manually and hosted on multiple machines (or dropped on Amazon S3 for instance).

About the lock time, I think gmaxwell was talking about this: https://en.bitcoin.it/wiki/NLockTime , not an actual timer in the card. This could actually work because generating a Bitcoin transaction with 1 input and 1 output is considerably easier than implementing a full transaction parser/generator in JavaCard. The recipient of the funds could obviously refuse the payment if the key is "time bombed" this way and I would have to make sure that that single transaction the card generates is bulletproof (people will obviously ask if it doesn't leak their private key, etc). And of course, this would require the card to actually know the full private key (that is get the half that the wallet has generated as well) - so in theory the card would now know the Bitcoin address you are using, something that is impossible if it only holds just half of it and never signs anything.

Regarding the GPS question, I'm not sure what you're trying to achieve. The wallet (the smartphone) could log the GPS position, the exact time of the transaction, etc, but those would not be signed/certified by anyone. "Certified location" is a very hard problem - you would need a tamperproof GPS receiver, with spoofing protection, physically tied to the smartcard in some way (otherwise you could simply tunnel location requests to a remote location). So if that's what you're looking for, the answer is probably "no" for now. If you simply want to log where a transaction took place for your own use, your smartphone wallet can do that quite easily.

[adam3us]

Another alternative, if the device knows what the address of its private key is... is that it can give you SPV fragments to show that key being paid... and then you only have to have (possibly somewhat old) block headers, to verify the amount.

Well so long as we are relying on trusted things, one could have a virgin mined coin and a time-stamp authority using TPM hardware also, which would define just that coin is valid if its virgin (its address is in the coinbase/block that the card can present) and the public key is signed by a certified-as hardware contained key, and the difficulty of the mine is >= difficulty at that time-stamp (to prevent cheaper mining at historic difficulty rates.

Thats a looser definition of time-stamping as its not directly blockchain auditable, though it can easily be made indirectly blockchain auditable by including the time-stamping authorities signed master-hash into a bitcoin message in the block chain.  It is looser because doesnt quite adhere to the 21mil limit - its follows bitcoin difficulty but doesnt contribute to it.  To track it strictly you'd need to what gmaxwell said with SPV.


Btw I presume people also know about or recall firmcoin https://bitcointalk.org/index.php?topic=232898.0 by Sergio_Demian_Lerner, it also contains a private key, only in that case uses the hardware to sign transactions, and does do things with SPV information.  I presume he made at least a prototype from the initial post photo.


About the private key, and addative homomorphism, its not explicitly stated that I saw in the article or thread, but I think what is going on is that the smartphone app has the second half of the coin, to compose the address (as with BIP 38) except thats using ECDH (curve multiply) vs addative homomorphism (analogous effect).  Then the smart phone transfers one half of the key to the other smartphone, and the hardware key container transfers the other half (via hw certified RSA as described in this thread).  The key-half held by the phone cant be changed between transfers, without going via the block chain, so all previous parties who held the coin have enough to spend the coin online, once the coin private key is taken from a card.

[EDIT: and the purpose of this is like a poor-mans observer protocol like in Brands and other offline ecash systems: the card cant tell much because what it knows is not correlateable with the public key].

What about instead at each transfer the private key (composed of x+y where the public key is Q=xG+yG, x held on card, y held on smart-phone) is resplit as in proactive security at each transfer?

So far the design is smartphone and the card never know the full private key z=x+y mod n in one place, unless and until the coin is spent online (by removing it from the card).  To preserve that security assurance, the card can instead create r=random, send RSA(z'=x-r) to the other card, and r to the other phone.  Then the other phone learns y'=y+r and hte other card learns x'=x-r, and the private key and public key remain the same: z=x+y=x'+y' mod n.  But yet the previous smartphone owner does not retain power to spend the coin, even if he physically stole it back from you as he is missing y'.  The recipient smartphone will not consider the payment offline validated unless it can check that x'G+y'G=Q and that x'G is certified by the card.


(I used this mechanism in my still not yet posted, really must get around to editing last bit and hitting send, non-TPM model for this).

Adam

[piotr_n]

The problem with that is that it would make the system dependent on that authority and its uptime.

Only when you want to add more balance to your card - if you just want to read out the bitcoin private keys, it should be able to work outside the authority's IT infrastructure.
I mean: offline payments are supposed to be the biggest advantage here and if you make a card which you cannot pop up with more coins, people might be more reluctant to buy it.

It would also require signature master keys to be present on an Internet-connected server (or a separate set of keys that are only used to sign balance confirmations or the current time). I would like to keep the keys offline as much as possible (all cards will be certified completely offline and the master keys will never leave the computer used to sign/certify the cards).

Yes, this is a real problem.
Obviously you don't want to keep the super master key online - you must not, it's against any acceptable security practices.
So I was rather thinking about a solution where the master key would only be used in an offline environment, in some dark room behind a steel door..

But then how do you handle depositing more coins into a card?
You can try to address it by using a key hierarchy; there would be the super master key (kept offline, that never changes) and a second-level key that cycles (this one can be online, though it needs to be really secured).
Let's say that the 2nd level key would cycle every 3 months.
So a user of a card would need to "refresh" the card at least once a quarter (using some kind of online terminal) to get the key for the next quarter...
But in general the key update can just be done by the way of adding a new balance to the card - which needs to happen online anyway.

This gives you (the issuing authority) an additional control over every card that you have issued.
You can not only refuse to refresh/pop-up cards that you already have on the blacklist, but you can also get advantage of a subscription based business model.
E.g. if someone stops paying you a $1/quarter fee, he cannot pop up his card anymore, because you won't give him a fresh 2nd level key.
Though he can still read out the existing bitcoin private keys from the card (and spend his existing balance), because only pop-ups would requite a valid 2nd level key.

The quarterly refresh messages (unique per card) can be prepared offline - in a bulk.
Even if you have tens of millions of cards, doing it once a quarter isn't impossible, especially when you are on a subscription model, so you essentially get paid for it.

[drazvan]

Hi Adam,

The mechanism you described (which is pretty cool btw!) would protect against physical theft of the card by a previous owner, in the absence of any other security measures. But in the case of the OtherCoin, each card is protected by a 6 digit PIN code and you get 3 tries, so stealing the card doesn't get you anything unless you can also get the PIN code. The card is also physically inside the phone, so it would be hard to steal without the user noticing it (unless he leaves the phone unattended for a long time). Finally, previous owners have no way of telling that you did not forward that key to someone else - since there's no trace of the payment anywhere, they could steal your card only to find out that you've already spent the key that they have the other half for. So I think we're safe, at least in the current model. Of course, there's always the Rubber Hose Cryptanalysis method (http://xkcd.com/538/) - that is sure to reveal the PIN in record time .

[drazvan]

Piotr, adding funds to the card is simple - the wallet already knows the address that results from combining the public key on the card with the public key it has generated. It also knows the private key it has generated, just not the one the card has.

So it works like this:

The card generates a private key x and calculates the corresponding public key P. The card reveals P to the wallet but keeps x secret.
The wallet generates a private key y and calculates the corresponding key Q.
The wallet then calculates the final public key as P+Q and calculates the associated Bitcoin address. That is a plain Bitcoin address, it can receive funds from anywhere.
Whenever it needs to spend the funds, the wallet asks the card for x (the private key corresponding to P). The card reveals it and discards x and P.
The wallet then calculates x+y => the private key corresponding to the P+Q public key.

So the wallet knows the Bitcoin address, you can send funds to it just as you would to any Bitcoin address. So there's no need for a "top up" procedure, any Bitcoin wallet can be used for that.

Getting cards back or forcing people to go to specific locations to reload them would probably make most of them think twice about buying them in the first place. I want them to be able to load them up by simply sending funds via the Bitcoin network to their address, I want them to be able to pay offline (or mostly offline - like gmaxwell suggested).

I also don't want to force people to go through the blockchain at any time - if they choose to just pass keys around using the OtherCoin mechanism, they should be free to do so.

Also, key renewal cannot be done over the Internet - when we sign a key with the master key, we basically say "we've verified this card and it's physically and logically one of ours, with the restrictions we imposed". This is only done offline, at the time the card is manufactured. Of course, cards can have an expiration date (and there probably will be one, like 10 years or so) - at that time, the card would stop working as an OtherCoin but it could still be used to reveal its keys to be used on the blockchain.

[gmaxwell]

The problem with smart cards is that they don't have a calendar.

No problem there: When you load a coin give it a SPV proof that it's loaded, the bitcoin network provides the date.

[piotr_n]

The card generates a private key x and calculates the corresponding public key P. The card reveals P to the wallet but keeps x secret.
The wallet generates a private key y and calculates the corresponding key Q.
The wallet then calculates the final public key as P+Q and calculates the associated Bitcoin address. That is a plain Bitcoin address, it can receive funds from anywhere.
Whenever it needs to spend the funds, the wallet asks the card for x (the private key corresponding to P). The card reveals it and discards x and P.
The wallet then calculates x+y => the private key corresponding to the P+Q public key.

Sorry - could you please elaborate a bit more on this.

I though what we were talking about was the card being able to control the actual private key - thus acting as a wallet itself, without an external parties.

If I do understand it well, the solution that you are proposing is adding more credits to the card, though making these credits tied to a specific "wallet". Am I getting it right?

What I was talking about was the card having the full private key (and it's balance, got from the authority, signed by the 2nd level key) - thus being able to reveal+destroy such a private key offline, without an existence of any additional "wallet".

In such case, if you trust the authority and the security of the card's hardware, you can essentially move the private keys offline, and having the private keys carrying different amounts (like coins in your wallet), you can pay any amount to any party - all possible offline, with only a single card, protected by the authority's reputation.

[piotr_n]

The problem with smart cards is that they don't have a calendar.

No problem there: When you load a coin give it a SPV proof that it's loaded, the bitcoin network provides the date.

That's tricky.
You know that all the coins in the existence are born as a coinbase and I do not quite see it how a card can estimate a legitimacy of a coinbase while not having access to any reliable time source. Not to mention that it would need to follow a chain - which is hard for such a small piece of embedded hardware.
1MB that a single block can heave - for such a tiny card, its really a lot. And even if you do not parse entire blocks, one transaction can be as big as 100kb.

[gmaxwell]

The problem with smart cards is that they don't have a calendar.

No problem there: When you load a coin give it a SPV proof that it's loaded, the bitcoin network provides the date.

That's tricky.
You know that all the coins in the existence are born as a coinbase and I do not quite see it how a card can estimate a legitimacy of a coinbase while not having access to any reliable time source. Not to mention that it would need to follow a chain - which is hard for such a small piece of embedded hardware.

Verifying SPV proof is trivial in embedded hardware. It's just a linked list of 80 byte headers, hashing each and checking the prev and hash under target, it can be streamed so they don't need to be in memory the whole time.

In any case, this is getting a bit far afield of what the othercoin design is... there are a lot of potentials in this space.

[piotr_n]

SPV is definitely a path worth exploring.

But @drazvan, do you even have ECDSA and the Kobuz curve on your platform?

[drazvan]

Sorry - could you please elaborate a bit more on this.

I though what we were talking about was the card being able to control the actual private key - thus acting as a wallet itself, without an external parties.

If I do understand it well, the solution that you are proposing is adding more credits to the card, though making these credits tied to a specific "wallet". Am I getting it right?

What I was talking about was the card having the full private key (and it's balance, got from the authority, signed by the 2nd level key) - thus being able to reveal+destroy such a private key offline, without an existence of any additional "wallet".
In such case, if you trust the authority and the security of the cards hardware, you can essentially move the private keys offline, and having them covered different amounts of bitcoins per key, you can pay any amount to any party - all offline.

The card is just a microSD card, with no network capabilities. So it has to be plugged into something to work and that something is your smartphone. And in order to prevent the card (that you might not fully trust) from knowing what you are doing with your funds, the smartphone also generates a keypair (public + private key) that it combines with the keypair the card has generated to get to the final Bitcoin public key / address to use.

Of course, there's nothing stopping a wallet from just using what the card gives it (that is take the public key from the card and run it through SHA256/RIPEMD and generate an address).

The card always controls its part of the private key and without that part the wallet cannot make payments but can receive payments and monitor the blockchain. It's also the wallet that runs all the Bitcoin functionality (checking balances, sending funds, etc). The card is just a private key generator that either keeps the key to itself or sends it securely to another card.

Does that answer your question? You can't go completely without a wallet, you would need at least a screen and some network connectivity. But the wallet will not be a specific wallet, any wallet should be able to just send/receive requests to/from the card. It's a simple library to send/receive APDUs (http://en.wikipedia.org/wiki/Smart_card_application_protocol_data_unit) through filesytem operations.

[drazvan]

SPV is definitely a path worth exploring.

But @drazvan, do you even have ECDSA and the Kobuz curve on your platform?

Yes and yes. They are both there. I already have them working (ECDSA on secp256k1) but the only place the Koblitz curve is used is to calculate the public key corresponding to the private key received (to check that the sender didn't just send a random number but the actual private key to the public key it's pretending to use).

[drazvan]

The problem with smart cards is that they don't have a calendar.

No problem there: When you load a coin give it a SPV proof that it's loaded, the bitcoin network provides the date.

That's tricky.
You know that all the coins in the existence are born as a coinbase and I do not quite see it how a card can estimate a legitimacy of a coinbase while not having access to any reliable time source. Not to mention that it would need to follow a chain - which is hard for such a small piece of embedded hardware.

Verifying SPV proof is trivial in embedded hardware. It's just a linked list of 80 byte headers, hashing each and checking the prev and hash under target, it can be streamed so they don't need to be in memory the whole time.

In any case, this is getting a bit far afield of what the othercoin design is... there are a lot of potentials in this space.

It doesn't have to be done in the card, that's the job of the wallet. The card secures the key, the wallet knows about balances. Once you send the key to the recipient, his card gets the key and the wallet verifies that the public key / address has the expected funds on it. The card simply verifies that the received private key corresponds to the public key and that it has never been revealed, that's all. The wallet is the one that checks the balance (either by parsing the SPV chain or actually looking at the blockchain) and confirms that the funds are really there (of course, there could be _more_ funds than it expects if someone sent additional Bitcoins to that address after the sender created the proof, but I guess the recipient would not mind ).

[drazvan]

I just realized, an easy way to think about all this is if you're familiar with GSM networks - the SIM card (a smartcard) secures the key that is used to identify you to the network. It does not speak the GSM protocol, it cannot talk to towers or call numbers or receive texts. It just securely runs an authentication protocol with the network, using the phone to relay its messages. The SIM card never knows if your subscription is even active or how much credit you have (if it's a prepaid account).

OtherCoin works in a similar way - it only secures keys and offers some guarantees regarding their status (never revealed before). The wallet runs the Bitcoin protocol and handles everything else. The only thing it cannot do itself is sign transactions to send funds away, it asks the card to reveal its half of the key or just send it to the other card in encrypted form.