RTXI is the dual of UTXO
posted on 25 Nov 2019A UTXO system like Bitcoin has the property that transactions are logically sequential but can be validated in polylog-span. This is why Bitcoin is scalable.
To understand the log-time parallel algorithm, it helps to understand how to validate a chain in reverse.
RTXI means Required Transaction Input. The RTXI set is matched against UTXO from “incoming” transactions in reverse order.
Some amount of RTXI remain until the first block is reached. At this point all RTXI must be satisfied, and any remaining UTXO is the UTXO at the head chain state.
(Note: This idea was independently described by keybase.io/stoichammer (reddit) (twitter), who called it “ZTXI” for “zero-conf transaction input”. A ZTXI could be described as an RTXI in the context of a block-under-construction.)
Partial results for reverse validation don’t prove much, and there is no apparent advantage of validating in reverse if the entire chain must be validated.
This algorithm is only useful as a conceptual stepping stone to the parallel algorithm that combines partial results recursively.
If a picture is worth a thousand words, how many words is a picture with words in it worth?
