From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 (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 ; 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 Date: Mon, 9 Sep 2024 08:40:53 -0400 Message-ID: Subject: [bitcoindev] Publishing text of 2017-era proposed Bitcoin opcode OP_FFS (Fold Function Stream) To: Bitcoin Development Mailing List 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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---------------- 
  BIP: XXX
  Layer: Consensus (soft fork)
  Title: FOLDFUNCTIONSTREAM
  Author: Jeremy Rubin 
          Ethan Heilman 
  Comments-Summary: No comments yet.
  Status: DRAFT
  Type: Standards Track
  Created: 2017-26-05
  License: PD
==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. 3 FOLDFUNCTIONSTREAM -1 FOLDFUNCTIONSTREAM Which can be shortened to (because of the negative number optimization I made...) -4 FOLDFUNCTIONSTREAM is equivalent to CAT CAT SHA256 ==Fold Functions== 
{| 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
==Examples== ==Specification== Refer to the reference implementation, reproduced below, for the precise semantics and detailed rationale for those semantics. 
int main() {
// whatever c++ code
}
==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.