Bit of adaptor signatures
Adaptor signatures are a pattern introduced by Andrew Poelstra in this very nice post on the mimblewimble list. He describes how they can simplify the Hash Timelock Contract use case. But adaptor signatures are a lower-level tool which leverage the algebra covered in a bit of taproot primitives.
sG = H(R||P||m)*P + R
^ ^ ^
| | |
EC POINTS | | |
-----------+----+--------------+---
SCALARS | | |
| | |
s = H(R||P||m)*p + r
Our old friend, the Schnorr signature scheme which produces signature (R,s)
Hopping right in at the algebra level, adaptor signatures add a tweak to a signature.
sG = H(R+T||P||m)*P + R + T
^ ^ ^ ^
| | | |
EC POINTS | | | |
-----------+----+----------------+---+---
SCALARS | | | |
| | | |
s = H(R+T||P||m)*p + r + t
The scalar t tweaks a signature and has a new point T, an adaptor signature (R,T,s).
One can view t, the adaptor secret, and T, the adaptor point, as ways to encrypt a signature. If a user has at least two of the original signature, tweaked signature, or the tweak secret (adaptor secret) they can calculate the third. This is easiest to see in an example. Bob and Alice want to perform an atomic coinswap (trade ownership of two coins).
// Step #1: Alice computes a signature for a transaction to Bob m_a,
// but with tweak t.
s_a = H(R_a+T||P_a||m_a)*p_a + r_a + t
// Step #2: Alice computes an adaptor signature (R_a,T,s_a') and
// gives it to Bob.
s_a' = s_a - t
// Step #3: Bob verifies the adaptor signature. Now he knows
// he just needs to get t at some point to tweak it.
s_a'G ?= H(R_a+T||P_a||m_a)*P_a + R_a
// Step #4: Bob creates an adaptor signature (R_b,T,s_b) for a
// transaction to Alice m_b.
s_b = H(R_b+T||P_b||m_b)*p_b + r_a
// Step #5: Alice tweaks Bob's adaptor signature with the secret t
// to make it a valid signature (R_b+T,s_b') for the transaction.
// She broadcasts the transaction which pays her.
s_b' = H(R_b+T||P_b||m_b)*p_b + r_a + t
// Step #6: Bob sees Alice's transaction on the public blockchain and
// grabs the s_b' part of the signature. Bob calculates the secret t
// which is just the difference.
t = s_b' - s_b
// Step #7: Bob tweaks the adaptor signature he first received
// from Alice to make it a valid signature. He broadcasts
// the transaction which pays him.
s_a = s_a' + t
Coinswap walkthrough…disregarding possible double-spend attacks which can be mitigated with layers of multiparty signatures and timelocks.
The signatures are being used as the “data pipes” to pass along the secret information, very cool. Bob is able to get t in step #6 after Alice puts the signature on the blockchain in step #5. Outside observers are none the wiser though that data is being transferred in step #5, it appears to look like any other transaction on the blockchain. Compare that to a HTLC where all transactions can be linked with their shared preimage secret.
The adaptor signatures in step #2 and step #4 are verifiable, but not valid on under consensus rules since the hash challenge commits to T and t is not added outside the hash. That verifiable part is important though, that is how Bob knows after step #3 he just needs to get t to tweak s_a' into something valid. It is in the commitment, no way for Alice to mess with it.
This exchange shows off the two patterns to embed data in a signature. And they kinda rely on each other. Step #1 creates a “pre-signature” which requires another tweak to be valid. Step #4 creates a signature which will help reveal a secret once tweaked and broadcasted.
A more complicated pattern is Point Timelock Contracts.
Point Timelock Contract
A quick review of the Hash Timelock Contract pattern which Point Timelock Contracts, PTLCs, improve on. A payment channel between two parties is an abstraction implemented with a mix of onchain and offchain transactions. Funds of the two parties, Alice and Bob as always, are tied down in an initial funding transaction which is onchain. This transaction has a UTXO with a 2 of 2 multisig script requiring both Alice and Bob to sign off on any further transactions. Alice and Bob can then trade commitment transactions offchain to update the balances in the payment channel. Balances are determined by the potential UTXO’s in the commitment transactions.
If a payment is routed through the payment channel, from Alice to Bob and then on to its final destination, the balance of the payment needs to put in a new output while it is in limbo. The contract output uses similar patterns as the payment channel itself, where a timelock is applied in case the payment fails or if Bob disappears. If the payment is successful, Bob should receive some secret from the other side which allows him to spend the UTXO. Generally, the output now is “folded” into the existing balance outputs, so the offchain commitment transaction goes back to just two UTXOs.
[ Sig_Alice | 2 of 2 of Alice and Bob] -- [ Sig_Alice Sig_Bob | Alice's balance / Alice ]
| Bob's balance / Bob ]
| Routing Contract / (Alice && Timelock) || (Bob && Secret) ]
The funding transaction’s UTXO and a potential commitment transaction for the channel showing off balances. Some of the complexities of the balance outputs are omitted, just focusing on the routing output.
Timelock tangent time! The above is actually a little hand wave-y. The routing outputs in the Lightning Network use a “two-stage” pattern. This is due to the complexities of all the timelocks in the payment channel. Some are absolute, some are relative, and it is not always immediately obvious how they interact. The routing timelocks are absolute since they are “linked” across a payment. The revocation timelocks (not pictured above) are relative to ensure a window of time for an attacker to be thwarted. The two-stage pattern puts these timelock requirements in their own transactions so that they are independent of each other. This means however that there needs to be a staging output, another 2-of-2 multisig, for the first routing output.
Complicating matters is the asymmetric nature of channel transactions. The routing offerer, Alice in this case, will have transactions with different structure than the routing receiver, Bob. This is required to satisfy the revocation requirements. The offerer needs a pre-signed timeout transaction and the receiver needs a pre-signed success transaction.
The gory details of these transactions are in BOLT3.
[ Sig_Alice | 2 of 2 of Alice and Bob] -- [ Sig_Alice Sig_Bob | Alice's balance / Alice ]
| Bob's balance / Bob ]
| Routing Contract / (2 of 2 of Alice and Bob && Timelock) || (Bob && Secret) ] -- [ Sig_Alice Sig_Bob | Alice && Relative Timelock ]
Two-stage routing output for the offerer with a second stage timeout transaction, still omitting revocation things for simplicity.
Ok, enough with the timelocks, the part PTLCs focus on is the secret. An HTLC, Hash Timelock Contract, ties transactions together so that they are atomic. The timelock part handles failures, ensuring a payment rolls back, and the hash part deals with success, ensuring a payment rolls forward. In an HTLC payment, the receiver generates a secret preimage, hashes it, and gives that hash to the sender. The sender than creates path across the Lightning Network, informing all the intermediate nodes of this hash contract. They can then set up the appropriate HTLC outputs and fold them back in as they learn of the secret, which propagates from receiver to sender. Worst case scenario for a “roll forward” is that the secret hits the blockchain and the rest of the intermediate hops need to read it from there in order to fulfil their contracts.
This works, but the shared secret/hash links all the nodes on a path together. It is a privacy leak. Ideally no one, not even the nodes on the path themselves, would know they are a part of the same payment.
Well, what if the secret is embedded in signatures instead of out in the open? The receiver still generates a secret, but now it is a private scalar t. They tell the payment sender the public key T = tG. An HTLC output pays to the holder of a secret preimage, but a Point Timelock Contract output pays to the holder of a secret scalar.
All that two-stage stuff from before? Forget about it. Let’s say we are in an el too world where revocation things are much simpler. The PTLC output can be a single public key, which requires a 2-of-2 signature and the secret tweak, and a timelock’d refund. Routing nodes can calculate these public key outputs using MuSig to generate a shared key and then tweak it with T. When the PTLC receiver learns of t they can tweak a signature to then spend that output (or choose to fold it in to the channel balances). How does a receiver learn of t? Let’s compare the process to HTLCs. A node receives and offer for an HTLC and can safely make the next downstream offer since they have in hand a signed transaction that says “if you get this preimage, you get these coins”. Their downstream HTLC offer uses the same hash, so they know they will get that hash (or the timelocks will roll everything back). If they instead receive a PTLC offer, they get an output and a signature. A signature that they can verify is not valid yet, but will be valid if they get t (step #3 in the coinswap flow above). They can safely offer the downstream output and tweak with T to get the same t guarantee.
When it is time to “unroll”, or settle, a PTLC the destination node tweaks their signature with t, they know the secret scalar. They share this signature with the PTLC offerer and they can choose to fold the output back into their payment channel outputs. The offerer can use the signature to calculate t and do the same process with the upstream PTLC, much like an HTLC settlement.
Notice the secret no longer ends up onchain linking the transactions together. If some part of the route does go to chain, the upstream receiver recognizes the signature and can use it to calculate t, so the “roll payment forward” process continues, but not all at once like in an HTLC (when instead a hash hits the chain). And in taproot terms, the most common settlement case could probably be a keypath spend (haven’t totally thought this one through though) and the rollback case a script spend.
This can be taken one step further though. When the sender gets T, they don’t have to send that to all the intermediate nodes like they do with the hash in HTLCs. Instead, they calculate a random nonce for each PTLC in the path. Every node is told of the public key “receive” and “offers” they will be working with for the payment, plus their personal private nonce. These are all linked with ECC addition, they are all using adaptor signatures. When a node’s “offer” PTLC is settled, they can use that signature with their private nonce to calculate the signature for their “receive” PTLC.
// The payment path.
(Alice) -> (Bob) -> (Charlie) -> (Dave)
// Dave generates the payment secret scalar t.
T = tG
// Alice generates the nonces used for each PTLC.
y_0, y_1, y_2
// Bob receives:
(t + y_0)G, y_1, (t + y_0 + y_1)G
// Charlie receives:
(t + y_0 + y_1)G, y_2, (t + y_0 + y_1 + y_2)G
// Dave receives:
(t + y_0 + y_1 + y_2)G, y_0 + y_1 + y_2
PTLC route building, the last node is special since it implicitly knows the secret.
When the payment “unrolls”, each node cancels out their own tweak. Nodes in the path don’t know they are on the same path (unless neighbors) based on the secret value. Better yet, only Alice, the sender, gets the original secret as proof of payment.