Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)

[NanoAkron]

Hi all,

There have been some heated discussions on here since Mike Hearn's 'proof of passport' talk for identifying valid nodes to prevent man-in-the-middle attacks (here: http://www.iamsatoshi.com/coinscrum-networking-evening-circle-london/).

I think that any solution that would require a token external to the bitcoin network itself, such as passports or ID cards, are inherently counter to the trustless, decentralised nature of bitcoin, as well as being potentially open to manipulation by unsavoury characters or forces either now or later.

The problem as it stands was stated quite well by erik777:

The bottom line is if you're trying to detect the integrity of a node you're talking to, you are asking peers that have talked to that node in the past that you've talked to in better contexts.  Each node can track latency, uptime, etc, on all the nodes they talk to.  They don't have to share details, just how normal it is.  

To be sure, you can't 100% trust any node.  That's not the goal.  You're just trying to make it more difficult for someone to create a fake bitcoin network on a wifi spot they are hosting.  This can make it virtually impossible to pop up a bunch of new nodes with no history on the bitcoin network, or to bring them up and down.  Does it rule out every type of node fraud?  No, but it makes it much harder.  You'd have to create a history on the network with your nodes.  And, as soon as your nodes are identified as bad, that history would become moot, requiring a new history.  

You are creating higher credibility for nodes with a HISTORY of uptime, consistent latency with its peers, and presence on the blockchain over those that are new, credibility you'd primarily use when on an untrusted local network and you need transaction confirmation quickly, the scenario Mike is trying to address with passports.

This is not the same as real world trust networks.  This is based purely on network data, with the network reinforcing itself, increasing its own integrity dynamically.  This is still conducive to a trustless network so long as you don't make it part of your core, but an add-on to offset those times when you can't otherwise trust the network and nodes you are currently talking to without a historical linkage.  

My personal feeling is that a 'proof-of-connectivity' relying on data transmission rates and time-stamping might be a way forward, and I'm currently looking for academic papers that could back this idea up in purely mathematical/objective terms. For example - if I gave you a starting point such as a nearby train station, and told you times and turns you could identify my house with 100% accuracy each time.

If you could start with one node and probe a map of its connectivity to others nearby, you'd end up with a trustless connectivity map accurately identifying that node.

Or imagine a 'Stargate' model, where a sequence of latencies to nearby nodes produces an unforgeable code/identifier. Each block originating from a node could even be labelled with its 'gate address'. Furthermore, this could generate a node map that's permanently encoded into the block chain, growing organically with the network but also allowing the identification of spoofed nodes (for example, nodes that suddenly appear and have a fixed time lag to one particular group of nodes that it's trying to spoof, but 'wrong' latencies to other supposedly nearby nodes).

So, we all know that:

1. Time moves in one direction
2. Networks have non-zero latencies between nodes
3. Geographic location can correlate with local network latency/routing
4. Time stamping CAN be highly accurate with modern technology

I believe a combination of these factors would allow more objective identification of nodes, using inherent properties of the network itself to provide zero-trust identification. The results could be hashed and encoded into blocks delivered by a particular node, thereby putting a form of the map into the blockchain.

I am NOT advocating white/black/brown-listing in any fashion, merely local trustworthiness built upon a history of functionality within the greater network.

All thoughts welcome. Previous discussion here: (https://bitcointalk.org/index.php?topic=429264.msg4753847).

[Peter Todd]

You're asking the wrong question really. The thing to do isn't to try to better establishing trustworthiness, it's to use Bitcoin in ways where you don't need your peers to be trustworthy. After all, the whole point of Bitcoin itself is to create a currency system where trust isn't required, and Bitcoin is quite successful at that. Don't screw that up by adding "trust" all over again.

So here's your new questions: "Why would a SPV client need to trust a peer?" and for each of those reasons "How can we improve our security and remove the need for that trust?"

[NanoAkron]

Thanks. As per the wiki, "SPV does not verify everything, but instead relies on either connecting to a trusted node, or puts its faith in high difficulty as a proxy for proof of validity."

Personally, I'm not too happy with the idea of 'trusted nodes', so let's focus on the 'high difficulty' side instead.

In other words, let's make it very difficult for a node to be spoofed. Mike Hearn's suggestion is to verify nodes through an externally issued trusted token.

I want instead to make it nearly impossible for nodes to pretend to be truly connected when they're actually not. Hence the idea of a 'proof-of-connectivity', relying on a p2p methodology and fixed physical principles (timestamping and non-zero network latency) and forming part of the core of node functionality.

What do you think?

[d'aniel]

You're asking the wrong question really. The thing to do isn't to try to better establishing trustworthiness, it's to use Bitcoin in ways where you don't need your peers to be trustworthy. After all, the whole point of Bitcoin itself is to create a currency system where trust isn't required, and Bitcoin is quite successful at that. Don't screw that up by adding "trust" all over again.

So here's your new questions: "Why would a SPV client need to trust a peer?" and for each of those reasons "How can we improve our security and remove the need for that trust?"

As I understand it, the scenario we're dealing with here is: SPV + 0-conf tx + malicious sender + all peers controlled by sender.  People are focusing on ways to make the latter difficult via Tor + anti-sybil measures, but you appear to be suggesting that this isn't actually necessary.

The tools I'm aware of to perhaps help here are:

1) UTXO set commitments enable SPV nodes to fully verify the received tx, which is nice, but of course the tx won't actually reach the miners before being double spent, since the SPV node is surrounded by the sender's nodes.
2) Replace-by-fee can create an incentive for the sender not to double spend by enabling you to, before any confirmations have occurred, spend the full value to fees, where the sender has included a bit extra which would otherwise have been sent back to him.  But this also doesn't actually help if the sender has you surrounded in the network, since you'd be relying on him to broadcast the replacement in time.

Are there some other tools I'm missing?  What lines are you thinking along here?

Edit: This https://bitcointalk.org/index.php?topic=321085.0 is maybe another way I know of.

[Peter Todd]

As I understand it, the scenario we're dealing with here is: SPV + 0-conf tx + malicious sender + all peers controlled by sender.  People are focusing on ways to make the latter difficult via Tor + anti-sybil measures, but you appear to be suggesting that this isn't actually necessary.

The tools I'm aware of to perhaps help here are:

1) UTXO set commitments enable SPV nodes to fully verify the received tx, which is nice, but of course the tx won't actually reach the miners before being double spent, since the SPV node is surrounded by the sender's nodes.
2) Replace-by-fee can create an incentive for the sender not to double spend by enabling you to, before any confirmations have occurred, spend the full value to fees, where the sender has included a bit extra which would otherwise have been sent back to him.  But this also doesn't actually help if the sender has you surrounded in the network, since you'd be relying on him to broadcast the replacement in time.

Are there some other tools I'm missing?  What lines are you thinking along here?

Something that's been proposed a number of times is that miners include node addresses of some kind in the blocks they mine. For instance a IP adddress + pubkey or Tor onion address. (which includes its own pubkey) With that mechanism being surrounded by malicious peers does no real harm - either those peers fail to relay block headers to you, resulting in you knowing you are disconnected, or they do, which lets you easily connect to a majority of hashing power reliably. In either case the replace-by-fee logic works fine. With regard to fees that also lets you make sure your unconfirmed transactions have gotten to hashing power reliably, so you know that if a miner is willing to accept your tx at the given fee, they had a chance of doing so. Similarly proof-of-propagation can be used for that information.

Where (U)TXO set commitments matters is to make sure peers aren't hiding any relevant transactions from you, and even without them there are lots of way to get the same effect like random sampling, and maybe most importantly, keeping your queries anonymous with Tor, VPN's, and good blockchain query privacy measures.

Edit: This https://bitcointalk.org/index.php?topic=321085.0 is maybe another way I know of.

You can also use fidelity-bond's to guarantee to the recipient that you won't double-spend a transaction - a very easily proven thing.  Off-chain transaction systems in general solve this problem too.

It's also worth remembering that it's actually pretty rare to need solid zero-conf transaction guarantees anyway - in almost all cases either you're not actually shipping some product immediately upon payment receipt, (shipping a product) canceling it after the fact is easy, (subscriptions) you know your customer anyway and can trust them.

Resorting to reliance on centralized, government controlled, systems as step #1 is just lazy thinking, and in this case encourages people to use Bitcoin in ways that are fundamentally unsafe without central authority.

[NanoAkron]

It's also worth remembering that it's actually pretty rare to need solid zero-conf transaction guarantees anyway - in almost all cases either you're not actually shipping some product immediately upon payment receipt, (shipping a product) canceling it after the fact is easy, (subscriptions) you know your customer anyway and can trust them.

Resorting to reliance on centralized, government controlled, systems as step #1 is just lazy thinking, and in this case encourages people to use Bitcoin in ways that are fundamentally unsafe without central authority.

Agree with you about your second point. Any thoughts on a 'proof-of-connectivity' for nodes, or am I just re-thinking the 'proof-of-propagation' issue?

As to your first point - some pubs take thousands in alcohol sales in a single night. If you could MITM them, laptop in a bag hidden in the middle of the busy room, they'd be in big trouble. This is where I feel zero-conf guarantees will be needed.

[Peter Todd]

Agree with you about your second point. Any thoughts on a 'proof-of-connectivity' for nodes, or am I just re-thinking the 'proof-of-propagation' issue?

I think you're extending it really, and you're probably not extending it in a way that really works. A good question to ask yourself is "How could I attack this with a bunch of fake proofs?"

As to your first point - some pubs take thousands in alcohol sales in a single night. If you could MITM them, laptop in a bag hidden in the middle of the busy room, they'd be in big trouble. This is where I feel zero-conf guarantees will be needed.

Nah, a pub is a pretty good example of why zero-conf doesn't matter all that much: If someone rips you off, you've got a pretty good chance of finding out in a few minutes. Ask the bartender which patron paid for it and have your bouncer go have a chat with them. Even with the busiest clubs this works pretty well - they've got security cameras everywhere to track down that person.

[d'aniel]

Thanks Peter, I forgot about the proof-of-propagation one.  I remember it sounding pretty slick.  Regarding miners publishing network addresses, Mike raised the issue of load balancing with something similar.  I guess that'd especially be a problem with most miners not even running full nodes.

[NanoAkron]

Nah, a pub is a pretty good example of why zero-conf doesn't matter all that much: If someone rips you off, you've got a pretty good chance of finding out in a few minutes. Ask the bartender which patron paid for it and have your bouncer go have a chat with them. Even with the busiest clubs this works pretty well - they've got security cameras everywhere to track down that person.

It's not the patron doing a double spend that's the worry, it's the guy sat in a corner with a briefcase pretending to be the node who mops up the evening's takings and slips away in silence. He's the 'node' we need to verify.

[Mike Hearn]

I'm glad my little talk is prompting people to talk about sybil attacks, but this conversation is confusing because you're all mixing up the two different types of attack I discussed (with two different types of solution)

1) MITM on bad wifi connections. Proof of propagation/connecting directly to miners/etc is in the same general area as connecting to randomly chosen peers through a trusted proxy. Most users don't have trusted proxies, but we can pick some Tor exits at random and correlate their answers to approximate this, which is what I proposed in the talk (and actually we're working on this for bitcoinj already).

Don't get me wrong - I like proof of propagation, if the bandwidth and latency requirements work out (I'd like to see some more detailed maths checking this). But it's not a whole lot different for solving case 1 than just using Tor.

2) Flooding networks with peers that look unrelated but actually aren't. Tor has the same problem, so I'm interested in solutions that generalise to all P2P networks. For these proofs of propagation etc are irrelevant. For Bitcoin it might be possible in every case to come up with fancy tricks based on proof of work, though remember someone has to actually write the code for all of these ideas! But I don't see how to avoid the issue with Tor. There just isn't any reasonable way that the Tor directory operators can know if nodes are related today, and if they are, Tor fundamentally breaks. Given that GCHQ has been tasked with breaking Tor (they're thinking of the children you see), advanced sybil attacks on it seem more likely than not in the near future.

Anyway, like I said, I love all the ideas flying about. But ... I'd appreciate it if in future people don't take material that was written to be interesting for a short presentation and make stupid assumptions, like if I talk about one or two solutions that must automatically mean I didn't think about any other solutions, or am a "lazy thinker". It was a 15 minute meetup talk, not a university lecture series.

[d'aniel]

GCHQ has been tasked with breaking Tor (they're thinking of the children you see), advanced sybil attacks on it seem more likely than not in the near future.

Ugh...

Anyway, like I said, I love all the ideas flying about. But ... I'd appreciate it if in future people don't take material that was written to be interesting for a short presentation and make stupid assumptions, like if I talk about one or two solutions that must automatically mean I didn't think about any other solutions, or am a "lazy thinker". It was a 15 minute meetup talk, not a university lecture series.

I wouldn't dare think of you as in any way lazy, and it's a shame that ideas can't be tossed around freely in Bitcoinland without witch-hunts ensuing.

[trilli0n]

2) Flooding networks with peers that look unrelated but actually aren't.

After giving it some more thought, I am starting to think that this can't be solved.

The problem with Tor is that you can't tell nodes apart. This, I believe, is a fundamental property of Tor as it intends to hide any network information. There is simply no way of knowing whether two or more nodes are on the same computer and controlled by a single person or group.

The only inherent property of a node that I can think of which can be verified securely is a lower bound for its computational speed. This can't be forged.

But nothing stops someone who wants to spoof the network with nodes from creating a huge number of nodes each pretending to have low computational power. At best, it would be suspicious.

I think when you think through the problem, you'll end up with a verification which is already in place: proof provided by the majority of computational power in the bitcoin network.

There's simply no replacement for that.

[Peter Todd]

2) Flooding networks with peers that look unrelated but actually aren't. Tor has the same problem, so I'm interested in solutions that generalise to all P2P networks. For these proofs of propagation etc are irrelevant. For Bitcoin it might be possible in every case to come up with fancy tricks based on proof of work, though remember someone has to actually write the code for all of these ideas! But I don't see how to avoid the issue with Tor. There just isn't any reasonable way that the Tor directory operators can know if nodes are related today, and if they are, Tor fundamentally breaks. Given that GCHQ has been tasked with breaking Tor (they're thinking of the children you see), advanced sybil attacks on it seem more likely than not in the near future.

It's easy to know if some Tor nodes are related and who runs them: there's a large number of high-bandwidth donation-based nodes run by various charitable organizations, e.g. torservers.net, and those nodes are well known. Tor does not fundamentally break by having who runs what nodes be publicly known - that's exactly how Tor already works.

The other interesting thing is that because tor is a semi-centralized system proof-of-bandwidth and proof-of-low-latency is practical - the central organization is trusted and can make the measurements - and that makes for a good lower-bounds on the financial resources expended to run those Tor nodes and the geographical decentralization of them. Basically it's a better version of proof-of-sacrifice, better because the "sacrifice" is inherently the thing you're suppose to be providing.

You're criticisms do apply to the I2P network though, a common criticism of it verses Tor.

Meanwhile if the GCHQ is your adversary, why are you making their job easier by giving them a huge advantage - they have access to tens of thousands of real and faked passports - that the honest defenders don't have?

[Peter Todd]

2) Flooding networks with peers that look unrelated but actually aren't.

After giving it some more thought, I am starting to think that this can't be solved.

The problem with Tor is that you can't tell nodes apart. This, I believe, is a fundamental property of Tor as it intends to hide any network information. There is simply no way of knowing whether two or more nodes are on the same computer and controlled by a single person or group.

Mike is propagating falsehoods. Here's a list of all Tor nodes: http://torstatus.blutmagie.de/ The organizations running many of those nodes make a point of advertising who they are and the fingerprints of the exit nodes they run: https://www.torservers.net/exits.html That also applies to relay nodes: http://www.enn.lu/status/relay

Tor is a technology, but it itself is just a tool; the reason why Tor can be used relatively safely is actually because of human social protections, not just cryptography. Infiltrating Tor is harder than it looks because you have to infiltrate large numbers of real-world organizations comprised of actual people - just the kind of thing that leads to rather undesirable leaks. It's also rather similar to how I've argued for some time now that the Electrum SPV clients are probably more secure and private because they rely on a small number of Electrum servers run by relatively accountable people rather than a large number of completely Bitcoin nodes run by parties unknown.

[coinrevo]

I believe the problem is that most concepts of traditional cryptography and computer security don't really apply. This is as much as about economics as anything else. Some of the real issues are just always out of scope in these discussions. One can't begin talking about them without having a different framework. One dimension from many of the current discussions missing is the political dimension, i.e. the effects on organization. This is not just about contracts, as contracts are rooted in legal system and government. Anyway, I don't think a purely technical view is really going to help very much to understand this. One can see this with the current designs of the payment protocols.

OP raises some very interesting points about the concept of geographic location. In a local context many of the concepts changes. As an example: in the context of traffic I trust that other actors will act a certain way. But I don't need to trust all actors, just actors around me at a specific moment in time. Most transactions take place in a geographic context.

If one thinks about these things in conjunction with meshnets I think one can come up with some very interesting thought experiments and future directions. I doubt that the next paradigm shift will be like the last, and at some point it might turn out that extending bitcoin might not be possible in the way it was thought. At least that's my conclusion from investigating all the "advanced" applications. There is the meme the bitcoin is like TCP/IP. I believe the relation of cryptocurrencies to protocols is quite complex and very different.

[Mike Hearn]

Tor does not fundamentally break by having who runs what nodes be publicly known - that's exactly how Tor already works.

I think you're misreading what was said.

Tor breaks if you pick three relays you think are not collaborating against you, but they actually are. Obviously if the Tor network is flooded with nodes that look superficially unrelated but are all run by an adversay, the chances of being deanonymized go up a lot.

I did not say you can't tell Tor nodes apart, so I'm not "propagating falsehoods". I said you can't know if they're really run by independent entities or by the same guy/people.

Meanwhile if the GCHQ is your adversary, why are you making their job easier by giving them a huge advantage - they have access to tens of thousands of real and faked passports - that the honest defenders don't have?

Anyone who wants to run Tor nodes can get a passport or use their existing one, it's not like there's a "no Tor" rule enforced by any countries passport office.

GCHQ might well be able to fake a large number of British passports, or heck, just use those of their employees. Perhaps they've even been able to hack a foreign country or two's passport agencies - who knows. But you can play geopolitics by having the ZKPOP reveal the issuing country and then picking relays run by citizens of countries that hate each other. That raises the stakes a lot - if GCHQ is forging a foreign countries passports that can, if discovered, turn into a major diplomatic disaster that isn't worth it.

In the current world all they have to do is rent a lot of servers around the world via front companies, hardly a big deal, and then run modified Tor nodes that log circuit activity. It can't get any easier than that.

[NanoAkron]

OP raises some very interesting points about the concept of geographic location. In a local context many of the concepts changes. As an example: in the context of traffic I trust that other actors will act a certain way. But I don't need to trust all actors, just actors around me at a specific moment in time. Most transactions take place in a geographic context.

Thank you for your reply. I'm trying to solve one specific problem I have in mind and see whether that could generalise to addressing some other issues in BTC at present.

Problem: Walk into a bar, pay for a drink, BTC vanishes into thin air because the node was spoofed or you got MITMd.
Problem 2: 51% attacks through mining pools

My proposed solution of encoding the 'linkage' between nodes could simultaneously address both of these.

Scenario 1:

If the node you see in a pub actually has no verifiable linkage history for its expected geographic location, it may be a spoofed node.

Of course, the bar could have just opened. But if they're running a true node, they'd be processing BTC blocks and building their reputation with other nodes. This could perhaps be in the form of an adjustment of new transaction fees (low for new nodes, higher for older ones) or maybe a CPU intensive relay delaying function so that like old fashioned password lockouts it would take a restrictively long time to continually spoof a node. Just thoughts at present, but still not requiring any verification tokens that are external to the network.

Scenario 2:

A mining pool has 51% block discovery rate. Well, they're probably operating through a handful of dedicated nodes. What if connectivity was reflected in an additional 'difficulty' metric added to the existing network difficulty (the 2016 block, 10-min difficulty).

I.e. more connected nodes relaying a lot of traffic between themselves have to work that little bit harder to process blocks relayed from each other, but less hard to crunch blocks from more distant nodes - this would encourage the network to preferentially source blocks from more distant nodes over more connected ones. This prevents a 51% attack by preventing chains of blocks being sequentially delivered from the same nodes, ensuring a good mix of blocks in the overall chain.

So, could 'local difficulty' and 'local fee' adjustments depending on node connectivity ('proof-of-connectivity') address both of these issues?

[Peter Todd]

Tor does not fundamentally break by having who runs what nodes be publicly known - that's exactly how Tor already works.

I think you're misreading what was said.

Tor breaks if you pick three relays you think are not collaborating against you, but they actually are. Obviously if the Tor network is flooded with nodes that look superficially unrelated but are all run by an adversay, the chances of being deanonymized go up a lot.

I did not say you can't tell Tor nodes apart, so I'm not "propagating falsehoods". I said you can't know if they're really run by independent entities or by the same guy/people.

Ah, yeah, my mistake, I misread that.

Anyone who wants to run Tor nodes can get a passport or use their existing one, it's not like there's a "no Tor" rule enforced by any countries passport office.

GCHQ might well be able to fake a large number of British passports, or heck, just use those of their employees. Perhaps they've even been able to hack a foreign country or two's passport agencies - who knows. But you can play geopolitics by having the ZKPOP reveal the issuing country and then picking relays run by citizens of countries that hate each other. That raises the stakes a lot - if GCHQ is forging a foreign countries passports that can, if discovered, turn into a major diplomatic disaster that isn't worth it.

In the current world all they have to do is rent a lot of servers around the world via front companies, hardly a big deal, and then run modified Tor nodes that log circuit activity. It can't get any easier than that.

It's just simple numbers - there's ~3,000 Tor nodes out there, and actually quite a bit less than that in terms of bandwidth product. If you don't create something honest people actually use, on a wide scale, what you've created is something that dishonest people use, on a wider scale. Remember that passports are held by large numbers of people, the GCHQ isn't going to have a hard time finding government employee with all kinds of passports, Russian, Chinese etc. even without faking them. (my former ~50 person company had individuals with those passports, and Iran, India and Pakistan among others) And if they do decide to hack them you've got a handy anonymous ZK proof scheme to cover up the fact you've done that.

[coinrevo]

NanoAkron, I think its valuable to think about these concepts, but unlikely they can be integrated with bitcoin. same with true identity which was kind of the goal I suppose with the passport mapping idea.

Proof of work is really a very clever workaround to achieve a certain goal, based on the fact that cycles can be moved around the globe arbitrarily. If one removes restrictions of TCP/IP one can redesign the PoW scheme. After all it also makes a lot of sense to have local money supply and money functions.

cjdns is an alternative to TCP/IP and uses cryptographic functions right at the core (an IP address is not a number assigned by an authority, but a node has a keypair). unlikely TOR the nodes' location are traceable. so you have some sort of identity and trust system build into the network, in a local sense.

[Minthos]

Problem: Walk into a bar, pay for a drink, BTC vanishes into thin air because the node was spoofed or you got MITMd.

What problem? Nobody can steal a customer's money that way. The bar won't give the customer an address that the bar doesn't control, and the customer won't sign a transaction to any other address than the one he receives from the bar. Are you worried that customers will double spend against the bar? If so, it'll quickly be discovered by the bar.