Stanford BPASE 2018 Day Three
2018 . 05 . 10
...
You can find the program for the conference and all slides and videos here. Notes for dayone are here, and daytwo here.
Table of Contents
Talk 1: Bulletproofs
Benedikt Buenz
http://crypto.stanford.edu/bulletproofs
initially designed to help with confidential txs, but can be applied to arbit computations
validity of btc tx:
 sig is correct
 inputs are unspent
 sum of inputs > sum of outputs. Difference > miner fees.
But is neither confidential (tx amounts not hidden) nor anonymous (can see addresses coming from and to).
Confidentiality is important e.g. for businesses to not reveal suppliers and customers.
Confidential Transactions idea:
 instead of sending amounts, we send cryptographiccommitments (which hides the actual values)
 e.g. Pedersen commitments: `Commit(x;r) = g^xh^r
 but then to check that sum of inputs >= sum of outputs, need to ensure that outputs are positive.
Confidential txs [Maxwell 2016]
 CT txes are structured like btc txes
 tx amounts are hidden
 tx graph is still public
 public verifiability of tx validity
To verify tx validity:
 use zeroknowledge proofofknowledge!
 peggy to victor: (prover to verifier):
 prover to verifier:
c = g^xh^r
is a commitment to a positive number x
 verifier: prove it
 verifier: here’s a challenge!
 prover and verifier do an interactive challengeresponse protocol
 peggy: here’s a response to prove it is positive and that Peggy knows it, but doesn’t tell victor what x specifically is
 uses Range Proof, x is in [0, 2^52]
NIZK: noninteractive zeroknowledge proof of knowledge
 more applicable to blockchains. In this, peggy creates the proof on her own, and can send the proof to victor or any public verifier.
Concrete rangeproof using bitcommitments
 idea: can represent the number in 52 bits
 peggy commits to all bits of number…explanation of Linear Range proof.
 for each bit of number, add a commitment
 and also develop a proof that:
 each commitvalue is in [0,1] i.e. is a “bit”
 and, these are “homomorphic commitments” i.e. satisfy the property that C(a) + C(b) = C(a+b), and so verifier that validate that their sum equals the commitment to the original value
Linear range proofs:
 based on sigmaprotocols with FiatShamir heuristic. This is what CT was originally proposed with.
 recent optimizations by Poelstra et al 2x improvement
 4kb for 64bit range proof —> way too large for a transaction
 linear in bitlength of range (bad)
 no trusted setup is needed (good)
Preprocessing SNARKs with Trusted Setup (GGPR ‘13)
 goal: reduce the size of the proof
 they precompute “queries” for the prover, and precompute “answers” for the verifier.
 prover computes short proof (always 188 bytes regardless of thing being proved), that is fast to verify.
 problematic: need to do setup. If malicious person does setup, then can be used to make “cheating proofs”.
 cannot prove that there was a malicious setup. Any bad behavior is undetectable at this point.
 can be alleviated by having multiple parties create the setup together, which is what ZCash did. But still have downsides.
 cannot disprove someone spreading FUD about a “bad setup”.
 low flexibility: any changes to the proofsystem needs new setup.
 proof time is k (constant) and so is verification time.
STARKS: CS Proofs (computationally sound) [BenSasson ‘17]
 Based on PCP theorem and FiatShamir heuristic
 no trustedsetup, but logsized proofs and verifications
 very elegant but not practical, because proofsize becomes really large: > 200kb proofsize, and prover overhead is massive (needs lots of RAM for 16bit circuit)
Bootle et al ‘16: logsized proofs for Arithmetic Circuits
 verification time is linear but proof time is logsized.
 interactive, multiround protocol
 publiccoin (verifier’s messages are random)
 for arbitrary arithmetic circuits
 assumption: discretelog, only
 proof size: O(log(n)) elements. This is pretty short. this is what we really care about in a replicatednetwork like a blockchain.
 proving and verifying is linear in circuit
 no proofs on committed values (important for range proofs)
Bulletproofs (also applies to MimbleWimble):
 improves on Bootle et al’s protocol
 can do proofs on committed values
 FiatShamir heuristic to create a NIZK
 has lots of good properties:
 relies on discretelog problem being hard (well tested)
 and can be used in any ellipticcurve problem, unlike SNARKS which rely on other assumptions beyond discretelog.
 proofsize:
 O(log(n)) elements for the rangeproof
 to prove that multiple outputs are in the range, bulletproof’s size increases very marginally compared to a linear rangeproof whose size will increase xN, for N outputs.
MultiParty Protocol for Bulletproofs
 its not common for multiple outputs in a transaction, so how can we incentivize this? CoinJoin!
 want it such that:
 can have multiple provers making a single proof without revealing their secrets to each other.
 trivial solution: concatenate the proofs, but that is linear again so not great.
 designed a multiparty computation protocol for bullet proofs: which lets one combine the proofs into a single one.
 works if circuits are disjoint i.e. n range proofs for n provers
 simply aggregate proofs in each round, and compute FiatShamir challege
 either log(n) rounds and log(n) communication
 or 3 rounds and O(n) communication
 This way CoinJoin helps with not just anonymity but also efficiency. There are economic incentives to adopt it!
Bulletproofs for CT or MimbleWimble
…insert image for comparing proof systems…
Applications:
 can use it for Solvency Proofs
 Mt Gox must prove they are solvent
 can provide a zeroknowledge proof that they are solvent
 doesn’t reveal what each customer has, or even what they have in total

with BP, proofsize goes down from 18GB > 60MB!
 for smart contracts:
 no trusted setup, for arbitrary computation
 proofs are short so tx size is kept small
 but verification time is linear, so may not be practical
 workaround: refereeddelegation model (what TrueBit uses).
 Protocol:
 Prover claims Proof is correct i.e. V(proof) = 1
 Lay out verification circuit, and name i’th gate V_i
 Challenger claims proof is invalid
 can do a binary search to find the divergence point in their claims
 Smart Contract just needs to verify the final gate
 Cost:
 O(log(n)) cpu to prepare proof
 O(log(n)) communication
 1 gate computation in the smart contract
 for verifiable shuffles:

set of senders (with emails, phones, btc addresses) > want to shuffle > and want to send to recipients
 found improvements when implemented in btcsecuritylib
 constant time prover
 fast verifier
 improving verification:
 if one unrolls the interactive protocol, then turns out one can verify with one big “multiexponentiation”
 well studied problem: it is sublinear N/log(N) i.e. gets better with bigger N
 BP are faster to verify than a SNARK (for small ciruit times)
 verifying takes 4ms. ECDSA sig verification is 5 times faster.
 batch verification also reduces down to doing one bug multiexponentiation
 4ms for each verification + 200mus for each additional proof
 implies is practical for btc in terms of verification time. So, no real barrier to add this to btc.
 other problems: quantum unsoundness, and some more.
Talk 2: Chainweb: a Braided ParallelChain PoW architecture for massive throughput
Will Martino, Stuart Popejoy: Kadena
ChainWeb:
 same energy, higher throughput, lower latency
Key Features:
 peer chains cross reference each other’s previous merkle roots
 trustless, destructive crosschain coin transfers through SPV at the smartcontract level
Prior Art:
 blockrope/betacoin
 crossreferencing chains twisted together
 GHOST/Decor+
 include orphaned header’s input for security
twostep trustless crosschain destructive coin transfers:
 delete coins on chain A. Specify:
 delete account on chain 1 and amount
 create chain and create acct
 “Create” requires a merkle proof of deletion
 smart contract runs spv, gets amount and acct from proof
 consume delete’s tx id
 use the concept of a “base graph” to estimate the size of graph made from N chains.
 “diameter”: distance between any two nodes.
 “merkle cones”: pretty neat idea that any nodes in the graph in the history or future cone can be checked with an efficient spv.
 security hypothesis:
 once a block’s future merklecone is formed, then a transaction is “confirmed”.
 considerations:
 configurable confirmation latency
 block time * basegraphdiameter
 bandwidth:
 heavy: whole chainweb block stream
 light: single chain
 light: only send headers for larger number of chains
 (headers carry the assurance)
 subset replication and mining:
 possible to mine subset of network
 role of large mining pools
 hashrate load balancers
 header stream network providers: hard for attacker. By withholding a block, prevents further mining since other previous headers in historycone are required.
 layer consensus providers: incentivized to have everyone see network as they see it to avoid misallocating their mining resources
 crosschain account transfers
 take the same amount of time (diameter) as a samechain transfer
 well formed Delete is enough for Bob to confirm the tx will occur, Create at Bob’s leisure (he knows its well formed and can do it whenever)
 Load balancing smart contracts
 crosschain transfer tools work for contract assets as well
 also see: Pact, smart contract language. nonturing complete (no recursion, etc.) and designed for nonprogrammers to write contracts (like people write excel formulas).
Talk 3: Mobius: privacy layer for ethereum
Rebekah Mercer
unlinkability: have many inputs which can give plausible deniability into who the sender was
approach 1: new currency
ZCash:
Dash: litecoin uses master node to do mixing in some way
monero: ring confidential txs
approach 2:
privacy overlay for an existing currency
 centralized
 naive solution: run a “bitcoin bath” in between senders and receivers. the “bath”
 but btcbath knows who the (sender, receiver) pair is!
 also, sender knows receiver’s address
 bad for: availability and theft. the btcbath can run away with the money!
 TumbleBit:
 creates two escrows (Alice to Tumbler, Tumbler to Bob)
 Tumbler doesn’t learn (Alice, Bob) pairing for the tx, only knows it talks to Alice and some other point to Bob.
 availability problem: if Tumbler goes down, money is not stolen but could be in limbo.
 lots of exchanges (txs cost $$$)
 decentralized
 Mixcoin, BlindCoin etc.
 CoinJoin:
 btc’s fav one.
 offchain: find other senders, and then share addresses to want to send to
 anonymity: senders learn who the receivers are. but receivers don’t know who the senders are.
 availability: if a large group of senders, then one sender could DoS this by claiming to intend to participate and at the last stage they could disappear.
 Xim:
 aim to reduce offchain communication, do onchain
 need to do 7 or so onchain txs
 mobius:
 main problem: entities participating need to do much coordination
 availability problem: built on ethereum so sidestep this problem by …
 anonymity: recipients can learn sender, but sender doesn’t know
 usecase: employer could pay wages but don’t know the employee’s addresses and so cannot monitor your use of money
 usecase: onboarding blockchain (passport etc). Exchange can link onchain address to offchain identity.
 only two messages to be exchanged ever (offchain) but online (need two messages per tx)
 ethereum
 normally, no privacy
 no local storage
 no nondeterministic execution
 no external lookup of data
 everything is expensive
 security is extremely important
 method
 smartcontract: senders deposit tx, and receivers withdraw tx
 sender tx: cannot specify recipient
 challenge 1: hide link between sender and receiver
 derive key:
 publish longterm master (public) key, instead of publishing address (hash of public key). The hash loses the nice algebraic structure that is exploited.
 others can derive child public keys for you
 only you can derive private key
 only one communication is needed per pair (ever).
 use DiffieHellman key exchange:
 sender generates a fresh random keypair: R = g^r
 recipient derives a longterm key pair: A = g^a
 the derived publickey = A.g^(H(A^r)), where H is a hash function
 note: the Hash could be a PRG which can derive more publickeys
 the derived privatekey = a + H(R^a)
 can have a publickey registry to avoid communication between aliceandbob
 senders use derived keys to deposit
 challenge 2: withdrawal must hide which receiver it is
 ring signature: three algos for setup, sign and verify
 receiver: need to prove that i deserve money
 zcash uses the blockchain via zksnarks to prove this
 in this limited setting, look at public keys that have money on them, receiver controls private key for one of them
 but ring sigs cannot be used to authorize money transfers, because sign step has private randomness which can make doublespending easy
 can use a “linkable ring signature”
 good summary slide at the end
Talk 4: Trustchain: micro economy for bandwidth tokens
John Pouwelse, Quintin Stokkink: Ledger Scientist
“TRIBLER: a social based peer to peer system”
Outline:
 science: produce trust with software
 overlay for torrentsearch and sharing
 distributed accounting system 2007today
 trustchain 10k tps
 microeconomy for bandwith tokens
 internet of trust for the real economy
currently trust is lockedin, where there is a reputation system owned by airbnb or uber
in the future, we’ll have a generic trust system
 “trustchain ietf” draft proposal for standardization (19 pages)
 scales horizontally, each person tracks just their transactions
 they don’t solve the doublespend problem
 end up building a network phonetophone that lets one run a reputation system ala uber or airbnb without having any central server
Talk 5: Dfinity: Threshold Relay
Timo Hanke, Dfinity
Whitepaper for consensus
goal for PoStake:
 fast consensus (5s): short block time, instant finality
 scalability (1m people)
 randomness:
 for scalability in terms of sharding.
 Also, expose randomness from consensus algo into app layer via an opcode.
 need it in consensus for leaderelection
 should be unpredictable, unmanipulatable.
 security (provable)
 no selfishmining, nothingatstake problems
Challenge 1: consensus and scalability
 tradeoff between finality and scalability
 e.g. PBFT chain: has finality after one block, but scales to only a few nodes
 pow chain: probabilistic finality over time, arbitrary many nodes
Challenge: randomness
1.derive randomness from chain?
* chain is manipulatable
* assumes everyone agrees on chain (but forkable!)
* hence:
* must not depend on chain, since it is “grindable”
* must not fork
 “last actor” bias:
* last actor has info advantage, can see randomness that may be output and could abort. e.g. one actor, and she needs to roll dice in cup, but could peek under it and see 6 and reject it.
 any fallback mechanism (after abort) introduces bias
 e.g.: miner discards block, commitreveal schemes (moved problem to when reveal happens that actor could be bad)
Challenge: Security  PoS attacks:
 causes of selfish mining and nothing at stake: sig are timeless and cheap.
 timeline > blocks can be withheld
 cheap > equivocate
Fundamental Observations:
 Obs 1: “threshold groups” have no last actor. a kofn threshold group have k actors who are necessary and sufficient.
 Obs 2: “consensus without consensus”:
 BLS threshold sigs
 private keys are split with groups. To combine, they make sigshares which then combine (handwave) without revealing full key
 BLS has all the following properties:
 distributed key generation: no trusted dealer required.
 not easy to do. Possible for discretelog systems, not easy for RSA or factoringbased systems b/c not easy to create a modulus that is product of two primes such that no individual member knows the two primes. In discretelog systems, the secret is a scalar element of Z mod p, which is easy to share with Shamirsecret sharing.
 unique: for every message only one signature verifies. Note: this doesn’t imply deterministic. True for RSA, but not true for most discretelog systems like ECDSA or Schnorr because they are randomized. When the system is initialized, one needs to pick some random k value, and so there are infinitely many signatures for each message.
 not deterministic: you could say in ECDSA one derives the kvalue from the message and the secretkey, but for the verifier it won’t work. Because to reveal this kvalue to the verifier would mean revealing the secret key.
 noninteractive: signature shares are created independently. Schnorr doesn;t satisfy this, but BLS does
 why “consensus without consensus”? the key generation process means all parties agree on something, and because it is unique it means they always agree on this message. Now, if the signature is the sourceofrandomness, then we’ve agreed on the random number.
 Obs3: Randomly sampled committees. Committeesize has ramifications, number of bad actors in the universe should be < 50%.
 Obs4: enforced publication
 notarization: majority signature done by a committee
 if a committee is a random sample of entire network > notarization is a proof of publication
 this notarization also serves as a timestamp, assuming each committee only active at a certain blockheight
 this scheme implies:
 blocks cannot be withheld
 impossible to build on old blocks.
 BUT: a block could get halfnotarized, if there is a timeout. An adversary can withhold sigshares, and hold back the notarization.
 to fix: have block ref previous notarization (rather than prev block itself). this results in just one withheld block but cannot have a withheld childchain.
q. how does one recover if a majority of validators is offline?
 assume majority is honest (implying online). Otherwise, system stalls until enough validators come online.
q. what are the tunable parameters?
this could be important when bootstrapping the network, or managing it over time as more participants join or leave.
 committee size
 block time:
rank blockmakers, because we want to give them a higher chance of submitting their block to the notaries.
q. fork choice rule?
 block maker needs to pick fork on which to build next block (can have various algos to weigh diff forks)
 notaries need to decide which of the two proposed blocks to confirm.
Second part, by Mahnush
Open Participation
 Until now, we’ve assumed everyone knows everyone’s publickeys and everybody knows the group publickeys.
 open participation: how do they regulate new participants joining?
 they define block epochs (a seq of blocks, bookended by two “key frame” blocks)
to join a group is hard:
 randomness of the chain defines new groups
 the group members run distributed key generation
 they join by providing their group public key
Challenge: how to agree on the group public key
solution: use the consensus mechanism of the dfinity chain at the current epoch to change the behavior of the system itself at future epochs
system contracts:
 are happening on the chain, and can manipulate the behavior of the system in the future.
 Most contracts require agreement, hence happening on the chain
 result will be used on;y on the side of a fork on which it is used
 examples:
 node registration
 group registration
 distributed key generation
 system parameters
 BNS
 DFN payment
DKG contract:
 for BLS we need signatures, so each person needs a signature
 (t, n) Distributed Key Generation: create a master public key and set of partial signing keys * previous studies:
 extensively studied in crypto literature
 most use pointtopoint communication
 assume or implement a reliable broadcast channel as a bulletin board. But because byzantine consensus is expensive, they cannot scale well.
 we use the Dfinity chain as the bulletin board
DKG phases:
 4 phases:
 dealing:
 share a secret value using a polynomial. Use Shamirsecret sharing
 create commitment to the polynomial
 encrypt the shares of each party and
 send the vector of shares to the contract
* all cryptoheavy steps are happening on the client, and chain only used for consensus.
 complain
 receive your share and commitment vector
 check validity of your share
 send your complaint to the contract if:
 no share received
 share was invalid
 justification
 send the share in cleartext to the contract. Everyone can check that it is valid.
* for each justification, the contract:
 checks if the share is valid
 if it is valid, it removes the complaint and accepts the sharing
 registration
 the group publickey is the sum of the verification vector of each successful dealer
 successful dealer: not have any unjustified complaints remaining
take away:
 system contracts are useful. Can be used to manage future behavior of the change
 carefully design so that heavy part of the code is clientside and only consensusparts are onchain
 only the data that need agreement over will pass to the contract
 contracts are eventdriven, instead of phasedriven
RapidFire Talks
Talk 6: Power Fault Tolerance: a new framing for consensus protocols
Juan Benet
Outline
 context:
 engineering protocol
 open problems
types of nodes: malicious, rational (need incentive), altruistic/honest (always follow protocol)
btc works even in presence of malicious nodes.
Introduce notion of proofs that data is stored.
current cloud is based entirely on replication.
currently users can lose data if the startup/company closes down.
what if: user owned data but could control who had access.
moreover: can we use incentives that enable renting space on harddrives.
modelled filecoin v2 paper after zerocash paper (zerocash was v2 of zerocoin)
filecoin is built on top of IPFS
stack:
 filecoin: decentralized storage network
 ipfs: dist web protocol
 ipld: auth data model and formats
 libp2p: modular p2p netoworking lib
Filecoin properties:
 must be a market
 must allow price undercutting
 must scale to ZB and beyond
 must provide all tiers of service
 good perf
 get rid of need for business frontend
Novel parts:
 decentralized storage network: need formalization for these protocols
 verifiable markets for storage and retrievable
 proofs of replication and proofs of spacetime
 useful proof of work for consensus
three characters:
 clients: store files, pay filecoin
 miners: store data for network collect filecoin
 network: organizes miners and clients
Network should constantly be requiring proofs of storage.
protocol needs blockchain for:
 currency, balances,
 market orders: bids, ask,
 allocations: which miners store what pieces
 proofs: verifiable record of correct beaviors
 contracts: state and execution of smart contracts
miner’s power is proportional to usefulstorage they provide network
markets for puts and gets can happen offchain, but for now is onchain to assist pricediscovery
type DSN interface {
Put(Data) Key
Get(Key) Data
Manage()
}
DSN properties:
 complete,
 secure if
 assures dataintegrity
 assures retrievability,
 tolerates management faults ((f, n)tolerant if f nodes accept n faults),
 tolerates storagefaults (f,m)tolerant if Put stores in m independent storages can tolerate f faults, where m «< n
 publicly verifiable
 auditable, via trace of operations
 incentivecompatible
ProofsofReplication & ProofsofSpacetime
 classifying the types of Proofsofstorage
 concept & a definition of proofsofreplication
 timebounded PoRep
 construction using CBC (expensive)
 concept and definition of Proofsofspacetime
 construction using proofchains
 compact construction using SNARKs
ProofsofSpace comprises ProofsofStorage, which comprises (PoRep, PoRet, ProofofDataPossession)
Security game for ProofsofStorage are of the form:
 Verifier sends to Prover: Setup(data)
 Verifier sends Challenge()
 Prover does proof < Prove(challenge, data); and sends proof
 Verifier: {0,1} < Verify(challenge, proof)
This is PDP (proof of data possession).
if proof can return data, then it is PoRet.
Problems:
 What if we want P to store 2 copies of data?:
* P could pretend to store 2 copies and only store one.
* simple fix: verifier preencrypts different copies
* but these preclude prover from repairing copies…
 What if we want P1…Pn to store 1 copy of data each? (Sybil attack):
* P1….Pn may be sybil identities or a coalition
* They could pretend to store 1 copy each, but deduplicate to store only 1.
 What if P could choose or determine the data?Generation Attack):
* concrete description: P could choose data such that P can generate the data ondemand. P then pretends to store the data, but regenerates it justintime to Prove challenges.
* hard to defend, but in DSN settings its very easy to do by aligning incentives.
* hard to avoid participation rewards to ensure Generation Attack would be irrational
ProofofReplication
 definition: a proving scheme where a prover P can prove to a verifier V that P is indeed storing a particular replica R^D of data D. No two replicas R^D_i and R^D_k can be deduplicated into the same physical storage.
 security game:
 init: verifier sends: setup(data, ek) and prover does: replica < Encode(data, ek)
 verifier sends “challenge”.
 prover does proof < Prove(challenge, replica) and sends proof
 verifier does {0,1} < Verify(challenge, proof)
 so, if there are two replicas on the same prover:
 init: verifier sends: setup(data, ek1, ek2), and prover does: r1 < encode(data, ek1); r2 < encode(data, ek2)
 verifier sends two challenges c1, c2
 prover makes p1, and p2 proofs and sends to verifier
 verifier does Verify(c1,p1) and Verify(c2,p2)
ProofofSpacetime
 how do we reduce frequency of verifications?
 ProofsofStorage require the verifier V to do frequent polling to ensure the prover P does indeed continue to store data D.
 intuitions:
 we can aggregate proofs and present them all at once
 we can use chaining to ensure proofs were produced sequentially, covering a span of time
 formally:
 a proving scheme that allows a prover P to aggregate ProofsofSpace(or ProofsofStorage) over time into an auditable record Proof that proves to a verifier V that P was indeed wasting space S (or storing data D) for a certain duration of time T.
 security game:
 verifier sends: Setup(data, r0)
 prover does:
 save data
 c0 < NextChallenge(r0)
 p0 < Prove(c0, data)
* two:
 c1 < NextChallenge(p0)
 p1 < Prove(c1, data)
* three:
 c2 < NextChallenge(p1)
 p2 < Prove(c2, data)
 verifier sends: poll & rechallenge r1
 c3 < NextChallenge(p2, r1)
 p3 < Prove(c3, data)
 prover sends: (p0, c0, …, (p3, c3)
 verifier does: {0,1} < Verify(c0,..c3, p0…p3)
 Note:
 This process represents an auditable proofschain
 can poll and add randomness to sequential computation. (Why?)
 compress: can aggregate the proofschain with a SNARK/STARK sp and just send sp as proof
See slides for:
 Storage Market
 Retrieval Market
 Filecoin Consensus and Power Fault Tolerance
 Secret Leader Election and Expected Consensus
 Storage Power Consensus: Useful ProofofWork for Consensus
 Open Problems
Users:
 IPFS is live
 dApps
 participants with large datasets: machine learning or scientific
Talk 7: Proof of Replication using Depth Robust Graphs
Ben Fisch
 system can internally ensure files are being stored
 PoStorage:
 proofs of data possession
 proofs of retrievability (similar to possession but with many queries can extract file)
 proofs of space: confirm that some resources are dedicated (could be junk!)
 proof of spacetime: storing space throughout period of time
Data Generation Attack:
 getting paid to store file, so generate junk data on the fly from some small seed on machine
 want proof: dedicating unique resources to storing data, even if can generate junk data
 this removes incentive to cheat, so no benefit to gening junk data
Crypto Definition
 PoRep.Setup(1^l, id, D) > R_id, commit_D
 setup generates replica R_id
 commit_D  (optional) commitment to data D.
 PoRep.Prove(R, id, c) > P_i
 takes a challenge c
 outputs proofofstorage of R_id
 PoRep.Verify(id, c, commit_D, P) > {0,1}
 Leads to an Extractor, proving proofofretrievability
 proofofspace: any snapshot (at time t) of the prover’s space must be of an appropriate size
 replication: can partition this snapshot into parts so that one can independently derive a replica of the original data.
 unfortunately, this is very hard to achieve in a cryptographic sense, because whatever strategy an honestprover uses to verify their snapshot, can be mimic’d be an adversary who stores the data+key and then generates the snapshot such that it has two partitions.
 so: assume a rational adversary. “Good” strategy satisfies strongreplication. For any adversary strategy, there is an efficient way to switch to a “good” strategy. Hence there is no real incentive to act bad.
Proofs of Replication:
 scalability: maintain security and perf for large files
 low communication: compact proofs (smaller than file size), and infrequent polling
 fast verification: low complexity verification, much faster than polling period / setup time.
Basic PoRep:
 main tool: verifiable timedelay encoding. Slow encoding, fast decoding.
 type of Verifiable Delay Function
 could do: AES(KDF(id), D) > R_id
 iterate many times
 slow to decode
 see Ben’s talk from daytwo for a faster way to do this
What about large files?
 encode separately each block
 apply erasure code to file before breaking blocks
 guarantees that if you haven’t deleted some data, can recover it
 verification: query for randomly sampled number of blocks to gain confidence that 90% of blocks aare being stored
 problem:
 initialization is expensive: each encoding takes a long time
 highly parallelizable for adversary
CBCstream encoding
 derive encoding on one block, and use as seed for next block
 adds sequentiality for each encoding, so can adjust the delay on each encoding (i.e. #iterations) so total time for N encodings remains the same
 verifier still randomly selects number of blocks and decodes
 BUT: adversary can delete half the blocks, and on the fly derive encodings from predecessar
Solution: use Depth Robust Chaining
Talk 8: TLSN: Nonrepudiation over TLS enabling Ubiquitous Content Signing
Hubert Ritzdorf
in TLS:
 Alice can get data from server,
 but cannot forward to Bob, because it is encrypted with symmetric key encryption between alice and server
may want to do so for e.g. for archiving.
better use case is: blockchain oracles
with smart contract on blockchain want to do something that requires on realworld data, and needs an external data source (called oracle) to help out.
requester/client <– TLS conversation (http session or else) –> generator/server <…..CA verifies identity of server to client to verify server identity
 can also have “verifier”(thirdparty/blockchain) that wants to learn something about the TLS conversation. (needs to trust CA)
 server sends “evidence” to client. Client makes proof from evidence and plaintext. client sends proof to verifier.
possible problems:
 requestresponse can suffer from content reordering issues. e.g. what is price of btc? and response can come in other order.
 privacy: usually send GET request to server. use access_token. added in plaintext with encryption. but now, this will be exposed.
 denial of service: if have 1 signature over everything. this may mean server gets very large state => DOS attack.
 redactability of proofs: if server has to decide what parts to redact. Means computational overhead on server => DOS attack.
goals:
 small server side state and overhead
 clientside privacy protection (client decides what parts to redact and which to keep after getting response form server)
 clear context > total order on requests
TLSN overview:
 start with TLS handshake.
 generate evidence: process small tls records with small state (on server). on client, needs to store all tls records and TLSN parameters from handshake
 client “returns evidence” to server
 server “signs: evidencegenerated + tls private key” + client’s evidence > sends evidence to client.
 client uses privacy settings to generate its proof, after any redactions it has done.
Talk 9: NuCypher KMS: Decentralized Key management system
MacLane Wilkison et al
whitepaper
Why?
 imagine if a sender (patient) is wanting to share data with multiple parties (doctors)
 encrypted multiuser chats
 encrypt every message for every participant. Doesn’t work for new participants who want to see history.
 share groupkey with everyone. But then one leak unravels security.
 decentralized netflix
 today, the CDN or other centralized services like S3 is trusted to have access to the files
Solution: proxy reencyption + decentralization
PRE (proxy reencryption)
 steps
 store file as C_A < encrypt(pk_A, m)
 send file to proxy as C_A
 proxy asks alice for rk_AtoB
 proxy sends to bob: c_B < reencrypt(rk_AtoB, C_A)
 this way proxy doesn’t get secret data, while bob sees data as if encrypted for him
Use threshold splitkey reencryption (Umbral)
 splitting works similar to Shamir keysplitting
 Umbral is spanish for threshold
 PRE properties: unidirectional, singlehope, noninteractive
 verification of reencryption correctness via Noninteractive ZK proofs of knowledge
used by:
 Medical
 MediBloc: https://medibloc.org/en/
 IRXO
 Medixain
 Wholesome
 IoT
 Spherity (with BigChainDB)
 decentralized marketplaces
 decentralized DBs