Topic: [SCALING] Minisketch (Read 513 times)

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?

just check this post and my follow-ups here: https://bitcointalksearch.org/topic/m.48855816 you need to be more humble, imo.

P.S.
OP! It is unacceptable for a self-moderated topic you kept Greg's shit intact and removed my answer. Now, I regret merits I sent to you  

And it is the drama, usual Greg Maxwell ... I'm just asking a simple question: Is this problem, fast boot, considered important at all? Is there any hope for noobs like me to have their work committed to the code? Or all we have to do is forking off from legendary engineers like you?  

What do I get? A personal attack about me not being up to date in the field, a maniac and a narcissist, ... why because I'v somehow insulted Greg the great, by saying that I'm sick of working on problems that are not considered a problem at all by the team who is in charge of the code.

What I don't get? An answer to my question: Is this problem, bootstrap nightmare, considered a priority by the Core team at all? Believe me Maxwell, it is part of my research  

P.S.
Speaking of engineering ... You guys don't even care about software engineering, bitcoin code is far from being engineered, the bootstrap problem tells everything about it. I do agree that decentralized consensus based p2p systems is new field, new problem domain and best practices are not established yet, but I don't expect being taught about how 'engineering goes in the real world' by people who are maintaining a system that takes like an age to boot.

Bitcoin nodes already tell their peers the minimum feerate they'll accept, so their peers don't won't offer anything that they won't accept. Doesn't even need to go into the IDs.   See BIP-133.  It would be possible to put the feerate in the IDs for even more fine grained/realtime filtering but I believe that would be a net waste of bandwidth due to the extra space for that information and the relatively few extra transactions that get sent in between feefilter updates.


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).

For computation we've been designing assuming needing to accommodate a rpi3 ... and part of the purpose of building minisketch as a fairly well optimized library was understanding exactly what the performance tradeoffs would be. 

One nice thing is that all the CPU heavy lifting is done by the party that requests reconciliation, so if you are CPU starved you can just reconcile less frequently. Doing so will also further reduce your bandwidth but just has a downside of propagating transactions somewhat slower.
 

from the introduction section of url above:
"If the elements are large, it may be preferable to compute the sketches over hashes of the set elements."

and I think this method will fit in cryptos. if so, then this would be a good idea to relay the FEE parameter with these hash values too. then you could add a HAND-SHAKING stage at the beginning of these back and forts:


and I have a question here. if I understand it right, the BCH here needs a rearrangement of data in mempool - so in continue, we should know does this rearrangement need more space too? and the encoding/decoding processes engage the processor of a node. may it put an end on nodes that have miniature hardware like raspberry family?

And I'm really sick of your insulting lectures when you can't even bother to keep up on the state of the art in what's already been proposed. Please spare me the excuses about how its other people's fault that you're not doing other things. You seem to have plenty of time to throw mud...

There are already existing designs for an assumevalid 'pruned sync'...  but not enough hours in a day to implement everything immediately, and there are many components that have needed their own research (e.g. rolling hashes like the ecmh, erasure codes to avoid having snapshots multiplying storage requirements, etc.).

If you want to help--great! But no one needs the drama.  It's hard enough balancing all the trade-offs, considerations, and boring engineering without having to worry about someone being bent that other people aren't going out of their way to make them feel important. It's hard even to just understanding all the considerations that other engineers express: So on one has time for people who come in like a bull in a china shop and don't put in that effort towards other people's work. It doesn't matter who you are, no one can guarantee that any engineering effort will work out or that its results will be used even if it does.  The history of Bitcoin (as is the case in all other engineering fields) is littered with ideas that never (yet) made it to widespread use-- vastly more of them from the very people you think aren't listening to you than from you. That's just how engineering goes in the real world. Don't take it personally.

We are above 300k already, aren't we? So, why not to solve bootstrap problem once forever, regardless of anything else?

I understand how crucial is the need for full validation but there exist drawbacks more than just bootstrap becoming more and more time consuming. Most importantly, the code needs to be downward compatible in a radically exaggerated way which leads to software bloat, as you know.

Theoretically once a node is convinced about the state at a given height, it is done with the history (it is how pruning works after all). What if we could establish a solid algorithm that provides the same security level as current boot-from-genesis approach strategy?

I'm preparing a draft for this, but I'm really sick of doing work on problems that you guys in the team are not interested in. Is there any chance to have your attention for such a proposal? I understand there is always a lot of issues and proposals and TODOs, I just need to know how much attention a proposal for a secure alternative to boot-from-genesis deserves to get.

Initial sync is already an enormous problem, and even if you assume computers/bandwidth improve at 18% year over year (which is a big assumption...) any blocksize over ~300kbytes means that the initial sync time will continue to get worse.

It's unclear, we know that the numbers are somewhat distorted by spynodes which commonly claim to be old versions, but we don't know by how much. I know that on nodes where I've aggressively banned spynodes I see a much newer node mix than luke does.

Regardless, in the future nodes could eventually decide to stop relaying unconfirmed transactions to old nodes... it's pretty backwards compatible to do so. But thats getting way ahead of things...

To clarify for anyone else who might be reading this, BCH in this case has nothing to do with Bitcoin Cash but rather stands for Bose-Chaudhuri-Hocquenghem. I just find it a fun coincidence:
https://en.wikipedia.org/wiki/BCH_code

(it's linked in the readme, I wasn't aware of these codes myself)

It wouldn't be the first (or last) time that other cryptocurrencies have used code developed by the Bitcoin devs if so



Schnorr sigs improve verification performance, or at least the Bitcoin developed standard for the koblitz elliptic curve does



Hmmm, I interpreted Minisketch relay as a means to improve the Bitcoin network's ability to handle the additional capacity that's gradually becoming available as segwit increases in usage (and likewise with schnorr). Arguably it's a marginal improvement, but it still makes the on-chain scaling that's unrealised (but possible) more viable. Still, maybe the scaling label for this thread is a little hyberbolic

Not necessarily.

The same reason that it has been for the past several years: a larger UTXO set makes verifying blocks slower and increases node requirements thus making it more expensive for people to run nodes. More transactions in general (which correlates to a larger UTXO set) makes it harder to run a node which means that there will be less nodes and thus less decentralization.

I am not against Bitcoin adoption in general. I am for more people using Bitcoin. However I do not believe that we can support having more people at this time with current technology. Minisketch does not change this fact because it is used for network relay, which is completely unrelated to blocks, consensus, and the UTXO set. Not every new technology in Bitcoin is for making more transaction throughput. In this case, this new technology is to reduce the total bandwidth cost for a node, which is good, but unrelated to transaction throughput.

Let's not turn this thread into another block size argument. That's completely off topic.

That's pretty neat, I'm looking forward to see whether this will bring any practical implications for Bitcoin.



That depends. Some transactions may lead to a quadratic increase of verification times [1]. This problem is fixed with SegWit transactions, however legacy transactions are still a thing so that might be important to keep in mind.

[1] https://bitcoincore.org/en/2016/01/26/segwit-benefits/#linear-scaling-of-sighash-operations

Nothing to do with me, I'm just delivering the news

Improving block reconciliation and helping with block size is not the only impact. Actually I'm more interested in the algorithm because of its efficiency in comparing two sets for not spending a same output (by same or different txns).

Besides my PoCW proposal I've been working on sharding for quite a while, interestingly in both cases, I've encountered to this problem: in a given state (block height) how do we choose between multiple blocks, processed/proposed in parallel?

Let's define two blocks to be antagonist if and only if they include transactions (identical or not) that spend a same output. If two blocks are not antagonist, a hypothetical protocol might allow both to be included in the blockchain.

Now suppose we need miners to relay a data structure like what carlton has implemented to represent spent UTXOs (and not the txns) using a simple XOR operation we would be able to verify antagonism of two competing blocks before downloading them. It is a huge step forward.

Although I'm more a block-time-decrease fan rather than a block-size-increase one and I'm concerned about quite more sophisticated approaches to on-chain scaling but I think your argument is generally against bitcoin adoption and it is so disappointing.

Increased UTXO size means increased user base, doesn't it? And you think it is infeasible to have a UTXO an order of magnitude bigger? Why?

As of your bootstrapping argument, we have UTXO commitment proposals and a row of novice solutions combined with pruning ready to be implemented and used.

Bootstrapping is not a big deal imo and bitcoin is not doomed to low adoption because of its UTXO size.

Right, but average block size is still not consistently above 1 MiB. Those days are coming though (if Lightning became very popular, there could be regular periods with a consistent 24 hour average blocksize of >= 3 MiB blocks)



Major features are usually added in 0.x.0 releases; bugfixes, softforks and minor feature backports comprise any 0.x.x releases. Minisketch relaying seems like it would be considered a major feature, so older versions wouldn't get it.

I agree to a certain extent, but I'm still conscious that we've not yet seen the full impact of the segwit block capacity increase. Minisketch relay for both transactions and blocks would mitigate that, but it will be a while before we reach average daily sizes of (say) 2-3 MB, and the overall blockchain will grow even more between now and then. I agree with achow101 that there's still initial block download to consider (using a rolling UTXO set could be used to make a contrary case, but that's for another discussion)



Fixed that, apologies


Right, but there are very few upgrades can be made to Bitcoin where old versions can benefit from new features.

Increasing the block size still increases the UTXO set size and the time to sync and validate all blocks. Minisketch does not help with initial sync or with validation, it only reduces the amount of bandwidth you consume for normal transaction relay (i.e. relaying unconfirmed transactions after you have already synced).

Kudos 
Excellent work here, I was disparately looking for such a solution, specially interested in efficient symmetric difference evaluation feature of the algorithm. I'm so excited right now, let me finish reading details, thank you very much dude, O....M....G 

libminisketch was published last week: https://github.com/sipa/minisketch/blob/master/README.md

This is a software library that can be used to allow set differences to be encoded and relayed using less data than before. Bitcoin currently relays blocks using a different technique known as "compact blocks" (BIP152), but Minisketch should improve on the performance of compact blocks by several factors (also, compact blocks fail if the amount of transcations a node needs to reconstruct a given block is lower than a certain threshold).

This type of technique has been suggested as a scaling technique in the past, but the suggested method (IBLT, inverted bloom lookup tables) has probabilistic decoding performance, and hence has an associated failure rate. Minisketch always decodes successfully.

Not only could Minisketch reduce the amount of data needed to relay blocks between nodes, but could also be used to reduce the amount of data needed to relay transactions. Current relay can use 200-300 MB bandwidth per day, using Minisketch as part of the tx relay method will reduce this considerably (alot of redundant inventory request/reply messages are sent with the present relaying logic, i.e. nodes use significant bandwidth simply asking each other "which transactions have you got")


It's obviously early in the Minisketch story, but this is a p2p layer change that doesn't require a soft fork to implement. Along with other potential improvements to help the Bitcoin network's resource load (Schnorr, taproot, MAST, rolling UTXO set), we could be using a significantly leaner network this time next year.