sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
<Taek>
if I understand the scheme fully, it encourages the miners to prefer taking all fees oob, but it encourages users to pay all fees on-chain using the mechanism that could get them a discount
<Taek>
and if a miner is unable to take certain fees oob, then they have to sacrifice all potential revenue from users that are using on-chain fees
marcoagner has quit [Quit: WeeChat 1.0.1]
<Taek>
I guess you could end up with an equilibrium where X% of blocks are fully oob, and then the rest are on-chain fees
<Taek>
but then if you are paying oob, you know you can only get into blocks X% of the time
<Taek>
well, same with on-chain too. If oob is >>50%, then it's probably something that would perpetuate
pro has joined #bitcoin-wizards
techguy305 has joined #bitcoin-wizards
<techguy305>
hey
techguy305 has left #bitcoin-wizards [#bitcoin-wizards]
punindented has quit [Remote host closed the connection]
pro has quit [Quit: Leaving]
Belkaar has quit [Ping timeout: 240 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Belkaar has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 248 seconds]
luke-jr has quit [Ping timeout: 246 seconds]
jb55 has quit [Ping timeout: 240 seconds]
jb55 has joined #bitcoin-wizards
luke-jr has joined #bitcoin-wizards
priidu has quit [Ping timeout: 240 seconds]
BashCo has joined #bitcoin-wizards
<maaku>
gmaxwell: I'm not sure why you're not seeing the all-or-nothing as an advantage, not a weakness. that's the argument from the other side -- it discourages out of band fees existing alongside regular fees
<maaku>
you build a block containing either one or the other -- regular fees or out-of-band-payments. not both. not some of each.
<maaku>
and in that model, it's the user incentive not to do out of band fees, because that only works if everyone does it, and if everyone does it it is strictly worse (because no rebates) than if everyone used regular fees
Ylbam has quit [Quit: Connection closed for inactivity]
_whitelogger has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 258 seconds]
dnaleor has quit [Quit: Leaving]
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 260 seconds]
CryptAxe has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
BashCo_ has quit [Ping timeout: 248 seconds]
Emcy has quit [Ping timeout: 248 seconds]
jb55 has joined #bitcoin-wizards
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
jb55 has quit [Ping timeout: 248 seconds]
jimmysong_ has quit [Read error: Connection reset by peer]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
[7] has quit [Ping timeout: 258 seconds]
TheSeven has joined #bitcoin-wizards
jb55 has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 240 seconds]
TheSeven has quit [Ping timeout: 246 seconds]
TheSeven has joined #bitcoin-wizards
Letze has quit [Remote host closed the connection]
Letze has joined #bitcoin-wizards
jb55 has joined #bitcoin-wizards
CheckDavid has joined #bitcoin-wizards
onabreak has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
c0rw1n_ has quit [Ping timeout: 258 seconds]
<luke-jr>
maaku: updated the BIP draft & code with your suggestions BTW
_whitelogger has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
deusexbeer has quit [Ping timeout: 246 seconds]
deusexbeer has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
CheckDavid has quit [Quit: Connection closed for inactivity]
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
CheckDavid has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
luke-jr has quit [Excess Flood]
luke-jr has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 248 seconds]
BashCo has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 258 seconds]
rusty has quit [Ping timeout: 258 seconds]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
jtimon has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
pr0zac- has quit []
Chris_Stewart_5 has quit [Ping timeout: 248 seconds]
jtimon has quit [Ping timeout: 258 seconds]
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 240 seconds]
dnaleor has quit [Ping timeout: 248 seconds]
BashCo_ has quit [Ping timeout: 260 seconds]
meshcollider has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
eck has quit [Ping timeout: 248 seconds]
eck has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
c0rw1n_ has joined #bitcoin-wizards
CheckDavid has quit [Quit: Connection closed for inactivity]
daszorz has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Read error: No route to host]
dnaleor has quit [Quit: Leaving]
daszorz has quit [Ping timeout: 258 seconds]
Emcy_ has quit [Quit: Leaving]
Emcy has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
dnaleor has quit [Ping timeout: 258 seconds]
meshcollider has quit [Quit: Connection closed for inactivity]
dnaleor has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
arowser has quit [Quit: No Ping reply in 180 seconds.]
arowser has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
PaulCapestany has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
laurentmt has quit [Quit: laurentmt]
AaronvanW has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
<maaku>
luke-jr: I was going to suggest moving the 520 push limitation too, but unfortunately that's enforced for all witness types :(
<maaku>
It's only there because of implementation issues that could fully be resolved in script, and I don't know why it would exist for non-script witness types
dnaleor has quit [Quit: Leaving]
Aranjedeath has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
<luke-jr>
maaku: eh, no it isn't?
dnaleor has quit [Quit: Leaving]
adiabat has quit [Ping timeout: 240 seconds]
<sipa>
maaku: no, it's not
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 258 seconds]
Aaronvan_ has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
<maaku>
sipa: explain?
<maaku>
there's no opcodes that modify large stack operations. DUP could have reference counting semantics
<maaku>
*large stack items
MaxSan has joined #bitcoin-wizards
<sipa>
maaku: ?
daszorz has joined #bitcoin-wizards
<sipa>
the 520 byte limit only applies to witness v0
<sipa>
and not to the p2wsh program, only to its initial stack
<maaku>
outside of DUP bombs, which are solved by reference counting instead of duplicating, I don't know of any way a single 520kB push is any worse than 1,000 520b pushes, other than filling the script with repeated dup/hash, which can be trivially prevented with hash limits based on witness size
BashCo has joined #bitcoin-wizards
<maaku>
sipa: Ah, you're right. I misread VerifyWitnessProgram when I looked into this earlier.
<sipa>
the main reason for the limit is that there is no use for large data elements - for now
BashCo_ has quit [Ping timeout: 240 seconds]
dnaleor has joined #bitcoin-wizards
<sipa>
and with the program itself no longer falling under that limit, even more so
intcat has quit [Remote host closed the connection]
<maaku>
It's possible tail-call scripts might want larger than 520 byte subscripts. Possible; I don't know of any examples. MAST itself reduces the maximum subscript size needed considerably.
<maaku>
But a stronger justification is Merkle branch proofs, for which 520 bytes is quite limiting
intcat has joined #bitcoin-wizards
<sipa>
i realized yesterday that if you have a sufficiently large merkle tree, an rsa accumulator would be more efficient instead, to produce set inclusion
<maaku>
any idea what that cutoff woul be?
<sipa>
in size, probably at 24 levels
<maaku>
*would be; and can you compactly prove multiple elements?
<sipa>
yes!
<sipa>
constant size
<sipa>
it's also much more cpu intensive to verify...
<sipa>
if you use 3072-bit arithmetic (~128 bit security), i think the proof would be 768 bytes
<luke-jr>
do we need new opcodes still?
<luke-jr>
and are they expensive enough that we lose the "don't need to count sigops" property?
<maaku>
Ok, FWIW my back-of-the-envelope calculation is that for a 256-depth tree (the highest I can reasonably imagine supporting, unless we want 384 for quantum resistance in the hash presumably used as key), the worst case proof of 1,000 items (stack size limit) is ~100kB with our 3 bit bitfield format
dnaleor has quit [Quit: Leaving]
<maaku>
sipa: that proof would be constant size right? this hypothetical RSAACCUMULATORVERIFY opcode would take N items or hashes from the stack, a 768 byte proof, and a 3072 bit accumulator?
<maaku>
I should go learn how RSA accumulators work, this is a gap in my knowledge :\
<luke-jr>
maaku: the per-input hashing limit seems potentially controversial :/
<maaku>
Proving one element from a 384-depth MBV is 12,434 bytes. One element from a 256-depth MBV is 8,289 bytes. I would be comfortable with a 12.5kB limit in a strawman proposal.
<maaku>
luke-jr: how so?
<maaku>
luke-jr: my thinking is that there isn't really reason to hash something more than a small constant factor, even if we had CAT or CAT-and-HASH opcodes
<sipa>
maaku: so you (the prover) choose two primes p q, with n=p*q a 3072-bit number; you also choose a generator g (which can be a small number, i think 65537 is often used)
<sipa>
then you compute for element in your set g^H(element) (where H is a 3072-bit hash)
<maaku>
e.g. hash tree validation, in script rather than MBV, is absolutely constrained to < 2 * size of leaf hashes + data
<maaku>
i can't think of a reason you'd hash more than that, other than purposeful attack, but maybe my imagination is limited
<sipa>
wait, no, you compute ((g^H(el1))^H(el2))^H(el3) ...
<sipa>
which is efficient if you know p and q
<sipa>
if i want to prove e1 belongs to the set, i reveal H(el2)*H(el3) mod (p-1)*(q-1)
<sipa>
and n
<sipa>
maaku: so i think the CPU time for verifying a proof is proportional to the number of elements you're proving
<sipa>
(one modular exponentiation for each)
dnaleor has joined #bitcoin-wizards
dnaleor has quit [Client Quit]
<sipa>
maaku: so OP_RSAACCUMULATORVERIFY would take N items from the stack, a 3072-bit modulus, a 3072-bit exponent, and a 256-bit hash of the expected result
BashCo has quit [Ping timeout: 248 seconds]
BashCo_ has joined #bitcoin-wizards
<andytoshi>
rsa accumulator proofs can be forged by the person who knows p and q can't they? i don't understand how these can be used on a blockchain
<sipa>
andytoshi: the receiver chooses p and q
<sipa>
and p*q is part of the proof
<andytoshi>
right, that's how these are usually used but for MAST there isn't really a receiver
Dizzle has joined #bitcoin-wizards
<sipa>
andytoshi: the signer is the receiver
<maaku>
sipa: ah, i see. thank you for the explanation
<sipa>
andytoshi: right, this may break down in case there are multiple parties involved
<sipa>
it may only work if there is a single coordinator who is involved in every branch
<andytoshi>
right, and that coordinator has the ability to take the coins (and can't provably eliminate this ability)
<sipa>
right
<maaku>
sipa: :( -- large key thresholds are something I was hoping to achieve here
<maaku>
eg. 18 of 30
meshcollider has joined #bitcoin-wizards
<sipa>
andytoshi: unless trusted setup :(
<sipa>
so for this to work we really only need a group of unknown size... it's not needed that there is anyone who can construct an inverse
<andytoshi>
sipa: sure. so fwiw this setup is super easy to split across multiple parties. there are use cases for this but they're more limited than those for MAST
<andytoshi>
otoh you can do weird things like have n parties agree on a bunch of spending conditions (like various thresholds, timelocks etc) and later they can actually add coniditions if they all cooperate
<andytoshi>
sipa: right, that too. you can use a UFO (but those are super big) or satoshi's pgp key or something
<sipa>
having one party that has p and q makes constructing the proof and the 'root' massively cheaper, though
<andytoshi>
yes. the size of the both is linear in the number of participants in the setup
<andytoshi>
unless there is some prime-splitting black magic i have never heard of
<andytoshi>
the setup i'm thinking of is that everyone choses a modulus, and the product of everyone's modulus is used as n, to be clear
<sipa>
but that makes n much larger?
<andytoshi>
yes, its size is linear in the number of participants
<sipa>
yes, then it doesn't solve much :)
<andytoshi>
heh. yeah :/
<sipa>
i guess it could, if you want to do 18-out-of-30, there are only 30 participants
<sipa>
not 30 choose 18
<sipa>
but still... you're not going to beat a merkle tree then
jb55 has joined #bitcoin-wizards
intcat has quit [Ping timeout: 248 seconds]
intcat has joined #bitcoin-wizards
Dizzle has quit [Quit: Leaving...]
adiabat has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
dnaleor has joined #bitcoin-wizards
<gmaxwell>
andytoshi: MPC construction of RSA numbers isn't that horrible.
Aranjedeath has quit [Ping timeout: 248 seconds]
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
Aranjedeath has joined #bitcoin-wizards
priidu has quit [Remote host closed the connection]
pro has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
Aranjedeath has quit [Ping timeout: 264 seconds]
Guest68082 is now known as [Derek]
[Derek] has quit [Changing host]
[Derek] has joined #bitcoin-wizards
vicenteH` has quit [Read error: Connection reset by peer]
jtimon has quit [Ping timeout: 240 seconds]
vicenteH has joined #bitcoin-wizards
Dizzle has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
Aranjedeath has joined #bitcoin-wizards
AaronvanW has quit []
laurentmt has quit [Quit: laurentmt]
dnaleor has joined #bitcoin-wizards
meshcollider has joined #bitcoin-wizards
daszorz has quit [Read error: Connection reset by peer]
Aranjedeath has quit [Quit: Three sheets to the wind]
<maaku>
luke-jr: I would let v1,20-byte be the hash160 of a script in your proposal
<luke-jr>
maaku: I thought someone cryptographically-smart decided that was too dangerous for scripts?
<maaku>
there's no need for a v1 upgrade to P2WPKH, and thare are potentially legitimate use cases where 160 bits are sufficient
<maaku>
luke-jr: it's a foot-gun protection
<luke-jr>
are there legitimate use cases, though?
<maaku>
the _general_ recommendation is that you use a 256-bit commitment because in the case of a multi-party script construction you're still secure by default without doing anything extra -- worst they can do is reduce security down to 128 bits
<luke-jr>
hmm
<maaku>
by, e.g., grinding a nonsense public key for a hash collision
<maaku>
but if you are the only party signing a script, but you're using a script instead of P2WPKH because you have more complex policy requirements (CLTV/CSV, multi-key but you own all the keys in different physical HSMs, etc.)
<maaku>
... then it is safe to have a smaller commitment. 128bit would be fine, but we seem to prefer hash160 over a 16-byte truncated hash, so _shrug_
<maaku>
Or, if you do some sort of setup step where people sign the keys they intend to use, the keys are delinearized, and there is no other source of data like a hash primage, etc.
<sipa>
as long as there is no P2WPKH-like construction that is Schnorr like, 160 bits is probably enough
<sipa>
and a direct pubkey v1 version could be added later
<maaku>
Having a 32-byte commitment by default is necessary to avoid inexperienced people doing dumb things. But it would be nice to save 12 bytes when you can
<maaku>
with proper warning labels and such
<sipa>
well instead of 32-byte hash P2WPKH, there should just be a direct pubkey in the output
<maaku>
sipa: why was non-20, non-32 segwit commitments treated as invalid instead of return true?
<sipa>
maaku: a mistake
<maaku>
ok
<maaku>
then yes, the signature aggregation patchset could later define v1,33-byte as a serialized pubkey using the new scheme, so long as we don't make that same mistake
<sipa>
indeed
<luke-jr>
tempting to try to shove a SHA3 opcode in, but that seems too much XD
<luke-jr>
and annoying to review since the final SHA3 and draft Keccak are incompatible
<sipa>
i think that can perfectly well be done independently later
<luke-jr>
right, that too
<luke-jr>
since we're ignoring sigops all over the place anyway, I'm just going to drop at least the per-script sigop limits..
<luke-jr>
are witness v0 sigops counted toward the block limit right now? (where?)
<sipa>
yes
<sipa>
there is a concept of sigop weight, with a limit of 80000 per block
<sipa>
there are per-script sigop limits?
<sipa>
there is a 201 per-script opcode limit
<sipa>
but that applies to all non-push opcodes, not just sigops