PathCoin

pathcoin.md

PathCoin

Caveat

Before we begin: this post describes a very limited protocol idea. It's possible that what we describe here is a start towards, or a component of, something genuinely useful, but in itself it's really more of a toy, albeit it's fun.

Non-interactive digital cash

Since the 90s, there was a dream that cash could be sent online just like email. We've basically been experimenting with tradeoffs against this pure vision ever since. Sometimes the tradeoff is: there's a central party we have to trust (either with our privacy or our money or the management or inflation or..), but otherwise we get the goal. Often the tradeoff includes: we have to interact with the receiver. In pretty much every case there's an online-ness requirement: we have to exchange messages with a p2p network of active nodes (bitcoin) or a central server and our counterparty, or at least, directly with our counterparty (e.g. Lightning) in the payment transaction.

What we want is something closer to: I come up to your lunch cart on the street, buy a hotdog by "handing over" "digital cash", you don't have to trust me but can accept it as money, I walk off with the hotdog and both people forget the other. And of course, we want that to work the same in an internet payment (especially the 'forget' part).

Nice dream.

How far, though, could you go, if you doggedly insisted, in a Bitcoin context, that the actual act of payment, was simply the handing over of some data or text.

Above is pictured a different way of trading off to achieve the goal; the opendime, which is a very cool cypherpunk idea (a spiritual cousin of, if not technically related to, Hal Finney's RPOW idea of the early 00s). If you trust that the hardware is not hackable (enough), you can accept the device as being == the coin.

A reminder, in case these ideas are not front of mind: I can't give you money by "handing over my private key", because that's really sharing data, not transferring it. You have no way of knowing whether I remember it; and if I remember it I have as much control over the coin as you do. So private key transfer is generally not a useful idea. There are big caveats - see Mercury wallet and perhaps even Intel SGX, but see also: opendime, as mentioned - the private key cannot be accessed without physically (and demonstrably) "breaking" the opendime; before that time people can transfer it physically, and treat it as physical transfer of ownership of the signing key.

The limitation of this meaning a "fixed denomination" coin is interesting; statechains, of which the above-mentioned Mercury is an implementation, in general, have this kind of limitation too.

Statechains make one of the various tradeoffs we already discussed, in that they have a trust in a third party (more particularly they are trusting in absence of collusion, something we're going to discuss at length here!). We're going to see how far we can get without that trust element.

So: can we make this kind of construction, without trust, in software, not hardware? Let's try! What is presented next as "PathCoin" is based on that idea. As we said at the start, it is VERY limited compared to what we would like to do in the "dream" explained above. But maybe it's the start of something?

Basic idea

First of all, let's consider shared ownership of a single utxo, in a taproot and Schnorr and MuSig2 world.

It's already pretty nice. There can be 100 people owning a multisig together and because of the above tech, it can look the same as one person, to the outside world (I won't discuss MuSig further in this doc, as it's kind of orthogonal. Simpler multisig exists, in taproot, if we need it).

For the rest of this description, though, let's have it be 5 people Alice, Bob, Carol, David, Eve. Just to keep things manageable.

So if they make a 5 of 5 multisig they can control funds together.

With taproot, they can create multiple spending paths with different spending conditions, when they set up this address, such as:

1 coin -> (Alice and Carol) OR (all 5) OR ( Bob and Carol after 1000 blocks OR (all 5)) OR (David and Eve after 2000 blocks)

So that convoluted script logic was just made up, but the point is we can use the 'script path spend' in taproot to make lots and lots of different spending paths that don't end up abusing the blockchain space limitation; only one of the spending paths ends up getting satisfied, and displayed, in the spending transaction. Great, simple so far, just taproot.

Now if all we really want to do is "use taproot to share and transfer money", we may well be better off with the kind of model explored in payment pools (that link is only one of several disparate discussions on this topic, I think). In that scenario, there is unilateral withdrawal available, but payments are cooperative, updating the contract inside the taproot output. It's a very promising direction, but here we're, again, insisting on no further interaction to make payments, in line with the 'cypherpunk dream'.

From here we'll build up the PathCoin idea in stages, starting with the most restrictive and slowly dragging it closer to useable, with more elements.

So, continuing from taproot: we could deliberately create several different paths with the same condition, like this:

Person	Alice	Bob	Carol	David	Eve
multisig script 1	A1	B1	C1	D1	E1	-> TXA
multisig script 2	A2	B2	C2	D2	E2	-> TXB
multisig script 3	A3	B3	C3	D3	E3	-> TXC
multisig script 4	A4	B4	C4	D4	E4	-> TXD
multisig script 5	A5	B5	C5	D5	E5	-> TXE

These are all 5/5 multisigs. Each list of 5 is different keys (see number suffixes), but the letter denotes which person owns the private key for that key. So this is just a 5 x 5 matrix of keys. The 'scripts' are just a single pubkey spending script, which happens to be a MuSig2 aggregated key.

Alternatively, and more simply, we could just define one 5/5 MuSig multisig, use the key-path spending in taproot, and simply perform 5 separate signing sessions on the same key (each session signing different transaction messages). So:

Person	Alice	Bob	Carol	David	Eve
musig session 1	A1	B1	C1	D1	E1	-> TXA
musig session 2	A1	B1	C1	D1	E1	-> TXB
musig session 3	A1	B1	C1	D1	E1	-> TXC
musig session 4	A1	B1	C1	D1	E1	-> TXD
musig session 5	A1	B1	C1	D1	E1	-> TXE

Functionally, this is not different; each signing session requires all 5 participants to agree on the outcome in both cases. We will use the latter, though, because it's simpler, and key path spending is more efficient and more private.

Now notice what happens if, let's say, Alice is the one who funds the output containing this 5 of 5 MuSig taproot output, and demands that she be provided signatures so as to be able to spend it, thusly:

Person	Alice	Bob	Carol	David	Eve
Session 1	σA1	σB1 ✔️	σC1 ✔️	σD1 ✔️	σE1 ✔️
Session 2	σA2	σB2	σC2 ✔️	σD2 ✔️	σE2 ✔️
Session 3	σA3	σB3	σC3	σD3 ✔️	σE3 ✔️
Session 4	σA4	σB4	σC4	σD4	σE4 ✔️
Session 5	σA5	σB5	σC5	σD5	σE5

(The coin value is U from now on).

If at the time we set up the address (and we of course all have to interact to do this - just like with any multisig), we have the signatures marked with checkmarks all be shared (amongst everybody to keep it simple), then you'll notice that Alice is the unconditional owner of the coin. She has 4 signatures given to her, meaning she can spend using path 1 at any time. While crucially none of the other parties (including Bob, who doesn't have Alice's signature on path 2) can spend the coin, and Alice knows that - she hasn't shared her signatures for other paths. So far so good.

Alice transfers to Bob

As we explained earlier, transferring a private key does not transfer ownership. Similarly, if Alice gives her signature σ_A2 to Bob, so that he is now able to spend from Path 2, it sadly is not a functional payment, since Alice can still use Path 1, any time. How to get round this?

Naive penalties don't work

One thought that might spring to mind is: in Lightning, they have a penalty mechanism, to punish a cheater on one side of a channel, who spends an old state, by giving all the money to the other side of the channel. If we tried to apply that idea here it wouldn't work. Here's why, concretely:

• We set everything up. Alice owns the coin.
• Alice transfers to Bob by giving her signature σ_A2, but also gives a 'promise' that if she ever spends using Path 1 (σ_A1), then Bob can claim a penalty (more than the coin being spent). This stops her being incented to spend using Path 1.
• Bob now transfers to Carol. What is Carol's assurance that Bob won't spend, now, using Path 2? The same - there would be a penalty payment from Bob to Carol. BUT! What is Carol's assurance that Alice won't spend the coin using Path 1?

The problem isn't that there's not a penalty (Bob could even send proof to Carol that the penalty existed). The problem is where it goes. If it goes to Bob, how does Carol know that Bob and Alice are not colluding, or are not both called Sybil? If they work together, then a penalty from Alice to Bob is meaningless and so Carol actually has no defence at all, and so this scheme fails.

This applies to any number of parties greater than two. It will never be enough to be safe from the misbehaviour of one party, you need to be safe from the misbehaviour of all.

Not feeling the burn.

One way to try to solve it is with burned funds. I claim that this could be viable, but it is very problematic, to the point I would not pursue it. An honest party attacked with a double spend of U, when the defence against it is burned funds, does not gain from the burned funds, thus an additional positive incentive as well as the burn, is required. Moreover, whether that extra incentive helps is very dependent on how much the attacker could bribe you to not execute the burn. If you look into it, you find that this approach is too game theoretically fragile.

Everyone wins (a little bit)?

We might conclude, from this line of reasoning, that every other party must benefit whenever one cheats, so that even if there is only one honest actor, they always have a defence. For example, with 5 parties as described, we can imagine that Alice might have to forfeit, to all of Bob, Carol, David and Eve, an amount strictly larger than U; thus her fidelity bond would be roughly 4 x (U + δ). This wouldn't be great, but we'll address this point later. Before we do, let's at least sketch out one way we could create such a forfeit or penalty.

Covenants, bonds, penalties: the inefficient first version

The fidelity bond concept is widely enough known; in its traditional sense it exists to be used as a penalty in a contract violation, and that's how we'd use it here.

Participants put up a certain amount of money in a 'fixed' location (fixed by a timelock). Let's say Alice pays to an output with a script like this:

EITHER (to Alice after 100 days) OR (to key T_A AND CTV <hash of tx1>)

, where tx1 is fixed to have 4 outputs, one each for Bob, Carol, David, Eve, each have amount U + δ.

(The use of δ here is of course just to create a negative incentive to cheat, even in the worst case.)

Here CTV refers to the currently-under-discussion (Jan 2022) covenant op code which may be added to Bitcoin (see CHECKTEMPLATEVERIFY). Any similar scheme that allows us to constrain where an output can be spent, rather than who can spend it, could play that role, in the following.

So this type of fidelity bond has a get-out clause, instead of just 'lock your funds for time 100 days', but: that get-out clause can only pay out to Alice's counterparties. In the normal case she'll lose more than 4 time the value of U, so that's a disaster for her; but even in the most adversarial case, where Alice colludes with 3 others (Bob, David, Eve) in an attempt to attack one victim (Carol), she (they) will still lose more than they gain (δ), and more important than that: Carol will gain more than she loses.

Now, when Alice creates this "fidelity bond", she'll need to actually know the private key t_A corresponding to the pubkey T_A (we'll see why shortly), but she won't ever want to use it! Nor to publish it such that anyone else could immediately destroy her funds.

Signature adaptors and toxic waste signatures

Before we fix up the inefficiency of that fidelity bond, let's flesh out how the transfer of value happens.

Given the above setup created at the same time as the set of 5x5 paths in the taproot output (we'll now call it the pathcoin output, value U), we can force a cryptographic linkage between that, and the fidelity bond outputs. When Alice sends σ_A2, she will actually send, to Bob, this full list:

σ_A1' , (σ_A2, ... σ_A5) The ' is for a signature adaptor rather than an actual signature. For the basics of signature adaptors and how they can be used to tie the revealing of a secret to the broadcast of a signature, see here and here. They require Schnorr signatures, which is one reason that this is only realizable in taproot.

Giving rise to this situation:

Person	Alice	Bob	Carol	David	Eve
Session 1	σA1 ❌	σB1 ✔️	σC1 ✔️	σD1 ✔️	σE1 ✔️
Session 2	σA2 ✔️	σB2	σC2 ✔️	σD2 ✔️	σE2 ✔️
Session 3	σA3 ✔️	σB3	σC3	σD3 ✔️	σE3 ✔️
Session 4	σA4 ✔️	σB4	σC4	σD4	σE4 ✔️
Session 5	σA5 ✔️	σB5	σC5	σD5	σE5

This short list of values she sends (should be around 320 bytes(?), in this toy case, with T_A implicit if it was shared upfront), we're claiming here that Alice has effectively entirely transferred control of the pathcoin utxo to Bob. (And it does mean full control - he can spend it immediately or at any time before some long fidelity bond timeout).

It could be sent in a simple format via email or text or literally anything. Not requiring a p2p network or an interactive exchange (Bob can be asleep when you send it, he can pick it up on a third party server etc. etc., you get the idea). Obviously there is a liveness requirement of Bob - check for a cheating transaction, so the advance here isn't so much "offline" transactions, it's non-interactive and off-chain transactions.

But first, what exactly are we claiming happened here? By sending the signature adaptor σ_A1', on point T_A, for the signature σ_A1, which is the signature Alice would have to broadcast to spend the pathcoin output herself, it means that if she ever does so, Bob would learn t_A (the formula is just t_A = σ_A1 - σ_A1'), the private key of T_A, and as discussed above, could use the fidelity bond (at least before the timeout) to claim an amount as penalty, greater than U.

The necessity to create this adaptor is why Alice must actually know the value t_A.

A sane Alice will actually therefore be much more likely to want to delete the signature σ_A1 than use it, and perhaps the value t_A also, but there is a finesse in there that we'll get to later.

But for now, let's follow the logic down the chain:

Third, fourth, .. recipients

After Alice has paid Bob as per above, the situation looks like the previous table.

Bob has 100% ownership. He can either spend the coin outside, or, pay Carol by repeating the process. He will send a longer list of items:

σ_A1'(T_A), σ_B2'(T_B), (σ_A3, ... σ_A5), (σ_B3, ... σ_B5)

Basically, he's sending Alice's revocation of her own claim, Alice's authorization of future payments in the path, and also his own revocation of his own claim, and his own authorization of future payments on the path.

Though it's a slightly longer list, it's still something you can trivially email. (It's crudely an O(N²) scaling in this simple model, but we hit other limitations before that matters!).

After this second transfer the table looks like this:

Person	Alice	Bob	Carol	David	Eve
Session 1	σA1 ❌	σB1 ✔️	σC1 ✔️	σD1 ✔️	σA2 ✔️
Session 2	σA2 ✔️	σB2 ❌	σC2 ✔️	σD2 ✔️	σA2 ✔️
Session 3	σA3 ✔️	σB3 ✔️	σC3	σD3 ✔️	σA2 ✔️
Session 4	σA4 ✔️	σB4 ✔️	σC4	σD4	σA2 ✔️
Session 5	σA5 ✔️	σB5 ✔️	σC5	σD5	σA2

At this point, like Alice, Bob would rationally immediately delete his σ_B2 value so as not to accidentally get his fidelity bond destroyed by revealing t_B .

The crucial point is of course, that here, Carol is defended against any collusion between Alice and Bob. If either of them (or both) tried to spend the pathcoin utxo, they would be revealing to Carol their adaptor secrets which would allow an immediate and uncontested penalty transaction, taking from the attacker more than they lost. Notice that in a case where the attacker is more than one step up the path, it doesn't matter who uses the adaptor to claim the punishment; everyone except the attacker gets it.

This latter asymmetry (not only the stolen-from gets rewarded) could incentivise malicious attempts to reveal the adaptor, which is why I said earlier: the rational thing to do is to indeed delete the full signature as soon as the adaptor has been revealed. They are indeed toxic waste.

Anyway, just for completion, here is what Carol would send to David:

σ_A1'(T_A), σ_B2'(T_B), σ_C3'(T_C), (σ_A4, σ_A5), (σ_B4, σ_B5), (σ_C4, σ_C5),

And David to Eve:

σ_A1'(T_A), σ_B2'(T_B), σ_C3'(T_C), σ_D4'(T_D), (σ_A5), (σ_B5), (σ_C5), (σ_D5)

Now we've laid out the general idea, let's address the main limitations to the construction:

1. This is a single coin with a single denomination U.
2. This is only allowing payment along one path (any person can cut the path short of course, by spending the coin, but the most that can happen is A->B->C->D->E). This is such a huge limitation that it makes the construction as-is nearly 100% impractical (you could find a use-case where this is viable, but .. you'll struggle).
3. This requires allocation of capital to an FB of value approximately N x U, where N is the length of the path.

All three of these limitations are best described as 'very very big' :)

In the rest of this document I'm going to propose a solution to (3), but I have only some unclear ideas about (2), and no particular ideas right now about (1).

Constant size bonds of U + δ

As discussed, (3) is a deal breaker, as presented, to doing long paths. Nobody would reasonably lock up 100 times the value of a coin to spend it.

Can we make it so that each participant only has to put up a bond of U + δ, not N x (U + δ)? I claim we can.

Let's define some terms: F_A means the utxo which represents a fidelity bond for A. CTV(t_A)-> means a script condition that forces the spending to the output indicated by the forwards arrow, but where the signature requires knowledge of the secret t_A (as discussed above, this secret will usually be revealed with reference to an adaptor signature on another, now illegal, spending event). H(S_C)-> is as for CTV(t_A)-> except the condition is just the knowledge of a secret S, in this case owned by C.

Our goal will be that the fidelity bond, before the timeouts indicated as TL_X, of party 1 will be claimable only by party 2, who is the aggrieved party, i.e. specifically the current holder of the pathcoin utxo, and we want this to be the case even though there is only forwards transfer of data as outlined above, i.e. we don't want to renegotiate contracts with everyone during payment events.

Let's start with Alice, making this chain of spends for her fidelity bond:

F_A script:

(A and TL_A) OR (CTV(t_A) -> (B and TL_B) OR (CTV(t_A) AND H(S_B) -> (C and TL_C) OR (CTV(t_A) AND H(S_C) -> (D and TL_D) OR (CTV(t_A) AND H(S_D) -> E))))) ;

t_A <-> σ_A1'

Unpacking: rather than Alice just locking a penalty to her adaptor σ_A1', she's pre-creating a chain of payouts of the penalty. When she pays Bob, he'll get the adaptor and know that he can wait on the TL_B before claiming the coin via that utxo. He'll know that Carol will not be able to cheat (colluding with Alice) by pulling it forwards into the third utxo, because it's locked to a secret S_B) that only he controls. Those S secrets block all similar forms of collusive attack.

Then if later Bob pays Carol, he'll transfer (σ_A1') and also transfer S_B, (as well as the signatures as described above). That means that Carol will be assured that if Alice spends, she'll be able to use CTV signatures to push it forwards to the third utxo, but as before, she knows it won't go any further due to her keeping hold of S_C, and wait for the TL_C. And so on.

And of course it doesn't stop there. Bob will need to do something similar:

F_B script:

(B and TL_B) OR (CTV(t_B) -> (C and TL_C) OR (CTV(t_B) AND H(S_C2) -> (D and TL_D) OR (CTV(t_B) AND H(S_D2) -> E))))) ;

t_B <-> σ_B2'

At the point where Carol receives the coin, Bob has rescinded all control of the funds, so he has no need for a penalty tx vs Alice. So Carol will have effective control of the coin in both the above paths, in the event that either of them illegally spends the pathcoin utxo. They can't both do it, of course (although they could both stupidly reveal the signature), because only one gets onto the bitcoin network.

Repeating this all the way down the path gives us another "triangular matrix" type situation (i.e. there are ~ NxN/2 of these FB_X outputs). The end result is that every honest owner can claim exactly one of these outputs as penalty, after a time delay which needn't be very long.

For this reason, in this (admittedly complex!) construction, each participant will only have to fund their FB_X output with an amount somewhat larger than the pathcoin utxo, i.e. U + δ, not N times that amount.

With this preparation in advance, we could reasonably consider constructing paths of length such that the O(N²) scaling of the initial setup signature transfer does not become overwhelming. I would tentatively suggest numbers N between 100 and 1000 are at least reasonable, depending on .... things.

What I certainly can't claim is that this construction is particularly useful. Remember that the root cause of the inflexibility is: we want each party to be able to pay forwards without any contract renegotiation, which means we have to 'expand out' all the possible future changes of ownership at the start.

It's certainly possible to try to construct a (yet more complex) version of PathCoin that allows multiple different paths amongst the same set of participants, but note that the number of paths is factorial in N, hence this is only even worth considering for very small numbers of participants (<=10 probably).

Whether there is a smart usage of other opcodes/signature constructions (for example, ANYPREVOUT) that would extend this out to be usable for different paths in some ways is .. an exercise for the reader!

Path chaining

This is more just musing about (2) than really attempting to solve it, for now.

One could imagine taking a current owner (say: David) who wants to then move the coin in a different direction than to Eve, taking the existing set of data (signature adaptors, signatures, hash secrets) that constitute his defence against malicious spending, and therefore constitute his current unconditional ownership, and using that as a starting point for the creation of a new path. This approach is obviously nontrivial, because: all the previous owners remain "in play" (and this can only done before the timelock that prevents them swiping out their FBs and then illegally spending). Also, David would have to convice a new bunch of potential owners (Fred, Grace, Harry, Ivy perhaps) that they do not have a threat from the earlier owners. I haven't yet figured out if that is possible, but perhaps it is, and if it or something similar could work, then chaining such paths almost gets it to the point of being practically useful (though still a bit too clunky, really, even given the wow factor of 'send money like email, without hitting the chain'; you have fixed denominations and you still have to decide upfront who to pay next, or otherwise rejig).

How does this extend to your hot dog merchant? The merchant would need to be part of the 100-plus ownership group of the coin, with setup ahead of time.

For value to transfer around back and forth between the participants, the total size of the scripts and keys would need to be increased by the expected number of roundtrips? I guess this is what you mean here:

What I certainly can't claim is that this construction is particularly useful. Remember that the root cause of the inflexibility is: we want each party to be able to pay forwards without any contract renegotiation, which means we have to 'expand out' all the possible future changes of ownership at the start. It's certainly possible to try to construct a (yet more complex) version of PathCoin that allows multiple different paths amongst the same set of participants, but note that the number of paths is factorial in N, hence this is only even worth considering for very small numbers of participants (<=10 probably).

How does this extend to your hot dog merchant? The merchant would need to be part of the 100-plus ownership group of the coin, with setup ahead of time.

Yes, that was part of the 'dream' :) Not realized by this construction in itself (at least not realistically).
I thought that the 'caveat' at the start would give the appropriate framing, as well as the comment in the mailing list and the section at the end. Perhaps I sold it as more interesting than it was, but the strong emphasis here is on something that might form a jumping off point for an actually realizable system ... see "exercise for the reader", above :)

For value to transfer around back and forth between the participants, the total size of the scripts and keys would need to be increased by the expected number of roundtrips?

Well I think I've mentioned some aspects of this in the doc, but probably too briefly. Other bits of analysis got lost in the wash.

First, for a single path, the data transfer for a single payment is crudely quadratic for the data transferred by party k to party k+1 since it requires a set like (adaptor1, adaptor2,.. adaptor k, (hash secret 1, secret 2 .. secret k), (sig1k, sig1(k+1), .. sig1n), (sig2k, sig2(k1+1), .. sig2n), .. (sigkk, sigk(k+1), .. sigkn)). (see the tables for why the sig part is like that, while the stuff at the start of the list is the fidelity bond bit).

Second, to analyze data transfer requirements for roundtrips, we'd have to have a viable model first of how roundtrips work. The last section of the gist is as I say a "musing" than any serious attempt at making a pathcoin be spendable to a new path after the one it was first created for. So I don't know.

Third, the alternative of trying to create all paths in one initial taproot output I have basically approximately dismissed above by referring to it as "factorial in N" and therefore not even conceivable for N>=10. It's possible I'm wrong to do so, e.g. groups of 5 or 6 with manageable numbers, plus some additional analysis, could conceivably be interesting if something like "path chaining" between them is possible, but again, it's a stretch, so far.

Correct me if I'm wrong, but because it is signature based it seems you'd just need a branch per participant and not a branch per transfer, right? Because suppose Bob has sig_i and sig_i+100, Bob would have discarded sig_i already and using the sig_i+100 path would not be revoked yet.

BTW I could see something like this being somewhat useful for e.g. exchanges to build a settlement layer between themselves which has different properties than Lightning.

Correct me if I'm wrong, but because it is signature based it seems you'd just need a branch per participant and not a branch per transfer, right? Because suppose Bob has sig_i and sig_i+100, Bob would have discarded sig_i already and using the sig_i+100 path would not be revoked yet.

@JeremyRubin By "branch" do you mean a branch in the taproot script tree of the pathcoin utxo? The way you worded it suggests you do, but I'm not quite understanding the idea.

well it sounded like above you would need a branch per payment in the taproot script tree, but I think the branches are just per-participant since they can be 'visited' multiple times.

@JeremyRubin So concretely, say it's Bob, you mean he could reuse path 2? Do you mean by constructing a second multisg on that path (i.e. the same keys)? So it would need to be part of the setup to create two sets of multisignatures on that keyset? It would still require pre-defining the path, though, because of the need to have defence against all previous owners, right? (but yes it would not require an extra branch in the merkle tree, right).

i think i don't understand the weeds enough yet, but maybe let me try at a high level:

each participant should have 1 path with O(1) storage space. That path looks like:

OR(timeout + revokable key, fraud proof(revokable key, blinded revokable key signature, revokation) + predetermined payouts w/ CTV)

All that I'm commenting is that by binding fraud proof to the combination of

(revokable key, blinded revokable key signature, revokation)

To do an update, holder i first "blind signs" for transfering to holder i+1, and then revokes signature i and includes all i-j revokations.

If signature i appears on the network, then any party has PERIOD to generate a fraud proof from it.

However, if i+1 shows up, and there is no revokation known, then no one can steal.

it's possible to use the same path per person many times over because generating a revokation is bound to a specific blinded signature, and not to just the key.

@JeremyRubin i wonder if you could unpack some of those thoughts further; it looks like you're describing a significantly different setup (but it's hard to be sure exactly).

I'm inferring that you're describing the script put directly into the owned output (the 'pathcoin utxo' as I put it)?

The complex scripts I described in the gist were specifically only scripts for the fidelity bond outputs. In my description, the actual pathcoin utxo is only a N branches taproot script output, each branch being N of N multisig only. For what it's worth, this does preserve one big advantage: as pure multisigs they are unconditionally spendable immediately, while owned.

When you say blinded, do you actually mean blind signatures or signature adaptors as per this document? I think I can semi-parse it as adaptors ("encrypted signatures" as Fournier likes to put it). But not sure.

I don't understand exactly what you mean by fraud proof. If I interpret it as Alice giving Bob an adaptor (as in the gist), then I could maybe see that what you're getting it at is something like:

Instead of just a dumb NxN multisig set as the utxo's script, it can be this kind of construction, like: OR(Alice_revocable + timelock, CTV (locked on Bob and Alice sigs) to: OR(Bob_revocable + timelock, CTV to: ..) etc. Sorry if this is nothing like what you had in mind, just a general guess as I don't know precise definitions (in particular, of fraud proof), here.

The scripts I gave in the gist were trying to address one particular thing: how to defend against collusion in the other members of the set, without having to massively expand the penalty payout. The chain of possible endstates in each fidelity bond is to guarantee that exactly the honest owner of the coin can claim it, even though it's only one "coin" (U value in the doc).

Perhaps as a start if you could tell me what in Bitcoin Script this: fraud proof(revokable key, blinded revokable key signature, revokation) would look like it could help. Also what predetermined outputs for the CTV you're thinking of.

Using more advanced script constructs in the main pathcoin output seems like it does have one big tradeoff, namely: if the pathcoin utxo itself is timelocked, it's never immediately spendable. But I would not be at all surprised if you could get super-interesting outcomes from doing that.

it's possible to use the same path per person many times over because generating a revokation is bound to a specific blinded signature, and not to just the key.

So is that basically the same as I was saying in https://gist.github.com/AdamISZ/b462838cbc8cc06aae0c15610502e4da#gistcomment-4040201 ? The thing is, that precisely the fancy footwork I described to get the result above: " The chain of possible endstates in each fidelity bond is to guarantee that exactly the honest owner of the coin can claim it" requires setting the path in advance. Although possibly we can finesse that, could well be something there.

yeah. i'm trying to probe at what you're describing since i'm not sure i fully get it yet, so thanks for answering the questions I'll go back and read more to see if i can understand the original post fully (i am at least as dumb as you may think i am, if not quite a bit moreso, these things take me time to load in).

well it sounded like above you would need a branch per payment in the taproot script tree, but I think the branches are just per-participant since they can be 'visited' multiple times.

@JeremyRubin

I was just thinking about this topic again this morning and re-read the thread, and I think maybe I understood what was confusing here:

In the tables, I labelled on the left "Path 1", "Path 2", etc, but that's misleading. Doh.

Each branch in the taproot script tree does not represent a different path for the "PathCoin" utxo. It's actually all 5 (or in general N) branches that are used for one path A->B->C->D->E. The transfer of signatures is just shifting ownership from one branch to the next down the rows of the table.

Yeah i think that's confusing for sure -- can you relabel it? What would you call it?

@JeremyRubin

In the first table in the writeup, each row is labelled 'Multisig path N' and the below paragraph kind of explains it:

These are all 5/5 multisigs. Each list of 5 is different keys (see number suffixes), but the letter denotes which person owns the private key for that key. So this is just a 5 x 5 matrix of keys. Now notice what happens if, let's say, Alice is the one who funds the output containing this MAST (taproot) tree of 5 scripts, and demands that she be provided signatures so as to be able to spend it, thusly:

I think I will change it to say 'Multisig script N' and the same below 'Script N' not 'Path N', in the other tables.

In case it helps, further, what I had in mind: Each row is one leaf in the taproot script/merkle tree, i.e. one script. But of course it's rather weird because: each of them is the same script, but with different keys, and the script for each leaf (i.e. each row in the above table) is just spending against a single pubkey, which happens to be internally 5 of 5 multisig, with MuSig2.

It's a good thing you encouraged me to at least think about it a little more concretely, because there are two important details:

1. Signature adaptors only have the kind of function used here or in similar things (coinswaps, PTLCs) if they're used inside a Musig construct, because that's the only way to constrain that exactly one signature is valid (i.e. it doesn't work with traditional multisig), so that signature<->secret is made atomic.
2. On reflection, I don't currently see why they have to be different keys in each of the scripts, I think it's enough that they are just different MuSig2 protocol instantiations, and they could be on the same keys. There may be some nuance I've missed there, for now I think it would work either way.

So hmm, if my point 2. actually stands above, then there may not even be any need for multiple scripts, it's just multiple MuSig2 protocol runs with sets of 5 signatures against each. That may well be part of what you were discussing upthread, though I think you were also discussing other things.

yes, I don't fully understand it yet (see earlier comment about my intellect) but indeed I was remarking that the branches seem reusable.

It seems to me, naively, that the scheme you present has many similarities to blockchains.

At each transfer there is a need for a "chain" or "path" of all previous owners provably giving data that invalidates their ownership of the coin. Similarly on a simple blockchain, you need the path from the transaction paying to you, to a coinbase, and each transaction invalidates (spends) a previous UTXO.

The data that needs to be transferred grows over time as well.

@ZmnSCPxj

It seems to me, naively, that the scheme you present has many similarities to blockchains.

That's an interesting point of comparison. Obviously a blockchain is a vastly more flexible construct (and also a setup like this presupposes an existing blockchain ofc), the thing we're trying to achieve here that we don't achieve on a blockchain is that there is only a transfer of information sender->receiver rather than to the world (or even, to all members of a fixed group, like this 5 party pathcoin group). Basically fix in advance a bunch of state that can be committed to chain, then use a kind of "airlock" system to move from one state to the other (perhaps a whimsical analogy ...).

The data that needs to be transferred grows over time as well.

Yes as per above discussion somewhere the data transfer is crudely quadratic in the path. I didn't think too much about this yet, since other limitations are too severe to think about that, yet.

One line of thinking that's been interesting me is: it might be possible to "hop over" steps on the path if you allow some relaxation of the 'no interaction for non-receivers' assumption and instead say 'no signing interaction from non-receivers', i.e. they could have software automatically rescind their possibility of payment by handing over the same list of data that they would hand over if they were receiving: (adaptor, forward signatures, hash preimage for fidelity bond), to their precursor in the path. i.e. concretely if B holds the coin and wants to pay D, then B could do 'query'/'ping' to C to get that data list, C, having sent it, would "delete" this pathcoin from its database (it never received this one, which is why of course it can safely hand over this data, also I am tacitly imagining there might be many such pathcoins in play at once), and B would send the same dataset to D that C would have sent otherwise, i.e. the revocations and authorizing signatures for A, B, C, so that D has ownership.
I'm not sure if that kind of tradeoff is interesting or not; perhaps: it would be an interesting mathematical exercise to try to decide what kind of path lengths and, indeed what kind of paths (repeated entries for individuals included?) would be somehow optimal to make it useful, if you make the assumption that hopping over M steps (example: B can send to E by hopping over C, D) is possible. There are, no doubt, practical issues with trying to do that, but I'm interested whether it's even theoretically viable.

Another line of thinking which interested me earlier today, but breaks my brain a bit: suppose, concretely, Alice's 'script' (or musig instantiation, as per above) paid out to her script A1, and suppose that A1 contained a 'revocation clause' that CTV-ed out to another version of the starting, pathcoin script: can we use APO to make it so that her revocation just pushes the coin back into the same state it started in? I.e. a bit like eltoo, to remove a need for fidelity bonds. I am not at all sure that this thought is coherent but just mentioning it.

to a coinbase

nit, but it's usually more than one :)

and B would send the same dataset to D that C would have sent otherwise, i.e. the revocations and authorizing signatures for A, B, C, so that D has ownership.

It occurs to me that there might be a fun privacy element to that: a bit like how in Sphinx we arrange it so you never know whether how many steps existed before your receipt of a packet, similarly you could whimsically imagine someone receiving a pathcoin as E in a list, but having no idea if it came from A, B, C or D.

Apologies in advance for the perhaps naive way of first approaching this discussion. Is it possible, if nothing else for sake of making it easier for us to understand, to shrink the concept of PathCoin down to N=2 participants (Alice, Bob) with then the goal of allowing for an (ideally) unlimited number of cycles where Alice assigns the UTXO to Bob and then Bob assigns it back to Alice?

Perhaps there is already a name and solution for the N=2 case with cycles and I just do not know it? If so, please point me in the right direction so I may contribute better to this discussion. Conceptually PathCoin is quite exciting from a 'cypherpunk dream' standpoint!

@VzxPLnHqr

Is it possible, if nothing else for sake of making it easier for us to understand, to shrink the concept of PathCoin down to N=2 participants (Alice, Bob) with then the goal of allowing for an (ideally) unlimited number of cycles where Alice assigns the UTXO to Bob and then Bob assigns it back to Alice?

The cycling infinitely idea - while enormously appealing of course - I haven't yet seen a way of making that kind of thing work. The construction here is basically, boiled down, "define in advance who are the ordered list of owners; commit a penalty bond that allows a transfer to work (the ordering is embedded in the penalty bond construction, so it can't be changed); then pass signatures + (special sauce allowing penalty to actually work in a multiparty case), corresponding to each transfer".

So the sequence of payments that can happen has to be defined in advance (with a mild caveat that what I said above in response to Zmn might allow jumping certain steps in the path - but still only forwards direction in that predefined path).

(I should also note the obvious, that you can make a path A B A B .. , though not infinite, but it doesn't seem that interesting compared to other things you can do with two parties .. probably).

Certainly not saying it's not possible, but it will require something else, so not discouraging people to think about it...

@AdamISZ

The cycling infinitely idea - while enormously appealing of course - I haven't yet seen a way of making that kind of thing work. .... Certainly not saying it's not possible, but it will require something else, so not discouraging people to think about it...

Understood. Thank you for clarifying.

So the sequence of payments that can happen has to be defined in advance

Right. So, as you indicated, an obvious way to form a finite cycle would be to enumerate and encode a path A --> B -->A --> .... ---> A --> B --> A. It still seems like it could be useful/interesting. I suppose at that point it is basically a deterministic lightning channel if such a thing exists?

Right. So, as you indicated, an obvious way to form a finite cycle would be to enumerate and encode a path A --> B -->A --> .... ---> A --> B --> A. It still seems like it could be useful/interesting. I suppose at that point it is basically a deterministic lightning channel if such a thing exists?

I don't think there's much value in it, because it's just swapping ownership of one coin, rather than updating balances as in the Poon-Dryja payment channel. This denomination limitation is very severe (see the same issue in statechains - it's useful if it can be scaled up to thousands of instances, or for special situations (privacy protocols, perhaps) but it can be very limiting unless you can bolt things on, like Lightning channels out of a fixed denomination utxo) (and more specifically, this existing 'PathCoin' construction can't scale up massively due to the fidelity bond).

In the process of coding this, came up with the following concept, and want to write it down before I forget:

Resetting, and maybe netting?:

One of a few ways to bring this construct to being closer to practically useful, would be to be able to revert or pay back payments along a path. This could extend to netting out transfers ("netting" is the common term in traditional finance, but "transaction cut through" is a very similar idea that bitcoin developers will have heard of). But resetting is already a meaty enough topic here, so I'll focus on that :)

Concretely, imagine a pathcoin PC1(A, B, C, D, E), where the parentheses indicate the fixed direction of transfers between the participants.

How could C "give back" (reset) PC1 to A? I now believe something like that is possible (a bit contrary to what I said in earlier comments), with limitations:

To reset the state so that A can spend, you need to restart the whole signing session. The keys of each participant are P_A, P_B, P_C, P_D, P_E, and we still use them, so we are still using the same address/scriptpubkey for PC1, call it sPK_1. If we make a new MuSig signing session (so new nonces), and partial-sign transactions spending out, as before, to destinations for A, B, C, D, E respectively, then we can do the same pathcoin partial signature sharing, on the same sPK_1 as before, with A "owning the coin" because they have partial sigs already for B, C, D, E.

"owning the coin" is in scare quotes there of course, because the previous signing session still exists. C can still spend PC1. But C could give the adaptor signature on her own part of the original signing session, to A. The original fidelity bond design doesn't work for this though:

(C and TLC) OR (CTV(tC) AND H(SC) -> (D and TLD) OR (CTV(tC) AND H(SD) -> E)))))

This only allows C's fidelity bond to be claimed by participants further along the path (D or E), not by A. It would be wrong to just say "add a clause for A which is spendable immediately with some cancellation secret" because this reintroduces collusion risk during normal (pre-reset) operation. The purpose of that structure was to say "if C illegally spends, let the coin move forward through the airlocks, to the exact current owner", so to speak. It can't just go to anyone with a secret, because that person could be colluding with C.

However if we are renegotiating a whole signing session, we can also all share more secrets to invalidate that first signing session. The simplest solution I can think of is to add an extra clause up front to the fidelity bond, that allows the fidelity bond to be claimed back to its original owner, only on condition that all (other) counterparties agree:

(C and TLC) OR (A and H(B_cancel) and H(C_cancel) and H(D_cancel) and H(E_cancel) and T_C) OR (CTV(tC) AND H(SC) -> (D and TLD) OR (CTV(tC) AND H(SD) -> E)))))

In words, the extra OR clause here says "pay out C's fidelity bond to any destination (no CTV), with no timelock restriction, to the owner of A, if they also have the adaptor secret t_C, and they have received cancellation secrets from all other parties in the pathcoin".

Notice that this clause has to have time preference over all the others.

The preimage corresponding to these X_cancel hashes could be handed over only in event of a reset. During normal operation, i.e. pre-reset, each party is protected from collusion by others, by not handing over this preimage. But if, after reset, the owner of the pathcoin PC1 from the first signing session (which is C) chooses to illegally spend it, they reveal t_C and thus A fulfills all of that OR clause and gets the fidelity bond immediately (before all timelocks).

The actions in summary:

• C holds PC1, wants to give it back to A.
• Everyone has to get back together (a big coordination issue, but we assume the event is not the normal one).
• Make a whole new MuSig signing session (on the same musig pubkey) reassigning ownership to A.
• C hands over adaptor to A.
• Everyone else apart from A hands over the cancellation secret.
• A can now consider themselves owner of the coin again, on the new signing session, as long as we stay before the original timelocks.

... but we note the following limitations:

• The "cancellation clause" has to be set in the original fidelity bond. i.e. we have to anticipate that this might happen, perhaps not a big deal.
• The new coin has to honour the same timelocks (does CSV usage change that? my suspicion is no)
• Everyone has to re-coordinate to do a new signing session. Thus resets are not just some spontaneous thing.
• State accumulates as we add more signing sessions.

Just briefly at the end, to state the hopefully obvious: that if such resetting is possible, it dramatically increases the extent to which this construct could be useful, as you could pay back and not only pay forward, in a single coin.

(Netting: imagine that A funds PC1 with 1btc and C funds PC2 with 1btc. Then, during normal usage, A pays B and B pays C in PC1, so the state is that C holds PC1 (value 1). And similarly in PC2 C pays B who then pays A, so that A holds PC2 (value 1).

An interesting efficiency is to "net out" these two transfers as their aggregate cancels out; A is owed nothing and C is owed nothing.)

Happy to see that you are still thinking about pathcoin (and even coding it up?), and this seems to be an exciting step forward!

With some of the latest bitvm developments, such as using op_codeseparator to allow for reprogrammable tapleaf logic gates, I am now wondering if there is some way we can improve the pathcoin fidelity bond situation too. Then again, maybe there is no way around each participant needing to post a FB of amount slightly greater than U, at least not without losing incentive compatibility.

Made some edits to the introduction to change to "keypath spending on 5 of 5 MuSig, in 5 different signing sessions" instead of "script path spending on 5 possible taproot leaves with 5 of 5 with different keys" because the former is way easier and more practical and, also, this is the model I used here:

https://github.com/AdamISZ/pathcoin-poc

May well make a few more minor edits, based on that coding writeup.

I've rather substantially changed my view of this whole construction over the last few days. I see now, more of a spectrum of possibilities here:

1. Describe a general script template like "(P_A and CLTV) OR (S_A and CTV)" as a "covenant time locked contract" or CTLC. The various setups are all using that as the root primitive ("S_A" is shorthand the image of any secret preimage initially created/owned by A, not limited to adaptor secrets).

2. The simplest version of the idea is that A can on-the-fly create a chain of CTLCs paying a path A,B,C,D,E say - but with a small caveat that A has to be able to define the secret-unlock image S_X for all participants X, to construct the scripts. That seems pretty trivial if they have some existing key e.g. P_C for C, that you can tweak, using various mechanisms, so I'll treat that as unimportant for now). Let's call this "Optimistic Pathcoin". With no collateral/penalty requirement, A can set up a PathCoin to B, C, D, E and each can send their secret S_X to participant S_{X+1} to effect transfer. Some commentary on that setup:

   2a. In case it isn't clear, this explicitly means, not MuSig, but A directly paying into a script:

(A AND CLTV) OR (S_A AND CTV ->)
(B AND CLTV) OR (S_B AND CTV ->)
(C AND CLTV) OR (S_C AND CTV ->)
(D AND CLTV) OR (S_D AND CTV ->)
E

(as before, the arrows mean "the CTV enforces payment into the next script". Each scriptPubKey here has only one "A or B" structure, there are 5 scriptPubKeys here, including the plain "E" at the end).

2b. "Optimistic PathCoin" comments: this structure is maximally flexible to setup, but, in itself, fails to remove on-chain footprint, so it's at best a "L1.5", certainly not an L2. It allows immediate and off-chain p2p transfer between participants in the path, but it doesn't get more privacy, really, nor save on fees. Moving the funds on chain is also timelocked. It's instructive to compare it with Rubin's "congestion control" structure. There, there isn't optionality of paying, all payments are defined, there is just finesse on when they happen. Here we have optionality on whether each transfer occurs. Additionally, while congestion control can take great benefit from using script trees instead of single paths, here we cannot do that because we have an off-chain double spend problem if there are multiple paths which can be traversed with p2p secret transfers.

3. The most complex version of the idea is the one originally laid out in this gist, which I'd call "Private PathCoin". It puts all the CTLCs into side-transactions "fidelity"/"penalty" bonds. This means that the main pathcoin, controlled with MuSig and adaptors for linkage to the side transactions, behaves like pure p2tr keypath spends, and it also means that we don't need timelocks for that coin. But the (more than) 100% collateral requirement for this "Private PathCoin" makes it less likely to be appealing in practice, and also, this "non-optimistic" variant requires everyone to do a coordinated signing step in setup (as described here and in the POC code).

4. At least one hybrid might make sense: have 5 signing sessions as in PrivatePathCoin, but have the transaction being signed in each case, pay to the chained CTLC construct illustrated above. So here we might regain the privacy (finessing presigning timelocks), and we definitely get the removal of onchain footprint, and we can claim to have removed the nasty collateral requirement again, but we have a thorny incentive problem: an enforcement by traversing e.g. three CTV clauses, must of necessity require more fees, so an illegal spender higher up the path, while they cannot steal the money (because the real owner will claim it via the CTLC chain), can grief the current real owner, forcing them to pay more fees. A way to prevent the honest holder from being punished by others' bad behaviour is required.