approximate_parameters()

[0xmountaintop]

vdf/vdf/src/proof_wesolowski.rs

Lines 69 to 89 in c740ef3

	/// To quote the original Python code:
	///
	/// > Create `L` and `k` parameters from papers, based on how many iterations
	/// > need to be performed, and how much memory should be used.
	pub fn approximate_parameters(t: f64) -> (usize, u8, u64) {
	let log_memory = (10_000_000.0f64).log2();
	let log_t = (t as f64).log2();
	let l = if log_t - log_memory > 0. {
	2.0f64.powf(log_memory - 20.).ceil()
	} else {
	1.
	};
	let intermediate = t * (2.0f64).ln() / (2.0 * l);
	let k = (intermediate.ln() - intermediate.ln().ln() + 0.25)
	.round()
	.max(1.);
	let w = (t / (t / k + l * (2.0f64).powf(k + 1.0)) - 2.0).floor();
	(l as _, k as _, w as _)
	}

I search for "approximat" in https://eprint.iacr.org/2018/623.pdf and it leads me to section 3.1 and section 4.3. However, none of them seems implying the logic in the above codes.

Why calculate l & k this way? Which part of the paper should I refer to?

[tyler-smith]

This memory optimization is broken. I haven't been able to dig in and figure out exactly how yet, but it's producing invalid proofs for t > 10_000_000.

Example:

~> vdf-cli 74b3961830935b83aa7802fc8332fb715590abcbaf3cf9fc0da4d45fd2639bfa 10000000 0029a8be4b9df217efc6cd16e208ad225f1cc71497b75b00391fd897bbb29e230e73e75243937125f883301ba562d89bbce246b20198759aa882e4444feb7533781d751a50bf97c8510533ea4f7ac169f565bb913a61240860a786294cbc8e358ed225b458894d30897d8a4c756924b897adf7eea3c974b4af11f6dd8c3552e678000cbc48be016b401aa0f40399c189ea63dded72ef19b0e6a10c5639e6a65a61fa37f7632cbbc1454992077bcf152e1d7981554d9e951a40da576d60ab39962425897401b63fe4ee37d22a69a6909da93ff37cb2b3efec9fab9fbf2ed9f6d40063f96bb170d911b5e7bbfc1eefed36087a90e7d1904b3fe88d07ee077d0f206f050013bc3c1dd06f01db0881e9d2238b827267b7af92205689c3246a6b7f8fa33f0c9c89d58146e6d3992d80e5b6a0cfbad780ce55d51bbfae72c0655e0419d1c60f64b5ca872c6689008b402ae2b0fd2efa694181fae59c5f8af0a15fae830b8d831b19f426522936ed7a71c894980934a88f7ac8fb36d098c26fcc3b62001d2244fffe2870e3d3bba732ac1fdeab067c30786515c2739ee91b4c8338df017569ee53aede60902228da60f4d7365d2aa77a9b3ded59475d8f4ff5506ac59d29f4103dae180388516e28f2baa62b4fddaabe14302445efaa6f031910667ab68a90bcd86b701964092330aaf186737d7611a3f794db0d6ba30cc51bdfc7cf74e59fffeb
Proof is valid

~> vdf-cli 74b3961830935b83aa7802fc8332fb715590abcbaf3cf9fc0da4d45fd2639bfa 10000001 002f8214ba82755fed1ca90ba40d616322d154dbcd5745891eb644f3424eaaec8f3dc4c9023df527c256c0328a8e0103e005104656d68f1b50da6c47b884d7f6c8b72f9a49b2b223c98f2006f9e8c89693d370b35d8775b1254196c89c0939c4ab1944ba3a3b48f24559db1d319ce935b6f4f10010b67606e1943d51ef53fba9a5001252f77072f0acdbab486eccc4dc7c691dab0376f7d57e31f7bc2ef3045e3c3292197dd1f92e723aaf48bff1f945fa92cc1bc7834c8dc321f579db10afcba95ff7c925a11346814eed8645b9dac24813892836fd427c222e5974c54693f33cf5810b10bc8d87659baf5fe9a2f6038dc623c96a3b30054ec7055e807b6155a74900226fe9bd4e3b8286adfd4f1c19db0b9994c22e27b7555dc3acecc155384a65446d7ab0e7b28e4c39a8eb96a06e1c936e95f6adb5200032f49544844b6247ff330faba402886601910a1e4f02719e3e59dba2b055dc9d5135b0025c694838d244c30be6760f2ad66fd602931e5113f28075550f2acb9cc4b8df2640033f10e2be001a243904f963333d208d89198a0fa40272a6ae421b8a69e2a75b8a265477a5f10cda8f89da30011aeeb5fde20f02d386d23c6039bf44f9d83a66fe6b110b9991b6db467a9abc179ec559664911c43aca2d68168995ae6bc2cda5a0fedebd6512a666658898d38dc32e0a234f10d74d8dd1d0f6db9ba51b590ec396218a4e36f3
Invalid proof

The first one is valid and the 2nd one isn't. Disabling this optimization by changing the code to fix l to 1. it begins generating valid proofs:

~> vdf-cli 74b3961830935b83aa7802fc8332fb715590abcbaf3cf9fc0da4d45fd2639bfa 10000001 002f8214ba82755fed1ca90ba40d616322d154dbcd5745891eb644f3424eaaec8f3dc4c9023df527c256c0328a8e0103e005104656d68f1b50da6c47b884d7f6c8b72f9a49b2b223c98f2006f9e8c89693d370b35d8775b1254196c89c0939c4ab1944ba3a3b48f24559db1d319ce935b6f4f10010b67606e1943d51ef53fba9a5001252f77072f0acdbab486eccc4dc7c691dab0376f7d57e31f7bc2ef3045e3c3292197dd1f92e723aaf48bff1f945fa92cc1bc7834c8dc321f579db10afcba95ff7c925a11346814eed8645b9dac24813892836fd427c222e5974c54693f33cf5810b10bc8d87659baf5fe9a2f6038dc623c96a3b30054ec7055e807b6155a749002644f58caad76ea7d4826d1b4da94932bd31ea72fbba4d82f54d364da56d8c3b0b3be90f28f4a3f7acb5f88668f1e957ae5ff3b73f7a88b08fbaf501f09dea38f1cd4d988978d21f6d2193ce67abc23df46426b413eacdf8b998e302999fffe3d93de49db6d27d1ac8dcf26458df56c52ec1a65f6137bec7a53421218676212cfff2ca5740ad5d0aa87e45017b2d02a2d0678bd613782d344b02bc0d8de8c7d7208ce8d9bf96ab22602cb750aed222e1adc6f40f7b31876ddd91840224f5e97008e783645c6fcc5df4f66f8377ea55d8eb4b5c4ed8f96f477b9e8b85b0e30ce7ddb60536e68db07816cc1ec1ff577f60091b8816b38c65d34c1324dbe8eb8bf7ab
Proof is valid