Date: Wed, 23 Mar 2022 09:37:23 +1000
From: Anthony Towns <aj@erisian.com.au>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20220322233723.GB7580@erisian.com.au>
References: <20220311044645.GB7597@erisian.com.au>
 <L7tNMIZp05o7FReQe8l-TjBDkuqbdby8Rk92X_BXEl7Hp5B7eAa-oyS0wMPDvLec03sJ7Q_yoW6ker0LS8k8VPXEHRhObF3EdB6zpLNZxRo=@protonmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <L7tNMIZp05o7FReQe8l-TjBDkuqbdby8Rk92X_BXEl7Hp5B7eAa-oyS0wMPDvLec03sJ7Q_yoW6ker0LS8k8VPXEHRhObF3EdB6zpLNZxRo=@protonmail.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
Cc: Bram Cohen <bram@chia.net>
Subject: Re: [bitcoin-dev] bitcoin scripting and lisp
Precedence: list

On Wed, Mar 16, 2022 at 02:54:05PM +0000, ZmnSCPxj via bitcoin-dev wrote:
> 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.

> > > > 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...

> 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.

> 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.

> 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).

> 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.

> > 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?

> 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...)

> <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...

> 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