Cardano-wallet: Bech32 Library

[KtorZ]

Context

In Shelley, addresses are encoded in bech32. A reference implementation (in Haskell) for bech32 encoding available here.

Decision

• Evaluate the quality of this reference implementation
• Extract it as a package and re-locate it in our lib/
• Add extra tests, if necessary
• Adjust the code to comply to our coding standards
• Adjust the reference implementation API to be eas(ier)y-to-use (for instance, having a decode :: Text -> Maybe Text or similar could be quite handy).

Acceptance Criteria

1. We _must_ support bech32 encoding & decoding
2. We _should_ provide a comprehensible and easy-to-use API for this module

---

Development Plan

PR

| Number | Base |
| --- | --- |
| #248 | master |
| #271 | master |
| #277 | master |

QA

• The reference implementation has been ported and adjusted to remove the bits that were bitcoin-specifics; we end up with a tiny API that is visible on haddock

• The code is fully tested here:

  • We've ported existing tests from the reference implementation see Codec.Binary.Bech32Spec
  • We've also added roundtrip tests for most of the conversions functions, see Codec.Binary.Bech32Spec

• There's an extra PR which outlines some work to perform error-detection (bech32 allows for identifying with a rather good precision _where_ an error is located within the address string). This is still experimental and unpolished so, might be done in another ticket for it is a bit out of scope for this particular one.

[rvl]

I am against reformatting code of vendored dependencies.
It doesn't improve the functionality in any way, and will make applying changes more difficult if the reference implementation changes.

[jonathanknowles]

@rvl @KtorZ

Current limitations of the reference implementation.

Building

The reference implementation is not available on Hackage.

Testing

1. Several building-block functions are not individually tested for correctness.

   • convertBits, toBase32, toBase256, bech32HRPExpand

2. Certain properties that should hold between functions are not individually tested. For example:

   • the inverse relationship between toBase32 and toBase256
   • the inverse relationship between charset and charsetMap
   • the inverse relationship between bech32Encode and bech32Decode
   • the inverse relationship between segwitEncode and segwitDecode

3. Certain properties of the decoder that could be tested are not tested. For example, all of the transformations below should cause the decoder to fail:

   • omitting one or more characters from a valid address.
   • mutating one or more characters within a valid address.
   • swapping pairs of characters within a valid address.

Usability

When a user inputs an address, we would ideally like to be able to give them feedback if the address contains an error. Ideally, our user interface would be able to show something like this:

                             ^ 
                      Invalid character

The bech32 format is actually designed to make it possible to give this kind of feedback in many cases.

However, the Haskell reference implementation doesn't provide this functionality. Although the bech32Decode and segwitDecode functions both reject invalid inputs, their return types don't discriminate between different types of failure. If we were to use the reference implementation as-is, then we wouldn't be able to give the user feedback that would allow them to fix their invalid input.

For example, all of the following failure cases will cause the above functions to evaluate to Nothing:

• The input is too long.
• The input is mixed case (only all-lower-case or all-upper-case addresses are acceptable).
• The human-readable portion contains an invalid character (at an identifiable position).
• The input is missing the 1 separator between the human-readable portion and the data portion.
• The data portion contains an invalid character (at an identifiable position).
• The data portion contains one or more characters that don't match the checksum (at an identifiable position). This is possible when the input contains exactly one or two mistakes. See this demonstration decoder, using bc1qw508d6qejxtdg4y6r3zarvary2c5xw7kv8f3t4 as an example invalid address.

Solutions:

Testing

We could solve 1–3 by building a suite of property tests (but we'd need to patch the original code to export lower-level functions that are not currently exported).

Usability

We could solve the user-feedback limitation by rewriting the bech32Decode and segwitDecode functions so that they return more information in the case of failure, using a richer set of types to represent failure. We can transform failure values into rich feedback for the user.

[jonathanknowles]

@rvl wrote:

I am against reformatting code of vendored dependencies.
It doesn't improve the functionality in any way, and will make applying changes more difficult if the reference implementation changes.

Assuming that it's feasible for us to push our changes upstream, and then consume upstream as an ordinary library (the ideal scenario), then I completely agree with this objection.

On the other hand, if we're aiming to (effectively) produce a new library (with code that is substantially different from the reference implementation), then I think this becomes less necessary. We do need to show that our implementation meets the specification, however.

[KtorZ]

@rvl Point is we'll probably not push changes upstream as this isn't a vendored dependency but a reference implementation on a repository. I'd be keen to actually publish our revised implementation to hackage (with consent of and credits to its original author) and maintain this published version.

The reference implementation is a good starting point, it gives a baseline for the core logic, but we'll likely att a more user-friendly API on top, more tests and some extra features as highlighted by @jonathanknowles right above ^^^

[piotr-iohk]

@jonathanknowles, @KtorZ This ticket is still in progress, isn't it? (as there is an open PR that's related https://github.com/input-output-hk/cardano-wallet/pull/277)

[KtorZ]

@piotr-iohk Technically ... no. The PR corresponds to some enhancement that are non-necessary for the ticket itself. But, we might as well wait for them the PR to be merged now...

[jonathanknowles]

@KtorZ wrote:

The PR corresponds to some enhancement that are non-necessary for the ticket itself. But, we might as well wait for them the PR to be merged now...

The error location detection is of course non-essential to this issue.

However, that particular PR (#277) had another component: it added a set of property tests to verify that corrupted Bech32 strings are correctly rejected by the decode function. Corruption is simulated in various ways:

• deleting characters
• inserting characters
• swapping characters
• mutating characters

I think it's fair to say that the above property tests are directly relevant to this issue, and that there's a good case for adding them (whether or not we have the error location detection code).

However, in hindsight, I think it would have been preferable to separate out these two different pieces of work into a pair of PRs.

[KtorZ]

Didn't realize that. Thanks for the heads up @jonathanknowles :pray:

[jonathanknowles]

Didn't realize that. Thanks for the heads up @jonathanknowles

No problem! :)

[piotr-iohk]

@jonathanknowles I have added small pr to #296 to improve coveralls of the bech32 lib. Can you double check if the _invalid checksum_ is expected to produce the corresponding _error_? (https://github.com/input-output-hk/cardano-wallet/pull/296/files#diff-5f9d3bec57a1b2fd69dbc65646199e44R276)

[jonathanknowles]

@jonathanknowles I have added small pr to #296 to improve coveralls of the bech32 lib. Can you double check if the _invalid checksum_ is expected to produce the corresponding _error_? (https://github.com/input-output-hk/cardano-wallet/pull/296/files#diff-5f9d3bec57a1b2fd69dbc65646199e44R276)

Hi @piotr-iohk. I've just checked, and this looks good to me.