Hardware wallet wire protocol

[slush]

So the real divergence here was that I assumed the device would be somewhat "independent."  It sounds like, instead, your device will be wholly dependent on a host computer to do most of the work for it, and the device will literally only sign.

Yes, exactly. You cannot expect full bitcoin implementation from the device with 256kB flash, 32kB RAM and a passive USB HID interface ;-). The purpose of the device is:
* Do not leak seed/private keys to the computer
* Confirmation of tx signing by the user, by displaying the transaction on the display and waiting for button press.

...and nothing more.

There will always be a computer-in-the-loop with your watching-only wallet to reformat the thing-to-be-signed into this low-level format for the device.

Exactly!

So, if you have some enormous transaction to sign, let's say with 100 inputs and the transaction data was 100 kB, can you at least hold 100 OutPoint-Value pairs in RAM?  i.e. you feed in first supporting transaction and output index (because your transaction will be spending that output from that tx) and the device will hash it and confirm that the hash and then store the hash and output value in RAM.  Then repeat for all supporting transactions to collect a list of "verified" outpoint-value pairs.  Then when you feed in the transaction to be signed, it can go through it's local memory to confirm each outpoint that belongs to you to be signed.

I designed something similar for input transactions, I call it "input streaming". In this way device don't need to store all inputs in the memory so the device can sign transaction with unlimited counts of inputs.

Although very high count of inputs may happen naturally (like when people are consolidating tiny pool payouts), having so many output transactions isn't so common and usually such complex transaction can be split into more smaller txes. However I over-looked the case of multisig transactions, where having very high number of outputs may be required as well. I'll try to propose some solution for this case too. Thank you for pointing to the problem...

Is that too crazy?

Not at all. I'd like to have a protocol which allow signing of data streams, without any limit to input and output transactions. As I described above, I already have a solution for input streaming, now I just need to think about output streaming. But this can be definitely solved...

[etotheipi]

By the way:  amusingly-relevant article on slashdot today about clocks getting off by 12 years...

http://news.slashdot.org/story/12/11/20/216234/ntp-glitch-reverts-clocks-back-to-2000

[etotheipi]

I designed something similar for input transactions, I call it "input streaming". In this way device don't need to store all inputs in the memory so the device can sign transaction with unlimited counts of inputs.

Although very high count of inputs may happen naturally (like when people are consolidating tiny pool payouts), having so many output transactions isn't so common and usually such complex transaction can be split into more smaller txes. However I over-looked the case of multisig transactions, where having very high number of outputs may be required as well. I'll try to propose some solution for this case too. Thank you for pointing to the problem...

Is that too crazy?

Not at all. I'd like to have a protocol which allow signing of data streams, without any limit to input and output transactions. As I described above, I already have a solution for input streaming, now I just need to think about output streaming. But this can be definitely solved...

Even without multi-sig, some people include a large number of outputs.   Many times, because it's inconvenient to actually execute an offline transaction, they may pool together many different outgoing transactions into a single transaction.  I know Armory users do this (I do it myself, sometimes), but usually because my offline computer needs to be booted in order to execute the tx and I'm just lazy   But for this reason, you probably need the device to be able to scroll so that it can display an arbitrary number of outputs.   I even have it on my own TODO list, to put Armory's confirmation list onto a scroll area to accommodate the rare times users specify two dozen outputs... (but I haven't had anyone complain yet, so I guess it's not common to do that many).

Something else that you need to accommodate:  since the device can't recognize its own addresses, it can't recognize its own change address.  Therefore, your protocol needs some way to tell the device which output is change -- perhaps specify the address index so that it can check that the marked change address truly is in your wallet.  Without it, the device doesn't know which is which, and even if the user understands how transactions and change work, a compromised desktop computer could swap the change address and the user wouldn't realize it's malicious. 

[someone42]

I designed something similar for input transactions, I call it "input streaming". In this way device don't need to store all inputs in the memory so the device can sign transaction with unlimited counts of inputs.

Although very high count of inputs may happen naturally (like when people are consolidating tiny pool payouts), having so many output transactions isn't so common and usually such complex transaction can be split into more smaller txes. However I over-looked the case of multisig transactions, where having very high number of outputs may be required as well. I'll try to propose some solution for this case too. Thank you for pointing to the problem...

You can do this if you re-order the fields* in the protocol buffer messages to match the order of the Bitcoin protocol (inputs before outputs, previous output reference before input script etc.). Then, you send the entire transaction through once per required signature. Each time an output is encountered, you prompt the user about it. This is merely an extension of your "streaming" idea, but applied to the whole transaction.

You can probably see the problem with this: the user will be prompted repeatedly, for each required signature. This makes for an unnecessarily bad user experience. This is how I intend to deal with the problem in my implementation:
1. While processing the transaction, a hash for signing needs to be calculated. In addition to this "signing hash", calculate an "input invariant hash" which is just like the signing hash, except it ignores all input scripts.
2. The input invariant hash will be the same regardless of which input is being signed (that's why it's called the "input invariant hash").
3. If the user fully approves a transaction, save that transaction's input invariant hash.
4. Include a field in the SignTx message which specifies whether the required signature is for a repeat of the previous transaction.
5. If the host specifies that the transaction is repeated, do not prompt the user.
6. In order to stop the host from lying about the status of the repeated transaction, compare the input invariant hash of the current repeated transaction with the saved input invariant hash, returning a Failure message if there is a mismatch.

The host signs a series of inputs like this:

Code:

tx = build_transaction();
is_repeated = 0;
for each input_number_to_sign in inputs:
        SignTx(tx, input_number_to_sign, is_repeated);
        is_repeated = 1;

*This brings me to something which will probably be a non-issue, but we should be aware of: (according to https://developers.google.com/protocol-buffers/docs/encoding) field ordering in a protocol buffer message is not guaranteed. Every serialiser will write out fields in field number order, but certain operations may not preserve this ordering.

[slush]

Something else that you need to accommodate:  since the device can't recognize its own addresses, it can't recognize its own change address.

If it is own address, desktop software should indicate this by filling "address_n" field in the message structure. Device can recalculate the address from the seed and this vector, so malicious machine cannot steal coins in this way.

[slush]

Then, you send the entire transaction through once per required signature. Each time an output is encountered, you prompt the user about it. This is merely an extension of your "streaming" idea, but applied to the whole transaction.

Yes, similar idea here.

You can probably see the problem with this: the user will be prompted repeatedly, for each required signature. This makes for an unnecessarily bad user experience. This is how I intend to deal with the problem in my implementation:

Yes, I had this idea yesterday as well, I've been just lazy do write it down O:-).

[slush]

Etotheipi, someone42, I'd like to know your opinion how to handle change addresses. There are basically two approaches:

a) When transaction is coming to self-address (validity can be verified by the device itself), hide output to change address from the user.
b) Show output to change address as normal output, it can be just displayed in slightly different way on the display.

ad a)
This is how bitcoin software is doing it now, although I don't like it much. User should see full information, otherwise there are some possible attacks. For example, by hiding change address from the UI, malicious (modified) software can send coins literally to /dev/null, by using some very high address vector for change address. Attacker don't take the money, but they're practically lost by the original owner.

ad b)
I see this approach as much safer. User see all outputs and it's only up to the desktop software to explain what's going up here. Change addresses are for example fully visible in Electrum and I don't think that people have any problem with it. Device still must support some kind of scrolling for multiple transaction outputs, so having one more output is not a problem.

[etotheipi]

Etotheipi, someone42, I'd like to know your opinion how to handle change addresses. There are basically two approaches:

a) When transaction is coming to self-address (validity can be verified by the device itself), hide output to change address from the user.
b) Show output to change address as normal output, it can be just displayed in slightly different way on the display.

ad a)
This is how bitcoin software is doing it now, although I don't like it much. User should see full information, otherwise there are some possible attacks. For example, by hiding change address from the UI, malicious (modified) software can send coins literally to /dev/null, by using some very high address vector for change address. Attacker don't take the money, but they're practically lost by the original owner.

ad b)
I see this approach as much safer. User see all outputs and it's only up to the desktop software to explain what's going up here. Change addresses are for example fully visible in Electrum and I don't think that people have any problem with it. Device still must support some kind of scrolling for multiple transaction outputs, so having one more output is not a problem.

It really depends on the target audience.  You and I are intimately aware of how Bitcoin works, under-the-hood, but non-techies think of their own wallet as a single number -- their balance.  They don't understand what "unspent outpoints" are, and why there is change, etc.  To them, they send 20 BTC to one address, they expect to see 20 BTC go to one address and their balance reduced by that much.  Forcing them to understand more than that is... a judgment call.

I've gotten lots of questions about "change addresses", and why it looks like users are sending coins to multiple people.  I tried to make it clear in the Armory tx display, but they don't always catch on.  For that reason, the "Standard" usermode in Armory tries to avoid making any mention of "change," for fear of confusing the user.

On the other hand, your device is not for absolute newbies (although many would argue that Armory isn't, either ).  I'm sure most of your users would understand what change is.  But I'm not sure displaying the change would make a difference -- even if they see it and understand it, they aren't going to know for sure that the displayed address is part of their own wallet.  The device verifying its own address is the roadblock to a malicious attack, not the user confirming it.

In fact, what will happen if the first 100 tx, the user sees the change output and confirms it.  On tx 101, the second addr pops up but isn't actually change (because it was maliciously replaced).  Is the user going to notice this is different?  Or just hit the "confirm" button twice like he always does because he's always confirming two outputs? 

[slush]

I'm trying to avoid some "extended usermodes", which just makes the flow more complicated and less universal.

Personally I'm not a fan of change addresses, but I understand that there's some demand for this feature. Change addresses are false promise of anonymity, because addresses in one wallet are still usually tainted enough that it's obvious they have common owner.

Now I have another idea - hide just transaction outputs which send coins to some input address which is mine. For wallets not using change addresses (like Elecrum has such option), you won't see "change" output. In this case users still can imagine wallet as you described - as an amount stored on some virtual account.

There's not enough space on the internal display to explain what change address is. If desktop software wants to use change addresses, then the change address (which is mine, but not in transaction input) can be visually marked (like inverted colors on the line or something) and it is up to the desktop software to explain its meaning to users.

[someone42]

Etotheipi, someone42, I'd like to know your opinion how to handle change addresses. There are basically two approaches:

a) When transaction is coming to self-address (validity can be verified by the device itself), hide output to change address from the user.
b) Show output to change address as normal output, it can be just displayed in slightly different way on the display.

ad a)
This is how bitcoin software is doing it now, although I don't like it much. User should see full information, otherwise there are some possible attacks. For example, by hiding change address from the UI, malicious (modified) software can send coins literally to /dev/null, by using some very high address vector for change address. Attacker don't take the money, but they're practically lost by the original owner.

ad b)
I see this approach as much safer. User see all outputs and it's only up to the desktop software to explain what's going up here. Change addresses are for example fully visible in Electrum and I don't think that people have any problem with it. Device still must support some kind of scrolling for multiple transaction outputs, so having one more output is not a problem.

I'm not so sure that displaying the change address deals with the "malicious send to /dev/null" attack described above. For example, say the device displays "change of 0.05581992 BTC was sent to 1HoYQQeA3BxWisDK3VtGFNbvnNPcoZTE5n". How do you even know whether that's a "genuine" change address?

Perhaps a better solution is to display the change address index instead. There is an immediately apparent difference between "change was sent to address 18" and "change was sent to address 1156397331". But will users understand this?

Another option is to require change addresses to be explicitly and sequentially generated by the wallet. However, this does require an internal counter that is incremented every time a change address is generated. The malicious change address attack is prevented because the wallet is presumably unable to generate millions of change addresses in any reasonable time.

[slush]

I'm not so sure that displaying the change address deals with the "malicious send to /dev/null" attack described above. For example, say the device displays "change of 0.05581992 BTC was sent to 1HoYQQeA3BxWisDK3VtGFNbvnNPcoZTE5n". How do you even know whether that's a "genuine" change address?

Yes, that's why I don't like the concept of change addresses. You must trust the bitcoin software that it generates some reasonable address for you, instead of just checking if one output address is going to the address you want and second output address is going back to one of original addresses (which can be even checked by the device).

Perhaps a better solution is to display the change address index instead. There is an immediately apparent difference between "change was sent to address 18" and "change was sent to address 1156397331". But will users understand this?

No :-(. I've been thinking about this too, but I'm affraid that "address index" is out of game for end users.

Another option is to require change addresses to be explicitly and sequentially generated by the wallet. However, this does require an internal counter that is incremented every time a change address is generated. The malicious change address attack is prevented because the wallet is presumably unable to generate millions of change addresses in any reasonable time.

Internal counter don't solve anything, because you can use the same seed on another device. This creates completely different set of problems.

[etotheipi]

I really don't think you're getting any value out of this.  The device can internally confirm that the change address belongs to your own wallet, and asking for user confirmation doesn't add any security -- but it does create confusion.  Even if users know what they're doing, they may accidentally confirm through a malicious change address because they are always asked to confirm two addresses when they send a tx with one target. 

I'd prefer, instead, that the second address only comes up when it is not part of their wallet.  If the user created the tx to go to 2 people, they'll expect to confirm twice, etc.  If they are asked for 3 confirmations, they'll immediately recognize something isn't right.  

[slush]

Is there really any benefit of using newly created change addresses? Except that this is default in Satoshi's client. This is the main question, because the risk is exactly in using freshly generated address which validity cannot be confirmed by the device or by the user...

If there's no clear benefit in using new change addresses, I'm inclining to display them to confirm as any other addresses.

[etotheipi]

Is there really any benefit of using newly created change addresses? Except that this is default in Satoshi's client. This is the main question, because the risk is exactly in using freshly generated address which validity cannot be confirmed by the device or by the user...

If there's no clear benefit in using new change addresses, I'm inclining to display them to confirm as any other addresses.

There's the non-zero benefit of:  ECDSA is secure right now... but if it wasn't, using new addresses still keeps your coins secure because your private key can't be broken if your public key isn't even known.  i.e. -- if you send back to an address that has its public key already in the blockchain, then in the far future if ECDSA is broken and/or quantum computers start becoming a reality, then you are vulnerable.

And of course -- the privacy aspect is improved. As you said, privacy is not guaranteed when using new addresses, but it's also not as bad as just reusing old ones.

[slush]

There's the non-zero benefit of:  ECDSA is secure right now... but if it wasn't, using new addresses still keeps your coins secure because your private key can't be broken if your public key isn't even known.  i.e. -- if you send back to an address that has its public key already in the blockchain, then in the far future if ECDSA is broken and/or quantum computers start becoming a reality, then you are vulnerable.

If this become a problem, then it is only the matter of software update to start using newly generated addresses. For now this is non-issue.

And of course -- the privacy aspect is improved. As you said, privacy is not guaranteed when using new addresses, but it's also not as bad as just reusing old ones.

Well, I accept that. Still we need to balance between security/usability/anonymity and I see using artifically created new addresses as a quite big risk. There's still enough time to think about it a bit more...

[etotheipi]

There's the non-zero benefit of:  ECDSA is secure right now... but if it wasn't, using new addresses still keeps your coins secure because your private key can't be broken if your public key isn't even known.  i.e. -- if you send back to an address that has its public key already in the blockchain, then in the far future if ECDSA is broken and/or quantum computers start becoming a reality, then you are vulnerable.

If this become a problem, then it is only the matter of software update to start using newly generated addresses. For now this is non-issue.

And of course -- the privacy aspect is improved. As you said, privacy is not guaranteed when using new addresses, but it's also not as bad as just reusing old ones.

Well, I accept that. Still we need to balance between security/usability/anonymity and I see using artifically created new addresses as a quite big risk. There's still enough time to think about it a bit more...

I don't understand the risk.  The desktop computer is perfectly capable of creating a new address in the same deterministic wallet, and telling the device what the address index is so that it can recognize it.  The user doesn't even have to know it's there, as long as the device is doing its job to verify ownership of the address. 

(1) If the device doesn't recognize the second address, the user must confirm the extra output, which will look suspicious.
(2) If the device does recognize it, then the user only confirms the original output they were expecting to see

[slush]

(2) If the device does recognize it, then the user only confirms the original output they were expecting to see

And what if computer ask for using address with index [2^32, 2^32, 2^32, 2^32] ? Don't forget that BIP32 is hierarchical. Good luck recovering coins send somewhere to this address space...

[etotheipi]

(2) If the device does recognize it, then the user only confirms the original output they were expecting to see

And what if computer ask for using address with index [2^32, 2^32, 2^32, 2^32] ? Don't forget that BIP32 is hierarchical. Good luck recovering coins send somewhere to this address space...

Oh, I missed that part.  I forgot that BIP 32 doesn't require computing addresses in order (Armory current wallets do require computing in the chain, but that has turned out to be more of a curse than a blessing, but would be useful here).  But I see your point, now.   And the suggestion about storing an index on the device and or displaying it for the user, makes more sense, now.

I'll think about that one...

[etotheipi]

Well here's an idea:  can the device at least store how many times it's ever created signatures?  Or something else that is at >=1 for each transaction it ever deals with?

Here's what I'm getting at:  BIP 32 allows for random access to any address, but it also specifies using a separate subchain for change addresses (the "internal" subchain).  This may have been overlooked by you early on for simplicity reasons, but it is part of the spec.   The idea is that change addresses will only ever come from this the internal chain, and that chain will never receive coins from any other source except the "external" chain (the main chain that is used for distributing payment addresses). 

The relevance is that the "internal" chain is very dense.  There will not be any gaps in the internal chain.  In fact, the highest index ever used in this chain should be about equal to the number of transactions ever signed by the device.   Therefore, if you implement both roots on the device, the device can safely declare that "a change address with an index higher than the number of transactions I've ever signed is invalid." 

[slush]

Yes, the device can store some simple counter, but I'm affraid that the overal design is becoming a bit fragile.

Technically you can have many devices or desktop wallets working on the same seed, but the device don't have independent access to the full blockchain, so it depends on information provided by the host computer.

Now we must decide what should device do if computer propose change address above current counter state...