Proof of Assets For Crypto Custodians
登录发表评论
文字内容
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 20092012 2013 2014 2015 20162017 2018 2019
6. History Maxwell & Todd discuss on IRC March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 20092012 2013 2014 2015 20162017 2018 2019
7. History Maxwell & Todd discuss on IRC March 2013 Wilcox publishes details on blog Bitcoin Whitepaper May 2013 October 2008 2008 20092012 2013 2014 2015 Mt. Gox suspends withdrawals February 2014 20162017 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 20092012 2013 2014 2015 Mt. Gox suspends withdrawals February 2014 20162017 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 20092012 2013 2014 2015 20162017 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 20092012 February 2019 Wilcox publishes details on blog Bitcoin Whitepaper 2008 Proof of Reserves 2013 2014 2015 20162017 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 • BIP127: Simple ProofofReserves 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 SHA256("ProofofReserves: 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 ZKproofs 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 NonCollusion • 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 noninteractive with FiatShamir 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/provingbitcoinreserves • Proof of Reserves • https://blockstream.com/2019/02/04/enstandardizingbitcoinproofofreserves/ • 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
推荐

微博应对突发流量的一些经验分享 胡波 PH...
Cloudwu

拥抱TARS：构建PHP微服务生态 梁晨 ...
Cloudwu

PHP 机智问答 范圣佑 陈光贤 PHPC...
Cloudwu

一个团队的集体学习—陈雷 PHPCon2019
Cloudwu

代码解耦之道 黄朝晖 PHPCON2019
Cloudwu

消息服务中台实践 王晶 PHPCon2019
Cloudwu

破解云原生应用的可观测性 刘征 PHPCO...
Cloudwu

百姓日用而不知 庄表伟 PHPCON2019
Cloudwu

PHP在2345的业务实践 高旭 PHPC...
Cloudwu

PHP常驻进程编程需知 郭新华 PHPCO...
Cloudwu
分享