0

I've asked similar question here: Is gossip protocol in Bitcoin perfect? But I didn't get an answer to my question really. I am ideating a consensus algorithm and I need definitive answer.

Can we take for granted that if in time period t there were 10,000 connected peers (no new peers connecting, no peers disconnecting), all with good internet connection and hardware, then if every of those 10,000 peers originated one transaction (or any kind of message) to his peers, can we take for absolutely granted that eventually every single one of those 10,000 connected peers have in his mempool all 10,000 transactions, including his own and those of 9,999 other peers and absolutely no transaction will be missing in mempool of any of those nodes (they will all have same set of data)? If yes, and would could be estimated time (seconds, minutes, hours)?

And now: things like double-spends, transaction correctness, peers connecting and disconnecting from network, etc. that happens in real cryptocurrency systems are not relevant here - this is a theoretical question and a theoretical situation.

Improve this question
2
  • 1
    If you drop all the practical reasons why propagation may not be perfect, then yes of course the result will be perfect. I don't understand what the answer is supposed to mean in that case. For example, the whole point of a cryptocurrency is resolving double spends - if you assume there aren't any, why do you care?
    – Pieter Wuille
    Jul 6, 2018 at 6:43
  • 1
    Related: impossibility result distributed systems with only 1 malicious process: groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
    – sanket1729
    Oct 23, 2018 at 20:25

1 Answer 1

Reset to default
1

Can we take for granted that if in time period t there were 10,000 connected peers (no new peers connecting, no peers disconnecting), all with good internet connection and hardware, then if every of those 10,000 peers originated one transaction (or any kind of message) to his peers, can we take for absolutely granted that eventually every single one of those 10,000 connected peers have in his mempool all 10,000 transactions, including his own and those of 9,999 other peers and absolutely no transaction will be missing in mempool of any of those nodes (they will all have same set of data)?

If you also include that no one is acting maliciously, then yes, under these perfect conditions with no malicious actors, you take for granted that a transaction will reach all nodes within some unknown time t. However, if there are malicious actors, then no.

If yes, and would could be estimated time (seconds, minutes, hours)?

This is impossible to know. It depends on the hardware, what the transactions consist of, the internet connection, etc. At best, it would probably take a few hundred milliseconds. At worst, likely a few minutes. Without more specific parameters, it is impossible to know.

Improve this answer
5
  • Thank you. You said that in order for that perfect conditions to work, we need to include that no one is acting maliciously. So, given that a part of network would work maliciously, say 10%-30% of entire network, what effect on scenario presented above would it have? Would the effect (all messages reaching all nodes) be reached even with some malicious nodes in network, just with more time, or would malicious nodes completely prevent this? Or maybe it's just that malicious nodes themselves can pretend that they didn't received them that your speaking about?
    – user84415
    Jul 6, 2018 at 15:58
  • I'm asking because as far as I understand the only thing that a malicious node can do in this given scenario is NOT to relay message. Maybe I need also to clarify that in this scenario all messages are asymmetrically signed so no malicious node can change the message, if that's what you think about. Thank you.
    – user84415
    Jul 6, 2018 at 16:03
  • 1
    @user84415 If the honest node is only connect to malicious nodes, a message could be delayed indefinitely. Also keep in mind that not all nodes keep mempools, etc. It is generally more realistic and useful to assume adversarial conditions, than ideal.
    – chytrik
    Jul 6, 2018 at 20:15
  • A malicious node can broadcast conflicting messages. If they themselves originate the message, then they can broadcast one message to half of their peers, and another message to the other half. This means that at least some nodes will receive one message before the other and thus result in different mempools.
    – Ava Chow ♦
    Jul 6, 2018 at 21:03
  • Thank you for answer. That is exactly what I was thinking about. But, even if malicious node will send one message to a half of his peers and different to other half, provided there is at least one honest node in each half, two messages will reach the network anyway, just some nodes will take one as the first (which they received first) and others will take the other one as the first. That is (messages deduplication and ordering) the double-spend problem that blockchain solves. For me, those answers are enough. Thanks.
    – user84415
    Jul 7, 2018 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.