Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9F05CC002D for ; Fri, 8 Jul 2022 15:50:34 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 6AFC8613D3 for ; Fri, 8 Jul 2022 15:50:34 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6AFC8613D3 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=hFNmN3lA X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.099 X-Spam-Level: X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Kgt89aAkH0st for ; Fri, 8 Jul 2022 15:50:33 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 64C0C6138C Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com [IPv6:2a00:1450:4864:20::536]) by smtp3.osuosl.org (Postfix) with ESMTPS id 64C0C6138C for ; Fri, 8 Jul 2022 15:50:33 +0000 (UTC) Received: by mail-ed1-x536.google.com with SMTP id fd6so27349962edb.5 for ; Fri, 08 Jul 2022 08:50:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:message-id:date:mime-version:user-agent:content-language:to :subject:content-transfer-encoding; bh=SQeJxenr3FOEnBM6tRTc8E+0N1cBQuka/MKE5EFD+eQ=; b=hFNmN3lArU922r/VetrmUH4Xyus6J9UqX81xidvjBv/knc7GLpEM/UGUgUWvQ8Fz7J 9AKrOeH7A/10kGdW5UMx/uxbu3hD5YZH/wqanFL1zTcbuylJiisKVbxCtx0Mx79zRRn7 Xo4EdOKfTVAuJF/NIh2zC3yOmyhMcZO/LH14ppp/uCVanohkuauFpY4Uu5EmvG6TD/qj 0WbmUvyhjcH8U7Pn6Wcyw+Cu1MbKK5N2s+I26uUsTW7+kah/I8HoKnqkae9wEmX6tNmh As+9Nx7mnvbOX/iQ4OgRcQp+1cLmVtB4JN/iZJ1SuGisXdRPhSMjn+idgodC0yFzHJfB 5E3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:message-id:date:mime-version:user-agent :content-language:to:subject:content-transfer-encoding; bh=SQeJxenr3FOEnBM6tRTc8E+0N1cBQuka/MKE5EFD+eQ=; b=J77dDORPbKYiuXwWpho50ms3pvl3Hg3u3cBTQyO+2C03wschwxhnp+YEI/Pxfs1NpG Fyrva2jJlX2v9ZP0WJH2WBnhnB4awyTe92UwUkioYXII7eyqqrFkfz+SZDSkDOQfq07H IvnkuZEzhqzQw6GKn2VxVbOAVwLgjGWL6h9bUwTtdShFVrq5u0cItS3pZOwk0ZokgPTG q+/aJuI4eYena0Jhy6ZzsUt191/fIKfO+dAv1p4J1PkIzhTAlmpN+GFXc1ULWLV2CkGX VULZdChcnaHI4aU/nTzUACn5BB3SsES2riZljfbFfo6ZHgo8DK0VHhevu9cM5pFnqVVv Bnzw== X-Gm-Message-State: AJIora9ZisGSKbd0qgV4yayDKkG3xXVvPxQ4BH9YEPi1JmoD6gybOKEq R9p1Etwmzty+VgH79esQekvIgh4iY0iHFQ== X-Google-Smtp-Source: AGRyM1vJxvtze5i+2OyQaP9vLN/qjKF2dhLBM7W0hpq6bWYCtjoOoxOtDf7Es/jMp5QW/13QR6plbg== X-Received: by 2002:a05:6402:448c:b0:435:9dcc:b8a5 with SMTP id er12-20020a056402448c00b004359dccb8a5mr5697850edb.287.1657295431596; Fri, 08 Jul 2022 08:50:31 -0700 (PDT) Received: from [10.11.10.13] (179-129-067-156.ip-addr.inexio.net. [156.67.129.179]) by smtp.googlemail.com with ESMTPSA id eg37-20020a05640228a500b0043a587eb95dsm11653714edb.5.2022.07.08.08.50.30 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 08 Jul 2022 08:50:30 -0700 (PDT) From: Jonas Nick X-Google-Original-From: Jonas Nick Message-ID: <33f275c2-06b1-4b4a-2a75-cafe36836503@gmail.com> Date: Fri, 8 Jul 2022 15:53:06 +0000 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Content-Language: en-US-large To: Bitcoin Protocol Discussion Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Fri, 08 Jul 2022 17:32:37 +0000 Subject: [bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures 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: Fri, 08 Jul 2022 15:50:34 -0000 Half-aggregation has been mentioned several times on this list in various contexts. To have a solid basis for discussing applications of half-aggregation, I think it's helpful to have a concrete specification of the scheme and a place for collecting supplemental information like references to cryptographic security proofs. You can find the BIP draft at https://github.com/ElementsProject/cross-input-aggregation/blob/master/half-aggregation.mediawiki Similar to BIP-340, this BIP draft specifies only the cryptographic scheme and does not prescribe specific applications. It has not received an extensive security review yet. Thanks to Elliott Jin and Tim Ruffing for the review so far. One new feature that the specified scheme has is "incremental aggregation" which allows aggregating additional BIP-340 signatures into an existing half-aggregate signature. While BIP-340 has a pseudocode specification and a reference implementation in python, this BIP draft has a formal specification written in hacspec [0] and auxiliary pseudocode. The formal specification is a mathematically precise description of the scheme, which paves the way for computer-aided formal proofs. Software tools ("proof assistants") allow proving properties about the formal specification ("no integer overflow") and apply formal software verification ("implementation is behaviorally equivalent to the spec"). I don't have concrete plans (nor the skillset) to use these techniques. Still, I think this is an exciting area to explore because it has the potential to increase the Bitcoin ecosystem's robustness significantly and has little downside. Since hacspec's syntax is a subset of Rust's syntax, one can use the standard rust toolchain to compile, execute and test the specification. You can find a blog post that gives a broader context at https://blog.blockstream.com/half-aggregation-of-bip-340-signatures/ [0] https://github.com/hacspec/hacspec