Bitcoin Bech32 address decode / validation

Bitcoin Bech32 address decode / validation - one mutable and one version with fold added.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70:

let charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
let generator: int list = [0x3b6a57b2; 0x26508e6d; 0x1ea119fa; 0x3d4233dd; 0x2a1462b3]

(*
    Bitcoin Bech32 address decode / validation
*)

let bech32Polymod (values:int list) =
    let mutable chk = 1
    for v in values do
        let b = chk >>> 25
        chk <- ((chk &&& 0x1ffffff) <<< 5) ^^^ v 
        for i in [0..4] do
            if ((b >>> i) &&& 1) = 1 then
                chk <- chk ^^^ generator.[i]
    chk



let bech32PolymodFold (values:int list) =
    (1,values)
    ||> List.fold (fun chk v ->
        let b = chk >>> 25
        let chk = ((chk &&& 0x1ffffff) <<< 5) ^^^ v
        let chk =
            (chk,[0..4])
            ||> List.fold (fun chk i -> if (b >>> i) &&& 1 = 1 then chk ^^^ generator.[i] else chk)
        chk
    )


let hrpExpand (hrp:string) =
    (hrp |> Seq.map (fun c -> c |> int >>> 5) |> Seq.toList)
    @
    [0]
    @
    (hrp |> Seq.map (fun c -> c |> int &&& 31) |> Seq.toList)



let verifyChecksum hrp data =
    let hrpExpand = hrp |> hrpExpand
    bech32PolymodFold (hrpExpand @ data) = 1


let decode (str:string) =
    let lastOneIndex = str.IndexOf('1')
    let hrp = str.[0..lastOneIndex-1]
    let data = str.[lastOneIndex+1..]
    let data =
        data
        |> Seq.map (fun c ->
            let v = charset.IndexOf c
            if v = -1 then 
                failwith "invalid bech32 address"
            else
                v
        )
        |> Seq.toList
    
    if verifyChecksum hrp data then
        hrp, data
    else
        failwith "invalid bech32 address"



decode "bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4"

decode "abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw"

val charset : string

Full name: Script.charset

val generator : int list

Full name: Script.generator

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val bech32Polymod : values:int list -> int

Full name: Script.bech32Polymod

val values : int list

val mutable chk : int

val v : int

val b : int

val i : int

val bech32PolymodFold : values:int list -> int

Full name: Script.bech32PolymodFold

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold

val chk : int

val hrpExpand : hrp:string -> int list

Full name: Script.hrpExpand

val hrp : string

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

module Seq

from Microsoft.FSharp.Collections

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val c : char

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val verifyChecksum : hrp:string -> data:int list -> bool

Full name: Script.verifyChecksum

val data : int list

val hrpExpand : int list

val decode : str:string -> string * int list

Full name: Script.decode

val str : string

val lastOneIndex : int

System.String.IndexOf(value: string) : int
System.String.IndexOf(value: char) : int
System.String.IndexOf(value: string, comparisonType: System.StringComparison) : int
System.String.IndexOf(value: string, startIndex: int) : int
System.String.IndexOf(value: char, startIndex: int) : int
System.String.IndexOf(value: string, startIndex: int, comparisonType: System.StringComparison) : int
System.String.IndexOf(value: string, startIndex: int, count: int) : int
System.String.IndexOf(value: char, startIndex: int, count: int) : int
System.String.IndexOf(value: string, startIndex: int, count: int, comparisonType: System.StringComparison) : int

val data : string

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

Raw view Test code New version

More information

Link:	http://fssnip.net/7Xt
Posted:	4 years ago
Author:	Daniel Hardt
Tags:	bitcoin , decode , validation , berch32