Auditing an offline wallet

[Roy Badami]

So, there's been some discussion of the idea that a watching-only wallet might be compromised in such a way that it gives out receiving addresses that are actually controlled by an attacker.  If the compromised wallet actually correctly faked the balance your off-line wallet should have, it might be possible for such an attack to go unnoticed for a considerable time.

One obvious countermeasure would be to periodically audit the balnce of the offline wallet by setting up a new watching-only wallet on a clean machine, and verifying the balance that way.  However, since this involves getting the blockchain onto the new system, such an audit is never going to be a quick and easy process.

I'm wondering whether the following process for a wallet-supported audit would be viable.

[NM, this doesn't work.  DeathAndTaxes points out to me that it's impossible to determine whether those coins have already been spent without access to the full blockchain.  I guess the only way to audit a cold wallet really is to set up a new watching-only wallet on a known-good machine.  Or at least, to maintain sufficient watching-only wallets that compromise of all of them is unlikely]

In order to conduct an audit, the watching-only wallet would write a flie to a flash drive, containing the following:

• Block headers of the entire block chain
• The complete transaction history of all UTXOs in the wallet, stretching back to the coinbase transactions that mined those coins
• The merkle branches that prove these transactions are in the relevant blocks

This file could then be loaded into the offline wallet, which could then verify the header chain, and compute the balances of all the UTXOs.  The above information is enough to prove that some chain exists that contains the purported transactions.  It's not, in theory, quite enough to prove that that chain is the real blockchain, but that could be assured by a system of signed checkpoints.

It would also be possible to get a reasonable degree of assurance in a trust-free manner, simply by having the offline system display the difficulty after the last block, which the user can verify is roughly correct.  This is enough to prove that whoever constructed this chain expended work at least equivalent to the entire bitcoin network hashing at current speeds for several weeks over four days, which is still a pretty high bar to faking an audit.

It's not conclusive, though, if the attacker has had months or even years to prepare the fake chain, but for the truly paranoid you could display a more detailed difficulty history, which would defeat an attacker who used lots of 4x difficulty increases to minimise the amount of work they needed to do.

Is this idea viable, or is there some reason I'm missing why this wouldn't work?

roy

EDIT: Rather than displaying the difficulty after the last block, display the difficulty value that was current immediately before the last difficulty change.  An attacker would have to have mined a full 2016 blocks at this difficulty, so it raises the bar significantly.  Signed checkpoints aren't as useful as I first thought, but I think there are still relatively simle checkpoint schemes that help here

EDIT: Better: pick the block midway between the last two difficulty changes, and display the date and time, balance, and difficulty as of that block.

[1714962681]

1714962681

[1714962681]

1714962681

[1714962681]

1714962681

[1714962681]

1714962681

[CircusPeanut]

If the compromised wallet actually correctly faked the balance your off-line wallet should have, it might be possible for such an attack to go unnoticed for a considerable time.
....
I'm wondering whether the following process for a wallet-supported audit would be viable:

In order to conduct an audit, the watching-only wallet would write a flie to a flash drive, containing the following:
...
This file could then be loaded into the offline wallet, which could then verify the header chain, and compute the balances of all the UTXOs.
...

It's not conclusive, though, if the attacker has had months or even years to prepare the fake chain, but for the truly paranoid you could display a more detailed difficulty history, which would defeat an attacker who used lots of 4x difficulty increases to minimise the amount of work they needed to do.

From these lines in your post it seems to me like you've mixed up the concepts of the address/key chain and the block chain.

The offline wallet has no connection to block chain. Only online watching only wallet does that. There is no need to "fake the balance" because the only record of your wallet's balance is in the online watching only wallet.

If you are worried, all you really have to do is make sure your online watching only wallet is giving you the correct public addresses. To do this, you can just try to sign a transaction every once in awhile with the offline wallet. Or, you can verify a bunch of addresses by manually generating them on both systems (Needs expert mode). Then  you can compare the lists.

[Roy Badami]

Yes, currently the offline wallet knows nothing about the blockchain, and therefore can't computer the balance of the wallet.

I'm proposing an audit mode whereby the offline wallet could be given a file containing just enough of the blockchain to determine the balance, and I'm also proposing countermeasures to guard against some possible attacks against that mechanism (since the offline wallet has no access to the Bitcoin network and hence can't apply the usual rules to determine the longest chain)

[DeathAndTaxes]

What use is verifying the balance displayed is correct?  Your own first posts indicates the possible threat is that an attacker includes the wrong address.  The offline wallet can easily determine which addresses correspond to keys it controls.  There is no need for the blockchain or balances.

It would also be possible to get a reasonable degree of assurance in a trust-free manner, simply by having the offline system display the difficulty after the last block, which the user can verify is roughly correct.  This is enough to prove that whoever constructed this chain expended work at least equivalent to the entire bitcoin network hashing at current speeds for several weeks over four days, which is still a pretty high bar to faking an audit.

The entire network creates one block at current difficulty every 10 minutes.  I am not sure where you got 4 days from.

Maybe it would be better to state exactly what you are trying to prove and why.

If you are just trying to prove the online wallet only contains your addresses then all you need is an export of those addresses.  The cold wallet can instantly determine if there is an address in the hotwallet which it doesn't have the private key for.

[Roy Badami]

What use is verifying the balance displayed is correct?

I don't understand that statement.  I believe I have X coins in my offline wallet.  But I only believe that because a (possibly compomised) online computer tells me that.

In what way could it be anything other than useful to verify that I really do have the X coins I think I have?

[DeathAndTaxes]

What use is verifying the balance displayed is correct?

I don't understand that statement.  I believe I have X coins in my offline wallet.  But I only believe that because a (possibly compomised) online computer tells me that.

In what way could it be anything other than useful to verify that I really do have the X coins I think I have?

Lets look at it the other way.  What use would there be for an attacker to fake your balance?  How exactly would they accomplish that and why?

[Roy Badami]

There is no need to "fake the balance"

An attacker that compromised my online computer to give out incorrect addresses would probably want to fake the balance so that I didn't notice.

If you are worried, all you really have to do is make sure your online watching only wallet is giving you the correct public addresses.

And to be 100% sure, I have to retrospectively verify every address it's ever given out.  Not entirely realistic.

[Roy Badami]

Lets look at it the other way.  What use would there be for an attacker to fake your balance?  How exactly would they accomplish that and why?

Oh, simple.

Assume an attacker compromises the computer with my watching only wallet and arranges so that every time I asked for a new receiving address it actually displays addresses under the attacker's control.  I then transfer coins to this address, intending to place them into cold storage; but unbenowst to me I'm actually paying them to the attacker.

In order to keep up this attack for as long as possible, it's in the attackers interests for the attacker to arrange for the watching only wallet to display the balance I think I should have, not the balance I actually have, so that I don't notice the attack.  If this is a savings wallet which I never withdraw from, the attacker could keep this up for years.  The compromised watching only wallet would display a balance that taliies with what I think I should have, but in reality the wallet is essentially empty because I never paid any coins into the real wallet.

[DeathAndTaxes]

There is no need to "fake the balance"

An attacker that compromised my online computer to give out incorrect addresses would probably want to fake the balance so that I didn't notice.

Ok sensing an x-y problem here.  The real threat you are worried about if the attacker adding his address to your online wallet so that you will accidentally use it (and lose funds).  The cold wallet only needs the addresses nothing else to ensure this is correct.

If you are worried, all you really have to do is make sure your online watching only wallet is giving you the correct public addresses.

And to be 100% sure, I have to retrospectively verify every address it's ever given out.  Not entirely realistic.

How much data you you think is going to be needed to verify the "balance of every address" (technically no such thing exists it is the outputs of every transaction).  Still if you only verify the outputs then you won't detect the attack until AFTER you have lost funds.  If you verify the hot wallet doesn't contain any foreign addresses you will (potentially) catch the attack before losing funds.  Which seems to be a better solution.

The naive solution is to dump all addresses from the hot wallet and send it to the cold wallet.  The cold wallet scans the list looking for ones which it doesn't have the private key for.  However there is no need to transfer all the addresses.   Technically we just need to know the set of addresses in the hot wallet is accurate.  A merkle tree of the addresses in the hot wallet as an example reduces the set of addresses to a single hash.  The cold wallet can construct the same merkle tree and verify the hashes match.  If they don't then the hot wallet contains addresses the cold wallet is unaware of (possible compromise).  For obvious reasons this merkle tree would need to be computed on a different machine (if hot wallet client is compromised then you can't be sure anything it outputs is valid).

[DeathAndTaxes]

Oh, simple.

Assume an attacker compromises the computer with my watching only wallet and arranges so that every time I asked for a new receiving address it actually displays addresses under the attacker's control.  I then transfer coins to this address, intending to place them into cold storage; but unbenowst to me I'm actually paying them to the attacker.

Then the actual concern is the hot wallet contains "foreign" addresses.  As indicated above that can be verified without any knowledge of the blockchain or transaction history.  Using a merkle tree the cold wallet could verify the SET of addresses in the hot wallet are accurate with a single hash (256 bits).

In order to keep up this attack for as long as possible, it's in the attackers interests for the attacker to arrange for the watching only wallet to display the balance I think I should have, not the balance I actually have, so that I don't notice the attack.  If this is a savings wallet which I never withdraw from, the attacker could keep this up for years.  The compromised watching only wallet would display a balance that taliies with what I think I should have, but in reality the wallet is essentially empty because I never paid any coins into the real wallet.

This is called an x-y problem.  The actual problem is to ensure the hot wallet doesn't contain any foreign addresses, you latched on to verifying the balances as the "way to do that".  It is a far more complex problem and one that doesn't need to be solved in order to solve the real problem.

http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem

[Roy Badami]

Who much data you you think is going to be needed to verify the "balance of every address" (technically no such thing exists it is the outputs of every transaction).

It is not every transaction.  It might be a lot of transactions, but it is still a minority of transactions that are needed (i.e. the amount of data needed is considerably smaller than the entire blockchain)

Still there is no need to verify every address.  You only need to verify the set of addresses.  A merkle tree of the addresses in the hot wallet as an example reduces the set of addresses to a single hash.  The cold wallet can construct the same merkle tree and verify the hashes match.  If they don't then the hot wallet contains addresses the cold wallet is unaware of (possible compromise).

But how do I know that the online computer didn't lie about the merkle hash?

Let me restate the problem.

Assume the online computer might be compromised, and I can't trust anything it displays, or anything it generates.  How can i determine the balance of my cold wallet, given that the offline computer is, well, offline.

[Roy Badami]

Then the actual concern is the hot wallet contains "foreign" addresses.  As indicated above that can be verified without any knowledge of the blockchain or transaction history.  Using a merkle tree the cold wallet could verify the SET of addresses in the hot wallet are accurate with a single hash (256 bits).

No, that is one possible compromise.  But I'm not jsut assuming that the wallet file might be compromised.  I'm assuming that the wallet code might be compromised.  I'm assuming that the computer that is running the wallet might be rooted.  It might be doing anything.  It might be displaying addresses and balances given to it by the attacker via a command and control connection, for all I know.

you latched on to verifying the balances as the "way to do that".  It is a far more complex problem and one that doesn't need to be solved in order to solve the real problem.

What if the real problem I want to solve, is to determine, reliably and in the presence of possibly compromised computers, how many coins I own?

I don't know about you - but I actually want to know how many coins I own.  That is the sole requirement here.  I currently think I own X coins, but it's possible that an attacker somehow tricked me into believing that.

I don't care about the details of how the attacker tricked me - the problem statement is precisely this: "How can I determine, with a high degree of certainty, how many coins i really own."

[DeathAndTaxes]

Quote from: DeathAndTaxes on Today at 04:54:02 PM
Who much data you you think is going to be needed to verify the "balance of every address" (technically no such thing exists it is the outputs of every transaction).

It is not every transaction.  It might be a lot of transactions, but it is still a minority of transactions that are needed (i.e. the amount of data needed is considerably smaller than the entire blockchain)

But it is every all transactions  Your spendable "balance" is equal to the value of the unspent outputs of all the transactions which defined your key(s) in the output.  How does your cold wallet know if an output is spent or not (without the blockchain)?  Also since responding I realized even this is not complete as the compromised wallet could simply leave recent spends out of the list.

But how do I know that the online computer didn't lie about the merkle hash?

You don't but if you take the wallet file and compute the merkle hash on another computer you can be assured that is valid (unless the other computer is also compromised).

[DeathAndTaxes]

I don't know about you - but I actually want to know how many coins I own.  That is the sole requirement here.

Really?  So if right now I injected my addresses into your wallet but you haven't used them YET and thus your balance is correct but you are in imminent danger of losing coins in the future you would not want to know that?  You only want a system which can tell you AFTER you have already had coins stolen (potentially an irreplaceable amount) that they are definitely gone?

[Roy Badami]

Quote from: DeathAndTaxes on Today at 04:54:02 PM
Who much data you you think is going to be needed to verify the "balance of every address" (technically no such thing exists it is the outputs of every transaction).

It is not every transaction.  It might be a lot of transactions, but it is still a minority of transactions that are needed (i.e. the amount of data needed is considerably smaller than the entire blockchain)

But it is every all transactions  Your spendable "balance" is equal to the value of the unspent outputs of all the transactions which defined your key(s) in the output.  How does your cold wallet know if an output is spent or not (without the blockchain)?  Also since responding I realized even this is not complete as the compromised wallet could simply leave recent spends out of the list.

Damn, you're right.  It really does need the entire blockchain.

But how do I know that the online computer didn't lie about the merkle hash?

You don't but if you take the wallet file and compute the merkle hash on another computer you can be assured that is valid (unless the other computer is also compromised).

Ok.  But you're assuming the compromise was the wallet file rather than the wallet code.  If the compromise was in the wallet code then analysing the wallet file on another computer isn't going to demonstrate anything.

[Roy Badami]

I don't know about you - but I actually want to know how many coins I own.  That is the sole requirement here.

Really?  So if right now I injected my addresses into your wallet but you haven't used them YET and thus your balance is correct but you are in imminent danger of losing coins in the future you would not want to know that?  You only want a system which can tell you AFTER you have already had coins stolen (potentially an irreplaceable amount) that they are definitely gone?

No... I'm saying it is the requirement I'm asking about here.  There are of course many other things one would want to assure oneself of.

But auditing the balance of a wallet is a reasonable requirement, surely.  To say, you shouldn't care what your balance is as long as you can convince yourself that you haven't been the subject of the particular attacks you think likely is, well bizarre.

[DeathAndTaxes]

You don't but if you take the wallet file and compute the merkle hash on another computer you can be assured that is valid (unless the other computer is also compromised).

Ok.  But you're assuming the compromise was the wallet file rather than the wallet code.  If the compromise was in the wallet code then analysing the wallet file on another computer isn't going to demonstrate anything.

True.  You would need to compare the addresses as shown by the hot wallet with the analyzed contents of the wallet file.  It would catch any issues in either the wallet or client on the compromised machine.  However upon further reflection that would be a rather painstaking, tedious, and error prone step.

The addresses could be checked in realtime.  The QR code of the "receiving address" could be scanned by a second system (like say a cellphone) which would verify the address is valid.  This could be done by either BIP32 public seed or for random keys signing the all addresses with a private key only know by the cold wallet.   Still I do admit this is rather clunky but I don't see another solution.

[Roy Badami]

Ok, it's still not quite the entire blockchain that I need, although it's a lot more than I originally thought.

I do need to prove that I haven't been tricked into spending coins that I think I still have, but that only needs full blocks for those blocks newer than my oldest UTXO.  I could deliberately move coins around to avoid any very old UTXO's although that would have privacy implications.

Still, you've convinced me that the only way to do an audit is with the entire blockchain.

[DeathAndTaxes]

auditing the balance of a wallet is a reasonable requirement, surely.

Maybe but it doesn't address the attack you indicated in the OP which is my point.

a watching-only wallet might be compromised in such a way that it gives out receiving addresses that are actually controlled by an attacker

Even if you could accurately and easily verify the balance reported by a wallet is correct, you only have an assurance that you haven't lost coins yet.  If that is your goal well you have succeeded.  What is confusing is you describe a scenario (quoted above) and your solution doesn't give you any assurance that the attack scenario (addresses controlled by an attacker) isn't true.

To say, you shouldn't care what your balance is as long as you can convince yourself that you haven't been the subject of the particular attacks you think likely is, well bizarre.

That is a mischaracterization.  Have fun.

[Roy Badami]

The addresses could be checked in realtime.  The QR code of the "receiving address" could be scanned by a second system (like say a cellphone) which would verify the address is valid.  This could be done by either BIP32 public seed or for random keys signing the all addresses with a private key only know by the cold wallet.   Still I do admit this is rather clunky but I don't see another solution.

All great, if you have been doing it since you started using the wallet.  Kind of hard to do retrospectively.

I can always audit my balance by using a watching-only wallet on a clean install of Armory.  I was just trying to figure out if there could be any other way, but it appears not.