Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8B4462C for ; Sat, 23 Jun 2018 19:49:56 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f45.google.com (mail-oi0-f45.google.com [209.85.218.45]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 23D235E2 for ; Sat, 23 Jun 2018 19:49:56 +0000 (UTC) Received: by mail-oi0-f45.google.com with SMTP id e8-v6so9081240oii.2 for ; Sat, 23 Jun 2018 12:49:56 -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 :cc; bh=TgoK/pxyFIbdgkd/V1RngUyZJm0p0aXy29cHGyGLDBQ=; b=C3jSBBRVa/rkW783IqGeO3VFMkkRq8C0SnooYlkfQVcV1RU35iVbHmAk842ft1HrUf WVxF4jzkzJdpu2dfVVbyB2ZL7qoLEXJ5e2lEBYEVFTR4s7heB2KFIXN2aIcCz1eRu8aq YnqsXwZnpdCbmWItNpWtnmFjNoxCHwtKAKQ7pUiDx3akxI2xB8R41FNyBoHpE0cFMqXK TH7YO0T+LKCUjUXUSrtLd5UKoJ0o7FkptyR9YgriMr36CnNqTc4JUnsX+f2Fj/bjtUOL R0mYUv7Qkbh2zNb7sBO+STLSV86AIcL0fa928n1oWArnlX5A7EVdRM3+eI/McyvbXTnZ 756A== 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:cc; bh=TgoK/pxyFIbdgkd/V1RngUyZJm0p0aXy29cHGyGLDBQ=; b=XVe/5hCgtEciLXSOsSw78u1CpDnUNwoXwO9ajefrGzYESbRZZlRPYnlhZlByLfyWS/ l4EDP3kMYHS72MM+H9ByHXd3WeJj1LubbTGG8d5NbPGBkYrPXi3nnD2WESM3wM2yXOgS DcdJNQmdANP+vfHJPMASepojq+frcSUsFF0eMMHoqIKsz/kSGflvWeAbY3LjwaZXg0nw ixLu1v0kPvU++7zE5sITAiwhlL+jpHfDQ4u6rSLvjk22PjqRjTXCSqCVaDE0omHS0ZHm ien4uqqPbwTviYm4/WGeRqLY6aMVY2lWy+WHlSBSafNssAv88Inx/BXojDoWjbE0rVq+ OG+A== X-Gm-Message-State: APt69E1SjtOqiE8HDelbguCicKCnWcvHyPD4FjOSu9dBnP7CrdGsBCn0 To3VNUpnL5kGMtgz25ODOYLTL8A1YFGfXQhCrW/gdA== X-Google-Smtp-Source: ADUXVKJvsMItY6eTks/z6TpFulxDM+q+fVXl7uDWVgGFqQhtv8ElF6nEPgXHaMc8z3nRT0d5P7jTDJCF5DclThnrsso= X-Received: by 2002:aca:5887:: with SMTP id m129-v6mr3636617oib.76.1529783395263; Sat, 23 Jun 2018 12:49:55 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a4a:6a89:0:0:0:0:0 with HTTP; Sat, 23 Jun 2018 12:49:54 -0700 (PDT) In-Reply-To: References: From: Pieter Wuille Date: Sat, 23 Jun 2018 12:49:54 -0700 Message-ID: To: "Russell O'Connor" 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 Cc: Bitcoin Protocol Discussion 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: Sat, 23 Jun 2018 19:49:56 -0000 On Fri, Jun 15, 2018 at 8:54 AM, Russell O'Connor wrote: > >> 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. > > > At the risk of making the proposal more complex, I wonder if it might be > better to support multiple checksum variants? The trade-off between code > length and recovery seems to be largely determined by the user's medium of > storage, which is likely to vary from person to person. I personally would > probably be interested in the 51 or even 102 character checksums variants. Here are some more numbers then. It's important to note that the number of correctable errors includes errors inside the checksum characters themselves. So if you want to aim for a certain percentage of correctable characters, the numbers go up much more dramatically. For codes restricted to 341 characters total (including the checksum characters), and assuming 103 data characters (enough for 512 bits): * With 26 checksum characters (adding 25%, 20% of overall string), 7 errors can be corrected (5% of overall string) * With 62 checksum characters (adding 60%, 38% of overall string), 17 errors can be corrected (10% of overall string) * With 116 checksum characters (adding 113%, 53% of overall string), 33 errors can be corrected (15% of overall string) * With 195 checksum characters (adding 189%, 65% of overall string), 60 errors can be corrected (20% of overall string) For codes restricted to 1023 characters total (including the checksum characters), and assuming 103 data characters (enough for 512 bits): * With 27 checksum characters (adding 26%, 21% of overall string), 7 errors can be corrected (5% of overall string) * With 64 checksum characters (adding 62%, 38% of overall string), 17 errors can be corrected (10% of overall string) * With 127 checksum characters (adding 123%, 57% of overall string), 36 errors can be corrected (15% of overall string) * With 294 checksum characters (adding 285%, 74% of overall string), 80 errors can be corrected (20% of overall string) * With 920 checksum characters (adding 893%, 90% of overall string), 255 errors can be corrected (25% of overall string) I'll gladly construct reference source code for any of these. Cheers, -- Pieter