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

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.

• If you sign every web server response, then someone that receives a value of $x$ can prove they really did receive it from you (as long as you're not claiming your secret signing key was stolen). Sep 8 at 2:45
• It seems in the best case you would be going for some blockchain-style solution. Create some sort of consensus mechanism where a majority of people are (hopefully) incentivised to constantly watch for these values and confirm they did actually see it. The main challenge would be incentivising people to be honest (especially if it is stock market data). Chainlink Oracles might be of interest to informing your research. Sep 8 at 9:41

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.

• Allegedly, Chainlink implements DECO, but I can't actually find the parameter to use DECO with their oracle SDK. Sep 8 at 15:26
• nota bene: there's no point to DECO — no reason to (ab)use TLS into a signature scheme — if you control the server itself (and if the data doesn't need to be masked), since, as the other answer entails, you could save everyone CPU cycles by simply adding signatures per se into your protocol. The (non-cryptographic!) problem of consensus remains. Sep 8 at 16:21
• So the end goal is to prove the data came from google. If google simply signed all of the data it returned with it's public key that would sufficient. Of course I can't ask Google to do that... so the question is how do I accomplish something similar? Sep 9 at 14:06
• @user491880 If you don't control the server (so you can't sign responses), then DECO actually provides utility in that case (generating proofs that someone possessing a valid TLS certificate for www.google.com served some data — or data fulfilling some criteria). There's still the whole hairy (not-exactly-cryptographic) issue of consensus: if Google serves contradictory data, how will a whistleblower reveal this? If Google or a CA are later compromised, or an older previously-valid keypair cracked, how will we avoid respecting data retroactively signed by the attacker? et cetera… Sep 9 at 15:17

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.