search

sipa / miniscript

Miniscript site and implementation
157 stars 47 forks source link

Add type-driven fuzzer #105

Closed sipa closed 2 years ago

sipa commented 2 years ago

Builds on top of #104.

This adds a second random node fuzzer, which uses type requirements to more efficiently explore the space of valid miniscripts. The other one is kept, as it is less complicated and thus easier to make sure it doesn't miss anything.

darosior commented 2 years ago

I added a commit to https://github.com/darosior/bitcoin/tree/miniscript_pr_105 which aims to cover more properties (o, n and z) for subs of and_v, and_b, or_b, andor and thresh.

sipa commented 2 years ago

@darosior I've been working on a generalization of the approach you're using here, to build a full table of the form "type X can be constructed using any recipe of the form "fragment Y with subtypes Z1/Z2/Z3/...", for all possible types X, automatically using the existing ComputeType rules. These are the rules I'm inferring; can you see anything obviously missing?

thresh rules are only included for 3 children, but that's sufficient to write manual logic for the more general case.

B: 0()
B: 1()
B: older()
B: after()
B: sha256()
B: hash256()
B: ripemd160()
B: hash160()
B: c:(Ku)
B: d:(Vz)
B: j:(Bn)
B: n:(B)
B: and_v(V,B)
B: and_b(B,W)
B: or_b(Bd,Wd)
B: or_d(Bdu,B)
B: or_i(B,B)
B: andor(Bdu,B,B)
B: thresh(Bdu,Wdu,Wdu)
B: multi()
V: v:(B)
V: and_v(V,V)
V: or_c(Bdu,V)
V: or_i(V,V)
V: andor(Bdu,V,V)
W: a:(B)
W: s:(Bo)
Bz: 0()
Bz: 1()
Bz: older()
Bz: after()
Bz: n:(Bz)
Bz: and_v(Vz,Bz)
Bz: and_b(Bz,Wz)
Bz: or_b(Bzd,Wzd)
Bz: or_d(Bzdu,Bz)
Bz: andor(Bzdu,Bz,Bz)
Bz: thresh(Bzdu,Wzdu,Wzdu)
Vz: v:(Bz)
Vz: and_v(Vz,Vz)
Vz: or_c(Bzdu,Vz)
Vz: andor(Bzdu,Vz,Vz)
Bo: sha256()
Bo: hash256()
Bo: ripemd160()
Bo: hash160()
Bo: c:(Kou)
Bo: d:(Vz)
Bo: j:(Bon)
Bo: n:(Bo)
Bo: and_v(Vz,Bo)
Bo: and_v(Vo,Bz)
Bo: and_b(Bz,Wo)
Bo: and_b(Bo,Wz)
Bo: or_b(Bzd,Wod)
Bo: or_b(Bod,Wzd)
Bo: or_d(Bodu,Bz)
Bo: or_i(Bz,Bz)
Bo: andor(Bzdu,Bo,Bo)
Bo: andor(Bodu,Bz,Bz)
Bo: thresh(Bzdu,Wzdu,Wodu)
Bo: thresh(Bzdu,Wodu,Wzdu)
Bo: thresh(Bodu,Wzdu,Wzdu)
Vo: v:(Bo)
Vo: and_v(Vz,Vo)
Vo: and_v(Vo,Vz)
Vo: or_c(Bodu,Vz)
Vo: or_i(Vz,Vz)
Vo: andor(Bzdu,Vo,Vo)
Vo: andor(Bodu,Vz,Vz)
Bn: sha256()
Bn: hash256()
Bn: ripemd160()
Bn: hash160()
Bn: c:(Knu)
Bn: d:(Vz)
Bn: j:(Bn)
Bn: n:(Bn)
Bn: and_v(Vz,Bn)
Bn: and_v(Vn,B)
Bn: and_b(Bn,W)
Bn: multi()
Vn: v:(Bn)
Vn: and_v(Vz,Vn)
Vn: and_v(Vn,V)
Bon: sha256()
Bon: hash256()
Bon: ripemd160()
Bon: hash160()
Bon: c:(Konu)
Bon: d:(Vz)
Bon: j:(Bon)
Bon: n:(Bon)
Bon: and_v(Vz,Bon)
Bon: and_v(Von,Bz)
Bon: and_b(Bon,Wz)
Von: v:(Bon)
Von: and_v(Vz,Von)
Von: and_v(Von,Vz)
Bd: 0()
Bd: sha256()
Bd: hash256()
Bd: ripemd160()
Bd: hash160()
Bd: c:(Kdu)
Bd: d:(Vz)
Bd: j:(Bn)
Bd: n:(Bd)
Bd: and_b(Bd,Wd)
Bd: or_b(Bd,Wd)
Bd: or_d(Bdu,Bd)
Bd: or_i(B,Bd)
Bd: or_i(Bd,B)
Bd: andor(Bdu,B,Bd)
Bd: thresh(Bdu,Wdu,Wdu)
Bd: multi()
Wd: a:(Bd)
Wd: s:(Bod)
Bzd: 0()
Bzd: n:(Bzd)
Bzd: and_b(Bzd,Wzd)
Bzd: or_b(Bzd,Wzd)
Bzd: or_d(Bzdu,Bzd)
Bzd: andor(Bzdu,Bz,Bzd)
Bzd: thresh(Bzdu,Wzdu,Wzdu)
Bod: sha256()
Bod: hash256()
Bod: ripemd160()
Bod: hash160()
Bod: c:(Kodu)
Bod: d:(Vz)
Bod: j:(Bon)
Bod: n:(Bod)
Bod: and_b(Bzd,Wod)
Bod: and_b(Bod,Wzd)
Bod: or_b(Bzd,Wod)
Bod: or_b(Bod,Wzd)
Bod: or_d(Bodu,Bzd)
Bod: or_i(Bz,Bzd)
Bod: or_i(Bzd,Bz)
Bod: andor(Bzdu,Bo,Bod)
Bod: andor(Bodu,Bz,Bzd)
Bod: thresh(Bzdu,Wzdu,Wodu)
Bod: thresh(Bzdu,Wodu,Wzdu)
Bod: thresh(Bodu,Wzdu,Wzdu)
Bnd: sha256()
Bnd: hash256()
Bnd: ripemd160()
Bnd: hash160()
Bnd: c:(Kndu)
Bnd: d:(Vz)
Bnd: j:(Bn)
Bnd: n:(Bnd)
Bnd: and_b(Bnd,Wd)
Bnd: multi()
Bond: sha256()
Bond: hash256()
Bond: ripemd160()
Bond: hash160()
Bond: c:(Kondu)
Bond: d:(Vz)
Bond: j:(Bon)
Bond: n:(Bond)
Bond: and_b(Bond,Wzd)
Bu: 0()
Bu: 1()
Bu: sha256()
Bu: hash256()
Bu: ripemd160()
Bu: hash160()
Bu: c:(Ku)
Bu: d:(Vz)
Bu: j:(Bnu)
Bu: n:(B)
Bu: and_v(V,Bu)
Bu: and_b(B,W)
Bu: or_b(Bd,Wd)
Bu: or_d(Bdu,Bu)
Bu: or_i(Bu,Bu)
Bu: andor(Bdu,Bu,Bu)
Bu: thresh(Bdu,Wdu,Wdu)
Bu: multi()
Ku: pk_k()
Ku: pk_h()
Ku: and_v(V,Ku)
Ku: or_i(Ku,Ku)
Ku: andor(Bdu,Ku,Ku)
Wu: a:(Bu)
Wu: s:(Bou)
Bzu: 0()
Bzu: 1()
Bzu: n:(Bz)
Bzu: and_v(Vz,Bzu)
Bzu: and_b(Bz,Wz)
Bzu: or_b(Bzd,Wzd)
Bzu: or_d(Bzdu,Bzu)
Bzu: andor(Bzdu,Bzu,Bzu)
Bzu: thresh(Bzdu,Wzdu,Wzdu)
Kzu: and_v(Vz,Kzu)
Kzu: andor(Bzdu,Kzu,Kzu)
Bou: sha256()
Bou: hash256()
Bou: ripemd160()
Bou: hash160()
Bou: c:(Kou)
Bou: d:(Vz)
Bou: j:(Bonu)
Bou: n:(Bo)
Bou: and_v(Vz,Bou)
Bou: and_v(Vo,Bzu)
Bou: and_b(Bz,Wo)
Bou: and_b(Bo,Wz)
Bou: or_b(Bzd,Wod)
Bou: or_b(Bod,Wzd)
Bou: or_d(Bodu,Bzu)
Bou: or_i(Bzu,Bzu)
Bou: andor(Bzdu,Bou,Bou)
Bou: andor(Bodu,Bzu,Bzu)
Bou: thresh(Bzdu,Wzdu,Wodu)
Bou: thresh(Bzdu,Wodu,Wzdu)
Bou: thresh(Bodu,Wzdu,Wzdu)
Kou: pk_k()
Kou: and_v(Vz,Kou)
Kou: and_v(Vo,Kzu)
Kou: or_i(Kzu,Kzu)
Kou: andor(Bzdu,Kou,Kou)
Kou: andor(Bodu,Kzu,Kzu)
Bnu: sha256()
Bnu: hash256()
Bnu: ripemd160()
Bnu: hash160()
Bnu: c:(Knu)
Bnu: d:(Vz)
Bnu: j:(Bnu)
Bnu: n:(Bn)
Bnu: and_v(Vz,Bnu)
Bnu: and_v(Vn,Bu)
Bnu: and_b(Bn,W)
Bnu: multi()
Knu: pk_k()
Knu: pk_h()
Knu: and_v(Vz,Knu)
Knu: and_v(Vn,Ku)
Bonu: sha256()
Bonu: hash256()
Bonu: ripemd160()
Bonu: hash160()
Bonu: c:(Konu)
Bonu: d:(Vz)
Bonu: j:(Bonu)
Bonu: n:(Bon)
Bonu: and_v(Vz,Bonu)
Bonu: and_v(Von,Bzu)
Bonu: and_b(Bon,Wz)
Konu: pk_k()
Konu: and_v(Vz,Konu)
Konu: and_v(Von,Kzu)
Bdu: 0()
Bdu: sha256()
Bdu: hash256()
Bdu: ripemd160()
Bdu: hash160()
Bdu: c:(Kdu)
Bdu: d:(Vz)
Bdu: j:(Bnu)
Bdu: n:(Bd)
Bdu: and_b(Bd,Wd)
Bdu: or_b(Bd,Wd)
Bdu: or_d(Bdu,Bdu)
Bdu: or_i(Bu,Bdu)
Bdu: or_i(Bdu,Bu)
Bdu: andor(Bdu,Bu,Bdu)
Bdu: thresh(Bdu,Wdu,Wdu)
Bdu: multi()
Kdu: pk_k()
Kdu: pk_h()
Kdu: or_i(Ku,Kdu)
Kdu: or_i(Kdu,Ku)
Kdu: andor(Bdu,Ku,Kdu)
Wdu: a:(Bdu)
Wdu: s:(Bodu)
Bzdu: 0()
Bzdu: n:(Bzd)
Bzdu: and_b(Bzd,Wzd)
Bzdu: or_b(Bzd,Wzd)
Bzdu: or_d(Bzdu,Bzdu)
Bzdu: andor(Bzdu,Bzu,Bzdu)
Bzdu: thresh(Bzdu,Wzdu,Wzdu)
Kzdu: andor(Bzdu,Kzu,Kzdu)
Bodu: sha256()
Bodu: hash256()
Bodu: ripemd160()
Bodu: hash160()
Bodu: c:(Kodu)
Bodu: d:(Vz)
Bodu: j:(Bonu)
Bodu: n:(Bod)
Bodu: and_b(Bzd,Wod)
Bodu: and_b(Bod,Wzd)
Bodu: or_b(Bzd,Wod)
Bodu: or_b(Bod,Wzd)
Bodu: or_d(Bodu,Bzdu)
Bodu: or_i(Bzu,Bzdu)
Bodu: or_i(Bzdu,Bzu)
Bodu: andor(Bzdu,Bou,Bodu)
Bodu: andor(Bodu,Bzu,Bzdu)
Bodu: thresh(Bzdu,Wzdu,Wodu)
Bodu: thresh(Bzdu,Wodu,Wzdu)
Bodu: thresh(Bodu,Wzdu,Wzdu)
Kodu: pk_k()
Kodu: or_i(Kzu,Kzdu)
Kodu: or_i(Kzdu,Kzu)
Kodu: andor(Bzdu,Kou,Kodu)
Kodu: andor(Bodu,Kzu,Kzdu)
Bndu: sha256()
Bndu: hash256()
Bndu: ripemd160()
Bndu: hash160()
Bndu: c:(Kndu)
Bndu: d:(Vz)
Bndu: j:(Bnu)
Bndu: n:(Bnd)
Bndu: and_b(Bnd,Wd)
Bndu: multi()
Kndu: pk_k()
Kndu: pk_h()
Bondu: sha256()
Bondu: hash256()
Bondu: ripemd160()
Bondu: hash160()
Bondu: c:(Kondu)
Bondu: d:(Vz)
Bondu: j:(Bonu)
Bondu: n:(Bond)
Bondu: and_b(Bond,Wzd)
Kondu: pk_k()
sipa commented 2 years ago

Interesting observation: many of these rules are bad; e.g. Bzdu may seem like it can be constructed using thresh, but that'd require (for thresh with more than 1 child) a Wzdu type, which has no rules for constructing it. This could be used to prune the list of rules.

sipa commented 2 years ago

Here is the pruned list of rules (removing all rules which require a subnode of type that is non-constructible, and removing all rules that contruct a type that is never needed in order to produce a B/V/K/W):

B: 0()
B: 1()
B: older()
B: after()
B: sha256()
B: hash256()
B: ripemd160()
B: hash160()
B: c:(K)
B: d:(Vz)
B: j:(Bn)
B: n:(B)
B: and_v(V,B)
B: and_b(B,W)
B: or_b(Bd,Wd)
B: or_d(Bdu,B)
B: or_i(B,B)
B: andor(Bdu,B,B)
B: thresh(Bdu)
B: thresh(Bdu,Wdu)
B: thresh(Bdu,Wdu,Wdu)
B: multi()

V: v:(B)
V: and_v(V,V)
V: or_c(Bdu,V)
V: or_i(V,V)
V: andor(Bdu,V,V)

K: pk_k()
K: pk_h()
K: and_v(V,K)
K: or_i(K,K)
K: andor(Bdu,K,K)

W: a:(B)
W: s:(Bo)

Bz: 0()
Bz: 1()
Bz: older()
Bz: after()
Bz: n:(Bz)
Bz: and_v(Vz,Bz)
Bz: or_d(Bzdu,Bz)
Bz: andor(Bzdu,Bz,Bz)
Bz: thresh(Bzdu)

Vz: v:(Bz)
Vz: and_v(Vz,Vz)
Vz: or_c(Bzdu,Vz)
Vz: andor(Bzdu,Vz,Vz)

Bo: sha256()
Bo: hash256()
Bo: ripemd160()
Bo: hash160()
Bo: c:(Ko)
Bo: d:(Vz)
Bo: j:(Bon)
Bo: n:(Bo)
Bo: and_v(Vz,Bo)
Bo: and_v(Vo,Bz)
Bo: or_d(Bodu,Bz)
Bo: or_i(Bz,Bz)
Bo: andor(Bzdu,Bo,Bo)
Bo: andor(Bodu,Bz,Bz)
Bo: thresh(Bodu)

Vo: v:(Bo)
Vo: and_v(Vz,Vo)
Vo: and_v(Vo,Vz)
Vo: or_c(Bodu,Vz)
Vo: or_i(Vz,Vz)
Vo: andor(Bzdu,Vo,Vo)
Vo: andor(Bodu,Vz,Vz)

Ko: pk_k()
Ko: and_v(Vz,Ko)
Ko: andor(Bzdu,Ko,Ko)

Bn: sha256()
Bn: hash256()
Bn: ripemd160()
Bn: hash160()
Bn: c:(Kn)
Bn: d:(Vz)
Bn: j:(Bn)
Bn: n:(Bn)
Bn: and_v(Vz,Bn)
Bn: and_v(Vn,B)
Bn: and_b(Bn,W)
Bn: multi()

Vn: v:(Bn)
Vn: and_v(Vz,Vn)
Vn: and_v(Vn,V)

Kn: pk_k()
Kn: pk_h()
Kn: and_v(Vz,Kn)
Kn: and_v(Vn,K)

Bon: sha256()
Bon: hash256()
Bon: ripemd160()
Bon: hash160()
Bon: c:(Kon)
Bon: d:(Vz)
Bon: j:(Bon)
Bon: n:(Bon)
Bon: and_v(Vz,Bon)
Bon: and_v(Von,Bz)

Von: v:(Bon)
Von: and_v(Vz,Von)
Von: and_v(Von,Vz)

Kon: pk_k()
Kon: and_v(Vz,Kon)

Bd: 0()
Bd: sha256()
Bd: hash256()
Bd: ripemd160()
Bd: hash160()
Bd: c:(Kd)
Bd: d:(Vz)
Bd: j:(Bn)
Bd: n:(Bd)
Bd: and_b(Bd,Wd)
Bd: or_b(Bd,Wd)
Bd: or_d(Bdu,Bd)
Bd: or_i(B,Bd)
Bd: or_i(Bd,B)
Bd: andor(Bdu,B,Bd)
Bd: thresh(Bdu)
Bd: thresh(Bdu,Wdu)
Bd: thresh(Bdu,Wdu,Wdu)
Bd: multi()

Kd: pk_k()
Kd: pk_h()
Kd: or_i(K,Kd)
Kd: or_i(Kd,K)
Kd: andor(Bdu,K,Kd)

Wd: a:(Bd)
Wd: s:(Bod)

Bzd: 0()
Bzd: n:(Bzd)
Bzd: or_d(Bzdu,Bzd)
Bzd: andor(Bzdu,Bz,Bzd)
Bzd: thresh(Bzdu)

Bod: sha256()
Bod: hash256()
Bod: ripemd160()
Bod: hash160()
Bod: c:(Kod)
Bod: d:(Vz)
Bod: j:(Bon)
Bod: n:(Bod)
Bod: or_d(Bodu,Bzd)
Bod: or_i(Bz,Bzd)
Bod: or_i(Bzd,Bz)
Bod: andor(Bzdu,Bo,Bod)
Bod: andor(Bodu,Bz,Bzd)
Bod: thresh(Bodu)

Kod: pk_k()
Kod: andor(Bzdu,Ko,Kod)

Bu: 0()
Bu: 1()
Bu: sha256()
Bu: hash256()
Bu: ripemd160()
Bu: hash160()
Bu: c:(K)
Bu: d:(Vz)
Bu: j:(Bnu)
Bu: n:(B)
Bu: and_v(V,Bu)
Bu: and_b(B,W)
Bu: or_b(Bd,Wd)
Bu: or_d(Bdu,Bu)
Bu: or_i(Bu,Bu)
Bu: andor(Bdu,Bu,Bu)
Bu: thresh(Bdu)
Bu: thresh(Bdu,Wdu)
Bu: thresh(Bdu,Wdu,Wdu)
Bu: multi()

Bzu: 0()
Bzu: 1()
Bzu: n:(Bz)
Bzu: and_v(Vz,Bzu)
Bzu: or_d(Bzdu,Bzu)
Bzu: andor(Bzdu,Bzu,Bzu)
Bzu: thresh(Bzdu)

Bou: sha256()
Bou: hash256()
Bou: ripemd160()
Bou: hash160()
Bou: c:(Ko)
Bou: d:(Vz)
Bou: j:(Bonu)
Bou: n:(Bo)
Bou: and_v(Vz,Bou)
Bou: and_v(Vo,Bzu)
Bou: or_d(Bodu,Bzu)
Bou: or_i(Bzu,Bzu)
Bou: andor(Bzdu,Bou,Bou)
Bou: andor(Bodu,Bzu,Bzu)
Bou: thresh(Bodu)

Bnu: sha256()
Bnu: hash256()
Bnu: ripemd160()
Bnu: hash160()
Bnu: c:(Kn)
Bnu: d:(Vz)
Bnu: j:(Bnu)
Bnu: n:(Bn)
Bnu: and_v(Vz,Bnu)
Bnu: and_v(Vn,Bu)
Bnu: and_b(Bn,W)
Bnu: multi()

Bonu: sha256()
Bonu: hash256()
Bonu: ripemd160()
Bonu: hash160()
Bonu: c:(Kon)
Bonu: d:(Vz)
Bonu: j:(Bonu)
Bonu: n:(Bon)
Bonu: and_v(Vz,Bonu)
Bonu: and_v(Von,Bzu)

Bdu: 0()
Bdu: sha256()
Bdu: hash256()
Bdu: ripemd160()
Bdu: hash160()
Bdu: c:(Kd)
Bdu: d:(Vz)
Bdu: j:(Bnu)
Bdu: n:(Bd)
Bdu: and_b(Bd,Wd)
Bdu: or_b(Bd,Wd)
Bdu: or_d(Bdu,Bdu)
Bdu: or_i(Bu,Bdu)
Bdu: or_i(Bdu,Bu)
Bdu: andor(Bdu,Bu,Bdu)
Bdu: thresh(Bdu)
Bdu: thresh(Bdu,Wdu)
Bdu: thresh(Bdu,Wdu,Wdu)
Bdu: multi()

Wdu: a:(Bdu)
Wdu: s:(Bodu)

Bzdu: 0()
Bzdu: n:(Bzd)
Bzdu: or_d(Bzdu,Bzdu)
Bzdu: andor(Bzdu,Bzu,Bzdu)
Bzdu: thresh(Bzdu)

Bodu: sha256()
Bodu: hash256()
Bodu: ripemd160()
Bodu: hash160()
Bodu: c:(Kod)
Bodu: d:(Vz)
Bodu: j:(Bonu)
Bodu: n:(Bod)
Bodu: or_d(Bodu,Bzdu)
Bodu: or_i(Bzu,Bzdu)
Bodu: or_i(Bzdu,Bzu)
Bodu: andor(Bzdu,Bou,Bodu)
Bodu: andor(Bodu,Bzu,Bzdu)
Bodu: thresh(Bodu)
sipa commented 2 years ago

Rebased on top of #104, and switched to an approach inspired by @darosior's mentioned above. The code now infers now automatically (based on the ComputeType behavior) rules for which fragments/subtypes to use for constructing any desired type. This should result in constructing type-valid miniscript nodes for 100% of all fuzzer iterations.

sipa commented 2 years ago

Rebased.

darosior commented 2 years ago

I plan to get to this soon. ------- Original Message ------- Le mardi 5 avril 2022 à 4:47 PM, Pieter Wuille @.***> a écrit :

Rebased.

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

darosior commented 2 years ago

I think you are missing Bdn, Bdnu and Bdnou in the curated list. For those i have:

Bdn: <all hashes>, multi, c:K, d:Vz, j:Bn, n:Bdn, and_b(Bdn, Wd)
Bdno: <all hashes>, c:pk_k, d:Vz, j:Bno, n:Bdno
Bdnou: <all hashes>, c:pk_k, d:Vz, j:Bnou, n:Bdno

I manually reconstructed the list of constructed type in the same fashion from my (incorrect btw) mapping in https://github.com/darosior/bitcoin/tree/miniscript_pr_105. I did not find any other missing instance, and all the "recipes" from your curated list are comprehensive as far as my own list goes.

sipa commented 2 years ago

@darosior Nothing in my list needs Bdn, Bdno, or Bdnou. Do you have any?

darosior commented 2 years ago

Oh, right. No, i don't. But we should fuzz them too as they are possibly-top-level fragment that could be used?

sipa commented 2 years ago

@darosior That's unnecessary - they can all be constructed using just the B rule. These rules' types aren't the exact type of what is constructed, just "if you need something that at least has type properties Bndu, here is how that can be done". And it appears that such a rule would just never be invoked by the fuzzer.

To be clear, the fuzzer aims to produce either a B, a V, a K, or a W. That together covers every potentially type-valid miniscript expression. It's just that the rules for producing those may require more specific types, and those are the ones listed here.

sipa commented 2 years ago

@darosior I think the cause of the gaps may be a bug I just found: the order of the types in the recipe is used in reverse order when constructing miniscript objects - which often results in not obtaining the desired type at all. Fixing.

darosior commented 2 years ago

Arf, i hadn't looked for that.. Will give the new coverage when you push the fix.

-------- Original Message -------- On Apr 13, 2022, 7:45 PM, Pieter Wuille wrote:

@.***(https://github.com/darosior) I think the cause of the gaps may be a bug I just found: the order of the types in the recipe is used in reverse order when constructing miniscript objects - which often results in not obtaining the desired type at all. Fixing.

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

sipa commented 2 years ago

Pushed a new version. Changes:

sipa commented 2 years ago

Diff:

diff --git a/bitcoin/test/fuzz/miniscript_random.cpp b/bitcoin/test/fuzz/miniscript_random.cpp
index 6005391..f6115d4 100644
--- a/bitcoin/test/fuzz/miniscript_random.cpp
+++ b/bitcoin/test/fuzz/miniscript_random.cpp
@@ -313,7 +313,10 @@ std::optional<NodeInfo> ConsumeNodeStable(FuzzedDataProvider& provider) {

 /* This structure contains a table which for each "target" Type a list of recipes
  * to construct it, automatically inferred from the behavior of ComputeType.
- *  Each recipe is a Fragment together with a list of required types for its subnodes.
+ * Note that the Types here are not the final types of the constructed Nodes, but
+ * just the subset that are required. For example, a recipe for the "Bo" type
+ * might construct a "Bondu" sha256() NodeInfo, but cannot construct a "Bz" older().
+ * Each recipe is a Fragment together with a list of required types for its subnodes.
  */
 struct SmartInfo
 {
@@ -322,7 +325,7 @@ struct SmartInfo

     SmartInfo()
     {
-        /* Construct a set of interesting types to reason with (sections of BKVWzondu). */
+        /* Construct a set of interesting type requirements to reason with (sections of BKVWzondu). */
         std::vector<Type> types;
         for (int base = 0; base < 4; ++base) { /* select from B,K,V,W */
             Type type_base = base == 0 ? "B"_mst : base == 1 ? "K"_mst : base == 2 ? "V"_mst : "W"_mst;
@@ -346,17 +349,12 @@ struct SmartInfo
             }
         }

-        /* Sort the types. That has the effect that if type A is a subtype of type B,
-         * type B will always be ordered before type A. As we'll be constructing recipes
-         * using these types, in order, in what follows, more general recipes will
-         * be constructed before more specific ones, and we can avoid the need to
-         * retroactive delete earlier more specific recipes when more general ones
-         * are added. */
-        std::sort(types.begin(), types.end());
-
-        /** Helper function to determine whether a recipe a is a superset of recipe b
-         *  (i.e., same fragment type, but the same or weaker type requirements for each
-         *  of its subnodes). */
+        /* We define a recipe a to be a super-recipe of recipe b if they use the same
+         * fragment, the same number of subexpressions, and each of a's subexpression
+         * types is a supertype of the corresponding subexpression type of b.
+         * Within the set of recipes for the construction of a given type requirement,
+         * no recipe should be a super-recipe of another (as the super-recipe is
+         * applicable in every place the sub-recipe is, the sub-recipe is redundant). */
         auto is_super_of = [](const recipe& a, const recipe& b) {
             if (a.first != b.first) return false;
             if (a.second.size() != b.second.size()) return false;
@@ -366,16 +364,23 @@ struct SmartInfo
             return true;
         };

+        /* Sort the type requirements. Subtypes will always sort later (e.g. Bondu will
+         * sort after Bo or Bu). As we'll be constructing recipes using these types, in
+         * order, in what follows, we'll construct super-recipes before sub-recipes.
+         * That means we never need to go back and delete a sub-recipe because a
+         * super-recipe got added. */
+        std::sort(types.begin(), types.end());
+
         // Iterate over all possible fragments.
         for (int fragidx = 0; fragidx <= int(Fragment::MULTI); ++fragidx) {
-            int sub_count = 0; //!< How minimum number of child nodes this recipe has
-            int sub_range = 1; //!< How many different consecutive couns of child nodes this recipe has.
+            int sub_count = 0; //!< The minimum number of child nodes this recipe has.
+            int sub_range = 1; //!< The maximum number of child nodes for this recipe is sub_count+sub_range-1.
             size_t data_size = 0;
             size_t n_keys = 0;
             uint32_t k = 0;
             Fragment frag{fragidx};

-            // Figure out how many subnodes the recipe needs, and k/data/keys args to pass to ComputeType. */
+            // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
             switch (frag) {
                 case Fragment::PK_K:
                 case Fragment::PK_H:
@@ -421,7 +426,7 @@ struct SmartInfo
                     sub_count = 3;
                     break;
                 case Fragment::THRESH:
-                    // Thresh is run for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
+                    // Thresh logic is executed for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
                     sub_count = 1;
                     sub_range = 2;
                     k = 1;
@@ -445,23 +450,19 @@ struct SmartInfo
                             if ((res << "K"_mst) + (res << "V"_mst) + (res << "B"_mst) + (res << "W"_mst) != 1) continue;

                             recipe entry{frag, subt};
+                            auto super_of_entry = [&](const recipe& rec) { return is_super_of(rec, entry); };
                             // Iterate over all supertypes of res (because if e.g. our selected fragment/subnodes result
                             // in a Bondu, they can form a recipe that is also applicable for constructing a B, Bou, Bdu, ...).
                             for (Type s : types) {
                                 if ((res & "BKVWzondu"_mst) << s) {
                                     auto& recipes = table[s];
-                                    // Now determine if we already have a recipe that's "super" to this, because then adding
-                                    // a more specific one is unnecessary.
-                                    bool have_super = false;
-                                    for (const auto& recipe : recipes) {
-                                        if (is_super_of(recipe, entry)) {
-                                            have_super = true;
-                                            break;
-                                        }
+                                    // If we don't already have a super-recipe to the new one, add it.
+                                    if (!std::any_of(recipes.begin(), recipes.end(), super_of_entry)) {
+                                        recipes.push_back(entry);
                                     }
-                                    if (!have_super) recipes.push_back(entry);
                                 }
                             }
+
                             if (subs <= 2) break;
                         }
                         if (subs <= 1) break;
@@ -499,8 +500,8 @@ struct SmartInfo
         /* Find which types are constructible. A type is constructible if there is a leaf
          * node recipe for constructing it, or a recipe whose subnodes are all constructible.
          * Types can be non-constructible because they have no recipes to begin with,
-         * can only be constructed using recipes that involve otherwise non-constructible
-         * types, or because they require infinite recursion. */
+         * because they can only be constructed using recipes that involve otherwise
+         * non-constructible types, or because they require infinite recursion. */
         std::set<Type> constructible_types{};
         auto known_constructible = [&](Type type) { return constructible_types.count(type) != 0; };
         // Find the transitive closure by adding types until the set of types does not change.
@@ -629,9 +630,14 @@ std::optional<NodeInfo> ConsumeNodeSmart(FuzzedDataProvider& provider, Type type

 /**
  * Generate a Miniscript node based on the fuzzer's input.
+ *
+ * - ConsumeNode is a function object taking a Type, and returning an std::optional<NodeInfo>.
+ * - root_type is the required type properties of the constructed NodeRef.
+ * - strict_valid sets whether ConsumeNode is expected to guarantee a NodeInfo that results in
+ *   a NodeRef whose Type() matches the type fed to ConsumeNode.
  */
 template<typename F>
-NodeRef GenNode(F ConsumeNode, Type root_type = ""_mst) {
+NodeRef GenNode(F ConsumeNode, Type root_type = ""_mst, bool strict_valid = false) {
     /** A stack of miniscript Nodes being built up. */
     std::vector<NodeRef> stack;
     /** The queue of instructions. */
@@ -647,7 +653,11 @@ NodeRef GenNode(F ConsumeNode, Type root_type = ""_mst) {
             auto subtypes = std::move(node_info)->subtypes;
             todo.back().second = std::move(node_info);
             todo.reserve(todo.size() + subtypes.size());
-            for (auto type : subtypes) todo.emplace_back(type, std::nullopt);
+            // As elements on the todo stack are processed back to front, construct
+            // them in reverse order (so that the first subnode is generated first).
+            for (size_t i = 0; i < subtypes.size(); ++i) {
+                todo.emplace_back(*(subtypes.rbegin() + i), std::nullopt);
+            }
         } else {
             // The back of todo has fragment and number of children decided, and
             // those children have been constructed at the back of stack. Pop
@@ -671,7 +681,11 @@ NodeRef GenNode(F ConsumeNode, Type root_type = ""_mst) {
                 node = MakeNodeRef(info.fragment, std::move(info.keys), info.k);
             }
             // Verify acceptability.
-            if (!node || !node->IsValid() || !(node->GetType() << type_needed)) return {};
+            if (!node || !(node->GetType() << type_needed)) {
+                assert(!strict_valid);
+                return {};
+            }
+            if (!node->IsValid()) return {};
             // Move it to the stack.
             stack.push_back(std::move(node));
             todo.pop_back();
@@ -845,5 +859,5 @@ FUZZ_TARGET_INIT(miniscript_random_smart, initialize_miniscript_random)
     FuzzedDataProvider provider(buffer.data(), buffer.size());
     TestNode(GenNode([&](Type needed_type) {
         return ConsumeNodeSmart(provider, needed_type);
-    }, PickValue(provider, BASE_TYPES)), provider);
+    }, PickValue(provider, BASE_TYPES), true), provider);
 }