Skip to content

Instantly share code, notes, and snippets.

Mark B Lundeberg markblundeberg

  • Wet coast, Canada
View GitHub Profile
@markblundeberg
markblundeberg / golomb_part1.md
Last active Apr 19, 2019
Further minimizing the redundancy in Neutrino filters (BIP158 / Golomb sets)
View golomb_part1.md

Further minimizing the redundancy in Neutrino filters (BIP158 / Golomb sets)

Last year saw the introduction of BIP158 and Neutrino wallet which use Golomb-coded sets to very efficiently encode which items are in bitcoin blocks.

The basic idea in BIP158 is that we have N items of interest (such as distinct scriptPubKeys) in a block, which we hash to integers in the interval [0,F-1] for some range F that is much larger than N. These are basically short hashes, but with an uneven number of bits. This set of hashes can be queried to check whether a candidate scriptPubKey might be in a block, by computing the hash for the candidate and checking if that integer is in the set. The false positive rate is approximately N/F, and can be therefore tuned by making F larger or smaller.

Golomb-Rice comes into play by providing a very size-efficient way of encoding the list of hashes (by sorting them and encoding just the differences with an entropy-optimized code), which is important for minimizing over

@markblundeberg
markblundeberg / covenant_noinput.md
Last active Feb 9, 2019
BCH floating transactions: SIGHASH_NOINPUT emulation using CHECKDATASIG covenants
View covenant_noinput.md

BCH floating transactions: SIGHASH_NOINPUT emulation using CHECKDATASIG covenants

A new sighash flag has been proposed (originally for Lightning, now for Eltoo) which redacts information about the spending inputs, most notably their transaction IDs.

This facility is both powerful and dangerous: it means that signatures intended for one transaction can be used on other transactions. It also makes up a very strong increase in the malleability of transactions. SIGHASH_NOINPUT allows for much more flexible off-chain smart contracts than nonmalleable transactions. Note that Eltoo requires SIGHASH_NOINPUT, for instance. It's not clear whether such a dangerous feature will be adopted on BCH any time soon.

In this gist I'm going to explain that CHECKDATASIG covenants let us write smart contracts that emulate SIGHASH_NOINPUT. This capability alone should in principle allow to build Lightning, Eltoo with bilaterally funded smart contracts on BCH (though, with some significant

@markblundeberg
markblundeberg / bip62_and_schnorr.md
Last active Feb 17, 2019
BIP62 and Schnorr: a new era in BCH privacy and smart contracting
View bip62_and_schnorr.md

Two new features are coming to Bitcoin Cash soon, hopefully in the May 2019 upgrade. I'd like to take the time to explain why I'm so excited about them. In short, we will be able to do:

  • Payment channels hidden as ordinary payments.
  • Atomic swaps hidden as ordinary payments.
  • Lightning-style payment channel networks too, if we want.
  • Secure chains of unconfirmed transactions involving multiple parties (layer 2).

That all may sound incredible, and I'm going to explain in this document how it is so.

--- Mark B. Lundeberg, 2019 Jan 29 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

@markblundeberg
markblundeberg / minimalif_not_needed.md
Last active Jan 30, 2019
SCRIPT_VERIFY_MINIMALIF not needed: making unmalleable smart contracts in BCH
View minimalif_not_needed.md

It's quite common to see smart contract constructions like this:

OP_IF
    <clause 1 conditions>
    <pubkey1> OP_CHECKSIG
OP_ELSE
    <clause 2 conditions>
    <pubkey2> OP_CHECKSIG
OP_ENDIF
@markblundeberg
markblundeberg / alt_cms.md
Last active Feb 2, 2019
Alternative OP_CHECKMULTISIG mechanics for Schnorr
View alt_cms.md

Currently with OP_CHECKMULTISIG we have the following N-of-M mechanics (legacy mechanics), illustrated by a 2-of-3 example:

  • Locking script: OP_2 pubkey_alice pubkey_bob pubkey_carol OP_3 OP_CHECKMULTISIG
  • ScriptSig (N+1 pushes): OP_0 sig_alice sig_carol (OP_0 is the dummy element)

This is a rather bad mechanism, where sig_carol needs to be checked against both pubkey_bob and pubkey_carol. As discussed elsewhere, this is a disaster for Schnorr batch verification. So in the May 2019 upgrade, we're going to make it so that the signatures sig_alice and sig_carol are not allowed to be Schnorr signatures. I mean, we could allow them to be Schnorr and just use single-checking, but we have better plans in mind...

Schnorr signature aggregates (with OP_CHECKSIG) are really cool but they aren't a replacement for OP_CHECKMULTISIG. So, we need a new way that at least allows for batch verification.

Our goal is to make it so that all UTXOs can be spent with Schnorr, and that includes multisigs. It is unthi

@markblundeberg
markblundeberg / notification.md
Last active Jan 7, 2019
BCH 24-bit public notification addresses
View notification.md

This is a brief specification proposing the use of short anyone-can-spend P2SH addresses. This protocol is already in use with BCHMessage as used in OpenSwap, for the 'public bulletin boards' feature, but may be of use in other protocols.

Rationale

Various protocols like on-chain messaging, payment codes, and so on need SPV-wallet-friendly notifications.

  • In BIP47, notifications are sent to an address owned by the recipient, which means that notifications create UTXO dust. If the UTXO dust is cleaned up, this causes a privacy concern as its destination can be traced. If not cleaned, then the UTXO set will grow and grow over time. BIP47 v2 tried to solve this by using a 1-of-2 multisig so that the sender can also clean up the dust, however this creates SPV unfriendliness for the recipient.
  • In stealth addresses, payments are tagged with an OP_RETURN including a few-byte prefix that can be use
@markblundeberg
markblundeberg / quadsig.md
Last active Oct 22, 2018
Quadratic sighash based on scriptCode
View quadsig.md

Quadratic sighash remains in BCH/Segwit digest algorithms.

Mark Lundeberg 2018 Oct 17

Abstract: Both BCH post-forkday signatures and the BIP143 Segwit signatures are ostensibly designed to remove the 'quadratic hashing problem', however as I will show, they are still vulnerable for long scripts. Back-of-the-envelope calculations show that it will become a serious concern if the existing script limits are relaxed.

Facts

  • Every OP_CHECKSIG requires hashing a potentially large amount of data, limited only by the size of scriptCode. The precise length is 159 + len(scriptCode) for scriptCodes longer than 255 bytes.
  • Since many OP_CHECKSIG calls are possible within a given script, this means transactions can be made where the required hashing time is quadratic in the length of script. (though, see the non-push opcode limit below)
@markblundeberg
markblundeberg / P2I.md
Created Sep 6, 2018
"Pay To Identity" — a proposed use of OP_CHECKDATASIG
View P2I.md

"Pay To Identity" — a proposed use of OP_CHECKDATASIG

Dr. Mark B. Lundeberg, 2018 September 6 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

A mechanism where a Bitcoin Cash payment is made to a personally identifying string (real name, email address, social media handle, etc.) instead of directly to a cryptographic key. The payment can only be claimed by the recipient if they generate a public key and get it certified by a trusted identity verifier. This certification signature is confirmed in script via the new opcode OP_CHECKDATASIG.

Characteristics:

  • Pay anyone, right now -- recipient doesn't need to have any cryptographic keys nor do they even need a phone/computer. (They only need these to claim the funds later.)
@markblundeberg
markblundeberg / pgp-checkdatasig.md
Created Aug 31, 2018
Using PGP signatures with bitcoin script OP_CHECKDATASIG
View pgp-checkdatasig.md

Using PGP signatures with bitcoin script OP_CHECKDATASIG

Dr. Mark B. Lundeberg, 2018 August 30 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

Since version 2.1, GnuPG is able to use the very same secp256k1 elliptic curve signature algorithm (ECDSA) as used in bitcoin. Quite soon Bitcoin Cash will add a new script opcode OP_CHECKDATASIG that is able to check signatures not just on the containing transaction, but also on arbitrary data. For fun, let's try to intersect the two signature systems and see what can be done!

Background

OP_CHECKDATASIG signatures

@markblundeberg
markblundeberg / hidden-atomic-swaps.md
Last active Feb 18, 2019
SwapChannels: hide your atomic swaps using ordinary payment channels
View hidden-atomic-swaps.md
You can’t perform that action at this time.