Bitcoin Forum

Hello everyone,

I've posted a message on the Project Development thread at https://bitcointalk.org/index.php?topic=319146.0 but it didn't get much attention, but there's a technical side to it that I'd like to submit to you and hopefully get some feedback.

To summarize, I'm in the process of developing a system called OtherCoin that allows anonymous off-chain payments by transferring private keys between tamper-proof smartcards. The private keys are either generated internally by the smartcard or received over an RSA-encrypted channel from a similar smartcard. The smartcard just certifies that any key it sends over the RSA-encrypted channel has never left the card in unencrypted form and has never been revealed to the wallet. The smartcard can reveal the private key to the wallet at any time - when it does that, it removes it from its secure storage, effectively making it a plain Bitcoin private key.

A short whitepaper is available at http://www.othercoin.com/OtherCoin.pdf . It explains more than I can do in a single post here.

The system has been designed to work in the absence of trust (you do not have to trust the smartcard, you always combine the public keys it generates with a second set generated by the wallet, so that the card has no idea what your actual Bitcoin public key / address is). And since it's a smartcard, it obviously can't communicate to the outside world by itself, so it cannot leak information. It never signs transactions, its purpose is to only generate private keys and store them securely, then either fully reveal them to the wallet or securely transfer them to the storage of a similar card.

I would appreciate some comments from the more crypto-knowledgeable developers here. I think it's currently the only off-chain payment system that does not rely on a central service/server - the issuer of the cards could go out of business and the system could continue to work indefinitely. And since transactions never touch the blockchain, they are invisible to the Bitcoin network (and your friends in law enforcement) - they are strictly point to point between the payer and the payee, no record is written in the blockchain or anywhere else.

Any ideas, comments and criticisms are welcome.

Thank you,
Razvan

Please say tamper-resistant.

Otherwise you are overselling the possible.

There is absolutely a place for that kind of system, but having a reasonable dialog requires being frank about precisely where the security breaks down.  E.g. if the tamper resistance is compromised, or the issuer cheats and issues fake cards or leaks their key, the result is a class break which renders all othercoin smartcards insecure and only useful for direct redemption to Bitcoin (because you couldn't trust if they were doublespends otherwise).

In general, it sounds like a fantastic idea.  I think it would also be neat if future Bitcoin hardware wallets had a smartcard slot that enabled them to host an othercoin card. (bitcoin hardware wallets are not as tamper resistant, but have important UI elements that protect you from compromise of your host).

My apologies, tamper-resistant is more accurate. The cards we plan to use are certified at the EAL 5+ level (http://en.wikipedia.org/wiki/Evaluation_Assurance_Level) which I understand to be fairly high - maybe not high enough for military apps but definitely designed to withstand casual hacking attempts.

Thank you!
Razvan

Also, the plan is to eventually get more than 1 entity certifying/signing the device key - in order to keep everyone honest. For instance, one of the entities signing the cards could be the Bitcoin Foundation or one of the large mining organizations. We would also obviously share the sources with them (but that would have to happen under NDA given the strict requirements of our NDA with NXP - without that we wouldn't have access to hardware-accelerated crypto and everything would be painfully slow, plus that we would have to add SPA/DPA (http://en.wikipedia.org/wiki/Power_analysis) countermeasures ourselves).

Petertodd would probably recommend bonding the cards in some (or multiple ways).

One way would be to make every card contain a shared bitcoin private key (same key in all cards) for some large amount of Bitcoin, visible sitting in the chain. The card could prove that it contains the key by being willing to do a bitcoin-signmessage for the key.

If someone can compromise your tamper resistance, they can obtain the coin and in doing so would alert everyone that the tamper-resistance has been compromised at least once.

There is an alert mechanism already built into the system - basically, the wallet gets a list of the public keys that the OtherCoin card claims to have secure private keys for, then monitors the blockchain for any transactions involving those addresses. If funds ever move out of any of them, it triggers an alarm and then we know the security has been breached somehow since the private key is supposed to have not been released to anyone (the current user can actually prove it by showing the OtherCoin card with the private key inside, in its "secure/unreleased" status).


I'll look into the bonding idea as well, thank you!

Thats kinda bad for privacy.  You could use a cryptographically secure bloom filter (http://www.tdp.cat/issues/tdp.a015a09.pdf) to improve privacy, but it's probably asking too much for your CPU power.

Interesting, done right you could probably make it so your alert mechnism wrote a cryptographic proof that could be showed to other people.

I was also thinking of something similar (draft post sitting in another tab), not skimmed your paper yet though.  I think I can get it to work, pseudonymously, somewhat online verification, but with untrusted open spec hardware, that anyone would be invited to produce and load bitcoins onto.  So the design parameters are a bit different.  But I share your excitement for physical electronic non-clonable coins (though I did not try to increase bitcoins privacy model in my idea) and encourage you if you're an operational guy who actually builds things go go for it :)

Specifically about your proposal and question the perf requirements of your card, I think you are not taking advantage of existing known technology.  Read about Stefan Brands observer protocol, chapter 6 (whole book online as pdf in chapters):

http://www.credentica.com/the_mit_pressbook.html

[EDIT: its long and full of crypto, but read 6.5.1 last para or two; and 6.5.4 shows you what he's thinking this is good for "bearer certificates" = offline transferable pseudonymous ecash.]

In short it gives you a way to have a smart card that does something very cheap (like one 256-bit mod mul and 256-bit mod add to compute cx+w mod n (a contribution to the signature)  Because of the inflow/outflow security arguments the card has no visibility into your privacy, its tamper resistance only protects double spending.  

Furthermore its offline spend compatible using limited-show protocol, which allows things like retep's comments about good behavior bonds.  You can put the private key for a high value coin (eg $10,000) in the private key certificates in such a way that if a single double spend occurs (which can only happen as a result of hacking a card) a simultaneous equation is released that allows recovery of the $10,000 private key (that is the basis of the limited-show protocol).

Brands protocols are defined on Schnorr signatures (or ECSchnorr) and of course bitcoin uses ECDSA.  It might be within the realms of possibility that you could achieve something analogous though DSA is a complexification of Schnorr that does nothing for security and just limits flexibility.  Brands also has an RSA group variant but that doesnt help the compatibility.

Adam

btw I its not so clear in the book, and I reinvented it in my 1995-2005 pre-bitcoin attempts to find a way to deploy a decentalized anonymous ecash, as specified what he is saying is actually not offline respendable, only offline spendable; ie after you've done your spend, before you can respend, you have to deposit the funds in an issuer bank.  (And in bitcoin or zerocoin or the 1999 Ta-Shma & Sander "auditable anonymous electronic cash" paper there is no central bank, but you have to send it to the blockchain/zerocoin mix/shared blackboard respectively, but the dependency is still present).

What I figured out is you can offline respend without deposit (without going online) using 0-value coin collection as the initial witness.  Very excited when I figured out that in 2000, and I asked Stefan about it, but it turns out there was a masters thesis on this topic and its mentioned in a footnote somewhere in Brands PhD thesis/book referenced above.

Anyway it seems to me you're more interested in offline re-spendability so you need to use that follow-on invention/re-invention.

Why I did nothing with this protocol (eg like rush off and implement it with B-money) is I was thinking it was not good enough - its necessarily, like bitcoin, pseudonymous, and publicly linkable, which I considered, and still do consider to be a privacy problem (and in bitcoin whether you believe in privacy or not, a fungibility problem in addition, hence all the debate about zerocoin, coinjoin, mixers and taint, whether you actually even want anonymity or not, those security concerns of fungibility and anonymity are actually orthogonal - you can have fungibility (via coin anonymity) with pseudonymity, or escrowed identity and other variants just fine).  Btw there is a difference between payment confidentiality and pseudonymity/anonymity also, you can have payment confidentiality with or without pseudonymity/escrowed identity pseudonymity/anonymity.  Bitcoin has limited payment confidentiality (you have to work hard with wallet control, which is not implemented, and disciplined fund separation, and mixes/coinjoining is of apparently statistically weak value according to the data analysts who have looked at the network flow statistics.  And thats a problem.  If nothing else we need to make bitcoin payment amounts confidential (eg homomorphic value encryption).  And even payees is extremely invasive if you think about it.  Oh the public can see you bought an ebook from this publisher.  Or you bought a condom pack from this supplier.  etc  Its ridiculously invasive as is, and if your credit card issue or bank account put your statements online like the block chain there would be a public outcry.

Also I have to say I am not someone convinced by the offline respendability security argument.  Even if there is a fidelity bond, the problem is offline respendable card is a license to print money, and people will just spend a multiple of the fidelity bond or try to.  One somewhat defense is that if multiple people have offline respenable money flowing around, some of them are going to convert it to online ("deposit" it) and as soon as that happens the double-spend hw hack is blown.  You want to pass a "this key and card series hacked" protocol revocation cert through the network, and switch to the ciphersuite/keyset B while working on deploying card C or firmware upgrade C.

Adam

Yup. There are more sophisticated ways of doing bonding, but I think for OtherCoin just doing the above is the way to go for v1.0 if you're pretty confident in the hardware. Just be clear to market this stuff for low-value, low-security-required applications initially and go slow with your expectations.

Regarding trusted hardware in general, people have this mistaken idea that the idea is fundamentally flawed because the secrets will always be possible to exploit. What they don't realize is that 60 years ago you would have made the exact same argument about cryptography: "This encryption business will never work because mathematics will always be broken eventually." In the case of trusted hardware we're still not there, but it certainly in theoretically possible to build hardware systems that impossible to extract secrets from, simply because at some point you've built a circuit whose physical dimensions are so small that the only way to probe it is with the physical structures already built into it. I work in analog electronics myself, and there's lots of situations where its physically impossible to probe a circuit and determine what state it is in because physics simply does not allow you to do so.  These limitations are every bit as real as the mathematical limitations that prevent someone from spending a Bitcoin they don't own, and future hardware designs that use them fully can and will be secure.

It's a nice idea, but as you say yourself "The only trusted authority is the issuer of the OtherCoin card".

So first of all you need to trust an authority.

Second, you need to have some kind of making sure that the card is not just pretending to be issued by an authority - this I guess you can do by putting the authority's private key inside the card and telling it to sign messages with it.

But the third problem is (and I had worked with smart cards for awhile) that basically every smart card can be hacked - it is only a matter of time and money.
So eventually someone will manage to get the authority's private key out of it and then will be able to make his own, fake cards.

And on top of that, there is always tha ever lasting: how can you even trust an authority? :)

But the idea is appealing and probably worth exploring.

In practice, secure hardware seems to be secure enough for many transactions. EMV is a successful system and AFAIK all the attacks against it are protocol attacks, or exploiting flaws in the terminal hardware or banking backend software (like poor RNGs). I've yet to hear about criminals decapping chips en-masse and exploiting the system that way, despite massive incentive to do so.

If you could obtain that trust, then I think a MintChip style secure hardware platform is a great way to do off-chain, off-line transactions. I hope it won't be necessary due to the increasing prevalence of internet connections and smartphones, but if it does prove useful, I think it'll work fine.

I would not call the guy a criminal, but... http://www.youtube.com/watch?v=Qk73ye2_g4o

For the application we are talking about, all it takes to extract the authority's private key is to successfully hack one card.
You might destroy hundreds of thousands of them, on the way there, but all you need is the master key that is shared among all of them.
So one is enough and you can make millions of fake ones ever since that moment.

Piotr_n, there is no private key that all the cards share. They all share the public key of the issuer in order to be able to verify other cards and ensure that the Bitcoin private keys are only transferred to cards issued with the same restrictions and running the same software.

Each card comes with its own "device key" (I think this is called an "endorsement key" in TPM world - see http://en.wikipedia.org/wiki/Trusted_Platform_Module ). The root private key (used to sign the endorsement keys) is definitely not present on any of the cards.

As I've described earlier, the plan is to raise an alarm when we detect a doublespend (meaning one of the cards was compromised). We also plan to have a CRL (http://en.wikipedia.org/wiki/Revocation_list) that we can use to mark a card as compromised.

Right now, the OtherCoin cards do not keep track of where they got the keys from (I mean they do verify the sender but they don't store it), but they could - they could create a chain of public keys indicating the previous owners of that Bitcoin private key (stored securely in the card, not released to the wallet). When the wallet detects an external spend for a key stored in its OtherCoin, it can essentially ask the card to release this chain and we can then blacklist all the cards in the chain (blacklisting would not mean locking them out of their funds, but forcing them to go through the blockchain for their transactions). Since we cannot tell exactly which card from the chain has been broken (but one definitely has been broken if we ended up with a key that has been spent externally), we blacklist them all.

I'm still reluctant to implement something like this since it would give quite a bit of power to the entity controlling the CRL - if implemented, each blacklist would have to be properly documented.

That's actually the plan, but we need to make sure that the person reporting the hack is not the person that has actually hacked the card. If we have a physically intact card that contains a private key that we've seen a spend operation for on the blockchain and the card can keep track of the previous owners of that private key, it can be asked to reveal that chain of previous owners. If two or more physically and logically intact OtherCoins report this, we can compare the chains and find the actual card that has performed the double spend.

The wallet will most probably employ Bloom filters to monitor the blockchain - but most wallets already do that, don't they? The wallet knows the public keys / addresses to look for and it's up to it to fine tune the Bloom filter to not reveal the exact addresses it's looking at. I wouldn't want to implement that on the smartcard.

Oh, OK.
So each card would have a unique private key and its corresponding public key, that would be signed by the issuing authority?

Now it starts making much more sense.
This can indeed work - as long as the private key used to sign the public keys of the cards they manufacture does not leak out of the authority.
Which is again: usually only a matter of time and money... :)
But OK - let's assume that it won't leak out.

In such case I have another concern.
From what I understand moving bitcoins from one card to another means sending the key from card A to B - storing it in card B, while destroying it in card A.
But is there some reliable method to avoid destroying the key in A too soon, or too late?
If you destroy it too soon, the coins will get lost - if you do it too late, you might end up with the same key being owned by two cards.

Piotr, the way it works is that there are two separate operations. The first one (called REVEAL) takes the Bitcoin private key out of the secure storage, encrypts it with the RSA-2048 public key of the recipient, then moves it to a public buffer (no longer in secure storage) that the wallet can read it from as many times as it wants. Once the wallet has successfully forwarded that encrypted key to the other end, it issues a second command called REMOVE that clears the public buffer. The Bitcoin private key is erased from secure storage as soon as REVEAL is called, but it is still available in its encrypted form (decryptable only by the recipient) in the public buffer until REMOVE is called.

So in the case of a communication breakdown, the sender can keep reading it from the buffer (or just cache it internally since it's encrypted) and retry sending it to the recipient that is now the only entity capable of recovering that Bitcoin private key.

The scheme also does replay protection by using a nonce sent together with the RSA public key (preventing you from resending an old recorded payment message to a recipient to convince him to reimport the key into its private storage).

Cool - thanks for explaining.

So REVEAL removes the Bitcoin from the card's balance storage, though keeps it in the card's NVM, encrypted with the recipient's RSA.
The recipient can request this RSA encrypted key as many times, as it wants - until it gives the REMOVE command, which essentially frees the memory in card A.

Yeah, I like this idea.
And sorry for not reading through carefully, at the first time, asking these questions instead. :)
But it's all clear now and I like it - I think it can work.

What is the protocol to establish an authenticated and encrypted channel between the smart cards that is resistant to MITM attacks?

Presumably the cards must present a certificate signed by a trusted (by the card) authority.

No trusted third party server – information is secured by each smartcard, there is no central server to be trusted with transaction details or that the system depends on for its operation.

A third party certificate authority which certifies the cards as being ones that will respect the anti-doublespending requirement.

Otherwise I just load one of these keys onto a fake card which double spends it. The tamper-resistance only matters if you actually can tell that you're talking to one of these tamper resistant cards.

Exactly. The recipient of the funds presents his signed RSA-2048 key signed by the issuer (us) and a nonce. The sender verifies the signature (to ensure that it comes from a trusted card), then uses its own RSA key to sign a message containing the Bitcoin private key + Bitcoin public key concatenated with the nonce and the destination address, then encrypts the message with the recipient public key and sends the encrypted data together with its own signed public key to the wallet.

So it basically signs a message saying "I hereby certify that the key <BITCOIN_PRIVATE_KEY> with corresponding <BITCOIN_PUBLIC_KEY> has been transferred via an encrypted channel to <RSA_DESTINATION_KEY> with a random nonce of <NONCE>", encrypts it and sends it over to the other side.

The recipient checks the certificate of the sender, then decrypts the message, compares the nonce to the one it has sent out (to prevent replay attacks), compares the destination address to its own (to prevent replays of messages sent to someone else), compares the public key with the one it computes locally from the private key, verifies the signature, then stores the key into its private storage.

I'm aware that there is a lot of redundancy in there (the Bitcoin public key can always be computed from the private key), but it helps keep parties honest.

Correct, the only time the issuer is involved is at manufacture time when the RSA keys identifying each card are securely generated on-card and stored, then their corresponding public keys are signed by the issuer and the certificates are also stored by the card to be presented to other cards.

Just as gmaxwell said, each card needs to make sure that it's talking to a similar card, not to a generic chip with fake RSA keys on it.

But how do you see the accounting part?
If the only thing the card can transfer is a Bitcoin private key, then it should be somehow known how many coins are there, behind this private key..
How do you see this?

That's the beauty of it... it doesn't ... the card never knows anything about Bitcoins or balances or anything like that. That's the job of the wallet running on your smartphone or whatever you have the OtherCoin card inserted into. The wallet acts like any other "watching" wallet, it can monitor balances, etc. It's only when it tries to pay from that address that it needs the private key - and it can either ask the card for it (in which case it's removed from secure storage and the wallet just uses it on the Bitcoin network) or it can ask the card to securely send it to the recipient's card (in which case it is encrypted with the recipient's RSA key and given to the wallet in encrypted form to be sent to the other end).

The card cannot sign Bitcoin transactions and only acts as a very "stubborn" Bitcoin key generator - you can ask it to generate a key, it will give you the corresponding public key but keep the private key secure, allowing you to do anything other than transfer the funds away. It's the wallet's job to monitor the blockchain, establish balances and communicate to the recipient (since the card has no communication capabilities other than its physical interface to the smartphone using the microSD slot).

I am thinking whether it would be possible to use such a card for offline transactions.
I mean, if you arm it with private keys that have access to some predefined amount of coins (e.g. 0.1 BTC each) - then you could essentially trade such a credits offline.

Right, so what you need to do is have a snapshot of pre-existing coins that are in circulation in this system. Today you could accomplish that with just a copy of the utxo set. (e.g. only about 250 mbytes of data)

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.

There is some online preparation, but the actual payments can be offline.

Yeah.
If you assume a trust in the authority that made the card, then you can as well ask the card itself how many coins are covered by a private key it gives you.
it should give you the info signed with its private key, that is signed with the authority's private key - so it's all about the trust to the authority and you can move coins offline.

It's a brilliant idea, @drazvan

One possibility though is making so that the authority doesn't have to fill it.   Card generates a private key, and then won't let you do anything with it until you provide the card with SPV proof (e.g. txn, fragment and 200 blocks of some suitable minimum difficulty) that the private key it generated has been paid.

And then you can pop it up later, after it has already left the factory...

Seems like we're creating history here ;)

So if someone brings out a new card after my card was issued and I haven't got the certificate for this new card stored on my card, then what is the protocol to establish authenticity and encryption?

If I might answer, since I think I already understand... :)

There is one master key - and its private part is kept by the issuing authority.
This key never changes and its public part is known to everyone.

You talking to a new card, just verify if the public RSA key the card gives you is signed with the authority's master key.
If it is - you assume the card is legit and anything it tells you is backed by the authority.

Since it isn't easy to hack a card, each time such an event would happen, its unique (though signed by the authority) key can be published and added to the blacklist - and the public blacklist would be updated from time to time by any party who would like to accept such a cards, thus minimizing the loses and discouraging the hackers.

Well, keep your enthusiasm bounded: This is strictly less secure than Bitcoin itself. If someone compromises a single card then the whole infrastructure is busted: Everyone becomes potentially vulnerable to double spending by an evil device which has seen the private keys they're holding, so they'd have to go redeem their coins on the network and pay them into new, hopefully more secure, cards.

It's a absolutely fantastic trade-off though: the reduction in security comes with privacy and convenience improvements. Even online, its useful for allowing instant transactions.

I'll make the idea even stronger:  Once you support in-field loading, it should be possible to "refresh" the coins on the card by spending them and doing a new in-field load.  If you successfully do that the coins you have refreshed are protected from double-spending by earlier holders.

Periodic refreshing would prevent a situation where someone runs a "spy card" that remembers a lot of private keys and does a lot of transactions and then suddenly one day captures up all the non-redeemed coins on the keys they've seen.

Of course. But I believe we are rather talking about small payments here.
It obviously shall not be used for million dollar payments, but can be very handy for tens of dollars payment - hacking a smart card for such a small amounts is just unprofitable.

In the current implementation, the card does not know anything about Bitcoin balances (it cannot parse transactions or do anything Bitcoin-related). It doesn't even know the actual address you're going to use (since that is always the sum of 2 public addresses - one that it generates and another one that the wallet generates).

However, the wallet holding the OtherCoin card does know the address, so part of the protocol could be demonstrating to the other wallet (not the card) that the funds are there. This could be done completely outside the smartcard - a wallet to wallet transfer of transaction data to prove that a certain output has a certain value, just like gmaxwell suggested. I really like that idea!

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 :)

ok, thanks, I didn't understand that part of it

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

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

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.

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.

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.

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.

Drazvan, excellent project!


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

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.

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

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.



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.

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

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.

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

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.

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.

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.

SPV is definitely a path worth exploring.

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

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.

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

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

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.

Yes, thank you - it does answer my question.

Though I disagree with the part that a card cannot go without a wallet.
I believe a card can be a wallet and the authority certifying it's software can be both; a great business model and a great invention for the masses.

And BTW, this thread is the best offline bitcoin payment solution/proposal/debate that I have seen so far.


Yes, I understand that a card does not have a display, not OK/Cancel buttons - thus it cannot be a wallet per se.
But if you sell it together with a secured terminal - the card in such a terminal is the wallet.
The wallet that is quite secured, IMO, and most important: one that can be used offline.
You trust the smart card telling you how many bitcoins are protected by a private key that it is giving to you...
And the card itself does not need to be familiar with bitcoin protocol whatsoever - it's just a simple wallet.

You are right Piotr, it can be made into a standalone wallet (and I expect others to do just that once the OtherCoin card is released). My focus right now is completing development on the JavaCard / smartcard side and adding compatibility with the standard Android Bitcoin wallet. But I am also the author of VisualBTC (https://bitcointalk.org/index.php?topic=210371.0) so at some point in the future I could also try to merge the two. I'm just taking it one step at a time :).

Sure.
Take your time and good luck with your projects!
They look promising - far more promising than bitcoin 0.9 ;)

I've been waiting for this....   https://bitcointalk.org/index.php?topic=147933 ... and so it begins.

I'll make a prediction here-- the popularity of off-line transaction will mean that bitcoin fees never peak above 200 BTC/day averaged over a month.  In fact they may have already peaked-- more people use bitcoin now than ever before and yet the fee's have never passed 100BTC/day at seven day rolling average and seem to be declining when averaged over longer time spans. ( http://blockchain.info/charts/transaction-fees  )

Once electronic schemes like become popular for smaller amounts and large off-chain bank-like transfers for larger amounts there will be little reason for anyone to use on-chain for normal commercial transactions.

Off chain transactions are only suitable for people who don't require certainty as to actually owning the bitcoins they think they own.

And these people include almost everyone here,  indeed I'll speculate and assume you yourself have participated in an off-chain transaction. 

Ask yourself this question: "Have I ever used an exchange to buy or sell bitcoin?"-- cause if you have then it most likely involved an off-chain transaction.

That depends on how how you define the boundary of a transaction.

In my case, there is nearly a 1:1 relationship between off-chain transactions and blockchain transactions related to buying and selling Bitcoins.

For example, when I purchase via Coinbase, they first allocate some of their bitcoins reserves to me via an internal database operation, which could be considered an off chain transaction, but as soon as those bitcoins are accessible I immediately withdraw them to my own wallet.

As far as I'm concerned, I'm not performing any off chain transactions because I never consider the purchase complete until the bitcoins I have bought move on the blockchain to an address I control.

I understand that several startups have a strong financial incentive to push a different paradigm, to convince users to let them hold their bitcoins on their behalf. When they inevitably steal/lose/confiscate their user's funds I won't be affected.

In the case of the OtherCoins, we're definitely not "holding bitcoins on the user's behalf". They're Bitcoins and remain Bitcoins, accessible at any time without contacting any external servers. The idea is to just allow them to be passed on to another person without going through the blockchain, but they can be used on the Bitcoin network just as easily - the OtherCoin smartcard simply makes sure that you can only do one or the other - it keeps parties honest, it doesn't hold your bitcoins.

If you read this thread, you'll see that it doesn't have the notion of Bitcoins and balances and doesn't even know what address you're using.

I'm not sure if this reply is directed at me or at  justusranvier.  If it was at me,  I would like to say that I do understand what you scheme is: it is very similar to this one that I outlined as an example of an electronic off-chain transaction using DRM on personal computers and phones- https://bitcointalk.org/index.php?topic=148232.msg1578079#msg1578079 (elsewhere in that thread I even say that it is possible to use smart cards).

The reason I mention bank-like off chain transactions above was because for most people conducting off-chain transactions with large amounts of money they would prefer the safety and reassurances that a bank like institution provides (eg: similar to how in the real world not many every day citizens by new cars/houses/businesses with cash-- they use bank cheques and the like).

Local off-chain electronic private key transfer is a great alternative for smaller items and would appeal to the masses, it would be very convenient for transactions like buying groceries and petrol etc.  Most people would accept the security risk associated for small amounts like this (eg: in the current fiat world few people here in Australia have reservations loading bus cards with a $20-to-$100 or so).   However, personally I wouldn't use private key transfer for anything more than a few thousand and I think will you find that many people wouldn't even use it for that much-- maybe just a few hundred.

There is a real need for your scheme and it is a great development.  Previously I've offered 50BTC for an open-source smart phone version for secure private key transfer, however at the moment smart-phones don't seem to have the necessary hardware-- Samsung KNOX comes close.  So I'll pledge 15BTC to your smart card idea on successful completion and public release (non-open source accepted).
  

Thank you beeblebrox! My answer was directed at justusranvier, I was just explaining that we do not hold our users' bitcoins in any way and we have no idea if/when transactions take place and what the value of those transactions is.

My comment was not specific to OtherCoin.

In general though, I don't expect any services that provide weaker security guarantees than blockchain transactions to survive in the long term. As more value moves into the ecosystem the incentive to steal will grow, and the thieves will target the softest targets first.

I could be wrong, but I think the blockchain is a case where we must put all our eggs in one basket (http://www.goodreads.com/quotes/37087-put-all-your-eggs-in-one-basket-and-then-watch).

I don't think it's going to be an "all or nothing" situation - I'm definitely not trying to replace the blockchain transactions, I am trying to augment them. Just as beeblebrox said, whenever they need anonymity or instant confirmation, people will pay off-chain. For large amounts and high security, they will go to the blockchain. For instance, I fully expect merchants to "redeem" their private keys onto the blockchain every now and then.

The "off-the-blockchain" transaction chain could be shorter or longer depending on how much you trust the system and how anonymous you want/need to be. This is why I'm trying to make it clear what the system knows and what its capabilities are and intentionally limit its abilities in order to prevent it from being abused by the issuer (which could be us or a licensee).

There's also another very interesting application for this technology/idea: Bitcoin addresses are anything but human-readable and since they are supposed to change with each incoming payment, there's no chance for the user to remember them.

The Bitcoin Payment Protocol (https://en.bitcoin.it/wiki/BIP_0070) addresses this concern by allowing payment requests to be signed using standard X.509 certificates. However, this requires the Bitcoin client to redo all the work that the browser has already done when accessing the site over HTTPS, present the certificate to the user for verification, etc. Browsers already do that and have done it for years and people are starting to get used to the iconography and visual cues that come with this process ("green lock", "green address bar", various warnings in the browser that the certificate doesn't match, etc).

So I was thinking that we could reuse this knowledge and leave the verification and the UI to the browser and the user. People already know how to check the certificate and ensure that they're not sending money to a phishing site. When they enter their credit card number on a site, they only have to check that the site is genuine, not check the merchant's bank account number or ask the bank to confirm that it really belongs to the merchant.

Users could simply pay by entering the private key of a Bitcoin address holding the funds in a text field on the site (just like they enter their credit card details) after they verify that the site is genuine. It would then be up to the merchant to sweep the funds to the correct address. This would also make it a lot easier to track down payments since they would no longer have to match incoming payments from the Bitcoin network to invoices/payment requests issued over HTTPS.

This could also work in face to face transactions - you would give the key to the other person after you are personally satisfied that they are who they say they are (or ask them for an ID if you don't). I guess what I'm trying to say is that people (and their computers) are becoming pretty good at identifying sites and other people, so maybe we should reuse that knowledge.

What do you think?

My main concern is on malware - the Payment Protocol (as hard as it is to implement properly on a secure device, IMHO) provides a way to address that, while this would create another trust issue to be solved.

Overall the idea looks interesting - there's some significant chatter those days about using smartcards as generic certified key generation devices - such as Fido/U2F https://sites.google.com/site/oauthgoog/gnubby - and this fits right in.

On a side note regarding smartcard platforms, I've done some research on the existing and open (as in, you can buy them right now without NDAs) Java Card that would be suitable for bitcoin applications and JCOP 2.4.2 looks nice (supporting Elliptic Curve key generation, SHA256 and ECDSA with SHA256) - it can be found on the Yubikey Neo. I've ported the BTChip application to it as a proof of concept and will be releasing the code shortly with a GPL license.

The problem with the payment protocol and malware is the one I described on the Trezor thread ( https://bitcointalk.org/index.php?topic=122438.msg3448363#msg3448363 ). Basically, browser malware could simply strip the payment protocol parts and change the destination address. Since most individuals and some of the merchants will not have certificates, the wallet cannot simply refuse to pay to addresses that do not present a certificate.

So it's basically safe if you absolutely know that the merchant implements the protocol (so if it presents the wrong cert or no cert at all, you do not pay them) but kind of useless to secure interactions with merchants you've never used before or individuals.

The YubiKey Neo is a great tool for development, I've actually used it to test the OtherCoin code over NFC. It does have some problems though with RSA key generation and randomness - see my thread on the Yubico forums at http://forum.yubico.com/viewtopic.php?f=26&t=1207 .

Right, but I think that's easily solved by having the physical wallet boot in Payment Protocol only mode, and require a user action (physically on the wallet itself) to reenable the old insecure behavior.


Not to turn this thread into a Java Card support party, but do you have the same behavior if you get/initialize the signature object when the applet is created ? I'll make some tests later and move that to Yubico forum.

That only works if the majority of the merchants support the Payment Protocol. Otherwise the user will receive the "insecure payment" warning a lot and will eventually disable it altogether since most of the time it simply means the merchant (or individual) being paid does not run the protocol rather than something fishy going on.


Yes, that's precisely when it happens (when the Signature object is initialized when the applet is created). It does _not_ happen if the signature object is created right before signing. Thanks for your help, I would appreciate it if you could give it a try, let's move that part to the Yubico forum though, as you suggested.

Also, paying by sending a private key allows for some very interesting form factors for the hardware wallets. Right now, the wallet needs to be able to read or receive the address of the recipient (so it needs a camera to read a QR code or an NFC reader or Internet connectivity). If payment is done by giving away the private key, the wallet no longer needs to "read" anything from the payee and payment can be prepared in advance, without knowing the final destination address. It's also safer since the payee has no way to inject any code/data into the wallet, it never sends it anything.

I was actually thinking of writing a wallet for these: http://wyolum.com/projects/badger/ - you would sync the wallet with the blockchain via USB once a day or so, then all payments would be done by simply selecting the amount using the 5 on-board buttons, then displaying a QR code containing the payment transaction to an address generated by the wallet and the private key associated with that address. The recipient would scan it, post the payment transaction to the blockchain, then post a second transaction sweeping the funds to whatever address it uses.

Just my 2 cents - this would be something separate from OtherCoin but equally interesting.

I've described how private key transfer could be used in person to person transactions (between trusted parties) or by online merchants - even in the absence of a secure chip - in this thread: https://bitcointalk.org/index.php?topic=329320.0 .

I plan to make this a part of the OtherCoin ecosystem at a certain point - if the recipient supports OtherCoin off-chain transactions, the key will be securely pushed to him that way. If he doesn't support it, payment can still take place by a transfer of private keys, if said key is encoded in a short human-readable phrase (a PayPhrase) that can be read over the phone or simply typed in an input field on a website.

I hope to see a future when Bitcoin addresses will go the way of IP addresses - they're still the basis of communication but nobody uses them directly or types them into anything. Humans are not meant to read those and I think the same applies to Bitcoin addresses.

If anyone's interested, I have completed a first version of the OtherCoin app (both the smartcard applet and an Android demo app).

The Android demo app can access 3 types of smartcards - a microSD internal card, a Bluetooth-based smartcard reader (namely this one: https://www.certgate.com/products/cgtoken/) and an NFC card (tested on the Yubikey Neo).

As mentioned in the whitepaper, private keys are generated by adding together two halves - one generated by the card and another one generated by the smartphone. This way the OtherCoin card never has access to your private key but can still guarantee the security of the system by keeping its half private.

The Android app can add new keys (that is ask the smartcard to generate them), request a BTC transfer (ask the card to send its signed public identity that the other card can verify to make sure it's talking to a legit card) and scan a response from the other smartphone (that contains the encrypted Bitcoin private key to import). It uses QR codes for the communication but it could be adapted to use Bluetooth, WiFi or just about anything else.

I've modified the protocol a bit to use ECDH key exchanges instead of RSA (that is the two parties now negotiate a symmetric encryption key using their EC public identities and use that to transfer the Bitcoin private key). RSA was just way too slow and keys were too large to fit into a decent (=readable) QR code.

Finally, it integrates with the Android Bitcoin Wallet to add funds to a specific OtherCoin key (it starts the Bitcoin Wallet with a prefilled destination address - you can see this in the demo movie at around 1:03) and to reveal a key (that is remove from the card and import it into the Bitcoin Wallet for use on the blockchain - see the demo movie at 0:35).

The video is at http://youtu.be/YXGOGMnRx2Y , it probably needs some annotations here and there, I will add them in the coming days.

Feel free to comment and ask questions. The Android app will be open-source to show you how to interact with an OtherCoin card (either via microSD, Bluetooth or NFC) and we're going to need some testers soon. The app is fully functional, everything described in the whitepaper is there and appears to be working fine.

I have spent the past few days polishing the UI and adding the ability to send/receive the keys over SMS. I am deliberately trying to avoid sending the keys over the Internet in any way - to make the transfer less likely to be noticed by someone looking at Internet traffic. SMS goes only through the facilities of the GSM operators while QR code goes nowhere (it's strictly screen to camera).

I will try to post another demo movie in the next few days to show off the new UI (new icons, less text) and demonstrate an SMS exchange.

I have also deliberately avoided exchange protocols over NFC and Bluetooth to keep the technical requirements as low as possible and also to "free" those two wireless options for communication with alternative form factors of the OtherCoin (NFC is used if you have a Yubikey Neo with the OtherCoin software on it while Bluetooth can be used to talk to the cgToken form factor (external Bluetooth smartcard reader).

As promised, I've uploaded a more detailed demo of the OtherCoin system to YouTube at http://www.youtube.com/watch?v=ZR8gz0uVBHk&feature=youtu.be (make sure you view it in HD).

It shows it running side by side on a Samsung Galaxy Note 2 and a Vodafone Smart Mini (a.k.a. Vodafone 875), sending keys back and forth over SMS and interfacing with the Android Bitcoin Wallet to reveal a key (remove it from Othercoin and import it into the wallet) and add funds to a key (stored securely in the OtherCoin smartcard). Sending/receiving keys via QR code still works, it's just not shown in this video.

If you have any questions, ask away. If you feel generous (or supportive), 1VeriFivRsUxUqdWMgUmHrgfQXL9J3dfe :).

Thank you,
Ravan

Congratulations on achieving demo status for your project.  This is a game changer for Bitcoin- the greatest innovation in a year since Bitcoin ATM's.  I can't understand why this isn't the top comments thread of the month  -- no comments anywhere yet?.  I think most people here just don't understand what this project is.

Previously I pledged 15 BTC on this thread to you for this- I have just sent you 5BTC and will send another 10 when it has the finishing touches and is publicly realeased.  Please spend this as you see fit (preferably on the project though I don't mind if you spend it otherwise-- you deserve it!).  

I'm interested in knowing if you familiar with the Samsung Knox Android phone- it has very strong privacy and security feature with allow apps to run in secure isolated containers.  Knox would be a great match for this project.  I'll give you another 0.5BTC if you port your software to make use of the available Knox features.  This shouldn't be too hard or take too long, from what I understand you contract Samsung and provided they approve the app they assist in wrapping the Android files to make use of the Knox features.

Have you thought about patenting your split key idea of using both the phone and the card?  It would be a good idea even if you are motivated to introduce this system for the benefit of bitcoin and not so much for your personal gain because it would help your system to become standard.  The widespread use of electronic off-chain private key exchange needs/requires very few solution providers so that people can exchange with others without compatibility issues.

Also how do you plan to advertise/introduce it to the bitcoin community.  I imagine that you could perhaps gain access to users by introducing it to local bitcoin groups and retailers.  This project needs to penetrate where people meet face to face regularly to conduct bitcoin transactions.

By-the-way:  I want this project of yours to succeed, so if it would help it I can lend you interest free up to 20 BTC to be paid back at your leisure as a gentlemen's agreement.  If you would like more I could lend it to you interest free up to 250BTC but this would require a formal agreement (you would have to pay the costs of drawing up a contract).  Even more is possibly available but it would require that I receive benefits in return (eg: exclusive rights to sell in my country, or a part of the business, etc.)

Thank you Beeblebrox, 5 BTC received.

I'm not sure what you mean by "public" - taking it commercial will take a bit longer (the main showstopper being the actual hardware - I have a few of each of the various hardware form factors for the OtherCoin card and obviously need to get some initial stock and selling these to end users requires various little details like a manual, a logo (engraved or silkscreened) on the actual card, a streamlined card issuance/provisioning mechanism (right now it's all manual and I don't scale very well :) ). I also plan to have a limited beta test with a few users just to confirm that I haven't missed anything obvious.

My plan for the coming weeks is to raise enough funds (either via donations such as yours or by preselling exclusive distribution rights) to allow me to focus on this project exclusively and take care of these little details before I go fully public.

The source code for the Android app has just been published at https://github.com/razvandragomirescu/OtherCoin - any interested party can take a look and verify that it actually works the way I described (keys are split between the smartcard and the phone, the card has no access to any network and communicates only to the smartphone, etc). It should also serve as a reference on how to interface with the various form factors that the OtherCoin will have (microSD card, external Bluetooth token or NFC token).

Regarding Samsung Knox, it already works with it. I've actually had Samsung wrap OtherCoin + the official Android Bitcoin Client + the helper tools for the Bluetooth OtherCoin and they all run from within the Knox container (tested on a Galaxy Note 2). The problem comes when interfacing with the OtherCoin card - Knox containers disallow communication to external storage (so no microSD or USB) and also block NFC. Only Bluetooth should work, but it doesn't (there's an exception in the BluetoothSocket system class - not in my code). I'm all over Samsung's support for this, they have specifically told me that Bluetooth should work but now they claim that only very specific "whitelisted" Bluetooth smartcard readers are allowed. But yes, it works in Knox, if you have a Samsung device that supports it let me know and I'll email you the wrapped APKs to try it.

Regarding user adoption, the plan was to get some early regional resellers that can help by promoting it at local Bitcoin meetups and conferences in their area. Preselling exclusive distribution rights (per country or per region) would also help us raise the necessary funds to turn this from something I'm working on in my spare time into a real business. I'm not sure where you are located, but if you're interested in acquiring the exclusive distribution rights in a certain area or country, make me a reasonable offer and I'll take it. You would not only get the exclusive rights for OtherCoin in your area but also the rights to the Card2Coin sub-project (see https://bitcointalk.org/index.php?topic=339389) that will become part of the OtherCoin ecosystem, closing the loop by allowing you to exchange your OtherCoin keys to dollars directly, without ever having to touch the blockchain.

Depending on how much we raise from early regional resellers, I might take those 20 BTC you've offered as a loan, I really appreciate the offer. Thank you!

(we should probably move the discussion to the Project Development area sometime, right now it's a mix of tech + project dev)

Yes, I should have realised  that Knox wouldn't allow communication to external storage such as the SD card.  But good to see that you've wrapped the parts anyway-- I am sending you 0.5BTC for that.




Anytime you wish to take my up on the offer just post a message here or in the other thread (which I've just discovered) about this project in the Project Development area and I'll send it to you.



PS: regarding buying distribution rights.  For me personally I would require that you have some sort of patent protection so that other competitors couldn't steal the market with alternative products.  Unfortunately, the basic concept of off-chain electronic transactions by  secure private key exchange would most likely not be patentable since the mechanism has been publicly detailed previously by others.  However, your idea of splitting the private key across the phone and card offering further customer protection I believe is novel (not only novel but also a great idea too :)   ) and should be patentable.  The split key feature could provide a selling edge to establish your product in a market dominating position-- a dominating position in this market is golden due to the fact that it has a native lock-in factor owing to the compatibility issue surrounding the cards being able to talk to each other and establishing secure connections.  

 (Actually, as-an-aside: In my particular case of Australia it may even be the case that you cannot patent the split key idea as it is my understanding that our law requires that the idea never be published before the patent application-- however I think this is the exception of most countries than the rule.  I believe that in places such as the USA you have up to one year after publicly detailing the mechanism to patent it-- but I'm not a lawyer so not so sure.)

Thank you, 0.5BTC received as well. If the smartcard reader whitelist that Samsung support mentioned is real, I will try to work with our supplier to get the OtherCoin/cgToken Bluetooth reader certified with Samsung to make it usable in the Knox container. Their support guy didn't sound very sure about it though, they had specifically told me to only use Bluetooth 2.1 (not 4.0 - that's not supported) and never mentioned this "whitelist" until I actually tried it and saw the exception being thrown in their system classes (the app passed certification just fine).

I'm not sure if the split key setup is patentable (but I am not a patent attorney either) - after all, that's how the vanity Bitcoin address generation works. They are not storing the secret half of the key in a tamperproof smartcard though or using the system to securely transfer value between parties.

One other thing that is interesting is that OtherCoin is not limited to just Bitcoin - any altcoin that still has the notion of a private key (used to transfer funds) can be integrated with it. If the altcoin uses Elliptic Curve crypto, then the split key scenario also works, but you can also use the system without a second half stored in the smartphone and just trust the smartcard to transfer the private key around safely.

I would definitely like to claim the remaining 10 BTC from your bounty as well, what would you like to see before that happens? The Android app can be in the Play Store in a few days but it's not very useful without the hardware (the OtherCoin card) - additional OtherCoin microSD cards will take a few weeks to arrive. Please let me know how you see this. You can also email me at razvan.dragomirescu (at) veri.fi or send me a PM.

To everyone else reading this thread, if you would like to be appointed as the exclusive reseller in your country or region (considering that the solution is not currently patented and, as Beeblebrox mentioned, we are not sure if it is patentable at all), feel free to make me an offer - I'm also willing to consider offers that pay a reservation fee immediately with the rest of it being due at the time the application starts selling.

SMS traffic goes through the internet nowadays.  Better use two channels

OtherCoin is channel agnostic, I've implemented SMS and QR codes as samples but you can also use NFC, Bluetooth, WiFi or even the Internet. SMS appeared safer (especially if parties are on the same network - meaning that the messages only go through the SMSC of the operator and do not leave their infrastructure).

You can also mix channels if you feel like it (even in the current implementation, you can send your request via SMS but scan the response from the QR code, although I don't see why you would do that).

In my opinion offering a validation / stamping service to "bless" the public key of a device you want to use with OtherCoin looks like a better idea and business model than a patent - especially since the process had already been disclosed here  ;D

Don't worry, that's coming:). Just didn't have time to implement that yet. This will be useful for completely offline transactions (right now transactions are simply off-chain but you still need access to a way to verify the balance associated with a private key - right now we use the BlockChain.info API with a pinned certificate to prevent man-in-the-middle attacks, but OtherCoin will also support signed "balance statements" that certify that at the time of the signature the balance of that particular key was x BTC (and as long as the key travels only between OtherCoin devices, its current balance can only be higher since nothing can be spent without the private key that is held securely in the smartcard).

I've also looked into using SPV to prove to the recipient that the key actually has a certain balance, but as far as I understood, SPV is _not_ safe if your only source of information is the potential attacker. SPV should be safe if the majority of the nodes you have access to are honest and in the case of an offline transaction, the only node you have access to is the sender of the funds who is also the most likely attacker.

I've posted some initial pricing data and a few details on how to order a unit from our first batch in the Project Development area at https://bitcointalk.org/index.php?topic=319146.msg4494688#msg4494688 .

Beeblebrox, I think I'm going to accept your offer. I've spent the past few days talking to various people and it looks like most of them do not really understand what OtherCoin is/does. They keep asking questions like "how is this different from spending Bitcoins between two Android smartphones" (as in using the Android Bitcoin Wallet to spend the funds directly via the blockchain) or "why do I need a microSD card in my phone to do this" (they don't know what a smartcard is or are even aware of how vulnerable an Android smartphone really is, especially when rooted).

On the other hand, distributors want to see a finished product (packaged, ready to sell) before they commit to anything, so I guess the first order of business would be to get these to look more "commercial", then into the hands of a few key people and reviewers that can understand how OtherCoin is different from a regular Bitcoin payment. I also need a demo video that shows the actual product in action, from the time you insert the card into your phone to your first payment through the system.

Just to clarify, is the 10 BTC part of your bounty still on (for when this becomes a commercial product, which should be in a few weeks)? If the 20 BTC loan removes the 10 BTC part of the bounty, I'd rather struggle to get it out the door on my own, then take the 10 BTC and use them on the project. As you can see, I am a bit reluctant to get into debt (managed to stay debt-free for 35 years ...) but I really believe in this idea and its potential.

You are also welcome to become more involved in the development/company if you wish to do so, I could use an adviser / partner, even if you don't want to do this in an official position (but also if you do).

Thank you,
Razvan

I'm going to reply to this in the other thread since what we are discussing is more relevant to "Project Development" than Bitcoin "Development and Technical Discussion".

Thank you Beeblebrox, will reply there.

Regarding the use of smartcards in Samsung Knox, here's Samsung's official response:


The app itself works fine but access to the smartcard is blocked by the Knox container. I do plan to work around it by having a hosted smartcard in the cloud (a physical one, plugged somewhere in your computer). That is planned, just not implemented yet.

Hello everyone,

Just a quick update on the software side: the initial plan was to have each OtherCoin keep track of the history of each received Bitcoin private key in order to be able to help with identifying a potential attacker that had managed to crack one of the cards and extracted its private key, allowing him/her to attempt double-spends (either simultaneous spends in the OtherCoin system or spending a key in OtherCoin and immediately spending the same key in the Bitcoin network).

After careful consideration, I've decided _not_ to implement this. Allow me to explain:

1. The main purpose of OtherCoin is to allow a way to _privately_ transact Bitcoins, without any traces in the blockchain or anywhere else. If we would be able to recover the history of a certain private key, someone else could do it too (or they could force us to do it for them). The easiest way to make sure the payment history cannot be recovered is to simply _not_ record it anywhere.

2. Provided that we don't make any stupid mistakes in the actual protocol (and we're going to make extra sure we don't), OtherCoin would only be vulnerable to physical attacks to the smartcard chip. Those are extremely expensive and require very specialized equipment and labs, not something your average script kiddie would have. The estimates I've seen were in the range of a few hundred thousand dollars in costs to attack / recover keys from a single card.

An attacker that manages to defeat one of our cards would only find his/her own private key, essentially allowing him to attempt double spends. However, to recover the high cost of the key recovery process, they would either have to attempt to double-spend a huge amount ($100k for instance) or a lot of smaller amounts (let's say 1000 payments of $100 each). As much as I'd like to see OtherCoin used for payments of hundreds of thousands of dollars, most recipients would probably immediately drop the transaction onto the blockchain to get it confirmed, so the attacker would no longer be able to double spend. For the 1000 * $100 scenario, the attacker must have 1000 people to transact with and hope that all of them do _not_ attempt to spend the OtherCoin Bitcoins on the blockchain before he's done (and none of the 1000 can identify him).

3. I suspect that if someone would ever attempt to crack an OtherCoin card (in the physical, expensive way), it would be the NSA or a similar govt funded entity. These entities would most certainly not do it in order to double spend anything, they would do it in an attempt to trace payments or identify persons/entities behind the OtherCoin addresses. However, if the cards do not contain any history information, an attacker would have nothing to gain by cracking a user's OtherCoin card (other than gaining access to his/her private keys and possibly spend the funds associated with those keys - something they can probably obtain with a $5 wrench - http://xkcd.com/538/ :) ).

I would be happy to hear your pro/con arguments. I realize that not implementing this makes us "deaf" in case of a successful crack of an OtherCoin card. We would know it has happened (the double-spend would be visible), but we would not know who has done it (unless we work our way backwards from the current owner of the key and count on them knowing/remembering who they got the key from, then rinse and repeat). But the upside is that there is no payment history, not in the blockchain, not on the card and not anywhere else. There's nothing for us or anyone else to extract, the info is just not there.

Let me know what you think.

I agree with your analysis; given the use-case is low-value payments, better to have a solid privacy guarantee and slightly weaker loss reistance than the other way around. After all, this thing could be useful for privacy too.

Reminds me: it'd be good to add some features to make it possible to to secure trades on a blockchain. Right now your OtherCoin.pdf whitepaper suggests two functions, generate key, and securely transfer key to another card. I think you actually need a third function that does bi-directional key transfer atomically.

Suppose Alice has 50LTC and Bob has 1BTC. They want to trade like for like. They can do this by first transferring the currency into an address that their respective OtherCoin card has control of and letting the transaction confirm. Next they tell their cards the transaction they want to make, Alice: "Give up secret key Alice_LTC in exchange for secret key Bob_BTC" and Bob: "Give up sec key Bob_BTC in exchange for Alice_LTC"

Now the two cards can communicate with each other securely. (being fully atomic and non-jam-proof will be tricky) When they're finished either party can repeat the process, or potentially just reveal the secret keys entirely so the coins can be spend normally. Interestingly the cards themselves don't have to have any concept of trust; all the cards care about was that they got a signed ACK from the other side. Whether or not that signature was from a trustworthy card can be left up to the user to evaluate.

Speaking of, you forgot to include "Reveal a secret key" in your list of basic operations. In fact, what you actually want to do is a bit more subtle than in your whitepaper: you should always be able to get your OtherCoin device to produce an encrypted and then signed message containing a given secret key. What key the message is encrypted to is irrelevant: under all circumstances once this message has been produced the OtherCoin device is guaranteed to securely delete the key from memory and never produce another such message. At the same time the device is also guaranteed to only accept a new secret key if the key is encrypted and signed by a trusted sender.

What's neat about this is it gives a one-sided upgrade path: new devices can still accept secret keys from old, but still trusted, device. For instance if the master secret keys are ever lost, you can create a new set and issue new devices that can still accept secret keys from the old devices, even if the old won't accept keys from the new.

With regard to history, I think there's an interesting attack-countermeasure possible without it, but first, a bit about how you'd actually use the card.

If the card is purely a secret key storage device, we have a practical problem of granularity: If Alice has 1BTC stored on one secret key, how can she send Bob 0.5BTC? Now, bi-directional transfers help here - if Bob happens to have 0.5BTC in one or more secret keys, he can give those keys to Alice in exchange for her secret key to make for the correct net amount transferred. Ideally you'd just fill your wallet with secret keys loaded with powers of two outputs, however that runs into the problem of minimum cost to spend a txout - at some point even if you had an output worth x BTC it'd cost you a significant fraction of that x BTC to spend in on-chain, so for the smallest amounts you'll want outputs along the lines of, say, 1.01BTC, so you can exchange it for Bob's 1BTC txout efficiently.

This is relevant to attacks when you consider the financial model of an attack. The attacker might spend, say, $50,000 worth of lab time to take apart one of these cards and extract the private keys on it. Once that is done the attacker can then create a fake software emulator and intercept the secret keys. However to actually profit from the attack the attacker needs to get something of value in exchange for pretending to delete secret keys, and the total value of on-chain txouts spendable minus the transaction costs to obtain them needs to be >$50,000 to break even.

Now suppose we limit the lifetime of a secret key to 1 year; after that year is up cards won't accept it. We can easily prove the creation date of a key by using the blockchain as a timestamped random beacon and committing a recent blockhash with ECC key derivation. Next we limit the total value of the secret keys that the card has access to per year. We can do this with Rivest's paywords scheme: the card calculates a chain of nonces derived from a root secret with w_i=H(w_{i+1}), revealing an additional step in the chain at each step. If peers expect a new, signed, nonce with every secret key exchange they can limit the total number of exchanges in a given time period by publishing those nonces. This can be a central server or decentralized p2p network; the requirements for consensus are very loose and not all nonces need to be published. Publishing two separate signatures for the same nonce - or overlapping range of nonces - is of course considered fraud and is easily proven. Storing the nonces isn't onerous, as they can be expired over time.

So long as the cost to attack a card is high compared to the cost of the card itself the economics work out. If a $5 card lasts two years and can move $25,000 worth of private keys per year, the cost to do so was 0.01% of the value of those keys. Meanwhile the attacker needs to keep the cost of the attack to <$25,000 to break even. I think the main question is what kind of economies of scale an attacker might get, and what kind of per-transaction cost users are willing to accept.

Oh, and FWIW, the paywords stuff doesn't need specific support by the cards themselves beyond the ability to calculate an arbitrary paywords chain; the software talking to the cards can handle the rest.

Thank you Peter, I'll look into those paywords, I wasn't aware of that system. Smartcards do not have an internal clock, so I was initially thinking of using a certified time source (that is a web service that accepts a nonce and returns a signed time+nonce packet indicating the current time), but if this could be done in a distributed fashion it could be interesting. I'm not sure how that would work though, how would you limit the amount being transacted or do you only suggest limiting the number of transactions that a card can do in a given time interval?

I am trying to keep the on-card system as simple as possible and only use cryptographic primitives that the chip manufacturer (NXP) has certified against various attacks (SPA/DPA). They have an entire document that describes how those primitives must be used in order to maintain security.

Adding on-card processing in JavaCard can be extremely slow and can leak information, that's the main reason why I haven't implemented Adam Back's suggestion to change the private key halves every time they are exchanged by adding a random value on the smartphone and subtracting the same value on the card to make sure that previous owners of a key cannot steal your smartcard and use the key half they used to know to reconstruct the Bitcoin key. JavaCard has no native BigInteger implementation and rolling our own would require careful testing against timing and power analysis attacks.

I am also trying to make this as independent of third party Internet services as possible. Certified balances (like btchip suggested) are going to be there, but they will be optional (you will always be able to just lookup the balance on the blockchain).

And yes, you are right about the granularity problem, you could either have smaller amounts on different keys or just send _most_ of the amount over OtherCoin and then post a transaction on the Blockchain to "split" a certain key into two (a remainder to pay and a change, sent to another OtherCoin address). I expect wallets to manage this the same way people manage their cash in large denominations. Merchants could also calculate a change amount and return it to the payer via OtherCoin (they don't care as much about their anonymity, so they can easily post to the Bitcoin network to split large OtherCoin keys into smaller ones or fund new keys with small change amounts).

Thanks for the feedback!
Razvan

A quick status update: OtherCoin is progressing nicely, I have cleaned up the protocol a bit and added the ability to send PIN-locked keys. A locked key is transferred just like any other Bitcoin key in the OtherCoin system but it's also protected by a PIN. Without the PIN, the recipient is unable to spend it or transfer it to another user. This allows a primitive type of escrow - once a key is transferred, the sender no longer has it but without the PIN, the recipient cannot do anything with it (other than verify that it exists and has funds on it). So the two parties have to agree in order for the recipient to obtain the necessary PIN to unlock the key.

I'm still working on the final packaging for the cards and their associated microSD readers (we will include a reader in the package for each card - for phones that do not have a microSD slot). On the Android side we've hit a bit of a problem with Android 4.4 KitKat - https://code.google.com/p/android/issues/detail?id=67406 . This prevents OtherCoin from working on Android 4.4 since the phone can no longer talk to the card. The miniature Bluetooth card readers that we plan to offer as an alternative (see http://www.certgate.com/products/cgcard/ ) will only be available in May, so one way or another we'll have a working solution for Android 4.4 by mid-May.

Finally, another important part of the OtherCoin ecosystem has been prototyped - the Card2Coin system I described here: https://bitcointalk.org/index.php?topic=339389 now has a prototype and a demo movie at https://www.youtube.com/watch?v=ZsOzeELdjxM . It's a distributed BTC/fiat exchange based on the idea of remotely charging someone else's credit card in exchange for your Bitcoins. This will eventually be integrated with the OtherCoin system, allowing you to buy Bitcoins, transfer them and sell them for USD _within_ the system, without ever touching the blockchain or any of the centralized exchanges, while still preserving your ability to go through the blockchain at any time.

Sorry! I must have read your reply and forgotten about it.

The blockchain itself can be used as a clock in a few ways. The most obvious way is to process the block headers and just use the latest one lower bound on what time it is. However then you have to ask how does the card get the blockchain? You can add to the protocol an encrypted field that essentially lets anyone feed the card with block headers within any transaction going to it - if I'm sending you money I can inform your card about what time it is against your will.

However, all the block headers are kinda large for a Java card, so you really want to only send a subset. When you think about it every header the card gets is essentially making a kind of statement that some amount of work was done claiming the current time at least blockHeader.nTime Every header the card gets pushes the likely current time in some direction, usually forward. Making a bunch of fake block headers with high difficulty is very expensive, so you can probably come up with some rule that makes faking headers to lie to the card about the current time unprofitable. You can be a bit more clever with this by using interactive or non-interactive proofs, but long story short, Bitcoin doesn't support that yet.

You can also force the owner of the card to provide recent block headers via timestamping and merkle paths. The card would generate a nonce and and the card owner would be required to timestamp that nonce in the Bitcoin blockchain and provide the card with a merkle path from the nonce to the block header. The user is forced to keep providing the card with new blocks; with a minimum difficulty the cost of compromise is well defined, almost. Unfortunately it is possible for a group of card owners to collude and have some fake block headers generated so as to let them all benefit, driving the per-card cost of faking the time down. (possible without timestamping too I might add)

Timestamping infrastructure doesn't exist yet, but creating it isn't hard. I have a project called OpenTimestamps that was doing just that - I'd be happy to put some time into it again.

As for centralized time services personally I'd be very hesitant to use any kind of centralized service simply because it'd be temping for a court to order them to either shutdown, change keys, or sign fake timestamps as a way of disrupting OtherCoin users.



Good idea! How long will this pin be? What will you do to prevent brute-forcing it?

Thanks Peter! In all honesty, I haven't had the time to look into the timestamping issue yet, thanks for the suggestions! I'm trying to keep the initial release as simple and as "blockchain agnostic" as possible. All it does for now is secure private keys, it has no notion of blockchain/transactions/ECDSA/etc, so it can be easily reapplied to just about any other altcoin that uses private keys (are there any that don't? :) ).

I need to get the marketing materials done so I will probably stop adding features for a few weeks and focus on getting it launched. There's always room for a version 2 :).

Regarding the PIN, it's 4 digits / 3 tries. It's sent encrypted together with the private key and stored as an OwnerPIN JavaCard object (those are especially protected by the JavaCard runtime). You get 3 attempts to unlock the key - if you fail, the key is permanently blocked (I should probably make it delete it at that point to save space and prevent further attacks).

Heh, I certainly do recommend you consider seriously that option! I've got a lot more ideas than there are hours in the day.


Sounds good.


You can put me down for a pre-order BTW.

Hello Drazvan,

How are you going and how is the project coming along?

I'm curious to know what are the limits regarding how many keys the card can hold at once,  could you please tell me?

Thanks
Beeblebrox

Hey beeblebrox, good to have you back!

Right now, each key takes 32 bytes (the private key) + another 32 bytes stored as an encrypted blob (that is actually the half of the key that the phone knows, encrypted with AES by the phone). That blob is used to be able to move the smartcard between phones and re-build the OtherCoin key database if you only have the card (and a master password). The blob is not mandatory, but the current Android OtherCoin implementation uses it, so let's assume 64 bytes/key.

The current microSD smartcards we use have about 144K of storage (chip is NXP J5C145_M3) and the OtherCoin app itself is probably around 4K or so (haven't checked exactly). So 140000/64 = 2187.5. So you can safely assume that you can store about 2000 keys in the app - that would prove to be a bit unwieldy at this point with the current OtherCoin Android app since it shows them all to you and you choose the ones to transfer. Once we automate the process it will become easier. I think most people will have 100 keys or less in the system at any given time though.

As a status report, we're waiting for all 3 (yes three :) ) hardware manufacturers we use to fix their products. There will be 3 form factors for the OtherCoin product - a microSD card, a Bluetooth Low Energy keychain-style dongle and an actual Android device with a real (SIM-sized) smartcard inside. We're waiting for a new firmware from the microSD manufacturer to support Android 4.4 KitKat (current version does not work with KitKat and units cannot be upgraded in the field, so we would have had to recall them for an update or mail everyone new units). The Bluetooth Low Energy dongle will be available mid-May (around May 20th or so we've been told). The Android device has a bug with long-running smartcard operations (it times out too soon) and the manufacturer is supposed to send us an updated firmware next week.

I'm trying to make sure everything works on the smartcard side since that's very hard (if possible at all) to upgrade in the field. On the Android side we can always push an update through the Play Store if we find any issues. The app itself appears to be rock-solid, it's just these last minute interface bugs that drive me crazy. They have nothing to do with OtherCoin itself but with the way smartcards are read by the OS.

BTW, over the Easter holidays I tried to get away from the OtherCoin project and clear my mind a little bit, so I wrote this: https://bitcointalk.org/index.php?topic=586830 :). Now I'm back to the serious stuff.

Can it transfer fractions of the wallet? If not can it have multiple addresses of small amounts?

"Fractions of the wallet" - yes. "Fractions of a key" - no. Keys (and their associated balances) are transferred altogether, so you cannot transfer less than a key (that would effectively mean you are sharing it with someone else and the whole point is to make sure the key is only held by a single person at any given time). If you need to "break" a key into smaller amounts, you can easily do so through the Bitcoin network - transfer the key you want to split to the Bitcoin wallet, then fund two (or more) OtherCoin addresses from it with any values you need. This is also how you can pay the exact amount requested = you pay the majority in OtherCoin, then if the merchant wants to receive _exactly_ what he's asked for, you either pay the rest via Bitcoin or you break an OtherCoin key into two smaller ones, then transfer one to the merchant (for the remaining amount to pay).

To ease the use the smartcard key exchange for purchases I envision that it would be best if people had many wallet keys (from now on I will call them coins) with balances of standard denominations (example denominations: 1 uBTC, 10uBTC, 100uBTC, 1mBTC, 10mBTC, 100mBTC, 1BTC, 10BTC, etc) so that they can give the exact amount or be given return change by totalling multiple coins in the manner similar to normal fiat eg: to give 0.8253BTC use 8x100mBTC + 2x10mBTC + 5x1mBTC + 3x100uBTC.   You could quickly top-up your smartcard with more coins by asking other people directly for change or using a change service over the internet.

By-the-way Drazvan,  this is what I was going to write an email about to you a couple of months ago.  I am now sending a PM with some further details that you may be interested in.

That sounds like a good idea - although I'm not sure a web service is needed to do the change. If you want to split 1 BTC into 10 * 100mBTC or 100 * 10mBTC you can always go through Bitcoin (that is redeem a 1 BTC OtherCoin, then feed the balance into 10 or 100 smaller OtherCoins).

A web service could be useful though for premium services - that is the ability to split a larger coin into smaller ones without advertising this on the Bitcoin network and also getting confirmed or balance certified coins in return. So you would give the service your 1 BTC OtherCoin and it would give you 10 * 0.1BTC OtherCoins with more than 6 confirmations on their balance (or simply with a signed balance - regardless of the number of confirmations).

I plan to spend the next couple of weeks redesigning the user interface of the app a bit - that is way overdue! Right now it displays a list of the coins and their balances and you can long click on each to access the available options (Spend, Redeem, Delete, etc). This doesn't make much sense for the average user and looks downright weird when you have more than a few coins, so I plan to aggregate the view and just display a count of coins in each bucket (1 BTC, 100mBTC, 10mBTC, 1mBTC, etc) as well as keep a "floating" BTC balance (that is a pure Bitcoin balance that is not stored on the card but available to the Android app as a buffer to either create new coins or split existing ones or as an intermediate buffer for redeemed values). This way, if you want to split a larger coin or aggregate a few smaller ones you simply select them and it internally moves them to the floating BTC balance first (gets the private key and sweeps their value), then funds the coins you want to create. This would get rid of the requirement to have the Bitcoin client on board (you can still have it installed if you want to fund the floating balance externally or want to get some of the floating balance out).

Ok, I have a little bit of a dilemma: if we move to multiple OtherCoin denominations, each transaction would mean a transfer of multiple private keys (each key being 32 bytes secret on-card part and another 32 bytes known by the Android app). So it's 64 bytes/key. If we go all the way down to 0.1mBTC and assume people won't pay more than 10 BTC through the system (probably a safe bet at first), the maximum number of coins would be transferred when you pay 9.9999 BTC (45 keys, that's about 3 kilobytes including protocol overhead). That's a little too much for QR codes and could become a problem even for SMS chaining. It could be sent over NFC and over the Internet.

We could go with animated QR codes but I've used those before (I wrote this: www.visualbtc.com) and they're not exactly easy to use. So I wonder if I should drop QR codes altogether and keep SMS and Internet and NFC comms. SMS might be tricky (or expensive) for large transfers, it already uses concatenated messages but still, those are up to 140 bytes (160 characters) each, so you would need 20 or more to send a 45 key transfer. I've already implemented a small server that OtherCoin apps can send the info through (it's just a relay type of system, nothing fancy). Of course, QR codes and SMS have the advantage of not requiring and Internet connection, but we're going to need one anyway to split coins and do BTC transfers anyway.

Any thoughts would be appreciated. Thank you!
Razvan

Perhaps you could use denominations based on binary,  ie: 10uBTC, 20uBTC, 40uBTC, 80uBTC,.... .  To cover the 10e6 fold range from 10uBTC to 10BTC you only need a maximum of 20 keys if you sum it the most efficient way.  (I started at 10uBTC to allow for transactions such as paying for reading an item of news from a web-site, or paying to get change from an internet change site :) , etc.)

Is twenty keys too many for a QR code?

Of course most people would have trouble working out how to represent arbitrary amounts in binary but the phone/computer would do this behind the scenes anyway.  All they would really need to know is the total amount they hold while the computer handles using the correct change in a transaction.   By default you could just have their total displayed with a option to display a summary of the holdings of each denomination and a further option to show the details of each individual coin's key/wallet.

Each time a person engages in a transaction their phones could automatically negotiate with each other to top-up with any coins they need if one has excess in some denominations but shortage in others  (the phone could even monitor the owner's usage pattern over time and determine their most commonly used denominations and build up a store of them).  This would lessen the need for people to use 3rd party online change services.

I don't understand what you mean.  Which server are you talking about?   Drazvan's system doesn't rely on a 3rd party server,  it is a private key exchange between two people.

No, Eternity's right, we could theoretically look at our proxy to see the (encrypted) traffic between parties. We could see who's transferring to whom. However, the actual transaction is encrypted with a negotiated key (Diffie Hellman exchange), so we can't see that.

So yes, using our proxy makes things a little less private - but remember, you're coming from Bitcoin transactions where _everything is public_. In a Bitcoin transaction _everybody_ knows who you're paying, in a proxied OtherCoin transaction we could theoretically know who you're paying (but not to what address and how much). And in OtherCoin you have the option to just pay in person using NFC or QR codes or SMS (although you could say SMS goes through the wireless operator, so they would know that you're paying someone).

The proxy is there for convenience and is optional, it doesn't automatically push the data through us - there's a button that you need to press to upload the data to our proxy. It makes things easier for transactions with remote users if you choose to use it.

Hi Drazvan,

Here are the advantages for a web change service that I had in mind-

These two you have already pointed out:

-Speed of receiving pre-confirmed (and certified) coins is the main advantange of using a web-service for change.  The service will be more or less instant when compared to creating change coins on the block chain and waiting for them to confirm at the time of the transaction (in cases where the receiver insists on confirmed coins).  

- Anonymity offered to the sender since they're not using their own wallet address to create the coin, the person recieving dosen't get to see any of the wallet addresses of the sender.


There are also a couple of others that I have thought of:

- You can offer a service guarantee that all the coins that you have personally created and certified are clear of taint from the major theft events (clear of publicly recorded/verified affected addresses atleast).  The person receiving the coins doesn't have to check them against the block-chain for taint.

- it may be cheaper to use the web-service.  Since the web-service has plenty of time to pre-make coins it can use lower-priority transactions (even feeless ones if the service operator waits a long time).  So the web-service can sell their change coins cheaper than a person can make them for themselves if the person has to make it confirm quickly (ie: in the next block) at the time of the transaction.  


The speed and the cheapness form the main economic case that I can see for the web-service being successful/profitable.

Hello everyone,

I have updated the whitepaper at http://www.othercoin.com/OtherCoin.pdf to reflect the most recent changes in the protocol and application. I've decided to get rid of the centralized balance certification and use SPV proofs (as suggested in this thread). It's not fully implemented yet, but it shouldn't take very long now. Each device will simply download block headers, then at the time an OtherCoin key is funded, the payer waits for the transaction to be included in a block, then fetches the Merkle branch that links the transaction into the block and uses the serialized transaction + Merkle branch + block hash as a proof that the transaction really exists. Since each participant downloads his/her own blockchain headers, the payer cannot feed it fake blocks.

I've also detailed the PIN-based escrow mechanism that is built into the system and listed the hardware that we've tested it on and the hardware we expect it to work on.

Finally, I've submitted the app to the Coinbase Hackathon (I'm not sure if it will be accepted - their Terms and Conditions do not rule out older apps, but their submission page says the app should be "new" (as in created after April 7th - and OtherCoin obviously isn't) ). If they abide by the T&Cs, they should accept it, but we'll see.

BTW, here's the demo video I've created for the Hackathon: https://www.wevideo.com/view/395666124 . Enjoy and wish me luck! :)

Interesting to know it is still alive.

Just discovered this thread. Awesome project. I am wondering why this has so little attention from the community. Projects like this give a very good reason to stay conservative regarding the max block size limit.

It's very much alive, thank you! :). Just going slowly due to (current) lack of funding (and being a one-man-show more or less, with me filling in all the roles :) ). As soon as I've removed the dependency to the centralized balance signatures, OtherCoin will become truly and fully decentralized - even if we go out of business at some point, the system will continue to work and all cards will continue to be valid indefinitely.

Thanks for the $50 tip/donation to whoever sent it, it's the first donation I see in a long time :).

I think the apparent lack of interest is due to the fact that OtherCoin doesn't claim (or is expected to have) a net effect on the Bitcoin price. Its intention is to simply make off-chain truly private transactions possible. As a side effect, it would also make any blockchain transaction analysis useless (since coins could exchange hands offline hundreds or thousands of times without any trace in the blockchain or anywhere else on the Internet). It also removes the one to one mapping between addresses and persons - in the current system, once you've identified who owns a particular address, you can safely assume that any past or future payments sent to that address belong to that person. With OtherCoin in place, an address could effectively be "owned" by hundreds of people, just at different moments in time.

So OtherCoin proposes a more subtle change, one that would really make Bitcoin anonymous and isolated from any online intervention/analysis - that is harder to understand than a new mining chip or a new (online) fancy wallet. Or maybe I'm just nuts and people don't really care about their privacy and are perfectly ok with the pseudonymous nature of Bitcoin :).

Part of the issue might be trusting that secure transfer of private keys is actually possible.

Ok, is there anything that you think people need in order to confirm that this actually does what it says? Smartcards are not tamper-proof (nothing probably is), they are tamper resistant, but the cost of extracting a key from the smartcard might exceed the balance of said key.

If you're talking about the actual protocol used to move the key between cards, I can detail that as well. It's nothing fancy (you can't do very fancy stuff in JavaCard :) ). It's plain ECDH to negotiate a session key (each party verifies the other's public key first) and AES to encrypt the private key with the session key. Feel free to ask if you need me to go into details.

A more conclusive analysis of the cost of extracting a key would be a great help.

And yet this is the kind of project that would need tons of funding to really take off because it benefits/suffers from the network effect. The more people/merchants who would use OtherCoin, the more it would become useful and so on. And the more it would benefit Bitcoin in general.

It's a pity to see 21&Co... raising so much money for dubious projects while the promising ones are underfunded

With off chain transactions, what's the point of using a cryptocurrency then? I always believed that off-chain transactions far better suit centralized applications, as using it with a cryptocurrency basically makes the cryptocurrency itself irrelevant in the scheme of things since the transactions are done off-chain.

@drazvan
I stopped reading the whitepaper to ask here first.
So, you will not open source OpenCoin firmware and yet you suggest people simply trust you and risk their funds?

This doesn't make sense. I must be misunderstanding something.

OK, did read a little further to see that you reassure the reader that you are on the up and up.
How will you prove that the smartcard is not generating random-looking private keys which in fact are not random but have some deterministic element?

The OtherCoin Android application will be open source, it's just the part that runs on the secure microSD card that will be closed. The Android app generates its own random key that is _added_ to the one the smartcard generates and you can verify the Android app to ensure that the key is really random. So, even if the smartcard generates the most deterministic key (let's say it always generates 0 as its random key), you always add a random value of your own (generated by the Android app) to it. The result is obviously random (random + deterministic = random).

This is very similar to how vanity Bitcoin address generators work (see https://vanitypool.appspot.com/faq for instance). Also check out point #3 in the  "What it doesn't do" section of the whitepaper.

The whole point of OtherCoin is that it transacts _Bitcoin_, so there's no centralized authority that guarantees the funds. Whenever you want to get out, you don't have to check if the central issuer is still in business and they can't block your request or ask any questions - OtherCoin simply secures the transfer of _Bitcoin_ private keys that can be instantly redeemed on the blockchain. So it's off-chain but decentralized. The cryptocurrency is not irrelevant - it's the way you get your money in/out of the OtherCoin system. In most (all?) other off-chain systems, the central authority can not only track your payments (you tell them when you want to pay someone) but also control your deposits and withdrawals. With OtherCoin, deposits are simply Bitcoin payments to a random address that the app generates, withdrawals are simply private key sweeps (the app tells you the private key and destroys it from its secure storage). Transactions are off-chain and anonymous (you move Bitcoin private keys between offline devices).

Also take a look at http://bitcoin.stackexchange.com/questions/3853/can-one-safely-buy-vanity-addresses-from-a-third-party-without-risking-ones-coi - it contains a more technical description of why the way we do things in OtherCoin is safe for the end user (it's the exact same process).

Not all, but none widely deployed afaik, however openTXS systems have blind signature cash transfers that are untraceable by the server. The control aspect can be mitigated by a federation of servers facilitating blind transfers of the same/linked instruments.

There has been some research on the physical security of smartcards - I couldn't find any recent studies on cost, one study from 2004 ( http://www.cs.ru.nl/~erikpoll/hw/slides/04_smartcard_attacks.pdf ) indicates a cost of $100K for such an attack. The smartcard manufacturers (NXP and Infineon in our case) also guarantee their chips against side channel attacks if a strict set of rules is followed when running crypto algorithms - that's the reason we chose to stick with their proprietary functions instead of (possibly insecurely) implementing our own.

A server or a federation of servers would have to be maintained ($$$) and kept online and in business for the life of the product. It would also still know when a transaction takes place (just not the exact details). With OtherCoin, we don't know when a transaction takes place and even if we go out of business, the system still functions just fine (the software on the cards enforces the rules, not an online entity). This is also the reason I'm removing the centralized balance signing feature from the application and moving towards SPV proofs - even though it would make for a better business model (we could charge people a small fee to sign their balances), it would make the system vulnerable in case we go (or are forced) out of business. OtherCoin should not (and will not) depend on any online entity other than the Bitcoin network and should be as resilient as the Bitcoin network itself. 

Sounds ideal. Can't wait to test it out.

I was merely clarifying your "most(all?)" point(query?), nothing more.