BitcoinTalk

latency and locality

BitcoinTalk
#1
From:
mkrogh
Subject:
latency and locality
Date:
Hi bitcoin users

I found bitcoin yesterday, and I am really impressed by the idea of avoiding issuers/banks in a digital cash system.

However, I have one objection that I would like your view on.

That is the latency, or delay in a local transaction. Let us say that a payer and payee are located in the same city for example. I will claim, that they want a payment to go through
with a delay not much slower than the latency of network connections. With an issuer and using local coins (a prefix, say, can be used to localize a server of the issuer), the transaction should be done and verified in 100 microseconds or less. With a global p2p network, it is necessary to have all nodes receive the transaction, do some calculations and send results back.
It is not feasible,  with the speed of light as an upper limit, to do this faster than a second. As I understand it you actually use something like 10 minutes for one block, or even more for several block verifications. This means that verification of the absence of double spending is 10,000 or even tens of millions times too slow. This would get even worse in interplanetary trade of course.

The ideal payment system should be decentralized but also local, i.e., the verification of a local transaction must not have to wait for a light signal to travel to the other end of the "universe" and come back again.

Locality, in the sense describe here, is crucial, I will claim.

Sincerely,

Morten Krogh.
BitcoinTalk
#2
From:
FreeMoney
Subject:
Re: latency and locality
Date:
Why is it crucial?

One system doesn't have to be used for all needs. If interstellar money is needed people will choose whatever is best for that, same if people need their money in less than a second.
BitcoinTalk
#3
From:
knightmb
Subject:
Re: latency and locality
Date:
It is not feasible,  with the speed of light as an upper limit, to do this faster than a second. As I understand it you actually use something like 10 minutes for one block, or even more for several block verifications. This means that verification of the absence of double spending is 10,000 or even tens of millions times too slow. This would get even worse in interplanetary trade of course.

It depends on your network layout. If you are using the entire public network, then yes you are depending on that time for the data to be processed by everyone else that is running a node. But, you don't have to do it that way. You can build a trusted node (like a server) and have your clients direct connect to it and let it do the fast verification for you.

It won't net you 20 confirmations in a few milliseconds, but it will help stop double-spending as long as you remain in control of that node because it knows what is being spent. The whole double-spending issue arises from trust. When you are comparing anonymous seller to anonymous buyer, the only "middle man" for trust is the entire swarm (hence confirmations that neither is cheating)

If you know you can trust your own node(s), then it reduces the likely-hood that double-spending will occur within your own trusted network. So if your example applied to an ATM like card for example, the bank (or whoever) would have all of those ATM machines networked to their own private node (or server) which would then further connect to the outside (Internet) for the rest of the transactions. So if you went to an ATM, withdrew 100 BTC (say the entire account only had that much), then moments later went to another ATM elsewhere and tried to withdraw that amount again, somewhere along that trusted chain would spot a double-spend attempt and basically report back no BTC left for that address.

The whole verification process is how you put the swarm to work, all those clients are examining if your transaction was valid or not, but you don't have to wait for them to transfer the coin around. You can spend the coin around in circles all day without a single transaction verification. It's only when double-spending occurs does the network correct for itself and fix the balances.

Banks already have this exact same problem. They all have their own networks that connect to other bank networks and it's just as easy to double-spend on their ATM as has been demonstrated at black-hat hacker conventions for probably 10+ years now. I remember reading about the issue back in 1997 because a lot of networks will still on dial-up then for banks and the latency issue was part of the attack because everyone had their own *database* that all had to inter-connect.

With bitcoin, everyone is the database and banker and guard at the same time, so while it's not perfect, it's actually a lot better than what banks are using. Have you ever noticed at an ATM they have about 20 "network" stickers for all the different banks and setups that the ATM has to be compatible with?
BitcoinTalk
#4
From:
Insti
Subject:
Re: latency and locality
Date:
OP, have you read the Bitcoin snack machine thread?
BitcoinTalk
#5
From:
mkrogh
Subject:
Re: latency and locality
Date:
FreeMoney, I think it is crucial to have fast local transactions. It is needed for many businesses and person to person payments.
10 minutes or even 10 seconds is too slow. An extraterrestrial system was just an extreme example.

The most pressing problem, as I see it, is to get a digital cash system that makes it possible for people and small businesses to pay each other fast and without
registration and supervision from a big company/government.

I read the thread about vending machines. There were no real solutions except companies that would monitor for double checking in a few seconds. I agree that would be possible,
but we would lose the whole point of not having an issuer. This company needs to be trusted, it will break anonymity, and people need an account with that company.

What is wrong with the follwing "standard" system. A central bank/government issues a currency like today. It sets up servers around the world to validate transactions.
People pay each other by means of a single verification with one of the centeal bank's servers. The speed issue is solved by coins having the location of the relevant server embedded in them. In worst case, the server would need to make long round trips to other severs, but in most cases the first server would know the answer already. The cental bank could have an algorithm for distributing coins around the network to optimise latency and server load. The wallet would have an algorithm for choosing the most local coins when making a payment.
The wallet could also prepare by exchanging coins with the server. On your way to Europe, the wallet replaces "American coins" with European coins, such that payments will be fast in Europe. For the user, this is incredibly easy. It is anonymous, and it requires no agreements with any processing companies.
Also, there could be many issuers of the same currency if so desired.

Bitcoin gets rid of the issuers, but instead introduces unacceptable slowness or a lot of middlemen like credit card companies/debit accounts etc. Satoshi's solution, on the vending machine thread, with a double spending checking company is still too slow, even though faster than a block, and this company needs an omnipresence on the network almost like
an issuer.

But discarding speed, bitcoin seems extremely elegant. And of course there are uses for this kind of system. One could imagine many local bitcoin systems with an exchange between
different currencies. That would work except that an attacker can take over a small currency.
BitcoinTalk
#6
From:
Insti
Subject:
Re: latency and locality
Date:
The most pressing problem, as I see it, is to get a digital cash system that makes it possible for people and small businesses to pay each other fast and without
registration and supervision from a big company/government.

...

What is wrong with the follwing "standard" system. A central bank/government issues a currency like today. It sets up servers around the world to validate transactions.

So the solution to avoiding a big company/government regulation is a big company/government?

It is currently possible with Bitcoin to do transactions which are practically instant particularly if you do not fear some vast conspiracy to defraud you.
If you really do have need of transactions faster than Bitcoin can offer, use a different system, but you will probably have to forgo some of the benefits that Bitcoin currently offers.



BitcoinTalk
#7
From:
mkrogh
Subject:
Re: latency and locality
Date:
No, my goal is not to avoid government involvement in the payment system, but to not have the government monitor every transaction. There is a difference.

The current bill/coin system works like that. The government/central bank issues the currency but they don't monitor individual cash payments.
I think that is okay.

You claim that is possible to make almost instantaneous payments with bitcoin. How? That is what I thought everybody agreed upon was not possible. You need to wait for
one or more blocks to be solved before you can trust a coin. That takes minutes. Even in the best case it is limited by propagation, with the speed of light, around the network which is slow. The only solution is to create another banking system on top of this. Bitcoin then becomes the backbone of an intebank transfer system, not what the population at large is using.
   
It is not just me that needs fast transactions. There is giant demand for fast transfers of digital cash from cell phone to cell phone, web shopping, stock trading etc. 

But, we might just have different expectations from a digital cash system.

Has anyone ever stated clearly what problem bitcoin is solving? It seems to solve the problem of payments that don't need to be fast. But who are the potential users of that beyond people who thinks it is theoretically interesting like people on this board.

Do people agree with me on this point: We still need another digital cash system, and that probably needs to be issuer based.
BitcoinTalk
#8
From:
Insti
Subject:
Re: latency and locality
Date:
No, my goal is not to avoid government involvement in the payment system, but to not have the government monitor every transaction. There is a difference.

The current bill/coin system works like that. The government/central bank issues the currency but they don't monitor individual cash payments.
I think that is okay.
Every transaction is monitored in the bitcoin system.

Quote
You claim that is possible to make almost instantaneous payments with bitcoin. How? That is what I thought everybody agreed upon was not possible. You need to wait for
one or more blocks to be solved before you can trust a coin.
That is your requirement for trust, not mine. You can trust a transaction as soon as you see it if you like.
And people are going to shop with those who will give them speedy transactions.

Quote
That takes minutes. Even in the best case it is limited by propagation, with the speed of light, around the network which is slow. The only solution is to create another banking system on top of this. Bitcoin then becomes the backbone of an intebank transfer system, not what the population at large is using.
   
It is not just me that needs fast transactions. There is giant demand for fast transfers of digital cash from cell phone to cell phone, web shopping, stock trading etc. 

But, we might just have different expectations from a digital cash system.
Clearly.

Quote
Has anyone ever stated clearly what problem bitcoin is solving? It seems to solve the problem of payments that don't need to be fast. But who are the potential users of that beyond people who thinks it is theoretically interesting like people on this board.
Anyone who currently uses PayPal for a start.

Quote
Do people agree with me on this point: We still need another digital cash system, and that probably needs to be issuer based.
I don't. But I'm just one person.
BitcoinTalk
#9
From:
mkrogh
Subject:
Re: latency and locality
Date:
Every transaction is monitored in the bitcoin system.

But you can make it anonymous. Why are you bringing this up?This is a point, were I thought we agreed.
When I said monitoring, I meant including identification of the payer and payee.

Quote

That is your requirement for trust, not mine. You can trust a transaction as soon as you see it if you like.
And people are going to shop with those who will give them speedy transactions.

Yes, that is my requirement, and will be most others as well. You will see almost no companies that sell without a guarantee against double spending.


Quote
Anyone who currently uses PayPal for a start.

Most of those will prefer a fast issuer based system over a slow decentralized system, I will claim.
But they might prefer bitcoin over paypal.
BitcoinTalk
#10
From:
Insti
Subject:
Re: latency and locality
Date:
Every transaction is monitored in the bitcoin system.

But you can make it anonymous. Why are you bringing this up?This is a point, were I thought we agreed.
When I said monitoring, I meant including identification of the payer and payee.
Ok, when you said monitoring I thought you meant monitoring, so I was just pointing out that all the transactions were trackable in case you did not already understand this. Since it seems you do it's not a problem Smiley

Quote
Quote
That is your requirement for trust, not mine. You can trust a transaction as soon as you see it if you like.
And people are going to shop with those who will give them speedy transactions.

Yes, that is my requirement, and will be most others as well. You will see almost no companies that sell without a guarantee against double spending.

Quote
Anyone who currently uses PayPal for a start.

Most of those will prefer a fast issuer based system over a slow decentralized system, I will claim.
But they might prefer bitcoin over paypal.

It seems we have differing opinions on the way future will develop. Which is fine.
It'll probably turn out nothing like either of us expect anyway.

BitcoinTalk
#11
From:
mkrogh
Subject:
Re: latency and locality
Date:
Yes, it might turn out very differently. No digital cash for the masses for instance. A giant banking cartel that bribes politicians to keep the current system.
BitcoinTalk
#12
From:
Red
Subject:
Re: latency and locality
Date:
mkrogh: Yes, you are correct.

There is absolutely no requirement for there to be such latency in the bitcoin system. Nothing fundamental would change if the system were implemented with a block list that updated every 10 seconds, instead of every 10 minutes. It was just a design decision that could be changed without effecting monetary policy a bit.

In fact, there is no requirement their be a block list that updates in increments at all. The system would work fine if each transaction were validated one-by-one. In effect one transaction per block. That was a design decision to make networked consensus building easier.

However, when you say "local transaction validation" what you are grasping for is a truly distributed system, rather than a monolithic system made redundant. The current version of bitcoin is the latter. Each node does exactly the same work as every other node. Each redundantly checking every transaction. It is a system horribly wasteful of resources. And because it is so wasteful, generates latency as a waste product.

Bitcoin could be made into a truly distributed system by storing the transaction graph in a distributed hash table. This is the kind of magic that is behind most other P2P systems. In effect, each bitcoin address would be arbitrarily mapped to a smaller set of nodes that checked its transactions. In such a system, there is no need to broadcast global state to every machine. This takes huge amount of latency out without needing to change any of the desired behavior.
BitcoinTalk
#13
From:
FreeMoney
Subject:
Re: latency and locality
Date:

Yes, that is my requirement, and will be most others as well. You will see almost no companies that sell without a guarantee against double spending.


Did you know about this? You don't need to wait for it to get in a block to have way better certainty than PP or checks.

I believe it'll be possible for a payment processing company to provide as a service the rapid distribution of transactions with good-enough checking in something like 10 seconds or less.

The network nodes only accept the first version of a transaction they receive to incorporate into the block they're trying to generate.  When you broadcast a transaction, if someone else broadcasts a double-spend at the same time, it's a race to propagate to the most nodes first.  If one has a slight head start, it'll geometrically spread through the network faster and get most of the nodes.

A rough back-of-the-envelope example:
1         0
4         1
16        4
64        16
80%      20%

So if a double-spend has to wait even a second, it has a huge disadvantage.

The payment processor has connections with many nodes.  When it gets a transaction, it blasts it out, and at the same time monitors the network for double-spends.  If it receives a double-spend on any of its many listening nodes, then it alerts that the transaction is bad.  A double-spent transaction wouldn't get very far without one of the listeners hearing it.  The double-spender would have to wait until the listening phase is over, but by then, the payment processor's broadcast has reached most nodes, or is so far ahead in propagating that the double-spender has no hope of grabbing a significant percentage of the remaining nodes.
BitcoinTalk
#14
From:
mkrogh
Subject:
Re: latency and locality
Date:
FreeMoney, yes I knew about that.

Red, very interesting. So, a set of transactions in bitcoin can actually be made local. But it must be possible to control where a transaction should be validated. That must be coin
dependent because of double spending. So, if I understand, it must be possible, for any transaction, to choose which location the resulting coin should be validated in when that
coin is used next time. A random choice would not be good enough. But, are there some problems with an attacker taking over a certain location. The global system had the strength that an attacker would be outworked by the sum of all other CPUs.

Red, can you elaborate more on such a distributed version of bitcoin. Is it described anywhere?

Cheers.
BitcoinTalk
#15
From:
Gavin Andresen
Subject:
Re: latency and locality
Date:
Bitcoin could be made into a truly distributed system by storing the transaction graph in a distributed hash table. This is the kind of magic that is behind most other P2P systems. In effect, each bitcoin address would be arbitrarily mapped to a smaller set of nodes that checked its transactions. In such a system, there is no need to broadcast global state to every machine. This takes huge amount of latency out without needing to change any of the desired behavior.
Interesting idea.

So, lets see, I create a transaction to pay you (say) 100 of my newly minted bitcoins.

That'll be a transaction with two 50BTC TxIns (signed by me, pointing to two mature GENERATE transactions somewhere in the block chain) and one 100BTC TxOuts.

You want to make sure I haven't double-spent those TxIns, so instead of flooding the network with that transaction you find the hash of the two GENERATE transactions and send two queries down into the DHT network:  "Hey, here's a transaction, tell me if it is valid."  They say "yup", and then... what?  Include it in any blocks they're lucky enough to generate?  Broadcast it to everybody (which'd be no better than the current scheme) or some subset of the DHT network (what subset?)?

How do you know that you won't get a different answer to "is this transaction valid" if you ask again in 10 minutes when the network topology might have changed?

I don't know much about DHT networks and how they manage to keep reliable information when nodes may be coming and going (or buggy or malicious).  How would it work?

BitcoinTalk
#16
From:
MoonShadow
Subject:
Re: latency and locality
Date:
Red, very interesting. So, a set of transactions in bitcoin can actually be made local. But it must be possible to control where a transaction should be validated.

I think that you are getting lost in the choice of wording on this list.  Every bitcoin client, whether or not it is 'generating' or not, has a very recent copy of the entire block chain, and can check any new transactions against that block chain to see if those bitcoins were owned by the *address* that the other client claims he owns, at least up until the last block update.  I'm not saying local verification is implimented in the current client, but it's possible.  But that doesn't protect you from a concurrent double spend.  The distributed verification will add confidence in the validity of the transaction with each passing block, but it's not neccessary to perform a transfer.  Cash in person has similar problems, as the vendor can never be *certain* that the customer isn't passing off counterfit currency.  The risks of fraud are included in the costs of retail business, and if speed of transactions are paramount, the vendor can simply accept the results of his own client and take the risks that he might get burned.  Waiting for confirmation would help protect against fraud, but it's not a *requirement* for completion of a trade.  I would expect that smartphone clients would do this quick local verify by default, particularly when communicating with each other directly over ad-hoc wireless.

Also, the system doesn't even require that the receiving client be on the network at the time of the transfer.  You can send money to any address at any time, and their client could find out about it long after the transfer had been verified by the bitcoin network.
BitcoinTalk
#17
From:
NewLibertyStandard
Subject:
Re: latency and locality
Date:
Just agree to both use the same free online wallet before you make your trade. MyBitcoin.com offers instant transfers.
BitcoinTalk
#18
From:
mkrogh
Subject:
Re: latency and locality
Date:
creighto, I am only talking about verifying the absence of double spending. Of course, you can always receive a coin and just hope. That is clear.

I don't think that physical coins have this issue. Or gold. Firstly counterfeiting is really difficult, secondly "bill verifiers or gold verifiers" are local machines. If someone could
counterfeit gold or coins in a way that no local machine could detect, then it would be the same. But no one can do that.

With bitcoin in the version I have seen (not red's), you cannot build a local machine that verifies it. I don't understand what red exactly is proposing.


NewLibertyStandard, your suggestion is a bank, that the payer and the payee need an account with. I don't mind, but I don't think it is an answer to the issue of this thread.

What I see as the ideal solution has these properties.

1. You can participate by just having some software on your computer/phone.
2. The coins are stored by yourself. A coin is a string of characters, no physical gold or so is involved. Encryption keys are fine if you can generate them yourself.
3. No accounts or registrations with banks or governments are needed.
4. Payments can be totally verified including double spending checks. Tiny probabilites can be ignored. But I mean tiny, not just reasonably small.
5. If a person is traveling to a city, he (she) can prepare for the visit by exchanging coins. This exchange can be slow. After arriving to the city, the person can make fast payments
to a person residing in that city. By fast payments, I mean payments that are completely validated in a time frame that does not depend on the total size of the coin system. In other words local trade should be possible, even if the digital cash system is used all over the world (or galaxy). The preparation before arrival is important here. Of course, many coins can not be verified, fast, against double spending by the payee, but there should exist some coins that can, given the location. And the payer can prepare before arrival by getting such coins.
6. No issuer on whose honesty the system relies.   


1-5 is possible with an issuer. The coins have a tag that denotes where double spending will be verified. The issuer keeps the information about those coins on their servers in that location. In other words, the issuer's distributed hash table follows some rules for what coins are stored where. And those rules are publicly available.

1,2,3,4,6 seems to be bitcoin if I understand correctly.

Does 1-6 exist. Is that what red is saying?
BitcoinTalk
#19
From:
NewLibertyStandard
Subject:
Re: latency and locality
Date:
In real life, bank wires take much much longer than ten minutes. Most traditional services which you see as instantaneous are actually not instantaneous. Credit card charges don't go through immediately, the funds are just reserved immediately and the retailer trusts the credit card company. Not to mention that charges can be challenged, which means the final transaction could take weeks. Real bitcoin transactions occur much more quickly than real traditional electronic money transfers. If you need instant transfers, then you just have to set up the same tricks which the traditional electronic currency market uses, and that is basically what I suggested.
BitcoinTalk
#20
From:
MoonShadow
Subject:
Re: latency and locality
Date:
creighto, I am only talking about verifying the absence of double spending. Of course, you can always receive a coin and just hope. That is clear.



There is more to it than just hoping.  For starters, you could already have an existing business relationship, and trust built between two parties due to honest prior trading. 



Quote

I don't think that physical coins have this issue. Or gold. Firstly counterfeiting is really difficult, secondly "bill verifiers or gold verifiers" are local machines. If someone could
counterfeit gold or coins in a way that no local machine could detect, then it would be the same. But no one can do that.



Counterfeiting bitcoins is really difficult as well, and that is what a local blockchain check would protect you against.  It would also protect you against a double spend that wasn't concurrent, as if one guy backs up his wallet file and then spends his coins the night before and attempts to yank your chain.  It does not protect you against a professional criminal, but against the petty attempt.


[/quote]
With bitcoin in the version I have seen (not red's), you cannot build a local machine that verifies it.
[/quote]


I know from other threads that Red has a different understanding than I about how the system works.  Either or both of us could be wrong.  My understanding is that, at present, the clients attempt to announce a transfer and then wait for the collective to confirm the transfer via accepting the claim as valid in at least two blocks, after which point the network believes that you have valid bitcoins, therefore you do.

However, two clients can interact directly, in theory.

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.

This also means that the shopkeeper can only spend bitcoins that he had at the time of the power failure himself, since any new bitcoins that he receives will not yet be included in the blockchains of any other vendor, and any attempts by his client to transfer his unannounced coins will be rejected by the other clients.  All transfers will either be verified or rejected by the network within 30 minutes of network reconnection.
BitcoinTalk
#21
From:
Red
Subject:
Re: latency and locality
Date:
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.


BitcoinTalk
#22
From:
Gavin Andresen
Subject:
Re: latency and locality
Date:
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.
BitcoinTalk
#23
From:
MoonShadow
Subject:
Re: latency and locality
Date:
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.
BitcoinTalk
#24
From:
NewLibertyStandard
Subject:
Re: latency and locality
Date:
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.
BitcoinTalk
#25
From:
Red
Subject:
Re: latency and locality
Date:
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.


BitcoinTalk
#26
From:
Gavin Andresen
Subject:
Re: latency and locality
Date:
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?

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

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

Quote
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.
BitcoinTalk
#27
From:
MoonShadow
Subject:
Re: latency and locality
Date:
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.
BitcoinTalk
#28
From:
Red
Subject:
Re: latency and locality
Date:
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)

 
BitcoinTalk
#29
From:
Gavin Andresen
Subject:
Re: latency and locality
Date:
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:
Quote
When joining, nodes choose an identity at random, and then connect to those peers with whom they have a pre-established trusted relationship.
.... and:
Quote
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.
BitcoinTalk
#30
From:
satoshi
Subject:
Re: latency and locality
Date:
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?