From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 16 May 2024 08:22:07 -0700 Received: from mail-qv1-f62.google.com ([209.85.219.62]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s7cvm-0003hv-OV for bitcoindev@gnusha.org; Thu, 16 May 2024 08:22:07 -0700 Received: by mail-qv1-f62.google.com with SMTP id 6a1803df08f44-6a113df8f57sf98749196d6.2 for ; Thu, 16 May 2024 08:22:06 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1715872920; cv=pass; d=google.com; s=arc-20160816; b=VYZKExPvOy3XK7oyFrUj26OlRTscE5HR3Qet7AEzeqEMMhyuui7zUGoLJBYIlwx0KX voBOvU4QO5CX2Qu/yII+y1HhxpMuKhJMB0VKLHUlPF1a/lnePyBml4uXBlqjyJFhE+gu z4HuozQRUXXa2pHv0Q+DfAt3b1vX7AaDvyStWbL9NpcxOivZBjxXkKvfa9eC0QAJBX3j CPmbQrcypAZf/yWGUGFMfkf/7uIZEg2oBrBoLhXe18gCl5aIkx0OjizP1IWNEKHt7iD+ rPQMA9okVdaROkAOQiPF/IfNN579UGa0BM6jUbt9G+3CCoBynsTXsR4RfdDc4Bb4K6sX gVMw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:in-reply-to:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:sender :dkim-signature; bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=; fh=UZ/LGnt8Hig7Mx3rVNkYrlx58qfpXmjhdNfiq6UfyOQ=; b=qNPtzEpE3EeaOWGr1sGc6M2/ikgqRjGL8I4406Ck7DBFg64qNuqk7issROeYEHZoQZ NU4qZlci8Gqj5jSMqXvpaRooSnExtAydNU4IC9Ksdjyam6Ll/SQvGoAKa9/QeJ87WeTx rVwVPZGyT1RjVPTgTnSMl/croCMHvf3Y+yxSTr1Cy3fG121r4W4dVp4z0pO6ZUJnnBNz kDtLZhubSND25MKNqLFmjqXkYVxUB1MaXAcjPfdvglVCRF/2plL0E94HOktVcbJiAz2d /k9foRQ/k41i8RY12LrD6nfrNpJBlQDkYc25ENgygER57f5BfDSpbQqwfEJwE/DNK4h0 VtBg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1715872920; x=1716477720; 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:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:date:sender:from:to:cc :subject:date:message-id:reply-to; bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=; b=WzzCgZ//sxZjoqoZHyiT5GwkHo5/PmXcNrsyQzQAf4vAGy8YO2rAsVXdqXxZhVoCjS 0RnKIersEdywFMNEfzqzA5FeRNEZKp4PJlZHM+IJ8IaDoiJ7xvroPUgKOQ8RAz5K2dzz J5NH4xPpAfiyq8TeMovJGyCpPb3rGD6bhQPB8pGEtSatKGaAnsHAm55zK01HSbjcwMwh E40PjPi0GJczMUHhHnQGI99rxusapIU9bgwPZOloXt3dAGYi/z8B04NuMQr1gdM25Xo3 d3rQqY0TGrZ/iczwUgIC0WMOJAYoTwvTuXIzNf3Pihfc3GdlGzFG/6t7NEO0Ju1H4K+H l+WA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715872920; x=1716477720; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=; b=TXuHv0/VcwQlLQuQmox1fyKX9VxuIZRvwmgkL5Z+bm1MS/j4vCsc1y82I3B9A/hwR1 hBfcvuafwPP07rilHk+xogOHczd+VFHdYo67lJpSAEZeEeEmdeeIZaMV5JwPE7pV9143 Nbk94Rgfjt2MBNVnFEwoEDHagpemqFUW2lWbfFvxtutfDrjQPmh6vJ2Ua9LY6mkQyJNA 8Avjt4wOD/JrZCFn0A86/OtPlQcyNTil5e+MbQcUpVKJANF9NCzWpnDB4ASr0JNZrNtH NYVmoytI7scglRcoM2aSEvCMX+NBH0rWy05wkZQKYGEnxcboENH7LBxnHVJ7zZ563ngS uA7g== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCVX4wAAUUykxDIi43XI99LUQeQJKI360Ik6+BdT1cnlvjHXrY0vCI+Wsb4sENiQOIUbalfV4RZIu4MBVpurCSbhU5XdTqA= X-Gm-Message-State: AOJu0YwF2eSjxa5MeNN6HHQbEGRVqOIzFUePL1nx0aFkEyJ9rP/93Zad W+GxUg/GVVGlIgkrRn+Bo8HccvShK/s8931CT+TjePqgm4Mrc8h2 X-Google-Smtp-Source: AGHT+IFRdHZyOzOFXhn1auSZSb8dpsUmymfek1w09HDqLA0x+fG3l92moKISjzDtb2afn3kYpGNYxg== X-Received: by 2002:a05:6214:3383:b0:6a3:58d1:ff6f with SMTP id 6a1803df08f44-6a358d20220mr46100756d6.57.1715872920342; Thu, 16 May 2024 08:22:00 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:ad4:4ea5:0:b0:69b:1803:6ad6 with SMTP id 6a1803df08f44-6a15d23a3a8ls134793326d6.0.-pod-prod-06-us; Thu, 16 May 2024 08:21:59 -0700 (PDT) X-Received: by 2002:ad4:5fcf:0:b0:69b:7323:1ada with SMTP id 6a1803df08f44-6a16820a493mr3852516d6.11.1715872919227; Thu, 16 May 2024 08:21:59 -0700 (PDT) Received: by 2002:a05:620a:40c1:b0:792:a4c6:e0f4 with SMTP id af79cd13be357-792c6fe5026ms85a; Thu, 16 May 2024 06:28:00 -0700 (PDT) X-Received: by 2002:a67:ef44:0:b0:486:3434:a30c with SMTP id ada2fe7eead31-4863434a3d9mr719670137.16.1715866079127; Thu, 16 May 2024 06:27:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1715866079; cv=none; d=google.com; s=arc-20160816; b=FtxK7yF05VxUskha7ssqyJUN1P8s4ZwCBIXO7jLedspdMIpmQBE5+IEsL26wdXTbnA eI+ni9Xv5ADeLi0f/cJkuuipzOEc+9F4kol8iyDBn1TU47spfQW6J+1YFivY9P/ygWzQ Cz3BoiKvkPuUMLI/awEE9TleAc1chyZv+BLDZGB49DCRuF5KPbr/+cCJh6t1f3au7Vao rvhcEINviKub+XiAnyKdr7c/XDRD+iv9eodlfrJIX3+uatu7/MQHY3jOVQDryXO/mETU RMu6WjhlZ5GX1GcB2lRhB3fz3wt98fnAhHnvVGgMlbSrAlZPhccD1P7oMMRfH8svycld 3oaA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:dkim-signature; bh=CX+rEKGzodS3sO6tOqVpUY9oxboJgzwsR1lk8hCqayA=; fh=cahZDgTdN45RG3UsKThsxzoXgKY9yWPedXjgzYAIiH8=; b=a2+iSU+iTdnBC0as/b/DBsxP+G5d99QAfyzQWrqAOXDKHlpfHO/fN4ke9qqOvnX4dT 89P5jj1fardybm9hozbscHDybWYakOGvUVBUiLqtcIspWfxqkUWoOhHhow5TXyIK+CCy ctQG/BZx+/G35KrHeIZgzu1LveZU8YwBI2cF4DOnakwpDJUcnobEd73zHG2/txb5MPFY DCb+RjMF/aBlZRXIuqil/Gqb1HJ+pvwBEJLtyAy3TlaHynFWa8Iag6+N4B+GAvzNOF3n Sli0/BkqNzCgZ/VcQIuDEhZ3967zw6QaL+x1Y6l8u6nDXL6tMaVn88mv5obBzqQBo2VR 6nUA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net Received: from mail.wpsoftware.net ([66.183.0.205]) by gmr-mx.google.com with ESMTP id ada2fe7eead31-4858569b305si94144137.1.2024.05.16.06.27.58 for ; Thu, 16 May 2024 06:27:58 -0700 (PDT) Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) client-ip=66.183.0.205; Received: from camus (camus-andrew.lan [192.168.0.190]) by mail.wpsoftware.net (Postfix) with ESMTPSA id C530040102; Thu, 16 May 2024 13:27:56 +0000 (UTC) Date: Thu, 16 May 2024 13:27:55 +0000 From: Andrew Poelstra To: Rama Gan Cc: "bitcoindev@googlegroups.com" Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases Message-ID: References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="0W3JydEiLSLDNNv1" Content-Disposition: inline In-Reply-To: X-Original-Sender: apoelstra@wpsoftware.net X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net 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.8 (/) --0W3JydEiLSLDNNv1 Content-Type: text/plain; charset="UTF-8" Content-Disposition: inline On Thu, May 16, 2024 at 07:43:29AM +0000, Rama Gan wrote: > > But I guess this is explained by the large number of characters produced by > > the checksum. > > For clarity, 45 mins was from a benchmark in real conditions. It includes the > whole process of copying the seed phrase, checksumming it, generating the random > share A, checksumming it, deriving both shares B and C, verifying the checksums > and finally correcting a few mistakes. Recovery took 20 minutes. > > The checksum is the second source of inefficiency, the first one being that > BIP39 isn't compact. GF(29) can encode 128 bits within 7 words, and the checksum > would cost 7 more words. In comparison, BIP39 low density of information costs > 10 more words (5 data + 5 checksum). With a compact data format, the entire > 2-of-3 split process would take less than 30 minutes; and recovery with > verification would be under 15 minutes. I don't know if it can be optimized > further, but we're already looking at figures that the general public might find > acceptable. > With BIP39 density you have 24 words (96 characters). With GF29 compaction you could get this down to 14 words (56 characters). But codex32 does the same in 45 characters, plus a fixed/preprinted HRP. (And 6 of those 45 are a header which is usually faster to deal with since you're always dealing with the same characters.) In your case, since there's no way to get down to 48 characters, I wouldn't bother trying to compress any further. Either you fit in one side of a cryptosteel (no) or you fit in two sides of a cryptosteel or into a tube (yes, even without compression). And I agree that the existing figures are not bad, especially because the checksumming (which is the most common and also the least fun) is so fast. I think if you were able to squeeze an extra word of header data or version info, that would be worth doing, but probably not at the expense of making the user do a re-encoding phase. Which I suspect would be needed to try to get more information density out of your characters. > > Very cool. Though you say "single wheel" but you actually need two -- one to > > get the solving window and one to actually do the recovery. If I understand > > correctly, the "solving window" is equivalent to a "recovery symbol" in > > codex32. > > The solving window is the is the distance between two shares, and not a Lagrange > basis (to the best of my knowledge). It can be determined from the same single > wheel, that already implements subtraction. > > [3]: The 2-of-M wheel "Recovery" window shows the distance between two shares: > https://beta.penlock.io/2ofm-wheel.html > Ah, I understand. Looking again at your wheel, I see that it's a combination slide wheel (for addition/subtraction) and slide chart (for "recovery windows"). What I'm saying is that you don't need to have extra cutout windows for the recovery windows. You should be able to just label the characters on the inner wheel with them, similar to how you have already labeled = with (1). > > If so, despite the simple interpretation as "the difference between the > > shares", this object is secretly a Lagrange polynomial and you can _also_ > > compute it using a slide wheel rather than a full lookup-table volvelle. > > I'm not sure if I understand that, but it sounds like I missed an optimization > opportunity there. Can I ask you to develop that point a little? > I don't think this discussion of Lagrange polynomials is relevant actually. My point is that you don't need the cutout squares, and I think this is clearer if you think in terms of share index differences than if you think in terms of Lagrange polynomials. But. What I'm saying is that if you do the Lagrange polynomial calculation using the formula from Wikipedia, magically your differences will appear. They're the same thing, just expressed differently. -- Andrew Poelstra Director, Blockstream Research Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster -- 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/ZkYJ21cloqyvT93G%40camus. --0W3JydEiLSLDNNv1 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmZGCdsACgkQxYjWPOQb l8EHqQf8D7rFLlb9u92OB1SkmeAm5UhZx5Gt7NlJyGg1pfkm3I3P5vrqJNfjmO4v nMP4bWruJ6DlINYkEAmi034nm+gbkWfzzFB+cW5Adx1iSCXVFepChaMAmY0GCKPh g9cXf4wNlkDeqy3tX2ZUeXYVuB0DBKwePGHrQXgN/g1zKyAX92OhSggzNsLhzq2r zv65QBC9o213OlXmeuxmq5AqH6btpWnN1Bdx+O2/TEOTiT9zgZQU21ojfyPOkPbz Qe4DIlML56ga3IoS75MgDl4ae54eLl+jnZWQ6QvalsjQhvejzpaxRx+04dRnx6ft /eMPKoDd4jo3MTfcSu/P4hbtXEVHmg== =fvPO -----END PGP SIGNATURE----- --0W3JydEiLSLDNNv1--