Hardware wallet wire protocol

[slush]

Can you elaborate?

It has significant advantage as your wallet has been created recently. You created wallet around block 200k, so you need to synchronize only around 10k of blocks (20x speedup). However in few years of usage, on block 1M, you'll need to synchronize 800k of blocks. Then the advantage of timestamp is almost neglible, because the speedup will be only 0.2x (probably a lot less, as blocks are bigger and bigger).

[jgarzik]

Can you elaborate?

It has significant advantage as your wallet has been created recently. You created wallet around block 200k, so you need to synchronize only around 10k of blocks (20x speedup). However in few years of usage, on block 1M, you'll need to synchronize 800k of blocks. Then the advantage of timestamp is almost neglible, because the speedup will be only 0.2x (probably a lot less, as blocks are bigger and bigger).

All this is predicted on an invalid assumption:  the common case will be older, existing bitcoin users carrying around one big wallet.

First, wallet creation date is much different than individual key creation dates.

Keys are constantly created, therefore a portion of the wallet state is always created recently.  As blocks get bigger and bigger, key birthday reduces the number of keys one must scan in each block, especially if key retirement is also supported.

Long term you will have a rolling window of keys, no matter when the wallet is created.  Key birthdays will always be relevant and useful, for this reason.

Furthermore, there will always be new users creating new wallets, and users with multiple wallets.

[slush]

First, wallet creation date is much different than individual key creation dates.

...except the device doesn't with the keys, but with the seed (BIP32/Electrum). Device don't store private keys or any metadata for particular addresses.

However such metadata can be stored on the computer, using master public key as a wallet identifier.

Edit: Device can teoretically store timestamp of the seed generation, as some quick-and-dirty workaround. However this still must be provided by the computer, which will probably just ask the user.

[jgarzik]

Birthday is of continuing relevance to:  new users, new wallets.

[etotheipi]

First, wallet creation date is much different than individual key creation dates.

...except the device doesn't with the keys, but with the seed (BIP32/Electrum). Device don't store private keys or any metadata for particular addresses.

However such metadata can be stored on the computer, using master public key as a wallet identifier.

Edit: Device can teoretically store timestamp of the seed generation, as some quick-and-dirty workaround. However this still must be provided by the computer, which will probably just ask the user.

I've been battling this concept in Armory with its deterministic wallets, for a while.  I implemented "blockCreated" and "timeCreated" variables for each address, but I have been hesitant to actually use them for anything.  Because, I determined that getting it wrong was not worth the performance benefit of when it is right:  if you trust the timestamps are created and stored correctly, but it turns out that something was wrong (incorrect clock when it was stored), the user could be missing a big chunk of their wallet and it could be a mess trying to figure out what happened (during recovery of a deterministic wallet, that is).   Plus, even if it is right, unless the user knows exactly how much they had they don't know that it's right unless you do the full scan anyway.  At least for right now, doing the full scan isn't that much more cumbersome than a partial scan, so it's easier to just do it.

I don't know how the HW device will be dealing with addresses (or what is possible memory-wise), but I have found it extremely useful to store the keys even though they are derived from the root.  Not only does it allow me to store birthdays and comments/labels, but (most importantly) I can search for an address and know if it's in my wallet without re-doing all the computation.  If it's possible to at least maintain addr160 list in non-volatile memory, it will make everything quite a bit easier.

I am hesitant to "endorse" requiring key-indexes to be included in the TxDPs (as I call them in BIP 10, perhaps another phrase+acronym would be better).  The reason is to do with multi-sig, which makes sense to accommodate here -- since there's like 90% overlap between what's needed for offline wallets and multi-sig.   There will be situations where the TxDP will be created by another party who doesn't have your watching-only wallet, they are only supplied a public key to include in the transaction.  They don't know how to specify what your address index is, and your offline device will have no way to detect what public keys belong to you.  I guess you could have an optional field so that your online computer could "amend" the TxDP with your address index, but that sounds complicated.

I know it sounds premature to think about multi-sig for your HW device, but I don't think it makes sense to over-complicate that use case if it can be avoided.  If we must accommodate devices that can't even store their own address list, then we have to deal with it, but it's worth trying to avoid.  And in the end, even with 5000 addresses, that's only about 100 kB to store a raw addr160 list...

[jgarzik]

I've been battling this concept in Armory with its deterministic wallets, for a while.  I implemented "blockCreated" and "timeCreated" variables for each address, but I have been hesitant to actually use them for anything.  Because, I determined that getting it wrong was not worth the performance benefit of when it is right:  if you trust the timestamps are created and stored correctly, but it turns out that something was wrong (incorrect clock when it was stored), the user could be missing a big chunk of their wallet and it could be a mess trying to figure out what happened (during recovery of a deterministic wallet, that is).   Plus, even if it is right, unless the user knows exactly how much they had they don't know that it's right unless you do the full scan anyway.  At least for right now, doing the full scan isn't that much more cumbersome than a partial scan, so it's easier to just do it.

The clock might be wrong... but it's not gonna days or weeks wrong.

You have to include variability anyway, because blocks can vary.  So given birthday X, start scanning at X minus 2 days, or X minus 1 week.

[stick]

The clock might be wrong... but it's not gonna days or weeks wrong.

That's wrong assumption. If the battery on your motherboard is empty the date would be 1.1.1970. I can come up with some other scenarios where the date/time is seriously incorrect.

[jgarzik]

The clock might be wrong... but it's not gonna days or weeks wrong.

That's wrong assumption. If the battery on your motherboard is empty the date would be 1.1.1970. I can come up with some other scenarios where the date/time is seriously incorrect.

You're stretching.  Anything is "possible" but using a 0.01% case to justify giving new users a bad experience is not reasonable.

[etotheipi]

The clock might be wrong... but it's not gonna days or weeks wrong.

That's wrong assumption. If the battery on your motherboard is empty the date would be 1.1.1970. I can come up with some other scenarios where the date/time is seriously incorrect.

You're stretching.  Anything is "possible" but using a 0.01% case to justify giving new users a bad experience is not reasonable.

I'm not sure.  The "cost of misclassification" is not symmetric.  It takes 5 minutes to do it right 99.9% of the time, but it takes 7 min to do it right 100.0% of the time.  And given the heartache associated when it's done wrong, why not just take the 7 minutes?  At least, that's been my attitude, even if you don't agree with the trade-off. 

[2112]

The clock might be wrong... but it's not gonna days or weeks wrong.

Hardcore Americanism detected!  

The month-day-year versus day-month-year ambiguity with dates is an endless source of the errors that stick is thinking about. People in USA don't see is as often because most of the BIOSes and other low-level tools use the American layout. But it trips over many Europeans.

Wait till Americans start importing Czech-made wallets that use day-month-year order...

[etotheipi]

The clock might be wrong... but it's not gonna days or weeks wrong.

Hardcore Americanism detected!  

The month-day-year versus day-month-year ambiguity with dates is an endless source of the errors that stick is thinking about. People in USA don't see is as often because most of the BIOSes and other low-level tools use the American layout. But it trips over many Europeans.

Wait till Americans start importing Czech-made wallets that use day-month-year order...

I personally hate the American system.  It doesn't make any sense.  Though, I'm not sure how relevant it is here:  UTC unix time is the "path of least resistance" for storing timestamps in binary files, and thus wouldn't have that problem.

Part of the reason I avoided this is because there's a lot that can go wrong with offline computers.  The clocks could be totally wrong with no access to the internet, and thus they don't know the block height at birth, either.  I could insert special cases where I know one or the other based on what information is available at the time it was recorded in the log file.  But then I have to treat all conditions of {have/donthave} {block/time}.  And as I said... I think getting it wrong and silently missing parts of the user's wallet could be a disaster -- those could literally be lost forever, because no program that ever reads the file would check before the recorded time.

The end result is that users would just want to scan everything anyway, just to be sure. 

[kjj]

The clock might be wrong... but it's not gonna days or weeks wrong.

Hardcore Americanism detected!  

The month-day-year versus day-month-year ambiguity with dates is an endless source of the errors that stick is thinking about. People in USA don't see is as often because most of the BIOSes and other low-level tools use the American layout. But it trips over many Europeans.

Wait till Americans start importing Czech-made wallets that use day-month-year order...

I personally hate the American system.  It doesn't make any sense.  Though, I'm not sure how relevant it is here:  UTC unix time is the "path of least resistance" for storing timestamps in binary files, and thus wouldn't have that problem.

Part of the reason I avoided this is because there's a lot that can go wrong with offline computers.  The clocks could be totally wrong with no access to the internet, and thus they don't know the block height at birth, either.  I could insert special cases where I know one or the other based on what information is available at the time it was recorded in the log file.  But then I have to treat all conditions of {have/donthave} {block/time}.  And as I said... I think getting it wrong and silently missing parts of the user's wallet could be a disaster -- those could literally be lost forever, because no program that ever reads the file would check before the recorded time.

The end result is that users would just want to scan everything anyway, just to be sure. 

The european system is just as stupid, just incompatibly so.  ISO8601 puts magnitude in the proper order on all scales, and there hasn't been a valid excuse for using anything else in a long, long time (when you need actual dates, not seconds-from-epoch).

If you don't know the proper birthdate of a key or wallet, set it to zero so you get a full rescan.  Key birthdates is something I wish for about twice a week.  I do a lot of private key importing because I work with offline key generation.  The raw transaction API lets me bypass a lot of that, but not all.

If you don't think that key birthdays are important, just give it a few more years.  If bitcoin is going to take off, transaction volume (and thus scan complexity) is going to grow much faster than Moore's law, and the rescan that you think is just fine now will be downright painful soon.

P.S.  NTP has been around since 1985, if someone doesn't know if their clock is right or not, they deserve what they get.

[2112]

P.S.  NTP has been around since 1985, if someone doesn't know if their clock is right or not, they deserve what they get.

I'm fully with you on the use of ISO format for dates, but I disagree on the NTP for autoconfiguration.

NTP abuse is so rampant that it now has its own notable Wikipedia article:

http://en.wikipedia.org/wiki/NTP_server_misuse_and_abuse

And thats just a tip of iceberg. In many locales servers like "time.windows.com" are unreachable because of the rampant abuse by the various software licensing/subscription enforcement schemes. McAfee private-label products were implicated in DDoS-ing Swiss government NTP servers, if I recall correctly. And apparently the situation is slowly getting worse, not better.

[kjj]

P.S.  NTP has been around since 1985, if someone doesn't know if their clock is right or not, they deserve what they get.

I'm fully with you on the use of ISO format for dates, but I disagree on the NTP for autoconfiguration.

NTP abuse is so rampant that it now has its own notable Wikipedia article:

http://en.wikipedia.org/wiki/NTP_server_misuse_and_abuse

And thats just a tip of iceberg. In many locales servers like "time.windows.com" are unreachable because of the rampant abuse by the various software licensing/subscription enforcement schemes. McAfee private-label products were implicated in DDoS-ing Swiss government NTP servers, if I recall correctly. And apparently the situation is slowly getting worse, not better.

Yeah, I know.  On the other hand, DHCP can provide local NTP servers.

Timekeeping is one of the things that really pisses me off.  There is absolutely no excuse for any network operator to fail to provide and advertise local NTP servers.  GPS receivers with PPS interfaces have been dirt cheap and quite common for 10 or 15 years now, and ntpd supports them all.  Doing it right is well within the technical and financial means of any network provider.  Hell, within the means of most college students.

And device makers suck.  It isn't hard at all to implement NTP properly, but no one seems to until they end up on slashdot.  And times are changing; even the dinosaurs that have kept PBX systems in the dark ages have started to catch on.

[slush]

Implementing NTP directly in the device is without a chance, it is completely out of the focus.

However there can be some API for storing/retrieving timestamp to/from the device. But it will be just a dumb storage of the value and it will be up to the computer's software if it will use it or not. I cannot imagine anything useful what can be done with the timestamp by the device.

You're right that timestamps will be probably more and more in the future as people typically use recent wallets. Except that the device is designed more like a cold storage, so that timestamp optimization won't improve user experience for most of the users. Still, if storing timestamp of the seed generation will be useful, we can include it.

[etotheipi]

Implementing NTP directly in the device is without a chance, it is completely out of the focus.

However there can be some API for storing/retrieving timestamp to/from the device. But it will be just a dumb storage of the value and it will be up to the computer's software if it will use it or not. I cannot imagine anything useful what can be done with the timestamp by the device.

You're right that timestamps will be probably more and more in the future as people typically use recent wallets. Except that the device is designed more like a cold storage, so that timestamp optimization won't improve user experience for most of the users. Still, if storing timestamp of the seed generation will be useful, we can include it.

Yeah, we don't need to get too sidetracked on that topic.  I was just stating that even if you could store timestamps with each address, I'm not sure you're getting too much value out of it.

However, let me get back to the previous topic I brought up -- what's the chance you could store a raw addr160 list on the device?  Here's what I said before:

I don't know how the HW device will be dealing with addresses (or what is possible memory-wise), but I have found it extremely useful to store the keys even though they are derived from the root.  Not only does it allow me to store birthdays and comments/labels, but (most importantly) I can search for an address and know if it's in my wallet without re-doing all the computation.  If it's possible to at least maintain addr160 list in non-volatile memory, it will make everything quite a bit easier.

I am hesitant to "endorse" requiring key-indexes to be included in the TxDPs (as I call them in BIP 10, perhaps another phrase+acronym would be better).  The reason is to do with multi-sig, which makes sense to accommodate here -- since there's like 90% overlap between what's needed for offline wallets and multi-sig.   There will be situations where the TxDP will be created by another party who doesn't have your watching-only wallet, they are only supplied a public key to include in the transaction.  They don't know how to specify what your address index is, and your offline device will have no way to detect what public keys belong to you.  I guess you could have an optional field so that your online computer could "amend" the TxDP with your address index, but that sounds complicated.

I know it sounds premature to think about multi-sig for your HW device, but I don't think it makes sense to over-complicate that use case if it can be avoided.  If we must accommodate devices that can't even store their own address list, then we have to deal with it, but it's worth trying to avoid.  And in the end, even with 5000 addresses, that's only about 100 kB to store a raw addr160 list...

If the hardware device can only store the root, then it's going require either:  (1) a computer holding the watching-only wallet for the offline device to create the TxDP to be signed, or (2) When you give someone your public key for a multi-sig tx you gotta supply an address index with it somehow so they can include it, or (3) The TxDP must pass through the computer holding the watching-only wallet so that it can be amended with the correct address index. 

[slush]

However, let me get back to the previous topic I brought up -- what's the chance you could store a raw addr160 list on the device?  Here's what I said before:

Why we should store addresses on the device, when the address can be generated on the request from the seed?

the computation.  If it's possible to at least maintain addr160 list in non-volatile memory, it will make everything quite a bit easier.

Generate such list of addresses is a matter of second for the desktop machine. Using the device's memory for storing the list will limit the usability. For example we're using platform with 256kB memory for both application and data. Thanks to memory fragmentation, only limited part of that 256kB can be used for data storage.

I am hesitant to "endorse" requiring key-indexes to be included in the TxDPs (as I call them in BIP 10, perhaps another phrase+acronym would be better).

As far as I understand the BIP10, it is out of the scope for such device. Device requires very minimal interface and it needs prepared data by the computer. For example it requires streaming of inputs in separate messages to allow signing of huge transactions. However desktop software using the device for signatures can be BIP10 compatible, of course.

There will be situations where the TxDP will be created by another party who doesn't have your watching-only wallet, they are only supplied a public key to include in the transaction.  They don't know how to specify what your address index is, and your offline device will have no way to detect what public keys belong to you.

Public keys can be derived from master public keys stored in offline wallet, so yes, desktop software can compute indexes just from public keys.

If the hardware device can only store the root, then it's going require either:  (1) a computer holding the watching-only wallet for the offline device to create the TxDP to be signed

Yes, this is expected. Software can download master public key from the device, store it offline and then handle it as an offline wallet, generate addresses or so.

[etotheipi]

I think we diverged here.  I was kind of under the impression that we were coming up with a BIP 10+ that was more versatile (like, having a compact binary representation) so it could also be implemented in your device.   I'd really like to see this "protocol" standardized across devices and applicaitons -- which was the original goal of BIP 10, but I was the only one using it, so it never really got the versatility of a real "standard"... I stopped developing it when it worked for Armory, knowing it would be expanded later.

So, I was hoping that your device would simply implement the same BIP 10+, and everyone is happy.  I'm looking for the possibility that someone who creates a TxDP on their desktop, and requiring 3 other signatures, some of which may come from regular desktops, offline computers and/or your devices, that there won't need to be any special conversion for your device to be able to understand it, recognize its own keys, and sign it (after user confirmation).

With that in mind, I think someone42 mentioned the device won't hold its own address list, and thus this protocol requires telling the device which keys belong to it and what address index those keys are in the wallet.   I really wanted to avoid that, if possible, since it complicate other use cases.  It sounded like you said the device could regenerate all of its addresses/public keys from the root ... but given the other limitations of the device, I would think that calculating 200 public keys from a root private key every time would take a while.  And once you've used it a lot, 200 may not be enough.  If this is an unavoidable implementation, then we may be required to split the use cases into different "standards", but I hope you recognize the value of aiming for a single standard.

tl;dr  The protocol can easily be unified with all other devices/applications (i.e. BIP 10+) if you can have the device recognize its own addresses/pubkeys.  I was hoping for that unification, but it may not be achievable/efficient to do so.

[slush]

I think we diverged here.  I was kind of under the impression that we were coming up with a BIP 10+ that was more versatile (like, having a compact binary representation) so it could also be implemented in your device.

The protocol which I proposed is built on top of Protocol buffers. Having a separate parser for another format just to comply with BIP10 doesn't look smart enough.

 I'd really like to see this "protocol" standardized across devices and applicaitons -- which was the original goal of BIP 10, but I was the only one using it, so it never really got the versatility of a real "standard"... I stopped developing it when it worked for Armory, knowing it would be expanded later.

The conversion from BIP10 to something built on top of PB can be quite straightforward, so even BIP10-compatible software might convert the format for the device easily. To be honest, I didn't study internals of the BIP10 protocol yet, I just watched the protocol format.

...that there won't need to be any special conversion for your device to be able to understand it

You still need some desktop software to work with the device. As far as Armory or Electrum will support this device and Armory or Electrum implements BIP10, there's really no need why device itself must understand BIP10. Or any simple desktop (command line) tool can convert BIP10 format and pass the transaction into the device over USB.

 It sounded like you said the device could regenerate all of its addresses/public keys from the root ... but given the other limitations of the device

It will be computed by the computer, not by the device. I don't see problem here.

The protocol can easily be unified with all other devices/applications (i.e. BIP 10+) if you can have the device recognize its own addresses/pubkeys.  I was hoping for that unification, but it may not be achievable/efficient to do so.

This protocol is low-level layer for communication between the device and desktop software. This protocol must be optimized for low-resource devices and must be really minimal. There's no need why this should use BIP10 at all.

[etotheipi]

I think we diverged here.  I was kind of under the impression that we were coming up with a BIP 10+ that was more versatile (like, having a compact binary representation) so it could also be implemented in your device.

The protocol which I proposed is built on top of Protocol buffers. Having a separate parser for another format just to comply with BIP10 doesn't look smart enough.

 I'd really like to see this "protocol" standardized across devices and applicaitons -- which was the original goal of BIP 10, but I was the only one using it, so it never really got the versatility of a real "standard"... I stopped developing it when it worked for Armory, knowing it would be expanded later.

The conversion from BIP10 to something built on top of PB can be quite straightforward, so even BIP10-compatible software might convert the format for the device easily. To be honest, I didn't study internals of the BIP10 protocol yet, I just watched the protocol format.

...that there won't need to be any special conversion for your device to be able to understand it

You still need some desktop software to work with the device. As far as Armory or Electrum will support this device and Armory or Electrum implements BIP10, there's really no need why device itself must understand BIP10. Or any simple desktop (command line) tool can convert BIP10 format and pass the transaction into the device over USB.

 It sounded like you said the device could regenerate all of its addresses/public keys from the root ... but given the other limitations of the device

It will be computed by the computer, not by the device. I don't see problem here.

The protocol can easily be unified with all other devices/applications (i.e. BIP 10+) if you can have the device recognize its own addresses/pubkeys.  I was hoping for that unification, but it may not be achievable/efficient to do so.

This protocol is low-level layer for communication between the device and desktop software. This protocol must be optimized for low-resource devices and must be really minimal. There's no need why this should use BIP10 at all.

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.  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.   I had anticipated the device take, from any computer anywhere, a BIP10-like data stream, recognize it's own public keys/addresses, and get user confirmation to sign it.

Okay, we're on the same page now.  My point is valid, that a BIP10+ could potentially serve this purpose if we added extra complexity to accommodate devices that don't even know their own address pool, but it's not necessary.

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.

Then, it sounds like, if that transaction is actually 100 kB, then you can't even hold the whole thing at once.  If you have to sign 30 inputs, you would pass it in 30 times, each time with a different txin-script-in-txout-script-place-and-all-others-blanked.  The thing can accumulate the hash as it goes, and then pass out the signatures one at a time when it's done reading the final transaction.

Is that too crazy?  Or should the device be limited to handling transactions that will fit nicely into its cache?  It could be a requirement of the software that interfaces it (Armory, Electrum, etc), that it will prevent the user from sending tx bigger than X kB...?  However, even if this tx is within the size limit, there's no guarantee that any of your supporting transactions is within the size limit.