Breakthroughs in Wallets and Key Handling#

blockchainkit.wallets hub · History · Examples · API reference

“Your keys, your bitcoin. Not your keys, not your bitcoin.” – Andreas M. Antonopoulos, 2017

A cryptocurrency is digital money. Its record of who owns what is kept on a blockchain: a shared record, like a Python list of blocks of transactions. Many computers keep copies of it in step, and nobody can quietly edit an old entry. Cryptography is the mathematics of keeping and checking secrets.

Whoever holds the right secret number can spend the coins. So most of the money lost in cryptocurrencies is not lost to broken cryptography. It is lost to the way people handle their secrets:

a typo in an address sends a payment nowhere, or to someone else;
a guessable secret, such as a passphrase from a song, is guessed;
a lost backup loses the coins for good;
a single point of failure, one key on one laptop, fails.

A wallet is the program, or the habit, that holds a user’s secrets. This chronology follows how wallets learned to defend against each of these. It runs from the error-detecting codes behind addresses, through stretching passwords and deriving whole trees of keys from one backup, to sharing control of a key among several people or devices.

A few terms recur on every page:

A key pair is a secret number, the private key, and a public number computed from it, the public key. Here keys live on secp256k1, the elliptic curve of Bitcoin and Ethereum: the public key is the point \(K = kG\), a fixed point \(G\) added to itself \(k\) times. Computing \(K\) from \(k\) is fast; the reverse is infeasible.
A digital signature is a value only the private key could produce, but that anyone can check with the public key.
A hash function is like Python’s hash(), but built so that nobody can find two inputs with the same output, or an input with a chosen output. SHA-256 is the standard one. HMAC is a hash keyed by a secret.
An address is a short public name for a key or a script, like an account number: usually a hash of it, written in a form people can copy.
A smart contract (or just contract) is a program stored on a blockchain at its own address. Anyone can call its functions by sending a transaction. Ethereum is the main blockchain for contracts, and ether is its currency.

Several neighbours live elsewhere: Shamir’s and Feldman’s secret sharing and MuSig are in Breakthroughs in Cryptography, Bitcoin Script and P2PKH in Breakthroughs in Replicated Execution, the Parity multisig wallets in Breakthroughs in Smart Contracts, and address poisoning in Breakthroughs in Blockchain Fraud. Those pages explain their own terms.

The models in blockchainkit.wallets come in three kinds:

pure functions, whose output depends only on their input. Where a standard exists (Base58Check, Bech32, PBKDF2, scrypt, BIP32, BIP39’s seed derivation, ECDSA) they reproduce its published test vectors;
small seeded simulations, random but reproducible, as after random.seed(0);
contracts on World, a Python model of Ethereum.

Exact conventions and model boundaries lists where the models depart from deployed systems.

1959-1960 – BCH Codes: Correcting Errors with Polynomials #

A message sent over a noisy line arrives with some bits flipped. An error-correcting code adds redundant bits, so that the receiver can find and undo the flips. Alexis Hocquenghem in 1959, and independently Raj Chandra Bose and Dijen Ray-Chaudhuri in 1960, found how to build binary codes that correct any chosen number \(t\) of flipped bits.

The trick is to treat a word of bits as a polynomial, bit \(i\) being the coefficient of \(x^i\):

Work in a finite field GF(\(2^m\)), a set of \(2^m\) numbers with addition and multiplication. One element, \(\alpha\), generates all the others as its powers.
Pick a generator polynomial \(g(x)\) whose roots include \(\alpha, \alpha^2, \ldots, \alpha^{2t}\).
The codewords are the multiples of \(g(x)\), of length \(n = 2^m - 1\). To encode, append to the message the remainder that makes it a multiple.

Any two codewords then differ in at least

\[d \ge 2t + 1\]

bits (the BCH bound). So a received word with at most \(t\) errors is closer to its own codeword than to any other.

Decoding evaluates the received word at \(\alpha^j\). A codeword gives zero; the nonzero values, the syndromes, depend only on where the errors are. The Berlekamp-Massey algorithm turns them into a polynomial whose roots name the error positions.
Beyond t errors the decoder may give up, or worse, “correct” the word to a different codeword.
Bech32 addresses, in the 2017 entry, use a BCH code over GF(32) to detect, rather than correct, a person’s typos.

Implementation: blockchainkit.wallets.systems.bch.BCHCode builds narrow-sense binary BCH codes for \(3 \le m \le 8\) over blockchainkit.wallets.utils.galois.GaloisField, with systematic encoding, syndromes, Berlekamp-Massey and Chien’s search. Only binary codes are built; the Reed-Solomon codes of Breakthroughs in Layer-2 Scaling and Interoperability are their non-binary cousins.

References: A. Hocquenghem, Codes correcteurs d’erreurs, Chiffres 2, 147–156 (1959); R. C. Bose and D. K. Ray-Chaudhuri, On a class of error correcting binary group codes, Information and Control 3(1), 68–79 (1960). DOI; J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15(1), 122–127 (1969).

BCH error-correcting codes (1959-1960)

1969 – Verhoeff’s Check Digit and Detecting Transpositions #

A check digit is one extra digit appended to a number, such as an account number, so that a number copied with a mistake fails a test. Jacobus Verhoeff studied the mistakes Dutch clerks actually made. Most were one wrong digit; most of the rest were two neighbouring digits swapped, as in 1243 for 1234.

Adding the digits modulo 10 catches every wrong digit, but no swap: addition does not care about order.
Luhn’s scheme (1954), still on payment cards, doubles every second digit. It catches every swap except 09 and 90.
Verhoeff’s scheme catches every wrong digit and every swap.

Verhoeff’s insight was to compute in a group where order matters. The ten symmetries of a regular pentagon, five rotations and five reflections, form the dihedral group \(D_5\). Composing two of them depends on the order: rotate then reflect is not reflect then rotate. Label them 0 to 9 and write \(a * b\) for their composition. Then:

Permute each digit by a fixed permutation \(\sigma\), applied \(i\) times for the digit in position \(i\) from the right.
Choose the check digit \(a_0\) so that

\[\sigma^{0}(a_0) * \sigma^{1}(a_1) * \cdots * \sigma^{k}(a_k) = 0 .\]

A swap of neighbours changes the product, because neither the group nor the permutation lets the two digits trade places unnoticed. Addresses, in the next entries, protect a whole string the same way, with a checksum.

Implementation: blockchainkit.wallets.systems.check_digits.verhoeff_digit(), blockchainkit.wallets.systems.check_digits.luhn_digit() and blockchainkit.wallets.systems.check_digits.detection_rates(), which measures each scheme against every single error and adjacent swap of every short number. The \(D_5\) table is computed from the pentagon’s symmetries rather than copied.

References: J. Verhoeff, Error Detecting Decimal Codes, Mathematical Centre Tracts 29, Mathematisch Centrum, Amsterdam (1969); H. P. Luhn, Computer for verifying numbers, US Patent 2,950,048 (filed 1954, granted 1960).

Verhoeff’s check digit and detecting transpositions (1969)

Verhoeff's check digit and detecting transpositions (1969)

2000 – PBKDF2: Stretching Passwords into Keys #

A password makes a poor key. People choose a few thousand likely passwords, and an attacker who can test guesses offline simply tries them all. Burt Kaliski’s PBKDF2, published as RFC 2898, cannot make a password less guessable, but it can make every guess expensive:

Mix in a salt, a random value stored with the result. Two users with the same password get different keys, and the attacker cannot reuse one table of precomputed guesses for everyone.
Iterate a keyed hash \(c\) times, adding up the results with XOR:

\[U_1 = \mathrm{HMAC}(P, S \,\|\, 1), \quad U_j = \mathrm{HMAC}(P, U_{j-1}), \quad T = U_1 \oplus U_2 \oplus \cdots \oplus U_c .\]

The honest user pays \(c\) HMAC calls once, at login. An attacker trying \(N\) passwords pays \(N c\).

Stretching buys a fixed factor. 100,000 iterations make a six-digit PIN as costly as an unstretched eleven-digit one; it does not make a six-digit PIN safe.
It needs almost no memory, so a graphics card or custom chip runs thousands of guesses side by side. scrypt, in the second 2009 entry, attacks that.
BIP39 seed phrases, in the 2013 entry, are stretched with PBKDF2.

Implementation: blockchainkit.wallets.systems.stretching.pbkdf2() (HMAC with SHA-1, SHA-256 or SHA-512, checked against RFC 6070’s vectors and hashlib) and blockchainkit.wallets.systems.stretching.crack_pin(), which counts the attacker’s HMAC calls.

References: B. Kaliski, PKCS #5: Password-Based Cryptography Specification Version 2.0, RFC 2898 (September 2000); S. Josefsson, PKCS #5: PBKDF2 Test Vectors, RFC 6070 (January 2011).

PBKDF2 key stretching (2000)

2009 – Base58Check Addresses #

In Bitcoin’s first release, an address names a public key by its hash, written so that people can copy it. Its parts are:

a version byte, 0 for an ordinary Bitcoin address;
the 20-byte HASH160 of the public key, which is \(\mathrm{RIPEMD160}(\mathrm{SHA256}(K))\);
a 4-byte checksum: the first bytes of SHA-256 applied twice to the first two parts.

The result is written in base 58: the digits and letters, without 0, O, I and l, which are easily confused. Each leading zero byte is written as a leading 1, so ordinary addresses start with 1.

A wallet refuses an address whose checksum fails. A typo slips through only if the changed address happens to match its own checksum, with probability

\[2^{-32} \approx 2.3 \times 10^{-10} .\]

Without a checksum, every typo is a valid address. The account names of blockchainkit.structures are bare SHA-256 hex digests, where a typo silently pays a stranger, or nobody.
A hash promises nothing in particular. It catches most errors, but no class of errors is guaranteed, and it cannot say where a typo is. Bech32 will improve on both.
Base58Check also writes private keys and the extended keys of the 2012 entry.

Implementation: blockchainkit.wallets.systems.base58.base58check_encode(), blockchainkit.wallets.systems.base58.base58check_decode() and blockchainkit.wallets.systems.base58.p2pkh_address(), with RIPEMD-160 written out in blockchainkit.wallets.utils.ripemd160.hash160() since hashlib does not always provide it. Addresses match Bitcoin’s: private key 1 gives 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH.

References: S. Nakamoto, Bitcoin v0.1 source code, base58.h (January 2009); H. Dobbertin, A. Bosselaers and B. Preneel, RIPEMD-160: A strengthened version of RIPEMD, Fast Software Encryption, LNCS 1039, 71–82 (1996).

Base58Check addresses (2009)

2009 – scrypt and Memory-Hard Key Derivation #

PBKDF2 makes a guess slow, but a guess fits in a few hundred bytes. So an attacker builds a chip with thousands of tiny guessing circuits. Colin Percival’s scrypt makes each guess need a large amount of memory as well. Memory costs chip area, so parallel guessing gets expensive.

Its core, ROMix, works on a block \(B\) and a table of \(N\) entries:

Fill the table: each entry is a scrambled version of the last, \(V_i = \mathrm{BlockMix}^{\,i}(B)\).
Then make \(N\) reads, each at an address that depends on the current value:

\[X \leftarrow \mathrm{BlockMix}(X \oplus V_{\mathrm{Integerify}(X) \bmod N}).\]

The attacker cannot know in advance which entries will be needed.

Keeping the whole table costs \(N\) entries of memory and \(2N\) BlockMix calls.
Keeping only every k-th entry saves memory, but each missing entry must be recomputed from the last kept one, about \(k/2\) calls a read. Memory times time stays roughly constant.
Percival proved that no strategy does much better. So an attack’s cost, in chip area times time, grows with \(N^2\) rather than \(N\). Litecoin and many wallets adopted scrypt.

Implementation: blockchainkit.wallets.systems.scrypt.scrypt() implements RFC 7914 exactly, from blockchainkit.wallets.systems.scrypt.salsa20_8() and blockchainkit.wallets.systems.scrypt.block_mix(); blockchainkit.wallets.systems.scrypt.romix() adds a keep_every parameter that stores fewer entries and counts the cost. Parameters are small enough to run in pure Python.

References: C. Percival, Stronger key derivation via sequential memory-hard functions, BSDCan (2009); C. Percival and S. Josefsson, The scrypt Password-Based Key Derivation Function, RFC 7914 (August 2016).

scrypt and memory-hard key derivation (2009)

2012 – Pay-to-Script-Hash and Multisig Wallets #

One key on one device is one point of failure: lose it, or let it be copied, and the coins are gone. A coin locked to 2 of 3 keys survives either. Bitcoin could do this from the start, with a locking script listing all three keys. But the payer had to write that script into the payment, and pay a fee for its size, for a policy that was the payee’s business.

Gavin Andresen’s BIP16, pay to script hash (P2SH), moved the script to the spender:

The payee writes a redeem script, say “2 of these 3 keys”, and gives out only its hash, as an address starting with 3.
The coin is locked by a short script that only checks that hash:

\[\texttt{OP\_HASH160}\ \langle H(\text{redeem}) \rangle\ \texttt{OP\_EQUAL} .\]

To spend, the owners reveal the redeem script and their signatures. Validation runs in two stages: first the revealed script must hash to the locked value, then it runs on the signatures.

The policy stays private until the coin is spent, and the payer’s fee no longer depends on it.
Multisig became routine: exchanges’ cold storage, escrow, and wallets that split keys between a phone and a server.
The redeem script is capped at 520 bytes, the largest data push, which bounds how many keys it can list.

Implementation: blockchainkit.wallets.systems.p2sh.verify_p2sh() (the two stages, over blockchainkit.vm.systems.script.verify_script()), blockchainkit.wallets.systems.p2sh.multisig_redeem_script() and blockchainkit.wallets.systems.p2sh.serialize_script() (Bitcoin’s opcode bytes and push prefixes). The teaching Script has no OP_HASH160 or OP_CHECKMULTISIG, so the hash is OP_HASH256 and m-of-n is one OP_IF branch per set of m signers; 2-of-3 fits in 520 bytes, 2-of-4 does not.

References: G. Andresen, BIP 16: Pay to Script Hash (January 2012); G. Andresen, BIP 11: M-of-N Standard Transactions (2011).

Pay-to-script-hash and multisig (BIP16, 2012)

2012 – Hierarchical Deterministic Wallets (BIP32)#

Early Bitcoin wallets drew each new key at random. A backup held only the keys made so far, so a backup from last month could miss this week’s payments. Pieter Wuille’s BIP32 derives a whole tree of keys from one seed, so one backup, made once, covers every key the wallet will ever use.

An extended key is a private key \(k\) together with 32 extra bytes, its chain code \(c\). Child number \(i\) is made by hashing:

\[I = \mathrm{HMAC\text{-}SHA512}(c,\ K \,\|\, i), \qquad k_i = I_L + k \bmod n, \qquad c_i = I_R ,\]

where \(I_L\) and \(I_R\) are the two halves of the 64-byte result, and \(K = kG\) is the parent’s public key.

Public derivation. Since \(k_i G = I_L G + K\), anyone with the parent’s public key and chain code, its extended public key or xpub, can compute every child’s public key, but no private key. A shop’s web server can hand out a fresh address per order and hold nothing worth stealing.
The catch. The xpub and the private key of any one such child give away the parent: \(k = k_i - I_L\). Then every sibling falls too.
Hardened children, numbered from \(2^{31}\) and written \(i'\), hash the parent’s private key instead. They cannot be derived from an xpub, and do not leak their parent. Accounts are hardened for that reason.

Implementation: blockchainkit.wallets.systems.hd.master_key(), blockchainkit.wallets.systems.hd.derive_private(), blockchainkit.wallets.systems.hd.derive_public(), blockchainkit.wallets.systems.hd.serialize_extended_key() (xprv and xpub strings) and blockchainkit.wallets.systems.hd.recover_parent_private(), the leaked xpub attack. It reproduces BIP32’s first test vector on secp256k1.

References: P. Wuille, BIP 32: Hierarchical Deterministic Wallets (February 2012).

Hierarchical deterministic wallets (BIP32, 2012)

2013 – Mnemonic Seed Phrases (BIP39)#

A 128-bit seed written in hexadecimal is 32 characters such as 0c1e24e5917779d2..., which people miscopy. Marek Palatinus, Pavol Rusnak, Aaron Voisine and Sean Bowe proposed writing it as words:

Take 128 to 256 bits of random entropy.
Append a checksum: the first ENT/32 bits of its SHA-256.
Cut the bits into groups of 11. Each group is a number from 0 to 2047, and picks a word from a fixed list of 2048.

So

\[\frac{ENT + ENT/32}{11} \text{ words}: \qquad 128 \text{ bits} \to 12 \text{ words}, \quad 256 \text{ bits} \to 24 .\]

A miscopied word changes 11 bits, and the 4-bit checksum of a 12-word phrase catches it 15 times in 16.
The seed for BIP32 comes from stretching the phrase with PBKDF2 (HMAC-SHA512, 2048 iterations), salted with "mnemonic" plus an optional passphrase.
Every passphrase is valid and gives a different wallet. That allows a decoy wallet under duress, but a mistyped passphrase opens an empty wallet without any error.

The phrase is the whole wallet. Written on paper it is safe from hackers and exposed to fire, burglars and heirs who do not know what it is.

Implementation: blockchainkit.wallets.systems.mnemonics.entropy_to_mnemonic(), blockchainkit.wallets.systems.mnemonics.mnemonic_to_entropy() and blockchainkit.wallets.systems.mnemonics.mnemonic_to_seed(). The word list is 2048 four-letter words generated by a rule, not BIP39’s English list, so phrases differ from real wallets’; the seed derivation is BIP39’s own and reproduces its test vectors for English phrases.

References: M. Palatinus, P. Rusnak, A. Voisine and S. Bowe, BIP 39: Mnemonic code for generating deterministic keys (September 2013).

Mnemonic seed phrases (BIP39, 2013)

2014 – Multi-Account Derivation Paths (BIP44)#

BIP32 allows any tree of keys. So a seed backed up from one wallet program could restore an empty-looking wallet in another, which looked in other branches. Marek Palatinus and Pavol Rusnak fixed where keys sit, with five levels:

\[m / 44' / \text{coin}' / \text{account}' / \text{change} / \text{index}\]

purpose 44, hardened, names this scheme;
coin type, hardened: 0 for Bitcoin, 60 for Ether;
account, hardened, like separate bank accounts;
change: 0 for addresses given out to receive payments, 1 for the wallet’s own change;
index, counting addresses from 0.

A restoring wallet cannot know how many addresses were used, so it scans:

On each account’s receiving chain, derive addresses in order until 20 in a row have never been used. That number is the gap limit.
Stop at the first account with no used address at all.

A wallet that handed out more than 20 unpaid addresses in a row has made later payments invisible to any other wallet restoring the seed. The coins are safe, but nobody looks for them.

Implementation: blockchainkit.wallets.systems.paths.derive_path(), blockchainkit.wallets.systems.paths.parse_path() and blockchainkit.wallets.systems.paths.discover_accounts(), which scans P2PKH addresses with a chosen gap limit. Only the receiving chain is scanned, as BIP44 specifies.

References: M. Palatinus and P. Rusnak, BIP 44: Multi-Account Hierarchy for Deterministic Wallets (April 2014).

Multi-account derivation paths (BIP44, 2014)

2016 – The Brain-Wallet Drain #

A brain wallet keeps no file. Its private key is the hash of a passphrase the owner remembers:

\[k = \mathrm{SHA256}(\text{passphrase}) .\]

The appeal is that the coins can be carried across a border in one’s head. The flaw is that anyone can hash the same passphrase. Marie Vasek, Joseph Bonneau, Ryan Castellucci, Cameron Keith and Tyler Moore searched the Bitcoin blockchain for brain wallets by hashing billions of candidate phrases. They found that:

thieves had done the same, hashing dictionaries, quotations, lyrics and leaked passwords, and keeping a table from address to key;
most funded brain wallets were emptied, many within minutes of the first deposit;
thieves raced one another to sweep the same wallets.

Nothing slows the thieves. There is no salt, so one table serves every victim, and no stretching. And a phrase a person picks, even an obscure one, has far less entropy than the 128 bits of a random key.

Implementation: blockchainkit.wallets.systems.brainwallets.brain_wallet_key(), blockchainkit.wallets.systems.brainwallets.crack_brain_wallet() and blockchainkit.wallets.systems.brainwallets.simulate_brain_drain(), a seeded race of thieves with precomputed tables of a small PHRASEBOOK. Keys and addresses are real ("password" gives 16ga2uqnF1NqpAuQeeg7sTCAdtDUwDyJav); the population and the thieves’ delays are invented.

References: M. Vasek, J. Bonneau, R. Castellucci, C. Keith and T. Moore, The Bitcoin brain drain: examining the use and abuse of bitcoin brain wallets, Financial Cryptography and Data Security 2016, LNCS 9603 (2017).

The brain-wallet drain (Vasek et al., 2016)

2017 – Bech32 Addresses (BIP173)#

Segregated witness, activated in 2017, needed a new address format, and Pieter Wuille and Gregory Maxwell took the chance to design one for people rather than computers. A Bech32 string is:

a human-readable part such as bc for Bitcoin;
the separator 1;
data in 32 characters, all lower case, chosen to avoid look-alikes;
a 6-character checksum.

The checksum is a BCH code over GF(32), as in the 1959-1960 entry. Read the characters as the coefficients of a polynomial; a valid string leaves a fixed remainder modulo a generator of degree 6:

\[\mathrm{polymod}(\mathrm{expand}(hrp) \,\|\, data \,\|\, checksum) = 1 .\]

The code was searched for. Of 159,605 candidate generators, the one chosen detects every error in up to 4 characters, in strings of up to 89 characters. Base58Check’s hash only makes errors unlikely to pass.
One case makes addresses easier to read aloud and to fit in QR codes.
Errors can be located, though wallets are asked not to correct them: a corrected address may be a different, valid one.

Implementation: blockchainkit.wallets.systems.bech32.bech32_encode(), blockchainkit.wallets.systems.bech32.bech32_decode(), blockchainkit.wallets.systems.bech32.segwit_encode() and blockchainkit.wallets.systems.bech32.p2wpkh_address(), which pass BIP173’s test vectors: private key 1 gives bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4.

References: P. Wuille and G. Maxwell, BIP 173: Base32 address format for native v0-16 witness outputs (March 2017).

Bech32 addresses (BIP173, 2017)

2018 – Threshold ECDSA (Gennaro and Goldfeder)#

A multisig script, as in the 2012 entry, shows its policy on the chain and needs one signature per signer. A threshold signature is a single, ordinary signature under a single public key. It is made jointly by any \(t\) of \(n\) parties, each holding a Shamir share of a private key that nobody ever puts together.

For Schnorr signatures this is easy: responses add, so shares of the key give shares of the signature (MuSig, in Breakthroughs in Cryptography). Bitcoin and Ethereum use ECDSA, whose signature

\[s = k^{-1}(z + r x)\]

multiplies two secrets, the inverse of the nonce \(k\) and the key \(x\). Rosario Gennaro and Steven Goldfeder gave a fast protocol for that:

Each party holds a share \(k_i\) of the nonce and a random mask \(\gamma_i\).
A two-party multiplicative-to-additive (MtA) step turns a product of secrets held by two parties into a sum, \(\alpha + \beta = ab\), without revealing them.
With MtA the parties get shares of \(k\gamma\) and of \(kx\). Revealing \(k\gamma\) is safe, since \(\gamma\) hides \(k\), and it lets them compute \(R = k^{-1} G\).
Each party’s \(z k_i + r \sigma_i\) adds up to \(s = k(z + r x)\), an ECDSA signature with nonce \(k^{-1}\).

Exchanges and custody companies use threshold ECDSA so that no single server ever holds a whole key.

Implementation: blockchainkit.wallets.systems.threshold.threshold_keygen() (each party deals a Shamir sharing with Feldman commitments on secp256k1) and blockchainkit.wallets.systems.threshold.threshold_sign(), whose signatures verify with blockchainkit.wallets.systems.ecdsa.ecdsa_verify(). MtA is an ideal function (blockchainkit.wallets.systems.threshold.multiplicative_to_additive()), not Paillier encryption with range proofs, and nothing checks a cheating party.

References: R. Gennaro and S. Goldfeder, Fast multiparty threshold ECDSA with fast trustless setup, ACM CCS 2018, 1179–1194. DOI

Threshold ECDSA (Gennaro and Goldfeder, 2018)

2020 – Bech32m and a Checksum Flaw (BIP350)#

In 2019 a blind spot was found in Bech32. When a string ends in p, inserting or deleting q characters just before that p leaves the checksum valid.

The reason is algebraic:

q stands for the value 0, and p for 1.
The checksum asks that the remainder equal 1, the very value p adds.
Inserting zeros before the last value multiplies part of the polynomial by a power of \(x\) without changing the remainder.

Segregated-witness version 0 was safe by luck: its programs must be exactly 20 or 32 bytes, so an inserted character makes a wrong length. But Taproot, witness version 1, and later versions allow other lengths. Pieter Wuille’s Bech32m changes only the constant:

\[\mathrm{polymod}(\mathrm{expand}(hrp) \,\|\, data \,\|\, checksum) = \texttt{0x2bc830a3} .\]

With an irregular constant, appended zeros change the remainder. Bech32m is required from witness version 1 on, and Bech32 stays for version 0.

Implementation: the encoding argument of blockchainkit.wallets.systems.bech32.bech32_encode(), and blockchainkit.wallets.systems.bech32.segwit_decode(), which demands Bech32 for version 0 and Bech32m after, passing BIP350’s test vectors.

References: P. Wuille, BIP 350: Bech32m format for v1+ witness addresses (December 2020).

Bech32m and the insertion flaw in Bech32 (BIP350, 2020)

2021 – Account Abstraction (ERC-4337)#

Ethereum has two kinds of account:

an account controlled by a key pair can start transactions, but its rules are fixed: one ECDSA key, and fees paid in ether;
a contract account can follow any rule written in code, but cannot start a transaction.

So a social-recovery or multisig wallet needed a separate key-pair account to pay its fees. Changing the protocol to merge the two was proposed many times. ERC-4337, by Vitalik Buterin, Yoav Weiss and others, does it with contracts alone:

The owner signs a user operation, saying what the account should do, and sends it to a separate pool.
A bundler collects operations and submits them in one ordinary transaction to a single EntryPoint contract.
For each operation the EntryPoint asks the account’s own code to validate it, checking the signature and nonce by whatever rule the account chooses, and to pay its fee.
Then it runs each operation, and pays the fees to the bundler.

The owner signs a hash that names the EntryPoint and the chain,

\[h = \mathrm{SHA256}(\text{domain} \,\|\, \text{EntryPoint} \,\|\, \text{chain} \,\|\, \text{operation}),\]

so an operation cannot be replayed elsewhere. A failing validation would revert the whole bundle at the bundler’s cost, so bundlers simulate each operation first and drop the failures. Since validation is code, an account can rotate its key, batch payments, or plug in social recovery. The EntryPoint went live on Ethereum in March 2023.

Implementation: blockchainkit.wallets.systems.account_abstraction.EntryPoint, blockchainkit.wallets.systems.account_abstraction.SmartAccount (Schnorr-signed, with key rotation and batches) and blockchainkit.wallets.systems.account_abstraction.bundle(), which simulates on fork(). Fees are fixed amounts rather than gas times price, and there are no paymasters, aggregators or account factories.

References: V. Buterin, Y. Weiss, D. Tirosh, S. Nacson, A. Forshtat, K. Gazso and T. Hess, ERC-4337: Account Abstraction Using Alt Mempool, Ethereum Improvement Proposals (September 2021).

Account abstraction with ERC-4337 (2021)