jdlcdl/mnemonic_to_bytes_speedup.md

Last active August 17, 2024 13:24

Star () You must be signed in to star a gist
Fork () You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/jdlcdl/4f9f9cc8d24f5fc6d39e833520d2f199.js"></script>
Save jdlcdl/4f9f9cc8d24f5fc6d39e833520d2f199 to your computer and use it in GitHub Desktop.

Download ZIP

diybitcoinhardware/embit.bip39.mnemonic_to_bytes() speedup

Raw

mnemonic_to_bytes_speedup.md

diybitcoinhardware/embit.bip39.mnemonic_to_bytes() speedup

Back Story (a branch I do not intend to PR)

In the spring of 2024, while brute-forcing mnemonics, I took a look at improving the performance of embit.bip39.mnemonic_to_bytes(), which is:

well peer-reviewed
tested... arguably enough
stable and in-use by a number of projects

I ended up re-implementing this function using a big-integer accumulator. I call the branch "bip39_via_accumulator".

But this function was originally copied from Jimmy Song, a well respected developer with a real name (NOT anon like me).

My implementation had 3 primary changes for performance (I'll argue that it's also easier to read and understand):

negligeable improvement (2%-8%) with fewer branches and bytes conversions,
noticeable improvement (~2x-3x) using try/except instead of if word not in wordlist:,
noticeable (and memory expensive) improvement (2x-25x) using a word-->index dictionary.

Because embit is geared towards resource-limited micro-controllers, I have since removed the last enhancement, which accounted for the greatest performance boost on a few of the devices I tested.

This leaves the above branch as a 2x-3x performance improvement and a SCANDALOUS/HERETICAL total-rewrite of a perfectly functioning and highly sensitive library used by a few projects to protect only-God-knows how much family treasure.

New Plan (a branch I intend to PR)

With due respect for this existing stable library function (for my peers, and for fellow bitcoiners), I have re-imagined what I believe is a less-controversial branch that I'm calling "mnemonic_to_bytes_speedup". I plan to submit a pull-request for this, and that's why I've invited you here.

It has a single code commit aimed at the ~2x-3x speedup via a try/except block, with no functional changes.

It also has added tests to illustrate how a 3rd party app might choose to implement the word-->index dictionary speedup via the wordlist parameters of mnemonic_is_valid() and mnemonic_to_bytes(). This may very well better-belong in embit's "examples", since it is NOT truly implemented within embit, as well as the test-suites of 3rd party apps that use this memory-hungry trick.

I've chosen to add it to embit's tests because:

it works really well for speeding up mnemonic_to_bytes() when memory is available and when speed is wanted,
I'd want future developers to be aware of how wordlist is being used in the event they re-implement and break it,
I'm a believer that unit-tests are a great place to "document" intention (but embit devs might argue strongly that THIS WAS NEVER INTENDED.)

Past News (I've already issued this PR)

Along the way, I bumped into 2 edge cases that seemed "incorrect" to me, related to input-validation of mnemonic length as well as the same for entropy, and I've submitted embit pull-request #63 for that on August 15th 2024.

Author

jdlcdl commented Aug 17, 2024

I'm using the following to test different devices:

# micropython compatible single file for testing embit.bip39.mnemonic_to_bytes() speedup

"""
Performance Notes per device: 
Timing 5000 iterations of 24 choices of WORDLIST as mnemonic,
calling mnemonic_to_bytes() in 4 different ways:
1) un-altered mnemonic_to_bytes() as it exists currently, with default WORDLIST
3) `try/except` speedup from "mnemonic_to_bytes_speedup" branch, with default WORDLIST
2) un-altered function called with wordlist=wordindex
4) `try/except` speedup called with wordlist=wordindex

Xeon amd64 ubuntu: Python 3.10.12
mnemonic_to_bytes w/ list                 19/5000 valid, elapsed:    2489735us    497us/call
mnemonic_to_bytes_speedup w/ list         19/5000 valid, elapsed:    1367567us    273us/call
mnemonic_to_bytes w/ WordIndex            19/5000 valid, elapsed:     180188us     36us/call
mnemonic_to_bytes_speedup w/ WordIndex    19/5000 valid, elapsed:     173211us     34us/call

RPi4 raspiOS: Python 3.7.3
mnemonic_to_bytes w/ list                 19/5000 valid, elapsed:   10413014us   2082us/call
mnemonic_to_bytes_speedup w/ list         19/5000 valid, elapsed:    6145349us   1229us/call
mnemonic_to_bytes w/ WordIndex            19/5000 valid, elapsed:    1031786us    206us/call
mnemonic_to_bytes_speedup w/ WordIndex    19/5000 valid, elapsed:     985007us    197us/call

RPi0 raspiOS: Python 3.10.10
mnemonic_to_bytes w/ list                 19/5000 valid, elapsed:  251468489us  50293us/call
mnemonic_to_bytes_speedup w/ list         19/5000 valid, elapsed:  133671855us  26734us/call
mnemonic_to_bytes w/ WordIndex            19/5000 valid, elapsed:   15740069us   3148us/call
mnemonic_to_bytes_speedup w/ WordIndex    19/5000 valid, elapsed:   15349985us   3069us/call

RP2040 pico upython: MicroPython v1.22.2
mnemonic_to_bytes w/ list                 18/5000 valid, elapsed:  469956768us  93991us/call
mnemonic_to_bytes_speedup w/ list         18/5000 valid, elapsed:  170790464us  34158us/call
mnemonic_to_bytes w/ WordIndex            18/5000 valid, elapsed:  136229040us  27245us/call
mnemonic_to_bytes_speedup w/ WordIndex    18/5000 valid, elapsed:   86800328us  17360us/call

esp32s3 upython: MicroPython v1.23.0
mnemonic_to_bytes w/ list                 18/5000 valid, elapsed:  354344448us  70868us/call
mnemonic_to_bytes_speedup w/ list         18/5000 valid, elapsed:   80359880us  16071us/call
mnemonic_to_bytes w/ WordIndex            18/5000 valid, elapsed:   24143610us   4828us/call
mnemonic_to_bytes_speedup w/ WordIndex    18/5000 valid, elapsed:   23376606us   4675us/call

kendryte-k210 Amigo: MaixPy MicroPython v1.11
mnemonic_to_bytes w/ list                 18/5000 valid, elapsed:  109451680us  21890us/call
mnemonic_to_bytes_speedup w/ list         18/5000 valid, elapsed:   36680112us   7336us/call
mnemonic_to_bytes w/ WordIndex            18/5000 valid, elapsed:   30961598us   6192us/call
mnemonic_to_bytes_speedup w/ WordIndex    18/5000 valid, elapsed:   24456360us   4891us/call
"""


import random
import hashlib
try: 
     from time import time_ns as my_time
     us_divisor = 1000
except: 
     from time import ticks_us as my_time
     us_divisor = 1


WORDLIST = [
    'abandon', 'ability', 'able', 'about', 'above', 'absent', 'absorb', 'abstract', 'absurd', 'abuse', 'access', 'accident', 'account', 'accuse', 'achieve', 'acid',
    'acoustic', 'acquire', 'across', 'act', 'action', 'actor', 'actress', 'actual', 'adapt', 'add', 'addict', 'address', 'adjust', 'admit', 'adult', 'advance',
    'advice', 'aerobic', 'affair', 'afford', 'afraid', 'again', 'age', 'agent', 'agree', 'ahead', 'aim', 'air', 'airport', 'aisle', 'alarm', 'album',
    'alcohol', 'alert', 'alien', 'all', 'alley', 'allow', 'almost', 'alone', 'alpha', 'already', 'also', 'alter', 'always', 'amateur', 'amazing', 'among',
    'amount', 'amused', 'analyst', 'anchor', 'ancient', 'anger', 'angle', 'angry', 'animal', 'ankle', 'announce', 'annual', 'another', 'answer', 'antenna', 'antique',
    'anxiety', 'any', 'apart', 'apology', 'appear', 'apple', 'approve', 'april', 'arch', 'arctic', 'area', 'arena', 'argue', 'arm', 'armed', 'armor',
    'army', 'around', 'arrange', 'arrest', 'arrive', 'arrow', 'art', 'artefact', 'artist', 'artwork', 'ask', 'aspect', 'assault', 'asset', 'assist', 'assume',
    'asthma', 'athlete', 'atom', 'attack', 'attend', 'attitude', 'attract', 'auction', 'audit', 'august', 'aunt', 'author', 'auto', 'autumn', 'average', 'avocado',
    'avoid', 'awake', 'aware', 'away', 'awesome', 'awful', 'awkward', 'axis', 'baby', 'bachelor', 'bacon', 'badge', 'bag', 'balance', 'balcony', 'ball',
    'bamboo', 'banana', 'banner', 'bar', 'barely', 'bargain', 'barrel', 'base', 'basic', 'basket', 'battle', 'beach', 'bean', 'beauty', 'because', 'become',
    'beef', 'before', 'begin', 'behave', 'behind', 'believe', 'below', 'belt', 'bench', 'benefit', 'best', 'betray', 'better', 'between', 'beyond', 'bicycle',
    'bid', 'bike', 'bind', 'biology', 'bird', 'birth', 'bitter', 'black', 'blade', 'blame', 'blanket', 'blast', 'bleak', 'bless', 'blind', 'blood',
    'blossom', 'blouse', 'blue', 'blur', 'blush', 'board', 'boat', 'body', 'boil', 'bomb', 'bone', 'bonus', 'book', 'boost', 'border', 'boring',
    'borrow', 'boss', 'bottom', 'bounce', 'box', 'boy', 'bracket', 'brain', 'brand', 'brass', 'brave', 'bread', 'breeze', 'brick', 'bridge', 'brief',
    'bright', 'bring', 'brisk', 'broccoli', 'broken', 'bronze', 'broom', 'brother', 'brown', 'brush', 'bubble', 'buddy', 'budget', 'buffalo', 'build', 'bulb',
    'bulk', 'bullet', 'bundle', 'bunker', 'burden', 'burger', 'burst', 'bus', 'business', 'busy', 'butter', 'buyer', 'buzz', 'cabbage', 'cabin', 'cable',
    'cactus', 'cage', 'cake', 'call', 'calm', 'camera', 'camp', 'can', 'canal', 'cancel', 'candy', 'cannon', 'canoe', 'canvas', 'canyon', 'capable',
    'capital', 'captain', 'car', 'carbon', 'card', 'cargo', 'carpet', 'carry', 'cart', 'case', 'cash', 'casino', 'castle', 'casual', 'cat', 'catalog',
    'catch', 'category', 'cattle', 'caught', 'cause', 'caution', 'cave', 'ceiling', 'celery', 'cement', 'census', 'century', 'cereal', 'certain', 'chair', 'chalk',
    'champion', 'change', 'chaos', 'chapter', 'charge', 'chase', 'chat', 'cheap', 'check', 'cheese', 'chef', 'cherry', 'chest', 'chicken', 'chief', 'child',
    'chimney', 'choice', 'choose', 'chronic', 'chuckle', 'chunk', 'churn', 'cigar', 'cinnamon', 'circle', 'citizen', 'city', 'civil', 'claim', 'clap', 'clarify',
    'claw', 'clay', 'clean', 'clerk', 'clever', 'click', 'client', 'cliff', 'climb', 'clinic', 'clip', 'clock', 'clog', 'close', 'cloth', 'cloud',
    'clown', 'club', 'clump', 'cluster', 'clutch', 'coach', 'coast', 'coconut', 'code', 'coffee', 'coil', 'coin', 'collect', 'color', 'column', 'combine',
    'come', 'comfort', 'comic', 'common', 'company', 'concert', 'conduct', 'confirm', 'congress', 'connect', 'consider', 'control', 'convince', 'cook', 'cool', 'copper',
    'copy', 'coral', 'core', 'corn', 'correct', 'cost', 'cotton', 'couch', 'country', 'couple', 'course', 'cousin', 'cover', 'coyote', 'crack', 'cradle',
    'craft', 'cram', 'crane', 'crash', 'crater', 'crawl', 'crazy', 'cream', 'credit', 'creek', 'crew', 'cricket', 'crime', 'crisp', 'critic', 'crop',
    'cross', 'crouch', 'crowd', 'crucial', 'cruel', 'cruise', 'crumble', 'crunch', 'crush', 'cry', 'crystal', 'cube', 'culture', 'cup', 'cupboard', 'curious',
    'current', 'curtain', 'curve', 'cushion', 'custom', 'cute', 'cycle', 'dad', 'damage', 'damp', 'dance', 'danger', 'daring', 'dash', 'daughter', 'dawn',
    'day', 'deal', 'debate', 'debris', 'decade', 'december', 'decide', 'decline', 'decorate', 'decrease', 'deer', 'defense', 'define', 'defy', 'degree', 'delay',
    'deliver', 'demand', 'demise', 'denial', 'dentist', 'deny', 'depart', 'depend', 'deposit', 'depth', 'deputy', 'derive', 'describe', 'desert', 'design', 'desk',
    'despair', 'destroy', 'detail', 'detect', 'develop', 'device', 'devote', 'diagram', 'dial', 'diamond', 'diary', 'dice', 'diesel', 'diet', 'differ', 'digital',
    'dignity', 'dilemma', 'dinner', 'dinosaur', 'direct', 'dirt', 'disagree', 'discover', 'disease', 'dish', 'dismiss', 'disorder', 'display', 'distance', 'divert', 'divide',
    'divorce', 'dizzy', 'doctor', 'document', 'dog', 'doll', 'dolphin', 'domain', 'donate', 'donkey', 'donor', 'door', 'dose', 'double', 'dove', 'draft',
    'dragon', 'drama', 'drastic', 'draw', 'dream', 'dress', 'drift', 'drill', 'drink', 'drip', 'drive', 'drop', 'drum', 'dry', 'duck', 'dumb',
    'dune', 'during', 'dust', 'dutch', 'duty', 'dwarf', 'dynamic', 'eager', 'eagle', 'early', 'earn', 'earth', 'easily', 'east', 'easy', 'echo',
    'ecology', 'economy', 'edge', 'edit', 'educate', 'effort', 'egg', 'eight', 'either', 'elbow', 'elder', 'electric', 'elegant', 'element', 'elephant', 'elevator',
    'elite', 'else', 'embark', 'embody', 'embrace', 'emerge', 'emotion', 'employ', 'empower', 'empty', 'enable', 'enact', 'end', 'endless', 'endorse', 'enemy',
    'energy', 'enforce', 'engage', 'engine', 'enhance', 'enjoy', 'enlist', 'enough', 'enrich', 'enroll', 'ensure', 'enter', 'entire', 'entry', 'envelope', 'episode',
    'equal', 'equip', 'era', 'erase', 'erode', 'erosion', 'error', 'erupt', 'escape', 'essay', 'essence', 'estate', 'eternal', 'ethics', 'evidence', 'evil',
    'evoke', 'evolve', 'exact', 'example', 'excess', 'exchange', 'excite', 'exclude', 'excuse', 'execute', 'exercise', 'exhaust', 'exhibit', 'exile', 'exist', 'exit',
    'exotic', 'expand', 'expect', 'expire', 'explain', 'expose', 'express', 'extend', 'extra', 'eye', 'eyebrow', 'fabric', 'face', 'faculty', 'fade', 'faint',
    'faith', 'fall', 'false', 'fame', 'family', 'famous', 'fan', 'fancy', 'fantasy', 'farm', 'fashion', 'fat', 'fatal', 'father', 'fatigue', 'fault',
    'favorite', 'feature', 'february', 'federal', 'fee', 'feed', 'feel', 'female', 'fence', 'festival', 'fetch', 'fever', 'few', 'fiber', 'fiction', 'field',
    'figure', 'file', 'film', 'filter', 'final', 'find', 'fine', 'finger', 'finish', 'fire', 'firm', 'first', 'fiscal', 'fish', 'fit', 'fitness',
    'fix', 'flag', 'flame', 'flash', 'flat', 'flavor', 'flee', 'flight', 'flip', 'float', 'flock', 'floor', 'flower', 'fluid', 'flush', 'fly',
    'foam', 'focus', 'fog', 'foil', 'fold', 'follow', 'food', 'foot', 'force', 'forest', 'forget', 'fork', 'fortune', 'forum', 'forward', 'fossil',
    'foster', 'found', 'fox', 'fragile', 'frame', 'frequent', 'fresh', 'friend', 'fringe', 'frog', 'front', 'frost', 'frown', 'frozen', 'fruit', 'fuel',
    'fun', 'funny', 'furnace', 'fury', 'future', 'gadget', 'gain', 'galaxy', 'gallery', 'game', 'gap', 'garage', 'garbage', 'garden', 'garlic', 'garment',
    'gas', 'gasp', 'gate', 'gather', 'gauge', 'gaze', 'general', 'genius', 'genre', 'gentle', 'genuine', 'gesture', 'ghost', 'giant', 'gift', 'giggle',
    'ginger', 'giraffe', 'girl', 'give', 'glad', 'glance', 'glare', 'glass', 'glide', 'glimpse', 'globe', 'gloom', 'glory', 'glove', 'glow', 'glue',
    'goat', 'goddess', 'gold', 'good', 'goose', 'gorilla', 'gospel', 'gossip', 'govern', 'gown', 'grab', 'grace', 'grain', 'grant', 'grape', 'grass',
    'gravity', 'great', 'green', 'grid', 'grief', 'grit', 'grocery', 'group', 'grow', 'grunt', 'guard', 'guess', 'guide', 'guilt', 'guitar', 'gun',
    'gym', 'habit', 'hair', 'half', 'hammer', 'hamster', 'hand', 'happy', 'harbor', 'hard', 'harsh', 'harvest', 'hat', 'have', 'hawk', 'hazard',
    'head', 'health', 'heart', 'heavy', 'hedgehog', 'height', 'hello', 'helmet', 'help', 'hen', 'hero', 'hidden', 'high', 'hill', 'hint', 'hip',
    'hire', 'history', 'hobby', 'hockey', 'hold', 'hole', 'holiday', 'hollow', 'home', 'honey', 'hood', 'hope', 'horn', 'horror', 'horse', 'hospital',
    'host', 'hotel', 'hour', 'hover', 'hub', 'huge', 'human', 'humble', 'humor', 'hundred', 'hungry', 'hunt', 'hurdle', 'hurry', 'hurt', 'husband',
    'hybrid', 'ice', 'icon', 'idea', 'identify', 'idle', 'ignore', 'ill', 'illegal', 'illness', 'image', 'imitate', 'immense', 'immune', 'impact', 'impose',
    'improve', 'impulse', 'inch', 'include', 'income', 'increase', 'index', 'indicate', 'indoor', 'industry', 'infant', 'inflict', 'inform', 'inhale', 'inherit', 'initial',
    'inject', 'injury', 'inmate', 'inner', 'innocent', 'input', 'inquiry', 'insane', 'insect', 'inside', 'inspire', 'install', 'intact', 'interest', 'into', 'invest',
    'invite', 'involve', 'iron', 'island', 'isolate', 'issue', 'item', 'ivory', 'jacket', 'jaguar', 'jar', 'jazz', 'jealous', 'jeans', 'jelly', 'jewel',
    'job', 'join', 'joke', 'journey', 'joy', 'judge', 'juice', 'jump', 'jungle', 'junior', 'junk', 'just', 'kangaroo', 'keen', 'keep', 'ketchup',
    'key', 'kick', 'kid', 'kidney', 'kind', 'kingdom', 'kiss', 'kit', 'kitchen', 'kite', 'kitten', 'kiwi', 'knee', 'knife', 'knock', 'know',
    'lab', 'label', 'labor', 'ladder', 'lady', 'lake', 'lamp', 'language', 'laptop', 'large', 'later', 'latin', 'laugh', 'laundry', 'lava', 'law',
    'lawn', 'lawsuit', 'layer', 'lazy', 'leader', 'leaf', 'learn', 'leave', 'lecture', 'left', 'leg', 'legal', 'legend', 'leisure', 'lemon', 'lend',
    'length', 'lens', 'leopard', 'lesson', 'letter', 'level', 'liar', 'liberty', 'library', 'license', 'life', 'lift', 'light', 'like', 'limb', 'limit',
    'link', 'lion', 'liquid', 'list', 'little', 'live', 'lizard', 'load', 'loan', 'lobster', 'local', 'lock', 'logic', 'lonely', 'long', 'loop',
    'lottery', 'loud', 'lounge', 'love', 'loyal', 'lucky', 'luggage', 'lumber', 'lunar', 'lunch', 'luxury', 'lyrics', 'machine', 'mad', 'magic', 'magnet',
    'maid', 'mail', 'main', 'major', 'make', 'mammal', 'man', 'manage', 'mandate', 'mango', 'mansion', 'manual', 'maple', 'marble', 'march', 'margin',
    'marine', 'market', 'marriage', 'mask', 'mass', 'master', 'match', 'material', 'math', 'matrix', 'matter', 'maximum', 'maze', 'meadow', 'mean', 'measure',
    'meat', 'mechanic', 'medal', 'media', 'melody', 'melt', 'member', 'memory', 'mention', 'menu', 'mercy', 'merge', 'merit', 'merry', 'mesh', 'message',
    'metal', 'method', 'middle', 'midnight', 'milk', 'million', 'mimic', 'mind', 'minimum', 'minor', 'minute', 'miracle', 'mirror', 'misery', 'miss', 'mistake',
    'mix', 'mixed', 'mixture', 'mobile', 'model', 'modify', 'mom', 'moment', 'monitor', 'monkey', 'monster', 'month', 'moon', 'moral', 'more', 'morning',
    'mosquito', 'mother', 'motion', 'motor', 'mountain', 'mouse', 'move', 'movie', 'much', 'muffin', 'mule', 'multiply', 'muscle', 'museum', 'mushroom', 'music',
    'must', 'mutual', 'myself', 'mystery', 'myth', 'naive', 'name', 'napkin', 'narrow', 'nasty', 'nation', 'nature', 'near', 'neck', 'need', 'negative',
    'neglect', 'neither', 'nephew', 'nerve', 'nest', 'net', 'network', 'neutral', 'never', 'news', 'next', 'nice', 'night', 'noble', 'noise', 'nominee',
    'noodle', 'normal', 'north', 'nose', 'notable', 'note', 'nothing', 'notice', 'novel', 'now', 'nuclear', 'number', 'nurse', 'nut', 'oak', 'obey',
    'object', 'oblige', 'obscure', 'observe', 'obtain', 'obvious', 'occur', 'ocean', 'october', 'odor', 'off', 'offer', 'office', 'often', 'oil', 'okay',
    'old', 'olive', 'olympic', 'omit', 'once', 'one', 'onion', 'online', 'only', 'open', 'opera', 'opinion', 'oppose', 'option', 'orange', 'orbit',
    'orchard', 'order', 'ordinary', 'organ', 'orient', 'original', 'orphan', 'ostrich', 'other', 'outdoor', 'outer', 'output', 'outside', 'oval', 'oven', 'over',
    'own', 'owner', 'oxygen', 'oyster', 'ozone', 'pact', 'paddle', 'page', 'pair', 'palace', 'palm', 'panda', 'panel', 'panic', 'panther', 'paper',
    'parade', 'parent', 'park', 'parrot', 'party', 'pass', 'patch', 'path', 'patient', 'patrol', 'pattern', 'pause', 'pave', 'payment', 'peace', 'peanut',
    'pear', 'peasant', 'pelican', 'pen', 'penalty', 'pencil', 'people', 'pepper', 'perfect', 'permit', 'person', 'pet', 'phone', 'photo', 'phrase', 'physical',
    'piano', 'picnic', 'picture', 'piece', 'pig', 'pigeon', 'pill', 'pilot', 'pink', 'pioneer', 'pipe', 'pistol', 'pitch', 'pizza', 'place', 'planet',
    'plastic', 'plate', 'play', 'please', 'pledge', 'pluck', 'plug', 'plunge', 'poem', 'poet', 'point', 'polar', 'pole', 'police', 'pond', 'pony',
    'pool', 'popular', 'portion', 'position', 'possible', 'post', 'potato', 'pottery', 'poverty', 'powder', 'power', 'practice', 'praise', 'predict', 'prefer', 'prepare',
    'present', 'pretty', 'prevent', 'price', 'pride', 'primary', 'print', 'priority', 'prison', 'private', 'prize', 'problem', 'process', 'produce', 'profit', 'program',
    'project', 'promote', 'proof', 'property', 'prosper', 'protect', 'proud', 'provide', 'public', 'pudding', 'pull', 'pulp', 'pulse', 'pumpkin', 'punch', 'pupil',
    'puppy', 'purchase', 'purity', 'purpose', 'purse', 'push', 'put', 'puzzle', 'pyramid', 'quality', 'quantum', 'quarter', 'question', 'quick', 'quit', 'quiz',
    'quote', 'rabbit', 'raccoon', 'race', 'rack', 'radar', 'radio', 'rail', 'rain', 'raise', 'rally', 'ramp', 'ranch', 'random', 'range', 'rapid',
    'rare', 'rate', 'rather', 'raven', 'raw', 'razor', 'ready', 'real', 'reason', 'rebel', 'rebuild', 'recall', 'receive', 'recipe', 'record', 'recycle',
    'reduce', 'reflect', 'reform', 'refuse', 'region', 'regret', 'regular', 'reject', 'relax', 'release', 'relief', 'rely', 'remain', 'remember', 'remind', 'remove',
    'render', 'renew', 'rent', 'reopen', 'repair', 'repeat', 'replace', 'report', 'require', 'rescue', 'resemble', 'resist', 'resource', 'response', 'result', 'retire',
    'retreat', 'return', 'reunion', 'reveal', 'review', 'reward', 'rhythm', 'rib', 'ribbon', 'rice', 'rich', 'ride', 'ridge', 'rifle', 'right', 'rigid',
    'ring', 'riot', 'ripple', 'risk', 'ritual', 'rival', 'river', 'road', 'roast', 'robot', 'robust', 'rocket', 'romance', 'roof', 'rookie', 'room',
    'rose', 'rotate', 'rough', 'round', 'route', 'royal', 'rubber', 'rude', 'rug', 'rule', 'run', 'runway', 'rural', 'sad', 'saddle', 'sadness',
    'safe', 'sail', 'salad', 'salmon', 'salon', 'salt', 'salute', 'same', 'sample', 'sand', 'satisfy', 'satoshi', 'sauce', 'sausage', 'save', 'say',
    'scale', 'scan', 'scare', 'scatter', 'scene', 'scheme', 'school', 'science', 'scissors', 'scorpion', 'scout', 'scrap', 'screen', 'script', 'scrub', 'sea',
    'search', 'season', 'seat', 'second', 'secret', 'section', 'security', 'seed', 'seek', 'segment', 'select', 'sell', 'seminar', 'senior', 'sense', 'sentence',
    'series', 'service', 'session', 'settle', 'setup', 'seven', 'shadow', 'shaft', 'shallow', 'share', 'shed', 'shell', 'sheriff', 'shield', 'shift', 'shine',
    'ship', 'shiver', 'shock', 'shoe', 'shoot', 'shop', 'short', 'shoulder', 'shove', 'shrimp', 'shrug', 'shuffle', 'shy', 'sibling', 'sick', 'side',
    'siege', 'sight', 'sign', 'silent', 'silk', 'silly', 'silver', 'similar', 'simple', 'since', 'sing', 'siren', 'sister', 'situate', 'six', 'size',
    'skate', 'sketch', 'ski', 'skill', 'skin', 'skirt', 'skull', 'slab', 'slam', 'sleep', 'slender', 'slice', 'slide', 'slight', 'slim', 'slogan',
    'slot', 'slow', 'slush', 'small', 'smart', 'smile', 'smoke', 'smooth', 'snack', 'snake', 'snap', 'sniff', 'snow', 'soap', 'soccer', 'social',
    'sock', 'soda', 'soft', 'solar', 'soldier', 'solid', 'solution', 'solve', 'someone', 'song', 'soon', 'sorry', 'sort', 'soul', 'sound', 'soup',
    'source', 'south', 'space', 'spare', 'spatial', 'spawn', 'speak', 'special', 'speed', 'spell', 'spend', 'sphere', 'spice', 'spider', 'spike', 'spin',
    'spirit', 'split', 'spoil', 'sponsor', 'spoon', 'sport', 'spot', 'spray', 'spread', 'spring', 'spy', 'square', 'squeeze', 'squirrel', 'stable', 'stadium',
    'staff', 'stage', 'stairs', 'stamp', 'stand', 'start', 'state', 'stay', 'steak', 'steel', 'stem', 'step', 'stereo', 'stick', 'still', 'sting',
    'stock', 'stomach', 'stone', 'stool', 'story', 'stove', 'strategy', 'street', 'strike', 'strong', 'struggle', 'student', 'stuff', 'stumble', 'style', 'subject',
    'submit', 'subway', 'success', 'such', 'sudden', 'suffer', 'sugar', 'suggest', 'suit', 'summer', 'sun', 'sunny', 'sunset', 'super', 'supply', 'supreme',
    'sure', 'surface', 'surge', 'surprise', 'surround', 'survey', 'suspect', 'sustain', 'swallow', 'swamp', 'swap', 'swarm', 'swear', 'sweet', 'swift', 'swim',
    'swing', 'switch', 'sword', 'symbol', 'symptom', 'syrup', 'system', 'table', 'tackle', 'tag', 'tail', 'talent', 'talk', 'tank', 'tape', 'target',
    'task', 'taste', 'tattoo', 'taxi', 'teach', 'team', 'tell', 'ten', 'tenant', 'tennis', 'tent', 'term', 'test', 'text', 'thank', 'that',
    'theme', 'then', 'theory', 'there', 'they', 'thing', 'this', 'thought', 'three', 'thrive', 'throw', 'thumb', 'thunder', 'ticket', 'tide', 'tiger',
    'tilt', 'timber', 'time', 'tiny', 'tip', 'tired', 'tissue', 'title', 'toast', 'tobacco', 'today', 'toddler', 'toe', 'together', 'toilet', 'token',
    'tomato', 'tomorrow', 'tone', 'tongue', 'tonight', 'tool', 'tooth', 'top', 'topic', 'topple', 'torch', 'tornado', 'tortoise', 'toss', 'total', 'tourist',
    'toward', 'tower', 'town', 'toy', 'track', 'trade', 'traffic', 'tragic', 'train', 'transfer', 'trap', 'trash', 'travel', 'tray', 'treat', 'tree',
    'trend', 'trial', 'tribe', 'trick', 'trigger', 'trim', 'trip', 'trophy', 'trouble', 'truck', 'true', 'truly', 'trumpet', 'trust', 'truth', 'try',
    'tube', 'tuition', 'tumble', 'tuna', 'tunnel', 'turkey', 'turn', 'turtle', 'twelve', 'twenty', 'twice', 'twin', 'twist', 'two', 'type', 'typical',
    'ugly', 'umbrella', 'unable', 'unaware', 'uncle', 'uncover', 'under', 'undo', 'unfair', 'unfold', 'unhappy', 'uniform', 'unique', 'unit', 'universe', 'unknown',
    'unlock', 'until', 'unusual', 'unveil', 'update', 'upgrade', 'uphold', 'upon', 'upper', 'upset', 'urban', 'urge', 'usage', 'use', 'used', 'useful',
    'useless', 'usual', 'utility', 'vacant', 'vacuum', 'vague', 'valid', 'valley', 'valve', 'van', 'vanish', 'vapor', 'various', 'vast', 'vault', 'vehicle',
    'velvet', 'vendor', 'venture', 'venue', 'verb', 'verify', 'version', 'very', 'vessel', 'veteran', 'viable', 'vibrant', 'vicious', 'victory', 'video', 'view',
    'village', 'vintage', 'violin', 'virtual', 'virus', 'visa', 'visit', 'visual', 'vital', 'vivid', 'vocal', 'voice', 'void', 'volcano', 'volume', 'vote',
    'voyage', 'wage', 'wagon', 'wait', 'walk', 'wall', 'walnut', 'want', 'warfare', 'warm', 'warrior', 'wash', 'wasp', 'waste', 'water', 'wave',
    'way', 'wealth', 'weapon', 'wear', 'weasel', 'weather', 'web', 'wedding', 'weekend', 'weird', 'welcome', 'west', 'wet', 'whale', 'what', 'wheat',
    'wheel', 'when', 'where', 'whip', 'whisper', 'wide', 'width', 'wife', 'wild', 'will', 'win', 'window', 'wine', 'wing', 'wink', 'winner',
    'winter', 'wire', 'wisdom', 'wise', 'wish', 'witness', 'wolf', 'woman', 'wonder', 'wood', 'wool', 'word', 'work', 'world', 'worry', 'worth',
    'wrap', 'wreck', 'wrestle', 'wrist', 'write', 'wrong', 'yard', 'year', 'yellow', 'you', 'young', 'youth', 'zebra', 'zero', 'zone', 'zoo'
]

class WordIndex(dict):
    def index(self, word):
        return self[word]
wordindex = WordIndex({word: i for i, word in enumerate(WORDLIST)})


def choices(population, k=1):
    result = []
    for i in range(k):
        result.append(random.choice(population))
    return result

def mnemonic_to_bytes_speedup(mnemonic: str, ignore_checksum: bool = False, wordlist=WORDLIST):
    # this function is copied from Jimmy Song's HDPrivateKey.from_mnemonic() method

    words = mnemonic.strip().split()
    if len(words) % 3 != 0 or len(words) < 12:
        raise ValueError("Invalid recovery phrase")

    binary_seed = bytearray()
    offset = 0
    for word in words:
        try:
            index = wordlist.index(word)
        except Exception:
            raise ValueError("Word '%s' is not in the dictionary" % word)
        remaining = 11
        while remaining > 0:
            bits_needed = 8 - offset
            if remaining == bits_needed:
                if bits_needed == 8:
                    binary_seed.append(index)
                else:
                    binary_seed[-1] |= index
                offset = 0
                remaining = 0
            elif remaining > bits_needed:
                if bits_needed == 8:
                    binary_seed.append(index >> (remaining - 8))
                else:
                    binary_seed[-1] |= index >> (remaining - bits_needed)
                remaining -= bits_needed
                offset = 0
                # lop off the top 8 bits
                index &= (1 << remaining) - 1
            else:
                binary_seed.append(index << (8 - remaining))
                offset = remaining
                remaining = 0

    checksum_length_bits = len(words) * 11 // 33
    num_remainder = checksum_length_bits % 8
    if num_remainder:
        checksum_length = checksum_length_bits // 8 + 1
        bits_to_ignore = 8 - num_remainder
    else:
        checksum_length = checksum_length_bits // 8
        bits_to_ignore = 0
    raw = bytes(binary_seed)
    data, checksum = raw[:-checksum_length], raw[-checksum_length:]
    computed_checksum = bytearray(hashlib.sha256(data).digest()[:checksum_length])

    # ignore the last bits_to_ignore bits
    computed_checksum[-1] &= 256 - (1 << (bits_to_ignore + 1) - 1)
    if not ignore_checksum and checksum != bytes(computed_checksum):
        raise ValueError("Checksum verification failed")
    return data

def mnemonic_to_bytes(mnemonic: str, ignore_checksum: bool = False, wordlist=WORDLIST):
    # this function is copied from Jimmy Song's HDPrivateKey.from_mnemonic() method

    words = mnemonic.strip().split()
    if len(words) % 3 != 0 or len(words) < 12:
        raise ValueError("Invalid recovery phrase")

    binary_seed = bytearray()
    offset = 0
    for word in words:
        if word not in wordlist:
            raise ValueError("Word '%s' is not in the dictionary" % word)
        index = wordlist.index(word)
        remaining = 11
        while remaining > 0:
            bits_needed = 8 - offset
            if remaining == bits_needed:
                if bits_needed == 8:
                    binary_seed.append(index)
                else:
                    binary_seed[-1] |= index
                offset = 0
                remaining = 0
            elif remaining > bits_needed:
                if bits_needed == 8:
                    binary_seed.append(index >> (remaining - 8))
                else:
                    binary_seed[-1] |= index >> (remaining - bits_needed)
                remaining -= bits_needed
                offset = 0
                # lop off the top 8 bits
                index &= (1 << remaining) - 1
            else:
                binary_seed.append(index << (8 - remaining))
                offset = remaining
                remaining = 0

    checksum_length_bits = len(words) * 11 // 33
    num_remainder = checksum_length_bits % 8
    if num_remainder:
        checksum_length = checksum_length_bits // 8 + 1
        bits_to_ignore = 8 - num_remainder
    else:
        checksum_length = checksum_length_bits // 8
        bits_to_ignore = 0
    raw = bytes(binary_seed)
    data, checksum = raw[:-checksum_length], raw[-checksum_length:]
    computed_checksum = bytearray(hashlib.sha256(data).digest()[:checksum_length])

    # ignore the last bits_to_ignore bits
    computed_checksum[-1] &= 256 - (1 << (bits_to_ignore + 1) - 1)
    if not ignore_checksum and checksum != bytes(computed_checksum):
        raise ValueError("Checksum verification failed")
    return data



def main():

    runs = [
        (mnemonic_to_bytes, WORDLIST),
        (mnemonic_to_bytes_speedup, WORDLIST),
        (mnemonic_to_bytes, wordindex),
        (mnemonic_to_bytes_speedup, wordindex),
    ]
    
    summary = []
    for (function, wordlist_arg) in runs:
        count = 0
        valid = []
        random.seed(0)
        t0 = my_time()
        for i in range(5000):
            count += 1
            mnemonic = " ".join(choices(WORDLIST, k=24))
            try: result = function(mnemonic, wordlist=wordlist_arg)
            except: result = None
            if result: 
                print(mnemonic)
                valid.append(result)
        elapsed = my_time() - t0
        print()

        summary.append(
            "%-40s %3d/%4d valid, elapsed: %10dus %6dus/call" % (
                function.__name__ + " w/ " + type(wordlist_arg).__name__,
                len(valid), 
                count, 
                elapsed/us_divisor,
                elapsed/count/us_divisor
            )
        )
    print("\n".join(summary))


if __name__ == "__main__":
    main()