We’ve been working on teaching EC points to “understand” authorization policies expressed with boolean logic. We’d love feedback and ideas!
TL; DR. Bitcoin mainly gives two ways to express “who can spend”:
Threshold / multisignatures (FROST / MuSig2): great privacy and efficiency, but they fundamentally express only cardinality (k-of-n).
Scripts: more expressive, but limited in practice, and the policy can become visible when used.
We built a PoC framework that compiles a monotone boolean policy (AND/OR logic) over users’ long-term keys into a single signature verification key (one EC point). On-chain part remains boring: verification of one Schnorr signature against one key. All the policy “drama” happens off-chain.
What this means for Bitcoin:
You can express policies that threshold signatures can’t capture faithfully, e.g. (A ∨ B) ∧ (C ∨ D) (structure, not just counting). Policies we have used for benchmarks are below:
Thanks for this post.
There is a policy in the example:
let policy_str = "(policy my_policy (and (or A B) (or C D)))";
However, only A and C are co-signers in Musig2 which spends onchain. I guess B or D could not authorize any spending alone. Does policy signer resolves Musig2 setup and generates valid partial signature instead?
The verification key P is not a MuSig2 aggregation of all four parties. Instead, it’s a MuSig2 aggregation of P_left and P_right, where:
P_left = hash(ECDH(P_A, P_B)) * G
P_right = hash(ECDH(P_C, P_D)) * G
so P = MuSig2_KeyAgg(P_left, P_right).
To produce a valid under P signature, we need two parties who can access ECDH(P_A, P_B) and ECDH(P_C, P_D), respectively. Either A or B can compute the left ECDH (using their private key with the other’s public key), and either C or D can compute the right one. So, the set \{B,D\}can produce a valid signature, but \{A,B\}cannot because they both belong to the same P_left branch, leaving the right branch unsatisfied.
In the code example, Alice and Carol are the active signers, but this is just one of the four valid coalitions. Bob and Dave (or any other valid pair) can sign in exactly the same way.
I’ve been thinking about it for a bit and I think I’m a little confused as to why the ECDH and attached ZKPs are necessary? Would it not be sufficient to designate one party from each disjunction subtree in the CNF to generate a secret for that subtree at random and to share it with all of the other members of the subtree (and then each member signs the public key and all parties, in the subree or not, verify these signatures and ensure that all members used the same key)? If I’m understanding correctly, during the ECDH-based setup you do have to store the aggregate secret for a disjunction subtree since you cannot non-interactively recompute it, and at that point it isn’t stateless so why not just store a randomly generated/unstructured secret? Is there a benefit to ECDH-based key agreement over private broadcast?
Regardless of how the key agreement happens, so long as all parties agree on aggregate disjunction keys during setup, no adversary will be able to stop an honest qualified set from signing, and no adversary will be able to sign if they have only corrupted a non-qualified set (since they will be missing one fully-honest secret from a disjunction they are not a part of). This should still lead to a direct reduction to the security of MuSig.
I believe the idea of writing a policy in CNF where each disjunction subtree corresponds to a group of people who hold some replicated secret is called Replicated Secret Sharing (RSS). My understanding is that normally a RSS DKG is very simple and consists of just sharing some secrets and verifying everyone has the same secret using authentication.
If I’m not mistaken, it is also possible to do key rotation within RSS without needing ZKPs, though I don’t know much in detail about this.
Your intuition is right, we can realize CNF-by-clauses using replicated secrets: pick a per-clause secret, privately distribute it to all members of that OR-subtree, and then ensure everyone agrees on the resulting clause public key (via signatures, for example). If all parties agree on the clause keys, we still get the “qualified set can sign / non-qualified set can’t”.
But, I think the BLISK approach has some additional advantages:
It avoids storing new secret material. With RSS/private broadcast, every member stores extra clause secrets (one per clause they belong to), and you need secure authenticated channels (or a private broadcast primitive) plus a verifiable key rotation for those secrets (which might be difficult). BLISK’s OR-gate approach aims to keep the only long-term secrets as the parties’ existing keys and to make clause material derivable via key agreement rather than distributed.
Quoting this: no, you don’t have to store the aggregated (to be more precise, shared) secret, the secret for the clause is derived based on your secret and public values in the path. So, there is a state (and it’s fair to call it stateful construction), but the state is shared among all participants, it can’t be corrupted (only lost), and it’s literally the set of public keys (representing nodes).
Prevent OR-gate cheating without requiring everyone in the clause to co-sign the resolution. If a “resolver” can publish an arbitrary public key for an OR node, they can pick a key known only to them, breaking liveness/semantics for other authorized members (even if the unforgeability of MuSig remains intact). With RSS, your “everyone signs the clause pubkey” approach fixes this, but it changes the coordination/liveness model: now clause resolution requires collecting endorsements from the entire clause (or some approval rule), which can be painful for large/overlapping clauses or partially offline participants. BLISK instead aims for “any eligible member can resolve”, and everyone else can verify correctness non-interactively.
Rotation is where the ZK verifiability really matters.
In an RSS design, rotation generally means re-sharing/re-distributing clause secrets (interactive + authenticated private channels) or running a fresh DKG-like step per affected clause. In BLISK, we pay proof costs so that updating/resolving internal-node keys remains publicly checkable without re-running a distribution protocol. When one party is updating their key: 1) public keys of all other participants remain the same; 2) but they need to verify proofs and update a common state with the new version.
So I agree ECDH isn’t “cryptographically necessary” in principle; it’s a concrete way to get the local-derivability property (“any authorized member can derive the OR secret”) without introducing fresh replicated secrets. And the ZKPs are there to enforce the well-formedness/consistency of OR resolutions without requiring all clause members to participate in the policy setup (and while allowing individual keys to be updated by their owners non-interactively).
Correct me if I am wrong, but I believe MuSig-in-MuSig (e.g. A ^ (B ^ C)) has no security proof yet?
Or do you flatten them into a single level on compilation? Your description, especially with regards to using ECDH for OR gates, seems to imply that you retain the structure at all levels of the expression tree?
BLISK restricts policies to CNF: a single top-level AND over OR clauses, because the only MuSig2 KeyAgg happens at the top.
So an expression like A ∧ (B ∧ C) is compiled/normalized to A ∧ B ∧ C (three 1-literal clauses), i.e., just standard MuSig2 3-of-3, no additional security proof is required beyond ordinary MuSig2 for that part.
I see. I believe even complex nested AND / OR sequences should be convertible to an equivalent CNF (admittedly it has been a long while since I did digital logic, I kinda wonder at NOT gates, which have no true equivalent in Bitcoin, but if the original expression has no NOT gates and IF gates then the CNF should not have NOT gates either?).
On the other hand, I suppose the MuSig-in-MuSig stuff matters for the use-case where one of the participants is secretly a multisignature (or more generally, itself has a complicated but hidden Boolean-gate policy), which would then not fit in this framework, which seems to require that the entire policy be revealed up front, then compiled to CNF.
In practice the secrecy may not be needed for privacy, but for protocol simpllfication — you just say A ^ B where you are A and the other side B is free to use a simple singlesig or a complex Boolean-gate policy without having to bother you with TMI.
On the other hand if we have a generic standardized Boolean-policy-to-CNF compiler, maybe we can have a BOLT spec where you just say “A ^ B is the base policy for the channel, both sides are then free to replace their term with another Boolean policy that they reveal to the counterparty, then compile the policy to CNF and use Blisk”.
Yes, it would be very useful! The main limitation is that we can’t (or at least I don’t know how yet) have a multisignature public key as a child of an OR gate; ECDH doesn’t work in this case.
Wow, that’s another great idea, I didn’t think about it from this side. So, for instance, two organizations can create a channel based on their internal policies and make a cooperative close only if the policies of both are satisfied? Need only to think about how to do BLISK-based HTLCs.
This seems trivial? An HTLC is just (A & preimage) || (B & blockheight) and you can just compile the individual policies for A and B and compile them into two single pubkey point, and just use tapleaves for (policy-A & preimage) and (policy-B & blockheight)? You kinda need SCRIPT for hashlocks anyway. An optimization is to also add a policy(A & B) keypath spend.
The goal here is to have a generic k-of-n Lightning Network node. Channels require a A & B between the channel parties, and for this “k-of-n LN node” future, either of A or B or both may actually be a k-of-n.
Now, I believe ANY k-of-n policy can be iterated as a DNF, e.g. for a 2-of-4 of A B C D, that would be ((A & B) | (A & C) | (A & D) | (B & C) | (B & D) | (C & D)). And the DNF form can be converted to an equivalent CNF form (they are just normal forms and I believe any nested AND-OR expression can be converted to either form).
Thus, we can consider ANY general policy of nested AND and OR gates, then flatten them to AND-of-OR and feed it to Blisk.
Now the issues here for a k-of-n LN node are two-fold:
Creating a new channel state basically requires a partial signature from the other side, but without the full signature being generated on our side — the point is that the full signature can only be safely generated on unilateral closure. The CNF at the Blisk level may require the creation of the FULL signature, which is unsafe — storing the full signature is unsafe as old state can now be posted by anyone who gets access to your stored full signatures. I would need to look more deeply into this to see if this is actually safe; my intuition is that there will be at least one term in the CNF that is controlled only by signatories of one side, which would serve as the decision-makers for when to do a unilateral close later (and create the full signature).
After creating a new channel state, we need to invalidate old state. There is simply no way to do this that still respects the shachain requirement of BOLT, so we should “just” drop the shachain requirement. Without the shachain requirement, the public key for the revocation key can be generated using flatten-to-CNF-then-Blisk and then at revocation time, the same calculations are done on private keys this time, then the resulting private key is the revocation private key that you hand over to the other party to revoke your old state.
Both the above can be sidestepped by switching to Decker-Wattenhofer, BTW: each state change both creates the new state and invalidate old state in a single atomic step of creating the FULL signature under Decker-Wattenhofer. And Decker-Wattenhofer, unlike Decker-Russell-Osuntokun, does not require a consensus change.
Just wanted to chime in here since it appears relevant for this discussion, but I have a paper titled “Nested MuSig2” that should be appearing on the ePrint Archive within a few days detailing a secure way to nest MuSig2 keys! This should provide more flexibility in how private sub-AND clauses want to be.
Hey! It’s literally how our reference implementation works. For any input S-expression policy drawn in monotone boolean functions (only OR, AND gates) and not necessary in CNF the compiler compiles it to CNF under the hood. Moreover the compiler supports keywords that express precompiled policies: e.g. (threshold 3 A B C D E) compiles to 3-of-5 threshold policy in CNF. I think it’s one of the most amazing features in BLISK: it could handle merely any monotone policy (even a large one such as 11-of-15 threshold Liquid federation policy). You could try out by writing some S-expressions, compiling them, resolving and enduring MuSig2 session as described in the example.
