Merkle tree inside Block Headers for light client mode

[pmarches]

Hello All,

I am working on the bitcoinj client and I am trying to implement the block header download in light mode.

From the protocol specification Wiki (https://en.bitcoin.it/wiki/Protocol_specification#Block_Headers) , it seems that only the merkle root hash is stored in the Block Header. Having the merkle root hash is not sufficient to validate a transaction contained in that block. I would need the full Merkle tree and not only the root hash.

IMO the full merkle tree should be sent with the block header, not just the merkle root. For the full blocks, we do not need to send any node of the merkle tree since the tree is computed from the transactions that we have. Maybe the protocol should have an additional command to download the merkle tree given a merkle root? I find that to be inefficient and I would prefer to have the merkle nodes inside the block header...

Did I miss something?

Philippe

[MoonShadow]

Did I miss something?

Only that the merkle tree is not in the header so that the tree can be 'pruned' of long spent transactions, until there is nothing left but the 80 byte header.  If the merkle tree itself were included in the header, then the header would not only be potentially significantly larger, but of a variable length.  We do not want a variable length because we do not want to introduce a condition that it becomes advantageous for a mining client to ignore a transaction; because it would make it's hashing more difficult compared to another client that simply ignored all transactions racing for the block reward.

[theymos]

I'm not sure that there would be any point to providing Merkle trees through a separate message. You need to download full blocks to detect transactions to yourself, anyway.

[ByteCoin]

I'm not sure that there would be any point to providing Merkle trees through a separate message. You need to download full blocks to detect transactions to yourself, anyway.

When a lightweight client asks for the block containing transaction it need only be told the header and enough of the merkle tree to verify that the transaction belongs in the block. I imagine that at the moment with relatively low numbers of transactions per block the bandwidth savings of not sending all the transactions in the block will be low.

Detecting payments to yourself could be done by passing a request for all transactions crediting a given address. I can't think of a way that lightweight clients could do this without essentially revealing their receiving addresses.

Of course with my "balance sheet" proposal, the amount of information clients have to download to start from "cold" is minimized and a good amount of anonymity is preserved - but this would be a breaking change.

ByteCoin

[theymos]

Some semi-separate network will probably be created eventually to anonymously find transactions to yourself and get Merkle branches. Then there's no point in having a "get the full Merkle tree of this block" message, though. I can't think of any situations where this message would be useful.

[Mike Hearn]

If you're working on BitCoinJ could you please ask these sorts of questions on the mailing list? Bear in mind any eventual patches will have to be reviewed by me if you want them included.

It'd help if you describe what you want to achieve. If you want to accelerate the initial block chain download it's sufficient to make the Peer class understand how to use getheaders instead of getblocks in the case of an empty wallet. Obviously it's not safe to just download the headers when there are keys in the wallet but for the case of a new install it'd be OK. That's a first goal to reach.

If you want to avoid the need to download full blocks entirely, then as ByteCoin says you need not only the ability to fetch merkle branches (not full trees) from a remote node, but also the ability to ask for transactions matching particular templates. Fortunately BitCoin already defines a template system for scripts. Unfortunately it is not exposed via the network protocol and that would have to be added.

A mini design doc would be a great thing here.

[pmarches]

Thank you for all your answers,

Let me give you the scenario I am trying to implement.
- The use case does not require the light client to know the balance of its own account
- The light bitcoin client receives a transaction message from the p2p network or any other insecure source
- Without waiting for the transaction to be accepted by the network (by way of block creation) the light client wants to verify that the input transaction actually has money in it.

I understand that this introduces a security risk for the light client, but it is a tradeoff for usability that the user can live with since it is going to be used only for transactions with a physical presence.
Thus, I am trying check the following:
   1) Have the coins from the input transaction have already been accepted by the network
   2) The coins from the input transaction have never been redeemed (double spent) in another transaction

Any ideas are welcomed,

Philippe

[MoonShadow]

Thank you for all your answers,

Let me give you the scenario I am trying to implement.
- The use case does not require the light client to know the balance of its own account
- The light bitcoin client receives a transaction message from the p2p network or any other insecure source
- Without waiting for the transaction to be accepted by the network (by way of block creation) the light client wants to verify that the input transaction actually has money in it.

Sounds like a portable POS system, wherein the light client is only used to accept payments, not send them.  Under what conditions would such a crippled client be useful?  You could do exactly the same thing using a remote client, as long as you had real time access to the Internet. 

[ByteCoin]

1) Have the coins from the input transaction have already been accepted by the network

Ok so you look at the TxIns of the transaction which contains the PrevOut of the transactions you're checking. You can therefore send a "getdata" with the hashes to get the actual transaction, but that's not sufficient. You need to be able to find out which block that (or those) transactions was hashed into so you can download it and check the merkle tree and link it to the block chain headers. I'm not sure what queries you'd have to send to find out which block a transaction was hashed into. Is it even possible at the moment?

  2) The coins from the input transaction have never been redeemed (double spent) in another transaction

I don't think there's a way to prove that the inputs haven't already been spent without essentially downloading the entire block chain subsequent to the block that contained the inputs and verifying that the inputs aren't used in any transactions. Even if a new query was created, there's no obvious way for your lightweight client to check it's not being lied to.

If I'm mistaken in any of the above, please correct my reasoning.

Of course with my "balance sheets proposal" you get the assurance that your inputs haven't been spent as soon as you download the relevant branch of the balance sheet tree and verify its hash in the block chain.

ByteCoin

[MoonShadow]

Thank you for all your answers,

Let me give you the scenario I am trying to implement.
- The use case does not require the light client to know the balance of its own account
- The light bitcoin client receives a transaction message from the p2p network or any other insecure source
- Without waiting for the transaction to be accepted by the network (by way of block creation) the light client wants to verify that the input transaction actually has money in it.

I understand that this introduces a security risk for the light client, but it is a tradeoff for usability that the user can live with since it is going to be used only for transactions with a physical presence.
Thus, I am trying check the following:
   1) Have the coins from the input transaction have already been accepted by the network
   2) The coins from the input transaction have never been redeemed (double spent) in another transaction

Any ideas are welcomed,

Philippe

I've been thinking about this further, and I think that a lightweight client (such as would be found on a smartphone) would be one geared toward spending coins rather than receiving and verifying transactions.  That said, a lightweight client, or any client, that was disconnected from the Internet could still check that a transaction was valid by pulling the relevant block headers and merkle trees from the sending client via the same connection that the transaction itself was transmitted across.  Granted, this isn't safe, as it would be possible to spoof, but it certainly wouldn't be an easy thing to do.  Even if both clients were lightweight, the sending client would need to have at least a skeleton copy of the blocks that confirm his own balance.

This, of course, could only tell you that the coins were once owned by the sender, within a reasonable doubt; but not if the transaction is actually valid, as there still seems to be no way to check for a prior spend without scanning all the transactions in blocks that have occurred since.  Such a transaction could still be accepted with the risks.

[Mike Hearn]

Yes, the problem with your proposal is it doesn't protect you against double spends. Verifying the txins exist is not enough.

[MoonShadow]

Yes, the problem with your proposal is it doesn't protect you against double spends. Verifying the txins exist is not enough.

Well, it can be enough, depending on how much you trust the counter-party.  However, the normal situation of a lightweight client sending to a full client (i.e. a customer inside a brick&mortar shop) mitigates the double spend risks by limiting the window of time that can be done into miliseconds, because the full client can not only check the transaction's validity but also scan the live transaction queue for transaction that use the same inputs.  But this trick functionally requires a full client with continuous Internet access.

[Mike Hearn]

Philippe, could you go even another level higher? You want to do physical transactions, like using mobile phones?

If you want to have confidence in a transaction without being able to check it for yourself (a zero confirmation transaction) then the way to do it is connect to a bunch of full nodes and wait until they all announce that transaction to you. If you trust your internet connection isn't being tampered with, the fact that many nodes accepted it means it's very likely to confirm. A "miner backbone" of the sort discussed before would make that assurance even better.

[MoonShadow]

Philippe, could you go even another level higher? You want to do physical transactions, like using mobile phones?

If you want to have confidence in a transaction without being able to check it for yourself (a zero confirmation transaction) then the way to do it is connect to a bunch of full nodes and wait until they all announce that transaction to you. If you trust your internet connection isn't being tampered with, the fact that many nodes accepted it means it's very likely to confirm. A "miner backbone" of the sort discussed before would make that assurance even better.

Yes, this would work, because an honest client will not propagate an invalid transaction.  But if a smartphone had Internet access, what advantage does an entirely independent lightweight client have over a lightweight client that uses a trusted full client back at the office?  I can't imagine a situation that such a client, for the purpose of accepting payments, would be useful.

[Mike Hearn]

Well, you say "trusted full client" like that's an easy thing to conjure up. If I were to host such a server on my personal box, would you trust it? With Ⓑ10 sure. With Ⓑ10,000 .... heck, even I wouldn't trust my server with that, I just haven't put that much effort into securing it. Linux boxes get hacked all the time.

What about MyBitcoin? That's the canonical example of such a cloud wallet. Its contact address is a PO Box in the West Indies - if things go south, what are you going to do?

Building enough trust in your integrity and security takes a long time and a lot of effort. Companies that manage it are called banks and even though there are only a few they have to be heavily regulated for people to trust them (and how many people really trust banks these days?). In some parts of the world, like parts of Africa, it hasn't happened at all and people there just don't use banks and thus cannot use electronic payments either.

An independent, open source mobile wallet:

• is as easy to set up as BitCoin itself is (just install)
• can be verified by reading the code (lots of people know Java and can compile it themselves)
• does not require any trust in third party security procedures
• potentially doesn't even require an internet connection to buy things, as long as the merchant has internet access and can broadcast the transaction for you.

Today, the BitCoin community is made up mostly of people who have never met each other (I've met a few key people in person like justmoon, but not many). So minimizing the trust needed is useful and very much in the spirit of BitCoins design.

[ByteCoin]

...
An independent, open source mobile wallet:

• ...
• does not require any trust in third party security procedures
• potentially doesn't even require an internet connection to buy things, as long as the merchant has internet access and can broadcast the transaction for you.

That's a good goal but it's plain that bitcoin was not designed to support the use of mobile wallets.

For instance, imagine you have your mobile wallet and you're at the merchant who has internet access and a bitcoin client.
You transfer your bitcoins to the merchant.
The merchant's client does its own verification of the transaction and then sends it through the network.
Now the merchant can either ask some large miners whether it's on the transaction list going to be hashed into the next block or wait for the next block.
Suppose you're standing there with no internet connection and the merchant says to you "Erm... The miners are not confirming recipt and your transaction wasn't hashed into the last block." What are you going to do?
In one case, the merchant is lying and has taken your money and doesn't want to give you the goods.
On the other hand, you think the merchant thinks that you've just arranged with an accomplice to already spend those coins and the merchant's transaction is being rejected as a double spend.
Without an independent connection that is at least disinterested, even if it's not secure there's nothing you can really do.
Also, standing there waiting for blocks to confirm is not ideal. A better system would facilitate more reliable prompt confirmations of transactions.

ByteCoin

[Mike Hearn]

The rapid transaction acceptance thing has been done to death, I feel. Most people interact every day with merchants who are trustable, like big supermarket chains. You don't have to worry about the merchants attempting to confuse you into giving up the goods.

On the other hand, smartphones have internet connections nearly all the time. If it became useful for payments then big merchants that somehow didn't have good coverage already would get microcells installed. Your phone does the usual 3G handshake with the cell and gets a trustworthy, disinterested internet connection.

[ByteCoin]

The rapid transaction acceptance thing has been done to death, I feel. Most people interact every day with merchants who are trustable, like big supermarket chains. You don't have to worry about the merchants attempting to confuse you into giving up the goods.

The day you can do your supermarket shopping with bitcoin is the day you can say bitcoin has finally arrived. Supermarket chains will not be early adopters of bitcoin and without them, the supermarkets will not come along. The early adopters will be small merchants looking for a legitimate edge or alternatively an illegitimate edge in which they defraud some customers.

I take your point about smartphones having internet connections but it would be nice to have a useable bitcoin wallet on a smaller device with a similar form factor to a usb stick, an oyster card or a token generator.

ByteCoin

[MoonShadow]

On the other hand, smartphones have internet connections nearly all the time. If it became useful for payments then big merchants that somehow didn't have good coverage already would get microcells installed. Your phone does the usual 3G handshake with the cell and gets a trustworthy, disinterested internet connection.

Or simply an open wi-fi connection with common ports blocked, but not Bitcoin ports.  It is in the interests of the vendor to make sure that Bitcoin users have ready access to the Bitcoin network, even if they wouldn't want to have warwalkers mulling about the store downloading porn over thier Internet connection.

[MoonShadow]

Well, you say "trusted full client" like that's an easy thing to conjure up. If I were to host such a server on my personal box, would you trust it? With Ⓑ10 sure. With Ⓑ10,000 .... heck, even I wouldn't trust my server with that, I just haven't put that much effort into securing it. Linux boxes get hacked all the time.

What about MyBitcoin? That's the canonical example of such a cloud wallet. Its contact address is a PO Box in the West Indies - if things go south, what are you going to do?

I'm not talking about remote wallets, just simply a remote full client that you can query whom you already have a relationship with before walking into a transaction.  You don't have to trust another machine or user to hold your wallet.dat file, you just have to have a party that you know isn't interested in the outcome of your transaction.  An untrusted third party, if you will, but each party to the transaction needs at least one of such a client; and if you set up a full client of your own back at the house, I'd bet that you could trust it.

An independent, open source mobile wallet:

• is as easy to set up as BitCoin itself is (just install)
• can be verified by reading the code (lots of people know Java and can compile it themselves)
• does not require any trust in third party security procedures
• potentially doesn't even require an internet connection to buy things, as long as the merchant has internet access and can broadcast the transaction for you.

Today, the BitCoin community is made up mostly of people who have never met each other (I've met a few key people in person like justmoon, but not many). So minimizing the trust needed is useful and very much in the spirit of BitCoins design.

I don't disagree, but the above list is ideal for a client intended to convieniently spend coins, not accept them.  The spender doesn't need to be able to verify anything, at least not in real time.  It's the vendor selling things that is taking the risks.  Again, I ask the question; in what context would a portable POS system that needs to be disconnected from the Internet be useful?  Even hotdog vendors have Internet access.