Date: Wed, 22 Jun 2016 07:10:09 -0400
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20160622111009.GA10956@fedora-21-dvm>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="J2SCkAp4GZ/dPZZf"
Content-Disposition: inline
User-Agent: Mutt/1.5.23 (2014-03-12)
Subject: [bitcoin-dev] Closed Seal Sets and Truth Lists for Better Privacy
 and Censorship Resistance
Precedence: list


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

At the recent coredev.tech meetup in Zurich I spent much of my time discuss=
ing
anti-censorship improvements with Adam Back, building on his idea of blind
symmetric commitments[^bsc], and my own ideas of client-side verification. =
Our
goal here is to combat censorship by ensuring that miners do not have the
information needed to selectively censor (blacklist) transactions, forcing =
them
to adopt a whitelist approach of allowed transactions if they choose to cen=
sor.

Back's work achieves that by changing the protocol such that users commit to
their transaction in advance, in such a way that the commitment doesn't con=
tain
the information necessary to censor the transaction, although after commitm=
ent
all transactional information becomes available. Here we propose a similar
scheme with using "smart contract" state machine tooling, with the potential
for an even better Zerocash-like guarantee that only a subset of data ever
becomes public, without requiring "moon math" of uncertain security.


# The Closed Seal Maps

To implement Single-Use Seals we propose that miners attest to the contents=
 of
a series of key:value maps of true expressions, with the keys being the
expressions, and the values being commitments, which along with (discardabl=
e)
witnesses make up the argument to the expression. Once an expression is add=
ed
to the closed seal map, the value associated with it can't be changed.

Periodically - perhaps once a year - the most recent map is archived, and t=
he
map is started fresh again. Once archived a closed seal map is never change=
d.
Miners are expected to keep the contents of the current map, as well as the
most recent closed seal map - the contents of older maps are proven on dema=
nd
using techniques similar to TXO commitments.

A single-use seal[^sma] implemented with the closed seal maps is then
identified by the expression and a block height. The seal is open if the
expression does not exist in any closed seal maps between the creation block
height and the most recent block height. A witness to the fact that the seal
has been closed is then a proof that the seal was recorded as closed in one=
 of
the closed seal maps, and (if needed) proof that the seal was still open in=
 any
prior maps between its creation and closing.

Similar to the logic in Bitcoin's segregated witnesses proposal, separating=
 the
commitment and witness arguments to the seal expression ensures that the
witness attesting to the fact that a given seal was closed does not depend =
on
the exact signature used to actually close it.

Here's a very simple example of such a seal expression, in the author's
Dex[^dex] expression language, for an application that can avoid reusing
pubkeys:

     (checksig <pubkey> <sig> (hash <committed-value>))

This desugars to the following after all named arguments were replaced by
explicit destructuring of the expression argument, denoted by the arg symbo=
l:

    (and <nonce>
         (checksig <pubkey> (cdr arg) (digest (car arg))))

The arguments to the expression are the closed seal map's commitment and
witness, which are our committed value and signature respectively:

    (<committed-value> . <sig>)


## The Truth List

We implement an expression validity oracle by having miners attest to the
validity of a perpetually growing list of true predicate expressions, whose
evaluation can in turn depend on depend on previously attested expressions =
in
the truth list. SPV clients who trust miners can use the truth list to skip
validation of old history.

Similar to TXO commitments, we expect miners to have a copy of recent entri=
es
in the truth list, perhaps the previous year. Older history can be proven o=
n an
as-needed basis. Unlike TXO commitments, since this is a pure list of valid
expressions, once an item is added to the list it is never modified.

As the truth list can include expressions that reference previously
evaluated expressions, expressions of arbitrary depth can be evaluated. For
example, suppose we have an extremely long linked list of numbers, represen=
ted
as the following sexpr:

    (i_n i_n-1 i_n-2 ... i_1 i_0)

We want to check that every number in the list is even:

    (defun all-even? (l)
        (match l
            (nil true)
            ((n . rest) (if (mod n 2)
                            false
                            (all-even? rest)))))

In any real system this will fail for a sufficiently long list, either due =
to
stack overflow, or (if tail recursion is supported) due to exceeding the
anti-DoS limits on cycles executed in one expression; expressing the above =
may
even be impossible in expression systems that don't allow unbounded recursi=
on.

A more subtle issue is that in a merkelized expression language, an express=
ion
that calls itself is impossible to directly represent: doing so creates a c=
ycle
in the call graph, which isn't possible without breaking the hash function.=
 So
instead we'll define the special symbol self, which triggers a lookup in the
truth map instead of actually evaluating directly. Now our expression is:

    (defun all-even? (l)
        (match l
            (nil true)
            ((n . rest) (if (mod n 2)
                            false
                            (self rest)))))

We evaluate it in parts, starting with the end of the list. The truth list =
only
attests to valid expressions - not arguments - so we curry the argument to =
form
the following expression:

    (all-even? nil)

The second thing that is appended to the truth list is:

    (all-even? (0 . #<digest of "nil">))

Note how we haven't actually provided the cdr of the cons cell - it's been
pruned and replaced by the digest of nil. With an additional bit of metadat=
a -
the index of that expression within the trust list, and possibly a merkle p=
ath
to the tip if the expression has been archived - we can show that the
expression has been previously evaluated and is true.

Subsequent expressions follow the same pattern:

    (all-even? (1 . #<digest of "(0)">))

Until finally we reach the last item:

    (all-even? (n_i . #<digest of "(n_i-1 n_i-2 ... 1 0)">))

Now we can show anyone who trusts that the truth list is valid - like a SPV
client - that evaluating all-even? on that list returns true by extracting a
merkle path from that item to the tip of the list's MMR commitment.


# Transactions

When we spend an output our goal is to direct the funds spent to a set of
outputs by irrovocably committing single-use seals to that distribution of
outputs. Equally, to validate an output we must show that sufficient funds =
have
been directed assigned to it. However, our anti-censorship goals make this
difficult, as we'll often want to reveal some information about where funds
being spend are going immediately - say to pay fees - while delaying when o=
ther
information is revealed as long as possible.

To achieve this we generalize the idea of a transaction slightly. Rather th=
an
simply having a set of inputs spent and outputs created, we have a set of
_input splits_ spent, and outputs created. An input split is then a merkle-=
sum
map of nonces:values that the particular input has been split into; the
transaction commits to a specific nonce within that split, and is only vali=
d if
the seal for that input is closed over a split actually committing to the
transaction.

Secondly, in a transaction with multiple outputs, we don't want it to be
immediately possible to link outputs together as seals associated with them=
 are
closed, even if the transaction ID is known publicly. So we associate each
output with a unique nonce.

Thus we can uniquely identify a specific transaction output - an outpoint -=
 by
the following data (remember that the tx would usually be pruned, leaving j=
ust
the digest):

    (struct outpoint
        (tx     :transaction)
        (nonce  :digest))

An transaction output is defined as:

    (struct txout
        (value     :int)    ; value of output
        (nonce     :digest)
        (authexpr  :func))  ; authorization expression

An input:

    (struct txin
        (prevout :outpoint) ; authorization expression
        (split   :digest)   ; split nonce
        (value   :int))     ; claimed value of output spent

And a transaction:

    (struct transaction
        ; fixme: need to define functions to extract sums and keys
        (inputs   :(merkle-sum-map  (:digest :txin))
        (outputs  :(merkle-sum-map  (:digest :txout))
        ; and probably more metadata here)


## Spending Outputs

Our single-use seal associated with a specific output is the expression:

    (<auth expr> <outpoint> . arg)

When the seal is closed it commits to the merkle-sum split map, which is
indexed by split nonces, one per (tx, value) pair committed to.  This means
that in the general case of an spend authorization expression that just che=
cks
a signature, the actual outpoint can be pruned and what actually gets publi=
shed
in the closed seal set is just:

    (<auth expr> #<digest of <outpoint>> . arg)

Along with the commitment:

    #<digest of split map>

With the relevant data hidden behind opaque digests, protected from
brute-forcing by nonces, external observers have no information about what
transaction output was spent, or anything about the transaction spending th=
at
output. The nonce in the seal commitment prevents that multiple spends for =
the
same transaction from being linked together.  Yet at the same time, we're s=
till
able to write a special-purpose spend auth expressions that do inspect the
contents of the transaction if needed.


## Validating Transactions

When validating a transaction, we want to validate the least amount of data
possible, allowing the maximum amount of data to be omitted for a given
recipient. Thus when we validate a transaction we _don't_ validate the outp=
uts;
we only validate that the inputs spent by the transaction are valid, and the
sum of (split) inputs spent is correct. We only need to validate outputs wh=
en
they're spent - until then an invalid output is of no relevance. We also do=
n't
need to validate any outputs other than the ones we're trying to spend - the
merkle sum tree guarantees that regardless of what's going on with other
outputs, the funds we're spending are uniquely allocated to us.

This means our function to check that a transaction is valid won't check the
outputs of the transaction itself, but will check outputs of previous
transactions:

    (defun valid-tx? (tx)
        (map-reduce tx.inputs
            (lambda (txin)
                (and <input is valid>
                     <witness is valid>
                     <split is valid>
                     (valid-output? txin.prevout)))))


# Censorship Resistant Usage

To make use of the separation between seal closure and validation we need to
pass transaction information from peer to peer. Let's look at what happens =
when
Alice pays Bob:

1. Alice picks one or more inputs to spend.

2. For each input she constructs a split, paying part of the funds to a
per-input fee transaction with no outputs, and committing part of the funds=
 to
the transaction paying Bob. If she has change left over she'll construct a
third transaction with just that change as an input.

3. She signs each input, creating valid signatures for the corresponding
output's seal's authorization expression.

4. She broadcasts the subset of data corresponding to just the fee paying
transactions and related signatures individually, with a time delay between
each one. All other data is pruned, leaving just opaque digests.

5. Once all inputs are confirmed, she gives Bob the data corresponding to h=
is
transaction, including the relevant parts of the merkle trees, and relevant
closed seal witnesses.

At this point, a whole bunch of seals have been closed, but there's absolut=
ely
nothing on chain that links them together. Now let's suppose Bob pays Charl=
ie,
using the funds Alice gave him, and a different input to pay mining fees:

1. Bob constructs a fee paying transaction, splitting some funds from a
previously revealed output, and depending on the seal for the output Alice =
gave
him, but without spending any of that output's funds.

2. Bob broadcasts the above publicly. Miners have to add both seals to the
closed seal set to collect the fees.

3. Once confirmed, Bob gives Charlie the corresponding transaction informat=
ion
for his output, as well as the still-private information it depends on to p=
rove
that the output Alice created for Bob is itself valid.

Again, nearly none of the information related to the transaction is public,=
 yet
the funds have moved twice.


## Pruning Old History

Over time the proofs that a coin is valid will grow as each additional
transaction adds more data. We shorten these proofs by publishing some of t=
he
data in the form of additions to the truth list of valid expressions,
specifically the is-valid-tx? expressions that determine whether or not a
transaction (and prior transactions) are valid. This allows SPV clients who
trust miners to stop validating once they reach that old history.

Secondly, with transaction history linearization[^sma] we can avoid ever
revealing most of the transaction data, greatly improving privacy. Only one
input per transaction needs to be proven, so all data related to other inpu=
ts
can be discarded permanently; in practice this will lead to either one or t=
wo
public inputs, including the input made public to pay mining fees.


# "Smart Contracts"

Privacy aside, the combination of single-use seal and true expressions list
enables all known "smart contract" applications, such as the ones Ethereum
currently targets. After all, the accounts-based Ethereum architecture can
always be simulated with a series of single-use seal's that explicitly keeps
track of of an account balance based on actions taken.


# Open Questions

1. How does the above architecture interact with scaling proposals, like
sharding? Fraud proofs?

2. How does the statistical inflation protection of transaction history
linearization work in a real economy, e.g. if people use it gamble with the=
ir
funds?

3. PoW isn't a perfect random beacon; how do we take that into account when
designing linearization?

4. How do wallets pass proof data between each other, e.g. offline?

5. How do wallets backup proof data? (similar problem that Lightning has)


# References

[^bsc]: "blind symmetric commitment for stronger byzantine voting resilienc=
e",
        Adam Back, May 15th 2013, bitcoin-dev mailing list,
        https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-May/00=
2600.html

[^sma]: "Building Blocks of the State Machine Approach to Consensus",
        Peter Todd, Jun 20th 2016,
        https://petertodd.org/2016/state-machine-consensus-building-blocks
        https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/0=
12773.html

[^dex]: "Dex: Deterministic Predicate Expressions for Smarter Signatures",
        Peter Todd, May 25th 2016,
        https://github.com/WebOfTrustInfo/ID2020DesignWorkshop/blob/master/=
topics-and-advance-readings/DexPredicatesForSmarterSigs.md

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

--J2SCkAp4GZ/dPZZf
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

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

iQEcBAEBCAAGBQJXanIOAAoJEGOZARBE6K+ytWkH/1yGxUt2RdAULF4PyFAe/Scf
5dmM+CGWz7kQQCihdfZ5lChYdJXXu49Q6yVBSc31UvmNG98Q1bO5bH0y589Emvyc
Cn40XKLKENRTikNL21wnldPfZTj2Cpio0A+JeN7uV0ziCJutpvzW6zrTopyxwoHa
fMy9f9D/n9hZe8fz8EIxq9WLziFA5PHkjh2kM/iyj+kROaZrcwcPkHuerAOjivnI
V8jQFhEk+9R3zHajg9RZ07vUAtqusPljRYa5DBy6oAI7h0UrCkHsulAh/cIUiQ3Y
K32ia1a/PpJNBaugbwVTlzYQmamwOzesFw2WVQxWY+rrpb2l9txrFl3xkiEDVsU=
=CnTr
-----END PGP SIGNATURE-----

--J2SCkAp4GZ/dPZZf--