lnlink

iOS app for connecting to lightning nodes
git clone git://jb55.com/lnlink
Log | Files | Refs | Submodules | README

Bech32.swift (11675B)

      1 //  Copyright (c) 2017 Alex Bosworth
      2 //  Copyright (c) 2017 Pieter Wuille
      3 //
      4 // Permission is hereby granted, free of charge, to any person obtaining a copy
      5 // of this software and associated documentation files (the "Software"), to deal
      6 // in the Software without restriction, including without limitation the rights
      7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      8 // copies of the Software, and to permit persons to whom the Software is
      9 // furnished to do so, subject to the following conditions:
     10 //
     11 // The above copyright notice and this permission notice shall be included in
     12 // all copies or substantial portions of the Software.
     13 //
     14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
     20 // THE SOFTWARE.
     21 //
     22 
     23 import Foundation
     24 
     25 extension String {
     26   func lastIndex(of string: String) -> Int? {
     27     guard let range = self.range(of: string, options: .backwards) else { return nil }
     28 
     29     return self.distance(from: startIndex, to: range.lowerBound)
     30   }
     31 }
     32 
     33 let CHARSET = byteConvert(string: "qpzry9x8gf2tvdw0s3jn54khce6mua7l")
     34 let GENERATOR = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
     35 
     36 func polymod(_ values: [Int]) -> Int {
     37   return values.reduce(1) { chk, value in
     38     let top = chk >> 25
     39 
     40     return (Int()..<5).reduce((chk & 0x1ffffff) << 5 ^ value) { chk, i in
     41       guard (top >> i) & 1 > Int() else { return chk }
     42 
     43       return chk ^ GENERATOR[i]
     44     }
     45   }
     46 }
     47 
     48 func hrpExpand(_ hrp: [UInt8]) -> [UInt8] {
     49   return (Int()..<hrp.count).map { hrp[$0] >> 5 } + [UInt8()] + (Int()..<hrp.count).map { hrp[$0] & 31 }
     50 }
     51 
     52 func verifyChecksum(hrp: [UInt8], data: [UInt8]) -> Bool {
     53   return polymod((hrpExpand(hrp) + data).map { Int($0) }) == 1
     54 }
     55 
     56 func createChecksum(hrp: [UInt8], data: [UInt8]) -> [UInt8] {
     57   let values = (hrpExpand(hrp) + data + Array(repeating: UInt8(), count: 6)).map { Int($0) }
     58   let mod: Int = polymod(values) ^ 1
     59 
     60   return (Int()..<6).map { (mod >> (5 * (5 - $0))) & 31 }.map { UInt8($0) }
     61 }
     62 
     63 func byteConvert(string: String) -> [UInt8] {
     64   return string.map { String($0).unicodeScalars.first?.value }.flatMap { $0 }.map { UInt8($0) }
     65 }
     66 
     67 func stringConvert(bytes: [UInt8]) -> String {
     68   return bytes.reduce(String(), { $0 + String(format: "%c", $1)})
     69 }
     70 
     71 func encode(hrp: [UInt8], data: [UInt8]) -> String {
     72   let checksum = createChecksum(hrp: hrp, data: data)
     73 
     74   return stringConvert(bytes: hrp) + "1" + stringConvert(bytes: (data + checksum).map { CHARSET[Int($0)] })
     75 }
     76 
     77 enum DecodeBech32Error: Error {
     78   case caseMixing
     79   case inconsistentHrp
     80   case invalidAddress
     81   case invalidBits
     82   case invalidCharacter(String)
     83   case invalidChecksum
     84   case invalidPayToHashLength
     85   case invalidVersion
     86   case missingSeparator
     87   case missingVersion
     88 
     89   var localizedDescription: String {
     90     switch self {
     91     case .caseMixing:
     92       return "Mixed case characters are not allowed"
     93 
     94     case .inconsistentHrp:
     95       return "Internally inconsistent HRP"
     96 
     97     case .invalidAddress:
     98       return "Address is not a valid type"
     99 
    100     case .invalidBits:
    101       return "Bits are not valid"
    102 
    103     case .invalidCharacter(let char):
    104       return "Character \"\(char)\" is not valid"
    105 
    106     case .invalidChecksum:
    107       return "Checksum failed to verify data"
    108 
    109     case .invalidPayToHashLength:
    110       return "Unknown hash length for encoded output payload hash"
    111 
    112     case .invalidVersion:
    113       return "Invalid version number"
    114 
    115     case .missingSeparator:
    116       return "Missing address data separator"
    117 
    118     case .missingVersion:
    119       return "Missing address version"
    120     }
    121   }
    122 }
    123 
    124 public func decodeBech32(bechString: String) throws -> (hrp: [UInt8], data: [UInt8]) {
    125   let bechBytes = byteConvert(string: bechString)
    126 
    127   guard !(bechBytes.contains() { $0 < 33 && $0 > 126 }) else { throw DecodeBech32Error.invalidCharacter(bechString) }
    128 
    129   let hasLower = bechBytes.contains() { $0 >= 97 && $0 <= 122 }
    130   let hasUpper = bechBytes.contains() { $0 >= 65 && $0 <= 90 }
    131 
    132   if hasLower && hasUpper { throw DecodeBech32Error.caseMixing }
    133 
    134   let bechString = bechString.lowercased()
    135 
    136   guard let pos = bechString.lastIndex(of: "1") else { throw DecodeBech32Error.missingSeparator }
    137 
    138   if pos < 1 || pos + 7 > bechString.count {
    139     throw DecodeBech32Error.missingSeparator
    140   }
    141 
    142   let bechStringBytes = byteConvert(string: bechString)
    143   let hrp = byteConvert(string: bechString.substring(to: bechString.index(bechString.startIndex, offsetBy: pos)))
    144 
    145   let data: [UInt8] = try ((pos + 1)..<bechStringBytes.count).map { i in
    146       guard let d = CHARSET.firstIndex(of: bechStringBytes[i]) else {
    147       throw DecodeBech32Error.invalidCharacter(stringConvert(bytes: [bechStringBytes[i]]))
    148     }
    149 
    150     return UInt8(d)
    151   }
    152 
    153   guard verifyChecksum(hrp: hrp, data: data) else { throw DecodeBech32Error.invalidChecksum }
    154 
    155   return (hrp: hrp, data: Array(data[Int()..<data.count - 6]))
    156 }
    157 
    158 func convertbits(data: [UInt8], fromBits: Int, toBits: Int, pad: Bool) throws -> [UInt8] {
    159   var acc = Int()
    160   var bits = UInt8()
    161   let maxv = (1 << toBits) - 1
    162 
    163   let converted: [[Int]] = try data.map { value in
    164     if (value < 0 || (UInt8(Int(value) >> fromBits)) != 0) {
    165       throw DecodeBech32Error.invalidCharacter(stringConvert(bytes: [value]))
    166     }
    167 
    168     acc = (acc << fromBits) | Int(value)
    169     bits += UInt8(fromBits)
    170 
    171     var values = [Int]()
    172 
    173     while bits >= UInt8(toBits) {
    174       bits -= UInt8(toBits)
    175       values += [(acc >> Int(bits)) & maxv]
    176     }
    177 
    178     return values
    179   }
    180 
    181   let padding = pad && bits > UInt8() ? [acc << (toBits - Int(bits)) & maxv] : []
    182 
    183   if !pad && (bits >= UInt8(fromBits) || acc << (toBits - Int(bits)) & maxv > Int()) {
    184     throw DecodeBech32Error.invalidBits
    185   }
    186 
    187   return ((converted.flatMap { $0 }) + padding).map { UInt8($0) }
    188 }
    189 
    190 func encode(hrp: [UInt8], version: UInt8, program: [UInt8]) throws -> String {
    191   let address = try encode(hrp: hrp, data: [version] + convertbits(data: program, fromBits: 8, toBits: 5, pad: true))
    192 
    193   // Confirm encoded address parses without error
    194   let _ = try decodeAddress(hrp: hrp, address: address)
    195 
    196   return address
    197 }
    198 
    199 func decodeAddress(hrp: [UInt8], address: String) throws -> (version: UInt8, program: [UInt8]) {
    200   let decoded = try decodeBech32(bechString: address)
    201 
    202   // Confirm decoded address matches expected type
    203   guard stringConvert(bytes: decoded.hrp) == stringConvert(bytes: hrp) else { throw DecodeBech32Error.inconsistentHrp }
    204 
    205   // Confirm version byte is present
    206   guard let versionByte = decoded.data.first else { throw DecodeBech32Error.missingVersion }
    207 
    208   // Confirm version byte is within the acceptable range
    209   guard !decoded.data.isEmpty && versionByte <= 16 else { throw DecodeBech32Error.invalidVersion }
    210 
    211   let program = try convertbits(data: Array(decoded.data[1..<decoded.data.count]), fromBits: 5, toBits: 8, pad: false)
    212 
    213   // Confirm program is a valid length
    214   guard program.count > 1 && program.count < 41 else { throw DecodeBech32Error.invalidAddress }
    215 
    216   if versionByte == UInt8() {
    217     // Confirm program is a known byte length (20 for pkhash, 32 for scripthash)
    218     guard program.count == 20 || program.count == 32 else { throw DecodeBech32Error.invalidPayToHashLength }
    219   }
    220 
    221   return (version: versionByte, program: program)
    222 }
    223 
    224 func segwitScriptPubKey(version: UInt8, program: [UInt8]) -> [UInt8] {
    225   return [version > UInt8() ? version + 0x50 : UInt8(), UInt8(program.count)] + program
    226 }
    227 
    228 
    229 /*
    230 class TestBech32: XCTestCase {
    231   func testInvalidAddresses() {
    232     let INVALID_ADDRESS = [
    233       "tc1qw508d6qejxtdg4y5r3zarvary0c5xw7kg3g4ty",
    234       "bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5",
    235       "BC13W508D6QEJXTDG4Y5R3ZARVARY0C5XW7KN40WF2",
    236       "bc1rw5uspcuh",
    237       "bc10w508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kw5rljs90",
    238       "BC1QR508D6QEJXTDG4Y5R3ZARVARYV98GJ9P",
    239       "tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sL5k7",
    240       "tb1pw508d6qejxtdg4y5r3zarqfsj6c3",
    241       "tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3pjxtptv",
    242     ]
    243 
    244     INVALID_ADDRESS.forEach { test in
    245       ["bc", "tb"].forEach { type in
    246         do {
    247           let _ = try decodeAddress(hrp: byteConvert(string: type), address: test)
    248 
    249           XCTFail("Expected invalid address: \(test)")
    250         } catch {
    251           return
    252         }
    253       }
    254     }
    255   }
    256 
    257   func testChecksums() {
    258     let VALID_CHECKSUM: [String] = [
    259       "A12UEL5L",
    260       "an83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgs",
    261       "abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw",
    262       "11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247j",
    263       "split1checkupstagehandshakeupstreamerranterredcaperred2y9e3w"
    264     ]
    265 
    266     do {
    267       try VALID_CHECKSUM.forEach { test in
    268         let _ = try decodeBech32(bechString: test)
    269       }
    270     } catch {
    271       XCTFail(error.localizedDescription)
    272     }
    273   }
    274 
    275   func testValidAddresses() {
    276     let VALID_BC_ADDRESSES: [String: (decoded: [UInt8], type: String)] = [
    277       "BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T4": (
    278         decoded: [
    279           0x00, 0x14, 0x75, 0x1e, 0x76, 0xe8, 0x19, 0x91, 0x96, 0xd4, 0x54,
    280           0x94, 0x1c, 0x45, 0xd1, 0xb3, 0xa3, 0x23, 0xf1, 0x43, 0x3b, 0xd6
    281         ],
    282         type: "bc"
    283       ),
    284 
    285       "tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7": (
    286         decoded: [
    287           0x00, 0x20, 0x18, 0x63, 0x14, 0x3c, 0x14, 0xc5, 0x16, 0x68, 0x04,
    288           0xbd, 0x19, 0x20, 0x33, 0x56, 0xda, 0x13, 0x6c, 0x98, 0x56, 0x78,
    289           0xcd, 0x4d, 0x27, 0xa1, 0xb8, 0xc6, 0x32, 0x96, 0x04, 0x90, 0x32,
    290           0x62
    291         ],
    292         type: "tb"
    293       ),
    294 
    295       "bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7k7grplx": (
    296         decoded: [
    297           0x51, 0x28, 0x75, 0x1e, 0x76, 0xe8, 0x19, 0x91, 0x96, 0xd4, 0x54,
    298           0x94, 0x1c, 0x45, 0xd1, 0xb3, 0xa3, 0x23, 0xf1, 0x43, 0x3b, 0xd6,
    299           0x75, 0x1e, 0x76, 0xe8, 0x19, 0x91, 0x96, 0xd4, 0x54, 0x94, 0x1c,
    300           0x45, 0xd1, 0xb3, 0xa3, 0x23, 0xf1, 0x43, 0x3b, 0xd6
    301         ],
    302         type: "bc"
    303       ),
    304 
    305       "BC1SW50QA3JX3S": (decoded: [0x60, 0x02, 0x75, 0x1e], type: "bc"),
    306 
    307       "bc1zw508d6qejxtdg4y5r3zarvaryvg6kdaj": (
    308         decoded: [
    309           0x52, 0x10, 0x75, 0x1e, 0x76, 0xe8, 0x19, 0x91, 0x96, 0xd4, 0x54,
    310           0x94, 0x1c, 0x45, 0xd1, 0xb3, 0xa3, 0x23
    311         ],
    312         type: "bc"
    313       ),
    314 
    315       "tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy": (
    316         decoded: [
    317           0x00, 0x20, 0x00, 0x00, 0x00, 0xc4, 0xa5, 0xca, 0xd4, 0x62, 0x21,
    318           0xb2, 0xa1, 0x87, 0x90, 0x5e, 0x52, 0x66, 0x36, 0x2b, 0x99, 0xd5,
    319           0xe9, 0x1c, 0x6c, 0xe2, 0x4d, 0x16, 0x5d, 0xab, 0x93, 0xe8, 0x64,
    320           0x33
    321         ],
    322         type: "tb"
    323       )
    324     ]
    325 
    326     do {
    327       try VALID_BC_ADDRESSES.forEach { address, result in
    328         let scriptPubKey = result.decoded
    329         let hrp = byteConvert(string: result.type)
    330 
    331         let ret = try decodeAddress(hrp: hrp, address: address)
    332 
    333         let output = segwitScriptPubKey(version: ret.version, program: ret.program)
    334 
    335         XCTAssertEqual(output, scriptPubKey)
    336 
    337         let recreated = try encode(hrp: hrp, version: ret.version, program: ret.program).lowercased()
    338 
    339         XCTAssertEqual(recreated, address.lowercased())
    340       }
    341     } catch {
    342       XCTFail(error.localizedDescription)
    343     }
    344   }
    345 }
    346 
    347  */