Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Bech32: a base32 address format

Presentation for SF Bitcoin Devs, 2017-03-27
by

Pieter Wuille

on 30 September 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Bech32: a base32 address format

Bech32 addresses for Bitcoin
Pieter Wuille
March 27, 2017 - SF Bitcoin Devs
Thank you!
133E AC17 9436 F14A 5CF1 B794 860F EB80 4E66 9320

Why?
Checksum
Base 32
Character set
Structure
Bech32
Segregated Witness outputs: P2SH or native

* P2SH: compatible with old clients

* Native: more efficient and 128-bit secure

Old proposal: BIP142
* 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
Existing uses: Tor, I2P, ZRTP, Tahoe-LAFS
Minimum distance of a code
CRC codes
RS codes
BCH codes
Design for distance 5 possible!
Minimum distance 4
Detects 3 errors.

Corrects 1 error.
Bit error based:

A B C D E
01010 01011 01100 01101 01110

A
J
C
V
E
01010
10100
01100
10
1
10
01110

Bitwise cyclic: unnecessary
Naively: distance 2
Effectively: distance 4
Symbol based!
Limited to length < alphabet size. 31 = too short

Alphabet extension: use 2 characters at once
* Still only distance 4
Choice: 6 characters extra
Message length 71
Not limited to length 31
Usually bitwise, but not necessarily.

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...
BCH code selection
And many more...
Distance 6 for these!
* Analyse all 71-character addresses?


* Linear codes!


* Collision search!
73391955711682288371546268649666782105490079653384995959602842860381532034831513858240593699524021969747968 combinations :(
12024159379589 combinations :(
1702704605 combinations :)
bc
1
q
w508d6qejxtdg4y5r3zarvary0c5xw7k
v8f3t4

* Human-readable part (any character)
* Separator "1"
* Data part (Base 32 character set encoded):
* Witness version
* Witness program
* Checksum
* 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
* Effective length 42 (P2WPKH), 62 (P2WSH)
* Up to length 74 for future witness versions.
Full transcript