Proof of Assets For Crypto Custodians

blockchain

2019/05/15 发布于 技术 分类

blockchain  区块链 

文字内容
1. Proof of Assets For Crypto Custodians @jakecraige Crypto Engineering May 10, 2019
2. • We have access to the private keys Prove what? which control our funds • We have more assets than liabilities (customer balances)
3. Terminology ! Crypto Custodian ! Proof of Reserves (or Assets) ! Proof of Liabilities ! Proof of Solvency
4. History
5. History Bitcoin Whitepaper October 2008 2008 2009-2012 2013 2014 2015 2016-2017 2018 2019
6. History Maxwell & Todd discuss on IRC March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 2009-2012 2013 2014 2015 2016-2017 2018 2019
7. History Maxwell & Todd discuss on IRC March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 2009-2012 2013 2014 2015 Mt. Gox suspends withdrawals February 2014 2016-2017 2018 2019
8. History Maxwell & Todd discuss on IRC Provisions Paper August 2015 March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 2009-2012 2013 2014 2015 Mt. Gox suspends withdrawals February 2014 2016-2017 2018 2019
9. History Maxwell & Todd discuss on IRC Provisions Paper August 2015 March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 2009-2012 2013 2014 2015 2016-2017 2018 2019 Mt. Gox suspends withdrawals February 2014 MProve Paper December 2018
10. History Maxwell & Todd discuss on IRC Provisions Paper August 2015 March 2013 May 2013 October 2008 2009-2012 February 2019 Wilcox publishes details on blog Bitcoin Whitepaper 2008 Proof of Reserves 2013 2014 2015 2016-2017 2018 2019 Mt. Gox suspends withdrawals February 2014 MProve Paper December 2018
11. • Public Audit Our Options • Blockstream Proof of Reserves • Provisions: Proof of Solvency
12. Public Audit
13. Public Audit • Proof of Reserves • Sign a message with every address that has a balance • Send messages to auditor • Auditor verifies signature and balance on chain • Proof of Liabilities • Provide list of all customer identifiers and balances • Proof of Solvency • Auditor verifies sum of reserves is greater or equal to liabilities and publishes report
14. Maxwell Proof of Liabilities
15. Maxwell Proof of Liabilities • Proposed in 2013 from Greg Maxwell & Peter Todd • Allows custodians to build a proof that includes all customer balances where the customer can validate they are included in the proof.
16. Maxwell Proof of Liabilities
17. Proof of Reserves
18. Proof of Reserves • Proposal and tool released on February 4, 2019 by Blockstream • BIP-127: Simple Proof-of-Reserves Transactions • An unspendable transaction is the proof • Bitcoin Only
19. Proof of Reserves Unspent Outputs tx hash: abc amount: 1 tx hash: def amount: 2
20. Proof of Reserves Unspent Outputs Inputs tx hash: abc amount: 1 tx hash: def amount: 2 prev hash: abc amount: 1 prev hash: def amount: 2 Outputs
21. Proof of Reserves Unspent Outputs Inputs tx hash: abc amount: 1 tx hash: def amount: 2 Outputs amount: 3 prev hash: abc amount: 1 prev hash: def amount: 2
22. Proof of Reserves Unspent Outputs Inputs tx hash: abc amount: 1 prev hash: hash amount: 0 tx hash: def amount: 2 prev hash: abc amount: 1 prev hash: def amount: 2 SHA-256("Proof-of-Reserves: Custom Message") Outputs amount: 3
23. Proof of Reserves • BIP defines a standard that can be interoperable across wallets • No privacy. All outputs you own are revealed. • No proof of liabilities. The specification only covers reserves.* • Proof size is O(n) in the number of inputs *You could combine this with Maxwell’s Proof of Liabilities to have this
24. Provisions: Proof of Solvency
25. Provisions: Proof of Solvency • Paper published October 26, 2015 by Dagher et al • No production implementations • Uses ZK-proofs for privacy • Usable for any asset
26. Provisions: Proof of Solvency • Proof of Assets • Proof of Liabilities • Proof of Solvency • Zassets − Zliabilitities = 0 • Optional • Proof of Non-Collusion • Proof of Surplus
27. Provisions: Proof of Assets • Commitment to each public key and balance • Uses an anonymity set for privacy • Uses interactive sigma proofs • Made non-interactive with Fiat-Shamir transform • Proof size is O(n) in the number of public keys
28. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key
29. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾
30. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾 Public Key y = gx
31. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾 Public Key y = gx Knowledge of Private Key s ∈ {0,1}
32. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾 Public Key y = gx Knowledge of Private Key Balance Commitment s ∈ {0,1} b = g bal(y)
33. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾 Public Key y = gx Knowledge of Private Key Balance Commitment Pedersen Commitment s ∈ {0,1} b = g bal(y) p = bs ⋅ hv v ←$ ℤq
34. Provisions: Proof of Assets ZK commitment to balance and knowledge of private key Generators g, h ∈ 𝔾 Public Key y = gx Knowledge of Private Key Balance Commitment Pedersen Commitment Published Values s ∈ {0,1} b = g bal(y) p = bs ⋅ hv y, p v ←$ ℤq
35. Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier Prover Verifier
36. Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier Prover Verifier a1 = b u1 ⋅ h u2 u1, u2 ←$ ℤq
37. Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover a1 = b u1 ⋅ h u2 Verifier c ←$ ℤq Prover Verifier u1, u2 ←$ ℤq
38. Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover a1 = b u1 ⋅ h u2 Verifier c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier u1, u2 ←$ ℤq rv = u2 + c ⋅ v
39. Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover a1 = b u1 ⋅ h u2 Verifier c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 u1, u2 ←$ ℤq rv = u2 + c ⋅ v
40. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover a1 = b u1 ⋅ h u2 Verifier c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 u1, u2 ←$ ℤq rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1
41. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover a1 = b u1 ⋅ h u2 Verifier c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 u1, u2 ←$ ℤq rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1 c b u1+cs ⋅ h u2+cv = p ⋅ a1
42. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier a1 = b u1 ⋅ h u2 u1, u2 ←$ ℤq c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1 c b u1+cs ⋅ h u2+cv = p ⋅ a1 = (b s ⋅ h v)c ⋅ a1
43. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier a1 = b u1 ⋅ h u2 u1, u2 ←$ ℤq c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1 c b u1+cs ⋅ h u2+cv = p ⋅ a1 = (b s ⋅ h v)c ⋅ a1 = b cs ⋅ h cv ⋅ a1
44. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier a1 = b u1 ⋅ h u2 u1, u2 ←$ ℤq c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1 c b u1+cs ⋅ h u2+cv = p ⋅ a1 = (b s ⋅ h v)c ⋅ a1 = b cs ⋅ h cv ⋅ a1 = b cs ⋅ h cv ⋅ b u1 ⋅ h u2
45. p = bs ⋅ hv Provisions: Proof of Assets Verification of balance commitment Interactive Sigma Proof Prover Verifier a1 = b u1 ⋅ h u2 u1, u2 ←$ ℤq c ←$ ℤq Prover rs = u1 + c ⋅ s Verifier b rs ⋅ h rv = p c ⋅ a1 rv = u2 + c ⋅ v Verification Known = b, a1, c, rs, rv, p c b rs ⋅ h rv = p ⋅ a1 c b u1+cs ⋅ h u2+cv = p ⋅ a1 = (b s ⋅ h v)c ⋅ a1 = b cs ⋅ h cv ⋅ a1 = b cs ⋅ h cv ⋅ b u1 ⋅ h u2 b u1+cs ⋅ h u2+cv = b u1+cs ⋅ h u2+cv
46. Provisions: Proof of Liabilities • Commitment to each customer identifier and balance with range proof for positive amounts • Customer requests secret values from custodian and can verify their balance is in the proof. • Auditor* checks that sum of customer commitments is accurate • Proof size is O(n) in the number of customers *Can be anyone but likely some service due to the size of the proof
47. Provisions: Proof of Liabilities ZK commitment to balance
48. Provisions: Proof of Liabilities ZK commitment to balance Account Balance BinBalance = ⟨x0, x1, …, xb−1⟩ Balance = b−1 ∑ k=0 xk ⋅ 2k
49. Provisions: Proof of Liabilities ZK commitment to balance Account Balance Binary Commitment to Bits BinBalance for each bit = ⟨x0, x1, …, xb−1⟩ xk zk = g xk ⋅ h rk Balance = b−1 ∑ k=0 rk ←$ ℤq xk ⋅ 2k R= b−1 ∑ k=0 rk ⋅ 2k
50. Provisions: Proof of Liabilities ZK commitment to balance Account Balance Binary Commitment to Bits Commitment to Balance = ⟨x0, x1, …, xb−1⟩ BinBalance xk for each bit z= b−1 ∏ k=1 k zk(2 ) zk = g xk ⋅ h rk Balance = b−1 ∑ k=0 rk ←$ ℤq xk ⋅ 2k R= b−1 ∑ k=0 rk ⋅ 2k
51. Provisions: Proof of Liabilities ZK commitment to balance Account Balance Binary Commitment to Bits Commitment to Balance xk for each bit z= b−1 ∏ k=1 Customer Identifier = ⟨x0, x1, …, xb−1⟩ BinBalance zk = g xk ⋅ h rk Balance ∑ k=0 rk ←$ ℤq k zk(2 ) CID = H(user name n) = b−1 n ←$ {0,1}512 xk ⋅ 2k R= b−1 ∑ k=0 rk ⋅ 2k
52. Provisions: Proof of Liabilities ZK commitment to balance Account Balance Binary Commitment to Bits Commitment to Balance Published Values xk for each bit z= b−1 ∏ k=1 Customer Identifier = ⟨x0, x1, …, xb−1⟩ BinBalance zk = g xk ⋅ h rk Balance rk ←$ ℤq k ⟨CID, z0, …, zb−q⟩ ∑ k=0 zk(2 ) CID = H(user name n) = b−1 n ←$ {0,1}512 xk ⋅ 2k R= b−1 ∑ k=0 rk ⋅ 2k
53. Provisions: Proof of Liabilities Customer verification of balance commitment Request from prover (R, v, Balance)
54. Provisions: Proof of Liabilities Customer verification of balance commitment Request from prover Compute CID and verify it is in published data (R, v, Balance) CID = H(user name n)
55. Provisions: Proof of Liabilities Customer verification of balance commitment Request from prover Compute CID and verify it is in published data Compute balance commitment (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R
56. Provisions: Proof of Liabilities Customer verification of balance commitment Request from prover Compute CID and verify it is in published data Compute balance commitment Calculate prover commitment (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 ∏ k=0 k zk(2 )
57. Provisions: Proof of Liabilities Customer verification of balance commitment Request from prover Compute CID and verify it is in published data Compute balance commitment Calculate prover commitment Verify equality (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 ∏ k=0 zc = zp k zk(2 )
58. Provisions: Proof of Liabilities Customer verification of balance commitment Verification (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 ∏ k=0 zc = zp k zk(2 ) Known = R, v, balance, zk, …, zb−1 zc = zp
59. Provisions: Proof of Liabilities Customer verification of balance commitment Verification (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 ∏ k=0 zc = zp k zk(2 ) Known = R, v, balance, zk, …, zb−1 zc = zp g h = Balance R b−1 (2k ) z ∏ k k=0
60. Provisions: Proof of Liabilities Customer verification of balance commitment Verification (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 k zk(2 ) ∏ k=0 zc = zp Known = R, v, balance, zk, …, zb−1 zc = zp g h = Balance R = b−1 (2k ) z ∏ k k=0 ∏ k (g xk ⋅ h rk )(2 ) = ∏ k k g xk⋅2 ⋅ h rk⋅2
61. Provisions: Proof of Liabilities Customer verification of balance commitment Verification (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 k zk(2 ) ∏ k=0 zc = zp Known = R, v, balance, zk, …, zb−1 zc = zp g h = Balance R = b−1 (2k ) z ∏ k k=0 ∏ =g k (g xk ⋅ h rk )(2 ) = b−1 ∑k=0 xk⋅2k ⋅h b−1 ∏ ∑k=0 rk⋅2k k k g xk⋅2 ⋅ h rk⋅2
62. Provisions: Proof of Liabilities Customer verification of balance commitment Verification (R, v, Balance) CID = H(user name n) zc = g Balance ⋅ h R zp = b−1 k zk(2 ) ∏ k=0 zc = zp Known = R, v, balance, zk, …, zb−1 zc = zp g h = Balance R = b−1 (2k ) z ∏ k k=0 ∏ =g k (g xk ⋅ h rk )(2 ) = b−1 ∑k=0 xk⋅2k ⋅h = g Balanceh R b−1 ∏ ∑k=0 rk⋅2k k k g xk⋅2 ⋅ h rk⋅2
63. Provisions: Proof of Solvency ZK commitment to total assets ZAssets ⋅ ZLiabilitities −1 = ZAssets−Liabilities = 0
64. Provisions: Proof of Solvency ZK commitment to total assets Zassets = n ∏ i=1 pi Assets = n ∑ i=1 si ⋅ bal(yi)
65. Provisions: Proof of Solvency ZK commitment to total assets Zassets = n ∏ pi ∏ bisi ⋅ h vi = i=1 = Assets = n ∑ i=1 ∏ si ⋅ bal(yi) g bal(yi)⋅si ⋅ h vi
66. Provisions: Proof of Solvency ZK commitment to total assets Zassets = n ∏ ∏ bisi ⋅ h vi = i=1 = Assets = pi =g n ∑ i=1 n Assets ∑i=1 vi h ∏ si ⋅ bal(yi) g bal(yi)⋅si ⋅ h vi
67. Provisions: Proof of Solvency ZK commitment to total liabilities Zliabilities = c ∏ i=1 zi Liabilities = c ∑ i=1 Balancei
68. Provisions: Proof of Solvency ZK commitment to total liabilities Zliabilities = c ∏ i=1 = c ∏ i=1 zi g Balanceih Ri Liabilities = c ∑ i=1 Balancei
69. Provisions: Proof of Solvency ZK commitment to total liabilities Zliabilities = c ∏ i=1 = c ∏ zi Liabilities = i=1 =g ∑ i=1 g Balanceih Ri c c c ∑i=1 Balancei ∑i=1 Ri h Balancei
70. Provisions: Proof of Solvency ZK commitment to total liabilities Zliabilities = c ∏ i=1 = c ∏ zi Liabilities = c ∑ i=1 g Balanceih Ri i=1 c c =g ∑i=1 Balancei ∑i=1 Ri =g Liabilities ∑i=1 Ri h h c Balancei
71. Provisions: Proof of Solvency ZK commitment to assets - liabilities ZAssets ⋅ ZLiabilitities−1 = ZAssets−Liabilities
72. Provisions: Proof of Solvency ZK commitment to assets - liabilities ZAssets ⋅ ZLiabilitities−1 = ZAssets−Liabilities =g Assets ⋅h c ∑i=1 vi ⋅ (g c Liabilities ∑i=1 Ri −1 h )
73. Provisions: Proof of Solvency ZK commitment to assets - liabilities ZAssets ⋅ ZLiabilitities−1 = ZAssets−Liabilities =g Assets ⋅h c ∑i=1 vi ⋅ (g = g Assets−Liabilities ⋅ h 0 =g ⋅h c c ∑i=1 vi− ∑i=1 Ri c Liabilities ∑i=1 Ri −1 h c c ∑i=1 vi− ∑i=1 Ri )
74. Provisions: Proof of Solvency ZK commitment to assets - liabilities = g 0 ⋅ h sumv−sumr
75. Provisions: Proof of Solvency ZK commitment to assets - liabilities = g 0 ⋅ h sumv−sumr Prover creates proof of knowledge ZSolvency = h sumv−sumr = h excess
76. Provisions: Proof of Solvency ZK commitment to assets - liabilities = g 0 ⋅ h sumv−sumr Prover creates proof of knowledge Verifier checks proof of knowledge ZSolvency = h sumv−sumr = h excess … Schnorr Proof Verification
77. Provisions: Proof of Solvency ZK commitment to assets - liabilities = g 0 ⋅ h sumv−sumr Prover creates proof of knowledge Verifier checks proof of knowledge Verifier computes solvency ZSolvency = h sumv−sumr = h excess … Schnorr Proof Verification c n i=1 i=1 ZvSolvency = ∏ zi − ∏ pi
78. Provisions: Proof of Solvency ZK commitment to assets - liabilities = g 0 ⋅ h sumv−sumr Prover creates proof of knowledge Verifier checks proof of knowledge Verifier computes solvency Verifier verifies prover computation ZSolvency = h sumv−sumr = h excess … Schnorr Proof Verification c n i=1 i=1 ZvSolvency = ∏ zi − ∏ pi ZSolvency = ZvSolvency
79. Provisions: Summary • Scales linearly with respect to the proof size, construction and verification time. Protocol is easily parallelizable. • Does not reveal any information about addresses, total assets or customer balances. • If the public key has not been published on chain by including it in the anonymity set you would reveal it. • Generation & verification requires balance at a block hash oracle • No proposed standard that would be interoperable across companies
80. Open Questions • Committing to an address instead of public key • Proving cold storage assets • Optimizing proof size, generation and verification
81. In Summary
82. We’re hiring! coinbase.com/careers Thanks! • Maxwell Proof of Liabilities • https://web.archive.org/web/20171124195504/https://iwilcox.me.uk/2014/proving-bitcoin-reserves • Proof of Reserves • https://blockstream.com/2019/02/04/en-standardizing-bitcoin-proof-of-reserves/ • Provisions • https://eprint.iacr.org/2015/1008 • Demo Site: https://provisions.glitch.me • Rust Implementation: https://github.com/jakecraige/provisions • MProve • https://eprint.iacr.org/2018/1210 Jake Craige // @jakecraige