Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id D980DC002D for ; Fri, 30 Sep 2022 02:00:47 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id AB75C61207 for ; Fri, 30 Sep 2022 02:00:47 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org AB75C61207 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=R5gnA5Jp 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 gBmDUHTxZdCE for ; Fri, 30 Sep 2022 02:00:45 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 3E40961206 Received: from mail-il1-x12a.google.com (mail-il1-x12a.google.com [IPv6:2607:f8b0:4864:20::12a]) by smtp3.osuosl.org (Postfix) with ESMTPS id 3E40961206 for ; Fri, 30 Sep 2022 02:00:43 +0000 (UTC) Received: by mail-il1-x12a.google.com with SMTP id i9so1329639ilv.9 for ; Thu, 29 Sep 2022 19:00:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date; bh=avcU9keNmwPPKOsRN69fD8Qcqmw0e8VYvM1gsnk/UKs=; b=R5gnA5JpcRqyiNPwDxc5nTMJCzyosw0HQNdqfk1sOfo3dpllKQG1JSI+Ye3HWPYmF8 CiYtCm/xdB/MKanijjs4qJD7sdwEAJF0IDBI3AMPXO6L06Tgh+u3fV/dVE+uBV+aBFZT kOw7u6RW97AAuBDXuykQZECgA4iIuJ/elz7Ffq0Kl4k0SrxH4T8QmWB18JWdYG3wHtn9 Si3cKgCtr1fnNBkiTT2107aOVFCd96YOeW2CUbXQ+spBUZ4bK4TR8xNxIHGnC+F96WNp slDiNVp9RgfO6V8qPb1dqtch4v9fGUSeDkcBX9PrGma3FRPC39C+AHpzOppDzNYKixG1 uB6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date; bh=avcU9keNmwPPKOsRN69fD8Qcqmw0e8VYvM1gsnk/UKs=; b=xh9Scr3Pn4axUBye4nAdASiFv26lmGKDuUCiw5oYjbkQEMUaf0kdTEr1yneoxfeqIb vS/Rht2HXbrzt14mo3EOguGX1MlL9YGhxnydpiJaalbr3+GZ6nLjDp+73/Qek1NnomFX rw5pNzrqdf/0TCzfq59S23z3B/k1xWxZ0yAUPRdvfyf1Kkx80mktLvkA8Pw3Ia6EqVEP /3z2gaYE4PF3hs/qkMCFqmpIixKSu4Xp5/g54R/EkxTMC+VROaFEZU6yidq+LFfsdiwC UjiuicmaUuxui/gThII4mSPe+6Ey2s5xeoBB6582vK0vWW6Cq7pbpxbIyCn3WLqpKfkI iH1Q== X-Gm-Message-State: ACrzQf1fj67Ha0XL+vnmetTIGsgFLl6e44RgLyjj+wGm/+PAvNXjBqTD RsofkwVzej383sBz8cSObnq15qV5Skr3USQwcDeIugjzsoEvmA== X-Google-Smtp-Source: AMsMyM4lw0S8cbupCFdIlDeLY1RQ4JBsOAvGYm4n3IjbDoeMDyp3gUTFAP3aRZUMgBWNvh60SxG7bgqchcPCGZhGxfw= X-Received: by 2002:a92:3652:0:b0:2df:4133:787 with SMTP id d18-20020a923652000000b002df41330787mr3188715ilf.39.1664503242260; Thu, 29 Sep 2022 19:00:42 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Thu, 29 Sep 2022 22:00:30 -0400 Message-ID: To: Jeremy Rubin , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000007b864205e9db5c7b" X-Mailman-Approved-At: Fri, 30 Sep 2022 02:18:09 +0000 Subject: Re: [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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 30 Sep 2022 02:00:48 -0000 --0000000000007b864205e9db5c7b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Jeremy, Thanks for bringing back to awareness covenant-based drivechain designs again! I'm not super familiar with the thousands shades of sidechains, and especially how the variants of pegging mechanisms influence the soundness of the game-theory backing up the functionaries execution. However it could be interesting to give security bounds to the defect of any trusted component, such as the one-time trusted setup, and the impacts on funds. If it's a full-blown loss, a timevalue loss, a privacy leak, etc... Started at least an entry for the ZmnSCPxj design: https://github.com/ariard/bitcoin-contracting-primitives-wg/pull/9 One interesting point from the OG post: > The recursive covenant could, with the help of `OP_CAT` and > `OP_CTV`, check that every transaction spending the UTXO has a > second output that is an `OP_RETURN` with a commitment to the > sidechain block. > We can ensure that only one such transaction exists in each > mainchain block by adding a `<1> OP_CSV`, ensuring that only one > sidechain-commitment transaction can occur on each mainchain > block. Such recursive-covenant "embedded" sidechains could be used as solution to the double-spend of payment pools and channel factories partitions, as an instantiation of a "on-chain authoritative board" for partitions statement, as described earlier this year, in a quest to solve the high interactivity issue affecting those constructions [0]. Best, Antoine [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020370.h= tml Le mer. 14 sept. 2022 =C3=A0 14:32, Jeremy Rubin via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit : > *also available here on my blog with nicer > formatting: 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!=3D0`, 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!=3DMAX`, 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, { > ` <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 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --0000000000007b864205e9db5c7b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Jeremy,

Thanks for bringing back to awareness co= venant-based drivechain designs again!

I'm not super familiar wi= th the thousands shades of sidechains, and especially how the variants of p= egging mechanisms influence the soundness of the game-theory backing up the= functionaries execution. However it could be interesting to give security = bounds to the defect of any trusted component, such as the one-time trusted= setup, and the impacts on funds. If it's a full-blown loss, a timevalu= e loss, a privacy leak, etc...

Started at least an entry for the Zmn= SCPxj design:
https://github.com/ariard/bitcoin-contracting-primitiv= es-wg/pull/9

One interesting point from the OG post:
> The= recursive covenant could, with the help of `OP_CAT` and
> `OP_CTV`, = check that every transaction spending the UTXO has a
> second output = that is an `OP_RETURN` with a commitment to the
> sidechain block.> We can ensure that only one such transaction exists in each
> m= ainchain block by adding a `<1> OP_CSV`, ensuring that only one
&g= t; sidechain-commitment transaction can occur on each mainchain
> blo= ck.

Such recursive-covenant "embedded" sidechains could be= used as solution to the double-spend of payment pools and channel factorie= s partitions, as an instantiation of a "on-chain authoritative board&q= uot; for partitions statement, as described earlier this year, in a quest t= o solve the high interactivity issue affecting those constructions [0].
=
Best,
Antoine

[0] https://lists.linuxfoundati= on.org/pipermail/bitcoin-dev/2022-April/020370.html

Le=C2=A0mer. 14 = sept. 2022 =C3=A0=C2=A014:32, Jeremy Rubin via bitcoin-dev <bitcoin-dev@lists.linuxfoundat= ion.org> a =C3=A9crit=C2=A0:
also available here on my blog with nicer formatting:=C2=A0= https://rubin.io/bitcoin/2022/09/14/drivechain-apo/

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

This po= st presents general techniques that could be applied to many
different t= ypes of covenant.

# Peano Counters

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

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

Generate scripts as = follows:

```
<1 || K1> CHECKSIG
...
<1 || K5> C= HECKSIG
```

Now generate 2 signatures under Ki with flags `SIGHAS= H_SINGLE |
SIGHASH_ANYONECANPAY | SIGHASH_ANYPREVOUT`.


## Rul= e 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
Fo= r each Ki, when `i > 1` The second signature should cover:
```
Amo= unt: 1 satoshi
Key: Tr(NUMS, {<1 || K{i-1}> CHECKSIG})
```
<= br>

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

## Instantiation
Publis= h a booklet of all the signatures for the Increment and
Decrement rules.=

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


T= o create a counter, simply spend to output C:

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


The signa= ture 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<= br>Key: Tr(NUMS, {<1 || K3> CHECKSIG})
```

Which can then t= ransition (-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 de= sign presented previously is that it does not
handle arbitrary deposits = well.

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

This is not particular= ly 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 satos= hi, 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 splitti= ng or
joining.

Splitting can be accomplished by pre-signing, for = every `K^i_j`, where
`i!=3D0`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`:<= br>
```
Input: 2^i sats with key K^i_j
Outputs:
=C2=A0 =C2=A0 -= 2^i-1 sats to key K^{i-1}_j
=C2=A0 =C2=A0 - 2^i-1 sats to key K^{i-1}_j=
```

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

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

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


The spli= tting and joining behavior means that spookchain operators
would be empo= wered 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 inpu= t sequence to 1 block. No CSV is required
because nSequence is in the si= gnatures already.

# Terminal States / Thresholds

When a count= er 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 sol= ution would be to have the money at this point sent to an
`OP_TRUE` outp= ut, which the miner incrementing that state is
responsible for following= the rules of the spookchain. Or, it could be
specified to be some admin= istrator key / federation for convenience,
with a N block timeout that d= egrades 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 other= wise.


# 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 ou= tputs that must be created in when the Terminal
State is reached. This c= larifies the issue of "what is being voted
on".

This me= thod does not *lock in* at a consensus layer what Terminal
State is bein= g voted on.

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

# Setup Variants

= ## xpubs

Instead of using randomly generated keys for each state, de= fine 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
entro= py.

### Trustless Data Commit:

commit to the hash of the enti= re program spec as a tweak to the xpub,
so that someone can quickly veri= fy if they have all the signatures you
are expected to generate if hones= t.

One way to do this is to convert a hash to a list of HD Child Num= bers
(9 of them) deterministically, and tweak the xpub by that. This is = a
convenient, yet inefficient, way to tweak an xpub because the childhas 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 spook= chain blob to have given you
all the state transitions because of the tr= ustless 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.<= br>
## 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 w= ay.

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

## Soft Fork= ing Away Trust

Suppose a spookchain becomes popular. You could confi= gure your client
to reject invalid state transitions, or restrict the sp= ookchain keys
to only sign with the known signatures. This soft fork wou= ld smoothly
upgrade the trust assumption.

## Symmetry of State Tr= ansition Rules & DAG Covenants

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

This would look something like the= following for state i:

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

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

A compiler writer might p= erform 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 gra= ph is a Directed
Acyclic Graph, consisting of one or more components, co= mpiling those
with committed covenants, and then adding the removed edges back using
the one= -time-setup key materials.


# Commentary on Trust and Covenantine= ss

Is this a covenant? I would say "yes". When I defined c= ovenants in my
_Calculus of Covenants_ post, it was with a particular se= t of
assumptions per covenant.

Under that model, you could, e.g.,= call a 7-10 multi-sig with specific
committed instructions as 4-10 hone= st (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 recov= ering).

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

I model these type= s of assumptions around liveness and honesty as
different 'complexit= y 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 ho= nest and unkillable covenant that
requires no liveness from signers. Fur= ther, with APO, new instances of
the covenant do not require a new set o= f signers, the setup is truly
one-time. Therefore this type of covenant = exists in an even lower
trust-complexity class than CTV emulation via pr= esigneds, which
requires a new federation to sign off on each contract i= nstance.


With that preface, let us analyze this covenant:

1) A set of sets of transaction intents (a family), potentially
rec= ursive or co-recursive (e.g., the types of state transitions that
can be= generated).=C2=A0 These intents can also be represented by a
language t= hat generates the transactions, rather than the literal
transactions the= mselves. 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.
<= br>
The set of sets of transaction intents is to increment / decrement t= o
a successor or predecessor, or to halve into two instances or doublevalue by adding funds. Each successor or predecessor is the same type
= of covenant, with the excetion of the first and last, which have some
sp= ecial rules.


2) A verifier generator function that generates a f= unction 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 veri= fier generator is the simple APO CHECKSIG script.

3) A prover genera= tor 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 eith= er a new prover function, a finished proof, or a
rejection (if not a val= id intent).

The prover generator is the selection of the correct sig= nature from a
table for a given script.

Run the prover generator = with the private keys present *once* to
initialize over all reachable st= ates, 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 int= ents are
"impedance matched", that is, all statements the prov= er can prove and
all statements the verifier can verify are one-to-one a= nd onto (or
something similar), and that this also is one-to-one and ont= o with one
element of the intents (a set of transactions) and no other.<= br>
At a given key state the only things that may happen are signed
t= ransactions, no other data is interpreted off of the stack. Therefore
th= ere is perfect impedance match.


5) A set of assumptions under wh= ich 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 co= llision resistance, Discrete Log
Hardness, a SGX module being correct).<= br>
Uniquely, that during the setup phase at least one of the keys
we= re faithfully deleted.

The usual suspects for any bitcoin transactio= n are also assumed for
security.


6) Composability:

The= Terminal State can pay out into a pre-specified covenant if
desired fro= m any other family of covenants.
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000007b864205e9db5c7b--