Difference between revisions of "Mini private key format"

From Bitcoin Wiki
Jump to: navigation, search
m
 
(46 intermediate revisions by 11 users not shown)
Line 1: Line 1:
[[Image:QR-privkeys-sidebyside.png|thumb|right|QR codes of the same private key, in mini versus regular private key format. Both codes have the same dot density and error correction level, but the mini key is 57% of the full code's size.]]
+
[[Image:QR-privkeys-sidebyside.png|thumb|right|Comparison of QR codes of the same private key, encoded in mini private key format (left) and [[wallet import format]] (right). Both codes have the same dot density and error correction level, but the mini key is 57% of the full code's size.]]
The '''mini private key format''' is a method of encoding a Bitcoin private key in 22 characters so that it can be embedded in a small space. This private key format was first used in Casascius physical bitcoins, and is also favorable for use in QR codes.  The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.
+
[[Image:Redeemed Denarium physical bitcoin.jpg|thumb|right|A minikey in a small space on a physical bitcoin]]
 +
{{sample}}
 +
The '''mini private key format''' is a method of encoding a Bitcoin private key in as few as 30 characters for the purpose of being embedded in a small space. A private key encoded in this format is called a '''minikey'''. This private key format was designed for and first used in [[Casascius physical bitcoins]], and is also favorable for use in QR codes.  The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.
  
An example key using this encoding is '''S4b3N3oGqDqR5jNuxEvDwf'''.
+
Casascius Series 1 holograms use a 22-character variant of the minikey format, instead of 30 characters. Everything is the same other than the length. To properly implement minikey redemption, services and clients must support the 30-character format, but may optionally support the 22-character format as well to allow redemption of old Casascius coins. Use of the 22-character format for future applications is discouraged due to security considerations; the standard 30-character format should be used instead.
  
==Usage on a physical bitcoin==
+
An example key using this encoding is '''S6c56bnXQiBjk9m{{taggant private key}}qSYE7ykVQ7NzrRy'''.
The way it might appear within a physical bitcoin is on a round card printed as follows:
 
  
<center>S4b3N<br/>3oGqDq<br/>R5jNux<br/>EvDwf</center>
+
==Usage==
 +
===Physical bitcoins===
 +
{{multiple image|align=vertical|width=300
 +
|image1=Miniprivkeys.jpg
 +
|image2=Minipubkeys.jpg
 +
|footer=Paper disc inserts for [[Casascius physical bitcoins|Casascius coins]] with minikeys on the obverse (top) and corresponding address prefixes on the reverse (bottom)
 +
}}
 +
Minikeys are used extensively on physical bitcoins, because their small size allows them to be printed and read easily even on tiny surfaces inside the coins. Typically, a small paper or plastic disc is placed behind a tamper-evident security hologram on the back of a metal coin or bar, with the minikey printed on the inside such that it can only be read if the security hologram is removed.
 +
 
 +
Some physical bitcoins include a window in the security hologram to view the back of this disc, which includes the prefix of the address corresponding to the hidden minikey.
 +
 
 +
===1D barcodes===
 +
The mini private key is small enough to fit in a one-dimensional barcode while still remaining practical.  Among the most popular one-dimensional barcode symbologies, the one known as "Code 128" is best suited for encoding a minikey due to its favorable data density and support for mixed case strings.  The variant known as "Code 128-B" produces the shortest code for strings containing lowercase characters.
 +
 
 +
The sample private minikey encoded with Code 128-B looks like this:
 +
 
 +
[[Image:Private_minikey_in_1D_barcode.gif]]
 +
 
 +
===2D barcodes===
 +
The mini private key is suitable for use in QR codes.  The recommended settings for maximizing readability are: QR version 3, error correction level Q (near highest, 25% possible lost codeword recovery).  This results in a 29x29 grid.  A minikey QR code can also fit in a 25x25 grid with QR version 2, error correction level L (lowest, 7% possible lost codeword recovery).
 +
 
 +
The sample private minikey encoded as a QR code on a 29x29 grid looks like this:
 +
 
 +
[[Image:Private_minikey_in_2D_barcode.gif]]
 +
 
 +
==Import==
 +
Mini private keys can be imported through the following clients/services:
 +
 
 +
===Applications===
 +
* [[Armory]]
 +
 
 +
The current mainline ("Satoshi") client cannot currently be used to import minikeys.
 +
 
 +
===Web===
 +
 
 +
* [[BlockChain.info]]
 +
** Private keys can be imported into a Blockchain.info wallet and bitcoins can be sent to another address immediately upon import without needing to wait for any confirmations.  Even after import, funds remain associated with the private key until they are actually spent to a different address.
 +
* [[StrongCoin]]
  
 
==Decoding==
 
==Decoding==
The private key encoding consists of 22 alphanumeric characters from the [[base58]] alphabet used in Bitcoin.  The first of the 22 characters is always the uppercase letter S.
+
The private key encoding consists of 30 alphanumeric characters from the [[base58]] alphabet used in Bitcoin.  The first of the characters is always the uppercase letter S.
 +
 
 +
To determine whether the minikey is valid:
 +
 
 +
# Add a question mark to the end of the mini private key string.
 +
# Take the SHA256 hash of the entire string.  However, we will only look at the first byte of the result.
 +
# If the first byte is 00, the string is a well-formed minikey.  If the first byte is not 00, the string should be rejected as a minikey.
 +
 
 +
===Example with SHA256===
 +
Here is an example with the sample private key <tt>S6c56bnXQiBjk9mq{{taggant private key}}SYE7ykVQ7NzrRy</tt>.
  
To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string.  There is no encoding for breaks in the string even if printed that way - the SHA256 should be taken of exactly twenty-two bytes.
+
The string "<tt>S6c56bnXQiBjk9{{taggant private key}}mqSYE7ykVQ7NzrRy?</tt>" has a SHA256 value that begins with 00, so it is well-formed.
  
  SHA256("S4b3N3oGqDqR5jNuxEvDwf") = 0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D
+
To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string.  There is no encoding for line breaks in the string, even if the key is broken into multiple lines for printing.  The SHA256 should be taken of exactly thirty bytes.
 +
 
 +
  SHA256("S6c56bnXQiBjk9{{taggant private key}}mqSYE7ykVQ7NzrRy") = 4C7A9640C72DC2099F23715D0C8A0D8A35F8906E3CAB61DD3F78B67BF887C9AB 
 +
 
 +
This sample key in [[wallet import format]] is <tt>5JPy8Zg7z4P7RSLsiqcqyeAF1{{taggant private key}}935zjNUdMxcDeVrtU1oarrgnB7</tt>, and the corresponding [[Bitcoin address]] is <tt>1CciesT23BNionJe{{taggant address}}Xrbxmjc7ywfiyM4oLW</tt>.
 +
 
 +
==== Command line verification ====
 +
To calculate SHA256 from the command line on OSX or Linux devices:
 +
 
 +
echo -n "S6c56bnXQiBjk9{{taggant private key}}mqSYE7ykVQ7NzrRy?" | shasum -a 256
 +
 
 +
That should output a line of text like "<tt>000f2453798ad4f951eecced2242eaef3e1cbc8a7c813c203ac7ffe57060355d  -</tt>". Since the first two characters are <tt>00</tt> the verification passes for the mini key <tt>S6c56bnXQiBjk9{{taggant private key}}mqSYE7ykVQ7NzrRy</tt>
  
 
==Check code==
 
==Check code==
The check code is designed to be simple, but relatively computationally expensive so that it cannot be used to quickly reduce the key space in a brute force attackIt offers seven bits worth of error protection (or, in other words, in the event of a typo, the typo will be caught about 127 out of 128 times, or over 99%).
+
The mini private key format offers a simple typo check code.  Mini private keys must be generated in a "brute force" fashion, keeping only keys that conform to the format's rulesIf a key is well-formed (30 Base58 characters starting with S), but fails the hash check, then it probably contains a typo.
  
To determine whether a string passes the check code, follow these steps:
+
If the SHA256 hash of the string followed by '?' doesn't result in something that begins with 0x00, the string is not a valid mini private key.
# Ensure it is well-formed (22 characters, base58 alphabet, starts with S).
 
# Add a question mark to the end of the string, and take the SHA256 of that.  If the SHA256 starts with eight zero bits (hex 00), then the string passes the check code.
 
# If it does not, then with the same string (ending in a question mark), do 717 (seven hundred seventeen) rounds of SHA256 on the string.  If the result after the 717th round starts with eight zero bits (hex 00), then the string passes the check code.
 
# If the results of SHA256 after both tests don't start with eight zero bits, then the check fails.
 
  
 
==Creating mini private keys==
 
==Creating mini private keys==
Line 30: Line 84:
 
Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way.  In other words, there is no way to convert an existing full-size private key into a mini private key.
 
Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way.  In other words, there is no way to convert an existing full-size private key into a mini private key.
  
To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check.  (This means eliminating more than 99% of the candidates.)  Then use SHA256 to compute the corresponding private key, and in turn, the matching Bitcoin address.  The Bitcoin address can always be computed from just the private key.
+
To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check.  (This means eliminating more than 99% of the candidates.)  Then use the appropriate algorithm to compute the corresponding private key, and in turn, the matching Bitcoin address.  The Bitcoin address can always be computed from just the private key.
  
In all cases, you should use a secure cryptographic random number generator to eliminate risks of predictability of the random strings.  Also, for stronger security, accept only the strings that pass the typo check on the 717th round rather than the first.
+
It is strongly advisable to avoid using the digit "1" in minikeys unless it is being printed in such a way where a user is unlikely to mistake it for the lowercase letter "l".  Few clients and redemption tools are prepared to tell the user that their entry containing the letter "l" should actually be the number "1" - rather, they will simply reject the code and may leave the user confused.
 +
 
 +
In all cases, you '''must''' use a secure cryptographic random number generator to eliminate risks of predictability of the random strings.
  
 
==Python Code==
 
==Python Code==
The following code produces sample mini private keys in Python.  For real-world use, ''random'' must be replaced with a better source of entropy, as the Python documentation for ''random'' states the function ''"is completely unsuitable for cryptographic purposes"''.
+
The following code produces sample 30-character SHA256-based mini private keys in Python.  For real-world use, ''random'' must be replaced with a better source of entropy, as the Python documentation for ''random'' states the function ''"is completely unsuitable for cryptographic purposes"''.
  
 
<source lang="python">
 
<source lang="python">
Line 41: Line 97:
 
import hashlib
 
import hashlib
  
BASE58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
+
BASE58 = '23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
  
 
def Candidate():
 
def Candidate():
Line 48: Line 104:
 
     """
 
     """
 
     return('%s%s' % ('S', ''.join(
 
     return('%s%s' % ('S', ''.join(
         [BASE58[ random.randrange(0,len(BASE58)) ] for i in range(21)])))
+
         [BASE58[ random.randrange(0,len(BASE58)) ] for i in range(29)])))
  
def GenerateKeys(numKeys = 10, additionalSecurity = False):
+
def GenerateKeys(numKeys = 10):
 
     """
 
     """
 
     Generate mini private keys and output the mini key as well as the full
 
     Generate mini private keys and output the mini key as well as the full
 
     private key. numKeys is The number of keys to generate, and  
 
     private key. numKeys is The number of keys to generate, and  
    additionalSecurity controls whether to do 717 rounds of SHA256
 
 
     """
 
     """
 
     keysGenerated = 0
 
     keysGenerated = 0
Line 65: Line 120:
 
             # Take one round of SHA256
 
             # Take one round of SHA256
 
             candHash = hashlib.sha256(t).digest()
 
             candHash = hashlib.sha256(t).digest()
            if additionalSecurity:
 
                # Do the other 716 rounds for additional security
 
                for i in range(716):
 
                    candHash = hashlib.sha256(candHash).digest()
 
 
             # Check if the first eight bits of the hash are 0
 
             # Check if the first eight bits of the hash are 0
 
             if candHash[0] == '\x00':
 
             if candHash[0] == '\x00':
Line 82: Line 133:
 
         except KeyboardInterrupt:
 
         except KeyboardInterrupt:
 
             break
 
             break
     print('\n%s: %i\n%s: %i\n%s: %r\n%s: %.1f' %
+
     print('\n%s: %i\n%s: %i\n%s: %.1f' %
 
           ('Keys Generated', keysGenerated,
 
           ('Keys Generated', keysGenerated,
 
           'Total Candidates', totalCandidates,
 
           'Total Candidates', totalCandidates,
          'Additional Security', additionalSecurity,
 
 
           'Reject Percentage',
 
           'Reject Percentage',
 
           100*(1.0-keysGenerated/float(totalCandidates))))
 
           100*(1.0-keysGenerated/float(totalCandidates))))
Line 104: Line 154:
 
     Checks for typos in the short key.
 
     Checks for typos in the short key.
 
     """
 
     """
     if len(shortKey) != 22:
+
     if len(shortKey) != 30:
 
         return False
 
         return False
 
     t = '%s?' % shortKey
 
     t = '%s?' % shortKey
Line 111: Line 161:
 
     if tHash[0] == '\x00':
 
     if tHash[0] == '\x00':
 
         return True
 
         return True
    else:
 
        # Do an additional 716 rounds
 
        for i in range(716):
 
            tHash = hashlib.sha256(tHash).digest()
 
        # Check again for \x00
 
        if tHash[0] == '\x00':
 
            return True
 
 
     return False
 
     return False
 
</source>
 
</source>

Latest revision as of 03:03, 10 August 2017

Comparison of QR codes of the same private key, encoded in mini private key format (left) and wallet import format (right). Both codes have the same dot density and error correction level, but the mini key is 57% of the full code's size.
A minikey in a small space on a physical bitcoin

This page contains sample addresses and/or private keys. Do not send bitcoins to or import any sample keys; you will lose your money.

The mini private key format is a method of encoding a Bitcoin private key in as few as 30 characters for the purpose of being embedded in a small space. A private key encoded in this format is called a minikey. This private key format was designed for and first used in Casascius physical bitcoins, and is also favorable for use in QR codes. The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.

Casascius Series 1 holograms use a 22-character variant of the minikey format, instead of 30 characters. Everything is the same other than the length. To properly implement minikey redemption, services and clients must support the 30-character format, but may optionally support the 22-character format as well to allow redemption of old Casascius coins. Use of the 22-character format for future applications is discouraged due to security considerations; the standard 30-character format should be used instead.

An example key using this encoding is S6c56bnXQiBjk9m_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_qSYE7ykVQ7NzrRy.

Usage

Physical bitcoins

Paper disc inserts for Casascius coins with minikeys on the obverse (top) and corresponding address prefixes on the reverse (bottom)

Minikeys are used extensively on physical bitcoins, because their small size allows them to be printed and read easily even on tiny surfaces inside the coins. Typically, a small paper or plastic disc is placed behind a tamper-evident security hologram on the back of a metal coin or bar, with the minikey printed on the inside such that it can only be read if the security hologram is removed.

Some physical bitcoins include a window in the security hologram to view the back of this disc, which includes the prefix of the address corresponding to the hidden minikey.

1D barcodes

The mini private key is small enough to fit in a one-dimensional barcode while still remaining practical. Among the most popular one-dimensional barcode symbologies, the one known as "Code 128" is best suited for encoding a minikey due to its favorable data density and support for mixed case strings. The variant known as "Code 128-B" produces the shortest code for strings containing lowercase characters.

The sample private minikey encoded with Code 128-B looks like this:

Private minikey in 1D barcode.gif

2D barcodes

The mini private key is suitable for use in QR codes. The recommended settings for maximizing readability are: QR version 3, error correction level Q (near highest, 25% possible lost codeword recovery). This results in a 29x29 grid. A minikey QR code can also fit in a 25x25 grid with QR version 2, error correction level L (lowest, 7% possible lost codeword recovery).

The sample private minikey encoded as a QR code on a 29x29 grid looks like this:

Private minikey in 2D barcode.gif

Import

Mini private keys can be imported through the following clients/services:

Applications

The current mainline ("Satoshi") client cannot currently be used to import minikeys.

Web

  • BlockChain.info
    • Private keys can be imported into a Blockchain.info wallet and bitcoins can be sent to another address immediately upon import without needing to wait for any confirmations. Even after import, funds remain associated with the private key until they are actually spent to a different address.
  • StrongCoin

Decoding

The private key encoding consists of 30 alphanumeric characters from the base58 alphabet used in Bitcoin. The first of the characters is always the uppercase letter S.

To determine whether the minikey is valid:

  1. Add a question mark to the end of the mini private key string.
  2. Take the SHA256 hash of the entire string. However, we will only look at the first byte of the result.
  3. If the first byte is 00, the string is a well-formed minikey. If the first byte is not 00, the string should be rejected as a minikey.

Example with SHA256

Here is an example with the sample private key S6c56bnXQiBjk9mq_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_SYE7ykVQ7NzrRy.

The string "S6c56bnXQiBjk9_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_mqSYE7ykVQ7NzrRy?" has a SHA256 value that begins with 00, so it is well-formed.

To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string. There is no encoding for line breaks in the string, even if the key is broken into multiple lines for printing. The SHA256 should be taken of exactly thirty bytes.

SHA256("S6c56bnXQiBjk9_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_mqSYE7ykVQ7NzrRy") = 4C7A9640C72DC2099F23715D0C8A0D8A35F8906E3CAB61DD3F78B67BF887C9AB  

This sample key in wallet import format is 5JPy8Zg7z4P7RSLsiqcqyeAF1_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_935zjNUdMxcDeVrtU1oarrgnB7, and the corresponding Bitcoin address is 1CciesT23BNionJe_SAMPLE_ADDRESS_DO_NOT_SEND_Xrbxmjc7ywfiyM4oLW.

Command line verification

To calculate SHA256 from the command line on OSX or Linux devices:

echo -n "S6c56bnXQiBjk9_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_mqSYE7ykVQ7NzrRy?" | shasum -a 256

That should output a line of text like "000f2453798ad4f951eecced2242eaef3e1cbc8a7c813c203ac7ffe57060355d -". Since the first two characters are 00 the verification passes for the mini key S6c56bnXQiBjk9_SAMPLE_PRIVATE_KEY_DO_NOT_IMPORT_mqSYE7ykVQ7NzrRy

Check code

The mini private key format offers a simple typo check code. Mini private keys must be generated in a "brute force" fashion, keeping only keys that conform to the format's rules. If a key is well-formed (30 Base58 characters starting with S), but fails the hash check, then it probably contains a typo.

If the SHA256 hash of the string followed by '?' doesn't result in something that begins with 0x00, the string is not a valid mini private key.

Creating mini private keys

Creating mini private keys is relatively simple. One program which can create such keys is Casascius Bitcoin Utility.

Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way. In other words, there is no way to convert an existing full-size private key into a mini private key.

To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check. (This means eliminating more than 99% of the candidates.) Then use the appropriate algorithm to compute the corresponding private key, and in turn, the matching Bitcoin address. The Bitcoin address can always be computed from just the private key.

It is strongly advisable to avoid using the digit "1" in minikeys unless it is being printed in such a way where a user is unlikely to mistake it for the lowercase letter "l". Few clients and redemption tools are prepared to tell the user that their entry containing the letter "l" should actually be the number "1" - rather, they will simply reject the code and may leave the user confused.

In all cases, you must use a secure cryptographic random number generator to eliminate risks of predictability of the random strings.

Python Code

The following code produces sample 30-character SHA256-based mini private keys in Python. For real-world use, random must be replaced with a better source of entropy, as the Python documentation for random states the function "is completely unsuitable for cryptographic purposes".

import random
import hashlib

BASE58 = '23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def Candidate():
    """
    Generate a random, well-formed mini private key.
    """
    return('%s%s' % ('S', ''.join(
        [BASE58[ random.randrange(0,len(BASE58)) ] for i in range(29)])))

def GenerateKeys(numKeys = 10):
    """
    Generate mini private keys and output the mini key as well as the full
    private key. numKeys is The number of keys to generate, and 
    """
    keysGenerated = 0
    totalCandidates = 0
    while keysGenerated < numKeys:
        try:
            cand = Candidate()
            # Do typo check
            t = '%s?' % cand
            # Take one round of SHA256
            candHash = hashlib.sha256(t).digest()
            # Check if the first eight bits of the hash are 0
            if candHash[0] == '\x00':
                privateKey = GetPrivateKey(cand)
                print('\n%s\nSHA256( ): %s\nsha256(?): %s' %
                      (cand, privateKey, candHash.encode('hex_codec')))
                if CheckShortKey(cand):
                    print('Validated.')
                else:
                    print('Invalid!')
                keysGenerated += 1
            totalCandidates += 1
        except KeyboardInterrupt:
            break
    print('\n%s: %i\n%s: %i\n%s: %.1f' %
          ('Keys Generated', keysGenerated,
           'Total Candidates', totalCandidates,
           'Reject Percentage',
           100*(1.0-keysGenerated/float(totalCandidates))))

def GetPrivateKey(shortKey):
    """
    Returns the hexadecimal representation of the private key corresponding
    to the given short key.
    """
    if CheckShortKey(shortKey):
        return hashlib.sha256(shortKey).hexdigest()
    else:
        print('Typo detected in private key!')
        return None

def CheckShortKey(shortKey):
    """
    Checks for typos in the short key.
    """
    if len(shortKey) != 30:
        return False
    t = '%s?' % shortKey
    tHash = hashlib.sha256(t).digest()
    # Check to see that first byte is \x00
    if tHash[0] == '\x00':
        return True
    return False