From: "Luke-Jr" <luke@dashjr.org>
To: bitcoin-development@lists.sourceforge.net
Date: Wed, 15 May 2013 06:33:28 +0000
User-Agent: KMail/1.13.7 (Linux/3.9.0-gentoo; KDE/4.10.2; x86_64; ; )
MIME-Version: 1.0
Content-Type: Multipart/Mixed;
  boundary="Boundary-00=_7wykRH6kgNfe1w9"
Message-Id: <201305150633.31085.luke@dashjr.org>
Subject: [Bitcoin-development] RFC: c32d encoding
Precedence: list

--Boundary-00=_7wykRH6kgNfe1w9
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit

https://bitcointalk.org/?topic=205878

This encoding is designed so that it could replace Base58Check in new data, 
with the following goals in mind:
- Impossible(?) to manipulate without completely changing it
- Clearly identifiable prefix, regardless of data size
- Cheaper to process (simpler and faster code; it's a power-of-two radix)
- Fixed length string for fixed length data
- More unambiguous (removal of chars 'isuvzSVZ')
- Compatible with using seven-segment displays
- Altcoin friendly (16 bit namespace, which can be read without decoding)

Since there are fewer digits and more identifying/signature characters, 
addresses are longer. This should be less of a problem since ordinary users 
will hopefully be using addresses less common as the payment protocol becomes 
more popular.

Example Python code (including tests) is attached.
I can write up a formal BIP if this seems useful.

For example:

160 bits of data, such as current addresses:
    2nc111dhAPE2aUdYAOF88JhLn5jEjbULy4eFe9tyFYFE8
An ordinary P2SH destination, incorporating Greg's "require the hash mid-image 
to be relayed" concept (256 bits of data):
    2bc511A95e74P13dPb6b5t7yrh12EhC363ayH98n1cFbr3rAHdA49nCcC1G3P71j
The same key in Namecoin:
    2nc5119ttL35HPhc3Hh6aHe2tOhF6rdFtAOE1ahFLt9Ecabhcn5FLea5Le71P56C
The example "puzzle" script from the wiki (arbitrary scripting):
    2bc311d126acCyAnHAjabeUtOHcr7F811j4UYE6ECtOcbcGGn4O9chAt7O7y2LU9ty9cnG4
An alternative for BIP32 extended public keys (560 bits):
    2bc911AcchHheAGFnn9LC6FdF7bOc99APJtcEc46U655JheH6LCr3Y333eFEOtPJ9rj22rEcchHheAGFnn9LC6FdF7bOc99APJtcEc46U655JheH6LCr3YJCtPYea
An alternative for BIP32 extended private keys (552 bits):
    2bcb11O77GHdP53FH7Jh44OdEh3rLd4eFr2h7c8rGeErELG18yCy9O7L9LednyHJa5hyeAP77GHdP53FH7Jh44OdEh3rLd4eFr2h7c8rGeErELG18yCyGG5drPF1

--Boundary-00=_7wykRH6kgNfe1w9
Content-Type: text/x-python;
  charset="UTF-8";
  name="c32.py"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="c32.py"

# Digits are chosen to be the least ambiguous
# They all have unique seven-segment glyphs, and cannot be easily confused =
by humans
digits =3D '123456789abcdehjnrtyACEFGHJLOPUY'
radix =3D len(digits)

def encode(v):
	if not len(v):
		return ''
	n =3D 0
	bits =3D 0
	o =3D []
	pad =3D (len(v) * 8) % 5
	if pad:
		v =3D b'\0' + v
	v =3D bytearray(v)  # For Python 2.7 compatibility
	for i in range(len(v) - 1, -1, -1):
		n |=3D v[i] << bits
		bits +=3D 8
		while bits >=3D 5:
			o.insert(0, digits[n & 0x1f])
			n >>=3D 5
			bits -=3D 5
			if i =3D=3D 0 and pad:
				break
	return ''.join(o)

def decode(s):
	n =3D 0
	bits =3D 0
	o =3D bytearray()
	for i in range(len(s) - 1, -1, -1):
		n |=3D digits.index(s[i]) << bits
		bits +=3D 5
		while bits >=3D 8:
			o.insert(0, n & 0xff)
			n >>=3D 8
			bits -=3D 8
	return bytes(o)

def test():
	from math import ceil
	assert '' =3D=3D encode(b'')
	for (i, oc) in (
		(1, '8'),
		(2, '2'),
		(3, 'j'),
		(4, '4'),
		(5, 'Y'),
		(6, '8'),
		(7, '2'),
		(8, 'j'),
		(9, '4'),
	):
		ol =3D int(ceil(i * 8 / 5.))
		try:
			inzero =3D b'\0' * i
			inone =3D b'\xff' * i
			ezero =3D encode(inzero)
			eone =3D encode(inone)
			dzero =3D decode(ezero)
			done =3D decode(eone)
		=09
			assert ezero =3D=3D '1' * ol
			assert eone =3D=3D oc + ('Y' * (ol - 1))
			assert dzero =3D=3D inzero
			assert done =3D=3D inone
		except AssertionError:
			raise AssertionError('Input of length %s failed test' % (i,))
	try:
		for c in range(1024):
			decode('111' + chr(c))
	except ValueError:
		pass
	else:
		raise AssertionError('Invalid decode input (%02x) did not throw a ValueEr=
ror' % (c,))

if __name__ =3D=3D '__main__':
	test()
	print("Tests passed")

--Boundary-00=_7wykRH6kgNfe1w9
Content-Type: text/x-python;
  charset="UTF-8";
  name="c32d.py"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="c32d.py"

import c32
import hashlib
import struct

def _checksum(v):
	return hashlib.sha256(hashlib.sha256(v).digest()).digest()[-4:]

'''
String format:
=2D c32(Raw format) in reverse order

Raw format:
=2D 4 bytes checksum
=2D N bytes data (NOTE: encoded to prevent hidden changes)
=2D - for script:
=2D - - N bytes: varint preimage data length
=2D - - N bytes: preimage data
=2D - - N bytes: script data
=2D - for BIP32 HD parent key:
=2D - - 32 bytes: chain code
=2D - - 33 bytes: parent pubkey
=2D - for BIP32 serialized key:
=2D - - 1 byte: depth
=2D - - 4 bytes: child number
=2D - - 32 bytes: chain code
=2D - - One of:
=2D - - - 32 bytes: private key data
=2D - - - 33 bytes: public key data
=2D 1 byte flag (ignored if unknown)
=2D 1 byte type
=2D - 01 script (with preimage data)
=2D - 02 script hash preimage
=2D - 03 BIP32 HD parent key
=2D - 04 BIP32 serialized public key
=2D 2 bytes namespace (blockchain id)
=2D - 2d41 Bitcoin  ('2bc')
=2D - 2e01 Namecoin ('2nc')
=2D - 2e37 Freicoin ('FRC')
'''

class c32d:
	__slots__ =3D ('data', 'ns', 'dtype', 'dflag')
=09
	def __init__(self, data, ns, dtype, dflag):
		self.data =3D data
		self.ns =3D ns
		self.dtype =3D dtype
		self.dflag =3D dflag
=09
	@classmethod
	def decode(cls, s, raw =3D False):
		if not raw:
			full =3D c32.decode(s[::-1])
		else:
			full =3D s
	=09
		csum =3D bytearray(full[:4])
		v =3D bytearray(full[4:])
	=09
		# Encode the configuration bytes to simplify decoding
		pv =3D 0xbf
		for i in range(len(v) - 1, len(v) - 5, -1):
			pv =3D v[i] ^ (csum[i % 4]) ^ pv
			v[i] =3D pv
	=09
		v.append(0xbf)
		for i in range(len(v) - 1):
			v[i] ^=3D csum[i % 4] ^ v[i + 1]
		v.pop()
	=09
		v =3D bytes(v)
		if csum !=3D _checksum(v):
			raise ValueError('c32d checksum wrong')
	=09
		o =3D cls(None, None, None, None)
		o.data =3D v[:-4]
		o.dflag =3D v[-4]
		o.dtype =3D v[-3]
		o.ns =3D struct.unpack('!H', v[-2:])[0]
	=09
		return o
=09
	def encode(self, raw =3D False):
		try:
			v =3D self.data + struct.pack('!BBH', self.dflag, self.dtype, self.ns)
		except struct.error as e:
			raise ValueError(e)
		csum =3D bytearray(_checksum(v))
	=09
		v =3D bytearray(v)
		pv =3D 0xbf
		for i in range(len(v) - 1, -1, -1):
			pv =3D v[i] ^ csum[i % 4] ^ pv
			if i < len(v) - 4:
				v[i] =3D pv
		v =3D csum + bytes(v)
	=09
		if raw:
			return v
	=09
		return c32.encode(v)[::-1]

decode =3D c32d.decode

def encode(*a, **ka):
	return c32d(*a, **ka).encode()

def test():
	c32.test()
	for (p, s, raw) in (
		((b'', 0, 0, 0), '1111115Fd9acc', b'\xb5\xa5\x0c\xb9\x00\x00\x00\x00'),
		((b'test', 4232, 142, 219), '955OGe8hOGc97hH4EJj1', b'?V\x1e\\d/\x1cq\xdb=
\x8e\x10\x88'),
		((b'\xff' * 0x100, 0xffff, 0xff, 0xff), 'YYYYYYc327OYcC6F9Or6r14UYCJtc5UG=
t9n2YYbeH63jda5GnYjCEO3r8E53dGYFbchrG4c327OYcC6F9Or6r14UYCJtc5UGt9n2YYbeH63=
jda5GnYjCEO3r8E53dGYFbchrG4c327OYcC6F9Or6r14UYCJtc5UGt9n2YYbeH63jda5GnYjCEO=
3r8E53dGYFbchrG4c327OYcC6F9Or6r14UYCJtc5UGt9n2YYbeH63jda5GnYjCEO3r8E53dGYFb=
chrG4c327OYcC6F9Or6r14UYCJtc5UGt9n2YYbeH63jda5GnYjCEO3r8E53dGYFbchrG4c327OY=
cC6F9Or6r14UYCJtc5UGt9n2YYbeH63jda5GnYjCEO3r8E53dGYFbchrG4c327OYcC6F9Or6r14=
UYCJtc5UGb2cOdG3', b'\xb0\xce,*\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\x=
bf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc=
7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf=
0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88=
\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1=
\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j=
\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\=
xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\=
xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x=
88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\x=
c1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb=
9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x1=
2\xc7\x88\xb9j\xbf\xf0\xc1\x12\xc7\x88\xb9j\xbf\xf0\xc1\x12\xff\xff\xff\xff=
'),
	):
		(kp, pp) =3D ({}, p)
		for i in range(2):
			o =3D c32d(*pp, **kp)
			assert o.data =3D=3D p[0]
			assert o.ns =3D=3D p[1]
			assert o.dtype =3D=3D p[2]
			assert o.dflag =3D=3D p[3]
			kp =3D {
				'data': p[0],
				'ns': p[1],
				'dtype': p[2],
				'dflag': p[3],
			}
			pp =3D ()
		assert o.encode() =3D=3D s
		assert o.encode(raw=3DTrue) =3D=3D raw
=09
	def ensureValueError(f):
		try:
			f()
		except ValueError:
			pass
		else:
			raise AssertionError('Invalid decode input did not throw a ValueError')
	ensureValueError(lambda: encode(b'', -1, 0, 0))
	ensureValueError(lambda: encode(b'', 0x10000, 0, 0))
	ensureValueError(lambda: encode(b'', 0, -1, 0))
	ensureValueError(lambda: encode(b'', 0, 0x100, 0))
	ensureValueError(lambda: encode(b'', 0, 0, -1))
	ensureValueError(lambda: encode(b'', 0, 0, 0x100))
=09
	# Invalid c32d
	ensureValueError(lambda: decode('1111115Fd9adc'))
	ensureValueError(lambda: decode('11A1115Fd9acc'))
=09
	# Invalid c32
	ensureValueError(lambda: decode('111x115Fd9acc'))
	ensureValueError(lambda: decode('1111115Fd9acx'))

if __name__ =3D=3D '__main__':
	test()
	print("Tests passed")

--Boundary-00=_7wykRH6kgNfe1w9--