BIP Draft - Instant Partial Confirmation

[Serith]

Sorry, I promised to comment on your proposal in my thread: Collaboration between pools could make accepting 0-confirmation transaction safe , but then Meni Rosenfeld came up with his proposal: Trustless, instant, off-the-chain Bitcoin payments, which seemed much better all around, so I stopped thinking about your post too.


When a miner commits to include a transaction into a block, essentially it means that he promises to mine on top of a shorter blockchain if necessary. The condition could be to mine on top of a blockchain that is no shorter then by one block to thwart Finney attack, two blocks to be immune to extended Finney attack with two premined blocks or even six to make the attack unrealistic. But a miner has to know that he is not alone in this, and that the shorter blockchain will eventually become the longest, otherwise he makes himself open to the attack where he would lose mining time.

In my proposal it was solved with multisig transaction, but that would bring more centralization to Bitcoin. In yours there has to be additional protocol for that.

As an example, upon receiving a block that invalidates a confirmation, an IPC-participating miner could broadcast a message to the other (up to) 2016 miners saying "Hey! I don't like block X because it forces me to fail on a commitment, and I propose attacking it."  If the majority of miners send that message, they could follow it up with another message: "It looks to me like a majority of the mining power doesn't like block X, so I am attacking/ignoring it."

This is where you briefly touched it.


I just thought about possibility of using Assurance contracts

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include applications where frequent, small pledges need to be made automatically, for instance internet radio station funding and web page translation. Consider a browser extension that you send a bit of money to. It detects the current language of the page and broadcasts a pledge for a translation into your language to be prepared. If enough users with the extension land on the same page at the same time (eg, it was linked to from somewhere high traffic), then enough pledges are broadcast to trigger a payment to a company who prepares a high quality translation. When complete it automatically loads in your browser.

Create such transaction with high miner's fee, ask specific miners to chipin one satoshi to indicate their commitment, and then broadcast the transaction to let everyone know that there is indeed the majority of the network behind that transaction.

[casascius]

1. You can ask miners not to follow certain longer block branch, but the have the opposite incentive.

Which miners would have such an incentive?

They would only follow it if the majority of miners independently asserted that they don't want to follow it if a majority of other miners say the same thing.  And there is always an incentive, or at least no disincentive, in following the majority of miners.

2. You can't tell nodes or miners to invalidate blocks even if you have a proof of dishonest behavior, because that will give you a tool to invalidate blocks in the past. And that would give you a tool to revert millions of other (unrelated) transactions!

It is not a message that says "Please invalidate arbitrary block X".  The only kind of block that can be invalidated is a brand new block containing a conflicting transaction never-before-heard by the majority of miners, only after the majority of miners has actively committed to some other transaction they in fact have already heard about, and only after the majority of miners have reconciled with one another to agree that that's what happened.  However, my suggestion is rather off-the-cuff and could be infeasible - please provide an example of how you figure it could be used in an attack.

[notme]

That's arguable since p2pool mining requires a blockchain and regular pool mining can be done on a computer with just a livecd.

That's how it is today, but that is almost certainly not how it will be the day 8064 discrete mining pools ever come into existence.

How are you going to p2pool mine without a blockchain?  You would need supernodes or some other form of centralization.

Also, I consider it a concern because there are no rules in the system preventing it.  Sorry, but your guess as to what will happen just doesn't satisfy me.

There are no rules preventing me from repetitiously slamming my own head on the sidewalk, but it can be safely said it is unlikely to happen because there is no incentive to do such a thing.  As difficulty tends to infinity, the likelihood of someone solving a block by themselves in their own lifetime approaches zero, and so it's a pretty safe bet it's not going to be very popular as time goes on.

But 4032 pools that solve one block a month each doesn't sound entirely unreasonable to me, but I'll concede it is not a pressing issue and one that could be solve fairly easily as long as transient miners don't become an issue.

[Serith]

I just thought about possibility of using Assurance contracts

Examples where Bitcoin is superior to traditional payment methods for assurance contract fundraising include applications where frequent, small pledges need to be made automatically, for instance internet radio station funding and web page translation. Consider a browser extension that you send a bit of money to. It detects the current language of the page and broadcasts a pledge for a translation into your language to be prepared. If enough users with the extension land on the same page at the same time (eg, it was linked to from somewhere high traffic), then enough pledges are broadcast to trigger a payment to a company who prepares a high quality translation. When complete it automatically loads in your browser.

Create such transaction with high miner's fee, ask specific miners to chipin one satoshi to indicate their commitment, and then broadcast the transaction to let everyone know that there is indeed the majority of the network behind that transaction.

In general, could Assurance contracts serve as a voting system?

[casascius]

How are you going to p2pool mine without a blockchain?  You would need supernodes or some other form of centralization.

Who knows?  If I had an answer (I don't), it would probably be obsolete when the time came.  There are already discussions on how to use a meta-tree to allow a node to mine without the whole block chain.  A live CD (assuming CD's are not as dead as 8-tracks by then) could potentially pull all of that information off the network and into a ram drive and start mining with it.  USB flash drives can already hold the block chain and would certainly be able to handle a meta-tree solution.  By the time there's a possibility of 8000+ pools, a lot of evolution will have taken place and my guess is both the questions and the answers to them will probably have changed a lot.

[gmaxwell]

Just so I understand, how does p2pool collectively commit to anything?  Include the commitment in a sharechain block?
What about traditional centralized mining pools?  I agree that having proof of trying is a desirable benefit.

Imagine a mining pool. You have shares— they're really all failed blocks, they still have hashes that connect down to the transactions so you can show that the shares were an attempt to mine a particular transaction.

Now, add an extra hash to the coinbase, like merged mining, except its the hash of a prior share (of at least some difficulty). Bam. Now you have a share chain.   You can use this for a byzantine consensus of who's putting how much hash power into the pool. This is what p2pool does— nodes share shares with the difficulty adjusted so that on average there is one per ten seconds. They use this to decide who gets paid and they impose some validity rules on the candidate blocks before they'll be considered valid shares, e.g. that they pay the right people relative to the share chain consensus.

There is no reason that the validity rules can't include something like "your block must include txn XXX" where XXX is some txn that previously made it into the share chain with enough fees and without yet being conflicted in the bitcoin chain.  Then the sharechain itself is proof of past, current, and future effort being put into mining a transaction, as leaving out that txn would prevent you from getting paid by the pool, and you can easily extract this proof and show others. No signature validations either, just a bunch of small headers and cheap hash operations.

A centralized pool could generate such a sharechain itself internally— although if the pool was the only participant in a particular share chain there wouldn't be an incentive to not drop the txn out prematurely, so it's only evidence of past effort.  To improve on that centralized pools could participate in sharechains among themselves (probably slower, e.g. 1 minute, for latency reasons), meta-pooling their payouts and providing more trustworthy evidence of future effort (and lowering their variance too, I suppose).

[commonancestor]

Sorry if this is being slightly off-topic. If I am right here, the following approach would help greatly to reduce chances of double-spend.

The initial transactions are relayed around the network in few seconds. It is the blocks which take about 10 minutes. I understand that nodes immediately throw away any transactions which they identify as double-spend attempts. But instead they should flag them "double-spend attempt!" and relay them. This way the network will know about the double-spend in few seconds. Then after few blocks everyone could forget them.
It is still possible that the news will not reach every node immediately, but still better than waiting for next block.
It still needs to be decided how to prevent any spamming of the network this way but this seems doable.

[gmaxwell]

But instead they should flag them "double-spend attempt!" and relay them. This way the network will know about the double-spend in few seconds. Then after few blocks everyone could forget them.
It is still possible that the news will not reach every node immediately, but still better than waiting for next block.
It still needs to be decided how to prevent any spamming of the network this way but this seems doable.

Not a new idea and the flooding problem has a solution too, e.g. http://sourceforge.net/mailarchive/message.php?msg_id=27901281

Ideas are cheap. Got code?  

Though this provides no protection against finny attacks.

[runeks]

I believe it has been touched upon somewhat already, but what about if - instead of having to trust miners to include a transaction into a block - the client is sent blocks that have difficulty of 1/600th of the Bitcoin block chain's difficulty? This would produce, on average, one block (with 1/600th the difficulty of the block chain) every one second (provided all the miners participate). The receiver can actually check that the miner is working on his transaction if the miner creates a hash tree of all the transactions in the block he's mining, and then sends the client the necessary leaf hashes to verify that. The miner would only have to send 2*log2(num_tx)-1 hashes from the hash tree to the client in order for the client to verify that his transaction is being mined on in a block. This is an implicit guarantee that the client's transaction is not a double spend, as the miner's block wouldn't get accepted if it contained a double spend.

So if we let the data blocks in this example be transactions, and the client's transaction be "Data block 000", the miner would only have to send "Hash 0-0-1", "Hash 0-0", "Hash 0-1", "Hash 0" and "Hash 1" in order for the client to verify that his transaction is being worked on (since "Top hash" is included in the block header and the client knows the hash of his own transaction ("Hash 0-0-0").



Does anyone have any information on how much data a P2P network specializing in forwarding these types of messages would be able to handle? Only the block header would need to be sent out every 1 second (assuming all miners participate). When new transactions are sent into the network, that some client wishes to secure against a double spend, a hash of this transaction should be spread around in the network, so that clients can confirm that their transaction is included in the block. Perhaps the system should include some way for clients to advertise which leaf hashes they need in order to confirm that their own transaction is included in the block. Ie., if I'm concerned about the two transactions "Data block 003" and "Data block 006" being double spent, I wouldn't need to be sent "0-0-0", "0-0-1", "1-0-0" and "1-0-1" as they are not needed for me to verify that my transactions fit into the hash tree.

[gmaxwell]

I believe it has been touched upon somewhat already, but what about if - instead of having to trust miners to include a transaction into a block - the client is sent blocks that have difficulty of 1/600th of the Bitcoin block chain's difficulty? This would produce, on average, one block (with 1/600th the difficulty of the block chain) every one second (provided all the miners participate).

It's not a guarantee because the inclusion isn't fixed like it its when a transaction is actually mined, a miner could stop at any point.  Perhaps you could imagine some kind of system for discouraging that, but it would need a consensus mechanism... and would have to force all miners to mine the same txns (or at least no conflicts)

P2Pool now does this— miners exposing what they're working on in p2pool shares with no enforcement— however.

[runeks]

I believe it has been touched upon somewhat already, but what about if - instead of having to trust miners to include a transaction into a block - the client is sent blocks that have difficulty of 1/600th of the Bitcoin block chain's difficulty? This would produce, on average, one block (with 1/600th the difficulty of the block chain) every one second (provided all the miners participate).

It's not a guarantee because the inclusion isn't fixed like it its when a transaction is actually mined, a miner could stop at any point.  Perhaps you could imagine some kind of system for discouraging that, but it would need a consensus mechanism... and would have to force all miners to mine the same txns (or at least no conflicts)

I see your point. If I'm standing at the store and my payment device sends a transaction to a miner, waits for 10 1-second blocks - which I show to the guy at the store receiving the payment - and then leave, I can just send out a new transaction when I'm out of the store that spends the same output but has a higher fee, and the miner will want to include this instead.

Would the idea then be to make a share chain that is invalid if it contains two transactions spending the same output? So that in order for the miner to include a double spend, he would have to discard the shares that include the original transaction? That could be a problem with 1-second blocks though...

[Maged]

Would the idea then be to make a share chain that is invalid if it contains two transactions spending the same output? So that in order for the miner to include a double spend, he would have to discard the shares that include the original transaction? That could be a problem with 1-second blocks though...

Interesting. That solves the political problem with the idea that individual P2Pool miners would be forced into including certain transactions. Instead of being forced to include certain transactions, they just wouldn't be able to include one that conflicts with past blocks on the sharechain.

[runeks]

Would the idea then be to make a share chain that is invalid if it contains two transactions spending the same output? So that in order for the miner to include a double spend, he would have to discard the shares that include the original transaction? That could be a problem with 1-second blocks though...

Interesting. That solves the political problem with the idea that individual P2Pool miners would be forced into including certain transactions. Instead of being forced to include certain transactions, they just wouldn't be able to include one that conflicts with past blocks on the sharechain.

Are p2pool miners forced to include certain transactions as it is now? And if so, how come?

[Maged]

Would the idea then be to make a share chain that is invalid if it contains two transactions spending the same output? So that in order for the miner to include a double spend, he would have to discard the shares that include the original transaction? That could be a problem with 1-second blocks though...

Interesting. That solves the political problem with the idea that individual P2Pool miners would be forced into including certain transactions. Instead of being forced to include certain transactions, they just wouldn't be able to include one that conflicts with past blocks on the sharechain.

Are p2pool miners forced to include certain transactions as it is now? And if so, how come?

Not as far as I know. My post was in reference to the other idea in this thread where they would be forced to include transactions.

[gmaxwell]

Interesting. That solves the political problem with the idea that individual P2Pool miners would be forced into including certain transactions. Instead of being forced to include certain transactions, they just wouldn't be able to include one that conflicts with past blocks on the sharechain.

It doesn't really.

The expectation of solo mining is the same as pooled mining. If you'd like to split off and try to mine a conflicting transaction you can and you won't lose any coin on average— you'll even gain if the conflict has higher fees.

[Maged]

Interesting. That solves the political problem with the idea that individual P2Pool miners would be forced into including certain transactions. Instead of being forced to include certain transactions, they just wouldn't be able to include one that conflicts with past blocks on the sharechain.

It doesn't really.

The expectation of solo mining is the same as pooled mining. If you'd like to split off and try to mine a conflicting transaction you can and you won't lose any coin on average— you'll even gain if the conflict has higher fees.

Well, yeah. None of this solves the underlying problem that zero-confirmation transactions shouldn't be used for anything valuable and/or irrevocable because of the Finney attack. The only problem this helps solve is the enforcement of ethics if you want to use a specific pool.

[Mike Hearn]

I also think that pools will become less prominent in future. If the ASIC transition really does happen then non-serious miners (the type who use live cds) will get kicked out and the only miners left will be those who treat it as an actual business. If you've invested heavily into specialized equipment then mining solo against your own bitcoind isn't such a big deal. If you represent 0.1% of the networks hash power then you'd get a block every 10 days or so - hardly eye-bleeding variance risk given the time and effort it took to set up your mining farm.

Also, as mining gets more and more competitive (today it isn't), fees levied by pool operators would become a bigger burden. In theory mining should be a close to marginal business given the relatively low barriers to entry. P2Pool does not charge fees, and it may well survive a lot longer, but again - there's a certain simplicity to just mining solo that may be appealing for large-ish miners, and I think eventually all miners will be somewhat large. I doubt we actually need more than 1000 distinct miners as long as they're distributed around the globe.

[gmaxwell]

P2Pool does not charge fees, and it may well survive a lot longer, but again - there's a certain simplicity to just mining solo that may be appealing for large-ish miners,

Currently P2pool is simpler to run than solo mining, though this is an artifact of ~no larger miners except Luke bothering to submit patches to  full node software for mining scalability.

and I think eventually all miners will be somewhat large. I doubt we actually need more than 1000 distinct miners as long as they're distributed around the globe.

Your opposition to long term real decentralization in Bitcoin is well established at this point.  I think as a community we need to start speaking up emphatically against these positions. I hope you will not take it personally when I do, because I have great respect for you no matter how much I disagree with you on this subject.

If Bitcoin were only to have 1000 distinct non-trivial mining entities then I believe Bitcoin would be worse than pointless.  With so few entities having a veto over the validity of transactions it would be substantially more centralized than any of the largely existing widely used currencies— as there are are far more bank like entities than that for any major currency, and unlike bitcoin other currencies have cash transactions which are more reversal resistant. The cost and complexity of bitcoin is not justified if it doesn't provide a solid advantage over highly trust centric (semi-)centralized systems like the USD.

From a technical perspective: If you were only to have 1000 entities the Bitcoin consensus algorithm is fundamentally wrong:  The stochastic POW chain consensus provides slow and unpredictable eventual consensus. A consensus of 1000 entities can be accomplished far more inexpensively, rapidly, and reliably by identify them and using a majority vote with digital signatures. There are places for systems with this kind of security property, and they are the sorts of things OpenTransactions seek to create (potentially ones with much better scalability than the broadcast based Bitcoin system).

It would certainly be nice if there existed a global, thoroughly distributed, cheaply validated, medium of exchange which could enable trade between distinct scalable and fast confirming federated systems... but it won't be so if Bitcoin tries to become everything to everyone with forcing users through services providers and limiting miners to those who can handle gigabits of bandwidth for multigigabyte blocks.

Fast provably strong confirmations are not something the Bitcoin consensus algorithm can do without sacrificing the things that make Bitcoin worth having and we shouldn't be afraid to admit this.

[runeks]

Fast provably strong confirmations are not something the Bitcoin consensus algorithm can do without sacrificing the things that make Bitcoin worth having and we shouldn't be afraid to admit this.

My motivation isn't to change the Bitcoin algorithm. I started out thinking on ways to extend it, with another - optional - layer on top. Proof-of-work might not be the right way forward for fast double spend prevention though.

I'm thinking that it might be possible to leverage the fact that Bitcoin takes care of the long term double spend prevention. Ie., after an hour or so, the block chain prevents double spends. Perhaps there's some clever protocol that can utilize this feature of Bitcoin, so that it can concentrate on only preventing (with a certain probability) double spends for an hour, or so.

I'm also thinking that it doesn't need to prevent double spends with absolute certainty (not even the Bitcoin protocol can do this). We only need to know the probability of a certain transaction being double spent, and using the value of this transaction, we can charge a fee that makes it economically disadvantageous to attempt a double spend.

But this is just brainstorming for me.

I really do think that the ideas of Bitcoin replacing VISA are misguided. We should be comparing the Bitcoin network to SWIFT (with its 1-day+ settlement time) and not VISA, with its ~10-second settlement time (notwithstanding chargebacks). I don't think 10,000 transactions per second in the Bitcoin network will ever happen, when the settlement time is ~1 hour.

[Mike Hearn]

I'm hardly opposed to decentralization, otherwise I'd just recommend everyone use blockchain.info as their mobile wallet instead of putting so much effort into an SPV client, right?

I think the disagreement here comes from two sources. One, prediction of the future is not casting an opinion on it. Right now there are only, what, 12 or 15 miners with most of the power? Hardly what Satoshi envisioned. Yet somehow Bitcoin functions and people are using it. When I say we may not need more than 1000 miners, I'm not saying that would be the best possible configuration, just that in practice we may not need more - Bitcoin would probably work OK.

Two, wildly differing perspectives on the cost of hardware. The cost of the equipment needed to run a node that keeps up with VISA (or beat it) has come down a lot with better calculations, optimizations to the software, etc. If in future you need a 24 core machine with 12 drives attached to it to run a full node, I don't see that as leading to centralization and therefore I don't see it as needing to be fixed, because in a world where Bitcoin was so widely used there'd be plenty of people and organizations willing to run such nodes and the cost of the hardware would have fallen a lot anyway.

BTW, one of the prime advantages of proof of work, as I see it, is there's no need for co-ordination. It may well be that 1000 nodes can achieve consensus much faster just by swapping signatures amongst themselves. However if you want to become the 1001st node (or stop being the first node) that's much harder in such a design. With PoW you just start calculating, you can join or leave the network at any time. That "robust simplicity" as Satoshi put it is a great thing.

I really do think that the ideas of Bitcoin replacing VISA are misguided. We should be comparing the Bitcoin network to SWIFT (with its 1-day+ settlement time) and not VISA, with its ~10-second settlement time (notwithstanding chargebacks).

I don't think you can say "notwithstanding chargebacks". If you don't care about chargebacks/double spends then Bitcoin settles in a few seconds, about the same speed as card payments today. And if you throw trusted hardware into the mix (like smart cards, or computers with TPM chips), you can trust you have the money instantly, as you have some confidence that the hardware holding the private keys won't allow the owner to make double spends.

Let's be clear, Bitcoin is a set of techniques to reduce the probability of people rolling back their spends and it does a very fine job of that. We can layer more techniques on top to try and push the envelope around value/speed, but those techniques don't have to be extensions of the core system. For instance you can do what the credit card system does and have deep risk analysis of customers. You can have double spend insurance. You can have double spend alerts. You can leverage secure hardware, like trusted computing does. You can experiment with networks of payment channels routers, like in Menis proposal.

Probably we'll end up with some combination of these ideas, which will mean that plenty of Bitcoin merchants accept payments instantly and in practice users don't need to wait for confirmation.

It'd be neat if somebody could find a way to converge on a global consensus much faster. The physics of message propagation throughout a large broadcast network suggest it won't be feasible for a while though.