trustless address lookup for thin-clients

[qrius1111]

hi all, i'm new here and i'm not sure if i'm posting in the right place. feel free to move this post to somewhere appropriate.

i was thinking it would be nice to have a trustless way of looking up address balances without having to download the entire blockchain. i read in bip37 that there is a problem where a malicious remote node can omit transactions and there is no way for the thin client to know this has happened:

Thus, a merkleblock message is a block header, plus a part of a merkle tree which can be used to extract identifying information for transactions that matched the filter and prove that the matching transaction data really did appear in the solved block. Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible.

currently i'm not aware if this problem has been solved. i have googled for it and found nothing, so for the remainder of this post i will assume not...

one way around this might be to look up the address on blockchain.info or blockexplorer.com and verify that one's balance is correct, and therefore that no transactions are missing in the client. however this is not practical for a large e-commerce website which generates a lot of addresses automatically. i guess api calls can be used but still... i dislike the idea of trusting a third party when money is at stake.

and you could say that an e-commerce website should be downloading a full version of the blockchain - that would solve the problem. yet somehow it seems a bit of a wasteful requirement to me - particularly if other options are available.

i had an idea and i thought i'd see what people think of it. firstly, security is paramount, so it is vital that blanaces be validated by the client using the blockchain and not by some "trusted" third party. so i think that if a thin client wants to establish its balance, it should download the relevant transactions, pruned merkle tree for the block, and all block headers. i think this is already how all thin clients work - so no problems there.

but the problem lies in determining which transactions and pruned merkle trees to download - and specifically in ensuring that a full list of this data is provided. so my thinking was that an address book could be constructed using a merkle tree of addresses and their corrsponding lookup data, and then the root of that address book tree could be included in the blockchain somewhere - say the coinbase txin,  elsewhere in the bitcoin header, or even in a merge-mined blockchain like namecoin (this would avoid changes to the bitcoin protocol and clients could easily download all namecoin headers in addition to bitcoin headers as these are small). since this last option - using the namecoin blockchain - is the most likely solution of those 3, i will assume it for the remainder of this post.

full namecoin nodes would be able to verify this "address book merkle root" by reconstructing it for themselves, and maybe it could even be part of the namecoin protocol to reject blocks which contained incorrect "bitcoin address book merkle roots". the precise details of this address book are unknown to me, but a simplified example would look like this:

Code:

{
bitcoin address1: [bitcoin blockhash11, bitcoin blockhash12, bitcoin blockhash13, ...],
bitcoin address2: [bitcoin blockhash21, bitcoin blockhash22, bitcoin blockhash23, ...],
...
}

this way whenever a thin client wanted to download transactions for a specific address it could do a request to the address book (contained on many namecoin full nodes i envisage) to retrieve the specific blocks where its transactions are, then request the specified blocks the regular way through the network. really only specific txs in that block are required, but for simplicity's sake lets assume its the whole block at this stage.

namecoin miners could calculate the merkle root of all addresses by appending the latest bitcoin block's addresses into the merkle tree and keeping as many address branches pruned as possible from the previous instance of the database to reduce hashing (since the list of bitcoin addresses is huge).

and to ensure that remote nodes are not lying by omission when the thin clients request their address list, the minimal verification branches of the address merkle tree could be supplied to the thin client so that it can calculate the address-merkle-root by itself and compare it to the value in the block header.

friendly comments welcome. maybe this problem has already been solved in some other way that i'm not aware of, and the above is an inferior solution? let me know...

[1714933946]

1714933946

[1714933946]

1714933946

[1714933946]

1714933946

[hhanh00]

Looks similar to https://gist.github.com/maaku/2aed2cb628024800044d which seems inactive by now.

[qrius1111]

yeah that's very similar - albeit a bit more generic (which is probably a good thing).

as an aside, i also noticed that bip33 proposes a method to "discover the history of a bitcoin address without needing direct access to the blockchain", but it still relies on some degree of trust. if the client can be cut off from all reliable nodes then it really makes no difference what percentage of the contacted nodes are in agreement - agreement among malicious nodes offers no security. i know such a thing would be hard to pull off, but when the stakes are high the likelihood increases. for example if an isp were to simply block off access to ip addresses of trustworthy full-nodes, and only allow access to malicious nodes. or to redirect requests aimed at trustworthy nodes all to a single malicious node, the client could be fooled into thinking it had never received certain funds.

[hhanh00]

i know such a thing would be hard to pull off, but when the stakes are high the likelihood increases.

There is a recent study showing an attack that exploits the way bitcoin core handles addr messages and chooses peers.

[1]: http://cs-people.bu.edu/heilman/eclipse/

[domob]

Since you mentioned Namecoin, let me comment on that aspect (sorry if that's somewhat off-topic):  It is very unlikely that the Namecoin protocol will be changed to require (anything) about Bitcoin addresses.  In particular, requiring Namecoin miners to keep a full address book of Bitcoin addresses seems very unlikely.  Also, you might be interested in https://forum.namecoin.info/viewtopic.php?f=5&t=2239:  We're discussing a somewhat similar change to Namecoin at the moment, although for keeping a committment of the set of names (for light Namecoin clients) and not the Bitcoin address book.  I've not thought about how well the proposal fits to Bitcoin addresses, though, since we are interested in names.

[hhanh00]

Yes, it is a very similar idea. The only significant difference is the usage of a radix trie which could be helpful to you too.
I'm not sure why this proposal didn't get implemented. Maybe simply a lack of interest.
I like it - it would allow the publication of a verifiable UTXO set though it is already above 1 GB at this point.

If someone is interested in continuing the work in bitcoin core, I can implement something equivalent in my alternate client to compare with.

[gmaxwell]

There is a recent study showing an attack that exploits the way bitcoin core handles addr messages and chooses peers.

That particular work is irrelevant here, Bitcoin core is intrinsically safe against the attacks this poster is describing. What SPV nodes do to different (and usually inherently less safe).

[qrius1111]

domob, your discussion in the namecoin forum is very similar to this thread. i can see deciding where to put the root-hash of this bitcoin address-lookup thing, even if people think it is a good/efficient way of solving the spv problem, is going to be a task in and of itself.

as you say, each miner/pool-manager will have to have a full bitcoin node, or at the very least a steady flow of the latest bitcoin blocks built on top of an existing address book from some point in the past - just to be able to keep the address book up to date.

my original thinking for suggesting namecoin was that namecoin is intended as a distributed database, whereas bitcoin is more associated with currency. i was also thinking that getting changes made to bitcoin will be slower, and namecoin is maybe easier? however the proposal would mean that namecoin miners would have to run a bitcoin full node as part of their protocol, and it this would both require a lot more resources for namecoin miners, as well as breaking the "separation of concerns" between bitcoin and namecoin (although merged mining has already done that to some degree).

so maybe it would be best to keep the address book entirely on the bitcoin side of things.

this leaves the tx scripts (probably the coinbase txin) and the block header for storing the root-hash of the address book. the coinbase txin seems like a far better candidate, since it would not require changes to the bitcoin protocol. but i also realize that this is valuable space and there are a potentially infinite number of things people might want to store in the coinbase txin.