Author: Peter Todd 2014-12-22 00:11:37
Published on: 2014-12-22T00:11:37+00:00
On December 20, 2014, Peter Todd shared a note on behalf of Andrew Miller about using a "proof-of-publication" system to implement an "anti-replay" system. However, Todd argued that this isn't entirely true given the description of proof-of-(non)-publication and the definition of "anti-replay." The anti-replay mechanism is about proving that no message satisfying some property has been published, whereas proof-of-*non*-publication allows you to prove that some specific message has never been published. Todd suggested extending the definition of proof-of-(non)-publication to take in some predicate P to prove that no message m such that P(m) holds has ever been published efficiently. This requires anticipating some classes of P and building appropriate indices. Todd emphasized the importance of indexes and validation in cryptocurrency designs to support efficient anti-replay proofs. As long as the whole blockchain is available, one can scan through the entire blockchain and evaluate P for every transaction. Other tradeoffs are available if one is willing to trust some servers to maintain indices. Bitcoin's UTXO set effectively supports a predicate for each txout, while Ethereum contracts allow general-purpose contracts to build-your-own index. However, its key-value store doesn't support range queries, so it's not necessarily universal or as expressive as SQL.Todd concluded that proof-of-(non)-publication alone isn't sufficient to support efficient anti-replay proofs. While establishing "proof-of-publication" as a universal underlying primitive is significant, part of what Bitcoin provides is indexing and validation/exclusion.
Updated on: 2023-06-09T15:00:24.731511+00:00