btcutil/bech32/bech32.go

// Copyright (c) 2017 The btcsuite developers
// Copyright (c) 2019 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.

package bech32

import (
	"strings"
)

// charset is the set of characters used in the data section of bech32 strings.
// Note that this is ordered, such that for a given charset[i], i is the binary
// value of the character.
const charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"

// gen encodes the generator polynomial for the bech32 BCH checksum.
var gen = []int{0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3}

// toBytes converts each character in the string 'chars' to the value of the
// index of the correspoding character in 'charset'.
func toBytes(chars string) ([]byte, error) {
	decoded := make([]byte, 0, len(chars))
	for i := 0; i < len(chars); i++ {
		index := strings.IndexByte(charset, chars[i])
		if index < 0 {
			return nil, ErrNonCharsetChar(chars[i])
		}
		decoded = append(decoded, byte(index))
	}
	return decoded, nil
}

// bech32Polymod calculates the BCH checksum for a given hrp, values and
// checksum data. Checksum is optional, and if nil a 0 checksum is assumed.
//
// Values and checksum (if provided) MUST be encoded as 5 bits per element (base
// 32), otherwise the results are undefined.
//
// For more details on the polymod calculation, please refer to BIP 173.
func bech32Polymod(hrp string, values, checksum []byte) int {
	chk := 1

	// Account for the high bits of the HRP in the checksum.
	for i := 0; i < len(hrp); i++ {
		b := chk >> 25
		hiBits := int(hrp[i]) >> 5
		chk = (chk&0x1ffffff)<<5 ^ hiBits
		for i := 0; i < 5; i++ {
			if (b>>uint(i))&1 == 1 {
				chk ^= gen[i]
			}
		}
	}

	// Account for the separator (0) between high and low bits of the HRP.
	// x^0 == x, so we eliminate the redundant xor used in the other rounds.
	b := chk >> 25
	chk = (chk & 0x1ffffff) << 5
	for i := 0; i < 5; i++ {
		if (b>>uint(i))&1 == 1 {
			chk ^= gen[i]
		}
	}

	// Account for the low bits of the HRP.
	for i := 0; i < len(hrp); i++ {
		b := chk >> 25
		loBits := int(hrp[i]) & 31
		chk = (chk&0x1ffffff)<<5 ^ loBits
		for i := 0; i < 5; i++ {
			if (b>>uint(i))&1 == 1 {
				chk ^= gen[i]
			}
		}
	}

	// Account for the values.
	for _, v := range values {
		b := chk >> 25
		chk = (chk&0x1ffffff)<<5 ^ int(v)
		for i := 0; i < 5; i++ {
			if (b>>uint(i))&1 == 1 {
				chk ^= gen[i]
			}
		}
	}

	if checksum == nil {
		// A nil checksum is used during encoding, so assume all bytes are zero.
		// x^0 == x, so we eliminate the redundant xor used in the other rounds.
		for v := 0; v < 6; v++ {
			b := chk >> 25
			chk = (chk & 0x1ffffff) << 5
			for i := 0; i < 5; i++ {
				if (b>>uint(i))&1 == 1 {
					chk ^= gen[i]
				}
			}
		}
	} else {
		// Checksum is provided during decoding, so use it.
		for _, v := range checksum {
			b := chk >> 25
			chk = (chk&0x1ffffff)<<5 ^ int(v)
			for i := 0; i < 5; i++ {
				if (b>>uint(i))&1 == 1 {
					chk ^= gen[i]
				}
			}
		}
	}

	return chk
}

// writeBech32Checksum calculates the checksum data expected for a string that
// will have the given hrp and payload data and writes it to the provided string
// builder.
//
// The payload data MUST be encoded as a base 32 (5 bits per element) byte slice
// and the hrp MUST only use the allowed character set (ascii chars between 33
// and 126), otherwise the results are undefined.
//
// For more details on the checksum calculation, please refer to BIP 173.
func writeBech32Checksum(hrp string, data []byte, bldr *strings.Builder) {
	polymod := bech32Polymod(hrp, data, nil) ^ 1
	for i := 0; i < 6; i++ {
		b := byte((polymod >> uint(5*(5-i))) & 31)

		// This can't fail, given we explicitly cap the previous b byte by the
		// first 31 bits.
		c := charset[b]
		bldr.WriteByte(c)
	}
}

// bech32VerifyChecksum verifies whether the bech32 string specified by the
// provided hrp and payload data (encoded as 5 bits per element byte slice) has
// the correct checksum suffix.
//
// Data MUST have more than 6 elements, otherwise this function panics.
//
// For more details on the checksum verification, please refer to BIP 173.
func bech32VerifyChecksum(hrp string, data []byte) bool {
	checksum := data[len(data)-6:]
	values := data[:len(data)-6]
	polymod := bech32Polymod(hrp, values, checksum)
	return polymod == 1
}

// DecodeNoLimit decodes a bech32 encoded string, returning the human-readable
// part and the data part excluding the checksum.  This function does NOT
// validate against the BIP-173 maximum length allowed for bech32 strings and
// is meant for use in custom applications (such as lightning network payment
// requests), NOT on-chain addresses.
//
// Note that the returned data is 5-bit (base32) encoded and the human-readable
// part will be lowercase.
func DecodeNoLimit(bech string) (string, []byte, error) {
	// The minimum allowed size of a bech32 string is 8 characters, since it
	// needs a non-empty HRP, a separator, and a 6 character checksum.
	if len(bech) < 8 {
		return "", nil, ErrInvalidLength(len(bech))
	}

	// Only	ASCII characters between 33 and 126 are allowed.
	var hasLower, hasUpper bool
	for i := 0; i < len(bech); i++ {
		if bech[i] < 33 || bech[i] > 126 {
			return "", nil, ErrInvalidCharacter(bech[i])
		}

		// The characters must be either all lowercase or all uppercase. Testing
		// directly with ascii codes is safe here, given the previous test.
		hasLower = hasLower || (bech[i] >= 97 && bech[i] <= 122)
		hasUpper = hasUpper || (bech[i] >= 65 && bech[i] <= 90)
		if hasLower && hasUpper {
			return "", nil, ErrMixedCase{}
		}
	}

	// Bech32 standard uses only the lowercase for of strings for checksum
	// calculation.
	if hasUpper {
		bech = strings.ToLower(bech)
	}

	// The string is invalid if the last '1' is non-existent, it is the
	// first character of the string (no human-readable part) or one of the
	// last 6 characters of the string (since checksum cannot contain '1').
	one := strings.LastIndexByte(bech, '1')
	if one < 1 || one+7 > len(bech) {
		return "", nil, ErrInvalidSeparatorIndex(one)
	}

	// The human-readable part is everything before the last '1'.
	hrp := bech[:one]
	data := bech[one+1:]

	// Each character corresponds to the byte with value of the index in
	// 'charset'.
	decoded, err := toBytes(data)
	if err != nil {
		return "", nil, err
	}

	// Verify if the checksum (stored inside decoded[:]) is valid, given the
	// previously decoded hrp.
	if !bech32VerifyChecksum(hrp, decoded) {
		// Invalid checksum. Calculate what it should have been, so that the
		// error contains this information.

		// Extract the payload bytes and actual checksum in the string.
		actual := bech[len(bech)-6:]
		payload := decoded[:len(decoded)-6]

		// Calculate the expected checksum, given the hrp and payload data.
		var expectedBldr strings.Builder
		expectedBldr.Grow(6)
		writeBech32Checksum(hrp, payload, &expectedBldr)
		expected := expectedBldr.String()

		err = ErrInvalidChecksum{
			Expected: expected,
			Actual:   actual,
		}
		return "", nil, err
	}

	// We exclude the last 6 bytes, which is the checksum.
	return hrp, decoded[:len(decoded)-6], nil
}

// Decode decodes a bech32 encoded string, returning the human-readable part and
// the data part excluding the checksum.
//
// Note that the returned data is 5-bit (base32) encoded and the human-readable
// part will be lowercase.
func Decode(bech string) (string, []byte, error) {
	// The maximum allowed length for a bech32 string is 90.
	if len(bech) > 90 {
		return "", nil, ErrInvalidLength(len(bech))
	}

	return DecodeNoLimit(bech)
}

// Encode encodes a byte slice into a bech32 string with the given
// human-readable part (HRP).  The HRP will be converted to lowercase if needed
// since mixed cased encodings are not permitted and lowercase is used for
// checksum purposes.  Note that the bytes must each encode 5 bits (base32).
func Encode(hrp string, data []byte) (string, error) {
	// The resulting bech32 string is the concatenation of the lowercase hrp,
	// the separator 1, data and the 6-byte checksum.
	hrp = strings.ToLower(hrp)
	var bldr strings.Builder
	bldr.Grow(len(hrp) + 1 + len(data) + 6)
	bldr.WriteString(hrp)
	bldr.WriteString("1")

	// Write the data part, using the bech32 charset.
	for _, b := range data {
		if int(b) >= len(charset) {
			return "", ErrInvalidDataByte(b)
		}
		bldr.WriteByte(charset[b])
	}

	// Calculate and write the checksum of the data.
	writeBech32Checksum(hrp, data, &bldr)

	return bldr.String(), nil
}

// ConvertBits converts a byte slice where each byte is encoding fromBits bits,
// to a byte slice where each byte is encoding toBits bits.
func ConvertBits(data []byte, fromBits, toBits uint8, pad bool) ([]byte, error) {
	if fromBits < 1 || fromBits > 8 || toBits < 1 || toBits > 8 {
		return nil, ErrInvalidBitGroups{}
	}

	// Determine the maximum size the resulting array can have after base
	// conversion, so that we can size it a single time. This might be off
	// by a byte depending on whether padding is used or not and if the input
	// data is a multiple of both fromBits and toBits, but we ignore that and
	// just size it to the maximum possible.
	maxSize := len(data)*int(fromBits)/int(toBits) + 1

	// The final bytes, each byte encoding toBits bits.
	regrouped := make([]byte, 0, maxSize)

	// Keep track of the next byte we create and how many bits we have
	// added to it out of the toBits goal.
	nextByte := byte(0)
	filledBits := uint8(0)

	for _, b := range data {

		// Discard unused bits.
		b = b << (8 - fromBits)

		// How many bits remaining to extract from the input data.
		remFromBits := fromBits
		for remFromBits > 0 {
			// How many bits remaining to be added to the next byte.
			remToBits := toBits - filledBits

			// The number of bytes to next extract is the minimum of
			// remFromBits and remToBits.
			toExtract := remFromBits
			if remToBits < toExtract {
				toExtract = remToBits
			}

			// Add the next bits to nextByte, shifting the already
			// added bits to the left.
			nextByte = (nextByte << toExtract) | (b >> (8 - toExtract))

			// Discard the bits we just extracted and get ready for
			// next iteration.
			b = b << toExtract
			remFromBits -= toExtract
			filledBits += toExtract

			// If the nextByte is completely filled, we add it to
			// our regrouped bytes and start on the next byte.
			if filledBits == toBits {
				regrouped = append(regrouped, nextByte)
				filledBits = 0
				nextByte = 0
			}
		}
	}

	// We pad any unfinished group if specified.
	if pad && filledBits > 0 {
		nextByte = nextByte << (toBits - filledBits)
		regrouped = append(regrouped, nextByte)
		filledBits = 0
		nextByte = 0
	}

	// Any incomplete group must be <= 4 bits, and all zeroes.
	if filledBits > 0 && (filledBits > 4 || nextByte != 0) {
		return nil, ErrInvalidIncompleteGroup{}
	}

	return regrouped, nil
}

// EncodeFromBase256 converts a base256-encoded byte slice into a base32-encoded
// byte slice and then encodes it into a bech32 string with the given
// human-readable part (HRP).  The HRP will be converted to lowercase if needed
// since mixed cased encodings are not permitted and lowercase is used for
// checksum purposes.
func EncodeFromBase256(hrp string, data []byte) (string, error) {
	converted, err := ConvertBits(data, 8, 5, true)
	if err != nil {
		return "", err
	}
	return Encode(hrp, converted)
}

// DecodeToBase256 decodes a bech32-encoded string into its associated
// human-readable part (HRP) and base32-encoded data, converts that data to a
// base256-encoded byte slice and returns it along with the lowercase HRP.
func DecodeToBase256(bech string) (string, []byte, error) {
	hrp, data, err := Decode(bech)
	if err != nil {
		return "", nil, err
	}
	converted, err := ConvertBits(data, 5, 8, false)
	if err != nil {
		return "", nil, err
	}
	return hrp, converted, nil
}