Mike Hearn, London 2014 [video presentation]

[Mike Hearn]

This Proof of Passport just seems a solution in search of a problem. And the solution does not even work.

Did you watch my talk? There are two types of sybil attack I discuss. One is the wifi attack, for which I propose Tor.

The other is for flooding the network with bogus peers in general. For that I propose proof of sacrifice, and proof of passport.

What you are talking about is relevant for the first case only, for which using Tor is sufficient.

[erik777]

This Proof of Passport just seems a solution in search of a problem. And the solution does not even work.

Did you watch my talk? There are two types of sybil attack I discuss. One is the wifi attack, for which I propose Tor.

The other is for flooding the network with bogus peers in general. For that I propose proof of sacrifice, and proof of passport.

What you are talking about is relevant for the first case only, for which using Tor is sufficient.

I like tackling both problems with one stone.  Here's a solution that, yes, will require an extension to our current P2P protocol, but kills many birds which you only begin to address here:

1> When nodes discover each other for the first time, they share public keys with each other, which becomes a form "node ID".

2> A node will collect the IDs of the nodes it talks to, along with certain meta data, such as average latency over the past 24 hours, 30 days, etc,...

3> When a wallet talks to nodes, it collects their public keys.  When it transactions via them, it notes, it to.  So, a node confirming a transaction can be proven over time to have participated in the Bitcoin network.  We can decide what activities help to define honest participation, effectively building reputations for nodes.   

4> A node can periodically ask its peers to share the meta data they have on it, which those nodes sign. 

5> When your wallet to a node it's not sure it can trust, you can ask it for proof of network interaction.  It then signs a copy of the signed testaments of other nodes it obtained in #4.

6> Your wallet can compare the node keys in #5 against those previously collected via #3.  Based on this, it can create a "trust score" combining these factors. 

To be sure, this "trust score" isn't 100% guaranteed.  It only says that here are reasons to believe that the node you are thinking about trusting has given certain evidence of its reputation via peers you have used in the past.  In the end, the human with the wallet still has to decide if this "score" meets their threshold before completing their transaction.  But, like 6 confirmations, we can come up with a scoring system that, in the end, increases the expense of creating a fake wifi and bogus peers. 

This system can be extended using a "bad transaction" blockchain, because if you complete the transaction with a descent score, and it turns out to be bad, you now have proof that the node owning that key lied.  Because it took effort and time for that "node ID" to build a reputation, that reputation is thrown away.  Node reputations become the cost in this model, which take time, at a minimum, to earn. 

On top of that, we can include other meta data in the bad transaction chain, such as IP address.  Over time, we can use it to analyze these threats better and create better counter measures. 
         
Let's step out of our current problems and look at the possibilities.  We're creating a chain, not for currency transactions, but for network health intelligence.  Other types of network health indicators can go in there.  This can help the network learn how to improve, to increase resilience, to be more healthy and protected from various types of threats, like the 51% attack. 

[trilli0n]

This Proof of Passport just seems a solution in search of a problem. And the solution does not even work.

Did you watch my talk? There are two types of sybil attack I discuss. One is the wifi attack, for which I propose Tor.

The other is for flooding the network with bogus peers in general. For that I propose proof of sacrifice, and proof of passport.

What you are talking about is relevant for the first case only, for which using Tor is sufficient.

Yes I had watched it, but now watched it again. What you said in your talk was:

1. A Sybil attack can be carried out by tricking a node into thinking it is connected to the real bitcoin network when in fact it is not, by basically spoofing the bitcoin network over a controlled internet link. Tor can mitigate this Sybil attack, because it is impossible to spoof the Tor network, and the node has a way to discover that it is not connected to the real bitcoin network.

2. However, Tor introduces another problem since it hides IP addresses. It is not possible to verify that nodes seen through the Tor network aren't actually all coming from a single computer. This gives rise to another Sybil attack, where it is possible for a single computer to flood the network with nodes.

For 1, my proposed solution based on building trust would solve it, but so would using Tor.
For 2, we need proof of sacrifice or proof of passport, which is intended to prevent a single person or group from flooding the network with nodes.

Agree so far?

Now, the root of the problem seems to be the fact that one person or group is able to control a large number of nodes, enough to trick a peer node into believing it is connecting with the real bitcoin network when it is actually not. To mitigate this, a node must somehow be able to prove itself in a way that can not be easily replicated. Your solution proposes to use a proof of passport - a document with unique, verifiable properties, which you presume are hard to obtain. That would make it impossible for an attacker to flood the network with nodes, because each node requires a proof of passport.

Agree so far as well?

Now my problems with this:

1. It will not be difficult for a determined attacker to obtain many proofs of passports. As soon as proofs of passports obtain value, hackers will have them for sale in quantities, making the proof of passport instantly worthless.
2. It raises a barrier of entry for someone to participate in the network with a full node. A minority of the people own a passport. Only a subset of them will agree to provide a proof of passport for the privilege of running a full node.
3. What happens if someone else obtains my proof of passport and also runs "my" node? How does a network decide which node is the "good" one, and which one is the "bad" one?
4. I'm concerned about the privacy and security implications. A passport is gets tied to a node. Can't oversee this fully, though, I admit.
5. There might be better alternatives to solve this problem.
6. Despite you tinkering with the idea for over half a year, it's only now that an in-depth, serious, critical discussion is starting. The discussion should have been started by you six months ago. I'd expect a lead developer to more actively engage with the community for ideas that you can suspect to be controversial.

I think 1 is the elephant in the room, has been mentioned several times by multiple people, but unfortunately has so far not been addressed by you I think.

[trilli0n]

Quoting myself:

the root of the problem seems to be the fact that one person or group is able to control a large number of nodes, enough to trick a peer node into believing it is connecting with the real bitcoin network when it is actually not. To mitigate this, a node must somehow be able to prove itself in a way that can not be easily replicated.

How about asking all peers to simultaneously provide a small proof of work before trusting them? If the peers are all the same node, this will be suspiciously slow. Also, previously seen nodes may have previously known speeds. If a node is slower than usual, then this is also suspicious.

Could that work?

[erik777]

Quoting myself:

the root of the problem seems to be the fact that one person or group is able to control a large number of nodes, enough to trick a peer node into believing it is connecting with the real bitcoin network when it is actually not. To mitigate this, a node must somehow be able to prove itself in a way that can not be easily replicated.

How about asking all peers to simultaneously provide a small proof of work before trusting them? If the peers are all the same node, this will be suspiciously slow. Also, previously seen nodes may have previously known speeds. If a node is slower than usual, then this is also suspicious.

Could that work?

The limitation with that is you're now asking the nodes to become CPU intensive.  What's their incentive? 

Because this is a network problem, solving it at the network level permits P2P itself to become more robust.  This benefits bitcoin, but also other usages of P2P. 

While proof of work apparently works when you are talking about generating currency with value out of thin air (mining), it doesn't transcend well to other tasks.  With networking, efficiency and speed is a goal, and the primary value is in the sum of the parts rather than individual pieces.

Of course, I love that you are looking for an alternative to Mike's passport approach. 

[trilli0n]

Quoting myself:

the root of the problem seems to be the fact that one person or group is able to control a large number of nodes, enough to trick a peer node into believing it is connecting with the real bitcoin network when it is actually not. To mitigate this, a node must somehow be able to prove itself in a way that can not be easily replicated.

How about asking all peers to simultaneously provide a small proof of work before trusting them? If the peers are all the same node, this will be suspiciously slow. Also, previously seen nodes may have previously known speeds. If a node is slower than usual, then this is also suspicious.

Could that work?

The limitation with that is you're now asking the nodes to become CPU intensive.  What's their incentive?

Well, to support the bitcoin network of course. Isn't that the whole point of running a full node?

And it should not have to be that computationally intensive, because it only required once when first seen, and once when doing a transaction. There are no doubt better ways than I can come up with to implement it, but imagine the following simple and probably naive implementation:

Before doing a transaction, a set of nodes can be asked to repeatedly scrypt the same a string for one second, and provide the outcome, with which a lower bound for each of their speeds can be established. If this is not radically lower from the speeds that were found when the node was first seen, then the node is considered to be safe.

The fastests nodes can be considered the safest, because they will be the hardest to spoof.

[NanoAkron]

Quoting myself:

the root of the problem seems to be the fact that one person or group is able to control a large number of nodes, enough to trick a peer node into believing it is connecting with the real bitcoin network when it is actually not. To mitigate this, a node must somehow be able to prove itself in a way that can not be easily replicated.

How about asking all peers to simultaneously provide a small proof of work before trusting them? If the peers are all the same node, this will be suspiciously slow. Also, previously seen nodes may have previously known speeds. If a node is slower than usual, then this is also suspicious.

Could that work?

The limitation with that is you're now asking the nodes to become CPU intensive.  What's their incentive?

Well, to support the bitcoin network of course. Isn't that the whole point of running a full node?

And it should not have to be that computationally intensive, because it only required once when first seen, and once when doing a transaction. There are no doubt better ways than I can come up with to implement it, but imagine the following simple and probably naive implementation:

Before doing a transaction, a set of nodes can be asked to repeatedly scrypt the same string for one second, and provide the outcome, with which a lower bound for each of their speeds can be established. If this is not radically lower from the speeds that were found when the node was first seen, then the node is considered to be safe.

The fastests nodes can be considered the safest, because they will be the hardest to spoof.

Or each time a block is broadcast, it picks up 'breadcrumbs' of transmission times along its journey from A --> B. This generates a local network routing map. These breadcrumbs are somehow secured with a work function taking a certain amount of real time (perhaps hashes of time T=0 and time T=0+100msec) so you can see whether it's been artificially hindered or sped along its journey along one route. The breadcrumbs can be discarded after 'proof-of-connectivity' is established so as not to clog the block chain.

Thinking further, are there such things as hardware naive timing functions, perhaps a simple counter, say 'count to X' with the start time and end times signed. This would provide a hard definition of the expected performance of a node the next time it's questioned - if suddenly the timer takes longer, it's possibly compromised. You'd of course have to ensure that no 'sleeper cells' were installed along the way, waiting to suddenly begin relaying forged work.

[ArticMine]

The problem with proof of passport is that there are many people who have dual citizenship or even three or more citizenships. Since many countries in the world allow for dual citizenship these people can legitimately have several passports from multiple nation states. Furthermore dual citizens tend to breed dual citizens since many nation states recognize citizenship passed on from parent to child. This creates the possibility for a small family to have access to eight of more passports all legitimately obtained, more than enough to set up this kind of fake network.

By the way Canada a nation with a large number of immigrants that allows for dual citizenship is a perfect location for this.

Edit: Here is an example of the dual/triple citizenship attack on the proof of passport idea: https://bitcointalk.org/index.php?topic=433122.msg4765658#msg4765658

[Mike Hearn]

I mentioned in the talk that the difference that's interesting is "a few" vs "thousands" rather than one vs a few. If you bring up 3 nodes, that's not a bad thing! Heck, bring up 10! As long as a single wallet only uses one of your nodes per session, that's no big deal.

So yes I am aware (and already was aware) that some people have multiple passports, it's not like I never heard of dual citizenship.

The way the zero-knowledge proofs work is that you can choose what to include in the boiled down hashed data. For instance you could just include name and birthday. It'd mean a wallet might avoid connecting to two nodes run by two legitimately unrelated people if they happened to have the same name and be born on the same day, but it'd also mean they'd avoid nodes run by one guy with three passports. But the scale of these attacks isn't very interesting.

As to why I talked about this now instead of after six months, well, er, I don't give talks very often? At any given time I've got a billion ideas floating around in my head and frankly, I'm unlikely to post any of them here given this forums track record:   people flame, they hate, they make threads with titles like "How do we stop Mike Hearn" and often they haven't even actually read or understood what I really said. If you're surprised that I might not rush to post every idea I come up with here .... don't be.