@Mengerian @MarkBLundeberg

I think we're getting somewhere.

BLOCK VALIDATION

Let

Task 2 is obviously parallelizable for LTOR, with only boundary conditions communicated between the workers. The complexity class is O(

Task 2 for TTOR is still O(

Task 3 is parallelizable for both TTOR and LTOR. The complexity class is O(

BLOCK CREATION

For block creation, we need to

Task A has complexity class is O(1) (per insertion)

Task B has complexity O(log

Task C has complexity O(

----------

TTOR wins on Task B and C, and possibly loses on Task 2. It ties with LTOR on the rest.

But LTOR + Merklix would tie with TTOR on Task B and C and possibly win on Task 2. I also think LTOR + Merklix would be simpler to implement and faster by a constant factor than TTOR.

I still think LTOR is not worth it, but I think LTOR + Merklix might be worth it. Does Merklix actually work like @deadalnix thinks? That sounds very interesting.

I think we're getting somewhere.

BLOCK VALIDATION

Let

*N*be the number of transactions in a block and*M*be the number of workers. Let's think about block validation as three different tasks:- Checking that the transactions in the block are valid and not already spent
- Checking that the transactions are ordered correctly
- Verifying the Merkle root in the block header

*egardless of the order.*Please let me know if you disagree, because this seems really obvious to me. The complexity class is O(*N*) and can be easily split up over*M*workers. We could validate millions of transactions*per second***today**just by throwing more hardware (in parallel) at the task.Task 2 is obviously parallelizable for LTOR, with only boundary conditions communicated between the workers. The complexity class is O(

*N*) and can be split up over*M*workers.Task 2 for TTOR is still O(

*N*) I believe, but it is not obvious to me how to parallelize it, but I suspect it can be (I think @jtoomim said something about this).Task 3 is parallelizable for both TTOR and LTOR. The complexity class is O(

*N*log*N*).BLOCK CREATION

For block creation, we need to

A. Continually accept transactions into mempool

B. Maintain the required order

C. Update the Merkle root for each new block candidate

B. Maintain the required order

C. Update the Merkle root for each new block candidate

Task A has complexity class is O(1) (per insertion)

Task B has complexity O(log

*N*) per insertion for LTOR and I would argue O(1) for TTOR. I argue it could be made O(1) for TTOR because the transactions have to enter your mempool in topological order, and so you can probably get the required ordering for nearly free.Task C has complexity O(

*N*) per insertion for LTOR and O(log*N*) for CTOR. It's O(log*n*) for TTOR because you just tack new leaves on the the end of the Merkle tree; you don't need to rebuild the entire tree. We discussed the yesterday (@shadders, @imaginary_username).----------

TTOR wins on Task B and C, and possibly loses on Task 2. It ties with LTOR on the rest.

But LTOR + Merklix would tie with TTOR on Task B and C and possibly win on Task 2. I also think LTOR + Merklix would be simpler to implement and faster by a constant factor than TTOR.

I still think LTOR is not worth it, but I think LTOR + Merklix might be worth it. Does Merklix actually work like @deadalnix thinks? That sounds very interesting.

Last edited: