While I’ve previously touched on the topics of commitments and single-use-seals, my previous posts have been both highly technical and high level.

Here we’ll use a concrete example - a Bitcoin exchange attempting to prove their solvency - where commitments and single-use-seals can detect and prevent consensus fraud: two different people given different versions of what should be the same data. We’ll explain what commitments and single-use-seals are. We’ll work through this example in detail with actual proofs using a mock human readable format and verify those proofs by hand against the actual Bitcoin blockchain. Finally, we’ll discuss the bigger picture of what we were preventing and why conventional cryptographic approaches are ill-equipped to solve that problem.

Thanks goes to Christopher Allen/Alacrity Software for financially supporting this research.

Contents

  1. Two Sets of Books: Consensus Fraud
    1. The Privacy Problem
  2. Commitments
    1. Nested Commitments
    2. Commitments to People
  3. Single-Use-Seals
    1. Trust-Based Single-Use-Seals
    2. Bitcoin Transaction Outputs as Single-Use-Seals
      1. Verification
      2. Defeating Miner Censorship
    3. Single-Use-Seals for Globally Consistent, Updatable Key-Value Maps
      1. Fake Single-Use-Seals
  4. The Big Picture - Rivalrous Systems and Consensus Amplification
  5. Footnotes

Two Sets of Books: Consensus Fraud

Suppose that the Acme Bitcoin Exchange wants to give their customers confidence that their wallets do in fact have control of sufficient BTC to cover the account balances of all their customers at all times. They do the usual marketing fluff like videos showing off their fancy data center, protected by retina scanners and mantraps, and housed in a former missile silo. But they also go a step further: they decide to prove to their customers that even if all that fancy security failed and funds got stolen, the truth would come out.

In short, Acme wants to prevent anyone - be it a hacker or even Acme themselves - from being able to hide the fact that the exchange doesn’t have sufficient BTC to allow all their customers to withdraw their BTC balances.

Since Bitcoin is a crypto-currency, Acme can cryptographically prove they have the technical1 ability to spend a certain amount of BTC as of a particular time. We don’t go into the details of exactly how this might be accomplished, but basically this can be done by signing “dummy” transactions proving that Acme could have signed real transactions that actually spent the funds. Secondly, Acme proves that the coins themselves are uniquely allocated2 to them, ensuring that two different exchanges aren’t sharing the same pool of funds.

If Alice knows her account balance should be 10 BTC, proof that Acme has control of 79 BTC in total isn’t very useful by itself: she has no idea how much Acme owes the other customers. So let’s have Acme publicly publish the full list of accounts once a day along with the coin control proof:

Acme Bitcoin Exchange Solvency Proof
====================================
Nov 20th 2016

Alice   - 10 BTC
Fred    - 17 BTC
Mallory -  5 BTC
Pia     - 14 BTC
Wendy   - 33 BTC

<proof Acme controls 79 BTC as of Nov 20th 2016>

What happens if Acme suffers a theft or loss? If the account balances are left unchanged, the above scheme makes the theft immediately obvious: the total account balances will be greater than the coins Acme has been proven to control.

On the other hand, if either the thief or Acme try to cover up the theft/loss by reducing account balances, detection depends on the vigilance of the account holders. For example, Acme could try to hide their losses by artificially decreasing the balances of the least often used accounts - particularly accounts that had been frozen by AML/KYC investigations - in an attempt to make the books appear balanced.

Still this is a good start! While smaller thefts may not be detected in a timely fashion - if at all - we’ve at least made it likely that a larger theft will be detected, preventing further losses from customers depositing funds post-theft.

The Privacy Problem

Obviously it’s undesirable to make the complete set of account balances public. What if we at least limit access to Acme customers by requiring you to login first?

The next day Alice logs into her account, and downloads the most recent solvency proof:

Acme Bitcoin Exchange Solvency Proof
====================================
Nov 21st 2016

Alice   - 10 BTC
Fred    - 12 BTC
Mallory -  5 BTC
Pia     -  4 BTC
Wendy   - 18 BTC

<proof Acme controls 49 BTC as of Nov 21st 2016>

Looks good! Alice’s 10 BTC is there as expected; some people took funds out, but that happens sometimes.

Next Wendy logs in:

Acme Bitcoin Exchange Solvency Proof
====================================
Nov 21st 2016

Alice   -  3 BTC
Fred    -  6 BTC
Mallory -  5 BTC
Pia     -  2 BTC
Wendy   - 33 BTC

<proof Acme controls 49 BTC as of Nov 21st 2016>

Looks good! Wendy’s 33 BTC is there as expected; some people took funds out, but that happens sometimes.

Obviously we’ve got a problem: the exchange gave Alice and Wendy different solvency proofs, fraudulently hiding a recent hack by allocating the losses to different sets of accounts each time.

Commitments

We can solve this problem with a cryptographic commitment, specifically a public commitment. In summary, a commitment constrains what you can do in the future, based on data that exists today.

Now Acme hashes each daily solvency proof with a cryptographic hash function, producing a digest. The digest is then published on their website on a commonly used3 public page, such as in a specially marked, hidden, HTML comment on the front page.

Acme’s customers can now verify the solvency proof by first visiting the website anonymously (perhaps over Tor), and second logging into their account and downloading the (still-private) audit data. So long as the solvency proof data matches the commitment, they can be confident that they’re seeing the same solvency proof that everyone else sees; the exchange has committed to the data in advance because it’s not possible to generate two different solvency proofs that hash to the same digest.

Nested Commitments

Can a commitment commit to another commitment? Absolutely! Let’s look at how this works with an example of a human-readable merkle-sum tree.

The Acme Bitcoin Exchange has grown to a few hundred customers, and now splits up the solvency proof alphabetically by account:

Acme Bitcoin Exchange Solvency Proof
====================================
Nov 22nd 2016

A-E - 345 BTC - 81172c7b672cc7efc445f95314767501941057f785fd473fd42b637bdc70990c
F-J - 940 BTC - 73daa77f508a6969aed58a95c7f0ef2a5c2c50932bfea5374754db6537ccfa01
K-O - 195 BTC - bccab88791ffc367b465d045fd13d38a18f22d7bc6eaefe00a60a64f506ecd48
P-U - 526 BTC - dc64d99c3052e5e37380700bfef7f88a12ae33412a224ee91701153975d93715
V-Z - 160 BTC - 604a61ba7f3f3168ff9adb8ef6b88c335bd6ba3a01f2297d3e217bc11a16b16f

<proof Acme controls 2166 BTC as of Nov 22nd 2016>

Suppose Salma wants to verify her account balance is correctly included in the solvency proof. The top level solvency proof commits to a subtotal for all accounts in the range P-U; S is in that range, so she checks the corresponding data with that hash digest:

P -  41 BTC - fb4d8d790a7a6bbce2410109e493ca3c3695d76f8ae1dde1ad89504f4ac8ad84
Q - 120 BTC - 5fc956617833df39eeac500c32e0a5addfe931c4b28acd5d9f317656234c6fef
R - 148 BTC - e5e11ac66918cd2346b7ed7e16d1cdd60d9508c0202d9347f048aa9de3e4ddbf
S -  71 BTC - 8e4619b9440f269773b8f66954d44cf7d0ee2d31f76f3b5f1fdb1d75559c6971
T -  56 BTC - 2c78c4759d5ac14a456dba2ba79b0d213e8594b6b924a9cb14543a73a68b5957
U -  90 BTC - 6257950b3b48df66291383c68a46310ed032f807527f3b5141ef135ee100cf51

It’s another set of subtotals, this time for accounts starting with specific letters. Here’s the one with her name in it:

Sage  - 15 BTC
Salma - 24 BTC
Simon -  5 BTC
Sonya - 13 BTC
Stan  -  2 BTC
Stark - 12 BTC

Is this new scheme secure? While I could give you a math proof, let’s look at this more intuitively. First of all, the path down the three levels of proof is fixed in stone: what each digest commits to is unambiguous. So just like our single-level proofs, she has successfully verified that her account balance is recorded properly - there’s exactly one place where it could be in the whole data structure. Secondly, she can verify that the account balances she has access to sum up correctly.

Does it matter that she wasn’t able to verify the sums in parts of the proof that she didn’t have? For example, she has no idea if the subtotals corresponding to accounts starting with “Z” were correct: she just doesn’t have that data.

Which is the problem: she has no idea what account balances any account but her own should have. Thus the only thing she could verify is that the numbers added up correctly. Any actual attacker trying to pass off a fraudulent solvency proof would make sure the fake numbers they used added up, so it doesn’t matter that she didn’t verify that part of the proof.

Another way to think about this is verifying a solvency proof is like doing a distributed parallel computation where each participant only has a part of the dataset. Everyone checks that their part of the computation is correct, and the results are combined together in layers. The subtotals in this case are simply intermediate results of that computation.

Finally, note the privacy improvement: we no longer need to give every customer a full set of account data. An actual implementations of this concept would use a binary tree rather than our silly human-relevant alphabetical scheme, which in conjunction with a customer -> nonce mapping, can prove solvency without giving any information at all about the account balances of other customers.

Commitments to People

Speaking of actual implementations, our examples have all used normal human (first) names. Obviously this is a problem if two customers happen to have the same name, so we’d have to allow customers to use a different identifier to login that was unique, like an email address or user-name.

Homework problem: If the solvency proof continued to use customer’s names, but you logged into the Acme Bitcoin Exchange with your email address, what could go wrong? I’ll give you a hint: Should you be suspicious if your account balance in the solvency proof is higher than you expected?

Single-Use-Seals

While simply publishing a commitment on a website is a good first step, there’s still a lot of vulnerabilities, and it’s hard to automate. For example, it’s difficult to be sure you’ve actually gotten the commitment anonymously; any failure to do so makes it possible for the exchange to hide a shortfall by showing different commitments to different people. Timing is a problem as well: if an exchange knows a major customer is on vacation for a few days, they can temporarily cover up a loss by lying about that customers balance until they get back.

Now imagine if we had a way to securely commit to data that doesn’t yet exist. We’ll call this mechanism a Single-Use-Seal, by analogy with the physical uniquely numbered single-use-seals commonly used to detect tampering during storage and shipment:

Physical Single-Use-Seal

Each cryptographic single-use-seal is associated with a globally unique identifier. Single-use-seals start off in the open state, and can be closed over a message after the fact, producing a proof that the seal has been irrevocably bound to the message. A single-use-seal is secure if it’s infeasible to produce two apparently valid proofs that the same seal has been closed over two different messages.

Since the message a seal is closed over can itself commit to another seal, we can create complex data structures such as linked lists and merkle trees from single-use-seals seals; a single-use-seal can be used anywhere a commitment would otherwise be used and in turn, nearly all uses of hash functions in data structures are in fact forms of commitment.

Trust-Based Single-Use-Seals

The simplest form of single-use-seal is for closed-seal proofs to be signature-based and simply trust that the seal will never be closed twice. While this isn’t particularly secure, it’s can be a good way to formalize a trusted entities role. For example, in our above discussion of the Acme Bitcoin Exchange’s solvency proofs, we suggested that commitments be published on the exchange’s website. But that creates a problem: How do you prove the exchange misbehaved? A little-known fact about HTTPS is that it’s not normally possible to cryptographically prove to a third party what the contents of a HTTPS website were, so accusations of fraud could be dismissed as mere hearsay.

PGP signing the daily solvency proof solves that problem:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Acme Bitcoin Exchange Solvency Proof
====================================

Alice   - 10 BTC
Fred    - 17 BTC
Mallory -  5 BTC
Pia     - 14 BTC
Wendy   - 33 BTC

<proof Acme controls 79 BTC as of Nov 20th 2016>

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJYRYKZAAoJECSBQD2l8JH7dWQIAIh/9+k24+gZV2m5v5WQydUG
YJL+965SPWc2m30cWoek3IcCdv9SyUzjcdIqa6tzhTeJ5VeLw+tHX5Ze5qXUKToi
xdveQdHLATGm/KRpTwd5XCDnBeQtmclmv5yvmrNSR7DyVjGKqtZqGM37Ee5hEYfE
187T6vNBvwhxY1l261gxDjFE72EszzxM7IBdBsVcG7q7Lv1zCzThCqzHguj1zMj0
itvmY6HVbz0cao9LrpFIhQ6Zq8LDrfVtwM9gqOhjzKcP2mjDl6b9WoIf5ex8blZY
YovhtyvKRPhtstL2ABLplvzPjIQJeh2BzTstMV879U0VCZN1JEqdV+3D62PZsQo=
=5Q1f
-----END PGP SIGNATURE-----

Essentially the above is proof that the seal “Acme Bitcoin Exchange Solvency Proof - Nov 20th 2016” was closed over the Nov 20th 2016 solvency proof. And while it was technically trivial to close that seal over the following duplicate message, the fact that these two signed messages exist is unambiguous, non-repudiable, evidence of fraud:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Acme Bitcoin Exchange Solvency Proof
====================================

Alice   - 30 BTC
Fred    - 17 BTC
Mallory -  5 BTC
Pia     - 14 BTC
Wendy   - 13 BTC

<proof Acme controls 79 BTC as of Nov 20th 2016>

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJYRYLvAAoJECSBQD2l8JH7ARkH/02sZS9A4+l9wlxo+AyohR0/
H46o1MZSRSpG6HHQ57SCL3/7dsrpjFS9gnqFdpAoa3ejVLy2VTY3E4j/RZoFDFIB
JD7bRujiIu1OZwx7Uznf5UB9UCTGDoqtEW8Ucbl5trZxad/G8NzaNzr7o4/DxF7B
blPa2zYRnfdQQYX7QWW1UrDerb9lW509IX4R1cEdTGczSpQ2uPvpindX57yOaXV2
H2qD4vfRyFROghwccjKzSHSbXduFt3j3xQJq+cHBQlxIZs9GixGk9uaEY7oZ7TPY
2YLe6nJXJeAc/PgH0XUh5blB7ecjlc6cI9m1g3zBTIEyKRk4cBSc2vSw4aSzK0o=
=qPeQ
-----END PGP SIGNATURE-----

Bitcoin Transaction Outputs as Single-Use-Seals

Since transaction outputs are both uniquely identifiable, and can only be spent once, they can be used to implement single-use-seals that are just as secure as Bitcoin itself.

Let’s add single-use-seals to our previous example of the Acme Bitcoin Exchange’s solvency proofs. Remember that our goal here is to ensure that for a given day, all customers receive the same solvency proof. We’ll even do this for real, using actual Bitcoin mainnet transactions.

First, we create the genesis seal: b8b86d41647db9eb4fcb833cc685eb1264d7c3d2b8fb056551b3388e8c35a43b:1 This is simply a txout that we are able to spend.

At the end of the day, we create our first solvency proof:

Acme Bitcoin Exchange Solvency Proof
====================================
Dec 1st 2016

Alice   - 10 BTC
Fred    - 17 BTC
Mallory -  5 BTC
Pia     - 14 BTC
Wendy   - 33 BTC

<proof Acme controls 79 BTC as of Dec 1st 2016>

To make that solvency proof official, we need to close our genesis seal over the proof. However we can’t do that directly, as we need to commit to another open seal in the process so we can create the next day’s official solvency proof. So we pick another txout to use as the next seal, and commit to both with a separate header:

 Solvency: 534a405f376cd55c7cd41676dd728a729d0c536385e2e6e0beb7257bac752c01
Next Seal: 5b6705437ced5cca8ec52cfb187e5d3270e067817c4fcd5a26755d4ceb4c010c:0

Finally, genesis seal’s txout is spent. We’ll say our seal protocol specifies that a valid close transaction be a transaction whose last txout be an OP_RETURN with the SHA256 digest of the message the seal was closed over. Thus tx 976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5 closed the genesis seal over the above message, which in turn committed to the Dec 1st solvency proof.

Let’s do that again for the next day’s solvency proof:

Acme Bitcoin Exchange Solvency Proof
====================================
Dec 2nd 2016

Alice   -  5 BTC
Fred    - 15 BTC
Mallory -  3 BTC
Pia     - 10 BTC
Wendy   - 35 BTC

<proof Acme controls 65 BTC as of Dec 2nd 2016>

The associated header is:

 Solvency: 8c055d6890ab8b315618c3ba0c89ec83bc0291ae43c93ee0edc238b7865f09f3
Next Seal: c68fe1abc91e294c600911fc17db71ee627c9f3ad0fcf428c34fd1e804ed9859:0

Finally it’s made official by tx 19c2aa81cf6a0bf7d1f20810ca72baac44cb2532d765e162b0d58b4e050ff3af, which closed the previous day’s seal by spending the output 5b6705437ced5cca8ec52cfb187e5d3270e067817c4fcd5a26755d4ceb4c010c:0

Verification

Let’s try verifying the seal chain. An actual deployment of this idea for solvency proofs would almost certainly automate the verification process - e.g. with an app that the user could download and run client side. But we’ll do this by hand to fully understand the process.

First we need to know what the genesis seal is. Remember that what we’re trying to do here is verify that our copy of any particular solvency proofs is the same copy everyone else has; much like the similar problem of getting the right PGP key if we’re tricked into using a different genesis seal the entire process fails. Fortunately we only need to do this successfully once; an actual implementation with an automated verifier - perhaps downloaded from an app store - could include the genesis seal with the verifier.

The transaction that closed the genesis seal over that header was 976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5. Rather than relying on a (potentially untrustworthy) block explorer, let’s use Bitcoin Core v0.13.0’s new txout proof functionality to make sure that transaction is real and in the main chain:

$ wget https://petertodd.org/assets/2016-12-07/tx-proof-976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt
$ bitcoin-cli verifytxoutproof `cat tx-proof-976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt`
[
  "976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5"
]

That proof is in fact the block header of the block containing the transaction, and a merkle path proving that the transaction was contained in the block; it’s only 1KB in size and can be verified by pruned nodes and lite clients. To verify that the genesis seal was closed we deserialize the transaction, making sure that its txid is correct:

$ wget https://petertodd.org/assets/2016-12-07/tx-976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt
$ bitcoin-cli decoderawtransaction `cat tx-976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt``
{
  "txid": "976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5",
  "hash": "976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5",
  "size": 234,
  "vsize": 234,
  "version": 1,
  "locktime": 0,
  "vin": [
    {
      "txid": "b8b86d41647db9eb4fcb833cc685eb1264d7c3d2b8fb056551b3388e8c35a43b",
      "vout": 1,
      "scriptSig": {
        "asm": "3044022032bb36a1a9cf4e7bb3fb46e19222c44f21947ab2ac4b935e6d25eecc96f15f5b02204d903b7cbdaab5d69ed1e4cb595d3ec94e1e4c0a0231bd36b5f954f7d26d4725[ALL] 0361d98ae65e38a8a360f7710a990e1e2512c1047f75d42c91118e1720d2cc13a7",
        "hex": "473044022032bb36a1a9cf4e7bb3fb46e19222c44f21947ab2ac4b935e6d25eecc96f15f5b02204d903b7cbdaab5d69ed1e4cb595d3ec94e1e4c0a0231bd36b5f954f7d26d472501210361d98ae65e38a8a360f7710a990e1e2512c1047f75d42c91118e1720d2cc13a7"
      },
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.01450000,
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 452c4d0744a4b211f61c59ece60ca34f0c53c81c OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a914452c4d0744a4b211f61c59ece60ca34f0c53c81c88ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "17JkhKLroUoT1Urtphdrqbrkkpuh2WpKpv"
        ]
      }
    },
    {
      "value": 0.00000000,
      "n": 1,
      "scriptPubKey": {
        "asm": "OP_RETURN d28a129cd4475132846a49f84a85fc8cad4330622a6a8103a3e8c446f3d9ae4c",
        "hex": "6a20d28a129cd4475132846a49f84a85fc8cad4330622a6a8103a3e8c446f3d9ae4c",
        "type": "nulldata"
      }
    }
  ]
}

We can see that the transaction did in fact spend the genesis seal’s txout, closing that seal over the message with the SHA256 digest d28a129cd4475132846a49f84a85fc8cad4330622a6a8103a3e8c446f3d9ae4c. We download the first header file and check that its digest matches:

$ wget https://petertodd.org/assets/2016-12-07/acme-solvency-proof-dec-2nd-2016-header.txt
$ sha256sum acme-solvency-proof-dec-2nd-2016-header.txt
d28a129cd4475132846a49f84a85fc8cad4330622a6a8103a3e8c446f3d9ae4c  acme-solvency-proof-dec-1st-2016-header.txt

Now we can check that the header commits to the solvency proof:

$ cat acme-solvency-proof-dec-2nd-2016-header.txt
 Solvency: 8c055d6890ab8b315618c3ba0c89ec83bc0291ae43c93ee0edc238b7865f09f3
Next Seal: c68fe1abc91e294c600911fc17db71ee627c9f3ad0fcf428c34fd1e804ed9859:0
$ wget https://petertodd.org/assets/2016-12-07/acme-solvency-proof-dec-2nd-2016.txt
$ sha256sum acme-solvency-proof-dec-2nd-2016.txt
8c055d6890ab8b315618c3ba0c89ec83bc0291ae43c93ee0edc238b7865f09f3  acme-solvency-proof-dec-2nd-2016.txt

Great! Provided that Bitcoin itself is working, we’ve successfully downloaded the first solvency proof and verified that our copy of it is the same copy everyone else in the world has. We also know what the seal for the second solvency proof is; you can verify it by downloading the tx proof, tx, header, and solvency proof and repeating the above process.

Note that so long as the Bitcoin block chain isn’t reorged, all of the above is secure even if the private keys used to sign the transactions are leaked, because an attacker with those keys can’t re-spend previously spent coins. In fact, I’ll even give you that wallet.

Defeating Miner Censorship

A potential issue with using Bitcoin to implement single-use-seals is miner censorship:

  1. Miners who learn the txout associated with the seal can censor transactions spending that txout.
  2. Miners can censor OP_RETURN outputs in general.

We can solve the first problem by making use of a blinding nonce that’s kept secret4 until the transaction closing the seal has been mined. The way the transaction commits to the message is changed from simply putting the hash of the message directly in the transaction to putting H(nonce + H(message)) instead5. Finally, rather than publishing the seal directly as we did before, a commitment to the seal is published; the seal itself is now the outpoint and nonce, and is provided as part of the proof that the seal has been closed.

As for the second problem, the protocol for how seals are closed can be modified to allow the message to be committed in ways other than OP_RETURN outputs, e.g. unspendable outputs, multisig outputs, or via pubkeys/signatures with ECC math tricks like pay-to-contract-hash. Just make sure that the protocol is such that all the different commitment methods are guaranteed to be mutually exclusive, least it become possible to generate multiple valid proofs of the same seal being closed in different ways.

Single-Use-Seals for Globally Consistent, Updatable Key-Value Maps

The linear chain we described previously is inefficient when an exchange customer only needs to verify a subset of all solvency proofs, such as the most recently generated proof; a linear chain of seals forces them to download all solvency proofs even if they only need to verify the most recent one.

An obvious solution to this problem is to use a tree structure, with multiple levels of seals. In the case of an exchange, an obvious way to do this is to divide the levels by year, month, and day. Thus rather than having a genesis seal, you would have a genesis seal list:

Acme Bitcoin Exchange Solvency Seals - By Year
==============================================

2016: <per-year seal>
2017: <per-year seal>
2018: <per-year seal>
2019: <per-year seal>
2020: <per-year seal>

By month:

2016 Acme Exchange Solvency Proof Seals
=======================================

Jan: <per-month seal>
Feb: <per-month seal>
...
Nov: <per-month seal>
Dec: <per-month seal>

By day:

Jan 2016 Acme Exchange Solvency Proof Seals
===========================================

1st: <per-day seal>
2nd: <per-day seal>
...
31st: <per-day seal>

Of course, actually doing this would be a bit silly; any sane programmer would come up with a more generic solution that could be applied regardless of what type of key is being used to index the tree. On the other hand, seals are relatively expensive - just implementing a binary tree of them doubles the total number of seals needed - so we want a n-ary tree. Can we do better while keeping the code generic?

Fake Single-Use-Seals

Recall that a single-use-seal is simply a thing that can be uniquely identified, and can be closed to commit to a message. So from the point of view of the verifier, does it matter if the seal was ever open? Of course not! Thus cryptographic hash functions (aka commitments) can also implement perfectly good single-use-seals!6

Concretely, a single-use-seal trait7 written in Rust might look like the following:

trait SingleUseSeal {
    type ClosedProof;
    
    fn verify(&self, &Self::ClosedProof, msg: &[i8]) -> Bool;
}

A fake single-use-seal implemented with SHA256 might look like:

struct SHA256_FakeSeal {
    digest: [u8; 32],
}

impl SingleUseSeal for SHA256_FakeSeal {
    // Fake seals are always closed, so we don't need any extra data to
    // prove that.
    type ClosedProof = ();
    
    fn verify(&self, &Self::ClosedProof, msg: &[i8]) -> Bool {
        self.digest == SHA256(msg)
    }
}

Now we can write a generic, binary, seal tree implementation. Each inner node will commit to left and right seals as you would expect, but we’ll replace multiple levels in the tree with sub-trees of fake seals that commit to a smaller number of real seals. In short, we now have the equivalent of an n-ary tree where we can pick n appropriately at runtime, that to the rest of the codebase acts like a binary tree.

The Big Picture - Rivalrous Systems and Consensus Amplification

A Bitcoin exchange is just one of many examples of systems that are rivalrous. By that, we mean that one user’s use of the system is in competition with other users; in the case of the Acme Bitcoin Exchange, if Alice and Bob both deposit funds, they now have competing claims on the limited supply of BTC the exchange actually has, and it’s quite possible that both claims can’t be satisfied simultaneously even though they are equally valid. Unsurprisingly, almost all financial systems are rivalrous because the whole point of finance is to manage conflicts over limited resources.

Conventional cryptography is ill-equipped to deal with rivalry. Encryption has little, if anything, to do with the problem. Cryptographic signatures are good at telling you a message is authentic - a signature can prove to Alice that Bob really did sign a contract selling her his house - but a signature by itself tells you nothing about what other authentic messages might also exist - Bob may have also sold that same house to Charlie.

With commitments we took a small - but important - step towards fixing that problem: we can now create cryptographic proofs linking many different message together (commonly referred to by the overused term “blockchains”). The trees we discussed in the nested commitments section made those proofs efficient, by limiting where different messages could be in the overall data structure.

But commitments still require users of a system to somehow come to consensus on some “root” commitment every time the data changes. So we came up with single-use-seals, a “post-crypto” slight-of-hand that models something akin to a magical time-travelling commitment, reducing the problem to coming to consensus on a genesis seal.

What we didn’t talk about is how to actually implement a single-use-seal; we just assumed that Bitcoin works. While a full discussion is out of scope for this article, I’ll leave you with this: under the hood Bitcoin is itself just a bunch of commitments called “the blockchain”, and the exact data structure isn’t even particularly good (something I’ll cover in another blog post).

The magic in Bitcoin is simply the fact that there’s an effective mechanism - the proof-of-work and economic incentives underlying it - to determine which commitment - which blockchain - to use as the root consensus. Secondly, once consensus is reached, proof-of-work makes changing that consensus provably expensive in a way that’s tied to physics itself.

Bitcoin isn’t the only possible way to do this, but regardless it and systems like it all share something in common: In conjunction with commitments and single-use-seals we can use them as consensus amplifiers, allowing us to leverage a bit of consensus on one system to efficiently provide consensus for a whole world of other systems.

Footnotes

  1. Remember that there may be non-technical impediments to spending those funds, e.g. a court ordering funds to be frozen under penalty of imprisonment.

  2. In other words, the funds are uniquely committed to the Acme Bitcoin Exchange; methods to do this include pay-to-contract-hash pubkey derivation and special P2SH redeem scripts.

  3. Publishing on a commonly used page rather than a special URL makes it harder to selectively publish different commitments to different audiences without being detected by increasing the diversity of the readership.

  4. Deterministically deriving the blinding nonce from the secret key and txout is often convenient.

  5. If we don’t commit to the nonce value in the transaction, multiple seals can be created that refer to the same txout, and can all be validly closed simultaneously over a single message; put another way you’ve simply kept the seal secret, rather than properly committing to it.

  6. In fact, I strongly considered calling “Single-Use-Seals” by the name “Lazy Commitments” by analogy to lazy evaluation when I first came up with the concept.

  7. If you’re unfamiliar with Rust, traits are basically definitions of interfaces that types can implement; they’re roughly equivalent to base classes.