Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: NanoAkron on January 26, 2014, 04:51:36 PM



Title: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 26, 2014, 04:51:36 PM
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/ (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:

Quote
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 (https://bitcointalk.org/index.php?topic=429264.msg4753847)).


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 26, 2014, 08:43:01 PM
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?"


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 26, 2014, 09:01:58 PM
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?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: d'aniel on January 27, 2014, 01:08:15 AM
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 (https://bitcointalk.org/index.php?topic=321085.0) is maybe another way I know of.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 27, 2014, 01:53:22 AM
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 (https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02868.html) 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 (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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 27, 2014, 02:02:35 AM

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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 27, 2014, 02:11:39 AM
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: d'aniel on January 27, 2014, 03:41:25 AM
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 27, 2014, 09:54:27 AM

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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Mike Hearn on January 27, 2014, 10:00:18 AM
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: d'aniel on January 27, 2014, 11:55:27 AM
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...

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


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: trilli0n on January 27, 2014, 01:20:54 PM
Quote
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.




Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 27, 2014, 01:29:25 PM
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?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 27, 2014, 01:39:54 PM
Quote
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 27, 2014, 03:57:48 PM
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.



Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Mike Hearn on January 27, 2014, 04:17:12 PM
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.

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



Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 27, 2014, 04:19:20 PM

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?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Peter Todd on January 27, 2014, 04:59:58 PM
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 27, 2014, 05:00:56 PM
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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 28, 2014, 09:02:15 AM

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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 28, 2014, 10:06:41 AM

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.

That's not the worry. A man-in-the-middle attack (MITM) means that what the bar thinks is a valid node to the rest of the bitcoin network is actually the perpetrator.

That's the scenario we're talking about here - validating the pathway between user <--> node.

I want the validation to remain trustless and to not require any external validation e.g. "I say my node is valid and here's my driver's license to prove it." - validation should be like the rest of bitcoin: trustless and distributed, built upon a cryptographically signed 'proof-of-x' function.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 28, 2014, 10:13:20 AM

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.

That's not the worry. A man-in-the-middle attack (MITM) means that what the bar thinks is a valid node to the rest of the bitcoin network is actually the perpetrator.

That's the scenario we're talking about here - validating the pathway between user <--> node.

I want the validation to remain trustless and to not require any external validation e.g. "I say my node is valid and here's my driver's license to prove it." - validation should be like the rest of bitcoin: trustless and distributed, built upon a cryptographically signed 'proof-of-x' function.

So if nobody can steal anything, what's the problem?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 28, 2014, 12:40:15 PM

So if nobody can steal anything, what's the problem?

What do you mean? The MITM spoofing the node gets to run away with all of the BTC that the pub took that evening.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 28, 2014, 12:47:43 PM

So if nobody can steal anything, what's the problem?

What do you mean? The MITM spoofing the node gets to run away with all of the BTC that the pub took that evening.

How? It can't get the bar's private keys, and it can't change the bar's receiving addresses. So how is it supposed to get hold of those coins?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 28, 2014, 12:53:44 PM

So if nobody can steal anything, what's the problem?

What do you mean? The MITM spoofing the node gets to run away with all of the BTC that the pub took that evening.

How? It can't get the bar's private keys, and it can't change the bar's receiving addresses. So how is it supposed to get hold of those coins?

The bar thinks the man with the suitcase in the corner is actually a node. The bar is relaying blocks to the rest of the network through this supposed node. The blocks either get edited or just not relayed to the rest of the network. The man with the suitcase pretends to the bar that the block has been confirmed correctly. The man with the suitcase walks out with BTC.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 28, 2014, 01:02:05 PM

So if nobody can steal anything, what's the problem?

What do you mean? The MITM spoofing the node gets to run away with all of the BTC that the pub took that evening.

How? It can't get the bar's private keys, and it can't change the bar's receiving addresses. So how is it supposed to get hold of those coins?

The bar thinks the man with the suitcase in the corner is actually a node. The bar is relaying blocks to the rest of the network through this supposed node. The blocks either get edited or just not relayed to the rest of the network. The man with the suitcase pretends to the bar that the block has been confirmed correctly. The man with the suitcase walks out with BTC.

You need to read more about how bitcoin works. First of all, the bar doesn't send blocks anywhere since it doesn't mine. It doesn't even send transactions, it just listens for incoming transactions and incoming blocks. Secondly, transactions are signed before they're broadcast to the network. Once they have been signed, they can't be tampered with. So your MITM can't edit any transactions. What he can do is be selective about which transactions he forwards where. If he were to collude with the customers, he could help facilitate double-spending attacks against the bar, but as mentioned previously any such attack could quickly be detected.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 28, 2014, 01:24:07 PM
Its not how bitcoin works, but its an interesting concept. Instead of having the whole world verify blocks, one could somehow use nodes in some proximity. One could call it local web of trust.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 28, 2014, 11:29:16 PM
Its not how bitcoin works, but its an interesting concept. Instead of having the whole world verify blocks, one could somehow use nodes in some proximity. One could call it local web of trust.

One worry is the bar thinks its getting paid because it's seeing false confirmations, when in reality it's giving away drinks for free because the transactions are never getting relayed to the rest of the network.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 28, 2014, 11:36:08 PM
Its not how bitcoin works, but its an interesting concept. Instead of having the whole world verify blocks, one could somehow use nodes in some proximity. One could call it local web of trust.

One worry is the bar thinks its getting paid because it's seeing false confirmations, when in reality it's giving away drinks for free because the transactions are never getting relayed to the rest of the network.

Nope. A "confirmation" is a valid block with the transaction included, and a valid block includes a proof of work. The proof of work is far too valuable to waste trying to double spend in a bar.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 12:11:15 AM
Its not how bitcoin works, but its an interesting concept. Instead of having the whole world verify blocks, one could somehow use nodes in some proximity. One could call it local web of trust.

One worry is the bar thinks its getting paid because it's seeing false confirmations, when in reality it's giving away drinks for free because the transactions are never getting relayed to the rest of the network.

Nope. A "confirmation" is a valid block with the transaction included, and a valid block includes a proof of work. The proof of work is far too valuable to waste trying to double spend in a bar.

Except for 2 things: in rapid low-value retail environments where we're told 0 conf should be ok, and I know bars that turn over £2,000+/night. Plenty of easy pickings if you spoof a few confirmations by pretending to be the rest of the network.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Minthos on January 29, 2014, 12:23:34 AM
Its not how bitcoin works, but its an interesting concept. Instead of having the whole world verify blocks, one could somehow use nodes in some proximity. One could call it local web of trust.

One worry is the bar thinks its getting paid because it's seeing false confirmations, when in reality it's giving away drinks for free because the transactions are never getting relayed to the rest of the network.

Nope. A "confirmation" is a valid block with the transaction included, and a valid block includes a proof of work. The proof of work is far too valuable to waste trying to double spend in a bar.

Except for 2 things: in rapid low-value retail environments where we're told 0 conf should be ok, and I know bars that turn over £2,000+/night. Plenty of easy pickings if you spoof a few confirmations by pretending to be the rest of the network.

Are you aware that the block reward is currently worth 19200 USD? That's how much it costs to spoof a single confirmation. Nodoby is going to do that just to get a few free drinks in a bar.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 02:19:09 AM
So why did Mike Hearn go to lenghs to describe passport based verification of nodes? What problem was he proposing this would solve?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: d'aniel on January 29, 2014, 04:32:22 AM
So why did Mike Hearn go to lenghs to describe passport based verification of nodes? What problem was he proposing this would solve?

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.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Qoheleth on January 29, 2014, 05:33:33 AM
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.
Hrm. The problem is that even if the network decided to ask for passport blind-signing, that solution doesn't work for this use case because the attacker can issue passports.

On the other hand, it's a thought. If you had to sign with an identity that was fundamentally difficult to create due to some other consideration...


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: d'aniel on January 29, 2014, 06:39:26 AM
Hrm. The problem is that even if the network decided to ask for passport blind-signing, that solution doesn't work for this use case because the attacker can issue passports.
I believe the idea is that the ZKPOP can reveal the country that issued the passport, so when setting up your Tor circuit, you'd select relays from distinct countries.  Then a sybil attack against Tor would require international coordination of governments.

Though don't governments generally have access to lots of foreign passport scans from border crossings, airport, etc.?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 09:56:27 AM
Hrm. The problem is that even if the network decided to ask for passport blind-signing, that solution doesn't work for this use case because the attacker can issue passports.
I believe the idea is that the ZKPOP can reveal the country that issued the passport, so when setting up your Tor circuit, you'd select relays from distinct countries.  Then a sybil attack against Tor would require international coordination of governments.

Though don't governments generally have access to lots of foreign passport scans from border crossings, airport, etc.?

So let's go back to the topic at hand: How do we establish the trustworthiness of nodes without external tokens?

What structural/functional properties of bitcoin can we use to establish a node is a real node in a trustless and distributed fashion?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 29, 2014, 10:00:37 AM
People need to realize that proof of work is a means to an end. A better system is possible if nodes are connected to identities.

It seems to me very unlikely than there will be an establishment of a global identity system which can't be corrupted. You might be able to prove you own a passport, but you can't prove you haven't stolen the passport. There is no key testing. Human markers (fingerprints, eye scan, genetic information) are unique and testable. Other information usually used to create a map person => identity are physical addresses and bank accounts


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 10:06:55 AM
People need to realize that proof of work is a means to an end. A better system is possible if nodes are connected to identities.

It seems to me very unlikely than there will be an establishment of a global identity system which can't be corrupted. You might be able to prove you own a passport, but you can't prove you haven't stolen the passport. There is no key testing. Human markers (fingerprints, eye scan, genetic information) are unique and testable. Other information usually used to create a map person => identity are physical addresses and bank accounts

So take the ID requirement back a step and put the burden of proof on the nodes themselves. How does a node prove to other nodes that it is real and not spoofed?


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 29, 2014, 10:22:32 AM
What structural/functional properties of bitcoin can we use to establish a node is a real node in a trustless and distributed fashion?

I'm not sure Mike is serious about this proposal, although it sounded like it in the talk. He knows that miners/users will never accept this. bitcoin is unlikely to change in so major ways. And if you solve the mapping of identity to computer in new ways you can potentially have better systems than proof of work. there is no need for all nodes doing the same computation N times. going forward nodes is an increasing less useful concept. In the future compute power will not be local, but on some server. So the P2P model is really going away to some extent. bitcoin is now 5 years old, and since then the rise of cheap servers has been probably the most dramatic change. soon "cloud" will be even more ubiquitous, although there are of course many security issues.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 29, 2014, 10:41:52 AM
So take the ID requirement back a step and put the burden of proof on the nodes themselves. How does a node prove to other nodes that it is real and not spoofed?

How do you know your OS is not rooted? perfect backdoors are invisible. its hard to write a rootkit, but as they propagate its impossible to stop them. for example Zeus was a well-known Win rootkit. black hats can earn a lot of money (I assume), so there is the incentive. for the attacker it takes only one exploit, but the defenders have to cover all exploits. its not possible to write programs which defend all possible attacks. there is the idea you could use BTC in connection to compute cycles, but it seems unlikely that is workable in the near term. You can't write programs that prove that other programs are not malicious, which is connected to Turing's halting problem [1].

[1] http://en.wikipedia.org/wiki/Halting_problem


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 10:50:01 AM
So take the ID requirement back a step and put the burden of proof on the nodes themselves. How does a node prove to other nodes that it is real and not spoofed?

How do you know your OS is not rooted? perfect backdoors are invisible. its hard to write a rootkit, but as they propagate its impossible to stop them. for example Zeus was a well-known Win rootkit. black hats can earn a lot of money (I assume), so there is the incentive. for the attacker it takes only one exploit, but the defenders have to cover all exploits. its not possible to write programs which defend all possible attacks. there is the idea you could use BTC in connection to compute cycles, but it seems unlikely that is workable in the near term. You can't write programs that prove that other programs are not malicious, which is connected to Turing's halting problem [1].

[1] http://en.wikipedia.org/wiki/Halting_problem

But this is much like a criticism that Bitcoin doesn't really 'solve' the Byzantine Generals problem. Sure, it doesn't fully satisfy the definition of a 'solution' in a pure mathematical sense, but for all intents and purposes it's 'good enough' to be useful.

You don't have to 'prove' a node is real in a hard sense, just that it's behaving exactly like a real node would (relaying transactions to and from the greater network, not compromised by allowing external observer programs to 'look inside' during runtime) when it's asked to.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 29, 2014, 11:21:12 AM
I'm not sure what problem you're trying to address. botnets are the problem which would be partly solved by such an ID mapping.

I like the idea of using location data, but that is orthogonal to bitcoin/Proof-of-work, which is intertwined with TCP/IP. Although bitcoin could potentially change DNS and SSL through something like BitDNS/Namecoin.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: Mike Hearn on January 29, 2014, 11:59:33 AM
Though don't governments generally have access to lots of foreign passport scans from border crossings, airport, etc.?

That's true, they do. It's like a bigger variant of the hotel attack. So maybe the "reveal country and play geopolitics" wouldn't work well.

I thought of a couple of countermeasures but they decrease convenience a lot. One would be to find a way to do the time-spacing trick, perhaps by committing to a hash of some (derived?) data in the block chain, and then incorporating that and a block hash from N days later into the proof. However in the absence of AA it doesn't work, and most passports don't do AA, so that seems like a dead end.

The second is to have some random/semi/low trusted third party do a match between face and passport photo data (it can be extracted independently from the rest), in such a way that it's clear the owner of the passport is consenting to creating the fresh identity. That way attacks based on just grabbing someones data wouldn't work. Because matching two photos together perhaps with a MySpace style "salute" (write a code on a piece of paper and hold it up to the camera), is very easy, it could be a Mechanical Turk style microwork scheme. There's no need for the face-matching-person to know anything about who they are seeing. Accuracy could be measured and enforced by having other low-trusted third parties do random audits.

But that's very complicated and would take a lot of effort to set up. If Tor strongly suspected it was really being infiltrated by a lot of intelligence agency controlled nodes, it might become worth it. But otherwise I doubt it's worth it.

Note that ZKPOPs have use cases outside "how do we beat the government at sybil attacks". For instance, one reason porn sites hestitate to use Bitcoin is that they use credit cards as a form of age verification. Anonymous age verification, anti-spam systems, helping manage identities in end-to-end encrypted email ... there's lots of places where selectively revealed yet hard-to-forge identities would be useful.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 02:24:09 PM
Though don't governments generally have access to lots of foreign passport scans from border crossings, airport, etc.?

That's true, they do. It's like a bigger variant of the hotel attack. So maybe the "reveal country and play geopolitics" wouldn't work well.

I thought of a couple of countermeasures but they decrease convenience a lot. One would be to find a way to do the time-spacing trick, perhaps by committing to a hash of some (derived?) data in the block chain, and then incorporating that and a block hash from N days later into the proof. However in the absence of AA it doesn't work, and most passports don't do AA, so that seems like a dead end.

The second is to have some random/semi/low trusted third party do a match between face and passport photo data (it can be extracted independently from the rest), in such a way that it's clear the owner of the passport is consenting to creating the fresh identity. That way attacks based on just grabbing someones data wouldn't work. Because matching two photos together perhaps with a MySpace style "salute" (write a code on a piece of paper and hold it up to the camera), is very easy, it could be a Mechanical Turk style microwork scheme. There's no need for the face-matching-person to know anything about who they are seeing. Accuracy could be measured and enforced by having other low-trusted third parties do random audits.

But that's very complicated and would take a lot of effort to set up. If Tor strongly suspected it was really being infiltrated by a lot of intelligence agency controlled nodes, it might become worth it. But otherwise I doubt it's worth it.

Note that ZKPOPs have use cases outside "how do we beat the government at sybil attacks". For instance, one reason porn sites hestitate to use Bitcoin is that they use credit cards as a form of age verification. Anonymous age verification, anti-spam systems, helping manage identities in end-to-end encrypted email ... there's lots of places where selectively revealed yet hard-to-forge identities would be useful.

Time spacing could be achieved at the node-node handover of a block.

N1 isn't known to N2.

N1 --> N2: Here's a block. It has timestamp t0.
N2 waits a random amount of time <1sec.  
N1 <-- N2: Ok, now solve this small puzzle and send me a new timestamp.
N1 --> N2: Here's the solution and timestamp t0+N2_delay+x.

Now, t0+N2_delay+x must be greater than t0 - so the person in control of the node isn't just winding their clock backwards and forwards between problems. The latencies for the connection should also be the same in both directions, to within a narrow margin. Comparing the timestamps tells you how long that node should take to solve a particular puzzle, which can then be used as a reference when asking the same puzzle later. This tells you the physical make-up of the machine hasn't been swapped out and another one is just spoofing the ID.

This map of latencies and 'puzzle-solving-times' acts like a map/proof for other nodes in the network when they now want to talk to N1.

Again, I'm sure there are parts I'm missing, but this would be internal to the protocol itself and not require external tokens, and be fairly easy to bootstrap outwards from a single trusted server.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: coinrevo on January 29, 2014, 02:34:20 PM
NanoAkron, those are things I've thought of, too. but there is no way that such schemes can be implemented in bitcoin itself. The protocol can't change arbitrarily. what you're suggesting is at odds with TCP/IP. TCP/IP deals with unreliable communication over a scale free network (all nodes are equal). bitcoin depends crucially on long block times. Send some packets over random locations over the globe and you will see there will be a lot of statistical variance. Which is the reason why blocks exist (one can imagine geographically distributed blocks). TCP/IP only knows of nodes with IP addresses. You don't know where the node is (exact for datamining through approximation). For example people suggested changing the chain selection rule (GHOST). but all of the elements are carefully balanced, which makes the invention so ingenious.



Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: NanoAkron on January 29, 2014, 04:41:10 PM
NanoAkron, those are things I've thought of, too. but there is no way that such schemes can be implemented in bitcoin itself. The protocol can't change arbitrarily. what you're suggesting is at odds with TCP/IP. TCP/IP deals with unreliable communication over a scale free network (all nodes are equal). bitcoin depends crucially on long block times. Send some packets over random locations over the globe and you will see there will be a lot of statistical variance. Which is the reason why blocks exist (one can imagine geographically distributed blocks). TCP/IP only knows of nodes with IP addresses. You don't know where the node is (exact for datamining through approximation). For example people suggested changing the chain selection rule (GHOST). but all of the elements are carefully balanced, which makes the invention so ingenious.



Hmm…I see.



Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: hashman on January 29, 2014, 04:44:01 PM
Quote
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.
r

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.


Bingo.  Newbie gets it right, news at 11 :)  

You're not solving the sybil problem, it's information theory impossible.  I don't care if you have iris scanners and thumbrints and your nazi papers , information can be copied.  

(seriously,  passports?  

Article 13(2) of the Universal Declaration of Human Rights:

Everyone has the right to leave any country, including his own, and to return to his country. )


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: divine_core on January 30, 2014, 06:31:54 PM
Comparing the timestamps tells you how long that node should take to solve a particular puzzle, which can then be used as a reference when asking the same puzzle later. This tells you the physical make-up of the machine hasn't been swapped out and another one is just spoofing the ID.

What's the point? Anybody running a faster system can just slow it down to pretend to be the old, slower one.


Title: Re: Establishing the Trustworthiness of Nodes without External Tokens (eg Passports)
Post by: hashman on February 05, 2014, 01:17:47 PM

You're not solving the sybil problem, it's information theory impossible.



Well I guess I should retract that statement as these guys seem to have solved the problem:

"There are various means of authenticating Icelanders on the Internet"  auroracoin.org/airdrop.php


Lets see how it goes :)