[Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1658 bytes --]

Subject change to reflect that this is off-topic for the old thread.

Eventually, I think it makes sense to move to a system where you get seeds
> from
> a DNS (or other mechanism), connect to one or a few of the results, do a
> getaddr,
> fill your peer IP database with it, and disconnect from the DNS seeded
> peer.


This obviously makes no difference from a security perspective. If a DNS
seed is compromised it can feed you nodes that just connect you back to the
sybil. If you seed from DNS then that's your root of trust.

The problem with moving away from DNS seeding for bitcoinj clients at least
is that SPV clients are very sensitive to startup time. It isn't OK to
spend two minutes trying to connect to lots of long-dead IP addresses if
you're wanting to pay your bill in a restaurant. That means either you have
to spin up a lot of TCP connections in parallel, which I know from bitter
experience can cause problems with some crappy wifi routers (they think
it's a synflood), or you get a known fresh source of IPs like a DNS seed
response and then later on bring up connections to the P2P network from
that.

Implementing the latter is complicated - you have to partition your nodes
so the seed peers are separated from the peers you found via addr
broadcasts and seeded peers can't pollute your addr-found peers unless it's
your first run.

I've actually not experimented with this for a while. I'm hoping that by
the time this gets to the top of my todo list, network nodes will be stable
enough that actually you can always obtain at least one or two connections
if you try (say) 30 at once. But I have no idea if we're at that stage yet.

[-- Attachment #2: Type: text/html, Size: 2055 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4562 bytes --]

On Mon, May 06, 2013 at 04:58:56PM +0200, Mike Hearn wrote:

More generally, I think this shows clearly how SPV nodes have weaker
security than constantly operating full nodes, which we knew already, so
why not build a better SPV-specific system instead?

I've noticed on my Android phone how it often takes quite awhile to find
a peer that will actually accept an incoming connection, which isn't
surprising really: why should a regular node care about responding to
SPV nodes quickly?

For fast startup you would be better served with dedicated nodes that
are backed by fast hardware and high bandwidth internet connections.
You can discourage non-SPV use by refusing to relay full blocks.

You can have trusted individuals vouch for these special servers with
SSL certificates so you run less of a risk of connecting to a malicious
one trying to limit what information you see. For the initial
implementation, maybe just make a quick SSL accessible service with HTTP
GET so you don't have to integrate SSL into the network protocol and
have a couple of these HTTP GETable servers running. (IE, the trust is
actually that the SPV seed is honest)

Security will be no worse than before - if any one server/seed is honest
you're ok - and hopefully better due to the accountability. Obviously
you can use the existing bootstrap method in parallel at the same time.


What's good about partitioning between SPV and full node bootstrapping,
is the regular DNS seeds can optimize the other way: accept that some
nodes may turn out to be evil, and limit the damage by returning peers
from the widest pool possible even if some of those peers may be a bit
slow and unreliable. An attacker can't dominate the results by running a
small number of fast reliable nodes because the results returned comes
from a huge pool, so they are stuck with getting access to lots of IP
addresses, and maybe in the future we'll have even better methods of
resisting sybil attacks, and we will be able to implement those methods
even if they mean initial bootstrapping is slower.

> Subject change to reflect that this is off-topic for the old thread.
> 
> Eventually, I think it makes sense to move to a system where you get seeds
> > from
> > a DNS (or other mechanism), connect to one or a few of the results, do a
> > getaddr,
> > fill your peer IP database with it, and disconnect from the DNS seeded
> > peer.
> 
> 
> This obviously makes no difference from a security perspective. If a DNS
> seed is compromised it can feed you nodes that just connect you back to the
> sybil. If you seed from DNS then that's your root of trust.
> 
> The problem with moving away from DNS seeding for bitcoinj clients at least
> is that SPV clients are very sensitive to startup time. It isn't OK to
> spend two minutes trying to connect to lots of long-dead IP addresses if
> you're wanting to pay your bill in a restaurant. That means either you have
> to spin up a lot of TCP connections in parallel, which I know from bitter
> experience can cause problems with some crappy wifi routers (they think
> it's a synflood), or you get a known fresh source of IPs like a DNS seed
> response and then later on bring up connections to the P2P network from
> that.
> 
> Implementing the latter is complicated - you have to partition your nodes
> so the seed peers are separated from the peers you found via addr
> broadcasts and seeded peers can't pollute your addr-found peers unless it's
> your first run.
> 
> I've actually not experimented with this for a while. I'm hoping that by
> the time this gets to the top of my todo list, network nodes will be stable
> enough that actually you can always obtain at least one or two connections
> if you try (say) 30 at once. But I have no idea if we're at that stage yet.

> ------------------------------------------------------------------------------
> Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
> Get 100% visibility into your production application - at no cost.
> Code-level diagnostics for performance bottlenecks with <2% overhead
> Download for free and get started troubleshooting in minutes.
> http://p.sf.net/sfu/appdyn_d2d_ap1

> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


-- 
'peter'[:-1]@petertodd.org
000000000000002a871dc011fe28fd8fbffe577c02b91d2de09aeca8216644ef

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Jeff Garzik]

On Mon, May 6, 2013 at 12:12 PM, Peter Todd <pete@petertodd.org> wrote:
> I've noticed on my Android phone how it often takes quite awhile to find
> a peer that will actually accept an incoming connection, which isn't
> surprising really: why should a regular node care about responding to
> SPV nodes quickly?
>
> For fast startup you would be better served with dedicated nodes that
> are backed by fast hardware and high bandwidth internet connections.
> You can discourage non-SPV use by refusing to relay full blocks.
>
> You can have trusted individuals vouch for these special servers with
> SSL certificates so you run less of a risk of connecting to a malicious
> one trying to limit what information you see. For the initial
> implementation, maybe just make a quick SSL accessible service with HTTP
> GET so you don't have to integrate SSL into the network protocol and
> have a couple of these HTTP GETable servers running. (IE, the trust is
> actually that the SPV seed is honest)
>
> Security will be no worse than before - if any one server/seed is honest
> you're ok - and hopefully better due to the accountability. Obviously

Indeed, the DNS seeds are just servers run by trusted individuals anyway.

In either case, bitcoinj definitely wants fixing for its over-reliance
on DNS seeds.  This has been noted as a problem for a while.

-- 
Jeff Garzik
exMULTI, Inc.
jgarzik@exmulti.com

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Mike Hearn]

> > I've noticed on my Android phone how it often takes quite awhile to find
> > a peer that will actually accept an incoming connection, which isn't
> > surprising really: why should a regular node care about responding to
> > SPV nodes quickly?

I haven't seen that - remote nodes don't have any special code that
knows what kind of client is connecting, so if you're seeing delays I
suspect the issue is elsewhere. For example a seed that is serving
peers which are overloaded, or the general delays inherent to bringing
up a 3G data link from idle (this can take many seconds all by
itself).

I took out Jeffs seed a few weeks ago in git master because it was
often serving nodes that were full, so that should speed things up a
bit. The other seeds all run dynamic crawlers.

There are lots other ways to optimise performance beyond having fresh
seeds, for example, the Android app can (and probably will in future)
support putting Bluetooth MAC addresses in the URLs it serves via
QRcode/NFC. We prototyped it before but didn't finish. That means that
the sending side can provide the receiving side with a transaction via
a local Bluetooth socket, which eliminates the need to wait for P2P
bringup on the send side. In a typical merchant scenario the receive
side is more likely to have WiFi access and is more likely to be
talking to the network frequently, so its list of IPs gathered from
addr packets would be fresher, and it can do P2P bringup whilst the
user is confirming/signing/uploading on the sending side. Overlapping
the two buys precious seconds.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1613 bytes --]

On Mon, May 06, 2013 at 12:20:12PM -0400, Jeff Garzik wrote:
> > Security will be no worse than before - if any one server/seed is honest
> > you're ok - and hopefully better due to the accountability. Obviously
> 
> Indeed, the DNS seeds are just servers run by trusted individuals anyway.

Yup, and lets be really clear here: what I'm saying about existing DNS
seeds selecting peers from a wider pool isn't to fundementally reduce
the trust in those seeds, it's to reduce the amount of effort the people
*running* the seeds need to expend to return safe results.

> In either case, bitcoinj definitely wants fixing for its over-reliance
> on DNS seeds.  This has been noted as a problem for a while.

Anyway, DNS returns unsigned data usually - DNSSEC is not widely
implemented - so at least an alternative seed system with SSL certs
could provide a way of getting results from the seed to you in the first
place with a different set of vulnerabilities.  (I'm not going to say
it's really more secure - your ISP can MITM your connections to those
remote nodes anyway - but the types of attacks are at least different)

Speaking of, off-topic for this discussion, but in the future
node-to-node communicate should be encrypted and signed, and seeds
should have a mechanism to return the pubkey the node will use for
communication. This would protect against your ISP MITM attacking your
communications with every node. Of course, Tor hidden service nodes do
this already essentially.

-- 
'peter'[:-1]@petertodd.org
000000000000001882c602178bd4dc6501ecd65db1e1380224be98c923043c07

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Mike Hearn]

> Speaking of, off-topic for this discussion, but in the future
> node-to-node communicate should be encrypted and signed

Yes, I'd like to do this. The threat isn't really ISPs which are
mostly trustable (the worst they normally do outside of places like
China is dick about with ads), the big threat is people who use
untrusted WiFi without realising and end up thinking they received
money when actually they were just connected to a hotspot running in
the attackers pocket. I'm rather expecting that kind of thing to
happen in future.

I think we can converge on the best solution with several iterations:

Iteration 1) Make it clear in the UI that if the phone is connected to
WiFi, payments from untrusted people should not be accepted. Currently
the Android app merely says the money won't be spendable for a few
minutes. It needs to communicate the "may not exist" aspect more
clearly. If you're connected via a cell tower, the existing wording is
fine - it's very unlikely your telco is trying to scam you in a
person-to-person transaction, traffic is encrypted and 3G+ connections
authenticate the network so you can't be MITMd except by your telco.
Assuming you have a good list of IPs, of course.

Iteration 2) Give nodes keys that appear in addr broadcasts and seed
data (whether it be via https or otherwise), and have each node keep a
running hash of all messages sent on a connection so far. Add a new
protocol message that asks the node to sign the current accumulated
hash. Not all messages really need to be signed, eg asking for
signatures of blocks is sort of pointless at high difficulty levels
because the structures are self proving and a simple watchdog timer
that looks for unusually slow progress is probably enough. If the
client keeps the same accumulated hash then when you encounter
something you care about the accuracy of, you can ask for a signature
over all traffic so far.

Iteration 3) Do something about end to end encryption, just delegate
everything to Tor, or find some other way to obfuscate the origin of a
transaction (a mini onion network for example).

Last time I looked, Tor wasn't really usable in library form and
connecting to hidden services is really slow. So it'd be an issue to
just re-use it out of the box, I think.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2779 bytes --]

On Mon, May 06, 2013 at 06:47:22PM +0200, Mike Hearn wrote:
> Iteration 1) Make it clear in the UI that if the phone is connected to
> WiFi, payments from untrusted people should not be accepted. Currently
> the Android app merely says the money won't be spendable for a few
> minutes. It needs to communicate the "may not exist" aspect more
> clearly. If you're connected via a cell tower, the existing wording is
> fine - it's very unlikely your telco is trying to scam you in a
> person-to-person transaction, traffic is encrypted and 3G+ connections
> authenticate the network so you can't be MITMd except by your telco.
> Assuming you have a good list of IPs, of course.

You mean scam you with a zero-conf transaction that hasn't actually been
broadcast?

You know how I feel about zero-conf.

> Iteration 2) Give nodes keys that appear in addr broadcasts and seed
> data (whether it be via https or otherwise), and have each node keep a
> running hash of all messages sent on a connection so far. Add a new
> protocol message that asks the node to sign the current accumulated
> hash. Not all messages really need to be signed, eg asking for
> signatures of blocks is sort of pointless at high difficulty levels
> because the structures are self proving and a simple watchdog timer
> that looks for unusually slow progress is probably enough. If the
> client keeps the same accumulated hash then when you encounter
> something you care about the accuracy of, you can ask for a signature
> over all traffic so far.

We already depend on OpenSSL, why not just use standard SSL?

Define a per-node compressed pubkey to pass around, and then do whatever
is easiest to get the actual SSL up and running. If we have to use that
pubkey to in-turn sign for a secondary RSA key or whatever due to
compatibility, no big deal.

Define a new service bit SSL and if you connect to a SSL supporting node
switch to SSL within the same TCP connection.

> Iteration 3) Do something about end to end encryption, just delegate
> everything to Tor, or find some other way to obfuscate the origin of a
> transaction (a mini onion network for example).

Obfusication probably isn't the hard part, it's SPV bloom filter privacy
that is the tough one, but probably a problem better handled by Tor.

> Last time I looked, Tor wasn't really usable in library form and
> connecting to hidden services is really slow. So it'd be an issue to
> just re-use it out of the box, I think.

For phone stuff you should work with The Guardian Project - they've
implemented Tor on Android among other things and want to find easier
ways for apps to use it.

-- 
'peter'[:-1]@petertodd.org
000000000000014671272e3a4dd966bb56d4a9a27751b5cd4dc75dc931660cb5

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Jeff Garzik]

On Mon, May 6, 2013 at 1:19 PM, Peter Todd <pete@petertodd.org> wrote:
> For phone stuff you should work with The Guardian Project - they've
> implemented Tor on Android among other things and want to find easier
> ways for apps to use it.

You know my feelings about Java ;p but for hidden services, there
really does need to be a lib for server apps.

A proxy server approach is much more fragile, in certain scenarios,
than directly implementing an internal Tor hidden service node, and
handling the TLS connections within your own network framework.

-- 
Jeff Garzik
exMULTI, Inc.
jgarzik@exmulti.com

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Gregory Maxwell]

On Mon, May 6, 2013 at 10:19 AM, Peter Todd <pete@petertodd.org> wrote:
>> running hash of all messages sent on a connection so far. Add a new
>> protocol message that asks the node to sign the current accumulated
>> hash.
> We already depend on OpenSSL, why not just use standard SSL?

SSL doesn't actually provide non-repudiation. We actually want
non-repudiation. I want to be able to prove to others that some node
deceived me.

(there are a number of other arguments I could make against SSL, but
that one is probably sufficient— or rather, it's an argument that we
should have some way of cheaply getting non-reputable signatures
regardless of the transport)

>> Last time I looked, Tor wasn't really usable in library form and
>> connecting to hidden services is really slow. So it'd be an issue to
>> just re-use it out of the box, I think.
> For phone stuff you should work with The Guardian Project - they've
> implemented Tor on Android among other things and want to find easier
> ways for apps to use it.

Also look into torchat, which bundles a special tor build and runs a
hidden service.

Because of services like Blockchain.info attacking the casual privacy
users not using their webwallet service I've been thinking that even
for clients that don't normally use tor their own transaction
announcements should probably be made by bringing up a connection over
tor and announcing. But thats another matter...

I've switched to running on tor exclusively for my personal node (yay
dogfooding) and I've found it to connect and sync up very fast most of
the time. The biggest slowdown appears to be the our timeout on the
tor connections is very high and so if it gets unlucky on the first
couple attempts it can be minutes before it gets a connection. We're
short on onion peers and I sometimes get inbound connections before I
manage to get an outbound.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2023 bytes --]

On Mon, May 06, 2013 at 10:42:19AM -0700, Gregory Maxwell wrote:
> On Mon, May 6, 2013 at 10:19 AM, Peter Todd <pete@petertodd.org> wrote:
> >> running hash of all messages sent on a connection so far. Add a new
> >> protocol message that asks the node to sign the current accumulated
> >> hash.
> > We already depend on OpenSSL, why not just use standard SSL?
> 
> SSL doesn't actually provide non-repudiation. We actually want
> non-repudiation. I want to be able to prove to others that some node
> deceived me.

We don't have non-repudiation now, why make that a requirement for the
first version? Adding non-repudiation is something that has to happen at
the Bitcoin protocol level,(1) so it's orthogonal to using SSL to make sure
you're connection isn't being tampered with and is encrypted.

1) Non-repudiation is only useful with fraud proofs, and they will have
to be thought out for everything the node might claim.

> (there are a number of other arguments I could make against SSL, but
> that one is probably sufficient— or rather, it's an argument that we
> should have some way of cheaply getting non-reputable signatures
> regardless of the transport)

Exactly. Implement an SSL-protected transport, and leave non-repudiation
and broader issues of node identity as a later, long-term project. Many
client won't even want to support all that complexity, but they'll still
want to cheaply get the advantages SSL has with regard to MITM
resistance and privacy with little effort.

Anyway, the concept of a per-node identity keypair is the first step
towards non-repudiation, and implementing SSL transport.

> couple attempts it can be minutes before it gets a connection. We're
> short on onion peers and I sometimes get inbound connections before I

I run a fast node on EC2 that only accepts inbound connections over Tor
and I regularly have about ~50 inbound peers.

-- 
'peter'[:-1]@petertodd.org
0000000000000042d8b5bc3ca04847f711b82b66f08b7360a565ebd0b131621c

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Gregory Maxwell]

On Mon, May 6, 2013 at 10:53 AM, Peter Todd <pete@petertodd.org> wrote:
> We don't have non-repudiation now, why make that a requirement for the
> first version? Adding non-repudiation is something that has to happen at
> the Bitcoin protocol level,(1) so it's orthogonal to using SSL to make sure
> you're connection isn't being tampered with and is encrypted.

Because if you just want bitcoin p2p over SSL... just start up stunnel
on another port. Done. You've still solved nothing about the problem
of discovery issue.

> 1) Non-repudiation is only useful with fraud proofs, and they will have
> to be thought out for everything the node might claim.

That isn't so. If a node is reliably rogue I can go manually gather
evidence and people can manually take action against it.  Consider the
DNSseeds, right now fraud proofs really wouldn't matter— the limited
amount of trust put in those things is based not on "oh no, nodes will
ignore you in the future if you're bad", it's based on the ability of
misconduct to sully the operator's reputation.

But without non-repudiation the ability to tie reputation to good
behavior is fairly limited especially if they perform targeted
attacks. "Wasn't me"

Instead— I'd argue that non-repudiation is always useful when there is
trust. It's things like fidelity bonds— a trust generator that depend
on automatic enforcement— that are only useful with fraud proofs.

> Anyway, the concept of a per-node identity keypair is the first step
> towards non-repudiation, and implementing SSL transport.

Yea, indeed, per-node keys are useful for a bunch of things. Care is
needed to avoid problems like deanonymizing use over tor with them.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3459 bytes --]

On Mon, May 06, 2013 at 11:01:22AM -0700, Gregory Maxwell wrote:
> On Mon, May 6, 2013 at 10:53 AM, Peter Todd <pete@petertodd.org> wrote:
> > We don't have non-repudiation now, why make that a requirement for the
> > first version? Adding non-repudiation is something that has to happen at
> > the Bitcoin protocol level,(1) so it's orthogonal to using SSL to make sure
> > you're connection isn't being tampered with and is encrypted.
> 
> Because if you just want bitcoin p2p over SSL... just start up stunnel
> on another port. Done. You've still solved nothing about the problem
> of discovery issue.

stunnel only works if both sides support it.

re: discovery, the whole reason I brought up SSL was the idea that a
seed whome you have a secure connection to, like HTTPS or SSL, can
include the peer pubkey along with the peer's IP address, allowing you
to be sure you've connected to the peer the seed is giving you rather
than some other imposter.

Equally it'll let you be sure you've connected to the correct peer the
second time.

For applications where you *don't* need non-repudiation SSL is already
implemented and solves the secure peer communication issue, including
encryption, in an efficient way without requiring a lot of code
complexity to implement.

SSL could be implemented as a Google Summar of Code project by an
average developer, and importantly re-implemented by all the alt-clients
out there with relatively little work.

It may even be the case that some usage scenarios do find the CA system
useful. I might want to do -addnode ssl://petertodd.org on my Android
wallet to be sure I've connected to my Bitcoin node rather than some
MITM ISP imposter. I already have a SSL cert from a CA for petertodd.org
that I can use and my Android phone already has a list of CA's I can put
a reasonable amount of trust in.

> > 1) Non-repudiation is only useful with fraud proofs, and they will have
> > to be thought out for everything the node might claim.
> 
> That isn't so. If a node is reliably rogue I can go manually gather
> evidence and people can manually take action against it.  Consider the
> DNSseeds, right now fraud proofs really wouldn't matter— the limited
> amount of trust put in those things is based not on "oh no, nodes will
> ignore you in the future if you're bad", it's based on the ability of
> misconduct to sully the operator's reputation.

Sure, but how will non-repudiation be implemented? By having the node
sign the messages they send with their pubkey, and as Mike suggests
likely doing so in some sort of chained hash or preferably merkle
mountain range to allow for constructing proofs over multiple messages.

That has nothing to do with encrypting the transport, and will always be
a lot slower than SSL's symmetric cipher for when you don't need
non-repudiation but do want to be sure you've connected to the right
node.

> > Anyway, the concept of a per-node identity keypair is the first step
> > towards non-repudiation, and implementing SSL transport.
> 
> Yea, indeed, per-node keys are useful for a bunch of things. Care is
> needed to avoid problems like deanonymizing use over tor with them.

Per-node keys really need to be per listening address by default. In
fact, I'd argue for creating new keys on startup by default.

-- 
'peter'[:-1]@petertodd.org
000000000000015ef6fc2fc45adc1de0c344e99a59453bb09ac470a1d02b787d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Adam Back]

btw with nodes for transport security you might use self-certifying keys. 
Referring to Zooko's triangle, then the key is the node identity.  Similar
to a bitcion address.  So then just another ECDSA key and use emphemeral
ECDH for transport authenticated with the nodes key.

Maybe there can be some value to reputation to a node - eg it can charge a
higher micropayment for its p2p network services, a node with a good
reptuation could charge a higher micropayment for relaying (though bitcoin
itself probably doesnt like micropayments as bloating the transaction log).

Another ZKS era idea I had was to have a gossip protocol for users to find
out what other people think about the trustworthiness and reliability of
nodes.  If that info is distributed via gossip over multiple channels and
network connections over time, and kept in something like a gnutella host
cache (just a cache of random info with some eg random replacement policy)
it becomes very hard for a dishonest node to censor evidence of its low
reputation.

It is best as Gregory said to be able to directly prove, and punish by
block-chain validation, because that is more smart-contract like.  Bisbehave
and nodes wont connect to you or lose somehow.

But what exactly could you prove about a node?  You dont really know if a
node is an originator for a double spend, it could be relay.  And for
privacy and security you cant expect the node to use its coin address
private key.

Hmm: maybe one could use a Brands private credential with offline double
spend detection, with the reputation but not coin address of the node
disclosed, and the nodes coin address embedded in the proof.  Each node
could be is own CA, providing a ZKP.  If the node ever double spends a coin,
it loses its reputation as the coin address is revealed.

btw another old idea was to require proof of the existance of the private
key of a high value coin in the double-spend revealed information.  Then
basically to get a higher good-behaviour bond, the node ties up more coins,
and if a node cheats, the first person to discover this collects the
forfeited good behaviour bond.

Adam

ps I have an opensource openSSL based Brands (& Chaum) credential library at
http://www.cypherspace.org/credlb/ I didnt actually implement the ECDL
version, just the DL version, but that is not so hard, and its on my todo
list.  (There is also a strong RSA assumption version, also not
implemented).

On Mon, May 06, 2013 at 11:01:22AM -0700, Gregory Maxwell wrote:
>> 1) Non-repudiation is only useful with fraud proofs, and they will have
>> to be thought out for everything the node might claim.
>
>That isn't so. If a node is reliably rogue I can go manually gather
>evidence and people can manually take action against it.  Consider the
>DNSseeds, right now fraud proofs really wouldn't matter— the limited
>amount of trust put in those things is based not on "oh no, nodes will
>ignore you in the future if you're bad", it's based on the ability of
>misconduct to sully the operator's reputation.
>
>But without non-repudiation the ability to tie reputation to good
>behavior is fairly limited especially if they perform targeted
>attacks. "Wasn't me"
>
>Instead— I'd argue that non-repudiation is always useful when there is
>trust. It's things like fidelity bonds— a trust generator that depend
>on automatic enforcement— that are only useful with fraud proofs.
>
>> Anyway, the concept of a per-node identity keypair is the first step
>> towards non-repudiation, and implementing SSL transport.
>
>Yea, indeed, per-node keys are useful for a bunch of things. Care is
>needed to avoid problems like deanonymizing use over tor with them.
>
>------------------------------------------------------------------------------
>Learn Graph Databases - Download FREE O'Reilly Book
>"Graph Databases" is the definitive new guide to graph databases and
>their applications. This 200-page book is written by three acclaimed
>leaders in the field. The early access version is available now.
>Download your free book today! http://p.sf.net/sfu/neotech_d2d_may
>_______________________________________________
>Bitcoin-development mailing list
>Bitcoin-development@lists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3248 bytes --]

On Mon, May 06, 2013 at 08:32:22PM +0200, Adam Back wrote:
> But what exactly could you prove about a node?  You dont really know if a
> node is an originator for a double spend, it could be relay.  And for
> privacy and security you cant expect the node to use its coin address
> private key.

re: double-spends - punishing relay nodes and miners for them is a very
bad idea. Ultimately it is the blockchain by which Bitcoin comes to
consensus about what transactions belong in the blockchain - to punish
double-spends implies a second consensus mechanism. Anyway it's
unnecessary: you can hold the actual spender accountable for
double-spends and punish them directly rather than adding a lot of
complexity and dangerous assumptions about propagation to the Bitcoin
core network.


Some useful things you can hold relay nodes accountable for without a
lot of complexity:

1) Having a reasonably correct view of the best block. Make the node
sign a statement including a block hash sequence (the last 3-6 blocks)
and what it believes the current time is.

2) Accurate knowledge of the blockchain. Sign a statement claiming that
what block hash is for a given chain height. Note that due to reg-orgs
this is actually a different statement than #1 and nodes should be
careful what they are claiming.

3) Accurate knowledge of the UTXO set. Sign a statement claiming that
a given txid:vout for the current best block hash is in or not in the
UTXO set.

4) Accurate bloom filtering; same idea as #3

5) Make the node identity expensive to obtain. For instance, construct
PoW's including the node pubkey somehow, or purchase fidelity bonds for
the node's identity. Makes sybil attacks more difficult, among other
things.

5) Provide useful propagation/mining services. Sign a txid and
timestamp/blockhash-sequence, and hold the node accountable for how long
it takes the txid to make it into the blockchain. Useful especially for
miners offering the service of mining your transaction.


> Hmm: maybe one could use a Brands private credential with offline double
> spend detection, with the reputation but not coin address of the node
> disclosed, and the nodes coin address embedded in the proof.  Each node
> could be is own CA, providing a ZKP.  If the node ever double spends a coin,
> it loses its reputation as the coin address is revealed.

Be careful not to mix up the concept of a relay node with someone
posessing Bitcoins. Node's don't spend coins, people/wallets do.

> ps I have an opensource openSSL based Brands (& Chaum) credential library at
> http://www.cypherspace.org/credlb/ I didnt actually implement the ECDL
> version, just the DL version, but that is not so hard, and its on my todo
> list.  (There is also a strong RSA assumption version, also not
> implemented).

That stuff is cool, but we should focus first on simple efforts, like
SSL transport, that do not require complex cryptography to obtain an
improvement in security.

Of course, not to say long-term research is bad, but that's just not
going into the Bitcoin reference client in the near future.

-- 
'peter'[:-1]@petertodd.org
0000000000000124d42390b0db4c125f6be87835c49dc88f1bdeba527b77abc2

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Adam Back]

On Mon, May 06, 2013 at 03:08:57PM -0400, Peter Todd wrote:
>> Hmm: maybe one could use a Brands private credential with offline double
>> spend detection, with the reputation but not coin address of the node
>> disclosed, and the nodes coin address embedded in the proof.  Each node
>> could be is own CA, providing a ZKP.  If the node ever double spends a coin,
>> it loses its reputation as the coin address is revealed.
>
>Be careful not to mix up the concept of a relay node with someone
>posessing Bitcoins. Node's don't spend coins, people/wallets do.

My comment was to say that a good behaviour bond for a relay node could be
put on an address that is defined as unspendable until such time as an
auditor can prove the node engaged in the undesired behaviour, at which
point the audit receives the payment as part of his proof.  Or until the
node ceases to operate.  Its a smart contract.

However I added to that, that it is still possible to do that while
preseving privacy, to point out that it is technically possible, for people
to be aware of in their mental toolbox, if it helps solve an otherwise
tricky problem.

So that would be a privacy preserving smart contract, the parties are
unknown, and unknowable (with unconditional security even), but still the
smart contract executes.  In some sense a privacy preserving smart-contract
is closer to the real point of Szabo's smart-contract idea because you cant
try to renege on the contract in a conventional court - because you cant
identify your counter-party.  Bitcoins privacy feature is fairly weak so
that is probably often not true.

Of course you'd probably need zerocoin to stand much chance of proving an
address private key of an unlinked coin was in the double-spend disclosed
attribute in the first place, and as we know zerocoin is not that efficient.

> Make the node identity expensive to obtain. For instance, construct PoW's
> including the node pubkey somehow,

that could be easily done with the work of creating a vanity address.  eg
address containing many leading 0s.

Adam

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2952 bytes --]

On Mon, May 06, 2013 at 09:50:03PM +0200, Adam Back wrote:
> Of course you'd probably need zerocoin to stand much chance of proving an
> address private key of an unlinked coin was in the double-spend disclosed
> attribute in the first place, and as we know zerocoin is not that efficient.

Sounds like a lot of research potential with many far off possiblities. :)

> >Make the node identity expensive to obtain. For instance, construct PoW's
> >including the node pubkey somehow,
> 
> that could be easily done with the work of creating a vanity address.  eg
> address containing many leading 0s.

Bitcoin is interesting because it provides a nice way to determine the
value of a proof-of-work. Lets suppose you have a digest D and want to
create a proof of work for that digest.

1) Select a block B1 that is reasonably deep in the blockchain. (You
don't want it getting re-orged out of existence) Six blocks deep is
probably plenty.

2) Construct an invalid block header, BP, with SHA256(B1 | D) as the
previous block hash. All other fields can be set to whatever is required
by your hashing unit. (the merkle root would be an option too, but many
hashing setups can't put arbitrary data into it)

3) Hash until you have found the PoW with the difficulty you want.

4) Timestamp BP in the blockchain, resulting in a merkle path M leading to
a subsequent block B2. (1)


Now determining the value of D has a nice compact proof: B1, BP and M
and B2. Taking the minimum of the difficulties of B1 and B2 (in case
they cross a retarget boundry; don't want to create strange incentives)
determine the expected return in Bitcoins from the block reward had the
hasher solved valid blocks instead and you can determine exactly how
much the proof-of-work was worth, kinda...

Things get a bit complex from here on. First of all there isn't a
compact proof that will tell you how much the fees of solving that block
would have been worth, and there can't be because miners can easily
manipulate the apparent fees of a block in both directions.

Also as with fidelity bonds (https://en.bitcoin.it/wiki/Fidelity_bonds)
the question of which value to use, historic or current, is important
too. If you use the Bitcoin face value increases or decreases of the
value of a Bitcoin are arguably distorting. On the other hand, if you
use historical exchange rates, which currency do you use and where do
you get trustworthy historical exchange rate data? (2)


1) See https://github.com/opentimestamps

2) Which reminds me, I do need to get around to bugging Mt. Gox to PGP
sign their exchange rate data and timestamp it properly, or do one or
both myself. It should be archived at archive.org or something too,
heck, the blockchain should be too, although timestamping that will
require a bit more work...

-- 
'peter'[:-1]@petertodd.org
0000000000000190ee1bf5262b2557eb69b49d0e14e1d644ec44a8488f7f5181

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1749 bytes --]

On Mon, May 06, 2013 at 04:43:07PM -0400, Peter Todd wrote:
> Now determining the value of D has a nice compact proof: B1, BP and M
> and B2. Taking the minimum of the difficulties of B1 and B2 (in case
> they cross a retarget boundry; don't want to create strange incentives)
> determine the expected return in Bitcoins from the block reward had the
> hasher solved valid blocks instead and you can determine exactly how
> much the proof-of-work was worth, kinda...

One last thought... suppose you want to make these proof-of-works
transferable on the blockchain, as is easily possible with
announce/commit fidelity bond sacrifices. The problem is of course
re-use - you don't want it to be possible to use the same proof-of-work
for a different asset.

So for D use the txid:vout pair of a txout that you can spend, then
spend it to some output to create the start of the smartcoin/contract
asset chain. The txout can only be spent once, so the PoW is inherently
non-reusable.

The final proof is a more compact than a fidelity bond proof, just the
PoW block and a single transaction and existence proof rather than two
or three. (announce, commit, and commit txin if sacrifice is via fees)


Unfortunately PoW schemes do mean you are actually taking away from the
overall security of the network, and if there was a lot of demand for
these things it will lead to the undesirable effect of making it easy to
rent hashing power. Botnet owners will be happy to have a task that
requires even less communication than Bitcoin itself. Finally the
varience inherent in them is annoying too. But it's an interesting idea.

-- 
'peter'[:-1]@petertodd.org
00000000000001358eaf811792b28798a04103b2e47aecf54268736514defd2f

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Mike Hearn]

> You mean scam you with a zero-conf transaction that hasn't actually been
> broadcast?

Yeah. Or just scam you at all. It's hard to imagine an organisation as
a big as a mobile carrier engaging in financial scamming (roaming fees
excepted).

I've said this before, but I think it's worth repeating. The
double-spend protection the block chain gives you has a sweet spot
where it's really, really valuable (essential even) and then there are
lots of kinds of transactions on either side of that sweet spot that
don't really benefit from it.

Obvious/trivial case where you don't need a block chain - Facebook
buys Instagram for a gajillion coins. The legal system is plenty good
enough to ensure the payments are honoured. Another example, when my
employer pays me my salary. They aren't going to double spend this
except through some horrible accident that we can get sorted out some
other way.

Another case, very small payments. This is Satoshi's bag of crisps
example. If the cost/complexity of double spending is higher than what
the payment is worth, again, you don't really need the block chain.
That's why it's worth optimising unconfirmed transactions to be harder
to double spend, it optimises (pushes up) that lower bar.

Place where you really want the chain - largeish sums of money are
moving around, but not large enough to justify expensive
cross-jurisdictional legal action, or where the cost of identity
verification and all the associated paperwork is just too high. I
guess most online transactions fall into this bucket today.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[John Dillon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> > You mean scam you with a zero-conf transaction that hasn't actually been
> > broadcast?
>
> Yeah. Or just scam you at all. It's hard to imagine an organisation as
> a big as a mobile carrier engaging in financial scamming (roaming fees
> excepted).

Unless the government told them too.

> I've said this before, but I think it's worth repeating. The
> double-spend protection the block chain gives you has a sweet spot
> where it's really, really valuable (essential even) and then there are
> lots of kinds of transactions on either side of that sweet spot that
> don't really benefit from it.
>
> Obvious/trivial case where you don't need a block chain - Facebook
> buys Instagram for a gajillion coins. The legal system is plenty good
> enough to ensure the payments are honoured. Another example, when my
> employer pays me my salary. They aren't going to double spend this
> except through some horrible accident that we can get sorted out some
> other way.

The employer example actually shows something important: between a worker and
an employer double-spending already irrelevant. People get paid after they work
their two weeks not before, so the double-spend is already irrelevant.

However when your employer pays you on the blockchain until the transaction
confirms for someone else to accept funds from that payment they not only have
to trust you, but also the employer. Sure they could take it as "you said you
would apy me so it is your responsibility to make that happen" but that brings
a whole new level of complexity.

A scheme where you vouch for your payments with your identity can benifit from
being able to follow that chain all the way back to the last confirmed
transaction, although actually implementing this may be too complex to be
worthwhile, especially initially.

> Another case, very small payments. This is Satoshi's bag of crisps
> example. If the cost/complexity of double spending is higher than what
> the payment is worth, again, you don't really need the block chain.
> That's why it's worth optimising unconfirmed transactions to be harder
> to double spend, it optimises (pushes up) that lower bar.

Yes. But the issue is how are you going to optmize it? By adding yet more
restrictions and limitations on those who chose to run a node or mining
operation, or by actually fixing the trust issue? We know you can do the
latter, so do not sacrifice Bitcoin's core layer in silly attempts to make
double-spends harder. Fundementally Bitcoin has exactly one way of achieving
consensus, and that is the blockchain.

It must be your right to chose what transactins you chose to mine and chose to
relay. End of story. Bitcoin is not about imposing regulation on those who
choose to use it.

> Place where you really want the chain - largeish sums of money are
> moving around, but not large enough to justify expensive
> cross-jurisdictional legal action, or where the cost of identity
> verification and all the associated paperwork is just too high. I
> guess most online transactions fall into this bucket today.

Indeed. Especially for the most popular use of Bitcoin as a payment system:
buying things PayPal won't let you. In that circumstance the only leverage you
have is the protections of the blockchain and the damage you can do to the
other (often anonymous) parties reputation.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJRivRcAAoJEEWCsU4mNhiPoJcIAL7T/x5gipsCNn/w3EfhZhKo
iukP0Kc3cni/Kb6gJrOlXufIxDrX8QxEhbIIrypFbyg+xHPK8NzSd13ScKNtLgjM
w2uOI/IkgUh7VLIEZADqLO3TM5S5VDZ/A42yzTIq8MeWxaTBD1JulOc/RbljGu8V
UrF6ptxu2UXTc0eXcor1lHfJRVteTJAAba5Awa1EAHX8f2c/1FhdrnOZwfLVJIfK
/nnUgqGKc8l08knC6NnAlP39zbk/FHiZF/keWIFIzhiyXTnqKnqD096tIx6MpPci
LGafjCoXACpr1XeiSufER/z6WxTvOvCbWRw4MYrbyRkmChqMtc8a7RMEPLXhaMQ=
=Oh/p
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Adam Back]

Bitcoin p2p seeding requirements hav some ToR similarities, and we went
through the same security considerations with Zero-Knowledge systems freedom
network.  Though bitcoins attacker profile and motivation is different - so
the defense maybe even more demanding.  At least you have no shortage of
nodes and perhaps merchant interest and general good-will to lean on.

At ZKS I proposed we should fix the exit node issue (exit sees where you go
often in the clear) with an apache mod so the freedom aip tunnel (ToR tunnel
equiv) could terminate right on the web site.  (ZKS freedom network is long
dead but some of the ideas I think made it into ToR, eg I hope my end2end
forward anonymity idea that is implemented in Zach Brown's cebolla.)

Anyway I'd have about DNS being of limited value: bitcoins primary
vulnerability IMO (so far) is network attacks to induce network splits,
local lower difficulty to a point that a local and artificially isolated
area of the network can be fooled into accepting an orphan branch as the
one-true block chain, maybe even from node first install time.

(btw I notice most of the binaries and tar balls are not signed, nor served
from SSL - at least for linux).

Therefore as it applies to discover, you want to be able to discover peers
through as many network routes, and even steganographic protocols as
possible.  eg if a popular web server (say apache, or an apache module) put
a steganographic peer discover relay from its own network area, even for a
small bitcoin fee, that would help a lot.  (Steganographic in the SSL sense
would just mean that the peer seed request to /btcseed.cgi would not be
distinguishable to someone highly sophisticated on the inside of the router
all the peers traffic is routed through.  Eg you could easily do this with a
special magic header that overwrites something else or deletes some
unnecessary header so that the request at least is a standard size, and pad
the response to the same size as the site index.html or whatever).  If the
user picks a few SSL sites and cross checks (more for high value) a subset
of peers available on all and uses them as his seed that seems like a better
direction.

In that way an attacker cant control the network without denying service to
popular SSL sites, which would be a warning sign to users, or having at his
disposal a SSL sub-CA cert (like happened with diginotar and gmail).  You
may be able to pin CAs for popular sites.  Obviously to the extent you're
using SSL you want to generally use EDH for forward-secrecy.  And not RC4 :)

Probably anysite that accepts bitcoin payment will be happy to run such a
mod-bitcoin.


With ToR, it has a similar bootstrap problem to bitcoin.  So while that may
help it is also passing the buck, not necessarily solving the problem.  And
as I said I think its possible bitcoin has a higher assurance need in that
the attackers motivated my $$ might put more effort in than the odd
dictatorship trying to pay lip service to preventing people reading pages on
a blacklist.


Given the vulnerability of DNS to poisoning I would not trust it too much. 
I know its just a bootstrap, but ideally you dont want to bootstrap from a
known publicly vulnerable protocol - it invites DNS poison net splits
against new users.


Also to the extent that users local clock is under his control (with
unuthentcated NTP?) he should also treat sudden dramatic changes in luck
(deviations from 10min interval) as suspicious.  

Unfortunately at present because of the first past the post nature of the
bitcoin lottery, reduced variance hashcash cannot be used, so its hard to
infer too much even from quite significant luck changes.

Adam

On Mon, May 06, 2013 at 06:47:22PM +0200, Mike Hearn wrote:
>> Speaking of, off-topic for this discussion, but in the future
>> node-to-node communicate should be encrypted and signed
>
>Yes, I'd like to do this. The threat isn't really ISPs which are
>mostly trustable (the worst they normally do outside of places like
>China is dick about with ads), the big threat is people who use
>untrusted WiFi without realising and end up thinking they received
>money when actually they were just connected to a hotspot running in
>the attackers pocket. I'm rather expecting that kind of thing to
>happen in future.
>
>I think we can converge on the best solution with several iterations:
>
>Iteration 1) Make it clear in the UI that if the phone is connected to
>WiFi, payments from untrusted people should not be accepted. Currently
>the Android app merely says the money won't be spendable for a few
>minutes. It needs to communicate the "may not exist" aspect more
>clearly. If you're connected via a cell tower, the existing wording is
>fine - it's very unlikely your telco is trying to scam you in a
>person-to-person transaction, traffic is encrypted and 3G+ connections
>authenticate the network so you can't be MITMd except by your telco.
>Assuming you have a good list of IPs, of course.
>
>Iteration 2) Give nodes keys that appear in addr broadcasts and seed
>data (whether it be via https or otherwise), and have each node keep a
>running hash of all messages sent on a connection so far. Add a new
>protocol message that asks the node to sign the current accumulated
>hash. Not all messages really need to be signed, eg asking for
>signatures of blocks is sort of pointless at high difficulty levels
>because the structures are self proving and a simple watchdog timer
>that looks for unusually slow progress is probably enough. If the
>client keeps the same accumulated hash then when you encounter
>something you care about the accuracy of, you can ask for a signature
>over all traffic so far.
>
>Iteration 3) Do something about end to end encryption, just delegate
>everything to Tor, or find some other way to obfuscate the origin of a
>transaction (a mini onion network for example).
>
>Last time I looked, Tor wasn't really usable in library form and
>connecting to hidden services is really slow. So it'd be an issue to
>just re-use it out of the box, I think.

Re: [Bitcoin-development] Discovery/addr packets (was: Service bits for pruned nodes)

[Gregory Maxwell]

On Mon, May 6, 2013 at 11:04 AM, Adam Back <adam@cypherspace.org> wrote:
> bitcoins primary
> vulnerability IMO (so far) is network attacks to induce network splits,
> local lower difficulty to a point that a local and artificially isolated
> area of the network can be fooled into accepting an orphan branch as the
> one-true block chain,

Uh.  It currently costs about 2016*25*$120 = six million dollars to
reduce the difficulty in your isolated fork by a factor of 4.

To reduce it by a factor of 1000 (what would be required to make a
parallel fork that you could maintain in realtime with a single avalon
device) the cost is  sum(2016*25/4^n*120,n,0,ceil(log4(1000))) or
about eight million dollars.

Surely you can think of attacks on Bitcoin which are less expensive
than eight million dollars. :P

> maybe even from node first install time.

Protecting against that— making sure any such attack has to start from
a high difficulty— is, in my opinion, the biggest continued
justification for checkpoints.

> (btw I notice most of the binaries and tar balls are not signed, nor served
> from SSL - at least for linux).

They are signed.

> With ToR, it has a similar bootstrap problem to bitcoin.  So while that may
> help it is also passing the buck, not necessarily solving the problem.  And

No, it doesn't. It has centrally controlled directories that publish
an official Truth of the Network. Someone can isolate you and thus DOS
you, but they can't put you on a fantasy tor network.  But ...
centeralized.

> as I said I think its possible bitcoin has a higher assurance need in that
> the attackers motivated my $$ might put more effort in than the odd

It does, and we also consider decentralization a core value. But even
the tor project would like to decentralize more.

[Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Adam Back]

On Mon, May 06, 2013 at 11:25:50AM -0700, Gregory Maxwell wrote:
>On Mon, May 6, 2013 at 11:04 AM, Adam Back <adam@cypherspace.org> wrote:
>> bitcoins primaryvulnerability IMO (so far) is network attacks to induce
>> network splits, local lower difficulty to a point that a local and
>> artificially isolated area of the network can be fooled into accepting an
>> orphan branch as the one-true block chain,
>
>It currently costs about 2016*25*$120 = six million dollars to
>reduce the difficulty in your isolated fork by a factor of 4.

Well I take your point that you have to produce 2016 blocks, but at a lower
rate.  But that doesnt directly translate into my cost, I am thinking pure
network hacking.

Maybe I could hack a pool to co-opt it into my netsplit and do the work for
me, or segment enough of the network to have some miners in it, and they do
the work.

I am just thinking $500k/day worth of relatively perfect crime reward is a
lot of motivation for hacking networks.  Many routers home and even carrier
are vulnerable to people armed with cisco source code & 0-days.  The
netsplit doesnt have to be geographical, nor even topological, nor even
particularly long-lived.

If you control enough people's network routing at a low enough level, you
dont even have to stop transactions, nor do any mining work, just stop
blocks from the netsplit crossing over, and hold that position for say a day
(if your netsplit has 1/24 of network hash rate in it, so the split gets 6
confirmations to reassure the victims) and let the miners do the work.  Do
enough transactions to do a big cash out (spend differently on the two
netsplits).  Obviously a big and human inattentive pool, dark-miner etc is
the ideal target to put into the netsplit to increase the power while
controlling less nodes.

Malware could do the same thing for clients, dont forget most are running
windows.  Malware could also start a miner if none present.

>> maybe even from node first install time.
>
>Protecting against that— making sure any such attack has to start from
>a high difficulty— is, in my opinion, the biggest continued
>justification for checkpoints.

Do you know if there is any downwards limit on difficulty?  I know it takes
going slow for a long and noticeable time, but I am just curious on the
theoretical limit.

>> (btw I notice most of the binaries and tar balls are not signed, nor served
>> from SSL - at least for linux).
>
>They are signed.

I dont see the signatures.

http://bitcoin.org/en/download

I see no signatures for linux and none in the tarball.  There are some
public keys inside the tarball, thats it.  Also no SSL.  sourceforge support
SSL so you can download that.  But bitcoin.org doesnt even answer 443, and
the source forge link is HTTP.  But even if the sourceforge link was SSL one
should not serve an SSL download link from an HTTP page, any more than type
a password into an HTTPS form action on an HTTP page.  The attacker can just
redirect and the user doesnt know what is legitimate.

Consequently even if there is code signing on the windows exe, the user
doesnt know that, nor who they should be signed by, and as they are served
via HTTP, its bypassable.

I guess by far the easiest way to attack right now (at least linux users) is
just to change the binaries to create a user operated netsplit, or just have
all their wallets empty to you via a mix once the amount gets interesting.

(All attacks hypothetical of course - I'm actually a white-hat type of
person).

Adam

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Gregory Maxwell]

On Mon, May 6, 2013 at 3:51 PM, Adam Back <adam@cypherspace.org> wrote:
> Maybe I could hack a pool to co-opt it into my netsplit and do the work for
> me, or segment enough of the network to have some miners in it, and they do
> the work.

Or you can just let it mine honestly and take the Bitcoins. This is
fast (doesn't require weeks of them somehow not noticing that they're
isolated), and yields the values I listed as 'costs' if you would have
otherwise been able to use it to mine the difficulty down to 1.  Cost
is just as much foregone income from the alternative attack you could
have done instead.

> nor even topological, nor even
> particularly long-lived.

At least for attacks that drive the difficulty down it does.

If you want to talk about abusing a pool or creating a partition in
order to create short reorgs— I agree, those don't have to be long
lived and you can find many messages where I've written on that
subject.

It's inconsiderate to propose one attack and when I respond to it
changing the attack out from under me. :(  I would have responded
entirely differently if you'd proposed people segmenting the network
and creating short reorgs instead of mining the difficulty down.

> Do you know if there is any downwards limit on difficulty?  I know it takes
> going slow for a long and noticeable time, but I am just curious on the
> theoretical limit.

Every 2016 blocks can at most lower the difficulty by a factor of 4,
thats where the log4 (number of 2016 groups needed) and 4^n (factor in
cost reduction for each group) come from in the formulas I gave
previously.

> I dont see the signatures.

http://sourceforge.net/projects/bitcoin/files/Bitcoin/bitcoin-0.8.1/SHA256SUMS.asc/download

The signatures can't be inside the tarball because they sign the tarball.

Seems like the website redesign managed to hide the signatures pretty
good. They're in the release announcements in any case, but that
should be fixed.  Even when they were prominently placed, practically
no one checked them. As a result they are mostly security theater in
practice :(, — so— unfortunately, is SSL: there are many CA's who will
give anyone a cert with your name on it who can give them a couple
hundred bucks and MITM HTTP (not HTTPS!) between the CA's
authentication server and your webserver. Bitcoin.org is hosted by
github, even if it had SSL and even if the CA infrastructure weren't a
joke, the number of ways to compromise that hosting enviroment would
IMO make SSL mostly a false sense of security.

The gpg signatures and gitian downloader signatures provide good
security if actually used, solving the "getting people to use them"
problem is an open question.

And I agree, this stuff is a bigger issue than many other things like
mining the difficulty down.

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Petr Praus]

[-- Attachment #1: Type: text/plain, Size: 3874 bytes --]

I think it's worth noting that quite a large portion of Linux users
probably get the mainline Bitcoin client from the packages. I think Bitcoin
package maintainers are doing mostly a pretty good job :)


On 6 May 2013 18:13, Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Mon, May 6, 2013 at 3:51 PM, Adam Back <adam@cypherspace.org> wrote:
> > Maybe I could hack a pool to co-opt it into my netsplit and do the work
> for
> > me, or segment enough of the network to have some miners in it, and they
> do
> > the work.
>
> Or you can just let it mine honestly and take the Bitcoins. This is
> fast (doesn't require weeks of them somehow not noticing that they're
> isolated), and yields the values I listed as 'costs' if you would have
> otherwise been able to use it to mine the difficulty down to 1.  Cost
> is just as much foregone income from the alternative attack you could
> have done instead.
>
> > nor even topological, nor even
> > particularly long-lived.
>
> At least for attacks that drive the difficulty down it does.
>
> If you want to talk about abusing a pool or creating a partition in
> order to create short reorgs— I agree, those don't have to be long
> lived and you can find many messages where I've written on that
> subject.
>
> It's inconsiderate to propose one attack and when I respond to it
> changing the attack out from under me. :(  I would have responded
> entirely differently if you'd proposed people segmenting the network
> and creating short reorgs instead of mining the difficulty down.
>
> > Do you know if there is any downwards limit on difficulty?  I know it
> takes
> > going slow for a long and noticeable time, but I am just curious on the
> > theoretical limit.
>
> Every 2016 blocks can at most lower the difficulty by a factor of 4,
> thats where the log4 (number of 2016 groups needed) and 4^n (factor in
> cost reduction for each group) come from in the formulas I gave
> previously.
>
> > I dont see the signatures.
>
>
> http://sourceforge.net/projects/bitcoin/files/Bitcoin/bitcoin-0.8.1/SHA256SUMS.asc/download
>
> The signatures can't be inside the tarball because they sign the tarball.
>
> Seems like the website redesign managed to hide the signatures pretty
> good. They're in the release announcements in any case, but that
> should be fixed.  Even when they were prominently placed, practically
> no one checked them. As a result they are mostly security theater in
> practice :(, — so— unfortunately, is SSL: there are many CA's who will
> give anyone a cert with your name on it who can give them a couple
> hundred bucks and MITM HTTP (not HTTPS!) between the CA's
> authentication server and your webserver. Bitcoin.org is hosted by
> github, even if it had SSL and even if the CA infrastructure weren't a
> joke, the number of ways to compromise that hosting enviroment would
> IMO make SSL mostly a false sense of security.
>
> The gpg signatures and gitian downloader signatures provide good
> security if actually used, solving the "getting people to use them"
> problem is an open question.
>
> And I agree, this stuff is a bigger issue than many other things like
> mining the difficulty down.
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and
> their applications. This 200-page book is written by three acclaimed
> leaders in the field. The early access version is available now.
> Download your free book today! http://p.sf.net/sfu/neotech_d2d_may
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

[-- Attachment #2: Type: text/html, Size: 4954 bytes --]

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Matt Corallo]

I really beg to differ on this one.  If you're an Ubuntu user who is
behind only one distro (quantal) you're stuck on version 0.6.2 with no
updates since 2012 (yes, that means on May 15th you'll be lost). 
 
For those still on Debian Squeeze (ie barely out of date), you get
0.3.24! Yes, 0.3.24 including every issue we've fixed since
(https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures) and
bitcoin is not available in wheezy.

Those are just the two I bothered to look up, but, additionally, nearly
every distro I know of links bitcoin against libdb5.1 (latest Ubuntu,
Arch, etc) which means wallets run once with those packages will never
be usable an "official" Bitcoin build ever again.  I can't necessarily
fault them for this since 4.8 is quite old, but its certainly not "doing
mostly a pretty good job"

Matt

On Mon, 2013-05-06 at 23:48 -0500, Petr Praus wrote:
> I think it's worth noting that quite a large portion of Linux users
> probably get the mainline Bitcoin client from the packages. I think
> Bitcoin package maintainers are doing mostly a pretty good job :)

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Mike Hearn]

> Seems like the website redesign managed to hide the signatures pretty
> good. They're in the release announcements in any case, but that
> should be fixed.  Even when they were prominently placed, practically
> no one checked them. As a result they are mostly security theater

Security theater indeed - even if people check the signatures, where
did they get the identities of the signers/developers from?  Oh right,
the same website that served them the binary.

The signatures are useful for verifying the integrity of our mirrors.
The verify-bitcoin.sh script does this. Unfortunately it's not good
enough. I run it daily and from time to time it fails and says the
hashes don't match, which I assume means we may have a corrupted
mirror somewhere or the script itself is flaky. But the output is too
sparse to investigate. I modified it to print more data and am waiting
for it to fail again, unfortunately, I can't make it fail on demand.

Anyway. I've been thinking about this problem a fair bit. It's easier
to solve on some platforms than on others.

On Android, the Bitcoin Wallet app is protected by a few things:

1) Once installed, the device will only accept updates that were
signed by the same key as the original. So the auto update mechanism
is secure (including I believe against an attack by the store
operator, which is usually Google).

2) It appears at the top of the Play Store when you search for
"Bitcoin". Unfortunately the Store is somewhat gameable at the moment,
but that's getting fixed and more importantly over the long term, app
store operators have the right incentives to crack down on gaming of
search results. This combined with the reviews, ratings and social
recommendations of real users provides a series of signals that are
hard for an attacker/phisher to replicate. You can say to someone "Go
get the app called Bitcoin Wallet by Andreas Schildbach from the
store" and the chances they get the right thing, signed by the right
person, are very high.

3) I never got around to trying it, but the threshold RSA library I
obtained is theoretically capable of splitting the RSA keys used to
protect updates. I've talked to Andreas about this a little bit, and I
think he's open to the idea of splitting the Android signing key so it
requires a quorum of developers to release an update. This is Shoup
threshold RSA, not a Shamir secret share of the key bits.

4) The OS sandboxes apps from each other. That sandbox doesn't have a
great track record outside of Google-controlled devices because OEMs
and carriers don't have the right incentives to actually ship OS
security updates, but it's still a lot better than nothing and
hopefully over time these issues will get resolved.

All together this means users on phones and tablets have a somewhat
convincing security solution that fights against phishing and malware.

On MacOS X the binaries are signed under the legal identity of the
Bitcoin Foundation. Jim has started signing MultiBit with his legal
identity too (this is required to make Gatekeeper happy on recent
versions of MacOS). Unsigned binaries will not run by default on 10.8,
but anyone with a developer certificate can sign any binary. So whilst
a hacked bitcoin.org or a phishing site can distribute malware, at
least on OS X 10.8 it will require the user to override the built in
security systems, or it will require the malware author to steal a
developer certificate - probably not very hard but definitely raises
the bar.

On Windows antivirus companies operate what is effectively a form of
binary whitelisting. The new MultiBit release triggered AV warnings
for a few days until it got enough reputation to stop triggering. The
goal of these systems is to fight polymorphic viruses and they
understand code signing. If you reliably sign your binaries, positive
binary reputation accrues to your signing identity and not the binary
itself, so you can release updates and not get harassed.

On Linux we're actually the most exposed. It has by far the worst
situation of all - a culture in which man-in-the-middle attacks by
package maintainers are not only common but actively encouraged. The
Debian OpenSSL fiasco showed the critical danger this can place people
in. I believe we should have a health warning on the website telling
people to only get binaries from us unless they are on a distribution
that we are verifying doesn't apply any patches. But that's a ton of
work and I long ago burned out on the politics of Linux software
distribution.

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Adam Back]

Well its a bit more hopeful than that :)

On Tue, May 07, 2013 at 11:17:17AM +0200, Mike Hearn wrote:
>> Seems like the website redesign managed to hide the signatures pretty
>> good.
>
>Security theater indeed - even if people check the signatures, where
>did they get the identities of the signers/developers from?  Oh right,
>the same website that served them the binary.

If they are PGP signatures, they can check the PGP WoT; its not that
hopeless some us eg have our keys in Ross Anderson's PGP Global Trust
Register, a PGP and CA key fingerprint book.  

http://www.cl.cam.ac.uk/research/security/Trust-Register/index.html

Probably most of the CA keys expired, but many of the PGP keys didnt.  So to
the extent that those people take PGP WoT seriously, and the main developers
names and email addresses are known and scattered around hundreds of web
mailing list archives etc there is some trust anchor.


And even without a PGP WoT connection, if the website had SSL enabled, they
can trust the binaries its sending to the extent that it is securely
maintained, and to the limit of the CA security weakest link (modulo sub-CA
malfeasance, and all the certification domain ownership laxness you or
someone mentioned in another mail).  That there are limitations in it doesnt
mean you should not avail of the (moderately crummy) state of the art!

And that is tied back to the domain itself hwich is very mnemonic and
referenced widely in print, tv, websites etc.

>3) I never got around to trying it, but the threshold RSA library I
>obtained is theoretically capable of splitting the RSA keys used to
>protect updates. I've talked to Andreas about this a little bit, and I
>think he's open to the idea of splitting the Android signing key so it
>requires a quorum of developers to release an update. This is Shoup
>threshold RSA, not a Shamir secret share of the key bits.

I guess its the least of the concerns but I believe Damgards is better. 
Another possibility is threshold DSA (which is built using Damgards Paillier
additively homomorphic cryptosystem extension) and discrete log schemes are
easier to setup with zero-trust.  Other simpler discrete log signatures ie
Schnorr are much easier to work with (threshold DSA is a mite complicated),
but NIST tweaked Schnorr to create DSA, and the rest is history.  The trust
n-1 of n is good enough for signatures because anyway that is above the
assurance of the signature.

>On Linux we're actually the most exposed. It has by far the worst
>situation of all - a culture in which man-in-the-middle attacks by
>package maintainers are not only common but actively encouraged. The
>Debian OpenSSL fiasco showed the critical danger this can place people
>in. I believe we should have a health warning on the website telling
>people to only get binaries from us unless they are on a distribution
>that we are verifying doesn't apply any patches. But that's a ton of
>work and I long ago burned out on the politics of Linux software
>distribution.

Well before I tried the download I had downloaded and compiled a few
versions from git.  But to get a stable and experience the non-programmer
view I did first try "yum install bitcoin" and then "yum whatprovides bitcoin"
on fedora 18 with +rpmfusion and there appeared to be no package!

I didnt find the signature on the source either or I would've checked.


Other ways you could get usefully get assurance of the source is multiple
people signing the release, with an asserted meaning being - I checked the
patches that went into this and I see nothing malicious.  It might help if
one or more of the signer were pseudonymous even (eg Satoshi if willing)
because you cant coerce legally, nor physically a pseudonymous person
because you cant find them.  Its a lot of pressure on open secure coding
process when there is $1bil value protected by the integrity of the code. 
(It seems the most likely avenue to bypass that maybe simply the attacker to
just become a committer and slip the 0-day past the review process.  There
were in the past modest-impact and plausible looking mistakes in PGP
discovered after sometime.)

Adam

Re: [Bitcoin-development] limits of network hacking/netsplits (was: Discovery/addr packets)

[Mike Hearn]

> And even without a PGP WoT connection, if the website had SSL enabled, they
> can trust the binaries its sending to the extent that it is securely
> maintained

Yes, it would be nice to have SSL but that requires finding
alternative file hosting.

> I guess its the least of the concerns but I believe Damgards is better.

Unfortunately we don't have any choice in what to use. There's no way
on Android to change the signing key after deployment, so we can
either split the existing key or do nothing.

There is a quorum-of-developers signing system using gitian and
reproducible builds, but as noted by Gregory, the problem is that
people don't check the signatures (even ignoring the web of trust
aspect which raises the complexity much higher). This sort of thing
works best when combined with an auto update engine or other kind of
software distribution platform.