From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 756DA907 for ; Sun, 3 Jun 2018 19:23:19 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot0-f172.google.com (mail-ot0-f172.google.com [74.125.82.172]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F35CF6EE for ; Sun, 3 Jun 2018 19:23:18 +0000 (UTC) Received: by mail-ot0-f172.google.com with SMTP id i19-v6so4494434otk.10 for ; Sun, 03 Jun 2018 12:23:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=8Cy2FdPHE5LD3+ExzdIC83Sxgg+dsA8kdY0XmaZmHRo=; b=fj6XF7OyVdTw38F9mt8VRAp9zpNLFjsu5JFOSDb5dgIF+83+2u9cn5TQrr3vii5NgC m7cGbMB9XbDJUK7qMZzJ+9GeCDT2OQ9rLgx4tA64iPzZBQgnQryIGcBVBluow/1j5Meb sGTZSITS4fGBKBOW2ybTzLrRMK0fn36jXsMyoH1SYfEM+zJCamYgSE60J+CLC65lEyVz 7XOZvWwOy6q2RY+b8C0MP6FdnZyslh435lotrq9Nn4bKht4W8c40iw24zAWxX4gVXv/F befsv0enY+8k1h3Q5MuP50vSz1Nngr27MnhyukCY6R75kGBHQif63ixGL/1vg/5x9jsf bMTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=8Cy2FdPHE5LD3+ExzdIC83Sxgg+dsA8kdY0XmaZmHRo=; b=iPeRwAXh8KzduI8t6LykR/tusVA+jQw1QJTS4EfkCHKFk0UJv4/w8+lhutuwVLzZas ZcmqmnQO6dKaCUdkqJYeXyQcFRJP1rdWSfBGf88zdZRB40L6/BwEWmZai0rFs0QT+Z9L 5jNuFGL01zOzj1e3/PLhgmC1Jd8mL7OPhuul1rwiZLwRIT7bX69xGfvZr82qzDSVhQEr 46JDGT3GcTUYrwdZS3E35Pozf3uh32/FK7cifwTy+YlX9pDDMgpg1wyvc4k+/qkZlz6Q OengveTlqkozHLiHzubjx8poFz1MExQxBC4wcOePuJGIA2bCOpVsBER5BAF61BXrPjef bkLQ== X-Gm-Message-State: ALKqPwfIR0f59rf9eE/9KGqOCU2/DHKCYhRXEPOKCziWt6kwZSAXet2w OEAJ9Q8+a/oWHLoQK7RiLFqplEVr08Tq3FmHqUKuJw== X-Google-Smtp-Source: ADUXVKJgOlounZeJGN5TkBX5e3GZt9h91M9n70ebzDKmCQPobq16/a+L3qR+Y4/eBLYFV10/jjsNct2YzImyRWx5HCQ= X-Received: by 2002:a9d:4361:: with SMTP id y30-v6mr13362649oti.170.1528053797920; Sun, 03 Jun 2018 12:23:17 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a4a:6ac8:0:0:0:0:0 with HTTP; Sun, 3 Jun 2018 12:23:17 -0700 (PDT) In-Reply-To: References: From: Pieter Wuille Date: Sun, 3 Jun 2018 12:23:17 -0700 Message-ID: To: Jonas Schnelli , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] New serialization/encoding format for key material X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 03 Jun 2018 19:23:19 -0000 On Sun, Jun 3, 2018 at 9:51 AM, Jonas Schnelli via bitcoin-dev wrote: > Hi > > The BIP proposal is now available here: > https://gist.github.com/jonasschnelli/68a2a5a5a5b796dc9992f432e794d719 > > Reference C code is available here: > https://github.com/jonasschnelli/bech32_keys > > Feedback, criticism, etc. welcome! First of all, thanks for working on this. I have some concerns about the use of Bech32. It is designed for detecting 3 errors up to length 1023 (but is then picked specifically to support 4 errors up to length 89). However, for error correction this translates to just being able to efficiently correct 1 error (3/2, rounded down) up to length 1023. You can of course always try all combinations of up to N changes to the input (for any N), testing the checksum, and comparing the results against the UTXO set or other wallet information that may have been recovered. However, the checksum at best gives you a small constant speedup here, not a fundamentally improved way for recovery. However, we can design other base32 BCH codes easily with different properties. As we mostly care about efficient algorithms for recovery (and not just error detection properties), it seems more important to have good design strength (as opposed to picking a code from a large set which happens to have better properties, but without efficient algorithm, like Bech32). This is what I find for codes designed for length 93 (the first length for which efficient codes exist with length long enough to support 256 bits of data): * correct 1 error = 3 checksum characters * correct 2 errors = 6 checksum characters * correct 3 errors = 10 checksum characters * correct 4 errors = 13 checksum characters * correct 5 errors = 16 checksum characters * ... * correct 8 errors = 26 checksum characters (~ length * 1.5) * correct 11 errors = 36 checksum characters (~ maximum length without pushing checksum + data over 93 characters) For codes designed for length 341 (the first length enough to support 512 bits of data): * correct 1 error = 3 checksum characters * correct 2 errors = 7 checksum characters * correct 3 errors = 11 checksum characters * correct 4 errors = 15 checksum characters * correct 5 errors = 19 checksum characters * ... * correct 7 errors = 26 checksum characters (~ length * 1.25) * correct 13 errors = 51 checksum characters (~ length * 1.5) * correct 28 errors = 102 checksum characters (~ length * 2) So it really boils down to a trade-off between length of the code, and recovery properties. These two sets of codes are distinct (a code designed for length 93 has zero error correction properties when going above 93), so either we can pick a separate code for the two purposes, or be limited to the second set. If there is interest, I can construct a code + implementation for any of these in a few days probably, once the requirements are clear. Cheers, -- Pieter