Bitcoin Forum
May 04, 2024, 07:15:23 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: 10 minutes target, double-spending and wasted work from forks  (Read 2399 times)
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 23, 2011, 06:39:09 PM
Last edit: April 24, 2011, 01:12:33 PM by jtimon
 #1

Sorry if this is answered in the wiki or in some place in the  forum, but I just cannot find it.
Somewhere in the forum I've read that 10 minutes is the time that will take for a new generated block to be received by all nodes (without the other nodes creating a new block).
That is, the 10 minutes target would be there to prevent forks. You don't want forks because you don't want orphan blocks.
Is this true?
Where can I find the math behind it?

In the ripple project a bitcoin-like block chain for commit transactions it's being considered. The needs of ripple are different than bitcoin's though. First, I want to clarify that I don't represent ripple and they may have different opinions about what the needs of distributed ripple actually are.
We just want a distributed timestamping service. A transaction would have an expiration block number field. If it gets included in the block chain before that number, the transaction is valid. If not, the transaction won't be included in the block chain.
So we don't have double spend transactions.
As the ripple chain won't issue bitcoins, we don't have an incentive for the miners.
The solution could be for the creator of the transaction to mine his own mini-block with his transaction. A block (or mini-block) could contain others and add the proof of work on them to their own until the target difficulty is reached. This creates an incentive for the nodes to include transactions that are not their own.
Orphan blocks are not that bad in this system because we don't have double spend transactions and no miner will lost money with them. If a transaction gets out of the chain (because its block becomes orphan) and hasn't expired yet, it can still be included in the chain again and be valid.

Could we decrease the generation target time?

Another door that opens the absence of double spending transactions is the possibility of merging chains.
There's a possible attack. The ripple payer (who is presumably wants to include the transaction even if it has expired) could pretend that the transaction has been included on time, but in other branch of the chain. The transaction would become valid qith the merge.
The solution I thought was to require a minimum length (in work) and a maximum difference with the longest chain (also in work) to be merged.
If merges are possible, do we need a time target at all?
We could work just with one mini-block per transaction (although the mini-block could still include orphan mini-blocks).

Thoughts?

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
1714806923
Hero Member
*
Offline Offline

Posts: 1714806923

View Profile Personal Message (Offline)

Ignore
1714806923
Reply with quote  #2

1714806923
Report to moderator
"This isn't the kind of software where we can leave so many unresolved bugs that we need a tracker for them." -- Satoshi
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714806923
Hero Member
*
Offline Offline

Posts: 1714806923

View Profile Personal Message (Offline)

Ignore
1714806923
Reply with quote  #2

1714806923
Report to moderator
1714806923
Hero Member
*
Offline Offline

Posts: 1714806923

View Profile Personal Message (Offline)

Ignore
1714806923
Reply with quote  #2

1714806923
Report to moderator
FooDSt4mP
Full Member
***
Offline Offline

Activity: 182
Merit: 100


View Profile
April 24, 2011, 01:39:25 AM
 #2

Sorry if this is answered in the wiki or in some place in the  forum, but I just cannot find it.
Somewhere in the forum I've read that 10 minutes is the time that will take for a new generated block to be received by all nodes (without the other nodes creating a new block).
That is, the 10 minutes target would be there to prevent forks. You don't want forks because you don't want orphan blocks.
Is this true?
Where can I find the math behind it?

In the ripple project a bitcoin-like block chain for commit transactions it's being considered. The needs of ripple are different than bitcoin's though. First, I want to clarify that I don't represent ripple and they may have different opinions about what the needs of distributed ripple actually are.
We just want a distributed timestamping service. A transaction would have an expiration block number field. If it gets included in the block chain before that number, the transaction is valid. If not, the transaction won't be included in the block chain.
So we don't have double spend transactions.
As the ripple chain won't issue bitcoins, we don't have an incentive for the miners.
The solution could be for the creator of the transaction to mine his own mini-block with his transaction. A block (or mini-block) could contain others and add the proof of work on them to their own until the target difficulty is reached. This creates an incentive for the nodes to include transactions that are not their own.
Orphan blocks are not that bad in this system because we don't have double spend transactions and no miner will lost money with them. If a transaction gets out of the chain (because its block becomes orphan) and hasn't expired yet, it can still be included in the chain again and be valid.

Could we decrease the generation target time?

Another door that opens the absence of double spending transactions is the possibility of merging chains.
There's a possible attack. The ripple payer (who is presumably wants to include the transaction even if it has expired) could pretend that the transaction has been included on time, but in other branch of the chain. The transaction would become valid qith the merge.
The solution I thought was to require a minimum length (in work) and a maximum difference with the longest chain (also in work) to be merged.
If merges are possible, do we need a time target at all?
We could work just with one mini-block per transaction (although the mini-block could still include orphan mini-blocks).

Thoughts?


http://www.bitcoin.org/bitcoin.pdf

As we slide down the banister of life, this is just another splinter in our ass.
theymos
Administrator
Legendary
*
Offline Offline

Activity: 5194
Merit: 12968


View Profile
April 24, 2011, 03:53:58 AM
 #3

Latency should never be a factor. Otherwise, someone with good network resources will have an advantage, which breaks the "one CPU per vote" principle.

It could probably be reduced to a minute or two with current network conditions. 10 minutes is designed to work with any future eventuality.

For timestamping, I'd just put a hash in the Bitcoin block chain. Bitcoin transactions can contain arbitrary data.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 24, 2011, 10:51:43 AM
 #4


I've already read that. The only thing I can find there about the 10 minutes is "If we suppose blocks are generated every 10 minutes..."

Latency should never be a factor. Otherwise, someone with good network resources will have an advantage, which breaks the "one CPU per vote" principle.

Take into account that we don't reward block generators. All the CPU work someone does is to commit his own transaction.
The only advantage would be to commit his transactions first.

It could probably be reduced to a minute or two with current network conditions. 10 minutes is designed to work with any future eventuality.

For timestamping, I'd just put a hash in the Bitcoin block chain. Bitcoin transactions can contain arbitrary data.

Interesting. I didn't know.

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1129


View Profile
April 24, 2011, 11:40:19 AM
Merited by ABCbits (1)
 #5

This is mentioned in the FAQ actually. Let me know if it's not clear and I'll rewrite the answer (I wrote the original):

https://en.bitcoin.it/wiki/FAQ#Why_do_I_have_to_wait_10_minutes_before_I_can_spend_money_I_received?

Quote
Why ten minutes specifically? It is a tradeoff chosen by Satoshi between propagation time of new blocks in large networks and the amount of work wasted due to chain splits.

To traverse the network blocks must be transmitted, their contents verified and then relayed onwards. With huge blocks and large networks this could potentially be quite slow. If it takes a minute to propagate a block then with a 10 minute block time only 10% of the total work is being wasted on splits that are then resolved within a single block.
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 24, 2011, 01:11:06 PM
 #6

This is mentioned in the FAQ actually. Let me know if it's not clear and I'll rewrite the answer (I wrote the original):

https://en.bitcoin.it/wiki/FAQ#Why_do_I_have_to_wait_10_minutes_before_I_can_spend_money_I_received?

Quote
Why ten minutes specifically? It is a tradeoff chosen by Satoshi between propagation time of new blocks in large networks and the amount of work wasted due to chain splits.

To traverse the network blocks must be transmitted, their contents verified and then relayed onwards. With huge blocks and large networks this could potentially be quite slow. If it takes a minute to propagate a block then with a 10 minute block time only 10% of the total work is being wasted on splits that are then resolved within a single block.

Thank you. I should have read it but I couldn't find it.
So its there to prevent forks but, more specifically, to prevent the waste of work by the network.

But if we can "reuse" the wasted work, we can increase the generation rate, right?
We can re-include orphan blocks (or mini-blocks) and add their work to the work of the block they're solving.
If two competing branches became big enough (and there's not a big length difference between them) they could be merged because we don't have conflicting transactions (like double spending in bitcoin).

Could we operate a block chain like this without time target at all (just a minimum work per mini-block)?

This is not for bitcoin. I'm just trying to use the block chain idea, adapting it to other needs.
Apart from not needing to prevent conflicting transactions and not having to issue currency to incentive any miner (that makes impossible for the bitcoin chain to consider merges), there is another main difference.
We'll use the block chain to manage the expiration of transactions, so the faster the block generation the better.

If anyone see any flaws in the idea, please point them out.



2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416
Merit: 277


View Profile
April 24, 2011, 11:42:17 PM
Merited by ABCbits (1)
 #7

Somewhere in the forum I've read that 10 minutes is the time that will take for a new generated block to be received by all nodes (without the other nodes creating a new block).

Where can I find the math behind it?

Although you may hear that the 10 minute average block generation time was calculated based on propagation times and expected future transaction volumes, you should bear in mind that 10 minutes is a nice round number and that no calculations or simulations have come to light so far.

The time to transmit the transactions and blocks is small compared to the time taken to verify the data. The main obstacle to faster propagation times for blocks and transactions is that the data is checked before it is relayed. From a programming point of view, this is convenient as we're always sure that our client's view of the world is consistent even if other clients are trying to deceive it. However, given that the vast majority of clients are honest, it does seem a bit of a waste that all the clients redo the same calculations.

In order to speed block propagation there are several strategies which are faster but more complicated:
When a client receives a new transaction or block it records from where it came and advertises that it has the new transaction straight away. If another client requests the new transaction then then it is relayed straight away. When the client has time to check the transaction, if it's found to be bad then the client deletes it and makes a note to check transactions from that sender before advertising it next time. A client would be forgiven after a certain amount of time.
For blocks, the client should check successive individual transactions in the block in random order.

ByteCoin
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1129


View Profile
April 25, 2011, 09:38:52 AM
 #8

Yeah, to be clear the impression I got from Satoshi is that 10 minutes was an educated guess rather than the result of simulations or formulas. BGP is able to broadcast updates globally in less than one minute, so if we assume BitCoin is one day as large as the BGP mesh then 10 minutes wasn't really a bad guess.
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 25, 2011, 10:10:17 AM
 #9

Thank you, guys. Is good to know this because it means we could have a faster chain even if my proposal for not requiring time target (in a hypothetical ripple commit chain) is not feasible.

But what do you think about it? Does it make sense? Would it be feasible?

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416
Merit: 277


View Profile
April 26, 2011, 12:47:34 AM
 #10

But what do you think about it? Does it make sense? Would it be feasible?

I'm willing to evaluate the feasibility of proposed schemes if they are specified in sufficient detail. Your proposal is substantially different from bitcoin and the information you provide is not sufficient to provide a clear understanding of how it would work.

ByteCoin
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1129


View Profile
April 26, 2011, 08:43:52 AM
 #11

The other thing to think about is that there's really only two interesting speeds, <5 seconds and >5 seconds.

It's probably not possible to globally synchronize and lock in transactions in <5 seconds in a large broadcast network with todays technology. So if you're standing in line at the supermarket you need a different solution instead - like accepting transactions that were broadcast and verify successfully but have not been included into the proof of work yet.
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 26, 2011, 08:57:35 AM
 #12

But what do you think about it? Does it make sense? Would it be feasible?

I'm willing to evaluate the feasibility of proposed schemes if they are specified in sufficient detail. Your proposal is substantially different from bitcoin and the information you provide is not sufficient to provide a clear understanding of how it would work.

ByteCoin

I'm sorry, I tried to explain it clearly.
I'll try it again. Please ask whatever you want if a fail explaining myself again.

1) Differences from bitcoin:

-There's no conflicting transactions.
-The transactions have an expiry block number field. They can only be included in the block chain (they're only valid) if that block number has not been created yet.
-There's no mining. No currency is issued in block creation.
-Less time for block generation would be desirable.

2) Why would anyone include other people's transactions in their own block?
When someone wants his transaction to be included in the block chain, he preforms some proof of work to add it to his block mini-block and sends it to the network. He decides the difficulty target (there would be a minimum).
Another one can include this mini-block to his own and the work of the included block is added to the work of his mini-block.
The more work you put in your transaction, the more incentive other people have to include your transaction.
When a mini-block contains enough combined difficulty to become a proper block, well, it becomes a block and is added to the block chain.

3) The possibility of eliminating the time target (eliminate the difference between a mini-block and a proper block) by enabling chain merges.
When a chain branch becomes orphan in bitcoin, the following adverse effects take place:

-All the bitcoins generated in that branch are lost.
-All the fees charged in that branch are lost.
+All the transactions can be included later in the main block chain (this is not adverse).

When a chain branch becomes orphan in this ripple implementation, the following adverse take place:

-All transactions that have expired are lost.
-Some of the not expired transactions can be included later in the main chain, but they have to be included before they expire.

In this system we could have merges and avoid the lost of transactions, but there's a possible attack.
The payer want his transaction to be included in the block chain even if they've expired. It's not the payer who decides the expiration block number but the promisors (I don't think that more detail in this is necessary).
If merges are allowed, the payer can try to cheat the timestamping by creating an artificial branch that continues a block previous to the expiration block and then wait for that branch to be merged.
The first solution that comes to mind is to require a minimum length (in work) for the branches to be merged. But then the payer just need more time/computer power to cheat.
Merging must have more restrictions. A maximum difference (in work) between the main (the longest) chain and the branch to be merged is needed.
This maximum difference has to be proportional to the length of the chains since the fork. For example, the branch can be at most 10% shorter than the main chain to be merged.
What incentives nodes to merge chains?
The combined work of both branches will count as the length of the chain after the merge. So if one commits his transactions on top of a merge is likely that the transaction stays in the longest chain.

Maybe I missed something. Please, feel free to ask whatever you want.

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
jtimon (OP)
Legendary
*
Offline Offline

Activity: 1372
Merit: 1002


View Profile WWW
April 26, 2011, 09:07:40 AM
 #13

The other thing to think about is that there's really only two interesting speeds, <5 seconds and >5 seconds.

It's probably not possible to globally synchronize and lock in transactions in <5 seconds in a large broadcast network with todays technology. So if you're standing in line at the supermarket you need a different solution instead - like accepting transactions that were broadcast and verify successfully but have not been included into the proof of work yet.

That may be the case for bitcoin. But as we use the block chain to see if the transactions expire or not, if the time between blocks is 30 seconds instead of 10 minutes there's a huge improvement for us (even if we still need third parties for transactions in the supermarket). The intermediaries can define the expiration time with more detail and lock their credit for less time.
If you're interested in the details of the protocol, here's the current draft:

http://ripple-project.org/Protocol/Protocol?from=Protocol.Index

I want the block chain to replace the arbiters (or more recently called the registries in the ripple forum).

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!