path: root/3a/9b6575676e9a6607e4606ecba697d66b52a4ea

Delivery-date: Mon, 09 Sep 2024 05:59:42 -0700
Received: from mail-qv1-f63.google.com ([209.85.219.63])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBNPC7O3AMGQEFYKYWHY@googlegroups.com>)
	id 1sndza-00061D-Af
	for bitcoindev@gnusha.org; Mon, 09 Sep 2024 05:59:42 -0700
Received: by mail-qv1-f63.google.com with SMTP id 6a1803df08f44-6c353b29bd7sf71727776d6.2
        for <bitcoindev@gnusha.org>; Mon, 09 Sep 2024 05:59:42 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1725886776; cv=pass;
        d=google.com; s=arc-20240605;
        b=IE1MCrTOlE7uramq58tlTWYEArzmDzP9NxTDg+/qjjyZMnTu+s6G31zxxdPDjgiIsa
         638X80PcHACc/HC6d+pL5khOsEvXU78nZj/NZbQE1bwBDYg0dRc2APbFsc9fZ9gaXcq4
         9W7SayEWIpY95u+FyDBUElU6NJfT6r3v7vcVIDV92wQn4V4xwiT2LX+DOA7qM1vUEYlL
         y6dwHlEswpZ6BoRBybMtsc5SozLM5felM+c5VarpHHSSu1fY9LUc2S4A/0aVyIkm74JG
         R2FynIpiDQTC7ZKpta7Bbt/jKVr3lWLH0ohO6cWRTEkfY5Hiip+qPaLoDx7rsFw86VPq
         cQRw==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:to:subject:message-id:date:from
         :mime-version:sender:dkim-signature:dkim-signature;
        bh=RvwCLcbXN/gowEVE7pbpaow4z1kuALrhN/huaGmfefU=;
        fh=eJmV1atas82vJYRSD7g7JF6eJdqqybA/o6fU2UacskQ=;
        b=kTUCmU1qlLcErd45VBVD3MC1yVrxOzXYyGq+q0YAJHVH+uCtdWpo9dLEHOLTwZo7wG
         Q9IiXduxHmmrWNCmHbQjG5IjvfJW0hjDi6meMZfiHNosBw391/j75w+eLMCfF2IwUWi9
         SB9LWcc9dilXgrLZi8XFcG1AP5CLCPMb4mMgv/Y3e+cLDVguXi4sJMaBwYHvD5v18tez
         6quW6lbGVtId3MDXNJrlAzgzcFs4wnTyZNSKxhlkKOUvQ/CMOpT4HQxMc2GZ5eea541k
         tHJfyXZs4bzTSDA5DoexBvBr0Z+IsGVnPwfnHH9WQLqqYl2SIiO0lBsIv/Dd540QdKGl
         +hbQ==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=N2QgX4yI;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1725886776; x=1726491576; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version
         :sender:from:to:cc:subject:date:message-id:reply-to;
        bh=RvwCLcbXN/gowEVE7pbpaow4z1kuALrhN/huaGmfefU=;
        b=MNKEFtPA05IJPjvm/LpfP+3Tobdh42EOCYp9GwItjvRblNiTSsPN2q4cwWFQuRYpqn
         Mgllcx5z90NW/r02jMOzF5OKj+teH2Jzter1wF0Cfy9mvBGAHKzGrU7Xc6zf7uQOP787
         n6C/g8djdCJMl1iGtCPtQW0VYVAvdeh+ipB8cOWLjVBFeFZrknqCw10z2bZ59A63z8dO
         wG0lI1HZl7ufHmUJbcDoAWHnLMp9hLP3Dl996scAO8xJgyzeY4LXKk0ybr09ELS7YPso
         2b9ZDQI6idwJpbbtA45TUU0iWfvvgl+iXCi/9+TcaeKrhIkfARc4VjJWeaQig4gS/aLc
         Xlxw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1725886776; x=1726491576; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version:from
         :to:cc:subject:date:message-id:reply-to;
        bh=RvwCLcbXN/gowEVE7pbpaow4z1kuALrhN/huaGmfefU=;
        b=TdZhghxPl8wYHjn1GFpJfWcYovGs8WEXw7DSSN+3vE3rsMLd+ylAcr7TuSoTxXoK4o
         mes9qvzH+bcO2gNTx3JM/6XREUeEZNzuEocSqH24K6bciGOhGb7IpqznWc3/rLWeChtK
         AH12k1dZR2sJ/qcisgxesB3Xd58vKXli7n8/C1QEEWuDp9ipE8slO++yf0D7uDA5fhr9
         TlxS/UJQU7X+UwKVwyTPfWYLZ46GTVHLJqE+53rJBQwj4uHhJnFCUrgqb7ZjmArQ4NyQ
         fX7GDBQx/gjidV4JGkCLbI8VlRyyDlsFmY1mqq/FcBAy1bxFf64BiYm7bO3WFygEzxVY
         8C4Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1725886776; x=1726491576;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version
         :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
         :message-id:reply-to;
        bh=RvwCLcbXN/gowEVE7pbpaow4z1kuALrhN/huaGmfefU=;
        b=WpYZkIGKFOJxQZad6DOPmhEnNe7hY+VuyVSsRNVWgq8dK87wVUJIbBecaULY7W/hn2
         K84PJPUH3/Mf0W0Bz+t3CiVlapCwg5bnktdkD2kFHgQsW0zAf+bYuxmWV8r35wDmnd1N
         2W2T2X8VIHgizXnfHWUM8kXqARjlllYcOtUpAJmB0qkBeL7aC8E4E3EvH4Fpd8qJagsC
         rJbarulalWxqXjrTH6VXUO6d+qCzMrWEUqEtirR6GHJMJZ0OsaSPEb1yAmZof+V7ZGIx
         twfGOLdX7naG3ukUyypHK2kLYWDJMGb6DNIrwKJnUzR9PDQZPdjGoZob37fpBZQqGkuZ
         QjiQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUvytp+Jgd4plvXmWfd9np0p40KksLUInR4Shljjh0jeegUPYPuPxt6QvmHux4loxZpLSzyhWqGvQPT@gnusha.org
X-Gm-Message-State: AOJu0YxHbmO/7tCWd/5/GHivyi/vEb27muBRujTdcbFlCP/0vGfMySd0
	0g1VxxQqGpHaPxjO10sQdrVODI6E4pvjfcttXW4bYRoJ+4qukwPM
X-Google-Smtp-Source: AGHT+IF8jx5jhpjZu3WgB0utdOC2oP8NCKxdejA4A7jYAaf+smHCQ1NpaGFN3Kr5EUCMmF6s2OJ+bA==
X-Received: by 2002:a05:6214:469c:b0:6c3:562f:568 with SMTP id 6a1803df08f44-6c5281c4d03mr218875546d6.0.1725886775827;
        Mon, 09 Sep 2024 05:59:35 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6214:492:b0:6bd:7218:a1a6 with SMTP id
 6a1803df08f44-6c527c32fb5ls50703466d6.1.-pod-prod-09-us; Mon, 09 Sep 2024
 05:59:33 -0700 (PDT)
X-Received: by 2002:a05:620a:31a6:b0:7a9:b856:434 with SMTP id af79cd13be357-7a9b85607dfmr609052085a.12.1725886773539;
        Mon, 09 Sep 2024 05:59:33 -0700 (PDT)
Received: by 2002:a05:620a:935f:b0:7a1:d643:94b4 with SMTP id af79cd13be357-7a9a23e77e5ms85a;
        Mon, 9 Sep 2024 05:41:40 -0700 (PDT)
X-Received: by 2002:a05:6402:2691:b0:5a2:5bd2:ca50 with SMTP id 4fb4d7f45d1cf-5c3dc7bad6amr7283314a12.25.1725885698211;
        Mon, 09 Sep 2024 05:41:38 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1725885698; cv=none;
        d=google.com; s=arc-20240605;
        b=gGPEawycIpcdEqq+5xaECimfpisi/L+SEXNgGydXtlBk3pBWi31dbPaotAWmZO6dwt
         p6zqgkgY5d7glehQmAYth1Rrv0nY8p17lnFIZXq0RjrQUU3r6m3/hgjHO2WL4b42KKic
         tUcJBabhnyn2a/15eDHngiWxU4Coib6s167LU6JThYy4oZLEv9reA1sIRqCjtalufu6p
         AsA4+NX2GmmrZ1tTnDHkZXbcSlygE8uxLVI5b8FFcXcNJKKhodwfO9kRMB9NqGQNXOBa
         3BdKtdKuzjXrNbkp1nqCpcMJqr2qVBf086rmTxaNG+7zHqPWzS9HfoCPeRnzQ6U/l9Nv
         Vkfg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=to:subject:message-id:date:from:mime-version:dkim-signature;
        bh=VB3qZJOKSYVKK95FKowjc9PupYiIL4UjIwX8OYf8zyc=;
        fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
        b=Pq68v+7MpkwkuQV+06m1Z+f72Fi21UGBRikWywrymZtFmYoYukXMnJEl8528SK0y2/
         vpZ+GqVZgXMiv53iDRqoRyGo+E0sLD3XN5Jamkmb1rgLvtkOadJDCsO+BzqeiuV5NxaW
         IufBC/e7+d4e6+tOgqFKNsz1610Vnr4uKhpGbQwyQ9aREAWsssOM7sCIPx3U2cglTCpf
         KSHKXZ/ehuAFl3Dt81hUrj0r282FzYLIFVbgdnqFXYbPG6v10jn7wEg5OatHKdA/fm+5
         JrDoWgqzLIWQ0a1vG+YEeKfArakioM7ZDZqhsJoMfX0I0fQ+6Ave1xtfvENlpXl2mHwu
         iAnQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=N2QgX4yI;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com. [2a00:1450:4864:20::12d])
        by gmr-mx.google.com with ESMTPS id 4fb4d7f45d1cf-5c3ebda978csi177773a12.4.2024.09.09.05.41.38
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Mon, 09 Sep 2024 05:41:38 -0700 (PDT)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) client-ip=2a00:1450:4864:20::12d;
Received: by mail-lf1-x12d.google.com with SMTP id 2adb3069b0e04-5365c060f47so3293375e87.2
        for <bitcoindev@googlegroups.com>; Mon, 09 Sep 2024 05:41:38 -0700 (PDT)
X-Received: by 2002:a05:6512:318c:b0:52e:9b4f:dd8c with SMTP id
 2adb3069b0e04-536587c5fdamr7475472e87.35.1725885696895; Mon, 09 Sep 2024
 05:41:36 -0700 (PDT)
MIME-Version: 1.0
From: Ethan Heilman <eth3rs@gmail.com>
Date: Mon, 9 Sep 2024 08:40:53 -0400
Message-ID: <CAEM=y+Whf31baRXNe5M+31wn98Csb17QO90zP1UP+YkuKjimqg@mail.gmail.com>
Subject: [bitcoindev] Publishing text of 2017-era proposed Bitcoin opcode
 OP_FFS (Fold Function Stream)
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=N2QgX4yI;       spf=pass
 (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as
 permitted sender) smtp.mailfrom=eth3rs@gmail.com;       dmarc=pass (p=NONE
 sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

OP_FFS was an idea written up by Jeremy Rubin in 2017, during an email
conversation with me about a streaming hash function bitcoin opcode. I
am sharing it as it is sometimes referenced in public discussions but
was not previously public and it felt like it should be public. For
instance there was some discussion referring to OP_FFS on [the
bitcoin-dev mailinglist in 2019]
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017355.html)
and more recently on [twitter in
2024](https://x.com/bitgould/status/1804535410904764666).

This should not be read as a BIP proposal, BIP draft or endorsement,
there are just notes written up during private correspondence. This is
being published with Jeremy's express permission.

Can also be read as a gist:
https://gist.github.com/EthanHeilman/b12b9c834c61109aaccb6cb9ffc675e8

From Jeremy's email to me:

--------BEGIN BIP----------------
<pre>
  BIP: XXX
  Layer: Consensus (soft fork)
  Title: FOLDFUNCTIONSTREAM
  Author: Jeremy Rubin <j@rubin.io>
          Ethan Heilman <eth3rs@gmail.com>
  Comments-Summary: No comments yet.
  Status: DRAFT
  Type: Standards Track
  Created: 2017-26-05
  License: PD
</pre>

==Abstract==

This BIP describes a new opcode (FOLDFUNCTIONSTREAM) for the Bitcoin
scripting system that adds a number of functional folds across data that
are efficient to compute.


==Summary==

FOLDFUNCTIONSTREAM redefines the existing NOP4 opcode.
When executed, if any of the following conditions are true, the script
interpreter will terminate with an error:

* the stack is not at least 2 elements
* The top item is not a number (N) from -128 to 127. Let `M = 0 if N
== -1 else abs(N) - (1 if N < 0 else 0)`
* the 2nd to the top item on the stack is not a valid {fold type ||
fold midstate}
* the stack is not at least M+2 elements
* any items in between 2nd to top and `M +2` to the top could not be
applied under the fold function number given the midstate

Otherwise, script execution will proceed by popping the top number, stream
processing and popping the top M elements in reverse order, and updating the
midstate on the stack.  If the top item on the stack is negative, then the
stream is terminated and midstate is finalized.

==Motivation==

There are many computationally expensive constructs that enable useful types of
scripts, but are difficult to implement in Bitcoin safely.

For instance, CAT would enable concatenation of input arguments
followed by hashing.
However CAT and DUP can be used to cause exponential memory growth.

FOLDFUNCTIONSTREAM with a SHA256 argument could be used to hash an arbitrary
length concatenated string efficiently without worry of unbounded memory
growth.


    <a> <b>  <c> <FOLDFUNCTION_SHA256> 3 FOLDFUNCTIONSTREAM -1
FOLDFUNCTIONSTREAM

Which can be shortened to (because of the negative number optimization
I made...)

    <a> <b>  <c> <FOLDFUNCTION_SHA256> -4 FOLDFUNCTIONSTREAM

is equivalent to

    <a> <b> CAT <c> CAT SHA256



==Fold Functions==

<pre>
{| class="wikitable sortable" style="width: auto; text-align: center;
font-size: smaller; table-layout: fixed;"
!Name
!Tag
!Purpose
|Midstate
|Argument
|- SHA256
| 1
| Computes SHA256(s_0 || s_1 || ... || s_n)
| Serialized SHA256 midstate
| Arbitrary Byte Vector
|- FACTORS
| 2
| Computes i_1 | i_0 /\ i_2 | i_0 /\ ... /\ i_n | i_0
| Arbitrary Byte Vector interpreted as unsigned integer
|- MAST
| 3
| Computes SHA256(SORT_CAT(SHA256(SORT_CAT(SHA256(s_0), s_1)), ...), s_n)
| s_0 is an arbitrary length vector, s_1...s_n are 32 byte vectors
|- SORT
| 4
| Computes SORT([i_0, i_1, ..., i_n])
| Arbitrary precision integers
|- MODMULT
| 5
| Computes prod(i_1...i_n) mod i_0
| i_* is an arbitrary integer
|- MODADD
| 6
| Computes sum(i_1...i_n) mod i_0
| i_* is an arbitrary integer
|- SETCONTAINS
| 7
| Computes i_2...i_n in i_0 given i_1
| i_0 is an accumulator, i_1 is a witness, i_2...i_n are candidates
|- UNDEFINED_FAIL
| 0
| Immediately returns FALSE and ends script
| n/a
|- UNDEFINED_SUCCEED
| 8-255
| Immediately returns FALSE and ends script
| n/a
</pre>
==Examples==

==Specification==

Refer to the reference implementation, reproduced below, for the precise
semantics and detailed rationale for those semantics.

<pre>
int main() {
// whatever c++ code
}
</pre>

==Reference Implementation==

A reference implementation will be provided by the following pull request:

https://github.com/bitcoin/bitcoin/pull/XXX


==Deployment==

This BIP is to be deployed by "versionbits" BIP9 using bit 6 and incrementing
the SegWit script version. Signalling for bit 6 can happen safely before SegWit
activates because FOLDFUNCTIONSTREAM is only usable from SegWit scripts.

For Bitcoin '''mainnet''', the BIP9 '''starttime''' will be midnight
xxxxxxxxxxxx UTC (Epoch timestamp XXXXXXXXXX) and BIP9 '''timeout'''
will be midnight xxxxxxxxxxxx UTC (Epoch timestamp XXXXXXXXXX).

For Bitcoin '''testnet''', the BIP9 '''starttime''' will be midnight
xxxxxxxxxxxxxxx UTC (Epoch timestamp XXXXXXXXXX) and BIP9
'''timeout''' will be midnight xxxxxxxxxxxx UTC (Epoch timestamp
XXXXXXXXXX).


==Credits==

The orginal idea of stream hash opcodes to solve concatenation exponential
memory came from Ethan Heilman.

The generalization of this idea to a folding function with unbounded stream
operations came from Jeremy Rubin.


==References==

[https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki BIP 9]
Versionbits


==Copyright==

This document is placed in the public domain.

------------END BIP------------------

One thing I'm debating is if another order of the arguments makes more
sense. I initially had the midstate/type go first, but I realized that
made problems with evaluating with data passed in from a
scriptsig/witness, so I switched it. Unclear if this way has some
other problem I missed.

Also the UNDEFINED behavior is to make it easy to extend, but it also
makes it less safe to pass in untrusted stream types... tradeoffs?
(OP_WITHIN helps with bound checking the arg efficiently...  arg *
OP_WITHIN(min_expect, max_expect, arg) outputs either arg or 0).

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BWhf31baRXNe5M%2B31wn98Csb17QO90zP1UP%2BYkuKjimqg%40mail.gmail.com.