Bech32: a base32 address format

Why?

Checksum

Minimum distance of a code

Minimum distance 4

Detects 3 errors.

Corrects 1 error.

Choice: 6 characters extra

Message length 71

Segregated Witness outputs: P2SH or native

* P2SH: compatible with old clients

* Native: more efficient and 128-bit secure

BCH codes

CRC codes

RS codes

Symbol based!

Not limited to length 31

Usually bitwise, but not necessarily.

Design for distance 5 possible!

BCH code selection

Limited to length < alphabet size. 31 = too short

Alphabet extension: use 2 characters at once

* Still only distance 4

Bit error based:

A B C D E

01010 01011 01100 01101 01110

A J C V E

01010 10100 01100 10110 01110

73391955711682288371546268649666782105490079653384995959602842860381532034831513858240593699524021969747968 combinations :(

* Analyse all 71-character addresses?

* Linear codes!

* Collision search!

12024159379589 combinations :(

1702704605 combinations :)

Large design space: how to pick one?

* Start with 159605 codes: all distance 4 at length 71 or more

* Require distance 5 at length 71: 28825 left

* Pick the codes with the best worst case: 310 left

* Pick the codes with the best bit error behaviour: 2 left

* Pick one randomly

Many years of CPU time.... until we found symmetries

Tested all 3.58M 6-character cyclic codes...

Naively: distance 2

Effectively: distance 4

Bitwise cyclic: unnecessary

Old proposal: BIP142

Character set

Bech32

Base 32

* Case insensitive: easier to read/write

* Simple to convert (no bignum logic)

* Only 17% larger than Base 58

* Better checksums for prime power

* More compact in QR

* BIP address proposal:

https://github.com/sipa/bech32/blob/master/bip-witaddr.mediawiki

* Code complexity?

* Demo website with error location:

http://bitcoin.sipa.be/bech32/demo/demo.html

* Reference implementation is 122 lines of Python code

* Actual checksum algorithm: 10 lines

def bech32_polymod(values):

"""Internal function that computes the Bech32 checksum."""

generator = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]

chk = 1

for value in values:

top = chk >> 25

chk = (chk & 0x1ffffff) << 5 ^ value

for i in range(5):

chk ^= generator[i] if ((top >> i) & 1) else 0

return chk

No bignum code, no SHA256 dependency

Existing uses: Tor, I2P, ZRTP, Tahoe-LAFS

And many more...

Distance 6 for these!

Structure

bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4

* Human-readable part (any character)

* Separator "1"

* Data part (Base 32 character set encoded):

* Witness version

* Witness program

* Checksum

* Effective length 42 (P2WPKH), 62 (P2WSH)

* Up to length 74 for future witness versions.

Bech32 addresses for Bitcoin

Pieter Wuille

133E AC17 9436 F14A 5CF1 B794 860F EB80 4E66 9320

March 27, 2017 - SF Bitcoin Devs

Thank you!