Skip to content

Instantly share code, notes, and snippets.

View markblundeberg's full-sized avatar

Mark B Lundeberg markblundeberg

  • Wet coast, Canada
View GitHub Profile
@markblundeberg
markblundeberg / schnorrblind.md
Last active November 28, 2020 01:30
Blind Schnorr signatures

Blind Schnorr signatures

Requester has a message-hash m that they want to be signed by pubkey P that is owned by Signer (who knows P = xG for private key x and generator G).

The following is a direct adaptation of Matthew Green's blind scheme adapted for the specific case of bip-schnorr elliptic curve signatures (including the sign-flip factor) and has been used in the wild (for internal protocol message signing, not for transaction signing) since late 2019 in the BCH CashFusion protocol.

Symbols:

  • R R' P G are elliptic curve points. Additive convention is used.
  • n is the curve order.
  • a b e e' i j k s s' x are integers mod n.
@markblundeberg
markblundeberg / devabc.md
Last active February 5, 2020 15:43
ABC dev notes

Basic building: first mkdir build-ninja in repo root, then run cmake -GNinja .. within the new directory, then ninja check-all.

Build with clang:

CC=clang CXX=clang++ cmake -GNinja ..

Build with debug:

CC=clang CXX=clang++ cmake -GNinja .. -DCMAKE_BUILD_TYPE=Debug
@markblundeberg
markblundeberg / tapbch.md
Last active August 18, 2021 21:08
How might Taproot be implemented in BCH, and do we need it?

Taproot is an interesting technology to enable multiparty privacy on a bitcoin. Currently, there is a problem with multiparty contracts in that they are obvious deviation from the most common script type (P2PKH), which hurts privacy. The script that gets used will typically indicate exactly what kind of protocol was at play. Also complex P2SH scripts take extra resources (transaction size and CPU cycles).

The basic idea with Taproot is that instead of P2SH where a script is committed by a hash, you can hide a script (or set of possible scripts) as a commitment within a normal-looking public key. Now there are two ways to spend from this public key:

  1. Create a normal transaction signature using the public key, or,
  2. Reveal the commitment, and provide parameters that satisfy the revealed script.

To do #1, it means you need to know the private key, or, you have a set of signers who are able to produce a signature (that's where Schnor

@markblundeberg
markblundeberg / transcript.txt
Created May 19, 2019 04:20
transcript from Schnorr multisig with checksum0 and Chris Pacia
(https://github.com/markblundeberg/schnorrfun)
********************
Schnorr multisigger!
********************
Warning: this is for DEMONSTRATION and does not necessarily use safe/secure
techniques. Beware, funds can be easily lost!
@markblundeberg
markblundeberg / golomb_part2.md
Created April 22, 2019 23:48
Progressive knockout block filters

Progressive knockout block filters

In my last gist, I described how the BIP158 block filters are technically not quite optimal, though in an inconsequential way since the false positive rate has been made so low.

In this document I'm going to describe how it's possible to significantly beat the bandwidth requirements of BIP158 while also achieving a lower overall false positive rate. The idea is to prepare multiple independent filters per block, each of which which has a higher false positive rate. Practically this can give roughly a factor of two improvement over BIP158, but at the cost of additional complexity.

The problem

The BIP158 false positive rate was chosen with a particular size of wallet in mind -- somewhere around 1000 items (addresses) to watch in each block. There is a trade off between the overall size of the filter (which must be do

@markblundeberg
markblundeberg / golomb_part1.md
Last active March 29, 2022 20:55
Further minimizing the redundancy in Neutrino filters (BIP158 / Golomb sets)

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 February 5, 2021 20:05
BCH floating transactions: SIGHASH_NOINPUT emulation using CHECKDATASIG covenants

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 December 13, 2019 22:39
BIP62 and Schnorr: a new era in BCH privacy and smart contracting

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 March 29, 2022 20:57
SCRIPT_VERIFY_MINIMALIF not needed: making unmalleable smart contracts in BCH

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 February 2, 2019 01:19
Alternative OP_CHECKMULTISIG mechanics for Schnorr

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