bitcoin scripting and lisp
17 messages, 7 to 22 Mar 2022. Started by Bram Cohen.
Bram Cohen (8), ZmnSCPxj (5), Anthony Towns (4)
Quoted text (11 lines)
> > After looking into it, I actually think chia lisp [1] gets pretty much all > the major design decisions pretty much right. There are obviously a few > changes needed given the differences in design between chia and bitcoin: > > - having secp256k1 signatures (and curve operations), instead of > BLS12-381 ones > > - adding tx introspection instead of having bundle-oriented CREATE_COIN, > and CREATE/ASSERT results [10] >
Bitcoin uses the UTXO model as opposed to Chia's Coin Set model. While these are close enough that it's often explained as Chia uses the UTXO model but that isn't technically true. Relevant to the above comment is that in the UTXO model transactions get passed to a scriptpubkey and it either assert fails or it doesn't, while in the coin set model each puzzle (scriptpubkey) gets run and either assert fails or returns a list of extra conditions it has, possibly including timelocks and creating new coins, paying fees, and other things.
If you're doing everything from scratch it's cleaner to go with the coin set model, but retrofitting onto existing Bitcoin it may be best to leave the UTXO model intact and compensate by adding a bunch more opcodes which are special to parsing Bitcoin transactions. The transaction format itself can be mostly left alone but to enable some of the extra tricks (mostly implementing capabilities) it's probably a good idea to make new conventions for how a transaction can have advisory information which specifies which of the inputs to a transaction is the parent of a specific output and also info which is used for communication between the UTXOs in a transaction.
But one could also make lisp-generated UTXOs be based off transactions which look completely trivial and have all their important information be stored separately in a new vbytes area. That works but results in a bit of a dual identity where some coins have both an old style id and a new style id which gunks up what
Quoted text (8 lines)
> > - serialization seems to be a bit verbose -- 100kB of serialized clvm > code from a random block gzips to 60kB; optimising the serialization > for small lists, and perhaps also for small literal numbers might be > a feasible improvement; though it's not clear to me how frequently > serialization size would be the limiting factor for cost versus > execution time or memory usage. >
A lot of this is because there's a hook for doing compression at the consensus layer which isn't being used aggressively yet. That one has the downside that the combined cost of transactions can add up very nonlinearly, but when you have constantly repeated bits of large boilerplate it gets close and there isn't much of an alternative. That said even with that form of compression maxxed out it's likely that gzip could still do some compression but that would be better done in the database and in wire protocol formats rather than changing the format which is hashed at the consensus layer.
Quoted text (5 lines)
> Pretty much all the opcodes in the first section are directly from chia > lisp, while all the rest are to complete the "bitcoin" functionality. > The last two are extensions that are more food for thought than a real > proposal. >
Are you thinking of this as a completely alternative script format or an extension to bitcoin script? They're radically different approaches and it's hard to see how they mix. Everything in lisp is completely sandboxed, and that functionality is important to a lot of things, and it's really normal to be given a reveal of a scriptpubkey and be able to rely on your parsing of it.
Quoted text (9 lines)
> There's two ways to think about upgradability here; if someday we want > to add new opcodes to the language -- perhaps something to validate zero > knowledge proofs or calculate sha3 or use a different ECC curve, or some > way to support cross-input signature aggregation, or perhaps it's just > that some snippets are very widely used and we'd like to code them in > C++ directly so they validate quicker and don't use up as much block > weight. One approach is to just define a new version of the language > via the tapleaf version, defining new opcodes however we like. >
A nice side benefit of sticking with the UTXO model is that the soft fork hook can be that all unknown opcodes make the entire thing automatically pass.
Quoted text (9 lines)
> > The other is to use the "softfork" opcode -- chia defines it as: > > (softfork cost code) > > though I think it would probably be better if it were > > (softfork cost version code) >
Since softfork has to date never been used that second parameter is technically completely ignored and could be anything at all. Most likely a convention including some kind of version information will be created the first time it's used. Also Chia shoves total cost into blocks at the consensus layer out of an abundance of caution although that isn't technically necessary.
[10] [9] The CREATE/ASSERT bundling stuff is interesting; and could be
Quoted text (6 lines)
> used to achieve functionality like the "transaction sponsorship" > stuff. It doesn't magically solve the issues with maintaining the > mempool and using that to speed up block acceptance, though, and > the chia chain has apparently suffered from mempool-flooding attacks > recently [11] so I don't think they've solved the broader problem, >
Chia's approach to transaction fees is essentially identical to Bitcoin's although a lot fewer things in the ecosystem support fees due to a lack of having needed it yet. I don't think mempool issues have much to do with choice of scriptpubkey language. which is mostly about adding in covenants and capabilities.
That said, Ethereum does have trivial aggregation of unrelated transactions, and the expense of almost everything else. There are a bunch of ways automatic aggregation functionality could be added to coin set mempools by giving them some understanding of the semantics of some transactions, but that hasn't been implemented yet.
I previously posted some thoughts about this here: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-December/019722.html
Good morning Bram,
Quoted text (1 line)
> while in the coin set model each puzzle (scriptpubkey) gets run and either assert fails or returns a list of extra conditions it has, possibly including timelocks and creating new coins, paying fees, and other things.
Does this mean it basically gets recursive covenants? Or is a condition in this list of conditions written a more restrictive language which itself cannot return a list of conditions?
Quoted text (8 lines)
> > - serialization seems to be a bit verbose -- 100kB of serialized clvm > > code from a random block gzips to 60kB; optimising the serialization > > for small lists, and perhaps also for small literal numbers might be > > a feasible improvement; though it's not clear to me how frequently > > serialization size would be the limiting factor for cost versus > > execution time or memory usage. > > A lot of this is because there's a hook for doing compression at the consensus layer which isn't being used aggressively yet. That one has the downside that the combined cost of transactions can add up very nonlinearly, but when you have constantly repeated bits of large boilerplate it gets close and there isn't much of an alternative. That said even with that form of compression maxxed out it's likely that gzip could still do some compression but that would be better done in the database and in wire protocol formats rather than changing the format which is hashed at the consensus layer.
How different is this from "jets" as proposed in Simplicity?
Quoted text (6 lines)
> > Pretty much all the opcodes in the first section are directly from chia > > lisp, while all the rest are to complete the "bitcoin" functionality. > > The last two are extensions that are more food for thought than a real > > proposal. > > Are you thinking of this as a completely alternative script format or an extension to bitcoin script? They're radically different approaches and it's hard to see how they mix. Everything in lisp is completely sandboxed, and that functionality is important to a lot of things, and it's really normal to be given a reveal of a scriptpubkey and be able to rely on your parsing of it.
I believe AJ is proposing a completely alternative format to OG Bitcoin SCRIPT. Basically, as I understand it, nothing in the design of Tapscript versions prevents us from completely changing the interpretation of Tapscript bytes, and use a completely different language. That is, we could designate a new Tapscript version as completely different from OG Bitcoin SCRIPT.
Regards, ZmnSCPxj
On Sun, Mar 06, 2022 at 10:26:47PM -0800, Bram Cohen via bitcoin-dev wrote:
Quoted text (11 lines)
> > After looking into it, I actually think chia lisp [1] gets pretty much all > > the major design decisions pretty much right. There are obviously a few > > changes needed given the differences in design between chia and bitcoin: > Bitcoin uses the UTXO model as opposed to Chia's Coin Set model. While > these are close enough that it's often explained as Chia uses the UTXO > model but that isn't technically true. Relevant to the above comment is > that in the UTXO model transactions get passed to a scriptpubkey and it > either assert fails or it doesn't, while in the coin set model each puzzle > (scriptpubkey) gets run and either assert fails or returns a list of extra > conditions it has, possibly including timelocks and creating new coins, > paying fees, and other things.
One way to match the way bitcoin do things, you could have the "list of extra conditions" encoded explicitly in the transaction via the annex, and then check the extra conditions when the script is executed.
Quoted text (10 lines)
> If you're doing everything from scratch it's cleaner to go with the coin > set model, but retrofitting onto existing Bitcoin it may be best to leave > the UTXO model intact and compensate by adding a bunch more opcodes which > are special to parsing Bitcoin transactions. The transaction format itself > can be mostly left alone but to enable some of the extra tricks (mostly > implementing capabilities) it's probably a good idea to make new > conventions for how a transaction can have advisory information which > specifies which of the inputs to a transaction is the parent of a specific > output and also info which is used for communication between the UTXOs in a > transaction.
I think the parent/child coin relationship is only interesting when "unrelated" spends can assert that the child coin is being created -- ie things along the lines of the "transaction sponsorship" proposal. My feeling is that complicates the mempool a bit much, so is best left for later, if done at all.
(I think the hard part of managing the extra conditions is mostly in keeping it efficient to manage the mempool and construct the most profitable blocks/bundles, rather than where the data goes)
Quoted text (5 lines)
> But one could also make lisp-generated UTXOs be based off transactions > which look completely trivial and have all their important information be > stored separately in a new vbytes area. That works but results in a bit of > a dual identity where some coins have both an old style id and a new style > id which gunks up what
We've already got a txid and a wtxid, adding more ids seems best avoided if possible...
Quoted text (6 lines)
> > Pretty much all the opcodes in the first section are directly from chia > > lisp, while all the rest are to complete the "bitcoin" functionality. > > The last two are extensions that are more food for thought than a real > > proposal. > Are you thinking of this as a completely alternative script format or an > extension to bitcoin script?
As an alternative to tapscript, so when constructing the merkle tree of scripts for a taproot address, you could have some of those scripts be in tapscript as it exists today with OP_CHECKSIG etc, and others could be in lisp. (You could then have an entirely lisp-based sub-merkle-tree of lisp fragments via sha256tree or similar of course)
Quoted text (5 lines)
> They're radically different approaches and > it's hard to see how they mix. Everything in lisp is completely sandboxed, > and that functionality is important to a lot of things, and it's really > normal to be given a reveal of a scriptpubkey and be able to rely on your > parsing of it.
The above prevents combining puzzles/solutions from multiple coin spends, but I don't think that's very attractive in bitcoin's context, the way it is for chia. I don't think it loses much else?
Quoted text (11 lines)
> > There's two ways to think about upgradability here; if someday we want > > to add new opcodes to the language -- perhaps something to validate zero > > knowledge proofs or calculate sha3 or use a different ECC curve, or some > > way to support cross-input signature aggregation, or perhaps it's just > > that some snippets are very widely used and we'd like to code them in > > C++ directly so they validate quicker and don't use up as much block > > weight. One approach is to just define a new version of the language > > via the tapleaf version, defining new opcodes however we like. > A nice side benefit of sticking with the UTXO model is that the soft fork > hook can be that all unknown opcodes make the entire thing automatically > pass.
I don't think that works well if you want to allow the spender (the puzzle solution) to be able to use opcodes introduced in a soft-fork (eg, for graftroot-like behaviour)?
Quoted text (5 lines)
> Chia's approach to transaction fees is essentially identical to Bitcoin's > although a lot fewer things in the ecosystem support fees due to a lack of > having needed it yet. I don't think mempool issues have much to do with > choice of scriptpubkey language. which is mostly about adding in covenants > and capabilities.
Having third parties be able to link their spends to yours complicates mempool behaviour a fair bit (see the discussions on pinning wrt lightning txs -- and that's only with direct participants being able to link transactions). But it's very much a second-order effect compared to having fees being a meaningful thing at all. It took, what, six or seven years for people to start actually using dynamic fees in bitcoin?
Quoted text (2 lines)
> I previously posted some thoughts about this here: > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-December/019722.html
I'm pretty skeptical about having a database of large script snippets that will hopefully be reused in the future.
On Mon, Mar 07, 2022 at 10:56:38PM +0000, ZmnSCPxj via bitcoin-dev wrote:
Quoted text (2 lines)
> > while in the coin set model each puzzle (scriptpubkey) gets run and either assert fails or returns a list of extra conditions it has, possibly including timelocks and creating new coins, paying fees, and other things. > Does this mean it basically gets recursive covenants?
In chia the "scriptPubKey" is the hash of a lisp program, and when you create a new coin, the "scriptPubKey" of the newly generated coin is also the output of a lisp program. So writing a quine gets you general recursive covenants in a pretty straight forward way, as I understand it.
Quoted text (8 lines)
> > > - serialization seems to be a bit verbose -- 100kB of serialized clvm > > > code from a random block gzips to 60kB; optimising the serialization > > > for small lists, and perhaps also for small literal numbers might be > > > a feasible improvement; though it's not clear to me how frequently > > > serialization size would be the limiting factor for cost versus > > > execution time or memory usage. > > A lot of this is because there's a hook for doing compression at the consensus layer which isn't being used aggressively yet. That one has the downside that the combined cost of transactions can add up very nonlinearly, but when you have constantly repeated bits of large boilerplate it gets close and there isn't much of an alternative. That said even with that form of compression maxxed out it's likely that gzip could still do some compression but that would be better done in the database and in wire protocol formats rather than changing the format which is hashed at the consensus layer. > How different is this from "jets" as proposed in Simplicity?
Rather than a "transaction" containing "inputs/outputs", chia has spend bundles that spend and create coins; and spend bundles can be merged together, so that a block only has a single spend bundle. That spend bundle joins all the puzzles (the programs that, when hashed match the scriptPubKey) and solutions (scriptSigs) for the coins being spent together.
I /think/ the compression hook would be to allow you to have the puzzles be (re)generated via another lisp program if that was more efficient than just listing them out. But I assume it would be turtles, err, lisp all the way down, no special C functions like with jets.
Quoted text (10 lines)
> > > Pretty much all the opcodes in the first section are directly from chia > > > lisp, while all the rest are to complete the "bitcoin" functionality. > > > The last two are extensions that are more food for thought than a real > > > proposal. > > > > Are you thinking of this as a completely alternative script format or an extension to bitcoin script? They're radically different approaches and it's hard to see how they mix. Everything in lisp is completely sandboxed, and that functionality is important to a lot of things, and it's really normal to be given a reveal of a scriptpubkey and be able to rely on your parsing of it. > > I believe AJ is proposing a completely alternative format to OG Bitcoin SCRIPT. > Basically, as I understand it, nothing in the design of Tapscript versions prevents us from completely changing the interpretation of Tapscript bytes, and use a completely different language. > That is, we could designate a new Tapscript version as completely different from OG Bitcoin SCRIPT.
BIP342 defines tapscript, and it's selected by the taproot leaf version 0xc0; this hypothetical lispy "btcscript" might be selected via taproot leaf version 0xc2 or similar (elements' tapscript variant is selected via version 0xc4).
Cheers, aj
Good morning aj et al.,
Quoted text (9 lines)
> > They're radically different approaches and > > it's hard to see how they mix. Everything in lisp is completely sandboxed, > > and that functionality is important to a lot of things, and it's really > > normal to be given a reveal of a scriptpubkey and be able to rely on your > > parsing of it. > > The above prevents combining puzzles/solutions from multiple coin spends, > but I don't think that's very attractive in bitcoin's context, the way > it is for chia. I don't think it loses much else?
But cross-input signature aggregation is a nice-to-have we want for Bitcoin, and, to me, cross-input sigagg is not much different from cross-input puzzle/solution compression.
For example you might have multiple HTLCs, with mostly the same code except for details like who the acceptor and offerrer are, exact hash, and timelock, and you could claim multiple HTLCs in a single tx and feed the details separately but the code for the HTLC is common to all of the HTLCs. You do not even need to come from the same protocol if multiple protocols use the same code for implementing HTLC.
Quoted text (15 lines)
> > > There's two ways to think about upgradability here; if someday we want > > > to add new opcodes to the language -- perhaps something to validate zero > > > knowledge proofs or calculate sha3 or use a different ECC curve, or some > > > way to support cross-input signature aggregation, or perhaps it's just > > > that some snippets are very widely used and we'd like to code them in > > > C++ directly so they validate quicker and don't use up as much block > > > weight. One approach is to just define a new version of the language > > > via the tapleaf version, defining new opcodes however we like. > > > A nice side benefit of sticking with the UTXO model is that the soft fork > > > hook can be that all unknown opcodes make the entire thing automatically > > > pass. > > I don't think that works well if you want to allow the spender (the > puzzle solution) to be able to use opcodes introduced in a soft-fork > (eg, for graftroot-like behaviour)?
This does not apply to current Bitcoin since we no longer accept a SCRIPT from the spender, we now have a witness stack. However, once we introduce opcodes that allow recursive covenants, it seems this is now a potential footgun if the spender can tell the puzzle SCRIPT to load some code that will then be used in the *next* UTXO created, and *then* the spender can claim it.
Hmmm.... Or maybe not? If the spender can already tell the puzzle SCRIPT to send the funds to a SCRIPT that is controlled by the spender, the spender can already tell the puzzle SCRIPT to forward the funds to a pubkey the spender controls. So this seems to be more like "do not write broken SCRIPTs"?
Quoted text (20 lines)
> > > > - serialization seems to be a bit verbose -- 100kB of serialized clvm > > > > code from a random block gzips to 60kB; optimising the serialization > > > > for small lists, and perhaps also for small literal numbers might be > > > > a feasible improvement; though it's not clear to me how frequently > > > > serialization size would be the limiting factor for cost versus > > > > execution time or memory usage. > > > > A lot of this is because there's a hook for doing compression at the consensus layer which isn't being used aggressively yet. That one has the downside that the combined cost of transactions can add up very nonlinearly, but when you have constantly repeated bits of large boilerplate it gets close and there isn't much of an alternative. That said even with that form of compression maxxed out it's likely that gzip could still do some compression but that would be better done in the database and in wire protocol formats rather than changing the format which is hashed at the consensus layer. > > > > How different is this from "jets" as proposed in Simplicity? > > Rather than a "transaction" containing "inputs/outputs", chia has spend > bundles that spend and create coins; and spend bundles can be merged > together, so that a block only has a single spend bundle. That spend > bundle joins all the puzzles (the programs that, when hashed match > the scriptPubKey) and solutions (scriptSigs) for the coins being spent > together. > > I /think/ the compression hook would be to allow you to have the puzzles > be (re)generated via another lisp program if that was more efficient > than just listing them out. But I assume it would be turtles, err, > lisp all the way down, no special C functions like with jets.
Eh, you could use Common LISP or a recent-enough RnRS Scheme to write a cryptocurrency node software, so "special C function" seems to overprivilege C... I suppose the more proper way to think of this is that jets are *equivalent to* some code in the hosted language, and have an *efficient implementation* in the hosting language. In this view, the current OG Bitcoin SCRIPT is the hosted language, and the C++ Bitcoin Core interpreter for it is in the hosting language C++.
LISP can be both the hosted and hosting language because it is easy to implement `eval` in LISP and you can write macros which transform small code snippets into larger code. LISP code generating *more* LISP code is pretty much what macros are.
Regards, ZmnSCPxj
On Mon, Mar 7, 2022 at 2:56 PM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
Quoted text (9 lines)
> > > while in the coin set model each puzzle (scriptpubkey) gets run and > either assert fails or returns a list of extra conditions it has, possibly > including timelocks and creating new coins, paying fees, and other things. > > Does this mean it basically gets recursive covenants? > Or is a condition in this list of conditions written a more restrictive > language which itself cannot return a list of conditions? >
The conditions language is extremely restrictive but does allow for recursive covenants through the route of specifying output scriptpubkeys/puzzles, which Bitcoin already sort of in principle supports except that Bitcoin script's ability to generate and parse transactions isn't quite up to the task.
Quoted text (12 lines)
> > A lot of this is because there's a hook for doing compression at the > consensus layer which isn't being used aggressively yet. That one has the > downside that the combined cost of transactions can add up very > nonlinearly, but when you have constantly repeated bits of large > boilerplate it gets close and there isn't much of an alternative. That said > even with that form of compression maxxed out it's likely that gzip could > still do some compression but that would be better done in the database and > in wire protocol formats rather than changing the format which is hashed at > the consensus layer. > > How different is this from "jets" as proposed in Simplicity? >
My vague impression is that Simplicity jets are meant to be for things like Sha3 rather than shared library code. It might be that the way to use it would be to implement CLVM opcodes be a bunch of Simplicity jets. Whether that would be making the CLVM irrelevant or going through a pointless bit of theatre to be based on Simplicity under the hood I don't know.
The compression hook is that in each block instead of there being a list of puzzle reveals and solutions there's a generator written in CLVM which outputs that list, and it can be passed the generators of old blocks from which it can pull out code snippits.
On Mon, Mar 7, 2022 at 5:27 PM Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (4 lines)
> One way to match the way bitcoin do things, you could have the "list of > extra conditions" encoded explicitly in the transaction via the annex, > and then check the extra conditions when the script is executed. >
The conditions are already basically what's in transactions. I think the only thing missing is the assertion about one's own id, which could be added in by, in addition to passing the scriptpubkey the transaction it's part of, also passing in the index of inputs which it itself is.
Quoted text (21 lines)
> > > If you're doing everything from scratch it's cleaner to go with the coin > > set model, but retrofitting onto existing Bitcoin it may be best to leave > > the UTXO model intact and compensate by adding a bunch more opcodes which > > are special to parsing Bitcoin transactions. The transaction format > itself > > can be mostly left alone but to enable some of the extra tricks (mostly > > implementing capabilities) it's probably a good idea to make new > > conventions for how a transaction can have advisory information which > > specifies which of the inputs to a transaction is the parent of a > specific > > output and also info which is used for communication between the UTXOs > in a > > transaction. > > I think the parent/child coin relationship is only interesting when > "unrelated" spends can assert that the child coin is being created -- ie > things along the lines of the "transaction sponsorship" proposal. My > feeling is that complicates the mempool a bit much, so is best left for > later, if done at all. >
The parent/child relationship is mostly about implementing capabilities. There's this fundamental trick, sort of the ollie of UTXO programming, where to make a coin have a capability you have a wrapper around an inner puzzle for it where the wrapper asserts 'my parent must either be the unique originator of this capability or also have this same wrapper' and it enforces that by being given a reveal of its parent and told/asserting its own id which it can derive from that parent. The main benefit of the coin set approach over UTXO is that it reduces the amount of stuff to be revealed and string mangling involved in the parentage check.
Quoted text (5 lines)
> > (I think the hard part of managing the extra conditions is mostly > in keeping it efficient to manage the mempool and construct the most > profitable blocks/bundles, rather than where the data goes) >
Not sure what you mean by this. Conditions map fairly closely with what's in Bitcoin transactions and are designed so to be monotonic and so the costs and fees are known up front. The only way two transactions can conflict with each other is if they both try to spend the same coin.
Quoted text (11 lines)
> > They're radically different approaches and > > it's hard to see how they mix. Everything in lisp is completely > sandboxed, > > and that functionality is important to a lot of things, and it's really > > normal to be given a reveal of a scriptpubkey and be able to rely on your > > parsing of it. > > The above prevents combining puzzles/solutions from multiple coin spends, > but I don't think that's very attractive in bitcoin's context, the way > it is for chia. I don't think it loses much else? >
Making something lisp-based be a completely alternative script type would also be my preferred approach.
Quoted text (8 lines)
> > A nice side benefit of sticking with the UTXO model is that the soft fork > > hook can be that all unknown opcodes make the entire thing automatically > > pass. > > I don't think that works well if you want to allow the spender (the > puzzle solution) to be able to use opcodes introduced in a soft-fork > (eg, for graftroot-like behaviour)? >
This is already the approach to soft forking in Bitcoin script and I don't see anything wrong with it. You shouldn't write scripts using previously unrecognized opcodes until after they've been soft forked into having real functionality, and if you do that and accidentally write an anyonecanspend that's your own fault.
Quoted text (4 lines)
> Having third parties be able to link their spends to yours complicates > mempool behaviour a fair bit (see the discussions on pinning wrt > lightning txs -- and that's only with direct participants being able to > link transactions).
Bitcoin already has that with spending of transaction outputs, and Chia's mempool doesn't currently let transactions depend on other transactions in the mempool. If you do have that sort of dependency, you should have to smush both transactions together to make a single larger transaction and make it have enough of a fee to replace the smaller one.
I'm pretty skeptical about having a database of large script snippets
Quoted text (2 lines)
> that will hopefully be reused in the future. >
That database is just the list of old blocks which can be dredged up to have code pulled out of them.
Quoted text (5 lines)
> In chia the "scriptPubKey" is the hash of a lisp program, and when you > create a new coin, the "scriptPubKey" of the newly generated coin is > also the output of a lisp program. So writing a quine gets you general > recursive covenants in a pretty straight forward way, as I understand it. >
Usually you don't quite write a quine because you can be passed in your own code and assert your own id derived from it, but that's the basic idea. You need to validate your own id anyway when you have a capability.
Quoted text (7 lines)
> Rather than a "transaction" containing "inputs/outputs", chia has spend > bundles that spend and create coins; and spend bundles can be merged > together, so that a block only has a single spend bundle. That spend > bundle joins all the puzzles (the programs that, when hashed match > the scriptPubKey) and solutions (scriptSigs) for the coins being spent > together. >
I often refer to spend bundles as 'transactions'. Hope that isn't too confusing. They serve the same function in the mempool.
Quoted text (4 lines)
> > I /think/ the compression hook would be to allow you to have the puzzles > be (re)generated via another lisp program if that was more efficient > than just listing them out.
It literally has a lisp program called the generator which returns the list of puzzle reveals and transactions. The simplest version of that program is to return a quoted list.
On Mon, Mar 7, 2022 at 7:06 PM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
Quoted text (5 lines)
> > But cross-input signature aggregation is a nice-to-have we want for > Bitcoin, and, to me, cross-input sigagg is not much different from > cross-input puzzle/solution compression. >
Cross-input signature aggregation has a lot of headaches unless you're using BLS signatures, in which case you always aggregate everything all the time because it can be done after the fact noninteractively. In that case it makes sense to have a special aggregated signature which always comes with a transaction or block. But it might be a bit much to bundle both lisp and BLS support into one big glop.
Quoted text (8 lines)
> > For example you might have multiple HTLCs, with mostly the same code > except for details like who the acceptor and offerrer are, exact hash, and > timelock, and you could claim multiple HTLCs in a single tx and feed the > details separately but the code for the HTLC is common to all of the HTLCs. > You do not even need to come from the same protocol if multiple protocols > use the same code for implementing HTLC. >
HTLCs, at least in Chia, have embarrassingly little code in them. Like, so little that there's almost nothing to compress.
Quoted text (3 lines)
> This does not apply to current Bitcoin since we no longer accept a SCRIPT > from the spender, we now have a witness stack. >
My mental model of Bitcoin is to pretend that segwit was always there and the separation of different sections of data is a semantic quibble.
Quoted text (2 lines)
> So this seems to be more like "do not write broken SCRIPTs"? >
In general if people footgun that's their own fault. The resistance to covenants and capabilities in the past has largely been around what would happen if you had opt-out covenants which acted as riders and could monkey around in later spends which were none of their business. But if they're fully baked into the scriptpubkey then they're opted into by the recipient and there aren't any weird surprises.
Good morning Bram,
Quoted text (5 lines)
> On Mon, Mar 7, 2022 at 7:06 PM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote: > > > But cross-input signature aggregation is a nice-to-have we want for Bitcoin, and, to me, cross-input sigagg is not much different from cross-input puzzle/solution compression. > > Cross-input signature aggregation has a lot of headaches unless you're using BLS signatures, in which case you always aggregate everything all the time because it can be done after the fact noninteractively. In that case it makes sense to have a special aggregated signature which always comes with a transaction or block. But it might be a bit much to bundle both lisp and BLS support into one big glop.
You misunderstand my point.
I am not saying "we should add sigagg and lisp together!"
I am pointing out that:
* We want to save bytes by having multiple inputs of a transaction use the same single signature (i.e. sigagg).
is not much different from:
* We want to save bytes by having multiple inputs of a transaction use the same `scriptPubKey` template.
Quoted text (4 lines)
> > For example you might have multiple HTLCs, with mostly the same code except for details like who the acceptor and offerrer are, exact hash, and timelock, and you could claim multiple HTLCs in a single tx and feed the details separately but the code for the HTLC is common to all of the HTLCs. > > You do not even need to come from the same protocol if multiple protocols use the same code for implementing HTLC. > > HTLCs, at least in Chia, have embarrassingly little code in them. Like, so little that there's almost nothing to compress.
In Bitcoin at least an HTLC has, if you remove the `OP_PUSH`es, by my count, 13 bytes. If you have a bunch of HTLCs you want to claim, you can reduce your witness data by 13 bytes minus whatever number of bytes you need to indicate this. That amounts to about 3 vbytes per HTLC, which can be significant enough to be worth it (consider that Taproot moving away from encoded signatures saves only 9 weight units per signature, i.e. about 2 vbytes).
Do note that PTLCs remain more space-efficient though, so forget about HTLCs and just use PTLCs.
Quoted text (4 lines)
> > > This does not apply to current Bitcoin since we no longer accept a SCRIPT from the spender, we now have a witness stack. > > My mental model of Bitcoin is to pretend that segwit was always there and the separation of different sections of data is a semantic quibble.
This is not a semantic quibble --- `witness` contains only the equivalent of `OP_PUSH`es, while `scriptSig` can in theory contain non-`OP_PUSH` opcodes. xref. `1 RETURN`.
As-is, with SegWit the spender no longer is able to provide any SCRIPT at all, but new opcodes may allow the spender to effectively inject any SCRIPT they want, once again, because `witness` data may now become code.
Quoted text (1 line)
> But if they're fully baked into the scriptpubkey then they're opted into by the recipient and there aren't any weird surprises.
This is really what I kinda object to. Yes, "buyer beware", but consider that as the covenant complexity increases, the probability of bugs, intentional or not, sneaking in, increases as well. And a bug is really "a weird surprise" --- xref TheDAO incident.
This makes me kinda wary of using such covenant features at all, and if stuff like `SIGHASH_ANYPREVOUT` or `OP_CHECKTEMPLATEVERIFY` are not added but must be reimplemented via a covenant feature, I would be saddened, as I now have to contend with the complexity of covenant features and carefully check that `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` were implemented correctly. True I also still have to check the C++ source code if they are implemented directly as opcodes, but I can read C++ better than frikkin Bitcoin SCRIPT. Not to mention that I now have to review both the (more complicated due to more general) covenant feature implementation, *and* the implementation of `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` in terms of the covenant feature.
Regards, ZmnSCPxj
On Tue, Mar 08, 2022 at 06:54:56PM -0800, Bram Cohen via bitcoin-dev wrote:
Quoted text (8 lines)
> On Mon, Mar 7, 2022 at 5:27 PM Anthony Towns <aj@erisian•com•au> wrote: > > One way to match the way bitcoin do things, you could have the "list of > > extra conditions" encoded explicitly in the transaction via the annex, > > and then check the extra conditions when the script is executed. > The conditions are already basically what's in transactions. I think the > only thing missing is the assertion about one's own id, which could be > added in by, in addition to passing the scriptpubkey the transaction it's > part of, also passing in the index of inputs which it itself is.
To redo the singleton pattern in bitcoin's context, I think you'd have to pass in both the full tx you're spending (to be able to get the txid of its parent) and the full tx of its parent (to be able to get the scriptPubKey that your utxo spent) which seems klunky but at least possible (you'd be able to drop the witness data at least; without that every tx would be including the entire history of the singleton).
Quoted text (8 lines)
> > > A nice side benefit of sticking with the UTXO model is that the soft fork > > > hook can be that all unknown opcodes make the entire thing automatically > > > pass. > > I don't think that works well if you want to allow the spender (the > > puzzle solution) to be able to use opcodes introduced in a soft-fork > > (eg, for graftroot-like behaviour)? > This is already the approach to soft forking in Bitcoin script and I don't > see anything wrong with it.
It's fine in Bitcoin script, because the scriptPubKey already commits to all the opcodes that can possibly be used for any particular output. With a lisp approach, however, you could pass in additional code fragments to execute. For example, where you currently say:
script: [pubkey] CHECKSIG witness: [64B signature][0x83]
(where 0x83 is SINGLE|ANYONECANPAY) you might translate that to:
script: (checksig pubkey (bip342-txmsg 3) 2) witness: signature 0x83
where "3" grabs the sighash byte, and "2" grabs the signature. But you could also translate it to:
script: (checksig pubkey (sha256 3 (a 3)) 2) witness: signature (bip342-txmsg 0x83)
where "a 3" takes "(bip342-txmsg 0x83)" then evaluates it, and (sha256 3 (a 3)) makes sure you've signed off on both how the message was constructed as well as what the message was. The advantage there is that the spender can then create their own signature hashes however they like; even ones that hadn't been thought of when the output was created.
But what if we later softfork in a bip118-txmsg for quick and easy ANYPREVOUT style-signatures, and want to use that instead of custom lisp code? You can't just stick (softfork C (bip118-txmsg 0xc3)) into the witness, because it will evaluate to nil and you won't be signing anything. But you *could* change the script to something like:
script: (softfork C (q checksigverify pubkey (a 3) 2)) witness: signature (bip118-txmsg 0xc3)
But what happens if the witness instead has:
script: (softfork C (q checksigverify pubkey (a 3) 2)) witness: fake-signature (fakeopcode 0xff)
If softfork is just doing a best effort for whatever opcodes it knows about, and otherwise succeeding, then it has to succeed, and your script/output has become anyone-can-spend.
On the other hand, if you could tell the softfork op that you only wanted ops up-to-and-including the 118 softfork, then it could reject fakeopcode and fail the script, which I think gives the desirable behaviour.
Cheers, aj
On Tue, Mar 08, 2022 at 03:06:43AM +0000, ZmnSCPxj via bitcoin-dev wrote:
Quoted text (9 lines)
> > > They're radically different approaches and > > > it's hard to see how they mix. Everything in lisp is completely sandboxed, > > > and that functionality is important to a lot of things, and it's really > > > normal to be given a reveal of a scriptpubkey and be able to rely on your > > > parsing of it. > > The above prevents combining puzzles/solutions from multiple coin spends, > > but I don't think that's very attractive in bitcoin's context, the way > > it is for chia. I don't think it loses much else? > But cross-input signature aggregation is a nice-to-have we want for Bitcoin, and, to me, cross-input sigagg is not much different from cross-input puzzle/solution compression.
Signature aggregation has a lot more maths and crypto involved than reversible compression of puzzles/solutions. I was more meaning cross-transaction relationships rather than cross-input ones though.
Quoted text (5 lines)
> > I /think/ the compression hook would be to allow you to have the puzzles > > be (re)generated via another lisp program if that was more efficient > > than just listing them out. But I assume it would be turtles, err, > > lisp all the way down, no special C functions like with jets. > Eh, you could use Common LISP or a recent-enough RnRS Scheme to write a cryptocurrency node software, so "special C function" seems to overprivilege C...
Jets are "special" in so far as they are costed differently at the consensus level than the equivalent pure/jetless simplicity code that they replace. Whether they're written in C or something else isn't the important part.
By comparison, generating lisp code with lisp code in chia doesn't get special treatment.
(You *could* also use jets in a way that doesn't impact consensus just to make your node software more efficient in the normal case -- perhaps via a JIT compiler that sees common expressions in the blockchain and optimises them eg)
On Wed, Mar 09, 2022 at 02:30:34PM +0000, ZmnSCPxj via bitcoin-dev wrote:
Quoted text (1 line)
> Do note that PTLCs remain more space-efficient though, so forget about HTLCs and just use PTLCs.
Note that PTLCs aren't really Chia-friendly, both because chia doesn't have secp256k1 operations in the first place, but also because you can't do a scriptless-script because the information you need to extract is lost when signatures are non-interactively aggregated via BLS -- so that adds an expensive extra ECC operation rather than reusing an op you're already paying for (scriptless script PTLCs) or just adding a cheap hash operation (HTLCs).
(Pretty sure Chia could do (= PTLC (pubkey_for_exp PREIMAGE)) for preimage reveal of BLS PTLCs, but that wouldn't be compatible with bitcoin secp256k1 PTLCs. You could sha256 the PTLC to save a few bytes, but I think given how much a sha256 opcode costs in Chia, that that would actually be more expensive?)
None of that applies to a bitcoin implementation that doesn't switch to BLS signatures though.
Quoted text (4 lines)
> > But if they're fully baked into the scriptpubkey then they're opted into by the recipient and there aren't any weird surprises. > This is really what I kinda object to. > Yes, "buyer beware", but consider that as the covenant complexity increases, the probability of bugs, intentional or not, sneaking in, increases as well. > And a bug is really "a weird surprise" --- xref TheDAO incident.
Which is better: a bug in the complicated script code specified for implementing eltoo in a BOLT; or a bug in the BIP/implementation of a new sighash feature designed to make it easy to implement eltoo, that's been soft-forked into consensus?
Seems to me, that it's always better to have the bug be at the wallet level, since that can be fixed by upgrading individual wallet software.
Quoted text (2 lines)
> This makes me kinda wary of using such covenant features at all, and if stuff like `SIGHASH_ANYPREVOUT` or `OP_CHECKTEMPLATEVERIFY` are not added but must be reimplemented via a covenant feature, I would be saddened, as I now have to contend with the complexity of covenant features and carefully check that `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` were implemented correctly. > True I also still have to check the C++ source code if they are implemented directly as opcodes, but I can read C++ better than frikkin Bitcoin SCRIPT.
If OP_CHECKTEMPLATEVERIFY (etc) is implemented as a consensus update, you probably want to review the C++ code even if you're not going to use it, just to make sure consensus doesn't end up broken as a result. Whereas if it's only used by other people's wallets, you might be able to ignore it entirely (at least until it becomes so common that any bugs might allow a significant fraction of BTC to be stolen/lost and indirectly cause a systemic risk).
Quoted text (1 line)
> Not to mention that I now have to review both the (more complicated due to more general) covenant feature implementation, *and* the implementation of `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` in terms of the covenant feature.
I'm not sure that a "covenant language implementation" would necessarily be "that" complicated. And if so, having a DSL for covenants could, at least in theory, make for a much simpler implementation of ANYPREVOUT/CTV/TLUV/EVICT/etc than doing it directly in C++, which might mean those things are less likely to have "weird surprises" rather than more.
Cheers, aj
On Wed, Mar 9, 2022 at 6:30 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
Quoted text (10 lines)
> I am pointing out that: > > * We want to save bytes by having multiple inputs of a transaction use the > same single signature (i.e. sigagg). > > is not much different from: > > * We want to save bytes by having multiple inputs of a transaction use the > same `scriptPubKey` template. >
Fair point. In the past Bitcoin has been resistant to such things because for example reusing pubkeys can save you from having to separately pay for the reveals of all of them but letting people get credit for that incentivizes key reuse which isn't such a great thing.
Quoted text (20 lines)
> > > > For example you might have multiple HTLCs, with mostly the same code > except for details like who the acceptor and offerrer are, exact hash, and > timelock, and you could claim multiple HTLCs in a single tx and feed the > details separately but the code for the HTLC is common to all of the HTLCs. > > > You do not even need to come from the same protocol if multiple > protocols use the same code for implementing HTLC. > > > > HTLCs, at least in Chia, have embarrassingly little code in them. Like, > so little that there's almost nothing to compress. > > In Bitcoin at least an HTLC has, if you remove the `OP_PUSH`es, by my > count, 13 bytes. > If you have a bunch of HTLCs you want to claim, you can reduce your > witness data by 13 bytes minus whatever number of bytes you need to > indicate this. > That amounts to about 3 vbytes per HTLC, which can be significant enough > to be worth it (consider that Taproot moving away from encoded signatures > saves only 9 weight units per signature, i.e. about 2 vbytes). >
Oh I see. That's already extremely small overhead. When you start optimizing at that level you wind up doing things like pulling all the HTLCs into the same block to take the overhead of pulling in the template only once.
Quoted text (4 lines)
> > Do note that PTLCs remain more space-efficient though, so forget about > HTLCs and just use PTLCs. >
It makes a lot of sense to make a payment channel system using PTLCs and eltoo right off the bat but then you wind up rewriting everything from scratch.
Quoted text (11 lines)
> > > This does not apply to current Bitcoin since we no longer accept a > SCRIPT from the spender, we now have a witness stack. > > > > My mental model of Bitcoin is to pretend that segwit was always there > and the separation of different sections of data is a semantic quibble. > > This is not a semantic quibble --- `witness` contains only the equivalent > of `OP_PUSH`es, while `scriptSig` can in theory contain non-`OP_PUSH` > opcodes. > xref. `1 RETURN`. >
It's very normal when you're using lisp for snippets of code to be passed in as data and then verified and executed. That's enabled by the extreme adherence to no side effects.
Quoted text (7 lines)
> This makes me kinda wary of using such covenant features at all, and if > stuff like `SIGHASH_ANYPREVOUT` or `OP_CHECKTEMPLATEVERIFY` are not added > but must be reimplemented via a covenant feature, I would be saddened, as I > now have to contend with the complexity of covenant features and carefully > check that `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` were implemented > correctly. >
Even the 'standard format' transaction which supports taproot and graftroot is implemented in CLVM. The benefit of this approach is that new functionality can be implemented and deployed immediately rather than having to painstakingly go through a soft fork deployment for each thing.
On Wed, Mar 9, 2022 at 10:47 PM Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (8 lines)
> > To redo the singleton pattern in bitcoin's context, I think you'd have > to pass in both the full tx you're spending (to be able to get the > txid of its parent) and the full tx of its parent (to be able to get > the scriptPubKey that your utxo spent) which seems klunky but at least > possible (you'd be able to drop the witness data at least; without that > every tx would be including the entire history of the singleton). >
Yes that's the idea. Since the parent transaction is in the blockchain it could be pulled in automatically without having to charge vbytes for it.
Quoted text (4 lines)
> If softfork is just doing a best effort for whatever opcodes it knows > about, and otherwise succeeding, then it has to succeed, and your > script/output has become anyone-can-spend. >
That can be alleviated by when things call untrusted code they can wrap it in a guard which can be the soft fork opcode itself.
Quoted text (5 lines)
> > On the other hand, if you could tell the softfork op that you only wanted > ops up-to-and-including the 118 softfork, then it could reject fakeopcode > and fail the script, which I think gives the desirable behaviour. >
A simple approach to versioning like that may be more expedient. Soft forking in CLVM isn't implemented yet.
On Thu, Mar 10, 2022 at 8:46 PM Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (8 lines)
> Note that PTLCs aren't really Chia-friendly, both because chia doesn't > have secp256k1 operations in the first place, but also because you can't > do a scriptless-script because the information you need to extract > is lost when signatures are non-interactively aggregated via BLS -- > so that adds an expensive extra ECC operation rather than reusing an > op you're already paying for (scriptless script PTLCs) or just adding > a cheap hash operation (HTLCs). >
The CLVM currently supports BLS12-381 group 1 point operations which it uses to support taproot which I think is enough to support PTLCs but obviously isn't compatible with secp. In the future there will likely be a soft fork to include a complete set of BLS12-381 operations mostly to support ZK implementation.
Good morning aj et al.,
Quoted text (15 lines)
> On Tue, Mar 08, 2022 at 03:06:43AM +0000, ZmnSCPxj via bitcoin-dev wrote: > > > > > They're radically different approaches and > > > > it's hard to see how they mix. Everything in lisp is completely sandboxed, > > > > and that functionality is important to a lot of things, and it's really > > > > normal to be given a reveal of a scriptpubkey and be able to rely on your > > > > parsing of it. > > > > The above prevents combining puzzles/solutions from multiple coin spends, > > > > but I don't think that's very attractive in bitcoin's context, the way > > > > it is for chia. I don't think it loses much else? > > > > But cross-input signature aggregation is a nice-to-have we want for Bitcoin, and, to me, cross-input sigagg is not much different from cross-input puzzle/solution compression. > > Signature aggregation has a lot more maths and crypto involved than > reversible compression of puzzles/solutions. I was more meaning > cross-transaction relationships rather than cross-input ones though.
My point is that in the past we were willing to discuss the complicated crypto math around cross-input sigagg in order to save bytes, so it seems to me that cross-input compression of puzzles/solutions at least merits a discussion, since it would require a lot less heavy crypto math, and *also* save bytes.
Quoted text (13 lines)
> > > I /think/ the compression hook would be to allow you to have the puzzles > > > be (re)generated via another lisp program if that was more efficient > > > than just listing them out. But I assume it would be turtles, err, > > > lisp all the way down, no special C functions like with jets. > > > Eh, you could use Common LISP or a recent-enough RnRS Scheme to write a cryptocurrency node software, so "special C function" seems to overprivilege C... > > Jets are "special" in so far as they are costed differently at the > consensus level than the equivalent pure/jetless simplicity code that > they replace. Whether they're written in C or something else isn't the > important part. > > By comparison, generating lisp code with lisp code in chia doesn't get > special treatment.
Hmm, what exactly do you mean here?
If I have a shorter piece of code that expands to a larger piece of code because metaprogramming, is it considered the same cost as the larger piece of code (even if not all parts of the larger piece of code are executed, e.g. branches)?
Or is the cost simply proportional to the number of operations actually executed?
I think there are two costs here:
* Cost of bytes to transmit over the network. * Cost of CPU load.
Over here in Bitcoin we have been mostly conflating the two, to the point that Taproot even eliminates unexecuted branches from being transmitted over the network so that bytes transmitted is approximately equal to opcodes executed.
It seems to me that lisp-generating-lisp compression would reduce the cost of bytes transmitted, but increase the CPU load (first the metaprogram runs, and *then* the produced program runs).
Quoted text (4 lines)
> (You could also use jets in a way that doesn't impact consensus just > to make your node software more efficient in the normal case -- perhaps > via a JIT compiler that sees common expressions in the blockchain and > optimises them eg)
I believe that is relevant in the other thread about Jets that I and Billy forked off from `OP_FOLD`?
Over in that thread, we seem to have largely split jets into two types:
* Consensus-critical jets which need a softfork but reduce the weight of the jetted code (and which are invisible to pre-softfork nodes). * Non-consensus-critical jets which only need relay change and reduces bytes sent, but keeps the weight of the jetted code.
It seems to me that lisp-generating-lisp compression would roughly fall into the "non-consensus-critical jets", roughly.
Quoted text (20 lines)
> On Wed, Mar 09, 2022 at 02:30:34PM +0000, ZmnSCPxj via bitcoin-dev wrote: > > > Do note that PTLCs remain more space-efficient though, so forget about HTLCs and just use PTLCs. > > Note that PTLCs aren't really Chia-friendly, both because chia doesn't > have secp256k1 operations in the first place, but also because you can't > do a scriptless-script because the information you need to extract > is lost when signatures are non-interactively aggregated via BLS -- > so that adds an expensive extra ECC operation rather than reusing an > op you're already paying for (scriptless script PTLCs) or just adding > a cheap hash operation (HTLCs). > > (Pretty sure Chia could do (= PTLC (pubkey_for_exp PREIMAGE)) for > preimage reveal of BLS PTLCs, but that wouldn't be compatible with > bitcoin secp256k1 PTLCs. You could sha256 the PTLC to save a few bytes, > but I think given how much a sha256 opcode costs in Chia, that that > would actually be more expensive?) > > None of that applies to a bitcoin implementation that doesn't switch to > BLS signatures though.
Not being a mathist, I have absolutely no idea, but: at least as I understood from the original mimblewimble.txt from Voldemort, BLS signatures had an additional assumption, which I *think* means "theoretically less secure than SECP256K1 Schnorr / ECDSA". Is my understanding correct? And if so, how theoretical would that be?
PTLC signatures have the very nice property of being indistinguishable from non-PTLC signatures to anyone without the adaptor, and I think privacy-by-default should be what we encourage.
Quoted text (12 lines)
> > > But if they're fully baked into the scriptpubkey then they're opted into by the recipient and there aren't any weird surprises. > > > This is really what I kinda object to. > > > Yes, "buyer beware", but consider that as the covenant complexity increases, the probability of bugs, intentional or not, sneaking in, increases as well. > > > And a bug is really "a weird surprise" --- xref TheDAO incident. > > Which is better: a bug in the complicated script code specified for > implementing eltoo in a BOLT; or a bug in the BIP/implementation of a > new sighash feature designed to make it easy to implement eltoo, that's > been soft-forked into consensus? > > Seems to me, that it's always better to have the bug be at the wallet > level, since that can be fixed by upgrading individual wallet software.
Good point.
Though I should note that BIP-118 was originally proposed with a 5-line patch, so ---
Quoted text (6 lines)
> I'm not sure that a "covenant language implementation" would necessarily > be "that" complicated. And if so, having a DSL for covenants could, > at least in theory, make for a much simpler implementation of > ANYPREVOUT/CTV/TLUV/EVICT/etc than doing it directly in C++, which > might mean those things are less likely to have "weird surprises" rather > than more.
<rant> DSLs? Domain-specific languages?
Do you know how many people hate autoconf? That is because autoconf is secretly an embedded DSL in a really obscure language called `m4`. Some of the `autoconf` weirdnesses are due precisely to having to hack `m4` to make it look nicer, like that weird rule to use double `[[` and `]]` quotes around sections of program source code. Yes, it means we can have a nice `autoconf-archive`, but the actual code inside that archive? People *making*`autoconf` macros have to learn both `m4` and the existing `autoconf` macro ecosystem.
Then there is BluespecSV. Bluespec used to be an embedded DSL inside Haskell. Nobody wanted it because they had to learn *two* languages, Haskell, and Bluespec. Eventually they created BluespecSV, which was a language with completely separate grammar and tokens from Haskell, instead of embedded in it, and Bluespec was finally *actually* used in production. But the damage was done: people who do digital hardware design tend to *bristle* when they hear the word "Haskell", because of all the horrible embedded DSLs in Haskell (Bluespec was just one, but I have heard of a few others which never managed to jump from being more than a lab toy, including a cute one where the on-FPGA layout of the circuit was part of the construction of the circuit description).
Embedded DSLs are cute, but they require learning two languages, not a single new one. Just say no to embedded DSLs! </rant>
Ah, much better.
This seems to me to be not much different from adding a separate compiler, which translates from the surface language to the underlying opcode/lisp language, with similar risks: now you have *another* bit of indirection to audit. It feels like building a perpetual-motion machine, where we keep adding more stuff in the hope of reducing the complexity.
Regards, ZmnSCPxj
Good morning Bram,
Quoted text (11 lines)
> On Wed, Mar 9, 2022 at 6:30 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote: > > > I am pointing out that: > > > > * We want to save bytes by having multiple inputs of a transaction use the same single signature (i.e. sigagg). > > > > is not much different from: > > > > * We want to save bytes by having multiple inputs of a transaction use the same `scriptPubKey` template. > > Fair point. In the past Bitcoin has been resistant to such things because for example reusing pubkeys can save you from having to separately pay for the reveals of all of them but letting people get credit for that incentivizes key reuse which isn't such a great thing.
See paragraph below:
Quoted text (2 lines)
> > > > For example you might have multiple HTLCs, with mostly the same code except for details like who the acceptor and offerrer are, exact hash, and timelock, and you could claim multiple HTLCs in a single tx and feed the details separately but the code for the HTLC is common to all of the HTLCs. > > > > You do not even need to come from the same protocol if multiple protocols use the same code for implementing HTLC.
Note that the acceptor and offerrer are represented by pubkeys here. So we do not want to encourage key reuse, we want to encourage reuse of *how* the pubkeys are used (but rotate the pubkeys).
In the other thread on Jets in bitcoin-dev I proposed moving data like pubkeys into a separate part of the SCRIPT in order to (1) not encourage key reuse and (2) make it easier to compress the code. In LISP terms, it would be like requiring that top-level code have a `(let ...)` form around it where the assigned data *must* be constants or `quote`, and disallowing constants and `quote` elsewhere, then any generated LISP code has to execute in the same top-level environment defined by this top-level `let`.
So you can compress the code by using some metaprogramming where LISP generates LISP code but you still need to work within the confines of the available constants.
Quoted text (12 lines)
> > > HTLCs, at least in Chia, have embarrassingly little code in them. Like, so little that there's almost nothing to compress. > > > > In Bitcoin at least an HTLC has, if you remove the `OP_PUSH`es, by my count, 13 bytes. > > If you have a bunch of HTLCs you want to claim, you can reduce your witness data by 13 bytes minus whatever number of bytes you need to indicate this. > > That amounts to about 3 vbytes per HTLC, which can be significant enough to be worth it (consider that Taproot moving away from encoded signatures saves only 9 weight units per signature, i.e. about 2 vbytes). > > Oh I see. That's already extremely small overhead. When you start optimizing at that level you wind up doing things like pulling all the HTLCs into the same block to take the overhead of pulling in the template only once. > > > > Do note that PTLCs remain more space-efficient though, so forget about HTLCs and just use PTLCs. > > It makes a lot of sense to make a payment channel system using PTLCs and eltoo right off the bat but then you wind up rewriting everything from scratch.
Bunch of #reckless devs implemented Lightning with just HTLCs so that is that, *shrug*, gotta wonder what those people were thinking, not waiting for PTLCs.
Quoted text (10 lines)
> > > > > > This does not apply to current Bitcoin since we no longer accept a SCRIPT from the spender, we now have a witness stack. > > > > > > My mental model of Bitcoin is to pretend that segwit was always there and the separation of different sections of data is a semantic quibble. > > > > This is not a semantic quibble --- `witness` contains only the equivalent of `OP_PUSH`es, while `scriptSig` can in theory contain non-`OP_PUSH` opcodes. > > xref. `1 RETURN`. > > It's very normal when you're using lisp for snippets of code to be passed in as data and then verified and executed. That's enabled by the extreme adherence to no side effects.
Quining still allows Turing-completeness and infinite loops, which *is* still a side effect, though as I understand it ChiaLISP uses the "Turing-complete but with a max number of ops" kind of totality.
Quoted text (3 lines)
> > This makes me kinda wary of using such covenant features at all, and if stuff like `SIGHASH_ANYPREVOUT` or `OP_CHECKTEMPLATEVERIFY` are not added but must be reimplemented via a covenant feature, I would be saddened, as I now have to contend with the complexity of covenant features and carefully check that `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` were implemented correctly. > > Even the 'standard format' transaction which supports taproot and graftroot is implemented in CLVM. The benefit of this approach is that new functionality can be implemented and deployed immediately rather than having to painstakingly go through a soft fork deployment for each thing.
Wow, just wow.
Regards, ZmnSCPxj
On Wed, Mar 16, 2022 at 7:54 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
Quoted text (6 lines)
> My point is that in the past we were willing to discuss the complicated > crypto math around cross-input sigagg in order to save bytes, so it seems > to me that cross-input compression of puzzles/solutions at least merits a > discussion, since it would require a lot less heavy crypto math, and *also* > save bytes. >
When using BLS signatures all that math is much simpler. You use a single aggregated signature and always aggregate everything all the time.
I think there are two costs here:
Quoted text (4 lines)
> > * Cost of bytes to transmit over the network. > * Cost of CPU load. >
There are three potential costs: CPU, bytes, and making outputs. In Chia it's balanced so that the costs to a standard transaction in all three buckets are roughly the same. In Bitcoin the three are implicitly tied to each other by design which makes vbytes work okayish for Bitcoin Script as it exists today.
Quoted text (4 lines)
> It seems to me that lisp-generating-lisp compression would reduce the cost > of bytes transmitted, but increase the CPU load (first the metaprogram > runs, and *then* the produced program runs). >
Nah, CPU costs are dominated by signatures. Simple operations like applying some parameters to a template don't add much.
Quoted text (7 lines)
> Not being a mathist, I have absolutely no idea, but: at least as I > understood from the original mimblewimble.txt from Voldemort, BLS > signatures had an additional assumption, which I *think* means > "theoretically less secure than SECP256K1 Schnorr / ECDSA". > Is my understanding correct? > And if so, how theoretical would that be? >
It includes some an extra cryptographic assumption but it's extremely theoretical, having more to do with guessing what size of group provides comparable security in number of bits than whether the whole approach is in question. BLS12-381 is fairly conservative.
Quoted text (5 lines)
> > PTLC signatures have the very nice property of being indistinguishable > from non-PTLC signatures to anyone without the adaptor, and I think > privacy-by-default should be what we encourage. >
You do lose out on that when you aggregate.
Quoted text (11 lines)
> > I'm not sure that a "covenant language implementation" would necessarily > > be "that" complicated. And if so, having a DSL for covenants could, > > at least in theory, make for a much simpler implementation of > > ANYPREVOUT/CTV/TLUV/EVICT/etc than doing it directly in C++, which > > might mean those things are less likely to have "weird surprises" rather > > than more. > > <rant> > DSLs? > Domain-specific languages? >
Bitcoin Script is already a domain specific language, and the point of adding in a lisp-family language would be to make it so that covenants and capabilities can be implemented in the same language as is used for regular coin scripting. The idea is to get off the treadmill of soft forking in language features every time new functionality is wanted and make it possible to implement all that on chain.
On Wed, Mar 16, 2022 at 02:54:05PM +0000, ZmnSCPxj via bitcoin-dev wrote:
Quoted text (1 line)
> My point is that in the past we were willing to discuss the complicated crypto math around cross-input sigagg in order to save bytes, so it seems to me that cross-input compression of puzzles/solutions at least merits a discussion, since it would require a lot less heavy crypto math, and *also* save bytes.
Maybe it would be; but it's not something I was intending to bring up in this thread.
Chia allows any coin spend to reference any output created in the same block, and potentially any other input in the same block, and automatically aggregates all signatures in a block; that's all pretty neat, but trying to do all that in bitcoin in step one doesn't seem smart.
Quoted text (12 lines)
> > > > I /think/ the compression hook would be to allow you to have the puzzles > > > > be (re)generated via another lisp program if that was more efficient > > > > than just listing them out. But I assume it would be turtles, err, > > > > lisp all the way down, no special C functions like with jets. > > > > Eh, you could use Common LISP or a recent-enough RnRS Scheme to write a cryptocurrency node software, so "special C function" seems to overprivilege C... > > Jets are "special" in so far as they are costed differently at the > > consensus level than the equivalent pure/jetless simplicity code that > > they replace. Whether they're written in C or something else isn't the > > important part. > > By comparison, generating lisp code with lisp code in chia doesn't get > > special treatment. > Hmm, what exactly do you mean here?
This is going a bit into the weeds...
Quoted text (1 line)
> If I have a shorter piece of code that expands to a larger piece of code because metaprogramming, is it considered the same cost as the larger piece of code (even if not all parts of the larger piece of code are executed, e.g. branches)?
Chia looks at the problem differently to bitcoin. In bitcoin each transaction includes a set of inputs, and each of those inputs contains both a reference to a utxo which has a scriptPubKey, and a solution for the scriptPubKey called the scriptSig. In chia, each block contains a list of coins (~utxos) that are being spent, each of which has a hash of its puzzle (~scriptPubKey) which must be solved; each block then contains a lisp program that will produce all the transaction info, namely coin (~utxo id), puzzle reveal (~witness program) and solution (~witness stack); then to verify the block, you need to check the coins exist, the puzzle reveals all match the corresponding coin's puzzle, that the puzzle+solution executes successfully, and that the assertions that get returned by all the puzzle+solutions are all consistent.
Quoted text (1 line)
> Or is the cost simply proportional to the number of operations actually executed?
AIUI, the cost is the sum of the size of the program, as well as how much compute and memory is used to run the program.
In comparison, the cost for an input with tapscript is the size of that input; memory usage has a fixed maximum (1000 elements in the stack/altstack, and 520 bytes per element); and compute resources are limited according to the size of the input.
Quoted text (1 line)
> It seems to me that lisp-generating-lisp compression would reduce the cost of bytes transmitted, but increase the CPU load (first the metaprogram runs, and *then* the produced program runs).
In chia, you're always running the metaprogram, it may just be that that program is the equivalent of:
stuff = lambda: [("hello", "world"), ("hello", "Z-man")]
which doesn't seem much better than just saying:
stuff = [("hello", "world"), ("hello", "Z-man")]
The advantage is that you could construct a block template optimiser that rewrites the program to:
def stuff():
h = "hello"
return [(h, "world"), (h, "Z-man")]
which for large values of "hello" may be worthwhile (and the standard puzzle in chia is large enough at that that might well be worthwhile at ~227 bytes, since it implements taproot/graftroot logic from scratch).
Quoted text (4 lines)
> Over in that thread, we seem to have largely split jets into two types: > * Consensus-critical jets which need a softfork but reduce the weight of the jetted code (and which are invisible to pre-softfork nodes). > * Non-consensus-critical jets which only need relay change and reduces bytes sent, but keeps the weight of the jetted code. > It seems to me that lisp-generating-lisp compression would roughly fall into the "non-consensus-critical jets", roughly.
It could do; but the way it's used in chia is consensus-critical.
I'm not 100% sure how costing works in chia, but I believe a block template optimiser as above might allow miners to fit more transactions in their block and therefore collect more transaction fees. That makes the block packing problem harder though, since it means your transaction is "cheaper" if it's more similar to other transactions in the block. I don't think it's relevant today since fees seem to mostly be less than 1% of the block reward...
The ability to reference prior blocks might mitigate that; but that depends on how those back references are costed, which is all way beyond my knowledge.
Quoted text (4 lines)
> > On Wed, Mar 09, 2022 at 02:30:34PM +0000, ZmnSCPxj via bitcoin-dev wrote: > Not being a mathist, I have absolutely no idea, but: at least as I understood from the original mimblewimble.txt from Voldemort, BLS signatures had an additional assumption, which I *think* means "theoretically less secure than SECP256K1 Schnorr / ECDSA". > Is my understanding correct? > And if so, how theoretical would that be?
Like everything else in crypto, it's completely theoretical until it starts becoming practical?
Quoted text (1 line)
> PTLC signatures have the very nice property of being indistinguishable from non-PTLC signatures to anyone without the adaptor, and I think privacy-by-default should be what we encourage.
In bitcoin, you have a ~64B signature in every input, and hiding a 32B secret in each of those is quite feasible if they're schnorr signatures. When the block is published, 1000 different people can look at 1000 different signatures, and discover the 1000 different secrets they wanted to know.
In chia, every signature in the block is aggregated, so there is only a single ~96B signature in each block, and there's no way to hide 32kB worth of secret information in there. I'm not sure of the maths, but I think your options in chia and their costs would be roughly:
* normal tx with just agg signature, no lightning secrets = 1,200,000
* aggregated signature + hash preimage = 1,200,300 (HTLC) * aggregated signature + point d.log = 2,526,946 (PTLC visible) * manual disaggregated signature = 2,772,020 (PTLC hidden)
But your lightning preimage reveal doesn't look like a normal chia transaction in any case.
(Because chia's BLS12-381 curve differs from bitcoin's secp256k1, it's not even possible to reveal a secp256k1 PTLC preimage on chia, so you couldn't share a single PTLC-based lightning networks even if you solved the exchange rate problem. Well, I guess you could theoretically implement secp256k1 maths from scratch in chia lisp...)
Quoted text (4 lines)
> <rant> > DSLs? > Domain-specific languages? > Do you know how many people hate autoconf?
Uh, that seems like the sort of thing you type up then delete before sending...
Quoted text (3 lines)
> This seems to me to be not much different from adding a separate > compiler, which translates from the surface language to the underlying > opcode/lisp language,
No, what I meant was the lisp/opcode language is the DSL.
Though that said, there is a difference between chia lisp with macros and clvm code; p2_delegated_puzzle with macros looks like:
(mod
(public_key delegated_puzzle delegated_puzzle_solution)
(include condition_codes.clvm)
;; hash a tree
;; This is used to calculate a puzzle hash given a puzzle program.
(defun sha256tree1
(TREE)
(if (l TREE)
(sha256 2 (sha256tree1 (f TREE)) (sha256tree1 (r TREE)))
(sha256 1 TREE)
)
)
(c (list AGG_SIG_ME public_key (sha256tree1 delegated_puzzle))
(a delegated_puzzle delegated_puzzle_solution))
)
but as clvm code, it looks like:
(a (q 4 (c 4 (c 5 (c (a 6 (c 2 (c 11 ()))) ()))) (a 11 23)) (c (q 50 2 (i (l 5) (q 11 (q . 2) (a 6 (c 2 (c 9 ()))) (a 6 (c 2 (c 13 ())))) (q 11 (q . 1) 5)) 1) 1))
I don't think you want to include code comments in the blockchain though, so at some level I guess "compiling" is unavoidable.
Cheers, aj