Preventing Consensus Fraud with Commitments and SingleUseSeals
While I’ve previously touched on the topics of commitments and singleuseseals, 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 singleuseseals 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 singleuseseals 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 illequipped to solve that problem.
Thanks goes to Christopher Allen/Alacrity Software for financially supporting this research.
Contents
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 cryptocurrency, Acme can cryptographically prove they have the technical^{1} 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 allocated^{2} 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 posttheft.
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 used^{3} 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 (stillprivate) 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 humanreadable merklesum 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
AE  345 BTC  81172c7b672cc7efc445f95314767501941057f785fd473fd42b637bdc70990c
FJ  940 BTC  73daa77f508a6969aed58a95c7f0ef2a5c2c50932bfea5374754db6537ccfa01
KO  195 BTC  bccab88791ffc367b465d045fd13d38a18f22d7bc6eaefe00a60a64f506ecd48
PU  526 BTC  dc64d99c3052e5e37380700bfef7f88a12ae33412a224ee91701153975d93715
VZ  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 PU; 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 singlelevel 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 humanrelevant 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 username.
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?
SingleUseSeals
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 SingleUseSeal, by analogy with the physical uniquely numbered singleuseseals commonly used to detect tampering during storage and shipment:
Each cryptographic singleuseseal is associated with a globally unique identifier. Singleuseseals 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 singleuseseal 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 singleuseseals seals; a singleuseseal 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.
TrustBased SingleUseSeals
The simplest form of singleuseseal is for closedseal proofs to be signaturebased 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 littleknown 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, nonrepudiable, 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 SingleUseSeals
Since transaction outputs are both uniquely identifiable, and can only be spent once, they can be used to implement singleuseseals that are just as secure as Bitcoin itself.
Let’s add singleuseseals 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/20161207/txproof976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt
$ bitcoincli verifytxoutproof `cat txproof976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.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/20161207/tx976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.txt
$ bitcoincli decoderawtransaction `cat tx976e842f944b797352a111893d766ce1b3b211d987d31e764a424ee19de10fe5.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/20161207/acmesolvencyproofdec2nd2016header.txt
$ sha256sum acmesolvencyproofdec2nd2016header.txt
d28a129cd4475132846a49f84a85fc8cad4330622a6a8103a3e8c446f3d9ae4c acmesolvencyproofdec1st2016header.txt
Now we can check that the header commits to the solvency proof:
$ cat acmesolvencyproofdec2nd2016header.txt
Solvency: 8c055d6890ab8b315618c3ba0c89ec83bc0291ae43c93ee0edc238b7865f09f3
Next Seal: c68fe1abc91e294c600911fc17db71ee627c9f3ad0fcf428c34fd1e804ed9859:0
$ wget https://petertodd.org/assets/20161207/acmesolvencyproofdec2nd2016.txt
$ sha256sum acmesolvencyproofdec2nd2016.txt
8c055d6890ab8b315618c3ba0c89ec83bc0291ae43c93ee0edc238b7865f09f3 acmesolvencyproofdec2nd2016.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 respend previously spent coins. In fact, I’ll even give you that wallet.
Defeating Miner Censorship
A potential issue with using Bitcoin to implement singleuseseals is miner censorship:
 Miners who learn the txout associated with the seal can censor transactions spending that txout.
 Miners can censor
OP_RETURN
outputs in general.
We can solve the first problem by making use of a blinding nonce that’s kept
secret^{4} 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))
instead^{5}. 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 paytocontracthash. 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.
SingleUseSeals for Globally Consistent, Updatable KeyValue 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: <peryear seal>
2017: <peryear seal>
2018: <peryear seal>
2019: <peryear seal>
2020: <peryear seal>
By month:
2016 Acme Exchange Solvency Proof Seals
=======================================
Jan: <permonth seal>
Feb: <permonth seal>
...
Nov: <permonth seal>
Dec: <permonth seal>
By day:
Jan 2016 Acme Exchange Solvency Proof Seals
===========================================
1st: <perday seal>
2nd: <perday seal>
...
31st: <perday 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 nary tree. Can we do better while keeping the code generic?
Fake SingleUseSeals
Recall that a singleuseseal 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 singleuseseals!^{6}
Concretely, a singleuseseal trait^{7} written in Rust might look like the following:
trait SingleUseSeal {
type ClosedProof;
fn verify(&self, &Self::ClosedProof, msg: &[i8]) > Bool;
}
A fake singleuseseal 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 subtrees of fake seals that commit to a smaller number of real seals. In short, we now have the equivalent of an nary 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 illequipped 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 singleuseseals, a “postcrypto” slightofhand that models something akin to a magical timetravelling commitment, reducing the problem to coming to consensus on a genesis seal.
What we didn’t talk about is how to actually implement a singleuseseal; 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 proofofwork and economic incentives underlying it  to determine which commitment  which blockchain  to use as the root consensus. Secondly, once consensus is reached, proofofwork 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 singleuseseals 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

Remember that there may be nontechnical impediments to spending those funds, e.g. a court ordering funds to be frozen under penalty of imprisonment. ↩

In other words, the funds are uniquely committed to the Acme Bitcoin Exchange; methods to do this include paytocontracthash pubkey derivation and special P2SH redeem scripts. ↩

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. ↩

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

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. ↩

In fact, I strongly considered calling “SingleUseSeals” by the name “Lazy Commitments” by analogy to lazy evaluation when I first came up with the concept. ↩

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