Skip to content

Instantly share code, notes, and snippets.

sipa /
Created Aug 24, 2019
asmap build script
import sys
import re
import ipaddress
# This program loads AS mapping entries from stdin in the form "[IP]/[bits] AS[num]", where IP is an IPv4
# or IPv6 address, bits is an integer between 0 and 32 (for IPv4) or 128 (for IPv6), and num is an integer
# between 1 and 16777215.
def Parse(entries):
for line in sys.stdin:
sipa /
Last active Jun 13, 2018
Base32 distance=15 degree=27 length=1023 BCH code (corrects 7 errors)
# Basic encoding/decoding
def polymod(values):
chk = 1
for value in values:
top = chk >> 130
chk = (chk ^ top << 130) << 5 ^ value
chk ^= 0x48ad7da5f5dffe2565cb2f7406b4a2bcbc if ((top >> 0) & 1) else 0
chk ^= 0x55af243bb2f7943c3d4da6d046345795d if ((top >> 1) & 1) else 0
chk ^= 0xa91cc8534da778785f9247a01ceda669f if ((top >> 2) & 1) else 0
sipa /
Last active Feb 26, 2021
Minimizing the redundancy in Golomb Codes Sets

Minimizing the redundancy in Golomb Coded Sets

A Golomb Coded Set (GCS) is a set of N distinct integers within the range [0..MN-1], whose order does not matter, and stored by applying a Golomb-Rice coder with parameter B to the differences between subsequent elements after sorting. When the integers are hashes of elements from a set, this is an efficient encoding of a probabilistic data structure with false positive rate 1/M. It is asymptotically 1 / log(2) (around 1.44) times more compact than Bloom filters, but harder to update or query.

The question we try to answer in this document is what combinations of B and M minimize the resulting size of the filter, and find that the common suggestion B = log2(M) is not optimal.

Size of a Golomb Coded Set

To determine the size of a Golomb coding of a set, we model the differences between subsequent elements after sorting as a geometric distribution with p = 1 / M. This is a good approximation if the size of the set is large enou

View coin_tosses
1 state:
Output rate: 0.25
N0 (pos 0)
S0: 0=S1 1=S2 [0.5]
S1: 0=S0 1=0,S0 [0.25]
S2: 0=1,S0 1=S0 [0.25]
2 states:
Output rate: 0.375
N0 (pos 0)

Keybase proof

I hereby claim:

  • I am sipa on github.
  • I am pwuille ( on keybase.
  • I have a public key whose fingerprint is 133E AC17 9436 F14A 5CF1 B794 860F EB80 4E66 9320

To claim this, I am signing this object:

sipa /
Last active Apr 30, 2021
Covert ECDH over secp256k1

Covert ECDH over secp256k1

If ECDH is used to establish a shared session secret for an encrypted connection, two elliptic curve points need to be transmitted (one in each direction) before encryption starts. In order to avoid being identifiable as a (specific) ECDH negotiation, ideally those two points are sent in a way that is indistinguishable from random.

This problem is easily addressed by using curves that support Elligator-style encodings: functions that encode a (subset of) elliptic curve points as sequences of bytes with no observable bias: (almost) every byte sequence corresponds to exactly one point, and the others correspond to none.

Unfortunately, no Elligator-style encoding is known for secp256k1.

sipa / bech32_analysis.txt
Created Dec 19, 2017
Bech32 error detection analysis
View bech32_analysis.txt
Chances of not detecting an error in a Bech32 string. Lengths exclude the separator character '1'. Chances are multiples of 1 in 2^30.
Len 1 Error 2 Errors 3 Errors 4 Errors 5 Errors 6 Errors 7 Errors 8 Errors
1 0.000000000000000
2 0.000000000000000 0.000000000000000
3 0.000000000000000 0.000000000000000 0.000000000000000
4 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000
5 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000
6 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000
7 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 1.209844924575586

I'll first give some thoughts on the design of the wallet in general, before explaining current and future SegWit wallet support.

Current design

Conceptually, a wallet currently contains mapKeys, mapScripts, and setWatchOnly, which together determine which outputs are considered "ours" (IsMine), and how to solve and sign for them. Then the wallet further contains key metadata, key chains, and key pool at the wallet level that feed into this.

We determine whether outputs are ours using ad-hoc logic that mostly answers the question "Could we sign this?", but with some notable exceptions:

sipa /
Last active Oct 13, 2015
Differences between OpenSSL's ASN.1 parser and BER
  • Zero-length integers are accepted (with value 0), 8.3.1 says this is not allowed.
  • Expected-to-be-unsigned integers are parsed as if they weren't two's complement, violating 8.3.3.
  • Integers with excessive padding are accepted, violating 8.3.2.
  • Primitive values with indefinite length are accepted, when they are inside a constructed value with known length, violating 8.3.2.a. End-of-contents octets are not supported in this case, violating 8.1.5.
  • Lengths of constructed values are ignored in several cases.
  • Garbage inside sequences is accepted.
  • Garbage at the end is accepted.
  • Data types that are required to be primitive can be encoded as constructed instead, in which case the concatenation of all primitive values inside is used (ignoring their data types), violating for example 8.3.1.
  • 127-byte long length descriptors are accepted (ASN.1 allows up to 126 bytes), violating
  • Older OpenSSL code only accepted length descriptors up to the size of a 'long int' (which is platform dependent),
sipa / blocksize.mediawiki
Last active Apr 20, 2021
Block size according to technological growth.
View blocksize.mediawiki

Published as BIP 103