Bitcoin Forum
November 13, 2024, 06:30:35 AM *
News: Check out the artwork 1Dq created to commemorate this forum's 15th anniversary
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: [Scaling] Minisketch - Unmoderated  (Read 275 times)
mechanikalk (OP)
Member
**
Offline Offline

Activity: 99
Merit: 91


View Profile WWW
January 03, 2019, 08:00:20 PM
 #1

This post was deleted from the self moderated Minisketch thread, so I decided to start a new one so people can discuss.

We don't plan on changing how the mempool works-- rather, for each peer a sketch would be kept with all the transactions that your node would like to send / expect to receive with that peer. It takes a bit of memory but it's pretty negligible compared to other data kept per peer (such as the filters used to avoid redundant tx relay today).

Although, this is a very intriguing idea at first I have a couple of questions regarding incentives and resources of nodes as well as propagation latency.

In terms of peer sketches.  What determines how often a node will update a peer sketch? Are they doing it every time they get a transaction, or right after a peer requests it.  If they are doing it every time they get a transaction, the sketch takes more resources.  If they do it every time a peer requests an update, sketch creation causes a delay, followed by the delay in determining the difference and than subsequently requesting the deltas.  It was expressed that this could be done without a hard fork because it doesn't change the incentives.  I think that this does change the incentives of nodes in an indeterministic way which could lead to various forms of selfish and resource optimization behavior especially against small nodes.

The second question I have is how does this net effect latency.  The theoretical propagation time of data across the network is actually the upper bound on network throughput. Introducing latency to aggregate, share, compute, request and share transactions likely adds a lot of latency to the network which can actually decrease throughput.  Any thoughts on where the use of bandwidth competing with latency is optimal?
Carlton Banks
Legendary
*
Offline Offline

Activity: 3430
Merit: 3080



View Profile
January 03, 2019, 08:42:57 PM
Merited by gmaxwell (1)
 #2

Sorry about that, I have basic rules in my threads

1. No trolling. Even if you're not definitively a troll

2. No trolls. Even if you're not trolling


You fell afoul of rule 2 here: https://bitcointalk.org/index.php?topic=4638321.msg49019088#msg49019088

Is lightning network making bitcoin centralised?

Yes.

It is also reintroducing middleman which will perpetually charge transactions fees due to network driven oligopolies.  It is a lot like Visa and Master card.

If someone wants to talk to you in your thread, that's their business

Vires in numeris
aliashraf
Legendary
*
Offline Offline

Activity: 1456
Merit: 1175

Always remember the cause!


View Profile WWW
January 03, 2019, 10:16:59 PM
Last edit: January 03, 2019, 10:33:22 PM by aliashraf
 #3

1. No trolling. Even if you're not definitively a troll

2. No trolls. Even if you're not trolling

Oh, give me  a break.
You are accusing the guy to be a troll, because he has once stated something you don't like about the holly LN?
Thanks god you are not a mod here.
And yes, I'll never ever come to "your" threads. Self moderated threads suck, but yours seem to be a trap for retaliation or something.
 
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
January 04, 2019, 07:24:06 PM
Last edit: January 04, 2019, 07:37:50 PM by gmaxwell
Merited by DarkStar_ (4), ABCbits (2), bones261 (1)
 #4

Transactions announcements to other peers are already delayed for bandwidth reduction (because announcing may at once takes asymptotically about one forth the bandwidth: since ip+tcp+bitcoin have overheads similar to the size of one announcement and the delays usually prevents the same transaction from being announced both ways across a single link) and privacy reasons.  The delays are currently a poisson process with an expected delay of 5 seconds between a node transmitting to all inbound connecting peers. Outbound connections each see 2 second expected delay.

As a result reconciliation based relay doesn't increase delays (in fact, with our current WIP parametrization, it decreases average delays somewhat).  

I share Carlton Banks' concern.  Your tone in past messages as well as the this one is rude and somewhat irritating particularly when coupled with (otherwise innocent) ignorance of Bitcoin 101 topics like how transaction relay works.  The fact that your message went a day here without getting a reply even though you were unaware of the existing batching which any of thousands of people could have pointed out to you demonstrates one of the negative consequences of taking such a tone instead of asking a polite and professional question... If you actually care about learning you should refrain from that sort of behaviour.  If you're not actually interested in that, you should discontinue posting in this sub-forum because that isn't welcome here. People with actually useful answers aren't going to choose to spend their time hanging out somewhere to get insulted by newbies or people who just haven't done their homework.

Quote
done without a hard fork because it doesn't change the incentives
A number of hostile posters on bitcointalk and reddit seem to be using the word hardfork in a more or less random way.  A hardfork is not a general term for an idea the speaker thinks is a bad idea Smiley. A hardfork is a change in consensus rules which is irreconcilably incompatible with prior consensus rules e.g. accepting a block containing spends that previous software would reject as invalid.  Transaction relay is entirely outside of consensus and as a result no possible change to it would be a hardfork (or a softfork, for that matter).  The existing Bitcoin protocol and software even has a mode which disables transaction relay entirely (blocksonly) and it is fully consensus compatible with other nodes (and saves a metric boatload of bandwidth).

Quote
selfish and resource optimization behavior especially against small nodes
All of the computational work in reconciliation is performed by the party that initiates the reconciliation.  So a third party cannot cause you to expend more resources than you want to expend on it.  We've been doing protocol design assuming the need to support rpi3 nodes without an undue burden; which was part of the reason minisketch was required since prior bandwidth efficient reconciliation code was far too slow for limited hardware like that.  rpi3 is more or less the bottom end for running a full node-- already that target takes 20+ days to synchronize the chain.  Slower could still be used, but it would presumably reconcile less often.

Quote
The theoretical propagation time of data across the network is actually the upper bound on network throughput.
Not at all, Bitcoin is already a batch system-- blocks show up at random times and commit to a chunk of transactions, whatever is missed and still valid goes into a subsistent block. Both because blocks are relatively infrequent and because the mining process itself has seconds of latency (e.g. from batching new block templates to mining devices to avoid creating extreme loads on block template servers) the existing delays have little effect on the transaction handling delays.

More fundamentally, the connection you believe exists between tx propagation time and network throughput just doesn't exist:  It could take an hour to propagate transactions and the resulting network throughput would be unchanged because the network doesn't stop and wait while the transactions are being propagated. If it did, it would add an hour until you saw a confirmation, but the number of confirmed transactions per hour would not be changed.

Imagine you had an infinite number of dump trucks to use in hauling gravel from one city to another, 24 hours a day 365 days a year. Each truck carries 1 ton of payload and every 5 minutes a full truck leaves.  During week you will carry 2016 tons of gravel between the cities. It does not matter if the cities are 1 hour apart or 5 hours apart:  Changing latency does not change throughput for non-serialized operations.

In Bitcoin the latency is relevant-- not because of throughput reasons, but because of things like people caring about their transactions being confirmed sooner rather than later.  So long as the TX propagation delays are very small compared to the block finding interval they don't matter much in terms of the user's experience, so it's fine to trade off some small latency for other considerations like reduced bandwidth or increased privacy-- which is something Bitcoin currently does and has always done since the very first version (though the details of the trade-off have changed over time).

There are other minor considerations that make tx propagation delays matter some, but they're all of a sort where they don't matter much so long as they're significantly less than other delays (like block template updating delays).
mechanikalk (OP)
Member
**
Offline Offline

Activity: 99
Merit: 91


View Profile WWW
January 05, 2019, 07:14:03 PM
 #5

Sorry about that, I have basic rules in my threads

1. No trolling. Even if you're not definitively a troll

2. No trolls. Even if you're not trolling


You fell afoul of rule 2 here: https://bitcointalk.org/index.php?topic=4638321.msg49019088#msg49019088

Is lightning network making bitcoin centralised?

Yes.

It is also reintroducing middleman which will perpetually charge transactions fees due to network driven oligopolies.  It is a lot like Visa and Master card.

If someone wants to talk to you in your thread, that's their business

I find that to be a thoughtful answer to the question.  You may disagree, but that is the point of discussion. In all parts of civil society I think censorship is detrimental (even for trolls).  You classifying of me as a troll because of that comment, with which you disagree, is a perfect example of the slippery slope of censorship.

I don't want to discuss this further in this thread, but felt compelled to respond.
mechanikalk (OP)
Member
**
Offline Offline

Activity: 99
Merit: 91


View Profile WWW
January 05, 2019, 07:47:12 PM
 #6

Firstly, thank you gmaxwell for taking the time to answer my question.  I very much appreciate it.

Transactions announcements to other peers are already delayed for bandwidth reduction (because announcing may at once takes asymptotically about one forth the bandwidth: since ip+tcp+bitcoin have overheads similar to the size of one announcement and the delays usually prevents the same transaction from being announced both ways across a single link) and privacy reasons.  The delays are currently a poisson process with an expected delay of 5 seconds between a node transmitting to all inbound connecting peers. Outbound connections each see 2 second expected delay.

Is the proposal with minisketch to keep the same delay that is currently used?  Given the current rate of transactions on the network, what would be the anticipated bandwidth savings with minisketch (assuming delay remains unchanged)?


Quote
selfish and resource optimization behavior especially against small nodes
All of the computational work in reconciliation is performed by the party that initiates the reconciliation.  So a third party cannot cause you to expend more resources than you want to expend on it.  We've been doing protocol design assuming the need to support rpi3 nodes without an undue burden; which was part of the reason minisketch was required since prior bandwidth efficient reconciliation code was far too slow for limited hardware like that.  rpi3 is more or less the bottom end for running a full node-- already that target takes 20+ days to synchronize the chain.  Slower could still be used, but it would presumably reconcile less often.

With minisketch wouldn't a node need to compute and transmit different sketches for each one of its peers?

Quote
The theoretical propagation time of data across the network is actually the upper bound on network throughput.
Not at all, Bitcoin is already a batch system-- blocks show up at random times and commit to a chunk of transactions, whatever is missed and still valid goes into a subsistent block. Both because blocks are relatively infrequent and because the mining process itself has seconds of latency (e.g. from batching new block templates to mining devices to avoid creating extreme loads on block template servers) the existing delays have little effect on the transaction handling delays.

More fundamentally, the connection you believe exists between tx propagation time and network throughput just doesn't exist:  It could take an hour to propagate transactions and the resulting network throughput would be unchanged because the network doesn't stop and wait while the transactions are being propagated. If it did, it would add an hour until you saw a confirmation, but the number of confirmed transactions per hour would not be changed.

Imagine you had an infinite number of dump trucks to use in hauling gravel from one city to another, 24 hours a day 365 days a year. Each truck carries 1 ton of payload and every 5 minutes a full truck leaves.  During week you will carry 2016 tons of gravel between the cities. It does not matter if the cities are 1 hour apart or 5 hours apart:  Changing latency does not change throughput for non-serialized operations.

In Bitcoin the latency is relevant-- not because of throughput reasons, but because of things like people caring about their transactions being confirmed sooner rather than later.  So long as the TX propagation delays are very small compared to the block finding interval they don't matter much in terms of the user's experience, so it's fine to trade off some small latency for other considerations like reduced bandwidth or increased privacy-- which is something Bitcoin currently does and has always done since the very first version (though the details of the trade-off have changed over time).

There are other minor considerations that make tx propagation delays matter some, but they're all of a sort where they don't matter much so long as they're significantly less than other delays (like block template updating delays).

I don't think that this example fully encompasses the problem.  

The transaction propagation time, although inconvenient, is not the limitation on bitcoin specifically.  The problem limiting the throughput of Bitcoin is the average bandwidth available to the Bitcoin nodes and how much bandwidth is needed to handle a given number of TPS. The reason that latency becomes important in a multi-hop system is that it acts to reduce the effective bandwidth of the network.  

Adding additional propagation delays needs to be compensated by decrease in bandwidth. Minisketch clearly accomplishes this. However, there is a point which is optimal in that the total throughput of the system will be maximized with delay X given the amount of bandwidth reduction Y that the delay enables.

This is a well study trade-off that effects the throughput of TOR given the latency of nodes as well as the prescribed number of hops. I think that some of this work may be helpful in understanding how to optimize Minisketch.

In the case of Bitcoin, you may actually realize that substantially longer delays will be the point at which total network throughput is maximized or rather how the bandwidth is minimized given the current blocksize limit.  

This again gets a little bit tricky though because delaying relaying by say a minute could substantively increase TPS or decrease bandwidth but would cause some form of selfish mining.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
January 06, 2019, 03:59:26 AM
 #7

Is the proposal with minisketch to keep the same delay that is currently used?  Given the current rate of transactions on the network, what would be the anticipated bandwidth savings with minisketch (assuming delay remains unchanged)?
There is no concrete proposal yet, but all our design work has targeted keeping the same or lowering delay.

Quote
With minisketch wouldn't a node need to compute and transmit different sketches for each one of its peers?

Sketches are additive, so when a node decides to relay a transaction it computes the sketch of that transaction's ID.

Then it adds that sketch the the accumulated sketch for each peer.  Adding the sketch is just an XOR so it essentially takes no time.  This work is done per transaction too, so it doesn't matter how often the peer reconciles.  Reconciling justs causes the responder to send out the accumulated sketch and memset it with zeros.

Quote
I don't think that this example fully encompasses the problem.  
The transaction propagation time, although inconvenient, is not the limitation on bitcoin specifically.  The problem limiting the throughput of Bitcoin is the average bandwidth available to the Bitcoin nodes and how much bandwidth is needed to handle a given number of TPS. The reason that latency becomes important in a multi-hop system is that it acts to reduce the effective bandwidth of the network.  

You haven't explained why you believe that.  It simply isn't true-- see my dumptruck example.  Each transaction is relayed without waiting on the prior ones to arrive anywhere.   Can you try presenting your understanding using the infinite dump-truck analogy so that we can get on the same page?
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!