latency and locality

[Red]

What I'm suggesting doesn't exist yet. There was related talk about similar issues on the thermodynamic perversity of generating blocks. If I have just one central node, the system could generate a transaction block in a fraction of a second. If you wanted, it could do this only once every ten minutes. But it wouldn't need any more than a fraction of a second of CPU time on a single processor.

The reason is purely related to consensus.

So if you had two nodes, you could have them both redundantly capture all transactions, and then in a fraction of a second each could generate a block. They could then exchange block hashes and if they matched, they would have consensus. If they didn't match you could reach consensus in one of two ways. 1) compare the transactions of each block one by one, and create a block consisting of the union of all transactions. or 2) Just pick one of the blocks and go with it. The second is what bitcoin actually does now.

It just picks using the worlds most expensive coin flipper. You could accomplish the same task with a much cheaper coin flipper and nothing in bitcoin would change one bit.

That is what I mean by "design decision" a it doesn't change any of the requirements for the system's features or behavior. It just implements things differently.

----

So when I talk about distributing the transaction graph throughout a distributed hash table it is just a different possible (but currently non-coded) way of implementing bitcoin's key feature. The feature of verifying the transfer of bitcoins from one address to another, in a way that makes it impossible to double spend coins.

Optimally, if you had x,000 transactions per minute and 100 nodes, each node would only have to do 1/100th of the work of a single node handling x,000 transactions per minute. Each transaction is only required to be recorded once.

However, with the current bitcoin implementation, if you have 100 nodes, they all run at 100% cpu for x,000 transactions. If you add another 100 nodes, they all still run at 100% cpu but do exactly the same job. We used to call it "government work" when you could do a job with 5 guys, but instead they used 50 guys, because more people working is better for the economy!

So the new design constraint I'm proposing, is that for a given number of nodes (n), it should take (Order (1/n)) or maybe (Order log(n)) work per cpu to handle a given number of transactions. In this case work means CPU time and network communication. My design modifications FAIL if they give up any of the transaction protections of the existing system.

----

It turns out that the block list itself is not required to validate transactions. Only the transactions are required. So to understand what I'm suggesting you have to think about an equivalent bitcoin implementation without a monolithic block list containing every transaction in the history of the system.

Instead, the transactions are redundantly scattered across all the nodes. No node need keep a complete list off all transactions, but they must be able to quickly retrieve any transaction on demand. Optimally in Order(1) time, but Order(log(n) time would probably suffice. That reduces the storage requirements of any given node to Order(1/n).

Transactions are mapped to nodes by transaction out-points. You generate two unique out-point identifiers by hashing the transaction+out-point information. You then store the transaction redundantly on the five "closest nodes" to each out-point ID. That means for a system with 10,000 nodes. Each transaction is stored with 10X redundancy instead of 10,000X redundancy. (the 10X was an arbitrary choice, the redundancy would be based upon the DHT algorithm and characteristics of the node population.)

Now each of those 10 nodes holds that out-point data completely privately, unless another node can show a "need to know". In this case a need to know is demonstrated by submitting a signed transaction that includes a given out-point as an in-point. In this case the storage node stores the new transaction. It also returns any known transactions referencing that out-point. If there is a previous transaction in-point associated with the out-point the second transaction is a double spend.

So for any new transaction, to verify it, you send it to the five closest nodes to each in-point on the transaction. They record the transaction and immediately tell you if they've seen a double spend. If any have, it's a bogus transaction, which gets broadcast to the other close nodes.

Now the what I'm suggesting also increases anonymity because you no longer have to broadcast every transaction you make to the world. Also random individuals can't go poking around in your business.

There are many ways to map bitcoin transactions to DHTs. I just chose an example that would be easy to explain. There may be other possibilities offer improvement. But this one is sufficient to get the point across.

There is also a fun technology called a "dining cryptographers network" that could further improve some of the anonymity aspects of bitcoin.

[Gavin Andresen]

So for any new transaction, to verify it, you send it to the five closest nodes to each in-point on the transaction. They record the transaction and immediately tell you if they've seen a double spend. If any have, it's a bogus transaction, which gets broadcast to the other close nodes.

What happens when they disagree about which transaction happened first?  Majority rule?  Who decides what the majority is, and can it change if 4 of the five nodes leave the network and are replaced by another 5 nodes?

And if I know that I'm going to create a large transaction, can I do some work precomputing node IDs such that the transaction (which I haven't yet sent out) will hash to nodes that I control?   If I control all the nodes storing the transaction, then I can just answer "yes, absolutely, that transaction is valid and hasn't been double-spent..."

The brilliant insight behind bitcoin is the distributed timestamping mechanism; everybody agrees on an order of transactions.  I don't see how your scheme solves that problem.

[MoonShadow]

Imagine this picture...

You have a full client on your Iphone running in the background, and then there is a power failure.  You head down to the corner store, and find that the shopkeeper has put everything in the cooler on sale half price, cash or bitcoins only.  Your cellphone client connects with the shopkeeper's cell phone client over ad-hoc bluetooth.  Signs the transfer accouncement (there are no actual cryptocoins in your wallet, they exist only as a series of entries into an encrypted ledger we call the blockchain, more like writing a check than actual coins) over to the shopkeeper's address.  Shopkeeper's client can then (but does not have to) check his copy of the blockchain to verify that you actually owned said bitcoins at the time of his last blockchain update.  If it's good locally, he can assume that you are not trying to cheat him and accept the trade and you leave with your half priced milk.  This does not protect the shopkeeper from an intentional double spend, but you still had to have honestly owned the coins at one time in order to do this.  If you did not own the coins at the time the power went out, his client would have rejected the transfer.

There was another point here that I intended to make.

As with the example above, most cash transactions are not actually anonymous, but psuedo-anonymous.  For example, one party can be well established (the shopkeeper) while the other is mostly anonymous, (the bargain hunter in the above example) but even the buyer is not truely anonymous.  He has been in the shop many times before, and even if the shopkeeper doesn't know his name, he has seen his face enough times to recognize it.  So there is some trust that, since he is a local or regular customer, that he is not some pro trying to sting him with an opprotunistic scam.

Another example of a psuedo-anonymous transaction is the kind that both parties are anonymous to the world, but not to each other.  This is actually how *most* cash transactions work in the real world; but online it could go like this...

You want to get something, let's say, unusual.  You find this guy on, say, Tor with a hidden website selling your wanted commodity.  He is known to you only as, "pothead420" on the website.  You have no other way to contact him, and no means of finding out who is actually is.  You don't trust this guy, but someone is going to have to take a leap of faith, and that someone is likely going to be you.  So at first, you order small.  After a few succesful trades, your trust grows that "pothead420" is an honest dealer; so your orders grow larger.  He could screw you over at any time without recourse, but then he would be cutting off a regular customer, so he has an incentive to continue to treat you properly.


A third kind of pseudo-anonymous trust relationship could be found on this very forum that depends on reputation.  Most of us do not use our real names, but some of us do.  We assume that the member who uses the name of the bitcoin programmer is the actual programmer, and have some evidence to support this, but we cannot know for sure.  But, as far as this forum is concerned, he has a reputation.  So if you were to do direct business with him, and screw him, his word that you are not trustworthly would harm any business that you desired to conduct in the future, solely because he has a longer reputation than any newcomer.


All of these examples involve some kind of two party trust, but not one requires both parties trust a third.  Not even the verification of the blockchain.

[NewLibertyStandard]

All of these examples involve some kind of two party trust, but not one requires both parties trust a third.  Not even the verification of the blockchain.

Trusted third parties are very useful when trading with someone you don't trust. One person trusts the trading administrator enough to deposit bitcoins and the other person trusts a payment processor such as Liberty Reserve or Pecunix to provide proof to the trading administrator that the payment occurred and he trust the trading site administrator that he'll accept proof of payment. Both traders have to trust the trading site and the payment processor, both third parties, but they don't need to trust each other.

[Red]

If you look for reasons to dismiss the idea out of hand, you will find them. However if you use the example to increase your understanding of why some P2P systems succeed yet many more fail, it will give you some insight.

In that spirit, let me answer your questions directly.

What happens when they disagree about which transaction happened first?  Majority rule?  Who decides what the majority is, and can it change if 4 of the five nodes leave the network and are replaced by another 5 nodes?

If ANY other transaction using that out-point is found there is a double spend, same rules as the current bitcoin system. The only way there can be disagreement is conflicting transactions got broadcast simultaneously but one arrived a close node A first and the conflicting one arrived at close node E first. By the end of the two 5 node broadcasts, both parties would discover the double spend.

So which one is valid? Who cares. Flip a coin. That is exactly what bitcoin does in this situation. If my node is working on a block with on transaction, and your node is working on a block with a conflicting transaction, whoever solves the block first wins. Distributed coin flipping algorithms are trivial. All of this can be done almost immediately. Much faster than in 10 minute windows. So no, the majority doesn't change if 4 nodes leave, because consensus was reached and the nodes were made consistent.

By the way, standard DHTs already address preserving data when nodes leave, and spreading the data when nodes join.

And if I know that I'm going to create a large transaction, can I do some work precomputing node IDs such that the transaction (which I haven't yet sent out) will hash to nodes that I control?   If I control all the nodes storing the transaction, then I can just answer "yes, absolutely, that transaction is valid and hasn't been double-spent..."

No, this would be a requirement constraint. It is possible for the same reason that it is impossible to generate two public keys that match to the same bitcoin address. See my previous faux pas.

Nodes would generate node addresses based upon private keys, exactly as is being done for bitcoin addresses. This makes node spoofing implausible. All of the inputs to the out-point hash are fixed except the payee, which is pre-specified. The only flexibility I can think of would be in the payment amount. If you want to iterate through all possible amounts and try to create a simultaneous 5 way hash collision, knock yourself out.

The brilliant insight behind bitcoin is the distributed timestamping mechanism; everybody agrees on an order of transactions.  I don't see how your scheme solves that problem.

It actually solves the problem in exactly the same way, just with much less CPU power.

The brilliant insight behind bitcoin's distributed time stamping mechanism is you don't need absolute timestamps at all! You only need relative order. And for conflicts in a short window, you don't have to care at all. You can simply arbitrarily choose one.

My solution does exactly the same thing. It maintains relative order among transactions. It arbitrarily reaches consensus on conflicts. Neither method has a requirement to accurately order unrelated transactions by time. Again, that was a brilliant insight.

[Gavin Andresen]

So which one is valid? Who cares. Flip a coin. That is exactly what bitcoin does in this situation. If my node is working on a block with on transaction, and your node is working on a block with a conflicting transaction, whoever solves the block first wins.

Now I'm confused again.  I thought your scheme didn't have blocks, just transactions.  What do you mean, whoever solves "the block" first?

By the way, standard DHTs already address preserving data when nodes leave, and spreading the data when nodes join.

But standard DHTs are typically used to store chunks of MP3s or movies, indexed by a torrent file that has the hash for every piece.  So it is easy for me to tell whether or not I'm getting bad data from any particular DHT node.  I don't have to trust them.

Nodes would generate node addresses based upon private keys, exactly as is being done for bitcoin addresses. This makes node spoofing implausible.

Huh?  Lets say the network has 10,000 nodes in it.  I query the network to find the network node closest to a transaction that I want to double-spend.

So I generate a private key.  It has about a 1 in 10,000 chance of being closer than the current closest node.  So I keep generating private keys until I have 5 that are closer.  It's too late for me to figure out the odds, but lets say I generate 100,000 private keys, I'm pretty darn likely to find 5.  My wimpy laptop can generate at LEAST 100 ECC keys/second, so in under 20 minutes it could generate 100,000.

I create 5 nodes with those keys (telling the rest of the network "honest, folks, I chose those keys RANDOMLY...") and I've won.

All of the inputs to the out-point hash are fixed except the payee, which is pre-specified. The only flexibility I can think of would be in the payment amount. If you want to iterate through all possible amounts and try to create a simultaneous 5 way hash collision, knock yourself out.

I'm not trying to generate a transaction with a particular hash, I'm trying to generate node ids that are "closer" to that transaction's hash than any other node currently on the network.  That's much easier.

[MoonShadow]

All of these examples involve some kind of two party trust, but not one requires both parties trust a third.  Not even the verification of the blockchain.

Trusted third parties are very useful when trading with someone you don't trust.

Yes, but I was pointing out that waiting for verification is not usually neccessary in common usage of the currency.  It's the unknowns that call for waiting for verification or the use of a trusted third party.
So most everyday transactions, either online or IRL, can be performed with faith instantly, or with the additional confidence of the local client verification almost instantly.  The 10 minute lag isn't really a detriment.

[Red]

Now I'm confused again.  I thought your scheme didn't have blocks, just transactions.  What do you mean, whoever solves "the block" first?

My scheme doesn't have blocks. I was referring here to how the existing system operates.

Huh?  Lets say the network has 10,000 nodes in it.  I query the network to find the network node closest to a transaction that I want to double-spend.

So I generate a private key.  It has about a 1 in 10,000 chance of being closer than the current closest node.  So I keep generating private keys until I have 5 that are closer.  It's too late for me to figure out the odds, but lets say I generate 100,000 private keys, I'm pretty darn likely to find 5.  My wimpy laptop can generate at LEAST 100 ECC keys/second, so in under 20 minutes it could generate 100,000.

I create 5 nodes with those keys (telling the rest of the network "honest, folks, I chose those keys RANDOMLY...") and I've won.

I'm trying to generate node ids that are "closer" to that transaction's hash than any other node currently on the network.  That's much easier.

Yes, It's much easier!

You've made a quite plausible argument for this particular case. Kudos!

I'm not going to do the math either because that is really not the point. I'm not proposing "The solution". I'm suggesting that the amount of compute resources doesn't need to scale so badly to satisfy bitcoin's requirements. I'm only trying to show that there are other reasonable designs that can meet bitcoin's requirements with significantly lower CPU usage, and in the case of this thread less latency.

I think with the brain-trust that is this forum, any limitations in a distributed solution are easily discovered and rectified. Just as is being done with the current implementation. Perhaps I chose a poor way to create a node ID. Freenet proposes an entirely different way of shared generation of node IDs. It doesn't suffer from the issues you point out. Perhaps it has other issues in this situation. But I'm confident there exist a distributed implementation that would work.

Is the main thrust and incredulity in your argument because you think there CANNOT be a better solution than burning 100,000 CPU at 100% 24/7 and sending 100,000+ redundant messages per transaction?

(100,000 was Satoshi's number of expected core nodes for a system that supported millions of users)

 

[Gavin Andresen]

Is the main thrust and incredulity in your argument because you think there CANNOT be a better solution than burning 100,000 CPU at 100% 24/7 and sending 100,000+ redundant messages per transaction?

No, not at all.  Like I said when I jumped into this thread, I think using a DHT network to somehow distribute the work is a very interesting idea, it just seems to me any solution that partitions the network will be more vulnerable to attacks that insert malicious nodes.  I think it would be fantastic to come up with less resource-intensive solution that actually works.

How does Freenet generate node IDs?  The only info I see in the latest Freenet paper is:

When joining, nodes choose an identity at random, and then connect to those peers with whom they have a pre-established trusted relationship.

.... and:

The perhaps largest advantage that the trusted-connection model offers over traditional anonymity networks is protection against the Sybil attack [13], where a single attacker infiltrates the network by pretending to have many identities. Since the network depends on out of band trust relationships, an attacker gains strength only through the number of people he can fool into trusting him, and gains nothing by presenting multiple identities online.

...which doesn't sound like it would work very well for Bitcoin.

[satoshi]

Once you get away from a system where each node's influence is proportional to their CPU power, then what else do you use to determine who is (approximately) one person?

[knightmb]

Maybe we need a big technical chart that documents every single step about how BitCoin works and the next time someone starts a topic about why everything in bitcoin is done wrong, we can point to that chart and say "here's how it works, document how your new process will work in detail and we will compare"  

I think that would help to cut down on a lot of assumptions/disputes I see in topics every-time the issue of "this isn't being done right" comes up in this forum.

Just saying....  

[Red]

The method I was referring to was in the earliest version of Freenet. It was designed before the trusted connections model was implemented. I'd need to review all the details to remember the specifics. But basically you the nodes you would connect to were picked (I forget the method of picking) Then you pick a random number and broadcast it to all those nodes. Each of those nodes picks a random number and broadcasts it back to you, and to the other nodes in the set. All of the numbers are mathematically combined (don't remember the function) into your arbitrary ID. If you don't answer to that consensus ID no one with talk to you.

Don't sue me if I've got that wrong. That is from an obviously faulty memory.

The Sybil attack (named after the movie, I think) was a network segmentation attack. You create multiple personalities and try to surround a given node to deduce what they are storing. Obviously, that turned out to be possible for this method of ID generation. Hence the new friend-to-friend topography. The same limitation may be a weakness for bitcoin as well. But failures often provide the best guidance on new ways to proceed.

Forgetting the Freenet tangent for a moment...

The "Proof-of-work" technique may actually be applicable to address the ID generation problem you deftly pointed out. Instead of making it harder to generate the record of transactions, you could make it harder to generate new nodes and attach them to the network.

Suppose you (making this up as I go) required that nodes create a private key, then calculate a proof of work checksum on that key, and then the node ID became RIPE-160(SHA-256(POWCheckum(public key) + SHA-256(public key))). Or some such.

The intention being to slow node ID generation down enough for the attack to be untenable, but not so much that it makes it onerous for new nodes to join.

That combined with some last minute "salt" on the transactions, might get us most of the way there.

-------

By the way, I see what I overlooked in my previous conceptualization.

When a transaction is send to the DHT I was presuming would actually be stored on many (hopefully independent) nodes. 5 times related to each in-point and 5 times related to each out-point. Also once by the payer, and once by the payee. I guess that would be 17X redundant given 1 in and 2 outs.

Each of these places "could" resubmit the transaction back to the network if it went missing.

However, I failed to consider three things, 1) validators would only be using 5 of the 17 places for validation. 2) they have no way to query the other places of redundancy should the initial 5 locations be compromised. 3) the additional redundant places have no way of identifying the compromised nodes if they return targeted malicious lies.

Oops. But nice catch!

[Red]

Once you get away from a system where each node's influence is proportional to their CPU power, then what else do you use to determine who is (approximately) one person?

That is the key question of course. I think you need to make it harder to demonstrate you are a person/node. I posted some initial thoughts in the previous post.

[Red]

PS:---------

I really did think the CPU power contest was a brilliant solution. Then I actually did burn my leg with the bottom of my laptop. At that point I realized there was absolutely no way I was going to leave a node running just to support the network. I've run lots of P2P system just to support the network, but bitcoin is much harder to justify absent the "free money" enticement. And that enticement was not enough for me.

By assuring that you need 32 CPU machines and fat network pipes to compete in the battle to record transactions, you absolutely guarantee that the bitcoin ecosystem slides into a central core of trusted nodes and peripheral users that rely on them. That in itself is not a bad thing. (Your news server analogy is appropriate here.)

However, many people are attempting to contrast bitcoin as better than a central bank style system.

By guaranteeing that there will be a central small set of high powered, well connected and trusted nodes that clears all transactions. Where these nodes are peers among each other, but a service "superior" to the general public. And that only members of this elite core are eligible to receive "newly minted money." It really appears that you are just in the process of recreating all the existing fears.

The set of individual who have lots of BTC (like knightmb) will be the most interested in assuring transactions are recorded correctly. They will make sure they run high power honest nodes. As such, this set of BTC rich will receive a large subset of all new coins. That combined with planned price depreciation guarantees that the rich get relatively richer. The competition to this core of potentially "idle rich" is not the public at large, but scammers and BTC miners.

This is not an inspiring story to sell the public.