Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Anthony Towns via bitcoin-dev]

On Mon, Jul 05, 2021 at 09:46:21AM -0400, Matt Corallo via bitcoin-dev wrote:
> More importantly, AJ's point here neuters anti-covanent arguments rather
> strongly.
>
> On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:
> > In some sense multisig *alone* enables recursive covenants: a government
> > that wants to enforce KYC can require that funds be deposited into
> > a multisig of "2   2 CHECKMULTISIG", and that
> > "recipient" has gone through KYC. Once deposited to such an address,
> > the gov can refus to sign with gov_key unless the funds are being spent
> > to a new address that follows the same rules.

I couldn't remember where I'd heard this, but it looks like I came
across it via Andrew Poelstra's "CAT and Schnorr Tricks II" post [0]
(Feb 2021), in which he credits Ethan Heilman for originally coming up
with the analogy (in 2019, cf [1]).

[0] https://medium.com/blockstream/cat-and-schnorr-tricks-ii-2f6ede3d7bb5
[1] https://twitter.com/Ethan_Heilman/status/1194624166093369345

Cheers,
aj

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Jeremy via bitcoin-dev]

Hah -- ZmnSCPxj that post's a doozy -- but it more or less makes sense the
argument you're making in favor of permitting recursion at the transaction
level.

One part that's less clear is if you can make a case against being
recursive in Script fragments themselves -- ignoring bitcoin script for the
moment, what would be wrong with a small VM that a spender is able to
"purchase" a number of cycles and available memory via the annex, and the
program must execute and halt within that time? Then, per block/txn, you
can enforce a total cycle and memory limit. This still isn't quite the EVM,
since there's no cross object calling convention and the output is still
UTXOs. What are the arguments against this model from a safety perspective?



One of my general concerns with recursive covenants is the ability to "go
wrong" in surprising ways. Consider the following program (Sapio
-pseudocode), which is a non recursive
covenant (i.e., doable today with presigning oracles) that demonstrates the
issue.

struct Pool {
members: Vec<(Amount, Key)>,
}
impl Pool {
then!{
fn withdraw(self, ctx) {
let mut builder = ctx.template();
for (a, k) in self.members.iter() {
builder = builder.add_output(a, k.into(), None)?;
}
builder.into()
}
}
guard! {
fn all_signed(self, ctx) {
Clause::And(self.members.iter().map(|(a,k)|
Clause::Key(k.clone())).into())
}
}
finish! {
guarded_by: [all_signed]
fn add_member(self, ctx, o_member: Option<(Amount, Key)>) {
let member = o_member.into()?;
let mut new_members = self.members.clone();
new_members.push(member.clone());
ctx.template().add_output(ctx.funds() + member.0,
  Pool {members: new_members}, None)?.into()
}
}
}

Essentially this is a recursive covenant that allows either Complete via
the withdraw call or Continue via add_member, while preserving the same
underlying code. In this case, all_signed must be signed by all current
participants to admit a new member.

This type of program is subtly "wrong" because the state transition of
add_member does not verify that the Pool's future withdraw call will be
valid. E.g., we could add more than a 1MB of outputs, and then our program
would be "stuck". So it's critical that in our "production grade" covenant
system we do some static analysis before proceeding to a next step to
ensure that all future txns are valid. This is a strength of the CTV/Sapio
model presently, you always output a list of future txns to aid static
analysis.

However, when we make the leap to "automatic" covenants, I posit that it
will be *incredibly* difficult to prove that recursive covenants don't have
a "premature termination" where a state transition that should be valid in
an idealized setting is accidentally invalid in the actual bitcoin
environment and the program reaches a untimely demise.

For instance, OP_CAT has this footgun -- by only permitting 520 bytes, you
hit covenant limits at around 13 outputs assuming you are length checking
each one and not permitting bare script. We can avoid this specific footgun
some of the time by using SHA256STREAM instead, of course.

However, it is generally very difficult to avoid all sorts of issues. E.g.,
with the ability to generate/update tapscript trees, what happens when
through updating a well formed tapscript tree 128 times you bump an
important clause past the 129 depth limit?

I don't think that these sorts of challenges mean that we shouldn't enable
covenants or avoid enabling them, but rather that as we explore we should
add primitives in a methodical way and give users/toolchain builders
primitives that enable and or encourage safety and good program design.

My personal view is that CTV/Sapio with it's AOT compilation of automated
state transitions and ability to statically analyze is a concept that can
mature and be used in production in the near term. But the tooling to
safely do recursive computations at the txn level will take quite a bit
longer to mature, and we should be investing effort in producing
compilers/frameworks for emitting well formed programs before we get too in
the weeds on things like OP_TWEAK. (side note -- there's an easy path for
adding this sort of experimental feature to Sapio if anyone is looking for
a place to start)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor 
wrote:

>
> On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj  wrote:
>
>> Good morning Russell,
>>
>> > Hi ZmnSCPxj,
>> >
>> > I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.
>>
>> Well I believe we should ban partial Turing-completeness, but allow total
>> Turing-completeness.
>>
>
> Unfortunately, when it comes to cross-transaction computations, it is
> infeasible to ban non-terminating computation.
>
> The nature of recursive covenants is that the program "writes" the *source
> code* next step of the computation to the scriptPubKey to one of the
> outputs of its transaction. Technically speaking it verifies that the
> scriptPubKey is a commitment to the source code of the next step of the
> program, but morally that is the same as writing the source code.  Then the
> next step of the computation is invoked by someone "evaluating* that next
> step's source code by creating a valid transaction that spends the
> generated output.
>
> The point is this ability to create new source code and then evaluate it
> leads to the ability to write universal (i.e non-terminating)
> computations.  The only way to prevent it is to ban source code
> manipulation, but since Bitcoin Script source code is just a string of
> bytes, it would mean banning the manipulation of strings of bytes.  But the
> entire Bitcoin Script language works by manipulating strings of bytes
> within a stack machine.  Indeed the most trivial of non-terminating
> programs can be implemented by extracting the current input's scriptPubKey
> from the sighash and "writing" the identical scriptPubKey to one of its
> outputs.  That example hardly takes any manipulation at all to implement.
>

A follow up:  Because recursive covenants need to be sent to a new
transaction in order to recurse, you might choose to view this stepping
mechanism as productive by modeling each transaction step as the continue
constructor in your RecResult codata type.  Indeed after (drinking coffee
and) rereading your mailing list item, it seems that this is the point you
were making.

So sorry for my hasty response.  I believe we are largely in agreement here.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj  wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>

Unfortunately, when it comes to cross-transaction computations, it is
infeasible to ban non-terminating computation.

The nature of recursive covenants is that the program "writes" the *source
code* next step of the computation to the scriptPubKey to one of the
outputs of its transaction. Technically speaking it verifies that the
scriptPubKey is a commitment to the source code of the next step of the
program, but morally that is the same as writing the source code.  Then the
next step of the computation is invoked by someone "evaluating* that next
step's source code by creating a valid transaction that spends the
generated output.

The point is this ability to create new source code and then evaluate it
leads to the ability to write universal (i.e non-terminating)
computations.  The only way to prevent it is to ban source code
manipulation, but since Bitcoin Script source code is just a string of
bytes, it would mean banning the manipulation of strings of bytes.  But the
entire Bitcoin Script language works by manipulating strings of bytes
within a stack machine.  Indeed the most trivial of non-terminating
programs can be implemented by extracting the current input's scriptPubKey
from the sighash and "writing" the identical scriptPubKey to one of its
outputs.  That example hardly takes any manipulation at all to implement.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud via bitcoin-dev]

Thanks for the clarifications Sanket and Russel!

> OP_TWEAK

Ah gotcha. I'm very much in support of recursive covenants. I was lead to
them as a way to create more efficient and flexible wallet vaults. I
actually wrote a proposal

for an opcode to add state to an output. Its pretty useless without an
accompanying covenant opcode, but it seems a bit more straightforward than
the tricks you mentioned (op_tweak and otherwise). I don't plan on starting
a discussion on it yet tho, more work to be done on it and other things
to open discussion on first.

In any case, its nice to see so much general agreement on a topic that
could easily be embroidered in contention.

On Tue, Jul 6, 2021 at 9:26 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>
> I just think that unlimited recursive covenants (with or without a
> convenient way to transform state at each iteration) are **not** partial
> Turing-complete, but *are* total Turing-complete. (^^)
>
> (The rest of this writeup is mostly programming languages nerdery so
> anyone who is not interested in Haskell (or purely functional programming)
> and programming language nerdery can feel free to skip the rest of this
> post.
> Basically, ZmnSCPxj thinks we should still ban Turing-completeness, but
> unbounded covenants get a pass because they are not, on a technicality,
> Turing-complete)
>
> For now, let us first taboo the term "Turing-complete", and instead focus
> on what I think matters here, the distinction between partial and total,
>
> In a total programming language we have a distinction between data and
> codata:
>
> * Data is defined according to its constructors, i.e. an algebraic data
> type.
> * Codata is defined according to its destructors, i.e. according to a
> "behavior" the codata has when a particular "action" is applied to it.
>
> For example, a singly-linked list data type would be defined as follows:
>
> data List a where
> Cons :: a -> List a -> List a
> Nil :: List a
>
> On the other hand, an infinite codata stream of objects would be defined
> as follows:
>
> codata Stream a where
> head :: Stream a -> a
> tail :: Stream a -> Stream a
>
> For `data` types, the result type for each constructor listed in the
> definition *must* be the type being defined.
> That is why `Cons` is declared as resulting in a `List a`.
> We declare data according to its constructors.
>
> For `codata` types, the *first argument* for each destructor listed in the
> definition *must* be the type being defined.
> That is why `head` accepts as its first argument the `Stream a` type.
>
> This is relevant because in a total function programming language, there
> exists some programming rule that restricts recursion.
> The simplest such restriction is substructural recursion:
>
> * If a function recurs:
>   * Every self-call should pass in a substructure of an argument as that
> argument.
>
> Every program that passes the above rule provably terminates.
> Since every recursion passes in a smaller part of an argument, eventually
> we will reach an indivisible primitive object being passed in, and
> processing will stop recursing and can return some value.
>
> Thus, a programing language that has substructural recursion rule check
> (and rejects programs that fail the substrucutral recursion check) are not
> "Turing-complete".
> The reason is that Turing-complete languages cannot solve the Halting
> Problem.
> But a language that includes the substructural recursion rule *does* have
> a Halting Problem solution: every program that passes the substructural
> recursion rule halts and the Halting Problem is decidable for all programs
> that pass the substructural recursion rule.
> (i.e. we are deliberately restricting ourselves to a subset of programs
> that pass substructural recursion, and reject programs that do not pass
> this rule as "not really programs", so every program halts)
>
> For example, the following definition of `mapList` is valid under
> substructural recursion:
>
> mapList :: (a -> b) -> (List a -> List b)
> mapList f Nil= Nil
> mapList f (Cons a as)= Cons (f a) (mapList f as)
>
> The second sub-definition has a recursive call `mapList f as`.
> The second argument to that call, however, is a substructure of the second
> argument `Cons a as` on the LHS of the definition, thus it is a
> substructural recursive call, and accepted in a total programming language.
> *Every* recursion in `mapList` should then be a substructural call on the
> second argument of `mapList`.
>
> Now let us consider the following definition of 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj via bitcoin-dev]

Good morning Russell,

> Hi ZmnSCPxj,
>
> I don't believe we need to ban Turing completeness for the sake of banning 
> Turing completeness.

Well I believe we should ban partial Turing-completeness, but allow total 
Turing-completeness.

I just think that unlimited recursive covenants (with or without a convenient 
way to transform state at each iteration) are **not** partial Turing-complete, 
but *are* total Turing-complete. (^^)

(The rest of this writeup is mostly programming languages nerdery so anyone who 
is not interested in Haskell (or purely functional programming) and programming 
language nerdery can feel free to skip the rest of this post.
Basically, ZmnSCPxj thinks we should still ban Turing-completeness, but 
unbounded covenants get a pass because they are not, on a technicality, 
Turing-complete)

For now, let us first taboo the term "Turing-complete", and instead focus on 
what I think matters here, the distinction between partial and total,

In a total programming language we have a distinction between data and codata:

* Data is defined according to its constructors, i.e. an algebraic data type.
* Codata is defined according to its destructors, i.e. according to a 
"behavior" the codata has when a particular "action" is applied to it.

For example, a singly-linked list data type would be defined as follows:

data List a where
Cons :: a -> List a -> List a
Nil :: List a

On the other hand, an infinite codata stream of objects would be defined as 
follows:

codata Stream a where
head :: Stream a -> a
tail :: Stream a -> Stream a

For `data` types, the result type for each constructor listed in the definition 
*must* be the type being defined.
That is why `Cons` is declared as resulting in a `List a`.
We declare data according to its constructors.

For `codata` types, the *first argument* for each destructor listed in the 
definition *must* be the type being defined.
That is why `head` accepts as its first argument the `Stream a` type.

This is relevant because in a total function programming language, there exists 
some programming rule that restricts recursion.
The simplest such restriction is substructural recursion:

* If a function recurs:
  * Every self-call should pass in a substructure of an argument as that 
argument.

Every program that passes the above rule provably terminates.
Since every recursion passes in a smaller part of an argument, eventually we 
will reach an indivisible primitive object being passed in, and processing will 
stop recursing and can return some value.

Thus, a programing language that has substructural recursion rule check (and 
rejects programs that fail the substrucutral recursion check) are not 
"Turing-complete".
The reason is that Turing-complete languages cannot solve the Halting Problem.
But a language that includes the substructural recursion rule *does* have a 
Halting Problem solution: every program that passes the substructural recursion 
rule halts and the Halting Problem is decidable for all programs that pass the 
substructural recursion rule.
(i.e. we are deliberately restricting ourselves to a subset of programs that 
pass substructural recursion, and reject programs that do not pass this rule as 
"not really programs", so every program halts)

For example, the following definition of `mapList` is valid under substructural 
recursion:

mapList :: (a -> b) -> (List a -> List b)
mapList f Nil= Nil
mapList f (Cons a as)= Cons (f a) (mapList f as)

The second sub-definition has a recursive call `mapList f as`.
The second argument to that call, however, is a substructure of the second 
argument `Cons a as` on the LHS of the definition, thus it is a substructural 
recursive call, and accepted in a total programming language.
*Every* recursion in `mapList` should then be a substructural call on the 
second argument of `mapList`.

Now let us consider the following definition of `fibonacci`:

-- to use: fibonacci 1 1
fibonacci :: Integer -> Integer -> List Integer
fibonacci x y = Cons x (fibonacci y (x + y))

The above is not substructural recursive, neither argument in the recursive 
`fibonacci y (x + y)` call is a substructure of the arguments in the LHS of the 
`fibonacci` definition `fibonacci x y`.

Thus, we prevent certain unbounded computations like the above infinite 
sequence of fibonacci numbers.

Now, let us consider a definition of `mapStream`, the similar function on 
streams, using copattern matching rather than pattern matching:

mapStream :: (a -> b) -> (Stream a -> Stream b)
head (mapStream f as) = f (head as)
tail (mapStream f as) = mapStream f (tail as)

Now the interesting thing here is that in the substructural recursion check, 
what is being defined in the above stanza is ***not*** `mapStream`, but `head` 
and `tail`!
Thus, it ignores the `mapStream f (tail as)`, because it is **not** recursion 
--- what is being defined here is `tail`.

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Jeremy via bitcoin-dev]

heh -- I pointed out these evil multisig covenants in 2015 :)
https://medium.com/@jeremyrubin/regulating-bitcoin-by-mining-the-regulator-miner-attack-c8fd51185b78
I'm relatively unconcerned by it except to the extent that mining
centralizes to the point of censoring other traffic.

Overall, I think this is a great conversation to be having.

However, I want to push back on David's claim that  "Respecting the
concerns of others doesn't require lobotomizing useful tools.".

CHECKSIGFROMSTACK is a primitive and the opcode is not being nerfed in any
way shape or form. The argument here is that doing CSFS and not CAT is
nerfing CSFS... but CSFS is an independently useful and cool opcode that
has many of it's own merits.

Further, as described in my [blog post](
https://rubin.io/blog/2021/07/02/covenants/), CSFS has very high "design
specificity"... that is there's not *that* many design choices that could
possibly go into it. It's checking a signature. From the stack. That's all
folks! There are no design compromises in it. No lobotomy.

OP_CAT is more or less completely unrelated to CSFS. As Andrew has
[demonstrated](
https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html),
*just* OP_CAT alone (no CSFS) gives you covenants (albeit in a hacky way)
with Schnorr.

I think roconnor agrees that CAT(+CSFS?) are not really a "fantastic" way
to do covenants, that there are more direct approaches that will be better
or neccessary such as TWEAK or UPDATETAPLEAF. Let's work on those! But
let's also not hold up progress on other useful things while those are
brewing.

Non-Redundancy should be a non-goal for script -- although we strive to be
minimal, redundancy is inevitable. For example, OP_SWAP has identical
semantics to <1> ROLL, but SWAP is a common enough use that it is pragmatic
to assign it an opcode and OP_ROLL does something distinctly enhanced.
Similarly, even if we add CAT we will surely come up with saner ways to
implement covenant logic than Andrew's Schnorr tricks.

CTV in particular is designed to be a part of that story -- enough
functionality w/o OP_CAT to work *today* and serve a purpose long into the
future, but with OP_CAT (or shastream preferably) enhances it's
functionality in a useful way and with introspection opcodes (perhaps like
those being developed by elements) further gains functionality. Perhaps the
functionality available today will be redundant with a future way of doing
things, but we can only see so far into the future. However, we can see
that there are good things to build with it today.

It's the inverse of a lobotomy. Independent components that can come
together for a newer greater purpose rather than parts being torn apart
irreparably.

In the future when we have specific use cases in mind that *aren't* served
well (either efficiently or at all) by the existing primitives, it's
completely acceptable to add something new even if it makes an existing
feature redundant. APO, for example, will be redundant (afaict) will Glen
Willen's [Bitmask SigHash Flags](
https://bc-2.jp/archive/season2/materials/0203_NewElementsFeaturesEn.pdf)
should we ever get those.

--
@JeremyRubin 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

On Tue, Jul 6, 2021 at 2:26 AM Billy Tetrud  wrote:

> >  when people are talking about enabling covenants, we are talking about
> whether OP_CAT should be allowed or not
>
> Are they? Are you implying that anything that enables covenants is
> equivalent to enabling OP_CAT? Generally when I think about enabling
> covenants, I'm thinking more about OP_CTV (or some similarly specific
> opcode
> 
> ).
>
> > OP_TWEAK
>
> I wasn't able to find anything about what that is. Would you mind
> clarifying what that concept is?
>

In tapscript one can generally recover the current input's scriptPubkey
through sighash introspection via the usual covenant tricks.  This allows
you to make a recursive covenant by spending funds back to the same
identical scriptPubkey.  However, in order for a recursive covenant to be
actually interesting, there needs to be some sort of state update in each
transition.  If there is no state update then sending funds back to itself
is of very limited value.  It will reset the timer on relative locks, but
that is about all.

The "normal" way of writing useful recursive covenants is to modify the
scriptPubkey by changing a fragment of it that contains some sort of
state.  However in order to update a tapscript pubkey one needs to apply
not only hashing, to create a Merkel root, but also to create a tweaked
taproot pubkey that commits to this root.  While script currently comes
with a SHA-256 hashing opcode, there is no opcode that will let you perform
the necessary tweaking to create a taproot scriptPubkey.

But as I mentioned afterwards, there are other places in the UTXO that you
could put data in order to perform a state update.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Sanket Kanjalkar via bitcoin-dev]

After some brainstorming about the possible drawbacks of enabling
covenants, I have also slowly become more comfortable with the idea of
"unlimited" covenants. AJs example clearly shows that _all_ possible
"misuses" of covenants are already possible by Multi-Sig today, so it's not
a new vector that we are adding today.

>  My concerns have always been around ensuring that transaction and block
validation is not unduly burdensome for nodes.  So for Bitcoin Script, we
want to bound the amount of resources needed to execute it, preferably as a
linear function of weight[1], and preferably have it clear what the
evaluation costs are going to be prior to evaluation[2].  We also want to
keep Script execution as a pure function of the transaction data so that
nodes do not need to reevaluate their mempool on every new block.

Many bitcoin upgrades, in particular, Segwit, and tapscript sigops budget
have been along with the same principle. And as mentioned before, none of
these go against enabling recursive covenants.

> Are they? Are you implying that anything that enables covenants is
equivalent to enabling OP_CAT?

No, it is not equivalent. Russell is referring to a way to do covenants by
only using `OP_CAT`(along with Schnorr sigs that we already have) as
mentioned by Andrew Poelstra here
 .

I also am in general support of the `OP_CHECKSIGFROMSTACK` opcode. We would
need to update the suggestion to BIP340, and add it to sigops budget. I
have no strong preference for splitting R and s values or variable-length
messages.


On Tue, Jul 6, 2021 at 1:36 AM Billy Tetrud via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> >  when people are talking about enabling covenants, we are talking about
> whether OP_CAT should be allowed or not
>
> Are they? Are you implying that anything that enables covenants is
> equivalent to enabling OP_CAT? Generally when I think about enabling
> covenants, I'm thinking more about OP_CTV (or some similarly specific
> opcode
> 
> ).
>
> > OP_TWEAK
>
> I wasn't able to find anything about what that is. Would you mind
> clarifying what that concept is?
>
> On Mon, Jul 5, 2021 at 10:20 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi ZmnSCPxj,
>>
>> I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.  My concerns have always been around ensuring
>> that transaction and block validation is not unduly burdensome for nodes.
>> So for Bitcoin Script, we want to bound the amount of resources needed to
>> execute it, preferably as a linear function of weight[1], and preferably
>> have it clear what the evaluation costs are going to be prior to
>> evaluation[2].  We also want to keep Script execution as a pure function of
>> the transaction data so that nodes do not need to reevaluate their mempool
>> on every new block.  For consensus purposes we prefer to have simple
>> primitive operations that have clear and precise semantics that are as
>> likely as possible to be reimplemented correctly if they are reimplemented
>> (or at least let us not make this problem worse than it already is).  In
>> particular, Script needs to be easy to parse to avoid weird parsing
>> machines that lead to security vulnerabilities within node software.
>>
>> While the above design constraints imply a prohibition on Turing complete
>> computation within a single Script, they do not imply a prohibition on
>> arbitrary, covenant-enabled computations that spans across multiple
>> transactions.  Neither would these constraints prohibit some kind of STARK
>> or SNARK tapleaf version that was somehow capable of succinctly
>> representing arbitrary computations, so long as validation costs remain
>> bounded.
>>
>> And while it is true that covenant-enabled computations could allow users
>> to put their funds at risk through weird machines that manipulate their
>> money on the blockchain, as longs as that weirdness stays at that level of
>> the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
>> don't send your funds to random unverified Bitcoin Scripts, advice that is
>> already the case today.  We can keep that potential weirdness at bay by
>> keeping Script simple, and maintaining our understanding that the Script
>> programs (like the rest of the blockchain data) are untrusted inputs and
>> they need to be validated and scrutinized before interpretation.
>>
>> [1] In tapscript I believe all operations are linear time with the
>> exception of OP_ROLL.  However OP_ROLL is still constrained by global
>> limits on stack size, etc.
>> [2] In Bitcoin Script, without loops of any kind, every opcode is
>> evaluated at most once, so counting opcodes is an easy way to put an upper
>> bound on your costs before evaluation.
>>
>> On Sun, Jul 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud via bitcoin-dev]

>  when people are talking about enabling covenants, we are talking about
whether OP_CAT should be allowed or not

Are they? Are you implying that anything that enables covenants is
equivalent to enabling OP_CAT? Generally when I think about enabling
covenants, I'm thinking more about OP_CTV (or some similarly specific opcode

).

> OP_TWEAK

I wasn't able to find anything about what that is. Would you mind
clarifying what that concept is?

On Mon, Jul 5, 2021 at 10:20 AM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi ZmnSCPxj,
>
> I don't believe we need to ban Turing completeness for the sake of banning
> Turing completeness.  My concerns have always been around ensuring that
> transaction and block validation is not unduly burdensome for nodes.  So
> for Bitcoin Script, we want to bound the amount of resources needed to
> execute it, preferably as a linear function of weight[1], and preferably
> have it clear what the evaluation costs are going to be prior to
> evaluation[2].  We also want to keep Script execution as a pure function of
> the transaction data so that nodes do not need to reevaluate their mempool
> on every new block.  For consensus purposes we prefer to have simple
> primitive operations that have clear and precise semantics that are as
> likely as possible to be reimplemented correctly if they are reimplemented
> (or at least let us not make this problem worse than it already is).  In
> particular, Script needs to be easy to parse to avoid weird parsing
> machines that lead to security vulnerabilities within node software.
>
> While the above design constraints imply a prohibition on Turing complete
> computation within a single Script, they do not imply a prohibition on
> arbitrary, covenant-enabled computations that spans across multiple
> transactions.  Neither would these constraints prohibit some kind of STARK
> or SNARK tapleaf version that was somehow capable of succinctly
> representing arbitrary computations, so long as validation costs remain
> bounded.
>
> And while it is true that covenant-enabled computations could allow users
> to put their funds at risk through weird machines that manipulate their
> money on the blockchain, as longs as that weirdness stays at that level of
> the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
> don't send your funds to random unverified Bitcoin Scripts, advice that is
> already the case today.  We can keep that potential weirdness at bay by
> keeping Script simple, and maintaining our understanding that the Script
> programs (like the rest of the blockchain data) are untrusted inputs and
> they need to be validated and scrutinized before interpretation.
>
> [1] In tapscript I believe all operations are linear time with the
> exception of OP_ROLL.  However OP_ROLL is still constrained by global
> limits on stack size, etc.
> [2] In Bitcoin Script, without loops of any kind, every opcode is
> evaluated at most once, so counting opcodes is an easy way to put an upper
> bound on your costs before evaluation.
>
> On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning Dave,
>>
>> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
>> >
>> > > However, I think the broader community is unconvinced by the cost
>> benefit
>> > > of arbitrary covenants. See
>> > >
>> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
>> > > as a recent example. Therefore as a critical part of building
>> consensus on
>> > > various techniques I've worked to emphasize that specific additions
>> do not
>> > > entail risk of accidentally introducing more than was bargained for to
>> > > respect the concerns of others.
>> >
>> > Respecting the concerns of others doesn't require lobotomizing useful
>> > tools. Being respectful can also be accomplished by politely showing
>> > that their concerns are unfounded (or at least less severe than they
>> > thought). This is almost always the better course IMO---it takes much
>> > more effort to satisfy additional engineering constraints (and prove to
>> > reviewers that you've done so!) than it does to simply discuss those
>> > concerns with reasonable stakeholders. As a demonstration, let's look
>> > at the concerns from Shinobi's post linked above:
>> >
>> > They seem to be worried that some Bitcoin users will choose to accept
>> > coins that can't subsequently be fungibily mixed with other bitcoins.
>> > But that's already been the case for a decade: users can accept altcoins
>> > that are non-fungible with bitcoins.
>> >
>> > They talk about covenants where spending is controlled by governments,
>> > but that seems to me exactly like China's CBDC trial.
>> >
>> > They talk about exchanges depositing users' BTC into a covenant, but
>> > that's just 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

Hi ZmnSCPxj,

I don't believe we need to ban Turing completeness for the sake of banning
Turing completeness.  My concerns have always been around ensuring that
transaction and block validation is not unduly burdensome for nodes.  So
for Bitcoin Script, we want to bound the amount of resources needed to
execute it, preferably as a linear function of weight[1], and preferably
have it clear what the evaluation costs are going to be prior to
evaluation[2].  We also want to keep Script execution as a pure function of
the transaction data so that nodes do not need to reevaluate their mempool
on every new block.  For consensus purposes we prefer to have simple
primitive operations that have clear and precise semantics that are as
likely as possible to be reimplemented correctly if they are reimplemented
(or at least let us not make this problem worse than it already is).  In
particular, Script needs to be easy to parse to avoid weird parsing
machines that lead to security vulnerabilities within node software.

While the above design constraints imply a prohibition on Turing complete
computation within a single Script, they do not imply a prohibition on
arbitrary, covenant-enabled computations that spans across multiple
transactions.  Neither would these constraints prohibit some kind of STARK
or SNARK tapleaf version that was somehow capable of succinctly
representing arbitrary computations, so long as validation costs remain
bounded.

And while it is true that covenant-enabled computations could allow users
to put their funds at risk through weird machines that manipulate their
money on the blockchain, as longs as that weirdness stays at that level of
the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
don't send your funds to random unverified Bitcoin Scripts, advice that is
already the case today.  We can keep that potential weirdness at bay by
keeping Script simple, and maintaining our understanding that the Script
programs (like the rest of the blockchain data) are untrusted inputs and
they need to be validated and scrutinized before interpretation.

[1] In tapscript I believe all operations are linear time with the
exception of OP_ROLL.  However OP_ROLL is still constrained by global
limits on stack size, etc.
[2] In Bitcoin Script, without loops of any kind, every opcode is evaluated
at most once, so counting opcodes is an easy way to put an upper bound on
your costs before evaluation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Greg Sanders via bitcoin-dev]

Funny AJ mentions the multisig idea, because I know for a fact it's being
used in certain permissioned systems in this exact way. Regulators will
dream up these ideas with or without more useful covenants!

On Mon, Jul 5, 2021 at 9:46 PM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I find this point to be incredibly important. Indeed I, like several
> others, have historically been concerned with
> covenants in the unbounded form. However, as more and more research has
> been done in what they can accomplish, the
> weighting of such arguments naturally has to be reduced. More importantly,
> AJ's point here neuters anti-covanent
> arguments rather strongly.
>
> Matt
>
> On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:
> > On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via
> bitcoin-dev wrote:
> >> Bear in mind that when people are talking about enabling covenants, we
> are
> >> talking about whether OP_CAT should be allowed or not.
> >
> > In some sense multisig *alone* enables recursive covenants: a government
> > that wants to enforce KYC can require that funds be deposited into
> > a multisig of "2   2 CHECKMULTISIG", and that
> > "recipient" has gone through KYC. Once deposited to such an address,
> > the gov can refus to sign with gov_key unless the funds are being spent
> > to a new address that follows the same rules.
> >
> > (That's also more efficient than an explicit covenant since it's all
> > off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
> > that point, so that full nodes are only validating a single pubkey and
> > signature per spend, rather than having to do analysis of whatever the
> > underlying covenant is supposed to be [0])
> >
> > This is essentially what Liquid already does -- it locks bitcoins into
> > a multisig and enforces an "off-chain" covenant that those bitcoins can
> > only be redeemed after some valid set of signatures are entered into
> > the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
> > To some extent, likewise for coins held in exchanges/custodial wallets
> > where funds can be transferred between customers off-chain.
> >
> > You can "escape" from that recursive covenant by having the government
> > (or Liquid functionaries, or exchange admins) change their signing
> > policy of course; but you could equally escape any consensus-enforced
> > covenant by having a hard fork to stop doing consensus-enforcement (cf
> > ETH Classic?). To me, that looks more like a difference of procedure
> > and difficulty, rather than a fundamental difference in kind.
> >
> > Cheers,
> > aj
> >
> > [0] https://twitter.com/pwuille/status/1411533549224693762
> >
> > ___
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Matt Corallo via bitcoin-dev]

I find this point to be incredibly important. Indeed I, like several others, have historically been concerned with 
covenants in the unbounded form. However, as more and more research has been done in what they can accomplish, the 
weighting of such arguments naturally has to be reduced. More importantly, AJ's point here neuters anti-covanent 
arguments rather strongly.


Matt

On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:

On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via bitcoin-dev 
wrote:

Bear in mind that when people are talking about enabling covenants, we are
talking about whether OP_CAT should be allowed or not.


In some sense multisig *alone* enables recursive covenants: a government
that wants to enforce KYC can require that funds be deposited into
a multisig of "2   2 CHECKMULTISIG", and that
"recipient" has gone through KYC. Once deposited to such an address,
the gov can refus to sign with gov_key unless the funds are being spent
to a new address that follows the same rules.

(That's also more efficient than an explicit covenant since it's all
off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
that point, so that full nodes are only validating a single pubkey and
signature per spend, rather than having to do analysis of whatever the
underlying covenant is supposed to be [0])

This is essentially what Liquid already does -- it locks bitcoins into
a multisig and enforces an "off-chain" covenant that those bitcoins can
only be redeemed after some valid set of signatures are entered into
the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
To some extent, likewise for coins held in exchanges/custodial wallets
where funds can be transferred between customers off-chain.

You can "escape" from that recursive covenant by having the government
(or Liquid functionaries, or exchange admins) change their signing
policy of course; but you could equally escape any consensus-enforced
covenant by having a hard fork to stop doing consensus-enforcement (cf
ETH Classic?). To me, that looks more like a difference of procedure
and difficulty, rather than a fundamental difference in kind.

Cheers,
aj

[0] https://twitter.com/pwuille/status/1411533549224693762

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Anthony Towns via bitcoin-dev]

On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via bitcoin-dev 
wrote:
> Bear in mind that when people are talking about enabling covenants, we are
> talking about whether OP_CAT should be allowed or not.

In some sense multisig *alone* enables recursive covenants: a government
that wants to enforce KYC can require that funds be deposited into
a multisig of "2   2 CHECKMULTISIG", and that
"recipient" has gone through KYC. Once deposited to such an address,
the gov can refus to sign with gov_key unless the funds are being spent
to a new address that follows the same rules.

(That's also more efficient than an explicit covenant since it's all
off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
that point, so that full nodes are only validating a single pubkey and
signature per spend, rather than having to do analysis of whatever the
underlying covenant is supposed to be [0])

This is essentially what Liquid already does -- it locks bitcoins into
a multisig and enforces an "off-chain" covenant that those bitcoins can
only be redeemed after some valid set of signatures are entered into
the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
To some extent, likewise for coins held in exchanges/custodial wallets
where funds can be transferred between customers off-chain.

You can "escape" from that recursive covenant by having the government
(or Liquid functionaries, or exchange admins) change their signing
policy of course; but you could equally escape any consensus-enforced
covenant by having a hard fork to stop doing consensus-enforcement (cf
ETH Classic?). To me, that looks more like a difference of procedure
and difficulty, rather than a fundamental difference in kind.

Cheers,
aj

[0] https://twitter.com/pwuille/status/1411533549224693762

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj via bitcoin-dev]

Good morning Russell,


> On Sun, Jul 4, 2021 at 9:02 PM Russell O'Connor  
> wrote:
>
> > Bear in mind that when people are talking about enabling covenants, we are 
> > talking about whether OP_CAT should be allowed or not.
> >
> > That said, recursive covenants, the type that are most worrying, seems to 
> > require some kind of OP_TWEAK operation, and I haven't yet seen any 
> > evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we 
> > should leave such worries for the OP_TWEAK operation.
>
> Upon further thought, you can probably make recursive covenants even with a 
> fixed scritpubkey by sneaking the state into a few bits of the UTXO's amount. 
>  Or if you try really hard, you may be able to stash your state into a 
> sibling output that is accessed via the txid embedded in the prevoutpoint.

Which is kind of the point of avoiding giving too much power, because people 
can be very clever and start doing unexpected things from what you think is 
already a limited subset.
"Give an inch and they will take a mile".

Still, as pointed out, altcoins already exist and are substantially worse, and 
altcoin implementations are all going to run on Turing machines anyway (which 
are powerful enough to offer Turing-machine functionality), so maybe this is 
not really giving too much power, people can already fork Bitcoin and add full 
EVM support on it.

Regards,
ZmnSCPxj

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

On Sun, Jul 4, 2021 at 9:02 PM Russell O'Connor 
wrote:

> Bear in mind that when people are talking about enabling covenants, we are
> talking about whether OP_CAT should be allowed or not.
>
> That said, recursive covenants, the type that are most worrying, seems to
> require some kind of OP_TWEAK operation, and I haven't yet seen any
> evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
> should leave such worries for the OP_TWEAK operation.
>

Upon further thought, you can probably make recursive covenants even with a
fixed scritpubkey by sneaking the state into a few bits of the UTXO's
amount.  Or if you try really hard, you may be able to stash your state
into a sibling output that is accessed via the txid embedded in the
prevoutpoint.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor via bitcoin-dev]

Bear in mind that when people are talking about enabling covenants, we are
talking about whether OP_CAT should be allowed or not.

That said, recursive covenants, the type that are most worrying, seems to
require some kind of OP_TWEAK operation, and I haven't yet seen any
evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
should leave such worries for the OP_TWEAK operation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out covenants are the next ICO".
> i.e. ICOs are just colored coins, which are useful for keeping track of
> various stuff, but have then been used as a vehicle to scam people.
> But I suppose that is a problem that humans will always have: limited
> cognition, so that *good* popular things that are outside your specific
> field of study are indistinguishable from *bad* popular things.
> So perhaps it should not be a concern on a technical level.
> Maybe we should instead make articles about covenants so boring nobody
> will hype about it (^^;)v.
>
> Increased functionality implies increased processing, and hopefully
> computation devices are getting cheap enough that the increased processing
> implied by new features should not be too onerous.
>
>
>
> To my mind, an "inescapable" covenant (i.e. one that requires the output
> to be paid to the same covenant) is basically a Turing machine, and
> equivalent to a `while (true);` loop.
> In a `while (true);` loop, the state of the machine reverts back to the
> same state, and it repeats again.
> In an inescpable covenant, the control of some amount of funds reverts
> back to the same controlling SCRIPT, and it repeats again.
> Yes, you can certainly add more functionality on top of that loop, just
> think of program main loops for games or daemons, which are, in essence,
> "just" `while (true) ...`.
> But basically, such unbounded infinite loops are possible only under
> Turing machines, thus I consider covenants to be Turing-complete.
> Principle of Least Power should make us wonder if we need full Turing
> machines for the functionality.
>
> On the other hand --- codata processing *does* allow for unbounded loops,
> without requiring full Turing-completeness; they just require total
> functionality, not partial (and Turing-completeness is partial, not total).
> Basically, data structures are unbounded storage, while codata structures
> are unbounded processing.
> Perhaps covenants can encode an upper bound on the number of recursions,
> which prevents full Turing-completeness 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj via bitcoin-dev]

Good morning Dave,

> On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
>
> > However, I think the broader community is unconvinced by the cost benefit
> > of arbitrary covenants. See
> > https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > as a recent example. Therefore as a critical part of building consensus on
> > various techniques I've worked to emphasize that specific additions do not
> > entail risk of accidentally introducing more than was bargained for to
> > respect the concerns of others.
>
> Respecting the concerns of others doesn't require lobotomizing useful
> tools. Being respectful can also be accomplished by politely showing
> that their concerns are unfounded (or at least less severe than they
> thought). This is almost always the better course IMO---it takes much
> more effort to satisfy additional engineering constraints (and prove to
> reviewers that you've done so!) than it does to simply discuss those
> concerns with reasonable stakeholders. As a demonstration, let's look
> at the concerns from Shinobi's post linked above:
>
> They seem to be worried that some Bitcoin users will choose to accept
> coins that can't subsequently be fungibily mixed with other bitcoins.
> But that's already been the case for a decade: users can accept altcoins
> that are non-fungible with bitcoins.
>
> They talk about covenants where spending is controlled by governments,
> but that seems to me exactly like China's CBDC trial.
>
> They talk about exchanges depositing users' BTC into a covenant, but
> that's just a variation on the classic not-your-keys-not-your-bitcoins
> problem. For all you know, your local exchange is keeping most of its
> BTC balance commitments in ETH or USDT.
>
> To me, it seems like the worst-case problems Shinobi describes with
> covenants are some of the same problems that already exist with
> altcoins. I don't see how recursive covenants could make any of those
> problems worse, and so I don't see any point in limiting Bitcoin's
> flexibility to avoid those problems when there are so many interesting
> and useful things that unlimited covenants could do.

The "altcoins are even worse" argument does seem quite convincing, and if 
Bitcoin can survive altcoins, surely it can survive covenants too?

In before "turns out covenants are the next ICO".
i.e. ICOs are just colored coins, which are useful for keeping track of various 
stuff, but have then been used as a vehicle to scam people.
But I suppose that is a problem that humans will always have: limited 
cognition, so that *good* popular things that are outside your specific field 
of study are indistinguishable from *bad* popular things.
So perhaps it should not be a concern on a technical level.
Maybe we should instead make articles about covenants so boring nobody will 
hype about it (^^;)v.

Increased functionality implies increased processing, and hopefully computation 
devices are getting cheap enough that the increased processing implied by new 
features should not be too onerous.



To my mind, an "inescapable" covenant (i.e. one that requires the output to be 
paid to the same covenant) is basically a Turing machine, and equivalent to a 
`while (true);` loop.
In a `while (true);` loop, the state of the machine reverts back to the same 
state, and it repeats again.
In an inescpable covenant, the control of some amount of funds reverts back to 
the same controlling SCRIPT, and it repeats again.
Yes, you can certainly add more functionality on top of that loop, just think 
of program main loops for games or daemons, which are, in essence, "just" 
`while (true) ...`.
But basically, such unbounded infinite loops are possible only under Turing 
machines, thus I consider covenants to be Turing-complete.
Principle of Least Power should make us wonder if we need full Turing machines 
for the functionality.

On the other hand --- codata processing *does* allow for unbounded loops, 
without requiring full Turing-completeness; they just require total 
functionality, not partial (and Turing-completeness is partial, not total).
Basically, data structures are unbounded storage, while codata structures are 
unbounded processing.
Perhaps covenants can encode an upper bound on the number of recursions, which 
prevents full Turing-completeness while allowing for a large number of 
use-cases.

(if the above paragraph makes no sense to you, hopefully this Wikipedia article 
will help: https://en.wikipedia.org/wiki/Total_functional_programming )
(basically my argument here is based on academic programming stuff, and might 
not actually matter in real life)

Regards,
ZmnSCPxj
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud via bitcoin-dev]

I agree with you David. I think rather unconstrained covenants are
incredibly useful and important. Yes you can burn coins with them, you can
also permanently limit the usability of certain coins (which is less
destructive than burning them). But as Jeremy said, people are free to burn
their coins. People would also be free (in general) to reject coins
encumbered by weird government provisions or unknown provisions in hidden
scripts. A person/wallet shouldn't accept coins encumbered by scripts it
doesn't recognize.

Even if 99% of bitcoins became permanently encumbered by weird covenants,
the other 1% could still be plenty of bitcoins to run the economy, because
of its potentially infinite divisibility. Losing these coins, or someone
basically turning them into altcoin-like bitcoins shouldn't be a concern
really. What's the risk exactly? That people will be forced to take these
encumbered coins? A government can already force people to take whatever
altcoin they want to force on people - covenants don't make this worse.

Shinobi asks: "What if you extorted users with your 51% attack to move into
those?"

Well, you could do this anyway even without covenants existing already. The
51% attack could simply extort people to use whatever rules they want just
as easily (which isn't to say that easily - most users would probably
refuse to be extorted in either case). So I don't really think this is very
valid.

On Sun, Jul 4, 2021 at 1:33 PM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> > However, I think the broader community is unconvinced by the cost benefit
> > of arbitrary covenants. See
> >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > as a recent example. Therefore as a critical part of building consensus
> on
> > various techniques I've worked to emphasize that specific additions do
> not
> > entail risk of accidentally introducing more than was bargained for to
> > respect the concerns of others.
>
> Respecting the concerns of others doesn't require lobotomizing useful
> tools.  Being respectful can also be accomplished by politely showing
> that their concerns are unfounded (or at least less severe than they
> thought).  This is almost always the better course IMO---it takes much
> more effort to satisfy additional engineering constraints (and prove to
> reviewers that you've done so!) than it does to simply discuss those
> concerns with reasonable stakeholders.  As a demonstration, let's look
> at the concerns from Shinobi's post linked above:
>
> They seem to be worried that some Bitcoin users will choose to accept
> coins that can't subsequently be fungibily mixed with other bitcoins.
> But that's already been the case for a decade: users can accept altcoins
> that are non-fungible with bitcoins.
>
> They talk about covenants where spending is controlled by governments,
> but that seems to me exactly like China's CBDC trial.
>
> They talk about exchanges depositing users' BTC into a covenant, but
> that's just a variation on the classic not-your-keys-not-your-bitcoins
> problem.  For all you know, your local exchange is keeping most of its
> BTC balance commitments in ETH or USDT.
>
> To me, it seems like the worst-case problems Shinobi describes with
> covenants are some of the same problems that already exist with
> altcoins.  I don't see how recursive covenants could make any of those
> problems worse, and so I don't see any point in limiting Bitcoin's
> flexibility to avoid those problems when there are so many interesting
> and useful things that unlimited covenants could do.
>
> -Dave
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[David A. Harding via bitcoin-dev]

On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> However, I think the broader community is unconvinced by the cost benefit
> of arbitrary covenants. See
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> as a recent example. Therefore as a critical part of building consensus on
> various techniques I've worked to emphasize that specific additions do not
> entail risk of accidentally introducing more than was bargained for to
> respect the concerns of others.

Respecting the concerns of others doesn't require lobotomizing useful
tools.  Being respectful can also be accomplished by politely showing
that their concerns are unfounded (or at least less severe than they
thought).  This is almost always the better course IMO---it takes much
more effort to satisfy additional engineering constraints (and prove to
reviewers that you've done so!) than it does to simply discuss those
concerns with reasonable stakeholders.  As a demonstration, let's look
at the concerns from Shinobi's post linked above:

They seem to be worried that some Bitcoin users will choose to accept
coins that can't subsequently be fungibily mixed with other bitcoins.
But that's already been the case for a decade: users can accept altcoins
that are non-fungible with bitcoins.

They talk about covenants where spending is controlled by governments,
but that seems to me exactly like China's CBDC trial.

They talk about exchanges depositing users' BTC into a covenant, but 
that's just a variation on the classic not-your-keys-not-your-bitcoins
problem.  For all you know, your local exchange is keeping most of its
BTC balance commitments in ETH or USDT.

To me, it seems like the worst-case problems Shinobi describes with
covenants are some of the same problems that already exist with
altcoins.  I don't see how recursive covenants could make any of those
problems worse, and so I don't see any point in limiting Bitcoin's
flexibility to avoid those problems when there are so many interesting
and useful things that unlimited covenants could do.

-Dave


signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev