Factom has had SegWit from the beginning, due to a compromise

After telling some of this to a few Bitcoin core devs, Adam Back urged me to tell the story more widely. Factom had implemented something like SegWit long before the November 2015 announcement.

In the Summer of 2015, Paul Snow and I were putting the finishing touches on the Factom blockchain design. Lots of protocol polishing was happening. For example, we were agonizing over SHA3 not actually being finalized, despite a winner being declared in 2012.

I like to describe Factom as a mangrove of Merkle trees. It is a tangled hierarchy of different sub-blockchains that have multiple cross references.

One of the sub-chains manages the internal anti-spam token, factoids. We knew that malleability was a huge problem, and if handled poorly would totally break the system. Factom is account based, rather than UTXO based like Bitcoin. Malleability in Bitcoin will break individual user transactions, especially chains of unconfirmed transactions. The miners are mostly unaffected by maleability. In Factom, however, all the Federated Servers need to come to identical agreement on all the transactions. This means that if some of the servers across the P2P network saw a different malleated version of the same transaction, consensus would fail.

We thought we got rid of 3rd party signature malleability, but someone with the private key can always malleate their own transaction. Since Factom is account based, the transactions are considered unique if the inputs, outputs, and a timestamp are the same. Having a different signature on the same in/out/timestamp would hash to a different value, but would be considered the same transaction. One of them would be a doublespend, and would be invalid.

There were two ways to solve this problem which had two different philosophies.

The first philosophy was to have the entire transaction, signature and all, be included as part of the block hash. This would lock the transaction down for all time, but would cause some heartache on the P2P network. If two malleated transactions existed on the network at the same time, the P2P network would have to sort it all out before proceeding. This is the same as any other doublespend, though.

The second philosophy was to leave the signature out of the block hash entirely. Malleability would not be a problem, since every node could safely have completely different malleations, and still create the same block hash. Later, when these blocks are old enough, their signatures can be deleted, and just the balance changes retained. These ledger balance updates could still be proven to be complete because their hashes would still match.

I saw it as optimizing for the future vs optimizing for the present.

By ignoring malleability, some odd things become possible. With a multisig transaction, it would be ambiguous who authorized the transaction. For example in a 1 of 2 tx, signer A would make the transaction. Years later, signer B could substitute his signature into the block, and it would appear B had originally signed. It was a matter of perspective if this would be a problem. To some, it doesn’t really matter how the transfer was authorized. To others, it would matter a lot.

It would also no longer be possible to trust signatures of transactions just because they were in a block. If you wanted to re-propogate the historical blocks, you would need to check the signatures yourself before saving and passing them on. It would hamper efforts to download factoid blocks with less than full validation, like Bitcoin does with blocks before checkpoints.

On the other hand, hashing the entire transaction would mean that there would never be an opportunity to forgo downloading historical signature data. You couldn’t know if you downloaded the right data, since there wasn’t a hash to match the partial data against.

Our discussions about this long term scalability design got pretty heated. It was not uncommon for Paul’s famous juggling balls to be turned against me in response to a perceived frivolous technical argument. I suppose this was only fair after I caused him to jump out of his skin so many times.

The compromise was to build two Merkle trees. One Merkle tree hashed the entire transaction. The other only hashed the ledger part of the data (inputs, outputs, & timestamp). While this would make the P2P network deal with malleated transactions in the present, it would allow future users to skip downloading large amounts of data when determining token balances. It also preserved the immutable nature of the entire transaction, rather than just the ledger data.

Neither side quite got what they wanted, but the result allows for more client flexibility in the future.

Note: this scheme did not have a name at the time. It was only months later that the BIP-62 proposal was dropped and the term “segregated witness” came into the public eye. I was instantly a fan back in November 2015, because of the similar design we had worked out. I really hope it comes to fruition in Bitcoin too.