Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 4482CC000B for ; Tue, 22 Mar 2022 23:37:34 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 253B5848D3 for ; Tue, 22 Mar 2022 23:37:34 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.901 X-Spam-Level: X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KgGp4gYSWotV for ; Tue, 22 Mar 2022 23:37:32 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from azure.erisian.com.au (azure.erisian.com.au [172.104.61.193]) by smtp1.osuosl.org (Postfix) with ESMTPS id 8BCED848CE for ; Tue, 22 Mar 2022 23:37:32 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian)) id 1nWo46-0006gf-R1; Wed, 23 Mar 2022 09:37:29 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Wed, 23 Mar 2022 09:37:23 +1000 Date: Wed, 23 Mar 2022 09:37:23 +1000 From: Anthony Towns To: ZmnSCPxj , Bitcoin Protocol Discussion Message-ID: <20220322233723.GB7580@erisian.com.au> References: <20220311044645.GB7597@erisian.com.au> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Score-int: -18 X-Spam-Bar: - Cc: Bram Cohen Subject: Re: [bitcoin-dev] bitcoin scripting and lisp X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 22 Mar 2022 23:37:34 -0000 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...) > > 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