Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: rfugger on March 11, 2011, 07:55:58 PM



Title: A block chain for real-time confirmations
Post by: rfugger on March 11, 2011, 07:55:58 PM
I think the block chain is the most brilliant, elegant way I've seen for independent machines to form a consensus.  My main issue with it is the delay in confirming transactions.

My idea is to have transactions added to the block chain individually, rather than in blocks.  What would happen is that multiple transactions would simultaneously be added to the head of the chain, which ought to be fine as long as they are all mutually compatible.  All that's needed is for further transactions to be able to build on multiple compatible transaction streams and merge them, rather than just picking one.  It's possible that a transaction gets merged into several different streams, but that actually helps its odds should it ever end up in a stream that ends up getting rejected.

Each transaction includes its own proof-of-work.  If there are two parallel streams containing incompatible transactions, the stream with the greatest cumulative proof-of-work in its history becomes valid, and the other is dropped.  Therefore peers are motivated to build on as many valid transactions as they know, to decrease the odds of their stream being dropped, meaning they will want to merge all the compatible parallel streams they know of in order to maximize the proof-of-work in their new stream.  Peers will also be motivated to include as much proof-of-work as they can in their own transactions, for the same reason.

One benefit of this arrangement is that it doesn't need transaction fees or any other reward to motivate third-party block computations.

Thoughts?

Ryan


Title: Re: A block chain for real-time confirmations
Post by: khal on March 11, 2011, 08:33:08 PM
It's a security protection.

If you want a real time confirmation, patch the client to check if the sender really have coins (it may already do this). Once it's done, you don't need to really wait for inclusion in 6 blocks, or even in 1 block (but a transaction can currently be ignored by all blocks and forgotten, or depends on another transaction still not included, so 1 block may be a minimum of security)


Title: Re: A block chain for real-time confirmations
Post by: jtimon on March 11, 2011, 08:34:03 PM

Each transaction includes its own proof-of-work.  If there are two parallel streams containing incompatible transactions, the stream with the greatest cumulative proof-of-work in its history becomes valid, and the other is dropped.

Ryan

Wouldn't this be the same as having only one transaction per block?

Yes. That's the way he reduces the delay in confirming transactions. There's less time between blocks/transactions.

My idea is to have transactions added to the block chain individually, rather than in blocks.  What would happen is that multiple transactions would simultaneously be added to the head of the chain, which ought to be fine as long as they are all mutually compatible.  All that's needed is for further transactions to be able to build on multiple compatible transaction streams and merge them, rather than just picking one.  It's possible that a transaction gets merged into several different streams, but that actually helps its odds should it ever end up in a stream that ends up getting rejected.

How that merge would be made?


Title: Re: A block chain for real-time confirmations
Post by: theymos on March 11, 2011, 08:53:24 PM
That doesn't help much. You need to wait until your transaction is buried deep enough in the chain for an attacker with less than 50% of the network's computational power to be unable to reverse it. If there are many smaller, easier blocks, you'll just have to wait 300 confirmations (or whatever) until that target is reached. In other words, you always must wait for the network to do a lot of work after your transaction.

It would provide more fineness in desired confirmations; you could accept transactions with 2.5 Bitcoin-equivalent confirmations. But it's bad for scalability, and the increased fineness isn't valuable, IMO.


Title: Re: A block chain for real-time confirmations
Post by: rfugger on March 11, 2011, 08:55:55 PM
If you want a real time confirmation, patch the client to check if the sender really have coins (it may already do this). Once it's done, you don't need to really wait for inclusion in 6 blocks, or even in 1 block (but a transaction can currently be ignored by all blocks and forgotten, or depends on another transaction still not included, so 1 block may be a minimum of security)

Right, you should wait for at least one block to have pretty good reassurance.  That's a few minutes on average, not enough for point-of-sale, for example.

Wouldn't this be the same as having only one transaction per block?

Yes, with the addition of the capability of merging parallel streams.

How that merge would be made?

Instead of including the hash of a single predecessor block, you would include the hashes of all predecessor blocks.  For the proof of work, you would hash the root of a Merkle tree of all the predecessors, just like you do to include multiple transactions in blocks now. 

But if that were true then transaction volume would be pegged to the rate of block creation. The only way to increase circulation would be to have bigger transactions... Won't work.

There is no independent rate of block creation or target difficulty anymore.  Just one block per transaction, whenever a transaction happens, with whatever proof of work the submitter can generate.  So "blocks" will get generated continually.  ("Block" isn't a suitable word anymore, because it implies a grouping of transactions, which isn't the case here -- it makes more sense to just say "transaction" .)


Title: Re: A block chain for real-time confirmations
Post by: rfugger on March 11, 2011, 09:02:28 PM
That doesn't help much. You need to wait until your transaction is buried deep enough in the chain for an attacker with less than 50% of the network's computational power to be unable to reverse it. If there are many smaller, easier blocks, you'll just have to wait 300 confirmations (or whatever) until that target is reached. In other words, you always must wait for the network to do a lot of work after your transaction.

It would provide more fineness in desired confirmations; you could accept transactions with 2.5 Bitcoin-equivalent confirmations. But it's bad for scalability, and the increased fineness isn't valuable, IMO.

Good point.

I would argue that it would be valuable to have finer-grained confirmations for the sake of speed.  In a point-of-sale situation, for example, being able to confirm a small transaction quickly is very important.

Can you elaborate on how it hurts scalability?  Isn't it all the same data being passed around?

Thanks.


Title: Re: A block chain for real-time confirmations
Post by: rfugger on March 11, 2011, 09:10:16 PM
Further thoughts:

Anyone would be able to add proofs of work onto this kind of chain, continually making it stronger, by submitting zero-value transactions.  Peers who recently submitted transactions would be motivated to do this to ensure their transactions get sufficiently buried.  They could even pay others to do this for them if they wanted, which would be just like transaction fees in the current system.

You could still have coin-generating transaction blocks with a set target difficulty -- they would just include the one coin-generating transaction, though, but would need to have a reasonably current set of predecessors to be accepted.


Title: Re: A block chain for real-time confirmations
Post by: theymos on March 11, 2011, 09:29:37 PM
I would argue that it would be valuable to have finer-grained confirmations for the sake of speed.  In a point-of-sale situation, for example, being able to confirm a small transaction quickly is very important.

0.01 of a confirmation on your network is actually worse than 0 confirmations on the Bitcoin network. With 0 confirmations you are protected somewhat by the TCP-level network, but anyone can reverse a transaction with 0.01 confirmation, overruling the TCP-level network.

Can you elaborate on how it hurts scalability?  Isn't it all the same data being passed around?

It's a lot more data that lightweight clients will have to download. There's an 80-byte header per block that clients need. If this was required for every transaction, then lightweight clients would have to download about 17MB more data currently. This will become a lot more significant as the number of transactions per block increases. Also, if you have multiple "previous block" hashes in each transaction, you'll need headers that are much larger than 80 bytes. Normal clients will quickly lose the ability to send transactions.


Title: Re: A block chain for real-time confirmations
Post by: rfugger on March 12, 2011, 12:46:15 AM
0.01 of a confirmation on your network is actually worse than 0 confirmations on the Bitcoin network. With 0 confirmations you are protected somewhat by the TCP-level network, but anyone can reverse a transaction with 0.01 confirmation, overruling the TCP-level network.

Yes, as a payment recipient you would still have to wait until the cost of creating a conflicting parallel stream with a greater proof of work than your stream was greater than the value of the payment.  But for small payments, that might not be very long at all.  Right now, a 10-minute block is worth somewhere in the neighbourhood of $45.

It's a lot more data that lightweight clients will have to download. There's an 80-byte header per block that clients need. If this was required for every transaction, then lightweight clients would have to download about 17MB more data currently. This will become a lot more significant as the number of transactions per block increases. Also, if you have multiple "previous block" hashes in each transaction, you'll need headers that are much larger than 80 bytes. Normal clients will quickly lose the ability to send transactions.

Ah, I was only considering full clients.  Fair point.  With my proposal, if you didn't have enough bandwidth to receive all the transactions, you wouldn't be able to verify the proof of work in the chain.

There is no independent rate of block creation or target difficulty anymore.  Just one block per transaction, whenever a transaction happens, with whatever proof of work the submitter can generate.  So "blocks" will get generated continually.  ("Block" isn't a suitable word anymore, because it implies a grouping of transactions, which isn't the case here -- it makes more sense to just say "transaction" .)

OK then, how do you control the rate of currency inflation? Seems as though you are talking about a fundamentally different system that uses some of the same tools.

Normal "blocks" wouldn't generate coins anymore, since there is no target difficulty.  You could still have coin-generating blocks, but they would only contain the generating transaction, and have to meet a target difficulty.  Two generating transactions in parallel streams would conflict.  See my post re: generating transactions. 

It is a somewhat different system in that it shifts the burden of proof of work from a few block-computing machines, to anyone who wishes to record a transaction. 


Title: Re: A block chain for real-time confirmations
Post by: rfugger on March 12, 2011, 01:13:57 AM
If I get you... In your proposed system generating normal blocks would not be computationally intensive, but generating transactions would be.
Isn't this going the wrong way? This places the weight of the system on merchants with the rest of the market participants simply acting as consumers.

Perhaps, but merchants will always pass along the cost of the system to their customers...

Quote
And what's to keep a couple of nodes from making dummy purchases from each other simply to create coin? That sounds more like banking as it exists today IMO.

You can't generate coins by making a dummy purchase.  You have to hold a coin to make normal transaction.  You would only be able to generate coins by creating a coin-generating block, which would require the same target difficulty as the current system.


Title: Re: A block chain for real-time confirmations
Post by: Jim Hyslop on March 12, 2011, 02:00:14 AM
Normal "blocks" wouldn't generate coins anymore, since there is no target difficulty.  You could still have coin-generating blocks, but they would only contain the generating transaction, and have to meet a target difficulty.  Two generating transactions in parallel streams would conflict.  See my post re: generating transactions. 

It is a somewhat different system in that it shifts the burden of proof of work from a few block-computing machines, to anyone who wishes to record a transaction. 

If I get you... In your proposed system generating normal blocks would not be computationally intensive, but generating transactions would be.
No, I believe it's the other way around.

I think the problem is you and rfugger have different definitions of "normal" :-)

I think this won't hurt scalability if the 'headers only' protocol gets implemented. I think this idea might be worth exploring a bit more - I've been thinking along the same lines myself.

The proposal, as I understand it, is to have a "trading block" and a "mining block." The mining block would be the equivalent of what we currently have: it requires proof of work to be accepted by other peers, and it generates new bitcoins out of nothing, and claims any transaction fees for transactions included in the block.

The trading block, on the other hand, would consist of nothing but transactions (most likely a single transaction from the originator). Since it does not generate any new bitcoins, there is no work involved, and therefore no proof of work is required. And, since no work is required, it is not eligible to claim any transaction fees.

Think of the new trading block as an interim, semi-official confirmation. Kind of like a temporary driver's license.

The miners would still generate mining blocks, as usual. The mining block still includes transactions, and it is the mining block that is considered the official confirmation of the transaction.

To generate a trading block, the software first checks to see if it has received any trading blocks from its peers. If so, and if the root of the trading block chain is your node's highest mining block, then it uses the trading block as its previous block, otherwise it uses the highest mining block. It then creates the trading block and broadcasts it to connected nodes.

Sooner or later - most likely well before the next mining block appears - another peer will generate a transaction, and append its trading block to the one your node just sent out. When you receive that trading block, you have a confirmation - your temporary driver's license.

Multiple branches off the same mining block will occur, but that's OK because they won't (shouldn't) last more than 20 or 30 minutes. But, we'd have to figure out a way to encourage peers to use existing trading chains, or combine multiple trading block chains of depth 1 into a single chain.

Now, if yet another peer happens to receive the second trading block before it receives yours, then it broadcasts a request for your trading block and/or transaction.

As today, miners put incoming transactions in their memory pool, gather them into a block, then start working on the block, giving preference to transactions in trading blocks, and claiming any transaction fees associated with the transactions.

When nodes receive a new mining block, then they discard trading blocks where the transaction is in the mining block.

The incentive to use this system is to get quicker confirmation of transactions.

There are still a lot of gaps, and I'm sure there are problems I'm overlooking, but as I say, I think this is worth thinking through.


Title: Re: A block chain for real-time confirmations
Post by: Maged on March 15, 2011, 01:14:30 AM
There are many issues with this idea, most notably the lack of miners, the continued vulnerability to the 'finney attack', and the added bloat. However, this has inspired me. My suggestion is an optional extension to the protocol, which may or may not require a protocol switch if extensibility wasn't initially added to the block headers. In short: my idea is to add a parallel block chain to the existing one, but with combined headers.

First off, we need to make sure that the "trading block" (hereafter referred to as "hyperchain") gets mined. One of the best ways to do this is to take a leaf from the mining pool book and make it so that the hyperchain is formed from low-difficulty full blocks, possibly with a difficulty target of somewhere between 5-10 seconds. The only difference between normal blocks and hyperchain-enabled blocks would be that hyperchain blocks would add a "previous hyperblock" field to the existing block headers.

When I said that hyperblocks would just be low-difficulty blocks, I meant it. Transactions would be added to the block as they are now and the transactions in the block would not be removed when a hyperblock is formed, as if hyperblocks never existed. The only difference is that hyperblocks would be transmitted to hyperchain enabled clients at lower difficulties than normal blocks. As like any other block-chain, when new hyperchain blocks come in, regardless of if it's a full block with a hyperchain header or just a regular hyperblock, the "previous hyperblock" field would be updated to reflect the end of the longest hyperblock chain, relative to the last full block with a hyperchain header. Hyperchain conflicts would be resolved much like any other block-chain.

It is my impression that the main reasons that we have the difficulty target so high is because of the bandwidth and storage that would otherwise be required. This most certainly will be high-bandwidth, but only people who can handle it would enable it. As for storage, purge old hyperblocks the same way that the transaction cache is purged right now.

Finally, here comes the magic of the hyperchain:
The hyperchain would be what is used to resolve double-spends. Once a coin is spent and confirmed on the hyperchain, it cannot be re-spent on the block-chain. For this to work, most miners (>50% computational power) would need to have a hyperchain-aware client, although the hyperchain feature need not to be enabled. For hyperchain-aware clients that don't have the hyperchain feature enabled, upon receiving a full block containing a coin already thought to be spent according to the client's transaction cache (or even just getting a block that contains a transaction that hasn't been received normally), the client would go back and download the relevant portion of the hyperchain, much like the future "simple" clients would do for the normal block-chain, to resolve the double-spend. If the full block is in conflict with the hyperchain, the full-block is rejected (unless, of course, the majority overrule and continue that block-chain).

At this point, the 'finney attack' is only effective against the hyperchain. However, the hyperchain would move so quickly that the merchant would be able to wait for the first hyper-confirmation.

Speaking of confirmations, the confirmation numbers for transactions on the hyper-chain should be represented as the greatest fraction of normal difficulty of hyperblocks after the transaction was seen in the hyperchain. For example, if a transaction has been seen in a hyperblock of .5 normal difficulty, and a hyperblock of .6 normal difficulty came, it's number of confirmations would show ".60". As for transactions that were chained behind a full block that also had hyperblock headers but weren't actually confirmed in the block, show something like ".99 confirmations".

I really hope this made some sense to you guys, since I'm clearly trying to explain something way over my head.


Title: Re: A block chain for real-time confirmations
Post by: ryepdx on March 15, 2011, 02:35:21 AM
I think I see what you're saying. It would be analogous to keeping a delta index in something like Lucene, right?


Title: Re: A block chain for real-time confirmations
Post by: MoonShadow on March 15, 2011, 03:54:40 AM
There are many issues with this idea, most notably the lack of miners, the continued vulnerability to the 'finney attack', and the added bloat. However, this has inspired me. My suggestion is an optional extension to the protocol, which may or may not require a protocol switch if extensibility wasn't initially added to the block headers. In short: my idea is to add a parallel block chain to the existing one, but with combined headers.


There are some serious issues with such an idea, not the least of which is network latency, which is the main reason that the target interval is ten minutes to start with.  Another is the complexity added to the protocol.  And then I can't even see how it's necessary.  Transactions are complete in milliseconds, it's the confirmations that take ten minutes, which are way faster than how this is done by just about any other online method.  Credit card transactions are, likewise, nearly instant; but it can take up to 60 days before they are final.  So I have to ask, what is the problem trying to be solved?


Title: Re: A block chain for real-time confirmations
Post by: Cryptoman on March 15, 2011, 04:19:28 AM
So I have to ask, what is the problem trying to be solved?

I have to agree with this sentiment.  Each merchant can set his/her own threshold where they require X confirmations for any transactions over the threshold amount.  For example, anything below 1 BTC isn't worth anyone's time waiting for 6 or more confirmations.  As soon as the transaction shows up in the client, it can be considered valid.  Perhaps 2-5 BTC would require 2 confirmations, 5-50 BTC would require 4, etc.  It's not worth an attacker's computing power to try to double spend 1 BTC.  Anyone making a large transaction surely will have the patience to wait an hour or so for 6 confirmations.


Title: Re: A block chain for real-time confirmations
Post by: MoonShadow on March 15, 2011, 04:58:30 AM
So I have to ask, what is the problem trying to be solved?

I have to agree with this sentiment.  Each merchant can set his/her own threshold where they require X confirmations for any transactions over the threshold amount.  For example, anything below 1 BTC isn't worth anyone's time waiting for 6 or more confirmations.  As soon as the transaction shows up in the client, it can be considered valid.  Perhaps 2-5 BTC would require 2 confirmations, 5-50 BTC would require 4, etc.  It's not worth an attacker's computing power to try to double spend 1 BTC.  Anyone making a large transaction surely will have the patience to wait an hour or so for 6 confirmations.

Credit card charges less than $50 are not normally even checked at a Point-of-sale, such as a gas station, within a reasonable distance of the card owner's home.  Bitcoin permits a great deal better verification than the credit card companies provide the gas station owners.

And if the vendor is an online shopping vendor, there is no good reason to not wait for 6 confirmations before releasing an order for shipping.


Title: Re: A block chain for real-time confirmations
Post by: theymos on March 15, 2011, 05:19:24 AM
The "insurance" provided by each confirmation increases with the total network computational power. It might be useful to wait only a half-confirmation or less if the network becomes so massive that one confirmation can protect even very high-value transactions. It's not very useful now.

I could see a separate chain running with a target time of perhaps as low as one minute, but a target time of seconds will be impossible due to latency. I don't think a separate chain is the answer, though: there would be no incentive to create blocks on it, and there are probably other methods that will work even better. The network might never be large enough to support this, though, and no changes are necessary to Bitcoin now, so it's not worth working on. By the time it becomes useful, solutions for dealing with fast transaction acceptance will already have been established.


Title: Re: A block chain for real-time confirmations
Post by: jtimon on March 15, 2011, 11:40:48 AM
So I have to ask, what is the problem trying to be solved?

I think the problem that this system tries to solve is in-place transactions without the need of a trusted third party.


Title: Re: A block chain for real-time confirmations
Post by: Mike Hearn on March 15, 2011, 12:25:08 PM
I think the best way to make progress with this issue would be for somebody to look at the impact of using much faster block generation times.

10 minutes was chosen on the assumption of really large networks, really large blocks and thus potentially large propagation times. It's a tradeoff between convenience and avoiding wastage of mining effort.

But 10 minutes for block propagation is pretty huge. BGP updates propagate across the whole internet in less than one minute, as far as I can tell. And BitCoin is nowhere near large enough to see 10 minute propagation times today. It'd probably be possible to have one minute confirmations on todays network.

The questions to ask are:
  • Is 1 minute really better than 10? I think suspect there's really only two speeds that matter, "<5 seconds" and ">5 seconds".
  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?



Title: Re: A block chain for real-time confirmations
Post by: Matt Corallo on March 15, 2011, 12:53:15 PM
  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?
I think floating transactions can easily be made very low-risk.  Remember that if your client sees a new tx, it forwards it to all nodes around it.  If you are connected directly to some of the large miners, the probability that your client would not be notified of a double tx (assuming the attacker specifically sends conflicting txes to you and large miners at the same time to increase their chance) is very low.  Thus if the client informed the user if it received a conflicting tx for a tx which is to/from the user, the user could be easily notified within seconds of the original tx. 
Alternatively, each node could pass the first conflicting tx it sees or some kind of "Ive seen a tx which conflicts with this tx" message.  However, this increases the possibility for DDoS per coin (roughly x2 in terns of txes which need transferred through the network) so this is probably not a good idea. 


Title: Re: A block chain for real-time confirmations
Post by: MoonShadow on March 16, 2011, 07:27:16 AM

Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?


This is starting to feel familiar...

http://bitcointalk.org/index.php?topic=723.msg8019#msg8019

http://bitcointalk.org/index.php?topic=691.msg7283#msg7283


Title: Re: A block chain for real-time confirmations
Post by: Cdecker on March 16, 2011, 07:42:54 AM
I think the best way to make progress with this issue would be for somebody to look at the impact of using much faster block generation times.

10 minutes was chosen on the assumption of really large networks, really large blocks and thus potentially large propagation times. It's a tradeoff between convenience and avoiding wastage of mining effort.

But 10 minutes for block propagation is pretty huge. BGP updates propagate across the whole internet in less than one minute, as far as I can tell. And BitCoin is nowhere near large enough to see 10 minute propagation times today. It'd probably be possible to have one minute confirmations on todays network.

The questions to ask are:
  • Is 1 minute really better than 10? I think suspect there's really only two speeds that matter, "<5 seconds" and ">5 seconds".
  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?
I think we can actually have a tradeoff between fast confirmations and network size. Right now every single node gets all transactions, but what if we segment the network? The network would be segmented into a hypercube with variable degree. Each vertex is a cluster of nodes (mini-networks) which gets assigned there by hashing their IP (forcing nodes into a specific position of the overall network) and they'd take care of small amounts of outgoing addresses (to mark spent inputs), achieving consensus with a much faster block chain construction (micro-tick if you will). The miners still compute the usual proof of work, but if they find a lower difficulty block, they report it to their cluster to advance the local block chain. If a miner finds a global block it starts collecting transactions from all other vertices and announces the block.

I proposed this first way back while arguing that it would allow the network to scale better, but the micro-ticks look a lot like the block creation speedup you guys are looking for :D


Title: Re: A block chain for real-time confirmations
Post by: Maged on March 16, 2011, 08:02:51 AM
On a different note, other than my "hyperchain" extension (or maybe even Cdecker's, but it's too late for me to put thought into that one), to combat the finney attack, we could do something pretty scary: (temporarily) reject blocks that contain a different transaction for a coin than the client initially received. Yes, this would open the network up to a potential attack. It'd be interesting to look into, though.


Title: Re: A block chain for real-time confirmations
Post by: Steve on March 16, 2011, 06:21:54 PM
So I have to ask, what is the problem trying to be solved?

I think the problem that this system tries to solve is in-place transactions without the need of a trusted third party.


Exactly, and it's a problem that is better solved with a trusted third party IMO.  I think all of the proposals on this thread still have an element of time that must pass before you can really consider a transaction to be firmly embedded in history.  And, what is interesting is that the very nature of double spending involves the passage of time.  The only way to ensure that a double spend has not occurred is to wait some period of time until you are confident that you are still well connected to the real network and that no double spends have been attempted.  You can gain a degree of such confidence with the existing network by staying well connected and listening for double spends even before a new block has been generated.

I think what it comes down to are a few simple choices:
a) accept a transaction immediately and not worry about the potential for a double spend
b) wait a period of time for confirmation blocks
c) use a trusted third party to clear transactions instantly

For transactions of relatively small amounts, the effort required to double spend isn't worth it hence the occurrence should be small to non-existent.  Even accounting for some amount of fraud, this cost should be far cheaper than the transaction fees currently imposed by payment processors.


Title: Re: A block chain for real-time confirmations
Post by: Maged on March 16, 2011, 06:23:35 PM
I just realized something... If "instant" transactions were made too safe/secure, why would a person pay a transaction fee? Sure, each second that goes by after the transaction would increase the amount of mining nodes that weren't around when the transaction was first submitted, but that would add little additional risk. Since we need transaction fees to maintain the block chain in the future anyway, and double-spend protection could be used to attack the network...

  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?
I think floating transactions can easily be made very low-risk.  Remember that if your client sees a new tx, it forwards it to all nodes around it.  If you are connected directly to some of the large miners, the probability that your client would not be notified of a double tx (assuming the attacker specifically sends conflicting txes to you and large miners at the same time to increase their chance) is very low.  Thus if the client informed the user if it received a conflicting tx for a tx which is to/from the user, the user could be easily notified within seconds of the original tx. 
Alternatively, each node could pass the first conflicting tx it sees or some kind of "Ive seen a tx which conflicts with this tx" message.  However, this increases the possibility for DDoS per coin (roughly x2 in terns of txes which need transferred through the network) so this is probably not a good idea. 
...why not require a certain transaction fee to enable advanced double-spend protection (basic ds protection being what we have now) for a transaction? Such a fee would make both practical AND technical sense.

Practically, if a person doesn't want to wait when they buy something with BTC from an untrusted wallet (trusted wallets being banks that the seller trusts), they could pay the fee and the seller could feel much safer sending the order to the customer right away because double spends would be seen very quickly, the transaction would be significantly more likely be added to the next block, and, assuming we make the risky choice of rejecting blocks that clients think contain a conflicting transaction, they would also be fairly protected from the 'finney attack'.

Technically, a minimum fee to get advanced double-spend protection would mean that spamming the network by using double-spends to send twice the data per transaction would cost money, just as other types of spam currently do. Additionally, again also assuming my risky defense to the 'finney attack' doesn't have holes in its logic, it also means you would have to spend money just to have the chance of splitting the network with a 'finney attack', since this would make your block invalid and would give the fee to whoever generates a legitimate block.

As an amendment to my 'finney attack' suggestion, make clients accept blocks with the "wrong" transaction if the 'wrong' transaction initially arrived within, say, 5 seconds of the first one. That way you would have lower success of purposefully splitting the network if the transactions were sent from 2 sides of the network at once. In such a case, the seller would hear of the double-spend attempt fast enough anyway.


Title: Re: A block chain for real-time confirmations
Post by: BitterTea on March 16, 2011, 06:36:10 PM

c) use a trusted third party to clear transactions instantly


Isn't that what ClearCoin is?

I don't think so. I think ClearCoin waits 6 confirmations before a balance shows up in the account. I assumed he was talking about something more like a Bitcoin "bank".


Title: Re: A block chain for real-time confirmations
Post by: jtimon on March 16, 2011, 06:56:02 PM

c) use a trusted third party to clear transactions instantly


Isn't that what ClearCoin is?

I don't think so. I think ClearCoin waits 6 confirmations before a balance shows up in the account. I assumed he was talking about something more like a Bitcoin "bank".

Yes I think he means a Bitcoin bank, payment processor, account hub...I've heard a few names for this. The proposal I like most for third parties is thi one (Bitcoin AH):

http://bitcointalk.org/index.php?topic=2628.msg37261#msg37261

Maybe third parties is the only solution, but very fast transaction (seconds) without them would be definitely better.


Title: Re: A block chain for real-time confirmations
Post by: jtimon on March 16, 2011, 07:15:16 PM
Maybe it just can't be done. Third parties wouldn't be bad, just worse than a p2p solution.


Title: Re: A block chain for real-time confirmations
Post by: Steve on March 16, 2011, 07:56:24 PM
ClearCoin with some modifications could provide a service such as this...it could do it multiple ways...if ClearCoin doesn't trust the payer, then they must first have a clear coin account with confirmed funds in it...if ClearCoin does trust you, then ClearCoin is taking on the double spend risk any time you want to buy something.  The payee trusts that ClearCoin won't double spend and accepts its payments instantly.  I think this solution is far better than complicating (and possibly compromising) the underlying bitcoin protocol.  For many people, the risk of a double spend will still be so low that they won't even use the trusted third party service.  They'll just accept the transactions immediately upon broadcast. 

I guess I just don't see a big issue with this in the current system.


Title: Re: A block chain for real-time confirmations
Post by: jtimon on March 16, 2011, 10:50:36 PM
Yes, there are lots of things that could be done with a service like this to mitigate risk, even without a registration process. You could, for instance, do [transaction limit]+[captcha solve]+[ip ban] for small transactions.

That sounds good, but I'm sorry, I don't understand it.


Title: Re: A block chain for real-time confirmations
Post by: Jim Hyslop on March 16, 2011, 11:31:43 PM
There is a big misconception I'd like to clear up before I go back and examine the details of the discussion that I've missed over the last few days.

The 10 minute interval has no connection at all to technical issues such as network latency, bitcoin creation, etc. etc. The sole purpose of the ten minute interval is to ensure that the rate of Bitcoin creation is reasonably constant and predictable. It is an economic constraint, not a technical one. If there were no constraint on Bitcoin creation, then the market would very quickly get flooded, and the value of BTC would be extremely volatile.

In a similar vein, difficulty has exactly one purpose: to maintain the constant rate of Bitcoin creation. Every 2016 blocks, the software checks how long it took to create the last 2016 blocks. The goal is exactly two weeks (do the math). If it took longer than two weeks to create 2016 blocks, then the difficulty is reduced. If it took less than two weeks, then the difficulty is increased. For the purposes of this discussion, difficulty can be ignored, and we can assume a rate of 10 minutes per block.


Title: Re: A block chain for real-time confirmations
Post by: theymos on March 16, 2011, 11:50:19 PM
The 10 minute interval has no connection at all to technical issues such as network latency, bitcoin creation, etc. etc. The sole purpose of the ten minute interval is to ensure that the rate of Bitcoin creation is reasonably constant and predictable. It is an economic constraint, not a technical one. If there were no constraint on Bitcoin creation, then the market would very quickly get flooded, and the value of BTC would be extremely volatile.

That's totally wrong. Maybe latency was one of a few factors in determining the 10-minute target, but it definitely was a factor. From the source:

Code:
        // It is not an error when generated blocks are not accepted.  By design,
        // some percentage of blocks, like 10% or more, will end up not accepted.
        // This is the normal mechanism by which the network copes with latency.

10% block loss was anticipated with even 10-minute target times. This is made worse when you reduce the target time.

Generation rate would not have been a factor in determining target time, since you can easily reduce the reward per block to get the same result.


Title: Re: A block chain for real-time confirmations
Post by: Jim Hyslop on March 17, 2011, 12:27:04 AM
I'm going to combine all my responses into a single reply. I hope this doesn't confuse anyone ('specially me :)

There are many issues with this idea, most notably the lack of miners, the continued vulnerability to the 'finney attack', and the added bloat.
Lack of miners??? The difficulty increased by 37% a few days ago because a lot of miners have jumped on board.

I've seen a few references to "the finney attack" in these forums, but I can't find a description of what it is.  Can someone point me to a discussion of the attack, please?

There are some serious issues with such an idea[...].  Another is the complexity added to the protocol.
Extending the blocks to add a new type is not a big extension to the protocol. Unless we are using different definitions of the word - to me "protocol" is the definition of how data is passed from one node to another. In any case, the protocol must be extensible or sooner or later the whole system will collapse because of its inflexibility.

Transactions are complete in milliseconds, it's the confirmations that take ten minutes, which are way faster than how this is done by just about any other online method.  Credit card transactions are, likewise, nearly instant; but it can take up to 60 days before they are final.  So I have to ask, what is the problem trying to be solved?
I thought the subject line summed it up nicely: real-time confirmations.

Your comparison is flawed, because credit card transactions are reversible. Bitcoin transactions are not. Double-spent transactions can be rejected, but not reversed. That's why a (near) real-time confirmation is desirable. Before I let the guy who showed up at my place of business walk out the door with my merchandise, I want a reasonable assurance that the Bitcoins he used are valid.

Anyone making a large transaction surely will have the patience to wait an hour or so for 6 confirmations.
Maybe for an online transaction, but I'm thinking about a face-to-face transaction. I am not going to hang around some merchant's store for an hour just to have my transaction confirmed.

I could see a separate chain running with a target time of perhaps as low as one minute, but a target time of seconds will be impossible due to latency. I don't think a separate chain is the answer, though: there would be no incentive to create blocks on it, and there are probably other methods that will work even better.
Well, until someone tosses in an idea that works better, why not continue discussing this approach? There's no rule that says we have to actually do anything with these ideas. Maybe this discussion will spark someone thinking of a better solution.

On the topic of latency - has anyone attempted to measure how long it takes for a transaction to propagate through the P2P network? Is it even possible to measure? I can think of a couple of ways to measure the propagation, but they all involve changing the client so that it reports back to a single monitoring site - a proposition which I doubt very many users would approve of.

Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?[/li][/list]
What do you mean by "floating transactions"?

The network might never be large enough to support this, though, and no changes are necessary to Bitcoin now, so it's not worth working on. By the time it becomes useful, solutions for dealing with fast transaction acceptance will already have been established.
Sorry, I cannot agree with that sentiment. That's the kind of thinking that led to the Y2K problem. People kept putting off looking at their systems, so that in the end some of the solutions that went in were poorly thought out and ill-considered, or just plain abandoned.

Also, anyone remember Lotus 1-2-3? It was one of the first spreadsheets. It quickly took a lion's share of the marketplace, but because nobody at Lotus thought ahead and tried to put in new features or otherwise improved the software, other spreadsheets were able to surpass Lotus 1-2-3's capabilities. By the time Lotus figured out what was happening, they had lost any possible advantage they may have had, and 1-2-3 died. (and then they foisted Lotus Notes on us, but that's a whole other rant :D )

The time to think about these issues is now, while we have the luxury of tossing around ideas and exploring a lot of "what if" scenarios, and while the software is still in beta and changes are expected.

That's why I'm bringing up topics like the face-to-face exchange, which (to my knowledge) aren't currently supported by any clients. Someday, they may very well be.


Title: Re: A block chain for real-time confirmations
Post by: Jim Hyslop on March 17, 2011, 12:39:32 AM
(Whew, caught up :) )
The 10 minute interval has no connection at all to technical issues such as network latency, bitcoin creation, etc. etc. The sole purpose of the ten minute interval is to ensure that the rate of Bitcoin creation is reasonably constant and predictable. It is an economic constraint, not a technical one. If there were no constraint on Bitcoin creation, then the market would very quickly get flooded, and the value of BTC would be extremely volatile.

That's totally wrong. Maybe latency was one of a few factors in determining the 10-minute target, but it definitely was a factor. From the source:

Code:
        // It is not an error when generated blocks are not accepted.  By design,
        // some percentage of blocks, like 10% or more, will end up not accepted.
        // This is the normal mechanism by which the network copes with latency.

10% block loss was anticipated with even 10-minute target times. This is made worse when you reduce the target time.

Generation rate would not have been a factor in determining target time, since you can easily reduce the reward per block to get the same result.
Well, I wouldn't say totally wrong. I interpret that comment slightly differently. My interpretation is: "because of network latency, I estimate about 10% of blocks will be rejected. That is perfectly normal and nothing to be concerned about." There's no indication in that comment whether 10% was a goal, or a byproduct of the 10 minute spacing.

At this point, that comment is the only thing I've read which suggested there were any technical considerations for choosing 10 minutes. In fact, what I have read said that if there was a reason for choosing 10 minutes, Satoshi never communicated it to anyone. Unless you have another source which confirms that network latency was a factor in choosing 10 minutes, I think we'll have to leave the question open.

And this is probably a good place to repeat the question I asked in my last post (which will probably get glossed over because I crammed so much into a single post): Has anyone measured, or calculated, how long it would take for a transaction to propagate through the network?


Title: Re: A block chain for real-time confirmations
Post by: Maged on March 17, 2011, 02:02:15 AM
There are many issues with this idea, most notably the lack of miners, the continued vulnerability to the 'finney attack', and the added bloat.
Lack of miners??? The difficulty increased by 37% a few days ago because a lot of miners have jumped on board.
That statement was in regards to an independently mined block chain that was being suggested, hence my suggestion to combine the two chains so that the same miners would mine both at the same time, as a result of mining just one.

I've seen a few references to "the finney attack" in these forums, but I can't find a description of what it is.  Can someone point me to a discussion of the attack, please?
Finney Attack, as defined by Hal:
Suppose the attacker is generating blocks occasionally. in each block he generates, he includes a transfer from address A to address B, both of which he controls.

To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store and makes a payment to your address C with his address A. You wait a few seconds, don't hear anything, and transfer the goods. He broadcasts his block now, and his transaction will take precedence over yours.

----
Also, I just realized that the risky method of rejecting suspicious blocks that I mentioned later in this thread was already discussed:
http://bitcointalk.org/index.php?topic=3441.0

Finally, I really would like to see that question answered too.


Title: Re: A block chain for real-time confirmations
Post by: MoonShadow on March 17, 2011, 04:17:54 AM

Transactions are complete in milliseconds, it's the confirmations that take ten minutes, which are way faster than how this is done by just about any other online method.  Credit card transactions are, likewise, nearly instant; but it can take up to 60 days before they are final.  So I have to ask, what is the problem trying to be solved?
I thought the subject line summed it up nicely: real-time confirmations.

Your comparison is flawed, because credit card transactions are reversible. Bitcoin transactions are not. Double-spent transactions can be rejected, but not reversed. That's why a (near) real-time confirmation is desirable. Before I let the guy who showed up at my place of business walk out the door with my merchandise, I want a reasonable assurance that the Bitcoins he used are valid.


Well, let's examine that situation.  Could a convenience store accept bitcoin in real time?  I say certainly.  You walk in to the store to buy a candy bar, if you pay cash the attendant is likely to use a cash marker as a quick check for counterfit cash, but this is only a relatively minor means of avoiding such fraud.  In a similar fashion, a POS bitcoin client can check it's (presumedly recent) copy of the blockchain against the transaction that you produce for bitcoin.  If this check says that you honestly owned those coins up to the last update, it is unlikely that you are trying to double spend.  If we are talking about something a bit pricer, such as a grocery shopping trip in the 100's-of-dollars-range or so, the POS client might also be connected to a private VPN that exists to monitor for double spends in real time, (does your credit card transaction get approved in less than three seconds?  Even if it did, would it be unreasonable for the POS system to wait three seconds, looking for a competing transaction?  Longer than three seconds, and it likley doesn't even matter if a double spend is attempted, because the odds are extremely high that this transaction would be the one to get into the blockchain anyway.) signs of network divisions, or other possible frauds.  Some store chains, such as wal-mart would be likely to do this for themselves; but smaller stores and chains could join a VPN sponsored by their association.  Anything bigger, such as buying a new car, is likely to justify the increasing certainty of one or more blockchain confirmations.  Have you ever bought a car wherein the negotiations & credit process took less than a half-hour?

My point here is that it is possible, and likely, for a vendor to have a reasonable degree of trust that a valid transaction is legit without any confirmations (depending upon the relative value of the sale) and that increasing confirmations only add to the certainty.


Title: Re: A block chain for real-time confirmations
Post by: Matt Corallo on March 17, 2011, 08:04:47 AM
I just realized something... If "instant" transactions were made too safe/secure, why would a person pay a transaction fee? Sure, each second that goes by after the transaction would increase the amount of mining nodes that weren't around when the transaction was first submitted, but that would add little additional risk. Since we need transaction fees to maintain the block chain in the future anyway, and double-spend protection could be used to attack the network...

  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?
I think floating transactions can easily be made very low-risk.  Remember that if your client sees a new tx, it forwards it to all nodes around it.  If you are connected directly to some of the large miners, the probability that your client would not be notified of a double tx (assuming the attacker specifically sends conflicting txes to you and large miners at the same time to increase their chance) is very low.  Thus if the client informed the user if it received a conflicting tx for a tx which is to/from the user, the user could be easily notified within seconds of the original tx. 
Alternatively, each node could pass the first conflicting tx it sees or some kind of "Ive seen a tx which conflicts with this tx" message.  However, this increases the possibility for DDoS per coin (roughly x2 in terns of txes which need transferred through the network) so this is probably not a good idea. 
...why not require a certain transaction fee to enable advanced double-spend protection (basic ds protection being what we have now) for a transaction? Such a fee would make both practical AND technical sense.

Practically, if a person doesn't want to wait when they buy something with BTC from an untrusted wallet (trusted wallets being banks that the seller trusts), they could pay the fee and the seller could feel much safer sending the order to the customer right away because double spends would be seen very quickly, the transaction would be significantly more likely be added to the next block, and, assuming we make the risky choice of rejecting blocks that clients think contain a conflicting transaction, they would also be fairly protected from the 'finney attack'.

Technically, a minimum fee to get advanced double-spend protection would mean that spamming the network by using double-spends to send twice the data per transaction would cost money, just as other types of spam currently do. Additionally, again also assuming my risky defense to the 'finney attack' doesn't have holes in its logic, it also means you would have to spend money just to have the chance of splitting the network with a 'finney attack', since this would make your block invalid and would give the fee to whoever generates a legitimate block.

As an amendment to my 'finney attack' suggestion, make clients accept blocks with the "wrong" transaction if the 'wrong' transaction initially arrived within, say, 5 seconds of the first one. That way you would have lower success of purposefully splitting the network if the transactions were sent from 2 sides of the network at once. In such a case, the seller would hear of the double-spend attempt fast enough anyway.
Not at all true.  The point of a double spend attack is that although you put out two transactions, you don't pay for one of them.  Thus, charging people to have "double spend protection" wouldn't work as only one of the two transactions would be considered "valid" and thus only one would make it into the block chain.  The other transaction wouldn't be paid by or to anyone.  So if nodes relayed more blocks an attacker wouldn't pay any more to get more txes being pushed through the network (hence DDoS potential).


Title: Re: A block chain for real-time confirmations
Post by: Maged on March 18, 2011, 04:17:01 AM
I just realized something... If "instant" transactions were made too safe/secure, why would a person pay a transaction fee? Sure, each second that goes by after the transaction would increase the amount of mining nodes that weren't around when the transaction was first submitted, but that would add little additional risk. Since we need transaction fees to maintain the block chain in the future anyway, and double-spend protection could be used to attack the network...

  • Can floating transactions be made low-risk enough that it doesn't matter if they aren't included in a block right away?
I think floating transactions can easily be made very low-risk.  Remember that if your client sees a new tx, it forwards it to all nodes around it.  If you are connected directly to some of the large miners, the probability that your client would not be notified of a double tx (assuming the attacker specifically sends conflicting txes to you and large miners at the same time to increase their chance) is very low.  Thus if the client informed the user if it received a conflicting tx for a tx which is to/from the user, the user could be easily notified within seconds of the original tx. 
Alternatively, each node could pass the first conflicting tx it sees or some kind of "Ive seen a tx which conflicts with this tx" message.  However, this increases the possibility for DDoS per coin (roughly x2 in terns of txes which need transferred through the network) so this is probably not a good idea. 
...why not require a certain transaction fee to enable advanced double-spend protection (basic ds protection being what we have now) for a transaction? Such a fee would make both practical AND technical sense.

Practically, if a person doesn't want to wait when they buy something with BTC from an untrusted wallet (trusted wallets being banks that the seller trusts), they could pay the fee and the seller could feel much safer sending the order to the customer right away because double spends would be seen very quickly, the transaction would be significantly more likely be added to the next block, and, assuming we make the risky choice of rejecting blocks that clients think contain a conflicting transaction, they would also be fairly protected from the 'finney attack'.

Technically, a minimum fee to get advanced double-spend protection would mean that spamming the network by using double-spends to send twice the data per transaction would cost money, just as other types of spam currently do. Additionally, again also assuming my risky defense to the 'finney attack' doesn't have holes in its logic, it also means you would have to spend money just to have the chance of splitting the network with a 'finney attack', since this would make your block invalid and would give the fee to whoever generates a legitimate block.

As an amendment to my 'finney attack' suggestion, make clients accept blocks with the "wrong" transaction if the 'wrong' transaction initially arrived within, say, 5 seconds of the first one. That way you would have lower success of purposefully splitting the network if the transactions were sent from 2 sides of the network at once. In such a case, the seller would hear of the double-spend attempt fast enough anyway.
Not at all true.  The point of a double spend attack is that although you put out two transactions, you don't pay for one of them.  Thus, charging people to have "double spend protection" wouldn't work as only one of the two transactions would be considered "valid" and thus only one would make it into the block chain.  The other transaction wouldn't be paid by or to anyone.  So if nodes relayed more blocks an attacker wouldn't pay any more to get more txes being pushed through the network (hence DDoS potential).
Oh, I think I get what you are saying: Although the original transaction would have the fee added, there's nothing that would require the double-spent coin to have the fee. However, it doesn't really matter. As long as one of the transactions (the real one) pays the minimum required fee (let's assume that it is .01 BTC), you would still need a minimum of .02 BTC to transverse the network (.01 output, .01 fee), which is a code change that would need to be made (nobody sends real transactions with a .01 fee that output less than .01 BTC anyway). That would result in a .01 BTC/tx average for the network. Hell, we're already getting DDoSd with .01 BTC anyway.


Title: Re: A block chain for real-time confirmations
Post by: Mike Hearn on March 18, 2011, 11:46:17 AM
So to clear this up, the 10 minute interval is to do with latency and Satoshi has confirmed it to me in the past via email. Let me quote from some of our conversations:

Quote from: satoshi
Quote from: mike
Another is the 10 minute block target. I understand this was chosen to
allow transactions to propagate through the network. However existing
large P2P networks like BGP can propagate new data worldwide in <1
minute.

If propagation is 1 minute, then 10 minutes was a good guess.  Then nodes are only losing 10% of their work (1 minute/10 minutes).  If the CPU time wasted by latency was a more significant share, there may be weaknesses I haven't thought of.  An attacker would not be affected by latency, since he's chaining his own blocks, so he would have an advantage.  The chain would temporarily fork more often due to latency.

Though Satoshi is not posting to the forums at the moment, he is still paying attention to email, at least I get answers to my questions that way.