Predictable ordering of "proof-of-structure" (the 2018 CTOR upgrade) and possible future advances

Random
#1

I came to the conclusion of ordering transactions in Merkle tree by myself over the past week, as it is required to allow the type of parallelization I think is meaningful, and learnt that Bitcoin Cash had gotten there already by 2018. Good job to this community. The reason such ordering (CTOR) is meaningful is because it allows shards to contribute to the “proof-of-structure” in parallel (with a degree of sharding that is arbitrary, i.e., a node can use no sharding, another thousands) while respecting the Nakamoto consensus with a singular central authority that signs each “block of authority”.

I want to emphasize that with the sharding that Bitcoin Cash can now do since 2018, shards can also be geographically and socially decentralized (whilst operating as “teams” that have a view of the entire state at any given time). The “node” can become like a “mining pool” but for the blockchain itself, and nodes (teams) compete to verify the state is correct. This scales infinitely. Note, transactions are “owned” by shards so to use a UTXO from another shard you request the right, and it is first-served basis.

Such predictable ordering of “proof-of-structure” (that the Nakamoto consensus can then sign and attest to that the “team” agrees with the correctness of the state, and if they lie and the state is invalid the block is refuted by others and mining reward lost) can be achieved with other architectures than Merkle trees. Merkle trees cannot be ordered over all time, thus they need to sort transactions into blocks (and likewise, authority has to be in “blocks” in Nakamoto consensus, so, two birds with one stone). I was thinking (but this goes beyond Bitcoin Cash and is placed here as an open question): What if for the proof-of-stricture that is signed with Nakamoto consensus, we instead use a Patricia Merkle Trie? A singular trie, and nothing else. And the Nakamoto consensus signs the root of this trie in an “authorization hash-chain” that only contains the signatures and previous authorization hash. I.e., the “block” becomes a block of time of authority, and the proof-of-structure is not confined to block anymore as with Patricia Merkle Trie it can be ordered over all time.

This architecture is speculative, I ask others if you find it interesting or if it sounds retarded. Also, if anyone is interested in perfecting a Lightning Network on BCH I solved the coordination game theory for that, see here: https://resilience.me/3phase.pdf.

2 Likes
#2

There was a proposal by former ABC team to make the block’s root be a trie, they called it Merklix tree:

In the Bitcoin community, the concept has been introduced as the Merkle prefix tree [3] and the
Merklix tree [4]. The Ripple community refers to the concept as hash tree [5] while the Ethereum
community refers to it as Patricia tree [6].

I was interested in it for a while because it seemed neat that you can prove non-existence, but later I figured there’s not much use of that so lost interest. Other interesting properties are easier insertion/removals, but again - what’s the use?

I do like the idea of having 1 hash commit to the whole chain, against which you could verify a Merkle proof for any transaction. I was drafting a proposal to simply generate a merkle root of block headers and commit the root of [0, N-1] headers to the Nth block. Turns out, Electrum protocol already implements this (cp_height), albeit you have to trust Electrum servers for the root - or you have to process all headers to compute the root independently.

I wanted to dabble with this, thought to implement Eltoo and for that started to draft a CTV implementation in BCH Script. Which primitives do you need? We don’t have SegWit but thanks to TX introspection opcodes and OP_CHECKDATASIGVERIFY (aka CSFS in BTC circles) we can implement LN-type channels using the SIGHASH_ANYPREVOUT approach (as originally proposed in LN whitepaper).

We already have a 2-phase PTLC swap in production (1. Swap | Initiate Refund 2. Complete Refund | Punish), see here for details: ac-0353f40e / cross-chain-swap-ves · GitLab
This is in production on BasicSwap DEX, but volume is nothing to brag about, here’s the current metrics data gathered from the chain (contract p2sh fingerprint d2f1941cf34f4779feafd682e95a23ded64f11d113af139f967d6f3d8bb61565).

image

2 Likes
#3

Good to hear that Bitcoin ABC noticed already by 2018 that when ordering leaves in a Merkle tree it starts to become more or less similar to “binary tree” of some sort. I would say all of them (CTOR, or Merklix or Patricia) have the property that allows shards to assemble the “proof-of-structure” in parallel, so either works. The parallelizability under Nakamoto consensus (maintained singular point of authority) may be the important part, and exactly how it is achieved secondary.

My idea with the Patricia trie was that you do not have it per-block, but a singular Patricia trie of all transactions ever. And a separate proof-of-work hash-chain with the signatures of the “proof-of-structure” at each “block of authority”. The rationale for that, is that if sharding takes off in the way possible by parallelizable “proof-of-structure” it might get less messy with a singular trie. If you already split it into thousands of pieces or more, also managing those per block may just make it messier. Shards still need to store the hashes per “block” in a list so they can reorg in case of forks (and propagate to other shards who are syncing from a while back), but that is separate from the formal ledger proof.

I also thought of like you (a few years ago) to have Merkle tree of the blockchain itself, and then noticed the idea was around already (as I assume it would be). But a singular transaction trie provides the same property as you note (besides for the proof-of-work hash-chain but that is reasonably verified in sequence to prove the accumulated work anyway).

On multihop, the 2-phase that Ryan Fugger invented in 2006 something (I think) was never sufficient. It had gaping security problems (that is the reason the CLTV Delta is 6 hours, 40 blocks). The security issue was the reason to introduce the “staggered timeouts” idea, but before Ryan did so in 2008 he was by 2006 aiming to fix the problem by instead making the penalty gradual (instead of all-at-once). But it was not possible to achieve that on a 2-phasee commit, so he instead invented the staggered timeouts. With my invention now this spring, the 3-phase commit, Ryan’s original “gradual penalty” is possible, and true payment channel network becomes possible on any “collateral” (BCH or also ETH/ETC or something similar).

1 Like
#4

It’s an interesting idea, so instead of the block header committing to transactions in it (diff), it would commit to all past transactions + transactions in it (whole updated history).
But what’s the point? You say sharding, but the problem of validating new transaction is not that of updating history - it’s all about updating the UTXO state. Nodes don’t even need the history to be able to validate new updates, they only need header chain + UTXO state. So, what problem would this Patricia trie over all transactions be solving?

Note that Peter Rizun is proposing computing it over state.

I’m not sure we’re talking about the same scheme. The XMR-BCH swap is based on Hoenisch, P. & Pino, L.: Atomic Swaps between Bitcoin and Monero (2021) which is based on Gugger, J.: Bitcoin–Monero Cross-chain Atomic Swap (2020). What security problems do you mean, AFAIK the main problem is that BCH side always goes first so they waste some sats in fees if XMR side bails out, but on BCH that’s less of a problem than on BCH because fees are small. Here’s the diagram for what happens on both chains:

image
image751×424 25.2 KB

Anyway, notice that in BCH contract implementation both the 1st stage and the 2nd stage contracts have exact same structure - they just commit to different output bytecodes, depending on application.
We could trivially add 1 more stage on BCH side:

image
image1017×321 18 KB

But I don’t know what to do with this, like, what amounts to commit to, and pair which actions on BCH with which actions on the other chain?

#5

The reason for the CTOR upgrade in 2018 by Bitcoin Cash is because part of the problem of validating new transactions is to assemble the Merkle proof and that with CTOR this can be done by shards in parallel. Another problem is validating “unspent output” but this is not a centralized problem like the Merkle root. It is two separate types of problems. For the “unspent outputs” you can simply have shards own their transaction hash range including any “unspent output” on any of those transactions, and every other shard thus knows exactly who to ask, and it is on “first-served” basis. This works perfectly in distributed fashion whereas the Merkle root assembly problem did not without ordering transactions in the Merkle tree (incl. if using binary tree or trie or so as those are ordered as well).

The point of it is that it might be cleaner to work with and simpler, and therefore cleaner to work with when the sharding is done. It identifies that there are two problems: “proof-of-structure” and attestation by the consensus mechanism, and it separates them. Historically they were baked into the same problem, but they are two problems. The attestation has to be in “blocks of authority”. The proof-of-structure not necessarily. Also with this nodes do need to have history to validate updates which is good, they should store history.

I solved multihop coordination this spring, if your response to that was about single-hop ledger-to-ledger then yes different topics.