SIGHASH_WITHINPUTVALUE: Super-lightweight HW wallets and offline data

[etotheipi]

I bring this up, because as long as we've committed ourself to a [potential] hardfork in the next month, I think the following should be seriously considered.  Why?  Because "cold storage" is becoming a major force in the Bitcoin world.  More and more people and companies are looking at the benefits and trying to get it setup.  More people are finding themselves wealthy and want to protect it.  It is the holy grail of wallet security (multi-sig, too, but that will probably include offline wallets, instead of replacing it).    But implementation suffers from one extraordinary hurdle.


Example:

Let's say I want to create a $10 offline signing device.  I will put 32 kB of RAM and a small screen and a tiny embedded chip that is just powerful enough for ECDSA signing.   It will sign transactions for me after asking me to physically confirm with a button press.  But the device has so little RAM, it can't support arbitrary transactions.  So, I'll just make sure my online computer software never produces transactions bigger than 10 kB, and just do multiple transactions if necessary.  In Armory, I'll happily make that a configurable parameter.

But there's a serious problem here:  this isn't possible (and the Trezor ran into this).  Because of a tiny little oversight by Satoshi, nothing about the 10kB transaction indicates what the transaction fee is.  Without access to the blockchain, my tiny little device doesn't know whether it's signing 1 BTC input, or 1000 BTC input.  To accommodate this, you must supply all supporting transactions along with the one to be signed (and BIP 10 does this).  By doing this, the offline device can hash the supporting transaction, verify it matches the TxIn it is signing, and then record the 8-byte amount/value from that transaction.   It's a lot of work to verify those 8 bytes...

Worse, I don't have control over this.  I can choose never to create transactions bigger than X kB, and pick X based on my HW.  But if my wallet contains a UTXO that comes from a 100 kB transaction, I have to upload 100 kB to my offline device, just to verify those 8 bytes.  This forces devices like the Trezor, to implement streaming calculations, complicating the protocol 10-fold.  

If you don't do this, an attacker compromising the online computer could trick your offline computer into signing away your entire wallet to transaction fee.  While it's not the most direct way for the attacker to make money, it's the most direct way to ruin you by sending your life savings to some lucky miner (and they may have a way to benefit from it, like owning some mining power).

EDIT: I shouldn't focus entirely on the signing hardware.  Another major problem is bandwidth:  there's a lot of good ways to transfer a few kB securely between an online and offline computer, but not on the order of megabytes.  QR codes are such a method that I keep shooting down, because I have no idea how to make it work with MB of data.


Raw Technical Solution:

All this because Satoshi made one little oversight in the OP_CHECKSIG procedure:  the TxOut script is copied into the input being signed, but not the value.  If the value was copied prepended to the TxOut script, then the offline system only needs to be given the 8 bytes, and it could securely present the correct fee to the user and sign it.  If an attacker compromises the online computer and puts incorrect values into there to trick the offline computer, the offline signature will be invalid (because full nodes verifying the transaction will use the correct value the signature won't match).  

So the technical solution is simple:  Add a new SIGHASH type, which I dub SIGHASH_WITHINPUTVALUE.  This would have hashcode 0x10.  This would be OR'd with the existing hash types.  i.e. Currently all "regular" transactions are signed with (SIGHASH_ALL), now anyone who wants the benefit would sign with (SIGHASH_ALL | SIGHASH_WITHINPUTVALUE).  It is compatible with the existing hash types.

Analogy:
Right Now:  "I, the offline computer, sign this input to be sent to this address, no matter how much this input is worth"
Proposal:  "I, the offline computer, have been told this input is worth 13.28 BTC.  This signature is only valid if that's how much it's actually worth"


Considerations:

This solution has some nice properties:

• Simple!  For the signing and verification procedures, it's probably only a few lines of code.
• I have full control over data sizes to be exchanged with the offline device, down to the minimum of being able to sign a one-input-one-output transaction.  Currently, there's no way to avoid having to deal with 100kB-200kB of transaction data transfer (and if you want to be able to sign multi-input tx, you need to be able to handle megabytes)
• Also makes it resistent to changes at the network level: we plan to allow only 100 kB transactions right now.  So without this new SIGHASH, I design my device to handle up to 100kB.  But in two years, the limit is raised and people start mining 1 MB transactions, and I find that one of my inputs was from a 1 MB transaction.  Hardware upgrade?  Remember, the offline wallet needs to handle 100.0% of all transactions!  
  
• No problems with backwards compatibility:  Once the change goes into effect, new devices can be made and wallet software updated, to only use the new SIGHASH type.  It can be used even on wallets that already contain coins... because it only changes what is being signed.
• Should be completely non-controversial (technically):  this adds an optional restriction to transaction validity.  It doesn't change overall network topology or philosophy at all.  It's like asking the network to confirm, for the signer, that they were given the right value when signing.  That's all.

Downsides:

• Hardfork (of course).  But we've committed ourselves to a hard-fork next month, anyway.  And the extra hashtype would simply be "present" next month, but not become usable for 6-12 months, to allow time for upgrades.  I think this change has the right combination of simplicity and benefit to be worth throwing in
• Other clients would break if they're not paying attention and they are in the habit of verifying their own transactions.  Oblivious nodes would still be able to sign transactions, just not verify them.  Not so important for nodes that already trust the network to verify validity of transactions, but I'm sure things would break.

Anyone who has worked on offline wallets knows what a PITA it is to have to deal with supporting transactions.  Most of the ideas proposed in the Improving Offline Tx thread, were shot down because the solution needs to support multi-megabyte transfers.  This solution would eliminate that necessity.

[1713979362]

1713979362

[1713979362]

1713979362

[1713979362]

1713979362

[refaelsh]

Why are We committed to a hard fork next month?

[apetersson]

Why are We committed to a hard fork next month?

because of the BDB locking problem in 0.7. basically, we want to at least allow 1 MB blocks as intended.

[TierNolan]

What about using something like a 2 step transaction.

I create a transaction which pays to a new address for 0.1BTC and then signs a transaction which pays from that address to the actual target.

The intermediate address would be generated by the offline system and would be once off.

However, assuming it is accepted, your proposal is cleaner.

Another point is raises is that people should have hard fork ideas ready along with pull requests in the hopes of a mandatory hard fork .  Your idea also has the nice property of being relatively easy to implement quickly.

[Sergio_Demian_Lerner]

+1

Excelent idea. But if we are going to hardfork,  it´s time to rethink how the hash of the tx  is computes for signature verification. 
First, we should ban OP_CODESEPARATOR.

But I think the right way to do SIGHASH_WITHINPUTVALUE it is to put the amount outside the script, in another field, and stop embeding things in the input script.

Let
 
Tx' = Tx with all script inputs cleared

TxHash(Tx) = H ( H(Tx') | n | [ amount ] )

Where H() is a double SHA-256 hash. n is the input being verified and amount is the optionally amount.

The advantage of this scheme is that H(Tx) can be cached for the whole transaction, and the second application of H() is very fast. This prevents by design the vulnerability CVE-2013-2292 and it would allow to permit transactions over 100 Kbytes to be standard again.

[btchip]

+1 * 2

H(Tx') is useful as well when obtaining a single user confirmation for the whole transaction signing process.

FYI, the way I deal with this issue today (specification update pending), to make things easier :

- A new "trusted input" type is added. A trusted input is : transaction hash + index (prevout) / amount / signature of the previous data (using a key known only by the device)
- The device can generate a trusted input from a transaction output, by parsing a transaction, at any time (so it can be done in a batch before actually using it)
- When creating a new transaction, prevout is replaced by the trusted input.

[Mike Hearn]

Yes, great idea. It will definitely simply devices like the Trezor which I think will be absolutely critical to Bitcoin's long term success.

Gavin has talked about maybe doing a "script 2.0" in future. If that were to happen, then we'd probably introduce new opcodes to split up CHECK(MULTI)SIG anyway, and at that point a new sighash flag wouldn't be required, it'd be implicit in the use of the new opcodes.

Let's discuss this a bit more at the conference, and let's see how next months hard fork goes.

[drazvan]

FYI, the way I deal with this issue today (specification update pending), to make things easier :

- A new "trusted input" type is added. A trusted input is : transaction hash + index (prevout) / amount / signature of the previous data (using a key known only by the device)
- The device can generate a trusted input from a transaction output, by parsing a transaction, at any time (so it can be done in a batch before actually using it)
- When creating a new transaction, prevout is replaced by the trusted input.

Another idea would be to have a separate smartcard device that is plugged into an online machine and only generates trusted inputs from outputs (just like you do now). It signs them with its private key and your offline device knows the public key. Your offline device could require that all inputs are trusted inputs, without ever being online.

This way, if the online computer is compromised, it still can't lie to the offline computer about the value of an input - the connected smartcard verifies the transaction before certifying the value of its outputs.

[etotheipi]

FYI, the way I deal with this issue today (specification update pending), to make things easier :

- A new "trusted input" type is added. A trusted input is : transaction hash + index (prevout) / amount / signature of the previous data (using a key known only by the device)
- The device can generate a trusted input from a transaction output, by parsing a transaction, at any time (so it can be done in a batch before actually using it)
- When creating a new transaction, prevout is replaced by the trusted input.

Another idea would be to have a separate smartcard device that is plugged into an online machine and only generates trusted inputs from outputs (just like you do now). It signs them with its private key and your offline device knows the public key. Your offline device could require that all inputs are trusted inputs, without ever being online.

This way, if the online computer is compromised, it still can't lie to the offline computer about the value of an input - the connected smartcard verifies the transaction before certifying the value of its outputs.

It seems a bit excessive to bring in an extra piece of hardware to try solve this problem.  Not to mention there's too many ways for this to go wrong:  the compromised system could exploit the presence of the smartcard when you do a legitimate transaction, and pre-sign inputs that are likely to be used on future transactions, etc. 

I recognize you're proposing workarounds to the fact that SIGHASH_WITHINPUTVALUE is not implemented.  But I'd much rather require supporting-transactions until something like this new SIGHASH can be implemented.  Adding extra public keys and authentication of that sort to the offline device is considerably less than ideal.

[drazvan]

It seems a bit excessive to bring in an extra piece of hardware to try solve this problem.  Not to mention there's too many ways for this to go wrong:  the compromised system could exploit the presence of the smartcard when you do a legitimate transaction, and pre-sign inputs that are likely to be used on future transactions, etc. 

I recognize you're proposing workarounds to the fact that SIGHASH_WITHINPUTVALUE is not implemented.  But I'd much rather require supporting-transactions until something like this new SIGHASH can be implemented.  Adding extra public keys and authentication of that sort to the offline device is considerably less than ideal.

I'm not sure I understand what you mean, all the smartcard does is take a full transaction as input, check its signatures, then return a list of outputs and their value, signed with an internal private key (for simplicity, it could even be an HMAC using a shared key between the smartcard and the offline device). As long as you feed it valid transactions, it will happily check them for you and "certify" the value of the outputs. It essentially does the same thing you do on your offline Armory machine, but do it in a secure fashion as soon as the transaction is received by the online machine.

You are correct though, your proposal would take care of this at the protocol level. How long do you estimate it will take for all Bitcoin clients to start using the new protocol (if I understand correctly, payments sent without this flag would be unusable by the offline wallet - or they would require you to fallback to sending the transaction along, just like you do now, correct?).

[gmaxwell]

You're going to have to work awful hard to convince me that hashing data on the fly as it comes in and storing a single integer out of the middle is so insanely burdensome that it's worth the considerable risk of an incompatible change to the bitcoin protocol, requiring upgrading hundreds of thousands of machines.. etc.

It's certainly not happening in two weeks.

[etotheipi]

You're going to have to work awful hard to convince me that hashing data on the fly as it comes in and storing a single integer out of the middle is so insanely burdensome that it's worth the considerable risk of an incompatible change to the bitcoin protocol, requiring upgrading hundreds of thousands of machines.. etc.

It's certainly not happening in two weeks.

I wasn't recommending this as worthy of its own hardfork.  But it's a pretty darned simple and useful modification if we're planning to make incompatible, hard-forking changes anyway.  If we're going to be implementing something that is "latent-now-but-required-in-12-months" then this should be seriously considered.  The complexity of the process is not the only reason, it's also about the bandwidth.  The less data there is to transfer across a channel, the more secure options you have to construct that channel.  Right now, if you're going to make an offline signer, you have to accommodate many megabytes going across that channel, even if the vast majority of transactions don't require it.   By implementing this, you also leave the transaction sizes up to the user, not the people that sent him coins.

[allten]

I really like this..... a lot!
This is how I assumed it worked before getting into hardware development, but what a nasty surprise.

Does anyone else see any downsides? Other than it would have to be rushed to fit it in with this planned hard fork.

Really need some core developers to come out in full support of this right away.

[gmaxwell]

If we're going to be implementing something that is "latent-now-but-required-in-12-months" then this should be seriously considered.

Okay, a little confusion on my part then. Whats happening in couple weeks isn't the starting countdown for a hardfork, it's the required end date. So I thought you were proposing this be pulled into that. I think the sighash with input value seems pretty inelegant. Instead I'd just assume it would be a field external to the script for each input.

[etotheipi]

If we're going to be implementing something that is "latent-now-but-required-in-12-months" then this should be seriously considered.

Okay, a little confusion on my part then. Whats happening in couple weeks isn't the starting countdown for a hardfork, it's the required end date. So I thought you were proposing this be pulled into that. I think the sighash with input value seems pretty inelegant. Instead I'd just assume it would be a field external to the script for each input.

I knew it was a longshot to even consider it in the near future, but I wanted to get it out there, anyway.  And it turns out there's even more support for it than I expected.  So maybe there'll be a way to fit it in, in the future.  I guess if it is an implemented-but-not-enabled-for-X-months feature, there's no reason it has to be related to this hardfork.

I think the solution is perfectly elegant.  I mean, putting it in the transaction serialization would've been a good choice, but doing it this way totally achieves its goal while being fairly non-disruptive -- no one has to rewrite their blockchain parser to implement this.  They just add a new SIGHASH code and say it's disabled until date X.  And you save the "unnecessary" 8 bytes in the input (meh).

[allten]

So, could we get this post transformed into a BIP with a strategy for implementation?
If I understand correctly, Gavin has already laid the ground work for changes such as
these to be integrated into the Bitcoin protocol.

Thanks to the OP for getting this out there.

[TierNolan]

This is a hard fork.  

Using the Pay to Script Hash (/P2SH/) update as a precedent, you could implement it as a script template and therefore be a soft(ish) fork.

Something like

A new standard transaction is defined

scriptPubKey: [VarInt:value] OP_EQUAL_VERIFY OP_DUP OP_HASH160 [hash160(public key)] OP_EQUALVERIFY OP_CHECKSIG

scriptSig: [/INVAL/] [signature] [public key] [VarInt:value]

This script is considered standard if
- The value of the transaction output being spent is equal to the stated value

The script is considered validated if
- It is valid under the current rules
- The value of the transaction output being spent is equal to the stated value

With immediate effect
- Miners which agree should add /INVAL/ to their coinbase
- Miners which agree should not include transactions which fail these rules in blocks
- Nodes which agree should relay these transactions as standard

Formal acceptance
- Change accepted if included in 550 of the 1000 blocks from Block N to Block N + 999
-- If accepted, miners should reject blocks which contain invalid transactions

---------------------------

Armory could be setup to format all transactions that way immediately.  If users use armory to send coins to their private store, then they don't need so much data when spending.

[etotheipi]

Armory could be setup to format all transactions that way immediately.  If users use armory to send coins to their private store, then they don't need so much data when spending.

Yeah, Armory would do it in a heartbeat.  But as I said, I'm not sure this is worthy of it's own fork, even if it's popular.  I think it makes a perfect add-on to some other update that would cause a fork, because it is:

(1) Simple
(2) Uncontroversial
(3) Useful, but far from critical

It is (or should be) uncontroversial, because it adds an optional, extra restriction to tx validity. 

[allten]

..I'm not sure this is worthy of it's own fork, even if it's popular.  I think it makes a perfect add-on to some other update that would cause a fork..

You are probably right.
Looks like I'll have to be patient.  Can't wait though.
Thanks again!

[TierNolan]

Yeah, Armory would do it in a heartbeat.

I mean you could include the template without any official changes to the protocol. 

You could have a "send to cold store" transaction using the template I suggested.

It would have to send the transaction direct to a miner who will accept non-standard transactions though.

The signing algorithm sees the spend part of the script.  The scriptPubKey requires that the last thing the spending tx pushes onto the stack is the value of the TXO.

You cannot spend that output without including the info in the scriptSig.

It is (or should be) uncontroversial, because it adds an optional, extra restriction to tx validity. 

Technically, that makes it a soft fork.  What happens if undefined bits in the sighash field are set to 1?