path: root/c5/654713537e17b0b0e25e52fe17e5af1a30206f

Return-Path: <user@petertodd.org>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id DA66BC002D;
 Tue, 14 Jun 2022 11:12:19 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id C2FAF60E73;
 Tue, 14 Jun 2022 11:12:19 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.802
X-Spam-Level: 
X-Spam-Status: No, score=-2.802 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7,
 SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=petertodd.org header.b="I55+QMA+";
 dkim=pass (2048-bit key) header.d=messagingengine.com
 header.b="k2AIbcwn"
Received: from smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id T6ny9A3v3cXI; Tue, 14 Jun 2022 11:12:18 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com
 [64.147.123.21])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 80593605E9;
 Tue, 14 Jun 2022 11:12:18 +0000 (UTC)
Received: from compute5.internal (compute5.nyi.internal [10.202.2.45])
 by mailout.west.internal (Postfix) with ESMTP id 4266A3200906;
 Tue, 14 Jun 2022 07:12:15 -0400 (EDT)
Received: from mailfrontend2 ([10.202.2.163])
 by compute5.internal (MEProxy); Tue, 14 Jun 2022 07:12:15 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=petertodd.org;
 h=cc:cc:content-type:date:date:from:from:in-reply-to
 :in-reply-to:message-id:mime-version:references:reply-to:sender
 :subject:subject:to:to; s=fm3; t=1655205134; x=1655291534; bh=ey
 qHpJDUYeCGJLJHY/i5pdClnkpcCei6mrN7zoo1eC4=; b=I55+QMA+AHf0wPOckE
 sExBfRHaOQ2pJJZrd4FgajHqkj+O5CeyyLj0hq4IUk+HL9LIT9uoWPRqH9kfXsJh
 yO4k5LrxC+aKl9TpRcmaV0A630rcnj49jDa69/qb6mLWAOgiNBsDFbW0CUqgVfpQ
 fSSkRbn0IQjVu+swgBQuNmsJuW6OMN3rNREZImakoCwU4TtHJsG2is1el9MgJ39g
 LjCA1bYu3wlG1UaRGwG6JCscERQ3b1/DP83OlCcoDZK6ZLcgiUSdGdBmCSnwMUFM
 YCr7admg20KUzct5kIgiSl/Caeve8Bnd7ftxRUdhrtoSbk1uvJ37+5PHoDLZpdFh
 4txg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
 messagingengine.com; h=cc:cc:content-type:date:date:feedback-id
 :feedback-id:from:from:in-reply-to:in-reply-to:message-id
 :mime-version:references:reply-to:sender:subject:subject:to:to
 :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=
 fm2; t=1655205134; x=1655291534; bh=eyqHpJDUYeCGJLJHY/i5pdClnkpc
 Cei6mrN7zoo1eC4=; b=k2AIbcwnWl9mzDYvvGpwQpkUwed/rj4dv+Vj1TBfjzcP
 qnxawXa3TvG1HQYGUESxX2Lna82GD5jeDahdONQM+JukH4+8XjiUVEKl0++b91ad
 68qY/3TPo59y/6hvxWJHROy+k3LtYh0jjINbGkHHbP0rtzOZY+Y3KRc1h1yP1+nq
 tADd6BErz7Pb9DS1KKT6iLZnS6VsllscC90mxDV9290V2AhASsb572aTfnK8FkY6
 8Mr2q/iyfEhWQN0GIOJERhJ/Vj2NFE5Yid/wZgKsi0ysfsZBsHYlNRWEwrMNew7p
 tsYTStWw6RgqPNn5owV/xg5OnYuX6TU5EGfi6ayeqQ==
X-ME-Sender: <xms:Dm2oYhGWlEIU3hi_RqVKZduoCC3Vu7ZhR88RKsRkfV3l-8vLKySLNQ>
 <xme:Dm2oYmVHuTX60T0LfExgsUCHYnMWmc84t5RKKS9AxrA7t3RsWYStjfVkQuk0i2PMH
 li7ZAtM-2gbKPGtstI>
X-ME-Received: <xmr:Dm2oYjJ8hLRLv14vYFBIAgwdaseCEwbAdrF_g9thXhxkoM6Kc4uLV-ynAoN2hlMFj-v8OUKkL6rgbWNkmr20hraBiE2a>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvfedrudduledgfeeiucetufdoteggodetrfdotf
 fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
 uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne
 cujfgurhepfffhvfevuffkfhggtggujgesghdtreertddtvdenucfhrhhomheprfgvthgv
 rhcuvfhougguuceophgvthgvsehpvghtvghrthhouggurdhorhhgqeenucggtffrrghtth
 gvrhhnpeelvdellefftddukeduffejgfefjeeuheeileeftdfgteduteeggeevueethfej
 tdenucffohhmrghinhepphgvthgvrhhtohguugdrohhrghenucevlhhushhtvghrufhiii
 gvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehushgvrhesphgvthgvrhhtohguugdr
 ohhrgh
X-ME-Proxy: <xmx:Dm2oYnE5-QJJHWfGL0zob8KXM0K4bg-sZac0Byqkd5-rMACbEu_ubg>
 <xmx:Dm2oYnW_KFzQ54SawIfD1cjcqDJyHi37ob-BZYuS7g1bdrFI2tG7hw>
 <xmx:Dm2oYiM_H1C2zHF5uAdSlHJElQ28i4ceQvyL3XMflZxSRGbELF1VPQ>
 <xmx:Dm2oYkhm3kNOuuGgNq-4lAsBuV4Zk-vVddF4es3q7CnUr2Yg8hvxAA>
Feedback-ID: i525146e8:Fastmail
Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue,
 14 Jun 2022 07:12:14 -0400 (EDT)
Received: by localhost (Postfix, from userid 1000)
 id 1581520D53; Tue, 14 Jun 2022 07:12:14 -0400 (EDT)
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Jun 2022 11:12:20 -0000


--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--