Feedback-ID: i525146e8:Fastmail
Date: Tue, 14 Jun 2022 07:12:14 -0400
From: Peter Todd <pete@petertodd.org>
To: Jeremy Rubin <jeremy.l.rubin@gmail.com>
Message-ID: <YqhtDoN784GG4Cx8@petertodd.org>
References: <YhAwr7+9mGJAe2/p@petertodd.org>
 <CAD5xwhi=sKckFZew75tZTogoeFABraWtJ6qMC+RgZjcirxYyZw@mail.gmail.com>
 <YhC6yjoe3bAfBS+W@petertodd.org>
 <CAD5xwhjR06Lp3ka-MqZQE64tfE5uDQB6TrMh06khjYrDzuT95g@mail.gmail.com>
 <YlMw5NxXnGV9WrVg@petertodd.org>
 <CAD5xwhj1kaJf+QCcf1MOtaAec-xTTr2M9LkJPCu2Ej0L9_3iPg@mail.gmail.com>
 <YlmGv6WbDeDqGJKX@petertodd.org>
 <CAD5xwhgGgq30C7GniNh1_DobPe+P4NTJySUkDiBZBj=OjzO5KA@mail.gmail.com>
 <YmqFRlDIkfbyVIZ2@petertodd.org>
 <CAD5xwhhB+8n+9pWiSCtx3DAPnSwV_7xHnXZ14mEj9H93eWUNEw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="XHqCk7LgV0g3xv8l"
Content-Disposition: inline
In-Reply-To: <CAD5xwhhB+8n+9pWiSCtx3DAPnSwV_7xHnXZ14mEj9H93eWUNEw@mail.gmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 lightning-dev <lightning-dev@lists.linuxfoundation.org>,
 Jeremy <jlrubin@mit.edu>
Subject: [bitcoin-dev] Why OpenTimestamps does not "linearize" its
	transactions
Precedence: list


--XHqCk7LgV0g3xv8l
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Mon, May 02, 2022 at 08:59:49AM -0700, Jeremy Rubin wrote:
> Ok, got it. Won't waste anyone's time on terminology pedantism.
>=20
>=20
> The model that I proposed above is simply what *any* correct timestamping
> service must do. If OTS does not follow that model, then I suspect whatev=
er
> OTS is, is provably incorrect or, in this context, unreliable, even when
> servers and clients are honest.

Do you think RFC 3628 is "provably incorrect" too? It's just a standard for
Trusted Time-Stamping Authorities to issue timestamp proofs via digital
signatures, in the most straight forward manner of signing a message claimi=
ng
that some digest existed as of some time.

As the RFC says in the introduction:

    The TSA's role is to time-stamp a datum to establish evidence indicatin=
g that a
    datum existed before a particular time.  This can then be used, for exa=
mple, to
    verify that a digital signature was applied to a message before the
    corresponding certificate was revoked thus allowing a revoked public key
    certificate to be used for verifying signatures created prior to the ti=
me of
    revocation.

Simple and straight forward.

The problem here is starts with the fact that you're asking timestamp servi=
ces
to do things that they're not claiming they do; a timestamp proof simply pr=
oves
that some message m existed prior to some time t. Nothing more.

Worse though, linearization is a busted approach.

> Unreliable might mean different things to
> different people, I'm happy to detail the types of unreliability issue th=
at
> arise if you do not conform to the model I presented above (of which,
> linearizability is one way to address it, there are others that still
> implement epoch based recommitting that could be conceptually sound witho=
ut
> requiring linearizability).
>=20
> Do you have any formal proof of what guarantees OTS provides against which
> threat model? This is likely difficult to produce without a formal model =
of
> what OTS is, but perhaps you can give your best shot at producing one and
> we can carry the conversation on productively from there.

So as you know, an OpenTimestamps proof consists of a series of commitment
operations that act on an initial message m, leading to a message known to =
have
been created at some point in time. Almost always a Bitcoin block header. B=
ut
other schemes like trusted timestamps are possible too.

A commitment operation (namely hashes + concatenation) simply needs the
property that for a given input message m, the output H(m) can't be predict=
ed
without knowledge of m. In the case of concatenation, this property is achi=
eved
trivially by the fact that the output includes m verbatim. Similarly, SHA1 =
is
still a valid commitment operation.

Behind the scenes the OTS infrastructure builds merkle trees of commitment
operations for scalability reasons. But none of those details are relevant =
to
the validity of OTS proofs - the OTS infrastructure could magically mine a
block per transaction with the digest in the coinbase, and from the client's
point of view, everything would work the same.


The important thing to recognize is that timestamp proof is simply a one-si=
ded
bound on when a given message existed, proving a message existed _prior_ to
some point in time. For example:

    $ ots verify hello-world.txt.ots
    Assuming target filename is 'hello-world.txt'
    Success! Bitcoin block 358391 attests existence as of 2015-05-28 EDT

Obviously, the message "Hello World!" existed prior to 2015 (Indeed, it's s=
uch
a short message it's brute-forcable. But for sake of example, we'll ignore
that).

Thus your claim re: linearization that:

> Having a chain of transactions would serve to linearize history of
> OTS commitments which would let you prove, given reorgs, that knowledge of
> commit A was before B a bit more robustly.

=2E..misunderstands the problem. We care about proving statements about mes=
sages.
Not timestamp proofs. Building infrastructure to order timestamp proofs
themselves is pointless.


What you're alluding to is dual-sided bounds on when messages were created.
That's solved by random beacons: messages known to have been created *after=
* a
point in time, and unpredictable prior. A famous example of course being the
genesis block quote:

    The Times 03/Jan/2009 Chancellor on brink of second bailout for banks

Bitcoin block hashes make for a perfectly good random beacon for use-cases =
with
day to hour level precision. For higher precision, absolute time, there are
many trusted alternatives like the NIST random beacon, Roughtime, etc.


OpenTimestamps could offer a trustless _relative_ random beacon service by
making the per-second commitments a merkle mountain range, and publishing t=
he
tip digests. In fact, that's how I came up with merkle mountain ranges in t=
he
first place, and there's code from 2012 to do exactly that in depths of the=
 git
repo. But that's such a niche use-case I decided against that approach for =
now;
I'll probably resurrect it in the future for trusted timestamps/clock sync.

Again, involving the transactions themselves in any of this random beacon s=
tuff
is pointless.

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--XHqCk7LgV0g3xv8l
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCgAdFiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAmKobQgACgkQJIFAPaXw
kfsmeAf9GHdODR3XTTwWn9fPdgcnrgWr/ar3D6SVFO01Gyx34ifGbhfMpgpEyQdf
wHNPLD2lr8Ou675tSoF/T0O23lSNEeifipTnkBK7QGaGC1m+c/B2Stk4AWutUKHW
yw49xu6w6gg0sJls/XV3q7o1SrmERYPi3OY8plcA3I3dxnweQIDcHiol2SKTshWH
1mi/elQqOysZZcEkhZzQTk7MvZ+UfcsERe+GR4on/ogaPDZ1o7ieLhdKIsoE85gi
YBr3sJXdWHTPBr5x3c5s6t9EVyXMFmD9CyW+6kamW5w7yX39w2KUO5Ba9cinQ9ym
ihfaOq5gVdb+o4EI6ZW6RX04ZEV1Hg==
=ZyI8
-----END PGP SIGNATURE-----

--XHqCk7LgV0g3xv8l--