sipa

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

# 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

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 = log₂(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

sipa

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)

sipa

Keybase proof

I hereby claim:

• I am sipa on github.
• I am pwuille (https://keybase.io/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

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

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

sipa

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

• 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 8.1.3.5.c.
• Older OpenSSL code only accepted length descriptors up to the size of a 'long int' (which is platform dependent),

sipa

Published as BIP 103