i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
Yes, as I understand it, the trick is the deterministic order. The "signal as to how far down in that list" is the thing gavin tweeted about.
how reliable is a synced utxo set across all miners?
I don't think it is the utxo set, that has to be in an deterministic order, but the txs in the mempool. The utxo set is a result of the valid blockchain, so it should be synchronized already (except a node regards a block as valid, which later will become orphaned).
Gavin proposed to use "Invertible Bloom Lookup Tables". The lookup table tells the miner which transactions from its mempool should be considered for the verification of the published blockheader. Because now the miner knows which txs are used to form the block and in which order, he can reconstruct the merkle root and compare that against the published blockheader. However the proposed "Invertible Bloom Lookup Tables" are not 100% reliable. From a quick glance at the paper I found, that about <1% of keys are lost during an experiment with 10000 keys. Keys can be seen as txs in this case.
I just read the relevant parts of
a paper explaining ITLB (Invertible Bloom Lookup Tables)... quite an interesting data structure. It has a constant size (pre-chosen) and allows storing (key, value) pairs. "insert" and "delete" operations are efficient. "get" may fail and "list" may return partial results.
I can see how an ITLB of some constant size might be used for block announcements by miners.
Some things I don't quite get, though:
- why does this require deterministic ordering of txs in mempool?
- does this require that all txs a miner includes in a block are properly broadcast beforehand?
- would this require a hardfork or can it be used off-chain (so to say) by a subgroup of willing miners?
Now I ask myself what happens in case of the remaining 1%? Maybe the failure rate can be reduced by publishing multiple lookup tables of the same set?
maybe the publishing miner can include the 1% explicitly (he can determine which ones are affected himself and include the remainder). This would destroy the "constant size" property, but it would lessen the propagation cost of block size by ~99%, right?
