First off, I really appreciate you taking the time to reply. I am aware of the previous proposals to use lexigraphical mechanisms to create a preference in block choice.  However, the proposal here is different in that it has two key new realizations that although subtle are what make this powerful. I know the paper is very dense so I will try to give a more intuitive idea of what is going on.

1) Although each hash is an independent event, each block is a dependent event because it references the hash of the parent on which it is built.
2) The weighting of each block should be based on the expected number of hashes that are needed to reproduce the chain of blocks specified by the tip block.

These two ideas when added together allows us to propose a new weighting mechanism, entropy reduction, which eliminates issues with regards to withholding attacks.

When a block is produced the number of bits (~ leading binary zeros, or = log2(hash)) which exceed the block threshold value follow an exponential distribution b = e^x which has a mean expectation (lambda) of 1. This means a miner will expect on average to get 1 more bit than the threshold, but can achieve many bits within the exponential distribution. However, they could get
luck and get > 1 extra bit or they could get unlucky and get < 1 extra bit. The interesting thing here is that even if they get lucky and say get 3 extra bits there is still a 12.5% chance that if there is a competing block produces they will lose. The likely hood of loosing never goes to zero.

In addition, the weighting using entropy is adding bits, which is the same as multiplying in the linear field. Specifically, Bitcoin: Total Difficulty(n) = diff(n) + Total Difficulty(n-1) whereas PoEM is: Total Difficulty(n) = diff(n) * Total Difficulty(n-1) .This means that even if a miner was to get super "lucky" and find 20 extra bits (1 in 1 million blocks) the extra entropy would only count for 1/3rd of a normal block and they would still have a 0.0000001% chance of losing if they withheld the block. This means that no matter
how lucky a miner gets, they will always maximize revenue by broadcasting the block as quickly as possible.  This actually reduces the withholding attack that exists within the current difficulty weighting system.

If we took the same example, but use the current method of adding difficulties to determine block weight, the withholding period for finding 20 extra bits would be 1 million blocks.  So compare 1 million to 1. This example, elucidates that this is a very different proposal than the simple proposal of using apparent difficulty. Rather this proposal is doing two things. First, It is realizing apparent
difficulty is beneficial because it creates a rule which makes heavier chains and it actually adds randomness into winning a block to prevent withholding. Second, it is using the proper combinatorics, treating blocks as a series of dependent events, to weight them which in turn solves all of the issues with using apparent difficulty.

I hope that provides some intuition. In the paper we have shown that this is indeed the case both empirically as well as experimentally. If you look at the graph on page 12 we show that for any g (block production rate per network delay) that the confirmation delay is smaller using this method compared to the current Bitcoin weighting.



We also explored the concept of concentration or looking at how the outcome distribution effects the statistical convergence.  Bitcoin would be a binomial distribution and PoEM would be the biased gamma.

 

PS: Another way to think about this is that there is infinite variance in a single sample, so reintroducing randomness in the weighting, creates a better outcome because it means that a miner that has <50% of the hashrate is less likely to get sequentially lucky and produce a sequence of N blocks that is longer than the honest majority.

There is now formal security proof showing the safety and liveness of Proof-of-Entropy-Minima (PoEM).  https://eprint.iacr.org/2024/200

This relatively simple adjustment to the measurement of block weight has been empirically shown to: prevent selfish mining, create faster finalization time, increase throughput, and decrease block times while maintaining safety and liveness of the chain.  Modifications to the current heaviest chain rule are very straight forward.

The TL;DR is:

Presently the heaviest chain rule does not treat blocks as being dependent events even though they are dependent because of the hash link to the parent.

PoEM uses combinatorics to weigh the dependent block events appropriately. This generates a guaranteed unique weight for each block which is the average number of hashes, in expectation, that would be required to produce a chain of equal weight.

The guaranteed unique weight prevents the network from mining on competing forks because the likelyhood of having blocks of equal weight is (1/2^256) ~= 0

Additionally, the process naturally introduces randomization on each sample (ie block) which prevents profitable withholding attacks.

Finally, it shows that the threshold for a Sybil attack can be improved from 33% to 40%.

They do define the probability space 2^l which in the case of bitcoin is 2^256.

delta_S = 1/2^n where n is the number of leading zeros.  This makes sense from a Shannon entropy concept where entropy is a reduction in divergence and it also makes sense from a system entropy standpoint as well were miners exert work to lower the entropy and increase the system order.

If you look at the paper it is not just proposing you change chain work but that you simultaneously change the calculation of tip weight from very roughly being Td_new = Td_old + Td_threshold to Td_new = Td_old * Td_chainwork.  That would make both chain work and chain weight geometric which would actually improve finalization time by minimizing conflicts and maximizing recorded work.

I think the paper is correct.

Please tell me what you think the mistake in probability theory is.

Thanks in advanced.

This paper POEM: Proof-of-Entropy-Minima (https://arxiv.org/abs/2303.04305) was just published to arxiv.  It seems like a much better way to measure the heaviest chain tip as well as minimize time to resolve orphans.  It can instantaneously resolve 67% of orphans rather than having to wait for the next block.  Additionally, it seems to have better finalization time guarantees for a given hash.  Also, it has an equation that relates to finalization that would create objective measurable preference between different hash functions.

I think you should more holistically consider the meaning of centralization.  If I can't go to 7-11 and buy a coke with Bitcoin it is not fully decentralized.  If I need to have 3rd parties involved in a transaction it is not fully decentralized.  If I need to use centralized exchanges to trade with good liquidity it is not fully decentralized.  If it costs $200 to make a transaction it is pricing out network participants and small transactions which is not fully decentralized.

The more people that use Bitcoin, not just the number of people running nodes, is critical in answering the question of is it is decentralized.  Additionally, to have the largest network with the most particpants (most decentralized...?), I would argue that Bitcoin needs to scale on-chain.


If there are benefits such as a greater number of users, and increased utility at a lower cost, the marginal degree of centralization (fewer fully validating nodes) may very well be worth it.  However, I would contend that with larger user base even if the cost of running a fully validating node increases, the absolute number of full nodes would likely go up not down even if the relative number shrinks.

Yes, scaling the network is adding more network participants, this is accomplished through scaling.  The requirement that all market participants be fully validating nodes is a flaw not a virtue.  BlockReduce allows a larger number of incrementally more expensive ways of participating in the network while also scaling.  I think this is better than an all or nothing approach.  Additionally, when calculating market participants you should consider Bitcoin users in addition to nodes and miners as a metric of success.

A more thought out version of this is BlockReduce.

https://bitcointalk.org/index.php?topic=5060909.0

Overview paper:

https://arxiv.org/pdf/1811.00125.pdf

The actual effect on fault tolerance and decentralization has to be put into context that currently over 50% of Bitcoin's hashpower comes from only 4 pools.  As BlockReduce scales the node requirements to have a node which does partial state validation would be much less then a if Bitcoin scaled in its current state.  That would mean that although there may be fewer people validating full state, there will be more people, and fewer pools validating partial state. I would argue that having partially validating mining nodes is advantageous over having a deminimis number of pools.  Having smaller economic entities decide on the fate of the protocol rather than a few large pools would be positive for the ecosystem.


I think that people often times fall into tired narratives about majority of users, and fairness, et cetera without fully considering what any of it really means, or why it might be good or bad.  I would argue that if Bitcoin is meant to be censorship resistant and decentralized, that it must allow the greatest number of people to use it with the fewest intermediaries possible. Making low resource validation the primary focus of decentralization misses the point.  If even 20% of a population self custodianed Bitcoin which they regularly used for transactions it would be effectively impossible to censor or outlaw. When we discuss decentralization taking into account the power of the network which scales should also be a consideration, not just how easily it is validated.

That is a pretty insightful question.  However, the answer is pretty simple.  With all distributed networks from things like Napster to Bitcoin you always have a seed and a leech problem.  In the example of Napster it is driven by storage space more than bandwidth.  In the context of Bitcoin it is driven by bandwidth more than storage.  Therefore, if you are a Bitcoin node that has low bandwidth you are slowing the overall network down (leech), whereas if you have high bandwidth you are speeding it up (seed).  BlockReduce is not different from Bitcoin in this regard. However, BlockReduce rewards mining in the zone chains creating an economic incentive for participants who are mining to optimize for latency.

Coopex, great question!  Sorry, it has taken me a bit to get back to you. The miner is incentivized to hold zone state which they are not mining because it reduces the risk they will include a zone block in a region block which eventually gets rolled back in the zone.  If they were to wait or delay including zone blocks in the region blocks, they could also achieve greater certainty, however they would get lower rewards.  Running the alternate zone state allows them to have greater certainty about a zone block faster.  Doing so with a node which is appropriately placed in the network topology will decrease that nodes latency and further decrease risk.  Therefore, miners will be incentivized to keep state and do so in a network optimal way.  I would absolutely expect that a person running full state would do so using something like AWS to allow optimization of the geographic placement of nodes.

Tromp, I appreciate the time that you have taken to look at BlockReduce.  One thing that I would debate is the use of the word sharding.  Although, a miner can depend upon a zone blocks work as an attestation to the correctness of the included transactions, they are not required to.  Much like an SPV node doesn't have to keep the entire chainstate but rather just looks at a block header.  This is not sharding per say, but rather a mode of operation that a node can work within to use less resources.  I would anticipate that serious miners or pools will run and validate full state because they have an economic incentive to do so, while merchants will likely run partial state much like SPV. 

Another way to think about BlockReduce is as a form of multi-level erlay where "sketches" are sent when a zone, or region block is found rather than an arbitrary delay.  The obvious difference being that actual sub-blocks are found which are rewarded to incentivize miners to self organize in a network optimal way.

Round 2

The current hints for the 2 ETH are:

May 6th: The CAs
May 7th: I think you should go home now Devin

The previous hints can be disregarded as Round 1 to find 1 ETH has already been found.

Here is the solution to last weeks Puzzle for 1 ETH. This corresponds to this address which had 1 ETH.

Checkout our new puzzle for a chance to win 2 ETH!

The current hints for finding the 1 ETH are:

May 2nd: ECC
May 3rd: P=Q

Retweet today's hint for a chance to get tomorrow's hint today!

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


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


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


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.