path: root/7b/124c23a50e1023b70522cdc3316f5caae46fda

Return-Path: <jeremy.l.rubin@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 69FB5C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 14 Sep 2022 18:32:13 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 30D9660D6C
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 14 Sep 2022 18:32:13 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 30D9660D6C
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=DAA25KjN
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 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, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 Op1U2kw7Hms1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 14 Sep 2022 18:32:10 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 1257C60C0A
Received: from mail-yw1-x1134.google.com (mail-yw1-x1134.google.com
 [IPv6:2607:f8b0:4864:20::1134])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 1257C60C0A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 14 Sep 2022 18:32:10 +0000 (UTC)
Received: by mail-yw1-x1134.google.com with SMTP id
 00721157ae682-3450990b0aeso191013747b3.12
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 14 Sep 2022 11:32:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=to:subject:message-id:date:from:mime-version:from:to:cc:subject
 :date; bh=8Q+B74+orACw28jXFt2CY6lo4QcklS5PBpmyUjGcYhk=;
 b=DAA25KjNC/FVZVk537XqB+MQ9NvM7VbrXCQmjYjD2tfa9wwRuZMasgIjGb3ndVUuad
 GfWEyRoHkQNnmbPSPf/Nl1k5+ADRPEyFMxvKHgozMj2URdC6u+FfogYRyHQieGhpKGvt
 nZa2G1Wd0PPRqMaVauNwjfjJ/tUiO/kCj+5V6xxWR2PFQPKb00tlGMtNyXylwPRW9gqQ
 U6eFWRNM2LjHcOmBIdF5m8ffxU+TiJEpXTQwTMXApZw7Wj0o8P8faa90L5gTUf9j2bHf
 g7FVUmlL8edbu1YLZqX5PzbsROEqOcersS+dStS8FWFL2H6nk2UCckIop8GWNxOEZQmP
 esgA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=to:subject:message-id:date:from:mime-version:x-gm-message-state
 :from:to:cc:subject:date;
 bh=8Q+B74+orACw28jXFt2CY6lo4QcklS5PBpmyUjGcYhk=;
 b=VvslCmDG7j20WrBkTUk4yuQM246aH7shRIaDjwH1ogPIuEFtJKVlX3w8S0oUjQMkzN
 QvuI5HFifvcBghZ10lMvtpZoags8bSOeSkdDPRJoqb4xkeeX61y4GNBQQEcH/V8MV793
 J+5lXTITpNyaGwhObegBW89jEZI17mu5IfcgD+IwsXLP5+1ozFvMUbLSg7qP1d2pb7hr
 snA+8rJnKaWR1AktEMDU6oR3mFAJx09zLe2R7S/TmDIu5x3cSxO5+Nw/ddo2xqWN46Ej
 fS8yP6Mutv6Aia9iTyv/DW8wNpdSMPYfkrdRXLvcRf2m3pqNkwsvMKYU8Gq9lMTGOh42
 swNw==
X-Gm-Message-State: ACgBeo227T2Ywo8QAeo0Gd7tPoo6vBDvWzqDiYp3VV920xyCn1bfcepk
 OHN7k8m3/pIV9tYfiz4rnNqNeoYGcn+RTXigJd7PjtWVSyQ=
X-Google-Smtp-Source: AA6agR7ZzArvRxW7IA62r8msawAc3dN4rkZJFyVH1X9SnXuYMS4uCAeQ1s8ImYQGbS5DTKAm+nfQxHNA/lZfRmQK5+k=
X-Received: by 2002:a81:10c3:0:b0:349:8b81:9fb0 with SMTP id
 186-20020a8110c3000000b003498b819fb0mr7735833ywq.269.1663180327504; Wed, 14
 Sep 2022 11:32:07 -0700 (PDT)
MIME-Version: 1.0
From: Jeremy Rubin <jeremy.l.rubin@gmail.com>
Date: Wed, 14 Sep 2022 11:31:55 -0700
Message-ID: <CAD5xwhgKGMx79+RLpb-hjd3Gc=EKxTVzkpME-=KuM_C5+d7mRQ@mail.gmail.com>
To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000009e509e05e8a75803"
Subject: [bitcoin-dev] Spookchains: Drivechain Analog with One-Time Trusted
	Setup & APO
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: Wed, 14 Sep 2022 18:32:13 -0000

--0000000000009e509e05e8a75803
Content-Type: text/plain; charset="UTF-8"

*also available here on my blog with nicer
formatting: https://rubin.io/bitcoin/2022/09/14/drivechain-apo/
<https://rubin.io/bitcoin/2022/09/14/drivechain-apo/>*

This post draws heavily from Zmnscpxj's fantastic post showing how to
make drivechains with recursive covenants. In this post, I will show
similar tricks that can accomplish something similar using ANYPREVOUT
with a one time trusted setup ceremony.

This post presents general techniques that could be applied to many
different types of covenant.

# Peano Counters

The first component we need to build is a Peano counter graph. Instead
of using sha-256, like in Zmnscpxj's scheme, we will use a key and
build a simple 1 to 5 counter that has inc / dec.

Assume a key K1...K5, and a point NUMS which is e.g.
HashToCurve("Spookchains").

Generate scripts as follows:

```
<1 || K1> CHECKSIG
...
<1 || K5> CHECKSIG
```

Now generate 2 signatures under Ki with flags `SIGHASH_SINGLE |
SIGHASH_ANYONECANPAY | SIGHASH_ANYPREVOUT`.


## Rule Increment
For each Ki, when `i < 5`, create a signature that covers a
transaction described as:

```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K{i+1}> CHECKSIG})
```

## Rule Decrement
For each Ki, when `i > 1` The second signature should cover:
```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K{i-1}> CHECKSIG})
```



_Are these really Peano?_ Sort of. While a traditional Peano numeral
is defined as a structural type, e.g. `Succ(Succ(Zero))`, here we
define them via a Inc / Dec transaction operator, and we have to
explicitly bound these Peano numbers since we need a unique key per
element. They're at least spiritually similar.

## Instantiation
Publish a booklet of all the signatures for the Increment and
Decrement rules.

Honest parties should destroy the secret key sets `k`.


To create a counter, simply spend to output C:

```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K1> CHECKSIG})
```


The signature from K1 can be bound to C to 'transition' it to (+1):

```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K2> CHECKSIG})
```

Which can then transition to (+1):

```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K3> CHECKSIG})
```

Which can then transition (-1) to:

```
Amount: 1 satoshi
Key: Tr(NUMS, {<1 || K2> CHECKSIG})
```

This can repeat indefinitely.


We can generalize this technique from `1...5` to `1...N`.



# Handling Arbitrary Deposits / Withdrawals


One issue with the design presented previously is that it does not
handle arbitrary deposits well.

One simple way to handle this is to instantiate the protocol for every
amount you'd like to support.

This is not particularly efficient and requires a lot of storage
space.

Alternatively, divide (using base 2 or another base) the deposit
amount into a counter utxo per bit.

For each bit, instead of creating outputs with 1 satoshi, create
outputs with 2^i satoshis.

Instead of using keys `K1...KN`, create keys `K^i_j`, where i
represents the number of sats, and j represents the counter. Multiple
keys are required per amount otherwise the signatures would be valid
for burning funds.

## Splitting and Joining

For each `K^i_j`, it may also be desirable to allow splitting or
joining.

Splitting can be accomplished by pre-signing, for every `K^i_j`, where
`i!=0`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`:

```
Input: 2^i sats with key K^i_j
Outputs:
    - 2^i-1 sats to key K^{i-1}_j
    - 2^i-1 sats to key K^{i-1}_j
```

Joining can be accomplished by pre-signing, for every `K^i_j`, where
`i!=MAX`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`:

```
Inputs:
    - 2^i sats with key K^i_j
    - 2^i sats with key K^i_j
Outputs:
    - 2^i+1 sats to key K^{i+1}_j
```

N.B.: Joining allows for third parties to deposit money in externally,
that is not a part of the covenant.


The splitting and joining behavior means that spookchain operators
would be empowered to consolidate UTXOs to a smaller number, while
allowing arbitrary deposits.


# One Vote Per Block

To enforce that only one vote per block mined is allowed, ensure that
all signatures set the input sequence to 1 block. No CSV is required
because nSequence is in the signatures already.

# Terminal States / Thresholds

When a counter reaches the Nth state, it represents a certain amount
of accumulated work over a period where progress was agreed on for
some outcome.

There should be some viable state transition at this point.

One solution would be to have the money at this point sent to an
`OP_TRUE` output, which the miner incrementing that state is
responsible for following the rules of the spookchain. Or, it could be
specified to be some administrator key / federation for convenience,
with a N block timeout that degrades it to fewer signers (eventually
0) if the federation is dead to allow recovery.

This would look like, from any `K^i_j`, a signature for a transaction
putting it into an `OP_TRUE` and immediately spending it. Other
spookchain miners would be expected to orphan that miner otherwise.


# Open States / Proposals

From a state `K^i_1`, the transaction transitioning to `K^i_2` can be
treated as 'special' and the `OP_RETURN` output type can be used to
commit to, e.g., the outputs that must be created in when the Terminal
State is reached. This clarifies the issue of "what is being voted
on".

This method does not *lock in* at a consensus layer what Terminal
State is being voted on.

In certain circumstances, without violating the one-time-setup
constraint, if a fixed list of withdrawer's addresses is known in
advance, the Open States could cover withdrawals to specific
participants, which then must collect a certain number of votes from
miners.  However, it seems impossible, without new primitives, for an
arbitrary transaction proposal to be voted on.

# Setup Variants

## xpubs

Instead of using randomly generated keys for each state, define each
to be an xpub and derive a path where it is k/i/j for each
state/satoshi amount. This saves some data, and also requires less
entropy.

### Trustless Data Commit:

commit to the hash of the entire program spec as a tweak to the xpub,
so that someone can quickly verify if they have all the signatures you
are expected to generate if honest.

One way to do this is to convert a hash to a list of HD Child Numbers
(9 of them) deterministically, and tweak the xpub by that. This is a
convenient, yet inefficient, way to tweak an xpub because the child
has a normal derivation path for signing devices.

## Single Party

A single party pre-signs all the transactions for the spookchain, and
then deletes their xpriv.

You trust them to have deleted the key, and signed properly, but you
do not trust whoever served you the spookchain blob to have given you
all the state transitions because of the trustless data commitment.

## MuSig Multi-Party

Define a MuSig among all participants in the setup ceremony, N-of-N.

Now you simply trust that any one person in the one-time-setup was
honest! Very good.

## Unaggregated Multi-Party


Allow for unaggregated multi-sig keys in the spec. This grows with
O(signers), however, it means that a-la-carte you can aggregate setups
from random participants who never interacted / performed setup
ceremonies independently if they signed the same specs.

Can also combine multiple MuSig Multi-Parties in this way.

This is nice because MuSig inherently implies the parties colluded at
one point to do a MuSig setup, whereas unaggregated multi-sig could be
performed with no connectivity between parties.

## Soft Forking Away Trust

Suppose a spookchain becomes popular. You could configure your client
to reject invalid state transitions, or restrict the spookchain keys
to only sign with the known signatures. This soft fork would smoothly
upgrade the trust assumption.

## Symmetry of State Transition Rules & DAG Covenants

We could have our increment state transitions be done via a trustless
covenant, and our backwards state transitions be done via the setup.

This would look something like the following for state i:

```
Tr(NUMS, {
    `<sig for state K_{i+1}> <1 || PK_nonsecret> CHECKSIG`,
    `<1 || Ki> CHECKSIG`
})
```

The advantage of such an optimization is theoretically nice because it
means that *only* the non-destructuring recursive part of the
computation is subject to the one-time-setup trust assumption, which
might be of use in various other protocols, where recursivity might
only be unlocked e.g. after a timeout (but for spookchains it is used
at each step).

A compiler writer might perform this task by starting with an
arbitrary abstract graph, and then removing edges selectively (a
number of heuristics may make sense, e.g., to minimize reliance on
one-time-setup or minimize costs) until the graph is a Directed
Acyclic Graph, consisting of one or more components, compiling those
with committed covenants, and then adding the removed edges back using
the one-time-setup key materials.


# Commentary on Trust and Covenantiness

Is this a covenant? I would say "yes". When I defined covenants in my
_Calculus of Covenants_ post, it was with a particular set of
assumptions per covenant.

Under that model, you could, e.g., call a 7-10 multi-sig with specific
committed instructions as 4-10 honest (requires 4 signatories to be
honest to do invalid state transition) and 4-10 killable (requires 4
signatories to die to have no way of recovering).

For emulations that are pre-signed, like the varieties used to emulate
CTV, it is a different model because if your program is correct and
you've pre-gotten the signatures for N-N it is 1-N honest (only 1
party must be honest to prevent an invalid state transition) and
unkillable (all parties can safely delete keys).

I model these types of assumptions around liveness and honesty as
different 'complexity classes' than one another.

What I would point out is that with the counter model presented above,
this is entirely a pre-signed 1-N honest and unkillable covenant that
requires no liveness from signers. Further, with APO, new instances of
the covenant do not require a new set of signers, the setup is truly
one-time. Therefore this type of covenant exists in an even lower
trust-complexity class than CTV emulation via presigneds, which
requires a new federation to sign off on each contract instance.


With that preface, let us analyze this covenant:


1) A set of sets of transaction intents (a family), potentially
recursive or co-recursive (e.g., the types of state transitions that
can be generated).  These intents can also be represented by a
language that generates the transactions, rather than the literal
transactions themselves. We do the family rather than just sets at
this level because to instantiate a covenant we must pick a member of
the family to use.


The set of sets of transaction intents is to increment / decrement to
a successor or predecessor, or to halve into two instances or double
value by adding funds. Each successor or predecessor is the same type
of covenant, with the excetion of the first and last, which have some
special rules.


2) A verifier generator function that generates a function that
accepts an intent that is any element of one member of the family of
intents and a proof for it and rejects others.

The verifier generator is the simple APO CHECKSIG script.

3) A prover generator function that generates a function that takes an
intent that is any element of one member of the family and some extra
data and returns either a new prover function, a finished proof, or a
rejection (if not a valid intent).

The prover generator is the selection of the correct signature from a
table for a given script.

Run the prover generator with the private keys present *once* to
initialize over all reachable states, and cache the signatures, then
the keys may be deleted for future runs.

4) A set of proofs that the Prover, Verifier, and a set of intents are
"impedance matched", that is, all statements the prover can prove and
all statements the verifier can verify are one-to-one and onto (or
something similar), and that this also is one-to-one and onto with one
element of the intents (a set of transactions) and no other.

At a given key state the only things that may happen are signed
transactions, no other data is interpreted off of the stack. Therefore
there is perfect impedance match.


5) A set of assumptions under which the covenant is verified (e.g., a
multi-sig covenant with at least 1-n honesty, a multisig covenant with
any 3-n honesty required, Sha256 collision resistance, Discrete Log
Hardness, a SGX module being correct).

Uniquely, that during the setup phase at least one of the keys
were faithfully deleted.

The usual suspects for any bitcoin transaction are also assumed for
security.


6) Composability:

The Terminal State can pay out into a pre-specified covenant if
desired from any other family of covenants.
--
@JeremyRubin <https://twitter.com/JeremyRubin>

--0000000000009e509e05e8a75803
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000"><b><span style=3D"font-fa=
mily:Arial,Helvetica,sans-serif;color:rgb(34,34,34)">also available here on=
 my blog with nicer formatting:=C2=A0</span><span style=3D"font-family:Aria=
l,Helvetica,sans-serif;color:rgb(34,34,34)"><a href=3D"https://rubin.io/bit=
coin/2022/09/14/drivechain-apo/">https://rubin.io/bitcoin/2022/09/14/drivec=
hain-apo/</a></span></b></div><div class=3D"gmail_default" style=3D"font-fa=
mily:arial,helvetica,sans-serif;font-size:small;color:#000000"><span style=
=3D"font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)"><br></span>=
</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san=
s-serif;font-size:small;color:#000000"><span style=3D"font-family:Arial,Hel=
vetica,sans-serif;color:rgb(34,34,34)">This post draws heavily from Zmnscpx=
j&#39;s fantastic post showing how to</span><br></div>make drivechains with=
 recursive covenants. In this post, I will show<br>similar tricks that can =
accomplish something similar using ANYPREVOUT<br>with a one time trusted se=
tup ceremony.<br><br>This post presents general techniques that could be ap=
plied to many<br>different types of covenant.<br><br># Peano Counters<br><b=
r>The first component we need to build is a Peano counter graph. Instead<br=
>of using sha-256, like in Zmnscpxj&#39;s scheme, we will use a key and<br>=
build a simple 1 to 5 counter that has inc / dec.<br><br>Assume a key K1...=
K5, and a point NUMS which is e.g.<br>HashToCurve(&quot;Spookchains&quot;).=
<br><br>Generate scripts as follows:<br><br>```<br>&lt;1 || K1&gt; CHECKSIG=
<br>...<br>&lt;1 || K5&gt; CHECKSIG<br>```<br><br>Now generate 2 signatures=
 under Ki with flags `SIGHASH_SINGLE |<br>SIGHASH_ANYONECANPAY | SIGHASH_AN=
YPREVOUT`.<br><br><br>## Rule Increment<br>For each Ki, when `i &lt; 5`, cr=
eate a signature that covers a<br>transaction described as:<br><br>```<br>A=
mount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K{i+1}&gt; CHECKSIG})<br>```<br=
><br>## Rule Decrement<br>For each Ki, when `i &gt; 1` The second signature=
 should cover:<br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K{i-1=
}&gt; CHECKSIG})<br>```<br><br><br><br>_Are these really Peano?_ Sort of. W=
hile a traditional Peano numeral<br>is defined as a structural type, e.g. `=
Succ(Succ(Zero))`, here we<br>define them via a Inc / Dec transaction opera=
tor, and we have to<br>explicitly bound these Peano numbers since we need a=
 unique key per<br>element. They&#39;re at least spiritually similar.<br><b=
r>## Instantiation<br>Publish a booklet of all the signatures for the Incre=
ment and<br>Decrement rules.<br><br>Honest parties should destroy the secre=
t key sets `k`.<br><br><br>To create a counter, simply spend to output C:<b=
r><br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K1&gt; CHECKSIG})=
<br>```<br><br><br>The signature from K1 can be bound to C to &#39;transiti=
on&#39; it to (+1):<br><br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1=
 || K2&gt; CHECKSIG})<br>```<br><br>Which can then transition to (+1):<br><=
br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K3&gt; CHECKSIG})<br=
>```<br><br>Which can then transition (-1) to:<br><br>```<br>Amount: 1 sato=
shi<br>Key: Tr(NUMS, {&lt;1 || K2&gt; CHECKSIG})<br>```<br><br>This can rep=
eat indefinitely.<br><br><br>We can generalize this technique from `1...5` =
to `1...N`.<br><br><br><br># Handling Arbitrary Deposits / Withdrawals<br><=
br><br>One issue with the design presented previously is that it does not<b=
r>handle arbitrary deposits well.<br><br>One simple way to handle this is t=
o instantiate the protocol for every<br>amount you&#39;d like to support.<b=
r><br>This is not particularly efficient and requires a lot of storage<br>s=
pace.<br><br>Alternatively, divide (using base 2 or another base) the depos=
it<br>amount into a counter utxo per bit.<br><br>For each bit, instead of c=
reating outputs with 1 satoshi, create<br>outputs with 2^i satoshis.<br><br=
>Instead of using keys `K1...KN`, create keys `K^i_j`, where i<br>represent=
s the number of sats, and j represents the counter. Multiple<br>keys are re=
quired per amount otherwise the signatures would be valid<br>for burning fu=
nds.<br><br>## Splitting and Joining<br><br>For each `K^i_j`, it may also b=
e desirable to allow splitting or<br>joining.<br><br>Splitting can be accom=
plished by pre-signing, for every `K^i_j`, where<br>`i!=3D0`, with `SIGHASH=
_ALL | SIGHASH_ANYPREVOUT`:<br><br>```<br>Input: 2^i sats with key K^i_j<br=
>Outputs:<br>=C2=A0 =C2=A0 - 2^i-1 sats to key K^{i-1}_j<br>=C2=A0 =C2=A0 -=
 2^i-1 sats to key K^{i-1}_j<br>```<br><br>Joining can be accomplished by p=
re-signing, for every `K^i_j`, where<br>`i!=3DMAX`, with `SIGHASH_ALL | SIG=
HASH_ANYPREVOUT`:<br><br>```<br>Inputs:<br>=C2=A0 =C2=A0 - 2^i sats with ke=
y K^i_j<br>=C2=A0 =C2=A0 - 2^i sats with key K^i_j<br>Outputs:<br>=C2=A0 =
=C2=A0 - 2^i+1 sats to key K^{i+1}_j<br>```<br><br>N.B.: Joining allows for=
 third parties to deposit money in externally,<br>that is not a part of the=
 covenant.<br><br><br>The splitting and joining behavior means that spookch=
ain operators<br>would be empowered to consolidate UTXOs to a smaller numbe=
r, while<br>allowing arbitrary deposits.<br><br><br># One Vote Per Block<br=
><br>To enforce that only one vote per block mined is allowed, ensure that<=
br>all signatures set the input sequence to 1 block. No CSV is required<br>=
because nSequence is in the signatures already.<br><br># Terminal States / =
Thresholds<br><br>When a counter reaches the Nth state, it represents a cer=
tain amount<br>of accumulated work over a period where progress was agreed =
on for<br>some outcome.<br><br>There should be some viable state transition=
 at this point.<br><br>One solution would be to have the money at this poin=
t sent to an<br>`OP_TRUE` output, which the miner incrementing that state i=
s<br>responsible for following the rules of the spookchain. Or, it could be=
<br>specified to be some administrator key / federation for convenience,<br=
>with a N block timeout that degrades it to fewer signers (eventually<br>0)=
 if the federation is dead to allow recovery.<br><br>This would look like, =
from any `K^i_j`, a signature for a transaction<br>putting it into an `OP_T=
RUE` and immediately spending it. Other<br>spookchain miners would be expec=
ted to orphan that miner otherwise.<br><br><br># Open States / Proposals<br=
><br>From a state `K^i_1`, the transaction transitioning to `K^i_2` can be<=
br>treated as &#39;special&#39; and the `OP_RETURN` output type can be used=
 to<br>commit to, e.g., the outputs that must be created in when the Termin=
al<br>State is reached. This clarifies the issue of &quot;what is being vot=
ed<br>on&quot;.<br><br>This method does not *lock in* at a consensus layer =
what Terminal<br>State is being voted on.<br><br>In certain circumstances, =
without violating the one-time-setup<br>constraint, if a fixed list of with=
drawer&#39;s addresses is known in<br>advance, the Open States could cover =
withdrawals to specific<br>participants, which then must collect a certain =
number of votes from<br>miners.=C2=A0 However, it seems impossible, without=
 new primitives, for an<br>arbitrary transaction proposal to be voted on.<b=
r><br># Setup Variants<br><br>## xpubs<br><br>Instead of using randomly gen=
erated keys for each state, define each<br>to be an xpub and derive a path =
where it is k/i/j for each<br>state/satoshi amount. This saves some data, a=
nd also requires less<br>entropy.<br><br>### Trustless Data Commit:<br><br>=
commit to the hash of the entire program spec as a tweak to the xpub,<br>so=
 that someone can quickly verify if they have all the signatures you<br>are=
 expected to generate if honest.<br><br>One way to do this is to convert a =
hash to a list of HD Child Numbers<br>(9 of them) deterministically, and tw=
eak the xpub by that. This is a<br>convenient, yet inefficient, way to twea=
k an xpub because the child<br>has a normal derivation path for signing dev=
ices.<br><br>## Single Party<br><br>A single party pre-signs all the transa=
ctions for the spookchain, and<br>then deletes their xpriv.<br><br>You trus=
t them to have deleted the key, and signed properly, but you<br>do not trus=
t whoever served you the spookchain blob to have given you<br>all the state=
 transitions because of the trustless data commitment.<br><br>## MuSig Mult=
i-Party<br><br>Define a MuSig among all participants in the setup ceremony,=
 N-of-N.<br><br>Now you simply trust that any one person in the one-time-se=
tup was<br>honest! Very good.<br><br>## Unaggregated Multi-Party<br><br><br=
>Allow for unaggregated multi-sig keys in the spec. This grows with<br>O(si=
gners), however, it means that a-la-carte you can aggregate setups<br>from =
random participants who never interacted / performed setup<br>ceremonies in=
dependently if they signed the same specs.<br><br>Can also combine multiple=
 MuSig Multi-Parties in this way.<br><br>This is nice because MuSig inheren=
tly implies the parties colluded at<br>one point to do a MuSig setup, where=
as unaggregated multi-sig could be<br>performed with no connectivity betwee=
n parties.<br><br>## Soft Forking Away Trust<br><br>Suppose a spookchain be=
comes popular. You could configure your client<br>to reject invalid state t=
ransitions, or restrict the spookchain keys<br>to only sign with the known =
signatures. This soft fork would smoothly<br>upgrade the trust assumption.<=
br><br>## Symmetry of State Transition Rules &amp; DAG Covenants<br><br>We =
could have our increment state transitions be done via a trustless<br>coven=
ant, and our backwards state transitions be done via the setup.<br><br>This=
 would look something like the following for state i:<br><br>```<br>Tr(NUMS=
, {<br>=C2=A0 =C2=A0 `&lt;sig for state K_{i+1}&gt; &lt;1 || PK_nonsecret&g=
t; CHECKSIG`,<br>=C2=A0 =C2=A0 `&lt;1 || Ki&gt; CHECKSIG`<br>})<br>```<br><=
br>The advantage of such an optimization is theoretically nice because it<b=
r>means that *only* the non-destructuring recursive part of the<br>computat=
ion is subject to the one-time-setup trust assumption, which<br>might be of=
 use in various other protocols, where recursivity might<br>only be unlocke=
d e.g. after a timeout (but for spookchains it is used<br>at each step).<br=
><br>A compiler writer might perform this task by starting with an<br>arbit=
rary abstract graph, and then removing edges selectively (a<br>number of he=
uristics may make sense, e.g., to minimize reliance on<br>one-time-setup or=
 minimize costs) until the graph is a Directed<br>Acyclic Graph, consisting=
 of one or more components, compiling those<div>with committed covenants, a=
nd then<span class=3D"gmail_default" style=3D"font-family:arial,helvetica,s=
ans-serif;font-size:small;color:rgb(0,0,0)"> </span>adding the removed edge=
s back using</div><div>the one-time-setup key materials.<br><br><br># Comme=
ntary on Trust and Covenantiness<br><br>Is this a covenant? I would say &qu=
ot;yes&quot;. When I defined covenants in my<br>_Calculus of Covenants_ pos=
t, it was with a particular set of<br>assumptions per covenant.<br><br>Unde=
r that model, you could, e.g., call a 7-10 multi-sig with specific<br>commi=
tted instructions as 4-10 honest (requires 4 signatories to be<br>honest to=
 do invalid state transition) and 4-10 killable (requires 4<br>signatories =
to die to have no way of recovering).<br><br>For emulations that are pre-si=
gned, like the varieties used to emulate<br>CTV, it is a different model be=
cause if your program is correct and<br>you&#39;ve pre-gotten the signature=
s for N-N it is 1-N honest (only 1<br>party must be honest to prevent an in=
valid state transition) and<br>unkillable (all parties can safely delete ke=
ys).<br><br>I model these types of assumptions around liveness and honesty =
as<br>different &#39;complexity classes&#39; than one another.<br><br>What =
I would point out is that with the counter model presented above,<br>this i=
s entirely a pre-signed 1-N honest and unkillable covenant that<br>requires=
 no liveness from signers. Further, with APO, new instances of<br>the coven=
ant do not require a new set of signers, the setup is truly<br>one-time. Th=
erefore this type of covenant exists in an even lower<br>trust-complexity c=
lass than CTV emulation via presigneds, which<br>requires a new federation =
to sign off on each contract instance.<br><br><br>With that preface, let us=
 analyze this covenant:<br><br><br>1) A set of sets of transaction intents =
(a family), potentially<br>recursive or co-recursive (e.g., the types of st=
ate transitions that<br>can be generated).=C2=A0 These intents can also be =
represented by a<br>language that generates the transactions, rather than t=
he literal<br>transactions themselves. We do the family rather than just se=
ts at<br>this level because to instantiate a covenant we must pick a member=
 of<br>the family to use.<br><br><br>The set of sets of transaction intents=
 is to increment / decrement to<br>a successor or predecessor, or to halve =
into two instances or double<br>value by adding funds. Each successor or pr=
edecessor is the same type<br>of covenant, with the excetion of the first a=
nd last, which have some<br>special rules.<br><br><br>2) A verifier generat=
or function that generates a function that<br>accepts an intent that is any=
 element of one member of the family of<br>intents and a proof for it and r=
ejects others.<br><br>The verifier generator is the simple APO CHECKSIG scr=
ipt.<br><br>3) A prover generator function that generates a function that t=
akes an<br>intent that is any element of one member of the family and some =
extra<br>data and returns either a new prover function, a finished proof, o=
r a<br>rejection (if not a valid intent).<br><br>The prover generator is th=
e selection of the correct signature from a<br>table for a given script.<br=
><br>Run the prover generator with the private keys present *once* to<br>in=
itialize over all reachable states, and cache the signatures, then<br>the k=
eys may be deleted for future runs.<br><br>4) A set of proofs that the Prov=
er, Verifier, and a set of intents are<br>&quot;impedance matched&quot;, th=
at is, all statements the prover can prove and<br>all statements the verifi=
er can verify are one-to-one and onto (or<br>something similar), and that t=
his also is one-to-one and onto with one<br>element of the intents (a set o=
f transactions) and no other.<br><br>At a given key state the only things t=
hat may happen are signed<br>transactions, no other data is interpreted off=
 of the stack. Therefore<br>there is perfect impedance match.<br><br><br>5)=
 A set of assumptions under which the covenant is verified (e.g., a<br>mult=
i-sig covenant with at least 1-n honesty, a multisig covenant with<br>any 3=
-n honesty required, Sha256 collision resistance, Discrete Log<br>Hardness,=
 a SGX module being correct).<br><br>Uniquely, that during the setup phase =
at least one of the keys<br>were faithfully deleted.<br><br>The usual suspe=
cts for any bitcoin transaction are also assumed for<br>security.<br><br><b=
r>6) Composability:<br><br>The Terminal State can pay out into a pre-specif=
ied covenant if<br>desired from any other family of covenants.<br clear=3D"=
all"><div><div dir=3D"ltr" class=3D"gmail_signature" data-smartmail=3D"gmai=
l_signature"><div dir=3D"ltr">--<br><a href=3D"https://twitter.com/JeremyRu=
bin" target=3D"_blank">@JeremyRubin</a><br></div></div></div></div></div>

--0000000000009e509e05e8a75803--