From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1UcVHY-0001kj-3T for bitcoin-development@lists.sourceforge.net; Wed, 15 May 2013 06:33:48 +0000 X-ACL-Warn: Received: from zinan.dashjr.org ([173.242.112.54]) by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1UcVHW-00059C-4h for bitcoin-development@lists.sourceforge.net; Wed, 15 May 2013 06:33:47 +0000 Received: from ishibashi.localnet (unknown [IPv6:2001:470:5:265:222:4dff:fe50:4c49]) (Authenticated sender: luke-jr) by zinan.dashjr.org (Postfix) with ESMTPSA id 5151027A2966 for ; Wed, 15 May 2013 06:33:35 +0000 (UTC) From: "Luke-Jr" 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; ; ) X-PGP-Key-Fingerprint: E463 A93F 5F31 17EE DE6C 7316 BD02 9424 21F4 889F X-PGP-Key-ID: BD02942421F4889F X-PGP-Keyserver: hkp://pgp.mit.edu MIME-Version: 1.0 Content-Type: Multipart/Mixed; boundary="Boundary-00=_7wykRH6kgNfe1w9" Message-Id: <201305150633.31085.luke@dashjr.org> X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.6 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain X-Headers-End: 1UcVHW-00059C-4h Subject: [Bitcoin-development] RFC: c32d encoding X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 May 2013 06:33:48 -0000 --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--