Bitcoin Forum
December 06, 2016, 07:56:37 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Merkle tree inside Block Headers for light client mode  (Read 2870 times)
pmarches
Newbie
*
Offline Offline

Activity: 8


View Profile
April 19, 2011, 10:05:39 PM
 #1

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
1481054197
Hero Member
*
Offline Offline

Posts: 1481054197

View Profile Personal Message (Offline)

Ignore
1481054197
Reply with quote  #2

1481054197
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 19, 2011, 10:45:11 PM
 #2


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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
April 20, 2011, 02:20:04 AM
 #3

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
April 20, 2011, 02:31:49 AM
 #4

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
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
April 20, 2011, 02:58:37 AM
 #5

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
April 20, 2011, 05:37:39 PM
 #6

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
Newbie
*
Offline Offline

Activity: 8


View Profile
April 21, 2011, 12:17:20 AM
 #7

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
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 21, 2011, 12:32:15 AM
 #8

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. 

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
April 21, 2011, 01:00:10 AM
 #9

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
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 21, 2011, 05:00:47 AM
 #10

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
April 21, 2011, 05:15:15 AM
 #11

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

Activity: 1666



View Profile
April 21, 2011, 01:38:10 PM
 #12

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
April 21, 2011, 02:18:01 PM
 #13

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
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 21, 2011, 02:56:28 PM
 #14

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
April 21, 2011, 04:57:50 PM
 #15

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
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
April 21, 2011, 06:30:42 PM
 #16

...
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
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
April 21, 2011, 06:35:54 PM
 #17

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
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
April 21, 2011, 07:01:36 PM
 #18

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
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 21, 2011, 07:19:58 PM
 #19

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
April 21, 2011, 07:51:48 PM
 #20

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.
Quote

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.

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!