Return-Path: <german@diviproject.org> Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 429CFC016F for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 8 Jun 2020 22:01:24 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 2AEFD86055 for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 8 Jun 2020 22:01:24 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id D1IZ9IMz0PUF for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 8 Jun 2020 22:01:23 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f49.google.com (mail-wr1-f49.google.com [209.85.221.49]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 96B1585FAD for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 8 Jun 2020 22:01:22 +0000 (UTC) Received: by mail-wr1-f49.google.com with SMTP id q11so19136800wrp.3 for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 08 Jun 2020 15:01:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=diviproject-org.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=1seTOuVZIrWtxcTqAE30Dsft9zAbn6JiDSKe9ldIRfA=; b=QfY/M6bnXmxI/bVDgJQyEKq6k1OXoBNq6/98Ug1abbgaiqVu+HAYQc6ZLLPMiqY2Zw 0zm6DeC/no6IhH2ASTJhEjlEK5vPqKfPAbXYz7mjEw4BDaA7KowWcB5QcTyjfAT71wb8 ihsdADEthPx1v+FbJbnKeJvj2zEgQedlQjP83nxD+BQxlJAQuIUsly82yqW88u5M4wPz Xy3omE4HRa1QsmDzSI9XZ6UPSxwNuCe1yOTfhq0WIREcmdLqoIllf+2F1pFbczV8suJ1 1T9clpQmg36yg9aLlNnyzK3zUNoz065/zKEXg5WfhO9auMBAUgSS+qroLiSgvoV3+ANi gJ3g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=1seTOuVZIrWtxcTqAE30Dsft9zAbn6JiDSKe9ldIRfA=; b=iEhnUYSq9nQUToygpOHLWZOP7xgesbbfUmDMzecBqHxV2u4EwRGntgxcUTX+KLkDV2 6CUc+u1olKLOFRIdT7fSEakZbiL2H0YzW4zCentypSl+zOJhFQJUyM3VpxGtfJrTPAHh Plp7Hwl5R/khfHlQWgTzFkD+20w/kTzIoihP8wB2ouLnX8UKlAsbPTIR5gJb/uSufnTh 8zzfl97ybHZE1c6m7Uqi7B6LFePnI1knJ+jciZ2601iVlnLAkAMJEYAWn77BW8uoote2 rksWKc/4MFWOsyvn/8GLagdcncUgIfJQBBfTgVh7TJSU/fg2wwFfC0xdRFDuTYJlkG0r nqdg== X-Gm-Message-State: AOAM530WWZv4ffvjNXEQiiGPNh0NoDtbp1uwOBRmz9kzjrYDbEt6+SiJ QsTCksVM0/t/EpBeFFs9ZW3ceKvK5ZDylil3t1Mi69BZ X-Google-Smtp-Source: ABdhPJxNRIXMWMvlfO5UH545TKbebm5/C+AYHhRCe62gpxlvyrxGtBdhNfCi04nuY2RBy/nDOxrIFl+uIMt3r1sM63c= X-Received: by 2002:adf:e78a:: with SMTP id n10mr939180wrm.114.1591653680839; Mon, 08 Jun 2020 15:01:20 -0700 (PDT) MIME-Version: 1.0 From: German Luna <german@diviproject.org> Date: Mon, 8 Jun 2020 16:01:09 -0600 Message-ID: <CALmj_sU5pw5agXONUOcenBc0GJZP6_2Cc0OnSg-J86XEkq=eKQ@mail.gmail.com> To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, salvatore.ingala@gmail.com Content-Type: multipart/alternative; boundary="00000000000040902605a799c023" X-Mailman-Approved-At: Tue, 09 Jun 2020 01:56:14 +0000 Subject: Re: [bitcoin-dev] Hash-based accumulators with quick insertion X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Mon, 08 Jun 2020 22:01:24 -0000 --00000000000040902605a799c023 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Interesting work! I should be fortunate to make time to read it. I will point out, in case you'd not considered it, that you can support addition and removal indirectly by formulating it as a difference of sets. Similar to the collision-resistant replicated data types (CRDTs) concept. Checking for membership would simply become CheckMembershipInAdditionSet && !CheckMembershipInRemovalSet, assuming an item could only be added/removed once. You could also perhaps support multiple addition/removal by attaching a count of how many times it's been added though that might break some of the building blocks in the paper. --=20 Germ=C3=A1n Mathematician --00000000000040902605a799c023 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Interesting work! I should be fortunate to make time to re= ad it.<br><br>I will point out, in case you'd not considered it, that y= ou can support addition and removal indirectly by formulating it as a diffe= rence of sets. Similar to the collision-resistant replicated data types (CR= DTs) concept. Checking for membership would simply become CheckMembershipIn= AdditionSet && !CheckMembershipInRemovalSet, assuming an item could= only be added/removed once. You could also perhaps support multiple additi= on/removal by attaching a count of how many times it's been added thoug= h that might break some of the building blocks in the paper.<br clear=3D"al= l"><div><br></div>-- <br><div dir=3D"ltr" class=3D"gmail_signature" data-sm= artmail=3D"gmail_signature"><div dir=3D"ltr">Germ=C3=A1n<div>Mathematician<= /div></div></div></div> --00000000000040902605a799c023--