Gold collapsing. Bitcoin UP.

[cypherdoc]

@lunar

can he do math?:

>Let us for example say that BCH is trading at $600 USD and a WHC is trading at $6.25 USD. You own 50 BCH.

>If you sell your 50 BCH to gain the 5,000 WHC as any arbitrager will immediately do, you now have $625 x 5,000 value in WHC. That is, $312,500 or a $ 12,500 USD profit.

 

[awemany]

Being kind of reluctant to deal with this old wound once more, on LTOR, as you asked @Mengerian:

But is computing the Merkle tree really a significant part of block construction? My impression was that it's computation cost is pretty minimal compared to everything else. I did some back-of-the-envelope calculations that calculating the Merkle tree for a 1GB block with 5 million transactions should take something like half a second.

Yes. And not only back-of-the-envelope calculations but actual testing and benchmarking of real existing code shows that "TCTOR" - canonical ordering which is compatible with the current ruleset, would have a runtime of very roughly similar magnitude. Link.
Which is (or rather: was) one of my arguments that we would have some time to explore this further.

Note that complexity and runtimes of this order have been used as arguments for LTOR and its better behavior in parallelized environments. It seems a bit like a double standard to say (paraphrasing from memory) "Well, this run time will eventually impede blockchain growth" while also saying "It should be fine" in this case here, which at least seems like a valid angle to explore for further development (weakblocks, that is).

I'm also curious, does @awemany's subchains implementation do any of this efficient Merkle-updating? I would be surprised, since it seems like a small incremental gain. But I am interested to know if anyone has looked at how difficult or complicated it would be to actually implement.

Nope. But I guess I also don't need to deal with this anymore. My weakblocks code is on ice until all the canonical sorting stuff has been merged for the upcoming November upgrade.

I'll cope. Nothing about LTOR (or TTOR) is going to be a major issue anytime soon as far as I can see.

I have one plea, though (also @deadalnix): Can we please recommend that software external to bitcoind should refrain, until further notice, from assuming anything about transaction order in blocks? At least this would allow potential further updates down the road (I am thinking years down the road or so). With potential exceptions ("exclusion proofs") narrowly defined.

 

[cypherdoc]

@Peter R @awemany

I have been thinking about Lexical Transaction Order Rule (LTOR) and how it relates to subchains.

Seems to me the two are totally compatible. The only difference would be that with LTOR, when you receive a sub-block, you would insert the transactions into the appropriate place in the set, rather than appending them to the end of the list. This should be just as easy computationally I would think, and would be easily compatible with parallelized block construction in the future.

The Merkle tree would have to be re-built each time, but this is the case anyway with appending since the coinbase transaction also changes with each sub-block. Plus re-building the Merkle tree takes almost no time, and the only way to really solve that is with something like a "Merklix" tree (Which is almost exactly the same as a Merkle tree, but makes insertions efficient).

What are your thoughts? Was I wrong to have the impression you thought there was some issue with LTOR and subchains, or is there something I am overlooking?

doesn't LTOR prevent covert AB? which we can assume is being used routinely now by miners on both BTC and BCH. why would any miner be in favor of LTOR? also, it appears AB miners would be averse to anything that requires recomputing the Merkle root hash too frequently.:

>This may be possible, but restrictions such as transaction ordering might prevent such shuffling.


https://blog.bitmex.com/an-overview-of-the-covert-asicboost-allegation-2/

 

[awemany]

doesn't LTOR prevent covert AB? which we can assume is being used routinely now by miners on both BTC and BCH. why would any miner be in favor of LTOR? also, it appears AB miners would be averse to anything that requires recomputing the Merkle root hash too frequently.:

Interesting question, it seems to make it harder, yes. However, you can easily imagine that instead of moving transactions around, you just put some in and take out others (maybe some for which you have 'preground' their TXIDs to be at the right spot in the Merkle tree). Have we ever seen any hint of covert AB being used?

If (basically) all mining hardware out there supports AB, I guess the answer here is that it would be a change that would apply equally to the playing field and thus no single miner would need to care about his special interest.

 

[cypherdoc]

@awemany

>Have we ever seen any hint of covert AB being used?

the whole point is that we can't tell. except for maybe the excessive production of small blocks. that would be an inference of course.

but looky here. who's leading the pack in overt AB on BTC? Slush. if miners are dabbling using overt AB, you can bet they are using covert AB too. which also brings up the possibility as to why Antpool was avoiding stress test sized big blocks, since small block production is an option to avoid excessive Merkle root/tree rehashing:

https://asicboost.dance/

>If (basically) all mining hardware out there supports AB, I guess the answer here is that it would be a change that would apply equally to the playing field and thus no single miner would need to care about his special interest.

given that some proposals out there make it seem like LTOR can be an optional strategy, the conclusion in that scenario would be that none of them would do it.

 

[cypherdoc]

ossification (fighting) continues. like i said, the only thing viable, understandable, demonstrated, and generally agreed upon at this moment is continued blocksize increases. remove the limit altogether and get it over with, while we can:

https://medium.com/@g.andrew.stone/why-abcs-ctor-will-not-scale-8a6c6cf4a441

 

[Mengerian]

Two great articles demonstrating that Wormhole is toast. It really is lighting 2.0 and it's not looking good for Bitmain.

Craig seems to suffer from WDS (Wormhole Derangement Syndrome)

 

[AdrianX]

@lunar

can he do math?:

>Let us for example say that BCH is trading at $600 USD and a WHC is trading at $6.25 USD. You own 50 BCH.

>If you sell your 50 BCH to gain the 5,000 WHC as any arbitrager will immediately do, you now have $625 x 5,000 value in WHC. That is, $312,500 or a $ 12,500 USD profit.

A clincher here is like the concept of burning the ships when you invade a foreign land. There is no turning back.

You can buy back more BCH but then all you are doing is reducing the BCH money supply, and forcing the price up, BCH is not getting more valuable.

 

[cypherdoc]

great post:

https://www.reddit.com/r/btc/comments/9dx24f/a_hopefully_mathematically_neutral_comparison_of/

 

[adamstgbit]

for good or for bad, WHC is going to happen, no stopping it.
But
if Craig provides similar functionality to BCH itself, then WHC is going to become mostly irrelevant.

 

[freetrader]

Craig seems to suffer from WDS (Wormhole Derangement Syndrome)

One could almost say that Wormhole is living rent-free in Craig and his supporters' brains, where it's burning more neurons than BCH.
I doubt most other people ever spend more than a brief thought "oh, another token system on top of Bitcoin Cash" on it.

I enjoyed reading some of those emails between Ira and Craig.

I sell myself to gaming companies.

I still do a lot of work with Casinos, Sport Beng and other gaming firms. Some of this is not really legal within the US, hence Panama. Much of that secrecy comes from the fact that the US government would have closed what we did down as well if they could have, gaming would have been a great excuse to kill off Bitcoin. The thing is, it paid the bills.

Still can't get over the fact that this guy objected to DATASIGVERIFY on the basis of it allowing unlicensed gambling, something which is in now way enabled since it's already possible and has been for a long time, and the legality doesn't even have anything to do with any new opcode.

 

[Mengerian]

Being kind of reluctant to deal with this old wound once more, on LTOR, as you asked

Ha ha, OK, maybe I will leave this line of inquiry for now, in that case. Don't want to poke at old wounds.

Regarding the whole Canonical order discussion generally, it seems that the anti-LTOR voices are divided into several factions. Or the arguments shift depending on what issue is being discussed. Maybe it's a bit of both.

When the discussion is about parallelization, people point out that the main benefit comes from removing TTOR:

I have always advocated for no ordering, although I do not think the benefits really justify a hard fork.

- Andrew Stone, Reddit

And when the topic is propagation, it is pointed out that it's possible to make a canonical order that preserves topological order:

While it is true that most the bytes encoded the ordering, it is not necessarily true that ABC’s mandatory lexical ordering is the best way forward. For example, Gavin proposed a consensus-compatible canonical ordering that could be used today without a forking change:

- Peter R, Reddit

But these two positions are mutually exclusive. To decide what path to take, we need to look at the actual options (with the tradeoffs in each) and compare them.

I think that the options can be grouped into four categories:

1. "Do nothing": This means no hard fork or soft fork, and keeping the current order rules (TTOR, no CTOR). This is difficult to parallelize, and bad for block propagation.

2. "AOR (Any Order Rule)": Remove TTOR, but allow any order. This is a hard fork, is good for parallelizing the code, but with no propagation benefits.

3. "GTOR (Gavin's Transaction Order Rule)": This would be a soft fork if enforced, or could be left optional (Gavin's proposal left it optional). It preserves TTOR, and defines a canonical order on top of that. It's likely the worst option for parallelization, but good for Graphene propagation.

4. "LTOR (Lexical Transaction Order Rule), aka CTOR": This is a combined soft-fork to remove TTOR, with a tightening of the rules to enforce simple lexical order. It enables easy parallelizization of the code, and also provides the propagation benefits for Graphene and other block propagation systems.

It might be worth going into more specific details, but I think this is a fair summary.

So given the above, it seems to me LTOR is the best option.

 

[Peter R]

@Mengerian

In Gavin's proposal, GTOR was optional. So no soft fork.

 

[Mengerian]

@Peter R OK, thanks. I edited my post to indicate that it could be optional.

 

[Peter R]

I'd like to understand this debate with respect to parallelization better. Let's just look at block validation for now:

Upon accepting a block, I can divide the block up between workers to parallelize the validation of the transactions in that block. These workers could be threads on a computer, or separate pieces of hardware (imagine specialized hardware nodes).

One of the things I care about is whether or not all the transactions in the block _eventually_ make it through validation (the other things I care about are the Merkle root and the transaction order, which I'll get to later). If, part way through validation, a transaction fails because an input was missing, the worker responsible can just keep trying in hopes that another transaction gets processed which resolves the missing input. From @awemany's work, I think we can say that TTOR has the advantage here, because essentially all transactions should validate on the first attempt (no missing dependencies) [I know awemany was looking at the OTI algorithm and I'm imagining a different parallel algorithm, but I think the effect he noticed will apply to all parallel algorithms]. I don't know whether this advantage will be significant.

Regardless of the way transactions are ordered, validating all of the transactions in the block seems to be highly parallelizable (with one proviso being not _too_ many chained transactions, in which case topological seems better).

With AOR, there's only one more thing I need to check: does the Merkle root for the transactions match what's in the block header? For this, I need to know the order of the transactions. There is obviously at least _some_ complexity parallelizing this, because we need communication between the workers to build the Merkle tree. My hunch is that blocks sorted topologically will be better here, because then we can grow the Merkle tree slowly via subchains. I don't know whether this advantage will be significant.

With TTOR or LTOR, there's an additional check I need to make: does the order of the transactions satisfy the ordering rule? My hunch here is that LTOR will be better, because each worker can check its local ordering--as long as all the local orderings are correct, and the boundary conditions between the workers are correct (I'm a physicist not a computer scientist, so that's probably the wrong term), then the total block order is correct. With TTOR, I think the check would be more complicated to parallelize. I don't know whether this advantage will be significant. (Also, of course AOR is even better here, because then this check isn't required at all.)


In summary:

- Validating the transactions in a block is parallelizable regardless of ordering (transactions can be treated like a set).
- Checking the order takes some time (so AOR is better in this respect).
- Checking the Merkle root requires that the transactions be treated like a list -- and not a set (it's not like we can fully side-step the ordering problem).
- It's not obvious to me that making a change will lead to a significant improvement in terms of block validation.

 

[cypherdoc]

complexity, complexity. and no one has any real research data. tisk tisk.

 

[Peter R]

I think I finally figured out the reason for LTOR. LTOR makes sense if you pair if with @deadalnix's Merklix tree idea:

https://www.deadalnix.me/2016/09/24/introducing-merklix-tree-as-an-unordered-merkle-tree-on-steroid/

The reason for LTOR+Merklix is to make all steps easily parallelizable.

 

[shadders]

I don't think ABC think so. I mentioned that CTOR creates a dependency on merklix in Bangkok and heard many groans of derision from the ABC corner of the room.

 

[Mengerian]

I'd like to understand this debate with respect to parallelization better. Let's just look at block validation for now:

Thanks for laying this all out so clearly @Peter R, that helps.

Overall I generally agree with how you described things, but there are a few points where I see it a bit differently. These could maybe explain why we have come to different conclusions on LTOR.

Regardless of the way transactions are ordered, validating all of the transactions in the block seems to be highly parallelizable (with one proviso being not _too_ many chained transactions, in which case topological seems better).

I'm not sure about this. Because the technique for parallelizing validation ("outputs-then-inputs") also automatically handles chained transactions, it seems to me that long chains would be easily handled by the parallel algorithm, and checking the topological order would just be an extra difficult-to-parallelize step. I'm not sure how it would all work out with many small transaction chains, versus long transaction chains. Maybe @awemany has some insight into this.

With TTOR or LTOR, there's an additional check I need to make: does the order of the transactions satisfy the ordering rule? My hunch here is that LTOR will be better, because each worker can check its local ordering--as long as all the local orderings are correct, and the boundary conditions between the workers are correct (I'm a physicist not a computer scientist, so that's probably the wrong term), then the total block order is correct. With TTOR, I think the check would be more complicated to parallelize. I don't know whether this advantage will be significant. (Also, of course AOR is even better here, because then this check isn't required at all.)

I basically agree with the order checking difficulty can be ranked AOR > LTOR > TTOR. I also agree with you description of why checking order with LTOR is easily parallelizable. I think the important thing about this, though, is that the difference between AOR and LTOR is basically insignificant, whereas the difference between LTOR and TTOR is significant.

Also, I notice a big difference in our thinking when you say: "I think the check would be more complicated to parallelize. I don't know whether this advantage will be significant."

Because, the way I see it, to reach very large scale, parallelizing basically trumps everything else. Let's say something like subchains increases the ceiling on feasible block sizes by incrementally building (or validating) blocks during the 10-minute window. But if the process is inherently "linear" you still have a ceiling, even if it's 100 times higher. You can't really throw more hardware at the problem, because there is ultimately a technical limit of how quickly each step can be done.

Parallelizing, on the other hand, means you can break the task into many smaller chunks, and use more hardware. So even if the parallel process requires, say, twice as much computation as a linear process, you can handle the same workload with twice the hardware. And if it's really parallel at all levels, there no real technical limit to the workload it can handle. It turns it from a technical problem into an economic problem, which automatically solves itself with more usage.

As a hypothetical example, maybe the linear process will need computing resource worth 0.01 cents per transaction, but the parallel process will need 0.02 cents to process a transaction. Either way, it's cheap enough to not be a problem, and the parallel system can keep adding computing resources as usage increases, without ever running into a ceiling.

(By the way, I don't think parallel processes will actually use twice the resources, it's just a hypothetical example to make the point)

Looking at the whole picture, after LTOR is in place, Merkle tree structure is the main remaining non-parallelizable data structure. Maybe changing the Merkle tree to a Merklix tree will look like a good way to go, but I imagine that will have to go trough lots of analysis and debate. If it turns out to be infeaible to do that for some reason, I guess we'll have to assess whether the benefits of CTOR for propagation outweigh the benefits of incrementally building the Merkle tree, and potentially revert LTOR if not.

[EDIT: Just after I posted, I see that you you just posted a comment about Merklix trees. I agree that there is some synergy between the two, and make a compelling roadmap if considered together. But a case can be made for LTOR with or without Meklix]

To completely remove the scale ceiling, we want to turn the technical limits into something that can be solved through economics. The way to do this is to parallelize everything.

 

[MarkBLundeberg]

My interpretation of the changes in ABC code is that they are actually two steps in one: 1) Remove TTOR, and 2) Add CTOR. Interestingly, there are only a dozen lines or so that implement CTOR (#2), and without them the ABC fork would actually be TTOR->AOR.

I suspect one primary motivation is simply that they want to implement the parallel OTI algorithm. The OTI algorithm is elegant and obviously parallelizable. It runs in predictable time: Every transaction iterated exactly twice, and worker threads don't stumble over each other even if the block is one long chain of dependent transactions. If your algorithm needs retries, then the worst-case performance could be bad.

It was thought that using OTI would not allow verifying TTOR. So, I am guessing that because they wanted OTI, they had to first get rid of TTOR. Toomim showed that this turns out to be incorrect -- you can also verify TTOR using OTI with just a bit of extra memory usage.

Do the extra loops or extra memory usage actually make a difference? Toomim's benchmarks on the unparallelized versions show that all three approaches (serial validation, OTI, modified OTI) all have very similar speed. So indeed, perhaps there is no parallelism gain in removing TTOR. On the other hand, from looking at all the evidence, I don't think removing TTOR is going to *hurt* anything except that programmers will have to spend a bit of time switching over to OTI (easy).

This leaves the second change, of imposing CTOR. This is just the easiest way to make graphene work better and simpler. Once CTOR activates you can just remove the ordering info out of the graphene protocol. No need to worry about optional canonical orderings and optimizing the ordering information down to the entropy limit. If we can make graphene work better and simpler, then this *is* a good optimization since block propagation was becoming a noticeable issue during the stress test.