Proof-of-concept: mobile border wallet

[robbiehanson]

Border Wallets were recently introduced to "quickly and reliably memorize Bitcoin seed phrases." The goal here was to research how this might be integrated into a mobile bitcoin wallet.

Intro

Phoenix currently offers 2 methods to backup your seed

• Manual (e.g. user writes it down and saves paper)
• iCloud (associated with user's Apple account)

These can be thought of as 2 extremes: on one side is the user taking 100% responsibily, and on the other is near zero responsibility.

Although we would prefer the user to manually backup their seed, we understand this is difficult / intimidating for many casual users. So we are interested in finding alternative options, especially those which provide a solution somewhere in-between the 2 extremes listed above.

Border Wallets 101

The basic idea of a border wallet is:

• There's a randomized 16 * 128 grid of all (2048) BIP-39 compliant seed words (called the entropy grid)
• There's a matching empty grid of the same size (no words). On this empty grid, the user makes a pattern and memorizes it.
• The pattern must consist of either 11 or 23 cells, corresponding with either a 12-word or 24-word seed phrase.
• The final word of your seed phrase is then generated based on the user's pattern. Since the final word in a BIP-39 phrase contains the checksum, there are limited options. (For a 12th word, there are 128 valid options. For a 24th word there are only 8.) The selected word can thus be represented as a number, and this number can be written on the entropy grid since the number doesn't give anything away about the other words in the seed.

Thus the only thing needed to restore your seed in the future is the "entropy grid" and the memorized pattern. This means the entropy grid must be saved, but doesn't pose the same risks as a stored plaintext BIP-39 seed phrase.

What this means for Phoenix

Border wallets are effectively a hybrid between the 2 options we currently offer. The entropy grid is randomly generated, and then stored in the user's iCloud/Google account. But the entropy grid itself doesn't give anything away.

The user then needs to memorize a pattern.

So this is effectively a 2-of-2 backup. To recreate the seed a hacker needs both the (random) entropy grid, plus the correct pattern. Knowing only the pattern, for example, gets you nowhere.

But is a pattern better than a password? That's a valid question, and the Border Wallet docs have several things to say on the matter, including links to studies. I think it's safe to say that it might depend on the person.

But it's also safe to say that it might depend on the implementation. The official Border Wallet workflow involves handling multi-page PDF's ... which is fine if you're doing a manual backup outside of the wallet app. However, to directly integrate this into a mobile app means reducing the frictions of the official flow. So I wanted to know how you could make this idea work on a small mobile phone.

First attempt

I made an app with a 16 * 128 grid on the screen, where the user could tap a cell to enable/disable it. I then showed this prototype to several people, and asked them to make a pattern with either 11 or 23 boxes. The user reception was... not good.

• First, nobody liked making a pattern by tapping on the screen. They wanted to draw with their finger.
• Second, it was hard to make a pattern with exactly 11 or 23 boxes. This was a major turn off for many users, who spent a few minutes thinking really hard about what pattern they would be able to memorize. Only to be told, after all that work, that their pattern was invalid.
• Third, not a single person used anything other than the top portion of the grid. With 128 rows, the grid was quite tall. And needing to remember the location of the pattern (e.g. at the bottom, or a few rows down) was simply too much. It ultimately meant memorizing more than just the pattern itself.

The best advice I received was when one person told me: "I unlock my phone using a pattern. If this was more like my lock screen, I think it would be easier for people to use."

Second attempt

I replaced the grid with a dot-pattern on the screen. Now the user could draw with their finger. When drawing, the lines appear on the grid, and if the lines intersect with the dot then it "activates" and turns a different color. Here's the idea:

https://github.com/ACINQ/phoenix/assets/304604/a0e1ec0c-6997-4e41-bc9f-0acde2abd04c

Testing these changes with users produced a radically different response. They were much more animated, and seemed to actually enjoy the task of drawing a pattern which was memorable for them.

However, 3 problems remained:

• Every single user drew their pattern ONLY in the top portion of the grid.
• Not a single user produced a pattern that was exactly 11 or 23 dots. (This time I didn't mention it to them, and simply asked them to draw a pattern they could memorize.)
• Some patterns were hard to reproduce because of the density of the dots on a small iPhone screen. That is, the user could easily redraw their pattern, but it was too easy to accidentally trigger other dots that weren't activated in the original drawing.

Design challenge

What is the proper size grid for mobile devices? After playing around with several different sizes, I think a size that works really well on all devices is an 8 * 8 grid. It's big enough to allow many different patterns, but doesn't present the density problem seen in larger grids.

Also we allow the user to draw a pattern using any number of dots (except zero/empty), which allows for more creativity by the user.

So the prototype looks like this:

https://github.com/ACINQ/phoenix/assets/304604/b3b55b18-1ba8-40f8-ae2a-f5ae27d7f2e7

Security considerations

From a cryptography perspective, we're allowing the user to draw a pattern of any size (except zero) on an 8 * 8 grid. So that means (2^64) - 1 possible patterns. Also the pattern is just one part of what is essentially a 2-of-2 backup scheme, since the entropy grid is also required.

(That is, if a hacker gets ahold of your pattern, that's not very useful by itself. They will need the entropy grid, which itself is randomly generated.)

Regardless of what the user enters as their pattern, we need to map this to a series of locations on the entropy grid. So we just need a deterministic function that takes the user's pattern as input, and outputs enough bits that can be used for the locations. How many bits of output do we need ?:

• A location on a 16 * 128 grid can be represented in 11 bits (4 bits for x, 7 bits for y)
• 11 bits * 11 locations = 121 bits
• 11 bits * 23 locations = 253 bits

So if the deterministic function outputs 256 bits (or more), then we could generate the locations.

The details of this function should be stored within the entropy grid file, e.g.:

{
  "entropyGrid": [],
  "finalWordNumber": 4,
  "function": {
    "name": "pbkdf2-hmac-sha256",
    "salt": "random_salt_in_hexadecimal",
    "iterations": 2000000
  }              
}

So if a hacker gets ahold of your entropy grid, and they want to brute-force your pattern, then they encounter a situation where there are (2^64) - 1 possible inputs. And to test a single input requires them to perform pbkdf2-hmac-sha256(input, salt, rounds = 2_000_000) (and then check to see if the corresponding wallet has funds).

Decoy wallets

Given an entropy grid, any pattern you draw will generate a valid bitcoin seed. This means a user can backup a single entropy grid in the cloud, and create multiple wallets from that single backup. Meaning they can easily create a decoy wallet with a small amount of funds in it.

Final challenge

The docs on the border wallet website describe a process where the user first draws their pattern, and then receives their bitcoin seed phrase. But that's backwards... at least for Phoenix.

In Phoenix the user gets a wallet right away, and is prompted to backup their wallet later, when they actually start using it. (As discussed in the bitcoin design guide)

Luckily the workaround is pretty simple, since we can generate the entropy grid to match the user's pattern.

Proof-of-concept

This branch has an Xcode project that includes the primary steps:

• allowing the user to draw a pattern
• generating a corresponding entropyGrid.json file, and saving to disk (simulated cloud backup)
• allowing the user to restore their wallet by:
  • selecting their JSON backup from a list
  • redrawing their pattern

The Xcode project can be found in the "MobileBorderWallet" folder. It's pure Swift at this point, so you can just build-and-go in Xcode to try it out.

(Note: The drawing stuff doesn't work very well in the simulator. I get the feeling that Apple's Canvas is heavily hardware-optimized... So it works wonderfully on the device. But not so much on the simulator. Thus you're encouraged to run it on an actual device.)

[microchad]

Hey Robbie, exciting stuff! Thanks for reaching out. I just picked up your message, so let me properly digest it later today and come back to you.

[SuperPhatArrow]

Hi Robbie,

This is quite exciting! It's a great solution to the mobile UI.

I do have some questions that I am still unclear about.

Is the goal here to combine the grid and pattern to get the wallet BIP39 Mnemonic seed phrase or to combine the grid and pattern to create a key to encrypt/decrypt a backup file of the user's settings (eg seed, channel state backup, preferences, etc)?

[robbiehanson]

Is the goal here to combine the grid and pattern to get the wallet BIP39 Mnemonic seed phrase or to [...] create a key to encrypt/decrypt a backup file

To get a BIP39 mnemonic seed phrase, same as the original Border Wallet workflow.

A concrete example is missing from my explanation, which would better explain the technical details. Here's the current plan:

What gets stored in the cloud is an "Index Grid (0-2047)" that looks something like this:

{
  "language": "en",
  "entropyGrid": [2044,1664,1316,1603,447,],
  "finalWordNumber": 4,
  "function": {
    "name": "pbkdf2-hmac-sha256",
    "salt": "a381fd3913c2edcd4fe118c397e35c3a",
    "iterations": 2000000
  }                 
}

(The "entropyGrid" array will have length 2048, but is shortened here for readability)

So this is basically a machine-readable JSON version that matches the human-readable PDF version.

The user will need to memorize their pattern. (No details about this pattern are stored in the cloud. Only the JSON file like the one above.)

So when the user goes to restore their wallet, the wallet downloads the JSON file from the cloud, and prompts the user to enter their pattern. After the user finishes and taps "Next", we generate an input string from their pattern.

The input string is of the form: "(x,y),(x,y),..."

The 8*8 grid is numbered like:

(0,0) (1,0) (2,0) ... (7,0)
(0,1) (1,1) (2,1) ... (7,1)
(0,2) (1,2) (2,2) ... (7,2)
...
(0,7) (1,7) (2,7) ... (7,7)

So the string includes all the activated points, sorted top-to-bottom & left-to-right:

(0,0) < (1,0) < (0,1)

As a concrete example, the house that I drew in the demo video produces this input:

"(3,0),(4,0),(2,1),(5,1),(1,2),(6,2),(0,3),(1,3),(6,3),(7,3),(1,4),(6,4),(1,5),(3,5),(4,5),(6,5),(1,6),(3,6),(4,6),(6,6),(0,7),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7)"

So then we perform:

pbkdf2-hmac-sha256(input, salt iterations)

If you run this with the above input, and the salt/iterations listed in the above JSON, you get the following output (in hex format):

c7be1308cae43f178a0c6e813779cb4bff41beeed5990b171422464c5f31331d

This is 256 bits. And from these bits we're going to extract 11 locations to use for the entropy grid. Each group of 11 bits represents 1 location on the 16*128 entropy grid. (4 bits for x, 7 bits for y)

c7be13.toBinaryString() => "1100 0111 1011 1110 0001 0011"
"1100".toX() => 12
"0111101".toY() => 61
"1111".toX() => 15
"0000100".toY() => 4

So our first 2 points on the entropy grid are (12,61),(15,4). And what we end up with when we're done is:

(12,61),(15,4),(12,17),(9,46),(4,31),(8,94),(2,65),(8,110),(8,9),(11,94),(7,22)

And now we have everything we need to extract our BIP39 mnemonic seed phrase:

• entropy grid
• 11 locations on the entropy grid
• final word number

[SuperPhatArrow]

Ok, thanks for the detailed reply. If I understand you correctly:

1. User makes Pattern which is recorded as a string of x & y coordinates on an 8x8 grid. The length of the pattern is irrelevant since the string gets run through a PDKDF to output a fixed 256 bit number.
2. The software then converts this to a binary string and separates the bits into 11 bit sequences, (4 bits for x, 7 bits for y) so that you have enough for 11/23 words
3. The software then places the indices of the pre-generated random seed phrase at the relevant places on the grid to ensure that the user will land up on the correct seed phrase for their pattern in future.
4. The Software then fills the rest of the grid with random indices as obfuscation since they are irrelevant.

If I am correct in my understanding so far then what you have is a grid and not an entropy grid since there is no entropy in it because you have placed certain indices at certain places in the matrix. We at Border Wallets specifically chose "entropy grid" as terminology to emphasise that the entropy (or randomness) was in the grid, not the pattern. There is never randomness in the pattern or it would be impossible to remember.

If I am incorrect so far then what follows is irrelevant!

This may be fine since what you are essentially trying to do is password encrypt the seed phrase where the "Password" is the pattern and the "grid" is the ciphertext. If you are just using the pattern as a password, why not just use it as such? Take the output of step 1 above and use it as a key to encrypt the seed phrase using a random IV and salt which can be stored in the cloud. This has plenty of benefits for users where the pattern is easier to remember than a password and can be more complex than a password. Also, you can use standard encryption techniques developed by cryptographers rather than rolling your own, which is what this sounds like.

There are some gotchas though:

• While there are "(2^64) - 1 possible patterns", the chance of a particular pattern being correct is not 1 : (2^64) - 1. Patterns are human made and so there will be a ranking of all possible patterns from most likely to be chosen to least likely. Just like passwords, these can be dictionary attacked. The same is true of passwords though.
• It was not clear so far from your UI demos whether a single cell can be selected more than once on the 8 x 8 grid. If not, this significantly reduces your total number of possible patterns. I am not a mathematician but I'm sure it is simple to explain by saying pick an number between 1-100, we think there are 100 options but if you can't count 11, 22, 33 etc, the options are reduced. Only using the digits 0-9 is one thing but imagine saying you cannot use the same character twice in your password. This is closer to your 64 cell grid.
• For the average person, a memorable pattern will still be more complex than a memorable password. However, perhaps take some advice from years of password use by enforcing some minimum complexity? There is some threshold where a user must generate a pattern of at least n dots on the grid because all my dictionary attacks will start with one-dot-patterns! Perhaps at least 8 cells on the grid should be used?

Don't get me wrong, we would love for border wallets to be used in Phoenix but I feel like it is not actually the same and I don't want to discourage you or crap on your idea. The idea of a pattern instead of a password has many benefits to many users and the UX research you have done here is absolutely priceless!

While we would love a Border Wallets on Phoenix story, I think what you have here is something bigger that can be used everywhere passwords are used and I would like to use it in some other projects I'm working on. I guess I'm saying that this might be a "inspired by Border Wallets" rather than "Border Wallets" story.

[robbiehanson]

For a moment, let's forget about this PR, and just focus on the original Border Wallet workflow. One of the problems that wallets have adopting BW is that wallets often generate the recovery phrase first, and ask the user to perform a backup later. And not just Phoenix, a lot of wallets operate like that. Making it impossible to adopt the Border Wallet in its original workflow.

what you have is a grid and not an entropy grid since there is no entropy in it because you have placed certain indices at certain places in the matrix.

Lots to discuss about randomness.

In the border wallet docs you describe how to use the Fisher-Yates Shuffle algorithm to generate a "Maximum Entropy Grid". We both agree that this is an "entropy grid" - that is, that the grid is random.

What if you were to take the output from the Fisher-Yates shuffle algorithm, and put it thru the FY shuffle algorithm again? Would it be more random? No it would not. It would be neither more or less random. It would be equally random.

What if you took the output from FY shuffle, and you choose 2 random indices X & Y, and then swapped those items? Again, it would be equally random, neither more or less.

What if before performing the FY shuffle, you randomly choose 2 words X & Y. Then you perform the FY shuffle. And then you swap X & Y? Again, it would be equally random, neither more or less.

But what if you took a fixed string like "peer-to-peer electronic cash", and then you choose a random salt of 1024 bits, and you put the two thru PBKDF2, and used the output to select X & Y. Then you perform the FY shuffle. And then you swap X & Y? It turns out, the grid is still equally random. Because of the random salt, X & Y are random too. So we're doing the same thing as the paragraph above.

We at Border Wallets specifically chose "entropy grid" as terminology to emphasise that the entropy (or randomness) was in the grid, not the pattern.

We perform the FY shuffle to generate an entropy grid. And afterwards we perform 11 swaps. The indices of which are affected by a randomly generated salt, which is part of the entropy grid. (Remember: the salt is stored in the cloud file, i.e. part of the entropy grid, same as the lastWordNumber)

In other words, if you take the user's pattern, and then generate a random salt, and apply a PBKDF2, the output is random. Same as if you had input a fixed string with salt. The salt provides the randomness, and a different salt would produce a different output.

I understand where you're coming from. But I also understand that, unless we find a workaround for the shortcoming of the original workflow, it will continue to be impossible for many wallets to adopt Border Wallets. And what I'm proposing is, perhaps, a decent workaround:

• extra entropy is added to the entropy grid file in the form of a salt
• Pbkdf2(pattern, salt) = 11 (or 23) random indices
• perform FY shuffle to create entropy grid
• perform 11 (or 23) swaps based on the generated random indices

This proposed workaround has little to do with the rest of the PR. It could work for a standard 16*128 grid. And remember, this workaround is specifically targeted at apps which are attempting to integrate Border Wallets. The original workflow remains unchanged.

I'd really like to know what you think about this. You make a lot of other good points in your response, and perhaps we could discuss those later. But this is the very first hurdle we encountered when attempting to adopt Border Wallets. And this is the first crossroads we've come to with you when discussing our research. So if you feel like this workaround is inadequate, and that our grid is still just a grid, and not a real entropy grid, then please let us know.