Re: [Bitcoin-development] Protocol extensions

Re: [Bitcoin-development] Protocol extensions

[Eric Lombrozo]

There are other issues besides IP address anonymization that would
need to be addressed. I'm sure at least a good number of you have read
http://arxiv.org/abs/1107.4524 and have seen Dan Kaminsky's
slideshows.

i.e. all fund aggregations (transactions with multiple inputs using
different public keys) make it easy to associate all the public keys
to a single entity. Large movements of bitcoin to addresses that
haven't been seen before are often interesting events. Then you can
correlate transactions with trades on exchanges or with other data
sources for time and amount.

However, going back to what had been said earlier, the bitcoin
protocol itself is not really designed to address these issues. It is
designed with the goal of rapidly propagating transactions over a
network and getting a bunch of peers to be able to independently
verify that they occurred in a particular order and that the
signatures are valid.

The subject of how to anonymize cryptocurrencies is a separate one,
IMHO...and one which needs to address not only how to hide the
identity of those who relay transactions but also how to organize and
manipulate wallets as to thwart attempts at block chain analysis. And
these topics, although interesting in and of themselves, was not what
this thread was intended to address. This thread was intended to
address the issue of extending the protocol to allow for independently
running thin or specialized services that can all interface via the
bitcoin protocol without requiring one to step outside the protocol
with special gateway access.

[Bitcoin-development] Protocol extensions

[Eric Lombrozo]

Hey, guys.

I haven't posted here before so I'll introduce myself. My name's Eric,
I've been developing cryptocurrency-related
software for several months now, I've implemented some libraries for
dealing with core bitcoin datastructures, made
some custom builds of bitcoind and interfaced it with a few apps I've written.

In doing so, I've come to appreciate just how little of the potential
for the bitcoin protocol is being exploited right now...
not only in terms of the script features but in terms of the potential
commands and node types that could exist.

For instance, the protocol spec at
https://en.bitcoin.it/wiki/Protocol_specification only has 16 commands
listed and
only one service type...despite having a full 12 bytes for a command
code and a full eight bytes for a services
type.

The fact that only one node service type is specified is probably due
to the fact that the satoshi client was written
to be a standalone monolithic app that took care of all the essential
needs for a network of peers.
i.e. block chain storage/management, transaction signing/verification,
key generation/wallet management, block mining, etc...
However, I think there's an urgent need for breaking up all these
different tasks into separate components that can run as independent
services on different types of devices.

One of the big issues I'm dealing with now pertains to block chain
storage. As of right now, it is implemented as sequential
disk files using Berkeley DB in the satoshi client. Then you have
other projects that have been using SQL tables, etc...
But I believe the direction this really needs to move towards is some
sort of distributed hash table...and the database queries
should be performed using the bitcoin protocol itself. Perhaps adding
a few more commands. As things stand right now,
the only way to query for transactions or blocks is by their hash. And
once a transaction gets incorporated into a block and
removed from the transaction pool, one can no longer query it by the
transaction hash without stepping outside the bitcoin protocol.
We need access to the disk file that stores the blocks whether it be
via Berkeley DB or SQL or whatever.

I propose an extension to the bitcoin protocol to provide methods for
performing more sophisticated queries, such as "Give me
an inventory of transactions involving this particular public key" or
"Give me an inventory all transactions in the last n blocks with
unredeemed outputs." This could be done by adding a few more commands.

Furthermore, I propose a new network services type for nodes that
serve as block chain/transaction pool storage.

Of couse, any peer that wishes to verify the integrity of the block
chain would still have to download at the very least
all the block headers...and to be completely sure, also all the blocks
themselves...and verify everything. But it would be
very nice to be able to run thin services that can rely on other
network peers to do this work. It is still possible to attain
a high level of confidence in the integrity by querying multiple peers
for similar objects and comparing. It is also possible
to run your own dedicated block chain storage servers which you trust.

There are other ideas I have for other types of services, too.

Anyhow, I'm just throwing this out there...if anyone's interested I'd
love to develop these ideas further and help put together some
specs.

-Eric Lombrozo

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

Hey Eric,

Two comments.

1.
The ability to query for transactions belonging to pubkeys or bitcoin addresses is supported today by several implementations:
* blockexplorer.com
* bitcoin-js
* my own libBTC (will more on this soon)

To query for transactions you need to use json-rpc and not the bitcoin protocol, however. But still the purpose is the same: to be able to build thin clients that can rely on a server for storing the blockchain and keeping connected on the p2p network.

The reason for not having these queries part of the standard protocol (I think) are as they breaks anonymity, and that you would actually encourage people to participate in the p2p.

2. The second part you mention, to some how move the storage of the blockchain into a DHT based storage would be quite nice. The benefit of this is that it could be a way to integrate the smaller clients into the network without breaking the anonymity. But it should be thought out quite carefully. Further, if each client only store a fraction of the blockchain we should work out what fraction that need to be in order to ensure a similar service level. I would be happy to work with you on this.

Cheers,

Michael

On 17/12/2011, at 08:41, Eric Lombrozo wrote:

> Hey, guys.
> 
> I haven't posted here before so I'll introduce myself. My name's Eric,
> I've been developing cryptocurrency-related
> software for several months now, I've implemented some libraries for
> dealing with core bitcoin datastructures, made
> some custom builds of bitcoind and interfaced it with a few apps I've written.
> 
> In doing so, I've come to appreciate just how little of the potential
> for the bitcoin protocol is being exploited right now...
> not only in terms of the script features but in terms of the potential
> commands and node types that could exist.
> 
> For instance, the protocol spec at
> https://en.bitcoin.it/wiki/Protocol_specification only has 16 commands
> listed and
> only one service type...despite having a full 12 bytes for a command
> code and a full eight bytes for a services
> type.
> 
> The fact that only one node service type is specified is probably due
> to the fact that the satoshi client was written
> to be a standalone monolithic app that took care of all the essential
> needs for a network of peers.
> i.e. block chain storage/management, transaction signing/verification,
> key generation/wallet management, block mining, etc...
> However, I think there's an urgent need for breaking up all these
> different tasks into separate components that can run as independent
> services on different types of devices.
> 
> One of the big issues I'm dealing with now pertains to block chain
> storage. As of right now, it is implemented as sequential
> disk files using Berkeley DB in the satoshi client. Then you have
> other projects that have been using SQL tables, etc...
> But I believe the direction this really needs to move towards is some
> sort of distributed hash table...and the database queries
> should be performed using the bitcoin protocol itself. Perhaps adding
> a few more commands. As things stand right now,
> the only way to query for transactions or blocks is by their hash. And
> once a transaction gets incorporated into a block and
> removed from the transaction pool, one can no longer query it by the
> transaction hash without stepping outside the bitcoin protocol.
> We need access to the disk file that stores the blocks whether it be
> via Berkeley DB or SQL or whatever.
> 
> I propose an extension to the bitcoin protocol to provide methods for
> performing more sophisticated queries, such as "Give me
> an inventory of transactions involving this particular public key" or
> "Give me an inventory all transactions in the last n blocks with
> unredeemed outputs." This could be done by adding a few more commands.
> 
> Furthermore, I propose a new network services type for nodes that
> serve as block chain/transaction pool storage.
> 
> Of couse, any peer that wishes to verify the integrity of the block
> chain would still have to download at the very least
> all the block headers...and to be completely sure, also all the blocks
> themselves...and verify everything. But it would be
> very nice to be able to run thin services that can rely on other
> network peers to do this work. It is still possible to attain
> a high level of confidence in the integrity by querying multiple peers
> for similar objects and comparing. It is also possible
> to run your own dedicated block chain storage servers which you trust.
> 
> There are other ideas I have for other types of services, too.
> 
> Anyhow, I'm just throwing this out there...if anyone's interested I'd
> love to develop these ideas further and help put together some
> specs.
> 
> -Eric Lombrozo
> 
> ------------------------------------------------------------------------------
> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> Microsoft is holding a special Learn Windows Azure training event for 
> developers. It will provide a great way to learn Windows Azure and what it 
> provides. You can attend the event by watching it streamed LIVE online.  
> Learn more at http://p.sf.net/sfu/ms-windowsazure
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Protocol extensions

[Christian Decker]

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

A while back I had proposed a similar idea to the DHT, although my main
goal was to reduce the need for broadcasts.

My idea was to structure the network in a hypercube and use prefixes to
address different parts of the network, and use those prefixes also to find
the location where an item (transaction, block, ...) should be stored. Each
vertex in the hypercube is a small, highly connected, cluster of nodes. The
storage would be distributed, messages are routed on behalf of others,
which makes finding the origin of the query hard to find (think Tor), each
node would have to store only O(log(p)) items, with p being the prefix
length, maximum number of hops is equal to the dimension of the hypercube
O(log(n)).

Newly created transaction will be sent directly to the location they'll be
stored and miners retrieve new transactions at regular intervals. It might
increase delays to the confirmations, but it reduces the number of
broadcasts and storage requirements on nodes greatly.

Regards,
Chris


On Sat, Dec 17, 2011 at 2:13 PM, Michael Grønager <gronager@ceptacle.com>wrote:

> Hey Eric,
>
> Two comments.
>
> 1.
> The ability to query for transactions belonging to pubkeys or bitcoin
> addresses is supported today by several implementations:
> * blockexplorer.com
> * bitcoin-js
> * my own libBTC (will more on this soon)
>
> To query for transactions you need to use json-rpc and not the bitcoin
> protocol, however. But still the purpose is the same: to be able to build
> thin clients that can rely on a server for storing the blockchain and
> keeping connected on the p2p network.
>
> The reason for not having these queries part of the standard protocol (I
> think) are as they breaks anonymity, and that you would actually encourage
> people to participate in the p2p.
>
> 2. The second part you mention, to some how move the storage of the
> blockchain into a DHT based storage would be quite nice. The benefit of
> this is that it could be a way to integrate the smaller clients into the
> network without breaking the anonymity. But it should be thought out quite
> carefully. Further, if each client only store a fraction of the blockchain
> we should work out what fraction that need to be in order to ensure a
> similar service level. I would be happy to work with you on this.
>
> Cheers,
>
> Michael
>
> On 17/12/2011, at 08:41, Eric Lombrozo wrote:
>
> > Hey, guys.
> >
> > I haven't posted here before so I'll introduce myself. My name's Eric,
> > I've been developing cryptocurrency-related
> > software for several months now, I've implemented some libraries for
> > dealing with core bitcoin datastructures, made
> > some custom builds of bitcoind and interfaced it with a few apps I've
> written.
> >
> > In doing so, I've come to appreciate just how little of the potential
> > for the bitcoin protocol is being exploited right now...
> > not only in terms of the script features but in terms of the potential
> > commands and node types that could exist.
> >
> > For instance, the protocol spec at
> > https://en.bitcoin.it/wiki/Protocol_specification only has 16 commands
> > listed and
> > only one service type...despite having a full 12 bytes for a command
> > code and a full eight bytes for a services
> > type.
> >
> > The fact that only one node service type is specified is probably due
> > to the fact that the satoshi client was written
> > to be a standalone monolithic app that took care of all the essential
> > needs for a network of peers.
> > i.e. block chain storage/management, transaction signing/verification,
> > key generation/wallet management, block mining, etc...
> > However, I think there's an urgent need for breaking up all these
> > different tasks into separate components that can run as independent
> > services on different types of devices.
> >
> > One of the big issues I'm dealing with now pertains to block chain
> > storage. As of right now, it is implemented as sequential
> > disk files using Berkeley DB in the satoshi client. Then you have
> > other projects that have been using SQL tables, etc...
> > But I believe the direction this really needs to move towards is some
> > sort of distributed hash table...and the database queries
> > should be performed using the bitcoin protocol itself. Perhaps adding
> > a few more commands. As things stand right now,
> > the only way to query for transactions or blocks is by their hash. And
> > once a transaction gets incorporated into a block and
> > removed from the transaction pool, one can no longer query it by the
> > transaction hash without stepping outside the bitcoin protocol.
> > We need access to the disk file that stores the blocks whether it be
> > via Berkeley DB or SQL or whatever.
> >
> > I propose an extension to the bitcoin protocol to provide methods for
> > performing more sophisticated queries, such as "Give me
> > an inventory of transactions involving this particular public key" or
> > "Give me an inventory all transactions in the last n blocks with
> > unredeemed outputs." This could be done by adding a few more commands.
> >
> > Furthermore, I propose a new network services type for nodes that
> > serve as block chain/transaction pool storage.
> >
> > Of couse, any peer that wishes to verify the integrity of the block
> > chain would still have to download at the very least
> > all the block headers...and to be completely sure, also all the blocks
> > themselves...and verify everything. But it would be
> > very nice to be able to run thin services that can rely on other
> > network peers to do this work. It is still possible to attain
> > a high level of confidence in the integrity by querying multiple peers
> > for similar objects and comparing. It is also possible
> > to run your own dedicated block chain storage servers which you trust.
> >
> > There are other ideas I have for other types of services, too.
> >
> > Anyhow, I'm just throwing this out there...if anyone's interested I'd
> > love to develop these ideas further and help put together some
> > specs.
> >
> > -Eric Lombrozo
> >
> >
> ------------------------------------------------------------------------------
> > Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> > Microsoft is holding a special Learn Windows Azure training event for
> > developers. It will provide a great way to learn Windows Azure and what
> it
> > provides. You can attend the event by watching it streamed LIVE online.
> > Learn more at http://p.sf.net/sfu/ms-windowsazure
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>
> ------------------------------------------------------------------------------
> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> Microsoft is holding a special Learn Windows Azure training event for
> developers. It will provide a great way to learn Windows Azure and what it
> provides. You can attend the event by watching it streamed LIVE online.
> Learn more at http://p.sf.net/sfu/ms-windowsazure
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

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

[Bitcoin-development] Protocol extensions

[Gavin Andresen]

There was a discussion about using DHT's for transactions a while back
on the forums:
 https://bitcointalk.org/index.php?topic=723.msg7908#msg7908

If you can figure out a scheme that is secure from malicious Sybil
attacks then you're smarter than I am.

And additional protocol messages for lightweight clients is a good
idea, as long as they don't make it a lot easier to pull off a
denial-of-service attacks on a "full" node.

Although I do also wonder if we'll ever run into a problem with full
nodes refusing to answer requests from lightweight nodes (there might
be a tragedy-of-the-commons problem lurking there).

--
--
Gavin Andresen

Re: [Bitcoin-development] Protocol extensions

[theymos]

On Sat, Dec 17, 2011, at 02:06 PM, Gavin Andresen wrote:
> Although I do also wonder if we'll ever run into a problem with full
> nodes refusing to answer requests from lightweight nodes (there might
> be a tragedy-of-the-commons problem lurking there).

This seems likely. Also, even if many full nodes are willing to donate
resources, there may simply be too few full nodes to handle the load.

My preferred solution for handling scalability in the future is to
have lightweight clients download only headers and Merkle trees (which
are both small and easy to distribute), and then require senders to
contact recipients directly in order to transmit their transactions.
Then lightweight clients never need full blocks to build their
balances, and full nodes don't have to handle expensive queries from
lightweight clients.

Under this scheme, the current broadcast system could be used among full
nodes for a long time. Since clients wouldn't ever need to talk to full
nodes, they could form a separate network with less reliable
broadcasting and perhaps a fancier network architecture. Members of the
full network would connect to the most reliable members of the client
network in order to broadcast headers and Merkle trees and receive
transactions. Full nodes would *not* answer any client queries, so
dealing with the client network would not require many resources, and
miners would probably have an incentive to do it. (Creating a "separate"
network like this can be done by using the services field.)

I don't think requiring senders to email some data to the recipient
would be too burdensome, though it's probably also possible to design a
system where even offline recipients can receive transactions through
the Bitcoin network.

Re: [Bitcoin-development] Protocol extensions

[Jordan Mack]

While using DHT for storage of the block chain is an intriguing concept, 
I do not see how it is feasible. As Gavin noted, DHT is a system that is 
difficult to impossible to guarantee against data loss or manipulation.

Even if we found a way to store the block chain in DHT, how would 
transactions be verified? As Gavin noted, you could ask the network, but 
cannot necessarily trust the peers you are connected to. Verification of 
the full block chain allows the client to trust no one.

I also do not see how DHT would solve the problem of scalability in 
regards to broadcast messages, although I am definitely interested in 
the concept.

Re: [Bitcoin-development] Protocol extensions

[Jeff Garzik]

On Sat, Dec 17, 2011 at 7:44 PM, Jordan Mack <jordanmack@parhelic.com> wrote:
> While using DHT for storage of the block chain is an intriguing concept,
> I do not see how it is feasible. As Gavin noted, DHT is a system that is
> difficult to impossible to guarantee against data loss or manipulation.
>
> Even if we found a way to store the block chain in DHT, how would
> transactions be verified? As Gavin noted, you could ask the network, but
> cannot necessarily trust the peers you are connected to. Verification of
> the full block chain allows the client to trust no one.

Well, the block chain data itself is internally self-validating.  As
long as you know the latest block's hash -- a big "if" -- there is no
problem downloading all other block chain data from DHT or any other
untrusted source.

In a malicious case, you would notice latest-hash differs from
non-malicious and wind up downloading multiple chains, when walking
hashes backwards through a DHT/lookup table.  So, a bit more work but
nothing fundamentally less secure _on a trust basis_.

Of course, I was focusing on data validation, which ignores other
factors such as DoS'ing the DHT.

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

Re: [Bitcoin-development] Protocol extensions

[Jordan Mack]

theymos' full node and lite node write up got me thinking.

There are two problems here that we are trying to solve:
- The scalability of broadcast messages.
- The resources required to sync and verify the block chain.

I see three distinct groups of clients:
- Miners (dedicated servers & desktops)
- Full (desktops)
- Lite (mobile devices)

To address scalability of broadcasting, there could be three separate 
modes of operation (or client types). Mining nodes would retain the 
complete block chain, and share all messages between other mining nodes. 
Full nodes would retain the complete block chain, receive new block 
information from mining nodes, and share block data between each other. 
Lite clients would not contain the block chain, or any broadcast 
messages, and would query against a full client for all actions.

Mining nodes would handle the brunt of the barrage of messages. All 
block and transaction messages would have to be broadcast across all 
mining nodes. This would be essentially the same as all clients 
currently operate today.

A full client would be one step down from a mining client. They only 
need new block data, and new transactions that pertain to them (for 
instant notification). All other broadcast data is irrelevant to them. 
They would get new block data from connections to mining nodes, or from 
other peer nodes. The transaction submission could be sent directly to a 
connected mining node, or bounced through other connected full nodes, 
with a random number hops. This would disassociate the IP from the 
transaction, similarly to Tor.

To address the need for instant transaction notification, without 
broadcasting to to everyone, notification messages would be sent 
directly from one full client to the other. This is where aliases come 
in. When an alias is resolved, it includes both a Bitcoin address, and a 
list of IPs to notify of the transaction. This reveals the IP of the 
sender and receiver to each other. If the sender or receiver wishes to 
remain anonymous, then they could opt out of notification, and wait for 
the transaction to appear in the block chain.

A lite client would connect to a "trusted" full client over an encrypted 
connection. This would essentially function as a remote control to a 
full client, and allow a user to send, receive, and confirm normally, 
but without the overhead. A full client could reside on the home 
computer or server, which is owned by the user. A hosted wallet could 
also be used just as easily.

I don't like the idea of a header only client, unless this is just an 
interim action until the full block chain is downloaded in the 
background. Development of these types of clients is probably 
inevitable, but I believe that this breaks the most fundamental aspects 
of Bitcoin's security model. If a client has only headers, it cannot do 
full verification, and it is trusting the data from random anonymous peers.

Re: [Bitcoin-development] Protocol extensions

[Andy Parkins]

On Sunday 18 Dec 2011 01:27:10 Jordan Mack wrote:

> I don't like the idea of a header only client, unless this is just an
> interim action until the full block chain is downloaded in the
> background. Development of these types of clients is probably
> inevitable, but I believe that this breaks the most fundamental aspects
> of Bitcoin's security model. If a client has only headers, it cannot do
> full verification, and it is trusting the data from random anonymous
> peers.

I'm working on (slowly) making a client able to download-on-demand.  That is 
to say that the block chain headers would be downloaded and maintained, but 
the block bodies would be downloaded as needed for full verification.  It's 
certainly not possible with the current protocol; but it's certainly a 
conceivable application.  I suppose it slots between headers-only and full 
client conceptually.


Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

Re: [Bitcoin-development] Protocol extensions

[theymos]

On Sat, Dec 17, 2011, at 05:27 PM, Jordan Mack wrote:
> I don't like the idea of a header only client, unless this is just an
> interim action until the full block chain is downloaded in the
> background. Development of these types of clients is probably
> inevitable, but I believe that this breaks the most fundamental
> aspects of Bitcoin's security model. If a client has only headers, it
> cannot do full verification, and it is trusting the data from random
> anonymous peers.

A headers-only client is much better than trusting anyone, since an
attacker needs >50% of the network's computational power to trick
such clients.

For everyone to keep being a full node, hardware costs would need to
constantly go down enough for all nodes to be able to handle enough
transactions to meet demand. If hardware doesn't become cheap enough
quickly enough, either some people would be unable to handle being full
nodes, or the max block size wouldn't rise enough to meet demand and
transaction fees would become noncompetitive.

Re: [Bitcoin-development] Protocol extensions

[Alan Reiner]

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

The whole point of having headers built at a constant size and 
generation rate is to minimize the amount of data needed to "understand" 
of the blockchain while simultaneously maximizing integrity/security in 
the presence of untrusted nodes.  Barring the 50%-attack, you only need 
a couple honest nodes out of 50 to stay safe (as long as you're waiting 
for your 6 confirmations).   In fact, I would argue that a full node 
(Satoshi client), has the same level of security as a headers-only 
client... because they both base *all* their verification decisions on 
computations that end with comparing hashes to the longest-chain headers.

In the case that an attacker figures out how to isolate your node 
entirely and start feeing you poisoned blocks, then you are vulnerable 
with any kind of node, full or lightweight.  I don't see where the 
reduced security is.

The only issue I see is that a truly light-weight, headers-only node 
will be having to download an entire block to get one transaction it 
needs.  This would be significantly alleviated if nodes can start 
requesting merkle-trees directly, even without merkle-branch-pruning.   
If a node can ask for a tx and the tx-hash-list of the block that 
incorporated that tx,  he can easily verify his tx against his 
no-need-to-trust-anyone headers, and doesn't have to download MBs for 
every one.

As for blockchain pruning... I think it's absolutely critical to find a 
way to do this, /for all nodes/.  I am swayed by Dan Kaminsky's 
scalability warnings, and my instinct tells me that leaving full 
verification to a select few deep-pockets nodes in the future opens up 
all sorts of centralization/power-corporation issues that is contrary to 
the Bitcoin concept.  It is in everyone's best interest to make it as 
easy as possible for /anyone/ to act as a full node (if possible).  As 
such, I believe that the current system of minimizing TxOut size is the 
right one.  TxIns take up 0 bytes space in the long-run when taking into 
account any blockchain pruning/snapshot idea (except for nLocktime/seq 
transactions where the TxIn might have to be saved).

-Alan





On 12/18/2011 12:09 PM, theymos wrote:
> On Sat, Dec 17, 2011, at 05:27 PM, Jordan Mack wrote:
>> I don't like the idea of a header only client, unless this is just an
>> interim action until the full block chain is downloaded in the
>> background. Development of these types of clients is probably
>> inevitable, but I believe that this breaks the most fundamental
>> aspects of Bitcoin's security model. If a client has only headers, it
>> cannot do full verification, and it is trusting the data from random
>> anonymous peers.
> A headers-only client is much better than trusting anyone, since an
> attacker needs>50% of the network's computational power to trick
> such clients.
>
> For everyone to keep being a full node, hardware costs would need to
> constantly go down enough for all nodes to be able to handle enough
> transactions to meet demand. If hardware doesn't become cheap enough
> quickly enough, either some people would be unable to handle being full
> nodes, or the max block size wouldn't rise enough to meet demand and
> transaction fees would become noncompetitive.
>
> ------------------------------------------------------------------------------
> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> Microsoft is holding a special Learn Windows Azure training event for
> developers. It will provide a great way to learn Windows Azure and what it
> provides. You can attend the event by watching it streamed LIVE online.
> Learn more at http://p.sf.net/sfu/ms-windowsazure
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


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

Re: [Bitcoin-development] Protocol extensions

[Amir Taaki]

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

Has anyone considered 'snapshot' frames (blocks).

Message to node:

getsnapshot: hash

Node responds with a 'block' message.

Then the hash for that particular snapshot is hardcoded into the sourcecode. It would replace the checkpoints and use the last hash in that list.

Validating blocks is pretty fast right up until block 135k, which is where time taken balloons and starts become exponentially slower. As blockchain grows linearly, resources needed grows exponentially if you think about it.



________________________________
 From: Alan Reiner <etotheipi@gmail.com>
To: bitcoin-development@lists.sourceforge.net 
Sent: Sunday, December 18, 2011 6:06 PM
Subject: Re: [Bitcoin-development] Protocol extensions
 

The whole point of having headers built at a constant size and generation rate is to minimize the amount of data needed to "understand" of the blockchain while simultaneously maximizing integrity/security in the presence of untrusted nodes.  Barring the 50%-attack, you only need a couple honest nodes out of 50 to stay safe (as long as you're waiting for your 6 confirmations).   In fact, I would argue that a full node (Satoshi client), has the same level of security as a headers-only client... because they both base all their verification decisions on computations that end with comparing hashes to the longest-chain headers.

In the case that an attacker figures out how to isolate your node
    entirely and start feeing you poisoned blocks, then you are
    vulnerable with any kind of node, full or lightweight.  I don't see
    where the reduced security is.  

The only issue I see is that a truly light-weight, headers-only node
    will be having to download an entire block to get one transaction it
    needs.  This would be significantly alleviated if nodes can start
    requesting merkle-trees directly, even without
    merkle-branch-pruning.   If a node can ask for a tx and the
    tx-hash-list of the block that incorporated that tx,  he can easily
    verify his tx against his no-need-to-trust-anyone headers, and
    doesn't have to download MBs for every one.  

As for blockchain pruning... I think it's absolutely critical to
    find a way to do this, for all nodes.  I am swayed by Dan Kaminsky's scalability warnings, and my instinct tells me that leaving full verification to a select few deep-pockets nodes in the future opens up all sorts of centralization/power-corporation issues that is contrary to the Bitcoin concept.  It is in everyone's best interest to make it as easy as possible for anyone to act as a full node (if possible).  As such, I believe that the current system of minimizing TxOut size is the right one.  TxIns take up 0 bytes space in the long-run when taking into account any blockchain pruning/snapshot idea (except for nLocktime/seq transactions where the TxIn might have to be saved).  

-Alan





On 12/18/2011 12:09 PM, theymos wrote: 
On Sat, Dec 17, 2011, at 05:27 PM, Jordan Mack wrote: 
>I don't like the idea of a header only client, unless this is just an
interim action until the full block chain is downloaded in the
background. Development of these types of clients is probably
inevitable, but I believe that this breaks the most fundamental
aspects of Bitcoin's security model. If a client has only headers, it
cannot do full verification, and it is trusting the data from random
anonymous peers. 
>A headers-only client is much better than trusting anyone, since an
attacker needs >50% of the network's computational power to trick
such clients. For everyone to keep being a full node, hardware costs would need to
constantly go down enough for all nodes to be able to handle enough
transactions to meet demand. If hardware doesn't become cheap enough
quickly enough, either some people would be unable to handle being full
nodes, or the max block size wouldn't rise enough to meet demand and
transaction fees would become noncompetitive. ------------------------------------------------------------------------------
Learn Windows Azure Live!  Tuesday, Dec 13, 2011
Microsoft is holding a special Learn Windows Azure training event for 
developers. It will provide a great way to learn Windows Azure and what it 
provides. You can attend the event by watching it streamed LIVE online.  
Learn more at http://p.sf.net/sfu/ms-windowsazure
_______________________________________________
Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development 

------------------------------------------------------------------------------
Learn Windows Azure Live!  Tuesday, Dec 13, 2011
Microsoft is holding a special Learn Windows Azure training event for 
developers. It will provide a great way to learn Windows Azure and what it 
provides. You can attend the event by watching it streamed LIVE online.  
Learn more at http://p.sf.net/sfu/ms-windowsazure
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

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

Re: [Bitcoin-development] Protocol extensions

[Jorge Timón]

2011/12/17, theymos <theymos@mm.st>:
> My preferred solution for handling scalability in the future is to
> have lightweight clients download only headers and Merkle trees (which
> are both small and easy to distribute), and then require senders to
> contact recipients directly in order to transmit their transactions.
> Then lightweight clients never need full blocks to build their
> balances, and full nodes don't have to handle expensive queries from
> lightweight clients.

This idea is really interesting. Is there any drawback I don't see?

Re: [Bitcoin-development] Protocol extensions

[Gregory Maxwell]

On Sat, Dec 17, 2011 at 8:37 AM, Christian Decker
<decker.christian@gmail.com> wrote:
> My idea was to structure the network in a hypercube and use prefixes to
> address different parts of the network, and use those prefixes also to find
> the location where an item (transaction, block, ...) should be stored. Each
> vertex in the hypercube is a small, highly connected, cluster of nodes.

I strongly advise people who are not me to use this sort of scheme, so
that I may enjoy the benefits of robbing you blind.


.... But really, saying "some sort of DHT" without basically
presenting a working implementation that demonstrates the feasibility
of solving the very difficulty attack resistance problems these
schemes have basically triggers my time-wasting-idiot filter.  (Or
likewise, presenting a fixed network structure that would have a nice
small and easily identifiable min-cut...)

I don't doubt I'm completely alone in this,  though perhaps I'm more
of a jerk about it.   Even if your actual proposal might have some
merit you should be aware that every fool who has operated a
bittorrent client has heard of "DHT" and, although they may not even
understand what a hash table is, many have no reservation going around
suggesting them for _every_ distributed systems problem. Want to scale
matrix multiples? DHT! Want to validate bitcoin blocks? DHT! Network
syncup slow (because It's bound on validation related local IO)? DHT!
I suggest people solve the real problems first, then worry what name
to give the solutions. ;)

To address gavin's tragedy of the commons concern, one useful feature
would being able to mutually authenticate a peer... then full nodes
could pick and choose which lite nodes they're willing to do (a lot
of) hard work for. This would also be valuable because some modes of
lite operation require non-zero trust of the full node being queried.

Re: [Bitcoin-development] Protocol extensions

[Christian Decker]

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

Criticism accepted, although I'd appreciate it if you supply some reasons
about why it's such a bad idea :-)
The idea was never really popular and before starting work on a real
implementation I wanted to test the water, and should it turn out it's
complete non-sense I'm happy to accept that.

I don't want to have a DHT for the DHTs sake, I was more interested in
reducing the number of messages that need to be sent around the network,
since network load is going to be a major problem if we ever grow beyond a
certain point.

Just wanting to brainstorm.

Regards,
Chris
On Sat, Dec 17, 2011 at 8:28 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Sat, Dec 17, 2011 at 8:37 AM, Christian Decker
> <decker.christian@gmail.com> wrote:
> > My idea was to structure the network in a hypercube and use prefixes to
> > address different parts of the network, and use those prefixes also to
> find
> > the location where an item (transaction, block, ...) should be stored.
> Each
> > vertex in the hypercube is a small, highly connected, cluster of nodes.
>
> I strongly advise people who are not me to use this sort of scheme, so
> that I may enjoy the benefits of robbing you blind.
>
>
> .... But really, saying "some sort of DHT" without basically
> presenting a working implementation that demonstrates the feasibility
> of solving the very difficulty attack resistance problems these
> schemes have basically triggers my time-wasting-idiot filter.  (Or
> likewise, presenting a fixed network structure that would have a nice
> small and easily identifiable min-cut...)
>
> I don't doubt I'm completely alone in this,  though perhaps I'm more
> of a jerk about it.   Even if your actual proposal might have some
> merit you should be aware that every fool who has operated a
> bittorrent client has heard of "DHT" and, although they may not even
> understand what a hash table is, many have no reservation going around
> suggesting them for _every_ distributed systems problem. Want to scale
> matrix multiples? DHT! Want to validate bitcoin blocks? DHT! Network
> syncup slow (because It's bound on validation related local IO)? DHT!
> I suggest people solve the real problems first, then worry what name
> to give the solutions. ;)
>
> To address gavin's tragedy of the commons concern, one useful feature
> would being able to mutually authenticate a peer... then full nodes
> could pick and choose which lite nodes they're willing to do (a lot
> of) hard work for. This would also be valuable because some modes of
> lite operation require non-zero trust of the full node being queried.
>

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

Re: [Bitcoin-development] Protocol extensions

[Stefan Thomas]

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

Hey Chris,

> The storage would be distributed, messages are routed on behalf of 
> others, which makes finding the origin of the query hard to find 
> (think Tor)

This type of intermediate routing makes Tor slow 
<https://svn.torproject.org/svn/projects/roadmaps/2009-03-11-performance.pdf>. 
Bitcoin does not and imho should not make anonymity guarantees. Many 
users do not need them.

Let those who want anonymity connect through Tor, Freenet, etc. It's 
easy to add anonymity via an extra layer, but it is impossible to add 
performance on top of a slow system.

That's really the only thing I wanted to point out - if you do DHTs, 
focus on performance, not anonymity. :)

Cheers,

Stefan

On 12/17/2011 2:37 PM, Christian Decker wrote:
> A while back I had proposed a similar idea to the DHT, although my 
> main goal was to reduce the need for broadcasts.
>
> My idea was to structure the network in a hypercube and use prefixes 
> to address different parts of the network, and use those prefixes also 
> to find the location where an item (transaction, block, ...) should be 
> stored. Each vertex in the hypercube is a small, highly connected, 
> cluster of nodes. The storage would be distributed, messages are 
> routed on behalf of others, which makes finding the origin of the 
> query hard to find (think Tor), each node would have to store only 
> O(log(p)) items, with p being the prefix length, maximum number of 
> hops is equal to the dimension of the hypercube O(log(n)).
>
> Newly created transaction will be sent directly to the location 
> they'll be stored and miners retrieve new transactions at regular 
> intervals. It might increase delays to the confirmations, but it 
> reduces the number of broadcasts and storage requirements on nodes 
> greatly.
>
> Regards,
> Chris
>
>
> On Sat, Dec 17, 2011 at 2:13 PM, Michael Grønager 
> <gronager@ceptacle.com <mailto:gronager@ceptacle.com>> wrote:
>
>     Hey Eric,
>
>     Two comments.
>
>     1.
>     The ability to query for transactions belonging to pubkeys or
>     bitcoin addresses is supported today by several implementations:
>     * blockexplorer.com <http://blockexplorer.com>
>     * bitcoin-js
>     * my own libBTC (will more on this soon)
>
>     To query for transactions you need to use json-rpc and not the
>     bitcoin protocol, however. But still the purpose is the same: to
>     be able to build thin clients that can rely on a server for
>     storing the blockchain and keeping connected on the p2p network.
>
>     The reason for not having these queries part of the standard
>     protocol (I think) are as they breaks anonymity, and that you
>     would actually encourage people to participate in the p2p.
>
>     2. The second part you mention, to some how move the storage of
>     the blockchain into a DHT based storage would be quite nice. The
>     benefit of this is that it could be a way to integrate the smaller
>     clients into the network without breaking the anonymity. But it
>     should be thought out quite carefully. Further, if each client
>     only store a fraction of the blockchain we should work out what
>     fraction that need to be in order to ensure a similar service
>     level. I would be happy to work with you on this.
>
>     Cheers,
>
>     Michael
>
>     On 17/12/2011, at 08:41, Eric Lombrozo wrote:
>
>     > Hey, guys.
>     >
>     > I haven't posted here before so I'll introduce myself. My name's
>     Eric,
>     > I've been developing cryptocurrency-related
>     > software for several months now, I've implemented some libraries for
>     > dealing with core bitcoin datastructures, made
>     > some custom builds of bitcoind and interfaced it with a few apps
>     I've written.
>     >
>     > In doing so, I've come to appreciate just how little of the
>     potential
>     > for the bitcoin protocol is being exploited right now...
>     > not only in terms of the script features but in terms of the
>     potential
>     > commands and node types that could exist.
>     >
>     > For instance, the protocol spec at
>     > https://en.bitcoin.it/wiki/Protocol_specification only has 16
>     commands
>     > listed and
>     > only one service type...despite having a full 12 bytes for a command
>     > code and a full eight bytes for a services
>     > type.
>     >
>     > The fact that only one node service type is specified is
>     probably due
>     > to the fact that the satoshi client was written
>     > to be a standalone monolithic app that took care of all the
>     essential
>     > needs for a network of peers.
>     > i.e. block chain storage/management, transaction
>     signing/verification,
>     > key generation/wallet management, block mining, etc...
>     > However, I think there's an urgent need for breaking up all these
>     > different tasks into separate components that can run as independent
>     > services on different types of devices.
>     >
>     > One of the big issues I'm dealing with now pertains to block chain
>     > storage. As of right now, it is implemented as sequential
>     > disk files using Berkeley DB in the satoshi client. Then you have
>     > other projects that have been using SQL tables, etc...
>     > But I believe the direction this really needs to move towards is
>     some
>     > sort of distributed hash table...and the database queries
>     > should be performed using the bitcoin protocol itself. Perhaps
>     adding
>     > a few more commands. As things stand right now,
>     > the only way to query for transactions or blocks is by their
>     hash. And
>     > once a transaction gets incorporated into a block and
>     > removed from the transaction pool, one can no longer query it by the
>     > transaction hash without stepping outside the bitcoin protocol.
>     > We need access to the disk file that stores the blocks whether it be
>     > via Berkeley DB or SQL or whatever.
>     >
>     > I propose an extension to the bitcoin protocol to provide
>     methods for
>     > performing more sophisticated queries, such as "Give me
>     > an inventory of transactions involving this particular public
>     key" or
>     > "Give me an inventory all transactions in the last n blocks with
>     > unredeemed outputs." This could be done by adding a few more
>     commands.
>     >
>     > Furthermore, I propose a new network services type for nodes that
>     > serve as block chain/transaction pool storage.
>     >
>     > Of couse, any peer that wishes to verify the integrity of the block
>     > chain would still have to download at the very least
>     > all the block headers...and to be completely sure, also all the
>     blocks
>     > themselves...and verify everything. But it would be
>     > very nice to be able to run thin services that can rely on other
>     > network peers to do this work. It is still possible to attain
>     > a high level of confidence in the integrity by querying multiple
>     peers
>     > for similar objects and comparing. It is also possible
>     > to run your own dedicated block chain storage servers which you
>     trust.
>     >
>     > There are other ideas I have for other types of services, too.
>     >
>     > Anyhow, I'm just throwing this out there...if anyone's
>     interested I'd
>     > love to develop these ideas further and help put together some
>     > specs.
>     >
>     > -Eric Lombrozo
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Learn Windows Azure Live!  Tuesday, Dec 13, 2011
>     > Microsoft is holding a special Learn Windows Azure training
>     event for
>     > developers. It will provide a great way to learn Windows Azure
>     and what it
>     > provides. You can attend the event by watching it streamed LIVE
>     online.
>     > Learn more at http://p.sf.net/sfu/ms-windowsazure
>     > _______________________________________________
>     > Bitcoin-development mailing list
>     > Bitcoin-development@lists.sourceforge.net
>     <mailto:Bitcoin-development@lists.sourceforge.net>
>     > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>     ------------------------------------------------------------------------------
>     Learn Windows Azure Live!  Tuesday, Dec 13, 2011
>     Microsoft is holding a special Learn Windows Azure training event for
>     developers. It will provide a great way to learn Windows Azure and
>     what it
>     provides. You can attend the event by watching it streamed LIVE
>     online.
>     Learn more at http://p.sf.net/sfu/ms-windowsazure
>     _______________________________________________
>     Bitcoin-development mailing list
>     Bitcoin-development@lists.sourceforge.net
>     <mailto:Bitcoin-development@lists.sourceforge.net>
>     https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>
> ------------------------------------------------------------------------------
> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> Microsoft is holding a special Learn Windows Azure training event for
> developers. It will provide a great way to learn Windows Azure and what it
> provides. You can attend the event by watching it streamed LIVE online.
> Learn more at http://p.sf.net/sfu/ms-windowsazure
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


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

Re: [Bitcoin-development] Protocol extensions

[Jordan Mack]

On 12/18/2011 1:19 PM, Stefan Thomas wrote:
 > Let those who want anonymity connect through Tor, Freenet, etc. It's
 > easy to add anonymity via an extra layer, but it is impossible to add
 > performance on top of a slow system.

That's a very good point. This is needless complication at the protocol 
level. Alternatives, like Tor, could be used to provide the desired 
effect. Developers could even choose to integrate Tor functionality into 
the client itself at some point.

Re: [Bitcoin-development] Protocol extensions

[Wladimir]

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

On Mon, Dec 19, 2011 at 10:43 PM, Jordan Mack <jordanmack@parhelic.com>wrote:

> On 12/18/2011 1:19 PM, Stefan Thomas wrote:
>  > Let those who want anonymity connect through Tor, Freenet, etc. It's
>  > easy to add anonymity via an extra layer, but it is impossible to add
>  > performance on top of a slow system.
>
> That's a very good point. This is needless complication at the protocol
> level. Alternatives, like Tor, could be used to provide the desired
>

Agreed. Please don't roll your own onion network. It is very non-trivial to
get security and anonymity to an acceptable level. Securing cryptocurrency
itself is a big enough challenge already.

Another reason it is better to use Tor is because of the mixing effect. A
bitcoin-specific onion network would be subject to easy traffic analysis if
it only carries Bitcoin messages.

effect. Developers could even choose to integrate Tor functionality into
> the client itself at some point.
>

Yes, good idea. I've thought about making a "bitcoin tor bundle", analogous
to the firefox Tor bundle that is available from the Tor site itself.

Probably would need to package the block chain with it, as downloading that
over Tor takes ages and causes unnecessary load on the network...

Wladimir

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

Re: [Bitcoin-development] Protocol extensions

[Nicolas Fischer]

On Tue, 20 Dec 2011 10:10:23 +0100
Wladimir <laanwj@gmail.com> wrote:

> Probably would need to package the block chain with it, as downloading that
> over Tor takes ages and causes unnecessary load on the network...

I actually started a freenet plugin for blockchain distribution in summer (first rough steps only). Freenet seems really fit for this purpose since its mechanisms to provide wider storage (and thus faster requesting) for much-requested keys should help a lot here. Also freenet storage is decentralized, so that's another plus that goes hand-in-hand with bitcoin principles.

There's already a specification for "btcfn" which was done in 2010: https://bitcointalk.org/index.php?topic=55089.msg655410#msg655410

I stopped work on this because other people were supposedly working on it. I asked da2ce7 about it at the conference and he said progress was "slow".

I totally agree with the sentiment that these features should not be implemented in the bitcoin node itself but outsourced to the established systems, both because it's hard and also for "hiding traffic in the masses".

-- 
Nicolas Fischer <molec@gmx.de>

Re: [Bitcoin-development] Protocol extensions

[Kyle Henderson]

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

> Developers could even choose to integrate Tor functionality into the
> client itself at some point.
>

The "satoshi" bitcoin client already supports use over TOR with the proxy
option - I think this was something Satoshi made regular use of.

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

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

DHTs and Bitcoin:

First, lets define the problem we want to solve: scalability - when bitcoin takes over all credit card transactions (!), and even before that, we will meet a scalability problem. The blockchain will grow rapidly, (1MB/10min or 50GB/yr) and we will constantly have transactions pending to get into a block. Further, the clients will turn into toasters just from validating all transactions. At the same time we have a level of validation and block chain distribution that we really don't need - today txes are validated by 100k clients in the future that could be 100M clients, and they are stored at way more locations than they are today. So... all this calls for a partition of the transaction/block space, and for a more flexible than 1MB / block setup.

First things first. The partitioning of the tx space. One way to partition the tx space is through a partition in hash, namely the DHT approach. There might be other schemes, but as we already have both the ability to share addresses and maintain a hash space it seems obvious.

So we would like a scheme that provides distributed validation and storage keeping a similar level of trust and security as we have today. We hence need to be able to query another node for validation and ensure it is not pulling our leg (Sybil...).

There are two important aspects of bitcoin:
1. transaction signing / validation
2. to avoid double spending

1. Is a a simple and inclusive problem to solve, 2 is more complex and exclusive. 1. can to a large extend be solved by asking for transactions and validating these against the block chain - it is hard to cheat as you can match blocks containing your transaction with the block chain headers, requiring a false node to perform heavy proof of work tasks.
If we on the other hand query other nodes for 2. just blocking an answer would be enough to enable a double spend. (at least seen from the one node querying).

Today you can, assuming you have en up to date block chain, only block pending tx'es which gives you an approximate 10 minutes scale for cheating by double spending. If we create a setup where we distribute the block index and the block chain, we can fake any older transaction as well, and leave a node to believe that a tx has not been spend. The obvious way around it is to ensure a high level of connectedness and to query several geographically distributed nodes if a tx has already been spend. But this can be quite hard and also, you don't want to flood the network with to many extra commands.

If we design the system based on the above conclusions we get:

1. A client is, based on the hash of its ip:port assigned to serve a part of the block chain, a part of the block index and possibly also a part of the bitcoin addresses (hash160).

2. Further, the client can announce that it also serves any other hashspace fractions - e.g. to enable notification of payments to its bitcoin address or use of its coins (txouts).

3. On validation of a tx, the txins are queried for at the clients serving these and a possible double spend can be monitored. We need to query more clients to ensure we are not cheated by one. And we need to maintain the requirement that they come from separate A.B address spaces (so they don't just setup a matching hash from playing with C.D and ports).

4. The proper nodes are found using Chord DHT scheme (other schemes might be suitable as well).

Thin clients keep their spendable coins to a minimum and use only one bitcoin address, that way they will only serve and listen to 3 hash fractions. If we split the current space into 4096 parts we get roughly 100 clients for each hash space.

The (only?) new attack vector, compared to the current system is the possibility that a client has only evil peers within one hash range and hence can be fooled into believing an old tx can be spend again.

The new scheme will scale well as each client will only serve a part of the hashspace and hence the number of validations and block storage can be kept at a minimum. Further, it scales well for thin clients vs more full clients as you can add as many or as few (down to 1-3) hash space parts as you want, so the new scheme includes the old scheme in the limit of subscribing to all hash space parts.

I might have overlooked something - so please fill in some comments...

Cheers,

Michael


On 18/12/2011, at 22:19, Stefan Thomas wrote:

> Hey Chris,
> 
>> The storage would be distributed, messages are routed on behalf of others, which makes finding the origin of the query hard to find (think Tor)
> 
> This type of intermediate routing makes Tor slow. Bitcoin does not and imho should not make anonymity guarantees. Many users do not need them.
> 
> Let those who want anonymity connect through Tor, Freenet, etc. It's easy to add anonymity via an extra layer, but it is impossible to add performance on top of a slow system.
> 
> That's really the only thing I wanted to point out - if you do DHTs, focus on performance, not anonymity. :)
> 
> Cheers,
> 
> Stefan
> 
> On 12/17/2011 2:37 PM, Christian Decker wrote:
>> A while back I had proposed a similar idea to the DHT, although my main goal was to reduce the need for broadcasts.
>> 
>> My idea was to structure the network in a hypercube and use prefixes to address different parts of the network, and use those prefixes also to find the location where an item (transaction, block, ...) should be stored. Each vertex in the hypercube is a small, highly connected, cluster of nodes. The storage would be distributed, messages are routed on behalf of others, which makes finding the origin of the query hard to find (think Tor), each node would have to store only O(log(p)) items, with p being the prefix length, maximum number of hops is equal to the dimension of the hypercube O(log(n)).
>> 
>> Newly created transaction will be sent directly to the location they'll be stored and miners retrieve new transactions at regular intervals. It might increase delays to the confirmations, but it reduces the number of broadcasts and storage requirements on nodes greatly.
>> 
>> Regards,
>> Chris
>> 
>> 
>> On Sat, Dec 17, 2011 at 2:13 PM, Michael Grønager <gronager@ceptacle.com> wrote:
>> Hey Eric,
>> 
>> Two comments.
>> 
>> 1.
>> The ability to query for transactions belonging to pubkeys or bitcoin addresses is supported today by several implementations:
>> * blockexplorer.com
>> * bitcoin-js
>> * my own libBTC (will more on this soon)
>> 
>> To query for transactions you need to use json-rpc and not the bitcoin protocol, however. But still the purpose is the same: to be able to build thin clients that can rely on a server for           storing the blockchain and keeping connected on the p2p network.
>> 
>> The reason for not having these queries part of the standard protocol (I think) are as they breaks anonymity, and that you would actually encourage people to participate in the p2p.
>> 
>> 2. The second part you mention, to some how move the storage of the blockchain into a DHT based storage would be quite nice. The benefit of this is that it could be a way to integrate the smaller clients into the network without breaking the anonymity. But it should be thought out quite carefully. Further, if each client only store a fraction of the blockchain we should work out what fraction that need to be in order to ensure a similar service level. I would be           happy to work with you on this.
>> 
>> Cheers,
>> 
>> Michael
>> 
>> On 17/12/2011, at 08:41, Eric Lombrozo wrote:
>> 
>>> Hey, guys.
>>> 
>>> I haven't posted here before so I'll introduce myself. My name's Eric,
>>> I've been developing cryptocurrency-related
>>> software for several months now, I've implemented some libraries for
>>> dealing with core bitcoin datastructures, made
>>> some custom builds of bitcoind and interfaced it with a few apps I've written.
>>> 
>>> In doing so, I've come to appreciate just how little of the potential
>>> for the bitcoin protocol is being exploited right now...
>>> not only in terms of the script features but in terms of the potential
>>> commands and node types that could exist.
>>> 
>>> For instance, the protocol spec at
>>> https://en.bitcoin.it/wiki/Protocol_specification only has 16 commands
>>> listed and
>>> only one service type...despite having a full 12 bytes for a command
>>> code and a full eight bytes for a services
>>> type.
>>> 
>>> The fact that only one node service type is specified is probably due
>>> to the fact that the satoshi client was written
>>> to be a standalone monolithic app that took care of all the essential
>>> needs for a network of peers.
>>> i.e. block chain storage/management, transaction signing/verification,
>>> key generation/wallet management, block mining, etc...
>>> However, I think there's an urgent need for breaking up all these
>>> different tasks into separate components that can run as independent
>>> services on different types of devices.
>>> 
>>> One of the big issues I'm dealing with now pertains to block chain
>>> storage. As of right now, it is implemented as sequential
>>> disk files using Berkeley DB in the satoshi client. Then you have
>>> other projects that have been using SQL tables, etc...
>>> But I believe the direction this really needs to move towards is some
>>> sort of distributed hash table...and the database queries
>>> should be performed using the bitcoin protocol itself. Perhaps adding
>>> a few more commands. As things stand right now,
>>> the only way to query for transactions or blocks is by their hash. And
>>> once a transaction gets incorporated into a block and
>>> removed from the transaction pool, one can no longer query it by the
>>> transaction hash without stepping outside the bitcoin protocol.
>>> We need access to the disk file that stores the blocks whether it be
>>> via Berkeley DB or SQL or whatever.
>>> 
>>> I propose an extension to the bitcoin protocol to provide methods for
>>> performing more sophisticated queries, such as "Give me
>>> an inventory of transactions involving this particular public key" or
>>> "Give me an inventory all transactions in the last n blocks with
>>> unredeemed outputs." This could be done by adding a few more commands.
>>> 
>>> Furthermore, I propose a new network services type for nodes that
>>> serve as block chain/transaction pool storage.
>>> 
>>> Of couse, any peer that wishes to verify the integrity of the block
>>> chain would still have to download at the very least
>>> all the block headers...and to be completely sure, also all the blocks
>>> themselves...and verify everything. But it would be
>>> very nice to be able to run thin services that can rely on other
>>> network peers to do this work. It is still possible to attain
>>> a high level of confidence in the integrity by querying multiple peers
>>> for similar objects and comparing. It is also possible
>>> to run your own dedicated block chain storage servers which you trust.
>>> 
>>> There are other ideas I have for other types of services, too.
>>> 
>>> Anyhow, I'm just throwing this out there...if anyone's interested I'd
>>> love to develop these ideas further and help put together some
>>> specs.
>>> 
>>> -Eric Lombrozo
>>> 
>>> ------------------------------------------------------------------------------
>>> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
>>> Microsoft is holding a special Learn Windows Azure training event for
>>> developers. It will provide a great way to learn Windows Azure and what it
>>> provides. You can attend the event by watching it streamed LIVE online.
>>> Learn more at http://p.sf.net/sfu/ms-windowsazure
>>> _______________________________________________
>>> Bitcoin-development mailing list
>>> Bitcoin-development@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>> 
>> 
>> 
>> ------------------------------------------------------------------------------
>> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
>> Microsoft is holding a special Learn Windows Azure training event for
>> developers. It will provide a great way to learn Windows Azure and what it
>> provides. You can attend the event by watching it streamed LIVE online.
>> Learn more at http://p.sf.net/sfu/ms-windowsazure
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>> 
>> 
>> 
>> ------------------------------------------------------------------------------
>> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
>> Microsoft is holding a special Learn Windows Azure training event for 
>> developers. It will provide a great way to learn Windows Azure and what it 
>> provides. You can attend the event by watching it streamed LIVE online.  
>> Learn more at 
>> http://p.sf.net/sfu/ms-windowsazure
>> 
>> 
>> _______________________________________________
>> Bitcoin-development mailing list
>> 
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 
> ------------------------------------------------------------------------------
> Learn Windows Azure Live!  Tuesday, Dec 13, 2011
> Microsoft is holding a special Learn Windows Azure training event for 
> developers. It will provide a great way to learn Windows Azure and what it 
> provides. You can attend the event by watching it streamed LIVE online.  
> Learn more at http://p.sf.net/sfu/ms-windowsazure
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Protocol extensions

[Eric Lombrozo]

Is it just me or does it seem inevitable that at some point supernodes
will emerge that other nodes trust to validate transactions for them?
Supernodes needn't even store the entire block chain and transaction
pool...it would be sufficient that they keep lists of IP addresses of
other trustworthy nodes and partition them into a hashspace.

Anonymous peers have no reputation to defend...but a trusted supernode
would, which could provide just enough incentive for the supernode to
do its best to ensure the nodes it vouches for are indeed legit. Of
course, unless the supernode is validating the entire block chain and
transaction pool itself, it could only assess the trustworthiness of
other nodes by performing random sampling.

Michael, I really like your ideas and the clarity you bring to the
issue. Regarding the potential attack vector you mention, would it be
possible to partition the hashspace to minimize the risk that an
attacker can manage to disproportionately gain control over a part of
the hashspace?

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

I find it likely that we will at some point have supernodes. If we have browser based wallets then the server for these automatically becomes supernodes. Further, if we move along that direction, it becomes much simpler to use both the scheme I proposed or to use a a lot of other schemes for sharing the validation work on a farm constituting the supernode.

However, if we want to keep bitcoin in a real p2p setup and enable scalability in terms of ensuring both thin and fat client to connect then we need to go along the path I propose.

Actually, after thinking a bit more about the possible new attack vector I don't find it that alarming - if you still require 7 confirmations of any bigger transaction before you, as receiver accepts the transaction as payed you will not risk anything. The question is then if it is sufficiently easy to fake small transaction to e.g. gain access to micropayment based web services. I would again say no - the requirement that you have ok from e.g. 8 different A.B nodes will make it extremely difficult to cheat, and that would even require you to gain some level of control over the network that the service you want to cheat is connected through.

This means that you should not divide the hash space more finely than you would at all times be able to find 8 different A.B nodes. As the number of clients grows you can then divide the hash space further. (with 100000 nodes today and a division into 512 parts you would have approx 200 nodes to choose from).

Cheers,

M



On 21/12/2011, at 12:42, Eric Lombrozo wrote:

> Is it just me or does it seem inevitable that at some point supernodes
> will emerge that other nodes trust to validate transactions for them?
> Supernodes needn't even store the entire block chain and transaction
> pool...it would be sufficient that they keep lists of IP addresses of
> other trustworthy nodes and partition them into a hashspace.
> 
> Anonymous peers have no reputation to defend...but a trusted supernode
> would, which could provide just enough incentive for the supernode to
> do its best to ensure the nodes it vouches for are indeed legit. Of
> course, unless the supernode is validating the entire block chain and
> transaction pool itself, it could only assess the trustworthiness of
> other nodes by performing random sampling.
> 
> Michael, I really like your ideas and the clarity you bring to the
> issue. Regarding the potential attack vector you mention, would it be
> possible to partition the hashspace to minimize the risk that an
> attacker can manage to disproportionately gain control over a part of
> the hashspace?
> 
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app development. Create 
> new or port existing apps to sell to consumers worldwide. Explore the 
> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Protocol extensions

[Christian Decker]

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

For the future evolution without considering DHTs:
While I think we will sooner or later have supernodes, I don't think they
will need to be trusted too much.
Supernodes will be those nodes that verify all transactions and make them
available to miners. Since miners will become more and more specialized
these supernodes are likely to be owned by the miners themself. To be a
miner either you need to verify all the transactions you include (otherwise
others might be able to find an error in your block and thus drop it) or
have someone that verifies them for you. In the end I think we'll end up
with a hierarchical network, with the miners/supernodes tighly
interconnected at the top and the lightweight clients that simply verify
transactions (or their inputs to be precise) that are destined for them at
the bottom.

As for the DHT we had a few brainstorming sessions a while back on the
forum http://bit.ly/sc2RLZ (gmaxwell didn't like it then either :D)
Forcing someone to participate in a fixed position in the block storage
network is a good way to reduce the risk of a sybil attack as Michael said.
The hash should include only information that cannot be changed by the
user, so IP can be used, but including the port is risky.

Broadcasting the transactions would not need to be done, since miners fetch
them from their storage place, alternatively we could use the inv broadcast
to notify peers about a new block/transaction and let it retrieve them from
the permanent storage (DHT or block storage network). If we route traffic
internally in the DHT we could even start caching at nodes leading to the
real location, since announcements would lead to flashcrowds, putting heavy
load on the responsible nodes. Caching is not a risk since the hash of the
object to be retrieved is already known.

Regards,
Chris

On Wed, Dec 21, 2011 at 1:41 PM, Michael Grønager <gronager@ceptacle.com>wrote:

> I find it likely that we will at some point have supernodes. If we have
> browser based wallets then the server for these automatically becomes
> supernodes. Further, if we move along that direction, it becomes much
> simpler to use both the scheme I proposed or to use a a lot of other
> schemes for sharing the validation work on a farm constituting the
> supernode.
>
> However, if we want to keep bitcoin in a real p2p setup and enable
> scalability in terms of ensuring both thin and fat client to connect then
> we need to go along the path I propose.
>
> Actually, after thinking a bit more about the possible new attack vector I
> don't find it that alarming - if you still require 7 confirmations of any
> bigger transaction before you, as receiver accepts the transaction as payed
> you will not risk anything. The question is then if it is sufficiently easy
> to fake small transaction to e.g. gain access to micropayment based web
> services. I would again say no - the requirement that you have ok from e.g.
> 8 different A.B nodes will make it extremely difficult to cheat, and that
> would even require you to gain some level of control over the network that
> the service you want to cheat is connected through.
>
> This means that you should not divide the hash space more finely than you
> would at all times be able to find 8 different A.B nodes. As the number of
> clients grows you can then divide the hash space further. (with 100000
> nodes today and a division into 512 parts you would have approx 200 nodes
> to choose from).
>
> Cheers,
>
> M
>
>
>
> On 21/12/2011, at 12:42, Eric Lombrozo wrote:
>
> > Is it just me or does it seem inevitable that at some point supernodes
> > will emerge that other nodes trust to validate transactions for them?
> > Supernodes needn't even store the entire block chain and transaction
> > pool...it would be sufficient that they keep lists of IP addresses of
> > other trustworthy nodes and partition them into a hashspace.
> >
> > Anonymous peers have no reputation to defend...but a trusted supernode
> > would, which could provide just enough incentive for the supernode to
> > do its best to ensure the nodes it vouches for are indeed legit. Of
> > course, unless the supernode is validating the entire block chain and
> > transaction pool itself, it could only assess the trustworthiness of
> > other nodes by performing random sampling.
> >
> > Michael, I really like your ideas and the clarity you bring to the
> > issue. Regarding the potential attack vector you mention, would it be
> > possible to partition the hashspace to minimize the risk that an
> > attacker can manage to disproportionately gain control over a part of
> > the hashspace?
> >
> >
> ------------------------------------------------------------------------------
> > Write once. Port to many.
> > Get the SDK and tools to simplify cross-platform app development. Create
> > new or port existing apps to sell to consumers worldwide. Explore the
> > Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> > http://p.sf.net/sfu/intel-appdev
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>
>
>
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app development. Create
> new or port existing apps to sell to consumers worldwide. Explore the
> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

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

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

> 
> As for the DHT we had a few brainstorming sessions a while back on the forum http://bit.ly/sc2RLZ (gmaxwell didn't like it then either :D)
> Forcing someone to participate in a fixed position in the block storage network is a good way to reduce the risk of a sybil attack as Michael said. The hash should include only information that cannot be changed by the user, so IP can be used, but including the port is risky.

Agree, that is why we need to keep the different A.B segment requirement as is also imposed in the client today.

> 
> Broadcasting the transactions would not need to be done, since miners fetch them from their storage place, alternatively we could use the inv broadcast to notify peers about a new block/transaction and let it retrieve them from the permanent storage (DHT or block storage network). If we route traffic internally in the DHT we could even start caching at nodes leading to the real location, since announcements would lead to flashcrowds, putting heavy load on the responsible nodes. Caching is not a risk since the hash of the object to be retrieved is already known.

I agree that in practice the thinner nodes would most likely just serve as cache, but they need notification on tx'es involving some of their tx outs or involving some of theirs bitcoin addresses. Today there are some designs that operate with a thin client that connects to a (web)server and subscribe to listen for transactions involving a specific bitcoin address. By letting that be a part of the hash space including that address you would not reveal your address to the server and we would keep a true p2p setup.

Best regards,

Michael

> 
> Regards,
> Chris
> 
> On Wed, Dec 21, 2011 at 1:41 PM, Michael Grønager <gronager@ceptacle.com> wrote:
> I find it likely that we will at some point have supernodes. If we have browser based wallets then the server for these automatically becomes supernodes. Further, if we move along that direction, it becomes much simpler to use both the scheme I proposed or to use a a lot of other schemes for sharing the validation work on a farm constituting the supernode.
> 
> However, if we want to keep bitcoin in a real p2p setup and enable scalability in terms of ensuring both thin and fat client to connect then we need to go along the path I propose.
> 
> Actually, after thinking a bit more about the possible new attack vector I don't find it that alarming - if you still require 7 confirmations of any bigger transaction before you, as receiver accepts the transaction as payed you will not risk anything. The question is then if it is sufficiently easy to fake small transaction to e.g. gain access to micropayment based web services. I would again say no - the requirement that you have ok from e.g. 8 different A.B nodes will make it extremely difficult to cheat, and that would even require you to gain some level of control over the network that the service you want to cheat is connected through.
> 
> This means that you should not divide the hash space more finely than you would at all times be able to find 8 different A.B nodes. As the number of clients grows you can then divide the hash space further. (with 100000 nodes today and a division into 512 parts you would have approx 200 nodes to choose from).
> 
> Cheers,
> 
> M
> 
> 
> 
> On 21/12/2011, at 12:42, Eric Lombrozo wrote:
> 
>> Is it just me or does it seem inevitable that at some point supernodes
>> will emerge that other nodes trust to validate transactions for them?
>> Supernodes needn't even store the entire block chain and transaction
>> pool...it would be sufficient that they keep lists of IP addresses of
>> other trustworthy nodes and partition them into a hashspace.
>> 
>> Anonymous peers have no reputation to defend...but a trusted supernode
>> would, which could provide just enough incentive for the supernode to
>> do its best to ensure the nodes it vouches for are indeed legit. Of
>> course, unless the supernode is validating the entire block chain and
>> transaction pool itself, it could only assess the trustworthiness of
>> other nodes by performing random sampling.
>> 
>> Michael, I really like your ideas and the clarity you bring to the
>> issue. Regarding the potential attack vector you mention, would it be
>> possible to partition the hashspace to minimize the risk that an
>> attacker can manage to disproportionately gain control over a part of
>> the hashspace?
>> 
>> ------------------------------------------------------------------------------
>> Write once. Port to many.
>> Get the SDK and tools to simplify cross-platform app development. Create
>> new or port existing apps to sell to consumers worldwide. Explore the
>> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
>> http://p.sf.net/sfu/intel-appdev
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app development. Create
> new or port existing apps to sell to consumers worldwide. Explore the
> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] Protocol extensions

[Andy Parkins]

[-- Attachment #1: Type: Text/Plain, Size: 1917 bytes --]

On 2011 December 21 Wednesday, Christian Decker wrote:

> Supernodes will be those nodes that verify all transactions and make them
> available to miners. Since miners will become more and more specialized
> these supernodes are likely to be owned by the miners themself. To be a
> miner either you need to verify all the transactions you include (otherwise
> others might be able to find an error in your block and thus drop it) or
> have someone that verifies them for you. In the end I think we'll end up
> with a hierarchical network, with the miners/supernodes tighly
> interconnected at the top and the lightweight clients that simply verify
> transactions (or their inputs to be precise) that are destined for them at
> the bottom.

A thought occurred to me.  We already run a decentralised system, but it's 
done by making everyone duplicate all other work.  There is no fundamental 
reason why all work needs to be duplicated though.  What about this: every 
node randomly chooses whether to verify any particular transaction.  If we 
assume the network is large and the random factor is correctly chosen, then we 
can still guarantee that every transaction is verified.  Then, we simply add a 
protocol message that is a negative-announce transaction.  That is to say, we 
give nodes a way of telling other nodes that they think a transaction is 
invalid.  The other nodes are then free to verify _that_ assertion and forward 
the negative-announce.

Miners can then listen for negative-announcements and use them to decide were 
to dedicate their verification efforts.  They then don't need to verify all 
(or perhaps even any) transactions themselves and can dedicate their 
processing power to mining.

(I've actually mentioned this idea before, but that time I was using it as a 
double-spend prevention method).



Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

It is analog to getting assigned a random part (based on IP) of the hashspace and then only verify transactions within this fraction.

But, there is in fact a subtle difference: If anyone can choose to verify at random, you will see lazy implementations where random means none, and as it is random you cannot, from the outside, judge if a node is taking part in the validation work or if it just benefitting from others announcements. In the hash space part, you can monitor peers and see if they did not tell you about a failed validation and then disconnect from them as they are either malicious or lazy.

Besides from that, I like a setup where we scream about failed verifications, but keep a low profile on things that actually verifies...

/M


On 22/12/2011, at 11:12, Andy Parkins wrote:

> On 2011 December 21 Wednesday, Christian Decker wrote:
> 
>> Supernodes will be those nodes that verify all transactions and make them
>> available to miners. Since miners will become more and more specialized
>> these supernodes are likely to be owned by the miners themself. To be a
>> miner either you need to verify all the transactions you include (otherwise
>> others might be able to find an error in your block and thus drop it) or
>> have someone that verifies them for you. In the end I think we'll end up
>> with a hierarchical network, with the miners/supernodes tighly
>> interconnected at the top and the lightweight clients that simply verify
>> transactions (or their inputs to be precise) that are destined for them at
>> the bottom.
> 
> A thought occurred to me.  We already run a decentralised system, but it's 
> done by making everyone duplicate all other work.  There is no fundamental 
> reason why all work needs to be duplicated though.  What about this: every 
> node randomly chooses whether to verify any particular transaction.  If we 
> assume the network is large and the random factor is correctly chosen, then we 
> can still guarantee that every transaction is verified.  Then, we simply add a 
> protocol message that is a negative-announce transaction.  That is to say, we 
> give nodes a way of telling other nodes that they think a transaction is 
> invalid.  The other nodes are then free to verify _that_ assertion and forward 
> the negative-announce.
> 
> Miners can then listen for negative-announcements and use them to decide were 
> to dedicate their verification efforts.  They then don't need to verify all 
> (or perhaps even any) transactions themselves and can dedicate their 
> processing power to mining.
> 
> (I've actually mentioned this idea before, but that time I was using it as a 
> double-spend prevention method).
> 
> 
> 
> Andy
> 
> -- 
> Dr Andy Parkins
> andyparkins@gmail.com

Re: [Bitcoin-development] Protocol extensions

[Andy Parkins]

[-- Attachment #1: Type: Text/Plain, Size: 1497 bytes --]

On 2011 December 22 Thursday, Michael Grønager wrote:

> But, there is in fact a subtle difference: If anyone can choose to verify
> at random, you will see lazy implementations where random means none, and
> as it is random you cannot, from the outside, judge if a node is taking
> part in the validation work or if it just benefitting from others
> announcements. In the hash space part, you can monitor peers and see if
> they did not tell you about a failed validation and then disconnect from
> them as they are either malicious or lazy.

Why should they have to?  Joining the network as a node is very low cost to 
the other nodes.  You can't force any node not to be lazy, since their option 
is to disconnect themselves.  As to maliciousness, that is defended against 
because when a node negative announces a transaction, that transaction is 
going to be checked (note that there is still no implicit trust) -- if a node 
is incorrectly negative-announcing then it can justifiably be kicked.

> Besides from that, I like a setup where we scream about failed
> verifications, but keep a low profile on things that actually verifies...

Me too.  It's important though to distinguish between "you must be verifying" 
and "if you do verify, you must be honest about it".  No node should be forced 
to do any work it doesn't want to; but they should be forced to be truthful 
about the work they choose to do.



Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Protocol extensions

[Joel Joonatan Kaartinen]

On Thu, 2011-12-22 at 11:52 +0000, Andy Parkins wrote:
> Why should they have to?  Joining the network as a node is very low cost to 
> the other nodes.  You can't force any node not to be lazy, since their option 
> is to disconnect themselves.  As to maliciousness, that is defended against 
> because when a node negative announces a transaction, that transaction is 
> going to be checked (note that there is still no implicit trust) -- if a node 
> is incorrectly negative-announcing then it can justifiably be kicked.

a node that is not doing any checking themselves can not reliably
forward failed verifications without getting the blame for doing faulty
work. Those nodes would then have the incentive not to relay the failed
verifications. This ends up making it important to know which nodes will
be checking transactions or not so you don't isolate yourself from other
nodes that are also checking transactions.

- Joel

Re: [Bitcoin-development] Protocol extensions

[Christian Decker]

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

At first the idea of using negative announces seems attractive, but
remember that a malicious node might trigger verification for every
transaction, which may lead to a DoS.

Regards,
Chris

On Thu, Dec 22, 2011 at 1:14 PM, Joel Joonatan Kaartinen <
joel.kaartinen@gmail.com> wrote:

> On Thu, 2011-12-22 at 11:52 +0000, Andy Parkins wrote:
> > Why should they have to?  Joining the network as a node is very low cost
> to
> > the other nodes.  You can't force any node not to be lazy, since their
> option
> > is to disconnect themselves.  As to maliciousness, that is defended
> against
> > because when a node negative announces a transaction, that transaction is
> > going to be checked (note that there is still no implicit trust) -- if a
> node
> > is incorrectly negative-announcing then it can justifiably be kicked.
>
> a node that is not doing any checking themselves can not reliably
> forward failed verifications without getting the blame for doing faulty
> work. Those nodes would then have the incentive not to relay the failed
> verifications. This ends up making it important to know which nodes will
> be checking transactions or not so you don't isolate yourself from other
> nodes that are also checking transactions.
>
> - Joel
>
>
>
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app development. Create
> new or port existing apps to sell to consumers worldwide. Explore the
> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

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

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

Just adding to Joels comment:

The only one with an incentive to do validations are miners (otherwise they could risk having their mined blocks invalidated later by less lazy miners) and the ones who are to send and accept a transaction. In a distributed stored and validated block chain setup, you would hence need to ask some miners if the inputs to a transaction is valid or download all the chain yourselves.

The latter is what we do today and will not scale, the former is the logical consequence of a non-enforced random validation approach - so this will give us super nodes, namely miners, and at some point they could choose to also charge for the validations. It might be the direction we are moving towards, but then the p2p network is only for the miners and the rest of us can connect through https and use json-rpc to post transactions etc to them. I do, however, prefer a setup where we keep everything really distributed...

/M

On 22/12/2011, at 13:14, Joel Joonatan Kaartinen wrote:

> On Thu, 2011-12-22 at 11:52 +0000, Andy Parkins wrote:
>> Why should they have to?  Joining the network as a node is very low cost to 
>> the other nodes.  You can't force any node not to be lazy, since their option 
>> is to disconnect themselves.  As to maliciousness, that is defended against 
>> because when a node negative announces a transaction, that transaction is 
>> going to be checked (note that there is still no implicit trust) -- if a node 
>> is incorrectly negative-announcing then it can justifiably be kicked.
> 
> a node that is not doing any checking themselves can not reliably
> forward failed verifications without getting the blame for doing faulty
> work. Those nodes would then have the incentive not to relay the failed
> verifications. This ends up making it important to know which nodes will
> be checking transactions or not so you don't isolate yourself from other
> nodes that are also checking transactions.
> 
> - Joel
> 

Michael Gronager, PhD
Owner Ceptacle / NDGF Director, NORDUnet A/S
Jens Juels Gade 33
2100 Copenhagen E
Mobile: +45 31 62 14 01
E-mail: gronager@ceptacle.com

Re: [Bitcoin-development] Protocol extensions

[Andy Parkins]

[-- Attachment #1: Type: Text/Plain, Size: 2141 bytes --]

On 2011 December 22 Thursday, Joel Joonatan Kaartinen wrote:
> On Thu, 2011-12-22 at 11:52 +0000, Andy Parkins wrote:
> > Why should they have to?  Joining the network as a node is very low cost
> > to the other nodes.  You can't force any node not to be lazy, since
> > their option is to disconnect themselves.  As to maliciousness, that is
> > defended against because when a node negative announces a transaction,
> > that transaction is going to be checked (note that there is still no
> > implicit trust) -- if a node is incorrectly negative-announcing then it
> > can justifiably be kicked.
> 
> a node that is not doing any checking themselves can not reliably
> forward failed verifications without getting the blame for doing faulty
> work. Those nodes would then have the incentive not to relay the failed
> verifications. This ends up making it important to know which nodes will
> be checking transactions or not so you don't isolate yourself from other
> nodes that are also checking transactions.

Yes; I appreciate that.  It's the very point I'm making.  A node can choose 
what work to do, and should have a way of forwarding the results of that work 
to other nodes.  Transaction verifification is the main one.

Once a negative-announce message exists, it wouldn't be hard to have the other 
two you need as well: positive-announce and neutral-announce.  At present we 
have only neutral-announce.  However, as the need for super nodes and 
distributed verification gets bigger, having the forwarder able to offer an 
opinion on the quality of a transaction seems ideal to me.  Dishonesty will 
get you isolated pretty quickly if you use positive-announce and negative-
announce to lie.

The problem with this is that it requires a web of trust as well as a web of 
connections.  The only way to gain an advantage from this classified 
forwarding is if you have some way of assigning enough trust so that you can 
forward a classified transaction _without_ checking it yourself.  That doesn't 
sound like an easy problem though.



Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Bitcoin-development] Protocol extensions

[Zell Faze]

I may be missing something, but perhaps the simplistic method is the best.  

Start all nodes off with a certain level of trust.  Lets choose an arbitrary number 5.
If a node's trust level is high enough (lets say 10) forward transactions it sends you without checking them.
If a node's trust level is low enough (lets say 0) discard any transactions they send you (i.e. don't forward them on).
For nodes with a trust level between 1 and 9, forward without checking between 1 and 9 out of every 10 transactions.  Check the others, if they are valid, increase the trust level by 1, if they are invalid decrease the trust level by 3.

All of the numbers mentioned here (1-10, 1, 10, 1, 5, and 3) are arbitrary numbers that should be determined by the client or user-preferences instead of the protocol.  This would allow for clients to have varying amounts of initial trust/paranoia about their peers.

By decreasing the amount of trust faster than we increase it, we make it harder for untrustworthy clients to cheat us.  By having a cut off point, we make it so that untrustworthy clients can not DDoS us.  By randomly verifying some transactions in the beginning, we make it harder for a new client from DDoSing us, and we prevent our own trust level from being hurt too much for forwarding on invalid transactions.

The only problem I can personally see with this system is that if Node A trusts Node B with a 10 and Node C connects to Node A, then Node C can send  transactions that are invalid to Node C via Node A without Node C being any the wiser.  This would be stopped fairly quickly as Node B would catch on and stop forwarding transactions, but it would be a problem for new Nodes.

This could be fixed (somewhat) by having a message that says not to trust a particular node.

--Zell Faze



--- On Thu, 12/22/11, Andy Parkins <andyparkins@gmail.com> wrote:

> From: Andy Parkins <andyparkins@gmail.com>
> Subject: Re: [Bitcoin-development] Protocol extensions
> To: "Joel Joonatan Kaartinen" <joel.kaartinen@gmail.com>
> Cc: bitcoin-development@lists.sourceforge.net
> Date: Thursday, December 22, 2011, 9:46 AM
> On 2011 December 22 Thursday, Joel
> Joonatan Kaartinen wrote:
> > On Thu, 2011-12-22 at 11:52 +0000, Andy Parkins
> wrote:
> > > Why should they have to?  Joining the
> network as a node is very low cost
> > > to the other nodes.  You can't force any
> node not to be lazy, since
> > > their option is to disconnect themselves. 
> As to maliciousness, that is
> > > defended against because when a node negative
> announces a transaction,
> > > that transaction is going to be checked (note
> that there is still no
> > > implicit trust) -- if a node is incorrectly
> negative-announcing then it
> > > can justifiably be kicked.
> > 
> > a node that is not doing any checking themselves can
> not reliably
> > forward failed verifications without getting the blame
> for doing faulty
> > work. Those nodes would then have the incentive not to
> relay the failed
> > verifications. This ends up making it important to
> know which nodes will
> > be checking transactions or not so you don't isolate
> yourself from other
> > nodes that are also checking transactions.
> 
> Yes; I appreciate that.  It's the very point I'm
> making.  A node can choose 
> what work to do, and should have a way of forwarding the
> results of that work 
> to other nodes.  Transaction verifification is the
> main one.
> 
> Once a negative-announce message exists, it wouldn't be
> hard to have the other 
> two you need as well: positive-announce and
> neutral-announce.  At present we 
> have only neutral-announce.  However, as the need for
> super nodes and 
> distributed verification gets bigger, having the forwarder
> able to offer an 
> opinion on the quality of a transaction seems ideal to
> me.  Dishonesty will 
> get you isolated pretty quickly if you use
> positive-announce and negative-
> announce to lie.
> 
> The problem with this is that it requires a web of trust as
> well as a web of 
> connections.  The only way to gain an advantage from
> this classified 
> forwarding is if you have some way of assigning enough
> trust so that you can 
> forward a classified transaction _without_ checking it
> yourself.  That doesn't 
> sound like an easy problem though.
> 
> 
> 
> Andy
> 
> -- 
> Dr Andy Parkins
> andyparkins@gmail.com
> 
> -----Inline Attachment Follows-----
> 
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app
> development. Create 
> new or port existing apps to sell to consumers worldwide.
> Explore the 
> Intel AppUpSM program developer opportunity.
> appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> -----Inline Attachment Follows-----
> 
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Re: [Bitcoin-development] Protocol extensions

[Jordan Mack]

I think it would be a lot more than that. According to the Scalability 
page (https://en.bitcoin.it/wiki/Scalability) if Bitcoin took over all 
credit card transactions, that would be about 1.14GB per block. I 
believe that is 58.5PB per year. (6*24*365*1.14/1024) This would also 
mean the distribution of 2MB of block data per second, which doesn't 
include broadcast overhead.

On 12/21/2011 12:50 AM, Michael Grønager wrote:
> when bitcoin takes over all credit card transactions (!), and even before that,
 > we will meet a scalability problem. The blockchain will grow rapidly,
> (1MB/10min  or 50GB/yr)

Re: [Bitcoin-development] Protocol extensions

[Michael Grønager]

Agree, but even before that, we will meet problems of the current 1MB/10min limit.

The calculations from the scalability link surely indicates that there are 2 options for scalability either go for trusted supernodes backed by huge hardware resources or something else would be needed. The supernode approach is simple and easy to implement, but it also breaks a lot of the nice features about bitcoin. So if we want bitcoin to stay p2p we need to deploy other strategies. The hash space partitioning is one of them. And the nice thing is that it can be made to scale even for a javascript based validating and fully connected client running on a smartphone in a bitcoin future with billions of clients and transactions, and still it does not exclude you from running a trusted supernode either. 

Cheers,

M

On 21/12/2011, at 18:17, Jordan Mack wrote:

> I think it would be a lot more than that. According to the Scalability 
> page (https://en.bitcoin.it/wiki/Scalability) if Bitcoin took over all 
> credit card transactions, that would be about 1.14GB per block. I 
> believe that is 58.5PB per year. (6*24*365*1.14/1024) This would also 
> mean the distribution of 2MB of block data per second, which doesn't 
> include broadcast overhead.
> 
> On 12/21/2011 12:50 AM, Michael Grønager wrote:
>> when bitcoin takes over all credit card transactions (!), and even before that,
>> we will meet a scalability problem. The blockchain will grow rapidly,
>> (1MB/10min  or 50GB/yr)
> 
> ------------------------------------------------------------------------------
> Write once. Port to many.
> Get the SDK and tools to simplify cross-platform app development. Create 
> new or port existing apps to sell to consumers worldwide. Explore the 
> Intel AppUpSM program developer opportunity. appdeveloper.intel.com/join
> http://p.sf.net/sfu/intel-appdev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development