Topic: BlockReduce: Scaling Blockchain to human commerce - page 2. (Read 1288 times)

is there any update on this? Is this still in developement?

The ideology?


What about your understanding about the proposal, you believe it's viable?

I'm trying to learn.


It's "easy to imagine"? I'm confused.

You gave the OP merits for the topic. What's your opinion on this?

https://github.com/mechanikalk/bips/blob/master/bip-%3F%3F%3F%3F.mediawiki


I already said I'm not a technical person, I'm actually the stupid one, but would the technical people/coders take this proposal seriously?

OP, I read the white paper. I'm not a technical person, but are you actually serious about your proposal? For Bitcoin as a hard fork?

Hi there! I was looking through some old research papers about merge-mining and came upon this thread. I'm very interested in your proposal as it seems like a great way to shard state without losing security via merge mining! I have a question for you though: If miners have to verify all the state that passes up to Prime, they have to run a full node so that they have the state of all the blockchains to properly verify everything. They are incentivized to do this so that they don't mine invalid blocks, but in doing so they might put a strain on the network because their zone and region nodes are not necessarily in the same geographic region as the rest of the zone and region nodes. (Of course, the zone that the miner is located in will be optimal, but I am talking about the rest of the zones and regions necessary for running a full state node).
For example, for n zones, n/2 regions, and m miners running a full state node, we have m - 1 latent nodes in each zone (or n*(m-1) latent zone nodes total) and m - 1 latent nodes in each region (or (n/2)*(m-1) latent region nodes total). Do you consider this an issue for network latency? Is there perhaps some way or incentive for a miner to run a full node and also run each sub-node (zone and region) in the proper geographic location? This might be physically difficult without the use of some cloud provider like AWS.

Looking forward to hearing more! Thanks.

It is not comparing propagation to block reconciliation.  I understand how this could be confused. The  blocks found at the lowest level are the mechanism for sharing groups of transactions.  That is why I am comparing Bitcoins transaction propagation to BlockReduce Zone block propagation.  Propogating transactions in groups in a whisper protocol is much more bandwidth efficient.

BlockReduce will be as inefficient as Bitcoin at the lowest level zone groups.  The efficiency is gained by the aggregation of transactions into groups via "Zone blocks" and whispering them further in the network as blocks of transactions.


The structure for grouping and propagating transactions would not be dictated, but rather would be incentivized.  Miners would be incentivized to find lower level blocks and the impact of network latency on effectively using their hash power would incentivize them to find low latency zones to mine in.  This would cause each zone group to have lower latency then the total network and be able to process a higher TPS.  For example, if there were 4 zones available to mine in, miners would roughly divide the world into 4 geographic zones.  They wouldn't be well defined and would overlap from a geography standpoint, but having 4 networks at the zone level would be much more performant then having a single network.  The single network would still exist at the PRIME level.  However, by the time the transactions make it to PRIME they would be whispered in region blocks of 1000 transactions.


The incentive mechanism would be giving some reward for the collateral work via merge mining of zone, and region blocks with PRIME.


I have reviewed this proposal by Greg Maxwell.  It is interesting from an anonymization standpoint.  However, I did not see a mechanism by which the transactions would be delayed and aggregated but rather a routing schema that obfuscates the origin of a transaction.

Looking closer to your calculations it is about comparing bitcoin transaction propagation with your schema's block reconciliation. These are two basically different things (and yet you are exaggerating about the situation with bitcoin). As I've argued before, both bitcoin p2p and your schema need the same amount of effort and resources to be consumed for raw transaction propagation because they are full nodes and you just can't dictate a predefined topology like a central authority or something.


Well, I'm ok with collateral work and most of the ideas above, but not with dedicated nodes it would be hard to implement an incentive mechanism. Right now, Greg Maxwell and others are working on a privacy focused improvement to transaction relay protocol in bitcoin, Dandelion.  The good thing about this BIP is their strategy for delaying transaction relay procedure a while (to make it very hard if not impossible for surveillance services to track sender's IP) and it looks to be committed to the release code in near future! It will be a great opportunity  to do more processing (classification, aggregation, ... ) while the transaction is queued waiting for relay.

Could you please be more specific in what you find wrong with the math in the example I gave above?  The example is giving a simplified version of how a transaction is "whispered" across the network currently and with BlockReduce.  In terms of mempool, I don't really think this effects bandwidth because it essentially adds capacitance to the system which can be ignored at steady-state.


I would like to work with you to initiate a BIP like this.  

I would propose that if we aggregate transactions we will need a way for the nodes to determine when they should share groups of transactions.  Ideally the mechanism we come up with for determining when the groups share transaction should be decentralized so no single node can withhold transactions for an inordinate amount of time.  There should also be a way for the nodes that receive the grouping of transactions to be able to verify the criteria was met.  

We could use something like a one-way mathematic function operating on an unpredictable data set that would periodically stochastically meet some arbitrary criteria.  Then when the criteria is met the aggregating node could transmit the data to all of the other nodes.  The other nodes would then be able to easily verify the criteria was met.

We could improve upon this further if we created some redundancy for the aggregating node.  This could be accomplished by having a small group of nodes with high connectivity that work together to aggregate a set of transactions amongst themselves before sharing to the larger network.

Do you think something like this could work?

Sorry, but it is not correct. For transactions to be included in a block they have to be "whispered" in the network and stored in the node's mempool beforehand.  Your schema couldn't change anything about this and once a block is generated, nodes have to validate it and if for some reason they've not been informed of the transaction already they have to fetch it anyway. Without sharding the state, it would be very hard to improve bandwidth requirement for the network.

That been said, it is worth mentioning that the main challenge for scaling bitcoin is not the total bandwidth requirement for whispering transactions. Transactions occur with a random distribution in time and are naturally tolerant to be queued and delayed for few seconds, in a hypothetical 10,000 tps situation, it takes a moderate internet connection for a node to semi-synchronize its mempool with other peers. We could initiate a BIP for such a situation to improve transaction relay protocol in bitcoin networking layer by aggregating batches of fresh transactions and synchronizing them according to some convention like ordered set of 100 transaction ids falling into a specific criteria, ...

The most critical problem with networking is the latencies involved in whispering new blocks and when nodes have no clue about some of included transactions, it is the basis for proximity premium flaw in bitcoin and its centralization threat because of its direct consequence: pooling pressure.

Since the miners are validating all transactions in PRIME and including them in the PRIME block, 100% of the hash power voted for transactions that originated in either A or B.  

Think about the child chains as not consensus, rather think about them as a mechanism for creating sets of transactions which can be efficiently propagated.  This is what I call consistency.  A consistent set of transactions on which the network validates and performs work on to include in a block. Once everyone, all miners have the transaction set, they check them and build a PRIME block.  

All transactions are included in PRIME in some form of a nested merkle tree.  All transactions were validated by all miners, and voted on by all miners when included in PRIME.  Therefore there is no sharding of work.  Lets say for example A propogates a block with an invalid transaction.  Miners in B will see this invalid transaction and refuse to include the hash in PRIME or to do any work on the transactions included in that block.  By the rules of consensus, transactions are not actually valid until they have been included in PRIME.

Again, don't even think of the children chains as blocks.  Only think about them as a mechanism for aggregating transactions.

The reason that this is different then merge mining is that the consensus rules are consistent and checked across the hierarchy of all chains.  This is not true in the case of something like Bitcoin and Namecoin.

no.

With your example. Prime chain + 2 side chains. The miners of each side chain mine just their sidechain and the PRIME chain. So yes the Prime chain has 100% hash, but the side chains have 50% each.

This means that any transactions about to be included in the PRIME chain have been _secured_ by 50% of the hash in the side chain. Then you use 100% of the hash to secure that - in the PRIME chain. The weakest link in this scenario/chain is the 50% POW side chain. This is the security of the transactions in the side chain - not 100%.

You have secured the 50% POW trxs in perpetuity with 100% of the POW..

The reason that the side chains are just as secure as the PRIME chain is that the PRIME chain is still checking all transactions explicitly (if not implicitly). Lets use a simple example with a PRIME chain and two children chains.  Each child chain has 50% of the hash power of PRIME.  Miners in both children (A and B) are validating transactions that they receive via the children blocks and including the transactions and block hashes in PRIME.  Therefore, by validating the transactions before including the hash in PRIME, 100% of the hash power is checking the transaction. Therefore, the transactions are just as secure if there where no children chains.

Lets for example imagine a fork in A (malicious or otherwise).  The miners in B will have to decide which hashes in A to include when working on PRIME.  If they include the "wrong/invalid" hash they will be wasting work.  Therefore,  everyone is still explicitly voting on every transaction with 100% of the hash power.


I think that the above is they way that every chain benefits from ALL the PoW while explicitly validating every transactions.

If we want to complicate the discussion, if I am a small miner in PRIME and working in A and I don't want to validate every transaction in B, I could choose to "trust" the block given to me.  Why is this trust but not trust?  If I take it on faith I may waste work by including that B block hash in PRIME if it is invalid.  However, I am not taking it on faith because B is presenting to me half the work that goes into a PRIME block.  Therefore, it would be very expensive for B to create a bad block that would ultimately be discovered and re-orged out of the chain.  So, if I don't have the other computing resources to justify this validation, I can "bet" that the "bet" made by B is good.  In the case it is not, a larger miner with greater economic incentive and resource will identify and not include the block hash in PRIME. 

This level of trust is significantly lower compared to the trust that anyone has that is using a mining pool, or a Bitcoin user that doesn't run a full node.

Lets work through an example.  Lets use the following assumption, that a node has 100 peers, a transaction hash is 32 bytes, and a transaction is 250 bytes.

A transaction is broadcast to our nodes' peer.  Our node sees this, request the transaction data, and begins to broadcast the transaction hash to our peers.  In the meantime 49 of our nodes peers also broadcast the same transaction hash to our node.  This means that our node sends 50*32 bytes plus maybe 2*250 bytes and receives 50*32 bytes and 250 bytes. Just making an assumption on the number of times we transmit the transaction data.  Ideally for all nodes this would be >1 so 2 is pretty conservative.

Summary: 1 transaction - Tx: 2100 bytes Rx: 1850 bytes

If transactions are shared with a peer as a zone block that has 100 transactions in a block.  I will share a 32 byte hash of the block the same number of times and transmit the full block of data say the same number of times. So our node sends 50*32 plus 2*250*100 and receives 50*32 plus 250*100.

Summary: 100 transactions - Tx: 51600 bytes Rx: 26600 bytes

If I normalize this I get 516 Tx bytes/transaction and 266 Rx bytes/transaction.  

This represents 75% greater efficiency in transmit bandwidth usage and 90% greater efficiency in receive bandwidth usage.  

This gets even better when aggregating into PRIME.  In the smallest 2x2 hierarchy region blocks would have roughly 1000 transactions per block.  This means that at the PRIME level I would be achieving >98% reduction in bandwidth by more efficiently communicating transactions by aggregating them into region blocks before transmitting to peers.

@Aliashraf makes good points about the need for miners to validate all the data. Sharding has yet to fix this issue.

But, if we can brainstorm a bit, this idea may bear fruit

I like the idea of a central POW chain that everyone mines. And that off this central chain (the PRIME) you can run multiple side chains (a simplification of your hierarchical structure). The real issue for me is that POW side chains are insecure.. unless you can get a lot of miners to mine it. Check pointing the side chain blocks in the PRIME POW chain simply timestamps the insecure blocks securely ;p

So can we make the side chains more secure..well yes you can. You can mine them POS. POS doesn't work 'publicly' but in a federated environment it works much better. In an environment where you don't mind that certain people run the chain. Still better, by time-stamping the blocks in the PRIME POW chain, you actually remove the nothing at stake problem. Because now there is something. So 'getting on the correct chain' (the base POS problem - as you can copy a chain's security for free) is easy.

And Boom. I've just described Bitcoin + Liquid..

But can we do the same with POW.. ? I think POW altcoins are almost exactly this. They take traffic off the PRIME chain, PRIME miners don't need to validate them, they just don't run as _official_ side chains. The trick here is that the POW algorithms need to be different. The mining community large. Then you could run these as POW side chains.

Is there a way that every_chain can benefit from ALL the shared POW equally across all the different chains whilst only validating shards of the data ? Not yet.. me thinks. But THAT would be cool.

The research document from Bitfury you've referenced is out of date as you've mentioned, bitcoin has improved a lot since 2016 and BIP 152 (compact blocks).

As of your concerns about "significant volume of traffic is used passing the transaction hashes around" and your argument about improving it by topological improvement that you are proposing, besides ambiguities and threats involving the way this topology is to be dictated, I doubt it to be much helpful:
1- For non-mining full nodes/wallets that are actively participating in block/transaction relay protocol, nothing is changed and they will do their usual business of connecting and relaying hashes and the raw data if it is requested by peers.
2- For mining nodes, although showing little interest in transactions that belong to shards they are not currently mining on might look somewhat reasonable, it is not! They need to be aware of other transactions and their fees to make right decisions about the next shard they are willing to mine.
3-For spv wallets the business is as usual too.
4- For all full nodes, having transactions in mempool is a privilege as it helps to catch up earlier with new-block-found events (as they wouldn't need to query and validate transactions immediately)

So, I don't find a disruptive improvement here.

Once again, I need to express my deep respect for your work as I found it very inspirative and useful for my own line of research and protocol design, but I think it needs a lot of serious improvements.

cheers

Thank you for your comments and feedback. On your first point, I am aware that only hashes of transactions are originally transmitted before all transaction data. There was lack of precision in how I described transaction propagation in the Github BIP and I have updated it accordingly. However, it remains true that a significant volume of traffic is used passing the transaction hashes around.  If you look at this research paper by Bitfury from a few years ago, although slightly out of date, gives a good idea of bandwidth efficiency.  One time transmission of data in a peer-to-peer network is highly efficient.  The inefficiencies measured have to do with creating a consistent set of transactions. Therefore, if I can incrementally create this set and represent it by a hash as I share it, I will decrease my bandwidth usage significantly because 1 hash will represent 100 or 1000 hashes.

In terms of sharding state.  For simplicity of the initial discussions, lets just assume all nodes keep all state and validate all transactions.  BlockReduce would reduce the amount of bandwidth needed to propagate a higher number of TPS efficiently. It would increase the need for RAM proportional to the UTXO set, permanent data storage proportional to chain size, and CPU power proportional to TPS.  However, none of these items are currently the limiting factor for scaling.  The present limiting factor for scaling is bandwidth and addressing this item would allow a significant increase in TPS.

In terms of the other limiting factors, these can be addressed with other mechanisms, but again, lets just discuss the proposal initially in terms of all nodes keeping and validating all state.

Also, for reference I presented this at McCombs Blockchain Conference.  The video gives a quick overview of BlockReduce if anyone is interested in getting a summary that is easier than reading the paper.

This is an example of what I criticized in my above post about your misinterpretation of state sharding:
In cryptocurrency and blockchain literature, specially in bitcoin literature, by state we are referring to UTXO (the set of unspent transaction outputs). Plus, keeping, in this context, implies nothing less than commitment and as I've discussed in my previous post, you need to fully validate what you are committing to.

For your so-called 'zone nodes' to 'keep the state' of its ancestors, they need to validate the events (transactions) and state transitions (blocks) and it won't happen without spending the same amount of resources required for being a full region/PRIME node. It makes your classification of nodes and the whole 'node types' concept pointless. There is only one node type in your proposed architecture as far as we are talking about full/self-contained nodes and not bitcoin spv like nodes that are not secure and have little if not zero role in keeping the network secure.

On the other hand as upper level nodes are allowed to include transactions in their blocks, zone nodes have to keep track of their states and as @spartacusrex has correctly mentioned above, in your proposal, all nodes are PRIME.

Actually, you have gone that far to admit it, well, somehow:
It is 8TB obviously and for 1000 TPS you need more than just storage: RAM, processing power and bandwidth among them and for the latter I have already refuted your efficiency argument.

Great question and I appreciate the feedback.  The large miners that are mining PRIME will have an economic incentive to validate the blocks that are being passed up.  If a block is detected because it is nefarious or there is a casual fork in a lower chain, a miner that is keeping state over multiple child chains will be incentivized to figure out the valid block and redirect hashpower toward the correct fork in both the lower chain as well as only including the correct head hash in the blocks they are mining in the parent chains. The lower fork could propagate as a fork in a region and eventually a fork in PRIME which means that all hashpower is used to determine consensus. The PRIME miners are effectively notarizing the results of the lower chain.  Ideally, based on the slower block times of PRIME relative to region, and region relative to zones, most forks should be fixed before propagating one or more levels up.  If they do, the hash trees will provide an efficient mechanism for re-orging large amounts of data in PRIME.

Because all miners eventually need to do work on the region and zone hashes in PRIME and including a hash of an invalid block from a region or zone chain will invalidate a PRIME block they are incentivized to validate transactions.  This effectively means that all hashpower is validating what is going into PRIME.  It will be optional for the nodes that are validating transactions outside of the zone in which the are mining how much state they want to maintain.  If a node with little hashpower is mining in a zone and doesn't want to validate adjacent transactions, they could trust the incoming transactions to some economic point because incremental work has been performed by mining an adjacent zone block.  If a miner has more hash power, they will be incentivized to do more checking of more transactions and keep a greater amount of state.  In the extreme example they could keep all state of all things and this could be thought of as a PRIME node.  They would still only be able to direct hashpower uniquely to each zone, however, by keeping state in more places they will create an insurance policy against their hashpower being wasted in that bad blocks are found quickly.  They will also have an economic incentive to redirect hash power to adjudicate a fork.

There are many node types that could be had in this architecture.  I could have a zone node, a region node, and a PRIME node.
 
The zone node would only keep state of a zone, a region, and PRIME.  
A region node would keep state of a region, all zones in that region and PRIME.  
A PRIME node would keep state of all things.  

Even within the different node types there are different levels of validation that could be performed.  For example, a zone node could choose to validate and keep state of all zone peers.  They could also decide to keep some form of limited or truncated state.  For example, if the UTXO pool in each zone is passed into PRIME via the merkle interlink field, a zone would be able to trust zone state at some point of depth in PRIME. This would enable them to only need to keep a limited block depth of the adjacent zone verifications with only needing to maintain several hundred or a thousand blocks of the adjacent zones without introducing a trust outside of PRIME consensus.  The same logic could be used at the region level.

Even if all nodes are PRIME nodes and keep full state, the amount of permanent storage needed would only be 8GbTb per year for 1000 TPS which currently can be purchased for a couple hundred dollars.