Achieving consensus on a value with peers that can cheat or collude

Question

Suppose I have a webpage that publishes some number x that changes over time and the page is publicly accessible.

I would like to somehow create a proof that this webpage published value y at time t. Is there a way to make this possible?

This needs to be done without any sort of central authority, so it's not good enough to just sign the value + a timestamp by the webpage that is doing the publishing. So an example might be something like a stock market API publishing values, and we'd like to provide some proof they published a certain value at a certain time.

Answer 1

First off, I think that any (purely) cryptographic solution to this will be completely unable to address these threat models:

• What if you want to muddy the waters by secretly serving y' to yourself, generating a proof to reveal later, perhaps to "retroactively" overturn some outcome you don't like?
• What if you serve y to yourself (generating a proof), while presenting a 429 or 503 error to anonymous visitors, and y' to known (non-proving) web scrapers, such as web.archive.org, archive.is, and cache.google.com?

---

Now, to answer your question: what do you mean by y being "published"?

I can think of 3 reasonable interpretations:

1. No client was served any message unequal to y as an HTTP(S) response within some window around t
2. No client capable and willing to run proofs on the response (as well as to whistleblow about any inappropriate values) was served any message unequal to y as an HTTP(S) response within some window around t
3. The web server emitted y as an HTTP(S) response to at least one client capable and willing to run proofs on the response within some window around t

(1) is simply not feasible.

Clearly, it'll be very difficult to (cryptographically) "prove" anything about what your API serves to clients who aren't interested in doing proofs about the responses.

For example: if web.archive.org and archive.is both allege and agree that your server yielded value y' (unequal to y) in window t, then most reasonable people (assuming no serious political upheaval happens that'd compromise the archivists' integrity) would consider those archive servers' responses a valid "proof" that you (or at least someone who'd compromised your domain or host) served y' at that time. However, this isn't good from a cryptographic perspective unless you are willing to add in these archive services as "trusted witnesses" or "trusted oracles" in an instance of your cryptosystem.

If (2 & 3) is acceptable to you, however, you might consider DECO: Liberating Web Data Using Decentralized Oracles for TLS, which allows TLS clients to create zero-knowledge proofs about data received from TLS servers without TLS-N or any server-side software modifications.

DECO would allow any interested party to "whistleblow" your serving any y' value, and it would allow any interested party to "verify" your serving an appropriate y value.

Overall, the problem here is more of a consensus issue than a cryptographic one (though with DECO it is possible to make large cryptographic strides towards solving it). In particular: what is the process by which "whistleblowers" are supposed to reveal any y' values you serve? Is there a timeframe? A centralized service? What prevents you from just ignoring and banning anyone who whistleblows on your incongruence? I think that combining DECO (for the proofs) with a decentralized blockchain (for the consensus) is a possible viable way forward, depending on what threat models your users have.

Answer 2

Any such scheme will be just as dependent on a "central authority" as "sign the value + a timestamp by the webpage that is doing the publishing", given that said "central authority" determines the value of x.

The remaining thing to think about is whether the authority at a given time can manipulate results in a different time. We can easily prevent manipulation of past values, by not accepting any timestamps before the present time. However, for future values, the adversary which is able to compromise present authenticated values can also pre-generate future authenticated values. A mitigation here is to have key trust expire and/or a revocation registry.

If you must use a subjective protocol, there are a number of Schelling-point schemes and challenge protocols you can use, which are used in blockchain oracles - see for example Augur, UMA, Kleros.

You could try to combine these schemes, for example using public-key authentication, but with a decentralized court to rule on fraud and revoke keys. However, this would also defeat the security of the public-key authentication, as a compromised court would be able to revoke legitimate messages and rotate to a compromised key. Perhaps, though, it would decrease the frequency of challenges in practice.